顺序表和链表

🕗 发布于 2024-07-10 07:40 链表 数据结构 c语言

线性表

线性表在逻辑上是呈现线性结构，但在物理层面上不一定是连续的，常见的线性表有：顺序表，链表，栈，队列等等…
在这里插入图片描述

顺序表

顺序表是用一小段物理地址连续的存储单元依次存储数据的线性结构，一般情况下采用数组存储，一般可分为
静态顺序表（使用定长数组存储元素）

#define N 10
typedef int valuetype;
struct seqlist
{
valuetype arr[N];
int size;
};

动态顺序表（动态开辟的数组存储，空间不够可释放扩容）

typedef int valuetype;
struct seqlist
{
valuetype* arr;
int size;//有效数据个数
int capacity;//容量
};

静态顺序表较为不常见，我们下面来讨论动态的顺序表。

初始化

方法1：

void InitSeqlist(seqlist* psl)
{
psl->arr=NULL;
psl->size=psl->capacity=0;
}

不能只传结构体，因为函数内形参的初始化无法影响到外部的结构体，必须传地址。
方法2：

typedef int valuetype;
void InitSeqlist(seqlist* psl)
{
psl->arr=（valuetype*)malloc(sizeof(valuetype)*4);
if(psl->arr==NULL)
{
perror("malloc fail");
return;
}
psl->size=0;
psl->capacity=4;
}

销毁

void destroyseqlist(seqlist* psl)
{
psl->size=psl->capacity=0;
free(psl->arr);
psl->arr=NULL;//这里置空是可以影响到外面的结构体的，因为传参传的是指针
}

尾插

void push_back(seqlist* psl,valuetype x)
{
assert(psl!=NULL);
if(psl->size==psl->capacity)
{
(psl->capacity)*=2;//只能在使用初始化方法2时才能这样写，不然psl->capacity可能是0
free(psl->arr)；
psl->arr=(valuetype*)malloc(sizeof(valuetype)*psl->capacity);//也可以用realloc
if(psl->arr==NULL)
{
perror("malloc fail");
return;
}
}
psl->arr[psl->size]=x;
psl->size++;
}

头插

void push_front(seqlist* psl,valuetype x)
{
assert(psl!=NULL);
if(psl->size==psl->capacity)
{
(psl->capacity)*=2;//只能在使用初始化方法2时才能这样写，不然psl->capacity可能是0
free(psl->arr)；
psl->arr=(valuetype*)malloc(sizeof(valuetype)*psl->capacity);//也可以用realloc
if(psl->arr==NULL)
{
perror("malloc fail");
return;
}
}
for(int i=psl->size-1;i>=0;i--)
{
psl->arr[i+1]=psl->arr[i];
}
psl->arr[0]=x;
psl->size++;
}

尾删

void pop_back(seqlist* psl)
{
assert(psl!=NULL);
if(psl->size>0)
{
psl->size--;
}
}

头删

void pop_front(seqlist*psl)
{
assert(psl!=NULL);
if(psl->size>0)
{
for(int i=1;i<psl->size;i++)
{
psl->arr[i-1]=psl->arr[i];
}
psl->size--;
}
}

指定位置插入数据

void insert(seqlist* psl,int pos,valuetype x)
{
assert(pos>=0&&pos<=psl->size&&psl!=NULL);
if(psl->size==psl->capacity)
{
(psl->capacity)*=2;//只能在使用初始化方法2时才能这样写，不然psl->capacity可能是0
free(psl->arr)；
psl->arr=(valuetype*)malloc(sizeof(valuetype)*psl->capacity);//也可以用realloc
if(psl->arr==NULL)
{
perror("malloc fail");
return;
}
}
for(int i=psl->size-1;i>=pos;i--)
{
psl->arr[i+1]=psl->arr[i];
}
psl->arr[pos]=x;
psl->size++;
}//可以复用在头插/尾插

指定位置删除数据

