AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】——顺序表与链表

2024-08-13 26
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】——顺序表与链表

线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

  • 常见的线性结构：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就是说是连续的一条直线，但是在物理结构上并不一定是连续的，线性表在物理存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表从开始连续存储size个

顺序表时用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组数据存储，在数组上完成数组的增删查改。

顺序表一般分为：

1.静态顺序表

缺点：保存数据的数组较小不够使用，较大浪费

//静态顺序表
typedef int SLDateType;
#define N 10
struct Seqlist
{
  SLDateType a[N];
  int size;
};

2.动态顺序表

可以实现按需申请

  • 此时，如果free出现问题，原因可能是指针为野指针，指针未从初始地址释放或者指针越界
//动态顺序表
typedef int SLDateType;
struct Seqlist
{
  SLDateType* a;
  int size;
  int capacity;
};
  • 使用顺序表完成增删查改

seqlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1  
//头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
静态顺序表
//typedef int SLDateType;
//#define N 10
//struct Seqlist
//{
//  SLDateType a[N];
//  int size;
//};
//动态顺序表
//定义类型
typedef int SLDataType;
//设置初始容量
#define INIT_CAPACITY 5
typedef struct Seqlist
{
  SLDataType* a;
  //有效数据个数
  int size;
  //容量
  int capacity;
}SL;
//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//增
//后增
void SLPushBack(SL* ps, SLDataType X);
//前增
void SLPushFront(SL* ps, SLDataType X);
//插入
void SLInsert(SL* ps, int pos, SLDataType X);
//删
//后删
void SLPopBack(SL* ps);
//前删
void SLPopFront(SL* ps);
//中间删除
void SLErase(SL* ps, int pos);
//查
int SLFind(SL* ps, SLDataType X);
//改
int SLChange(SL* ps, SLDataType X,SLDataType Y);
//扩容
void SLCheckCap

seqlist.c文件

#include"seqlist.h"
//初始化顺序表
void SLInit(SL* ps)
{
  assert(ps->a);
  ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
  if (ps->a == NULL)
  {
    perror("Malloc fail");
  }
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}
//销毁顺序表
void SLDestroy(SL* ps)
{
  assert(ps->a);
  free(ps->a);
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
//打印顺序表
void SLPrint(SL* ps)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ",ps->a[i]);
  }
  printf("\n");
}
//后增
void SLPushBack(SL* ps, SLDataType X)
{
  assert(ps->a);
  SLCheckCapacity(ps);
  ps->a[ps->size] = X;
  ps->size++;
}
//后删
void SLPopBack(SL* ps)
{
  assert(ps->a);
  assert(ps->size>0);
  /*if (ps->size == 0)
  {
    return;
  }*/
  ps->size--;
}
//前增
void SLPushFront(SL* ps, SLDataType X)
{
  assert(ps->a);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end+1] = ps->a[end];
    end--;
  }
  ps->a[0] = X;
  ps->size++;
}
//前删
void SLPopFront(SL* ps)
{
  assert(ps->a);
  int begin = 0;
  while (begin >= 0 && begin < ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
//中间插入
void SLInsert(SL* ps, int pos, SLDataType X)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = X;
  ps->size++;
}
//中间删除
void SLErase(SL* ps, int pos)
{
  assert(ps->a);
  assert(pos >= 0 && pos <= ps->size);
  int begin = pos;
  while (begin >= pos && begin <= ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType X)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == X)
    {
      return i;
    }
  }
  return -1;
}
//改
int SLChange(SL* ps, SLDataType X , SLDataType Y)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == X)
    {
      ps->a[i] = Y;
      return 0;
    }
  }
  return -1;
}
//扩容
void SLCheckCapacity(SL* ps)
{
  if (ps->size == ps->capacity)
  {
    SLDataType* p = (SLDataType*)realloc((void*)ps->a, ps->capacity * sizeof(SLDataType)*2);
    if (p == NULL)
    {
      printf("Realloc fail");
      return;
    }
    ps->a = p;
    p = NULL;
    ps->capacity *= 2;
  }
}

main.c文件