void erase(seqlist* psl,int pos)
{
assert(pos>=0&&pos<psl->size&&psl!=NULL);
//assert(psl->size>0);//可有可无，因为上面那条断言就能把为0的情况判断出来
for(int i=pos+1;i<psl->size;i++)
{
psl->arr[i-1]=psl->arr[i];
}
psl->size--;
}//可以复用在头删/尾删

查找指定数据

int find(seqlist* psl,valuetype x)
{
for(int i=0;i<psl->size;i++)
{
if(psl->arr[i]==x)
return i;
}
return -1;//没找到
}

修改指定位置数据

void modify(seqlist* psl,int pos,valuetype x)
{
assert(pos>=0&&pos<psl->size);
psl->arr[pos]=x;
}

顺序表存在的问题

1.中间/头部的插入/删除时间复杂度是O(n)。
2.增容有时候要申请新空间，拷贝旧数据和释放旧空间，消耗大。
3.增容是以2倍或者1.5倍增长，势必会造成空间浪费。

链表

顺序表存在的问题，链表可以很好的解决。

链表的结构

typedef struct listnode
{
valuetype data;//数据
struct listnode* next;//结构体地址
}node;

链表的种类

可以对单向与双向，带头与不带头，循环或者非循环一起组成8种链表

无头单向非循环链表

结构简单，一般不会用来存储数据，而是作为其他数据结构的子结构，如哈希桶，图的邻接表等
在这里插入图片描述

无向单向非循环链表增删查改的实现

注意

malloc出来的节点需要free，否则会产生内存泄露，在函数里malloc产生的节点是不会释放的，只有free才能释放。

链表结构

typedef struct node
{
valuetype data;
struct node* next;
}node;

头插

void pushfront(node** pphead,valuetype x)
{
assert(pphead);
node* newnode=(node*)malloc(sizeof(node));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->next=NULL;
newnode->data=x;
newnode->next=*pphead;
*pphead=newnode;
}

尾插

void pushback(node**pphead,valuetype x)
{
assert(pphead);
node* newnode=(node*)malloc(sizeof(node));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->next=NULL;
newnode->data=x;
if(*pphead==NULL)
{
*pphead=newnode;
}
else
{
node* ptail=*pphead;
while(ptail->next!=NULL)
{
ptail=ptail->next;
}
ptail->next=newnode;
}
}

头删

void popfront(node** pphead)
{
assert(pphead);
assert(*pphead!=NULL);
node* fphead=*pphead;
*pphead=fphead->next;
free(fphead);
}

尾删

法1：

void popback(node** pphead)
{
assert(pphead);
assert(*pphead!=NULL);
if((*pphead)->next==NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
node* phead=*pphead;
while(phead->next->next!=NULL)
{
phead=phead->next;
}
node* tmp=phead->next;
free(tmp);
tmp=NULL//写程序的好习惯
phead->next=NULL;
}

法2：

void popback(node** pphead)
{
assert(pphead);
assert(*pphead);//无节点的情况
node* phead=*pphead;
if(（*pphead）->next==NULL)//节点仅有一个的情况
{
free(*pphead);
*pphead=NULL;
}
while(phead->next->next!=NULL)//节点数大于1的情况
{
phead=phead->next;
}
free(phead->next);
phead->next=NULL;
}

查找

法1：

node* find(node** pphead,valuetype x)
{
assert(pphead);
node* tmp=*pphead;
while(tmp)
{
if(tmp->data==x)
return tmp;
tmp=tmp->next;
}
return NULL;
}

法2：

node* find(node* phead,valuetype x)
{
node* tmp=phead;
while(tmp!=NULL)
{
if(tmp->data==x)
return tmp;
tmp=tmp->next;
}
return NULL;
}

在pos位置插入

void insert(node**pphead,node* pos,valuetype x)
{
assert(pphead);
assert(pos);
if(pos==*pphead)
{
newnode->next=*pphead;
*pphead=newnode;
}
else
{
node* newnode=(node*)malloc(sizeof(node));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->data=x;
node* tmp=*pphead;
while(tmp->next!=pos)
{
tmp=tmp->next;
}
newnode->next=pos;
tmp->next=newnode;
}
}

删除pos位置的节点

void erase(node** pphead,node* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if(pos==*pphead)
{
node* temp=*pphead;
*pphead=temp->next;
free(temp);
temp=NULL;
}
else
{
node* tmp=*pphead;
while(tmp->next!=pos)
{
tmp=tmp->next;
}
tmp->next=pos->next;
free(pos);
pos=NULL;
}
}

释放链表

void destroy(node** pphead)//也可以用一级指针，但要把头结点在外边置空，不然会造成野指针
{
assert(pphead);
assert(*pphead);
node* cur =*pphead;
node* after=cur->next;
while(after)
{
free(cur);
cur=after;
after=after->next;
}
free(cur);
*pphead=NULL;
}

带头双向循环链表

结构最复杂，一般用来单独存放数据，它也是实际当中最常使用的链表结构。
在这里插入图片描述

双向循环链表增删查改的实现

链表结构

typedef struct Dnode
{
valuetype data;
struct Dnode next;
struct Dnode prev;
}Dnode;

头结点刚开始的prev和next指针是指向自身的。

初始化

Dnode* Init(Dnode* phead)
{
phead=(Dnode*)malloc(sizeof(Dnode));
if(phead==NULL)
{
perror("malloc fail");
return NULL;
}
phead->next=phead;
phead->prev=phead;
return phead;
}

头插

法1：

void push_front(Dnode* phead,valuetype x)
{
assert(phead);
Dnode* newnode=(Dnode*)malloc(sizeof(Dnode));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->data=x;
phead->next->prev=newnode;
newnode->next=phead->next;
phead->next=newnode;
newnode->prev=phead;
}

法2：

void push_front(Dnode* phead,valuetype x)
{
assert(phead);
Dnode* newnode=(Dnode*)malloc(sizeof(Dnode));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
Dnode* first=phead->next;//这样就不需要关注顺序
phead->next=newnode;
newnode->prev=phead;
first->prev=newnode;
newnode->next=first;
}

尾插

void push_back(Dnode* phead,valuetype x)
{
Dnode* newnode=(Dnode*)malloc(sizeof())
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->data=x;
Dnode* ptail=phead->prev;
newnode->next=phead;
phead->prev=newnode;
ptail->next=newnode;
newnode->prev=ptail;
}

头删

法1：

void popfront(Dnode* phead)
{
assert(phead);
Dnode* first=phead->next;
if(first==phead)
return;
first->next->prev=phead;
phead->next=first->next;
free(first);
}

法2：

void popfront(Dnode* phead)
{
assert(phead);
Dnode* first=phead->next;
Dnode* second=first->next;
if(first==phead)
return;//也可以直接用assert，尾删同理
phead->next=second;
second->prev=phead;
free(first);
}

尾删

void popback(Dnode* phead)
{
assert(phead);
Dnode* ptail=phead->prev;
if(ptail==phead)
return;
ptail->prev->next=phead;
phead->prev=ptail->prev;
free(ptail);
}

查找

Dnode* Find(Dnode* phead,valuetype x)
{
assert(phead);
Dnode* cur=phead->next;
while(cur!=phead)
{
if(cur->data==x)
return cur;
cur=cur->next;
}
return NULL;
}

在pos位置前插入

void insert(Dnode* pos,valuetype x)
{
assert(pos);
Dnode* newnode=(Dnode*)malloc(sizeof(Dnode));
if(newnode==NULL)
{
perror("malloc fail");
return;
}
newnode->data=x;
Dnode* prev=pos->prev;
prev->next=newnode;
newnode->prev=prev;
pos->prev=newnode;
newnode->next=pos;
}//可以复用到头插尾插

删除pos位置的值

void erase (Dnode* pos)
{
assert(pos);
Dnode* prev=pos->prev;
Dnode* next=pos->next;
prev->next=next;
next->prev=prev;
free(pos);
}//可以复用到头删尾删

释放

void destroy(Dnode* phead)
{
Dnode* cur=phead->next;
while(cur!=phead)
{
Dnode* next=cur->next;
free(cur);
cur=next;
}
free(phead);//在外面对链表置空
}

原文地址：https://blog.csdn.net/2301_79127392/article/details/140159236

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【Linux】进程（9）：进程控制2（进程等待）
下一篇：关于美国服务器IP的几个常见问题

web前端开发--盒子属性
学院介绍
阅读更多2024-11-18
深度学习基础—Seq2Seq模型
decoder网络和编号4的语言模型几乎一模一样，机器翻译模型其实和语言模型非常相似，不同在于语言模型总是以零向量开始，而encoder网络会计算出一系列向量来表示输入的句子。假设输入猫咪图片，经过预
阅读更多2024-11-18
【第三章】Kubernetes资源与对象
文章目录1. Kubernetes资源介绍1.1 Pod1.2 Deployment1.3 Service1.4 Namespace2. Kubernetes资源实践2.1 部署应用2.2 访问应用2
阅读更多2024-11-18
SRT拥塞控制分析
在慢启动阶段，发送端会逐渐增加发送速率，直到网络出现丢包，这时会触发拥塞控制机制，减少发送速率。在拥塞控制中，如果网络出现丢包，发送端可能会增加数据包发送间隔，以减少网络拥塞。：拥塞窗口的大小，用于控
阅读更多2024-11-18
小红书内容推荐算法开发：利用API打造个性化用户体验
小红书，作为国内领先的内容分享社区，其丰富的用户生成内容（UGC）和独特的社区氛围，为推荐算法的开发提供了肥沃的土壤。通过小红书API获取的数据，我们可以构建用户兴趣画像和内容特征，进而实现个性化推荐
阅读更多2024-11-18
详解八大排序（一）------（插入排序，选择排序，冒泡排序，希尔排序）
在日常生活中，我们常常要将各种各样的数据进行排序，例如我要将班上的学生按照数学成绩从大到小的排序，像这种一般情况，编译器自带的sort函数就能满足我们的要求。但是，假如我要将班上姓刘的学生按照数学成绩
阅读更多2024-11-18
量化交易系统开发-实时行情自动化交易-3.4.3.2.期货交易数据
交易数据（Trade Ticks）是进行高频交易策略和市场情绪分析的核心数据之一，通过获取逐笔交易的数据，交易者可以识别大资金动向、市场参与者的行为，以及短时间内的市场动态。以下是通过 Python
阅读更多2024-11-18
Rust：AtomicI8 还是 Mutex＜u8＞?
提供的原子操作（如加载、存储等）在硬件层面得到支持，这些操作是不可分割的，即一旦开始执行，就不会被其他线程的操作打断。如果需要在多个线程之间安全地传递复杂的数据结构或进行复杂的同步操作，那么可能需要考
阅读更多2024-11-18
小程序-基于java+SpringBoot+Vue的智能小程序商城设计与实现
智能小程序商城是一个基于Java和Spring Boot框架开发的电子商务平台，利用微信小程序技术提供便捷的购物体验。系统支持商品浏览、购物车管理、订单处理、用户信息管理等功能，旨在为用户打造一个简洁
阅读更多2024-11-18
华为Ensp模拟器配置OSPF路由协议
开放式最短路径优先 (OSPF) 协议深度解析简介开放式最短路径优先（Open Shortest Path First, OSPF）是一种内部网关协议（IGP），用于在自治系统（AS）内进行动态路由选
阅读更多2024-11-18

顺序表和链表

线性表

顺序表

初始化

销毁

尾插

头插

尾删

头删

指定位置插入数据

指定位置删除数据

查找指定数据

修改指定位置数据

顺序表存在的问题

链表

链表的结构

链表的种类

无头单向非循环链表

无向单向非循环链表增删查改的实现

注意

链表结构

头插

尾插

头删

尾删

查找

在pos位置插入

删除pos位置的节点

释放链表

带头双向循环链表

双向循环链表增删查改的实现

链表结构

初始化

头插

尾插

头删

尾删

查找

在pos位置前插入

删除pos位置的值

释放

相关文章