#include"seqlist.h"
//测试顺序表
void TestSeqlist1()
{
  //定义顺序表
  SL s;
  //初始化顺序表
  SLInit(&s);
  //后增
  SLPushBack(&s,1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  //后删
  SLPopBack(&s);
  //打印
  SLPrint(&s);
  //前增
  SLPushFront(&s, 10);
  SLPushFront(&s, 20);
  SLPushFront(&s, 40);
  //打印
  SLPrint(&s);
  //前删
  SLPopFront(&s);
  //打印
  SLPrint(&s);
  //中间插入
  SLInsert(&s, 1, 6);
  //打印
  SLPrint(&s);
  //中间删除
  SLErase(&s, 2);
  //打印
  SLPrint(&s);
  //改
  SLChange(&s, 2, 9);
  //打印
  SLPrint(&s);
  
  //销毁顺序表
  SLDestroy(&s);
}
int main(void)
{
  //测试顺序表
  TestSeqlist1();
  return 0;
}

链表

了解完顺序表之后，可以明显发现顺序的缺点：

  • 中间与头部的插入删除，时间复杂度为O(N)
  • 增容需要申请空间，拷贝数据，释放旧空间，会有不小的消耗
  • 增容一般是呈2倍增长，会有一定的空间浪费

链表的概念

链表是一种物理存储的结构上非连续，非顺序的存储结构，数据元素的逻辑是通过链表中的指针链接次序实现的

注意：

1.链式结构在逻辑上是连续的，但是在物理上不一定连续。

2.现实中的结点一边拿都是从堆上申请出来的

3.从堆上申请的空间是按照一定的策略来分配的，俩次申请的空间可能连续，也可能不连续

链表的分类

  • 链表的分类大致分为：
    1.单向或者双向

2.带头或者不带头

3.循环或者非循环

其中最常用的是不带头单向非循环链表与带头双向循环链表

  • 不带头单向非循环链表：

结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等

  • 带头双向循环链表：

结构最复杂，一般用来单独存储数据，实际中使用的链表数据结构，都是双向循环链表

不带头单向非循环链表的实现

  • slist.h文件
#define  _CRT_SECURE_NO_WARNINGS 1  
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDatatype;
typedef struct SLinklistNode
{
  SLTDatatype date;
  struct SLinklistNode* next;
}SLTNode;
//增加结点
SLTNode* SLTNewNode(SLTDatatype X);
//打印
void SLTPrintf(SLTNode* phead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X);
//头删 
void SLTPopFront(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype X);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X);
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos ,SLTDatatype X);
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X);
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//销毁
void SLTDestory(SLTNode** pphead);
  • slist.c文件
#include"slist.h"
//打印
void SLTPrintf(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->date);
    cur = cur->next;
  }
  printf("NULL\n");
}
//新增加一个结点
SLTNode* SLTNewNode( SLTDatatype X)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->date = X;
  newnode->next = NULL;
  return newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X)
{
  //动态增加一个结点
  SLTNode* newnode = SLTNewNode(X);
  newnode->next = *pphead;
  *pphead = newnode;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
  //温柔
  /*if (*pphead == NULL)
  {
    return;
  }*/
  //断言
  assert(*pphead);
  
  SLTNode* first = *pphead;
  *pphead = first->next;
  free(first);
  first = NULL;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
  if (*pphead == NULL)
  {
    return;
  }
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//尾增
void SLTPushBack(SLTNode** pphead, SLTDatatype X)
{
  //新增一个结点
  SLTNode* newnode = SLTNewNode(X);
  SLTNode* tail = *pphead;
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->date == X)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{
  assert(pos);
  assert(pphead);
  if (*pphead == pos)
  {
    SLTPushFront(pphead, X);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = SLTNewNode(X);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (*pphead == pos)
  {
    SLTPopFront(pphead);
  }
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
}
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{
  assert(pos);
  SLTNode* newnode = SLTNewNode(X);
  newnode->next = pos->next;
  pos->next = newnode;
}
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}
//销毁
void SLTDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while(cur)
  {
    SLTNode* tmp = cur->NEXT;
    free(cur);
    cur = tmp;
  }
  *pphead = NULL;
}

带头双向循环链表的实现

Dlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1  
//带头双向循环链表的增删查改
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义类型
typedef int LTDataType;
//定义结构体
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}ListNode;
//创建一个返回链表的头结点（哨兵）
ListNode* ListCreate();
//双向链表的销毁
void ListDestory(ListNode* phead);
//双向链表的打印
void ListPrintf(ListNode* phead);
//创造一个newnode
ListNode* ListNewNode(LTDataType x);
//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x);
//双向链表的尾删
void ListPopBack(ListNode* phead);
//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x);
//双向链表的头删
void ListPopFront(ListNode* phead);
//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x);
//双向链表在pos前插入
void ListInsert(ListNode* phead, LTDataType x);
//双向链表在pos删除
void ListErase(ListNode* pos);

Dlist.c文件

#include"DList.h"
//创建一个返回链表的头结点（哨兵）
ListNode* ListCreate()
{
  ListNode* phead = ListNewNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//双向链表的销毁(需自行释放哨兵头)
void ListDestory(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    ListNode* tail = cur;
    cur = cur->next;
    free(tail);
    tail = NULL;
  }
}
//双向链表的打印
void ListPrintf(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  printf("->NULL->");
  while (cur != phead)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//创造一个newnode
ListNode* ListNewNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* newnode = ListNewNode(x);
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}
//双向链表的尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* tail = phead->prev;
  phead->prev = tail->prev;
  tail->prev->next = phead;
  free(tail);
  tail = NULL;
}
//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* newnode = ListNewNode(x);
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}
//双向链表的头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* first = phead->next;
  phead->next = first->next;
  first->next->prev = phead;
  free(first);
  first = NULL;
}
//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//双向链表在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* newnode = ListNewNode(x);
  ListNode* front = pos->prev;
  newnode->prev = front;
  newnode->next = pos;
  front->next = newnode;
  pos->prev = newnode;
}
//双向链表在pos删除(自行释放指针)
void ListErase(ListNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
}

顺序表与链表的区别

不同点 顺序表 链表
存储空间上 物理上连续 逻辑上连续，物理上不一定连续
随机访问 支持：O(1) 不支持：O(N)
任意位置插入或者删除元素 可能需要移动元素，效率低O(N) 只需要修改指针指向
插入 动态顺序表，空间不够需要扩容 没有容量的概念
应用场景 元素高效访问，频繁访问 任意位置插入和删除频繁
缓存利用率 高 低


文章标签：
存储
缓存
关键词：
数据结构链表
顺序表链表
数据结构顺序表链表
数据结构顺序表
大柏怎么被偷了
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
62 4
三三是该溜子
|
5天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
18 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
1月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
57 5
aliyun1622584902-46568
|
1月前
|
存储
顺序表和链表（2）
【10月更文挑战第23天】
aliyun1622584902-46568
63 2
顺序表和链表（2）
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
111 4
aliyun1622584902-46568
|
1月前
|
存储 算法 数据管理
顺序表和链表（1）
【10月更文挑战第22天】
aliyun1622584902-46568
33 2
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
34 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
41 2
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
50 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
73 0

热门文章

最新文章

  • 1
    【C语言】深入浅出：C语言链表的全面解析
  • 2
    Python编程数据结构的深入理解
  • 3
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 4
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 5
    Python 中的数据结构与其他编程语言数据结构的区别
  • 6
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 7
    Python 中的数据结构和算法优化策略
  • 8
    Python 中数据结构和算法的关系
  • 9
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 10
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 1
    【Python进阶（七）】——Series数据结构
    186
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1334
  • 3
    深入浅出数据结构之布隆过滤器
    72
  • 4
    数据结构/C++：位图 & 布隆过滤器
    48
  • 5
    数据结构/C++：哈希表
    84
  • 6
    数据结构/C++：红黑树
    46
  • 7
    数据结构/C++：AVL树
    49
  • 8
    栈的基本应用
    63
  • 9
    栈与队列理解
    49
  • 10
    数据结构/C++：二叉搜索树
    53

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)