引言
介绍链表之前，先来说一下顺序表，即数组的缺点：
- 顺序表在存储数据时，不易插入和删除数据；
- 顺序表的存储空间利用率和运行效率都不高；
为了解决上述缺点，线性表可以采用另一种存储结构—链式存储结构。
单链表
定义
(链表没特殊说明默认为单链表)链表是通过一组地址任意的存储单元来存储数据元素的存储结构；这些存储单元可以连续，也可以不连续。
1.单链表结点结构
2.头指针
头指针的作用有两个：
1.标识链表，即链表的名字；
2.存储链表中第一个结点的地址；
3.尾指针
尾指针即链表的最后一个结点，没有后继，因此指针域必须置空，即NULL。
单链表的创建
1.头插法创建单链表
创建步骤：
1.建立头节点Head，另其指针域置空；
2.生成新节点p(申请空间失败的话返回Head)；
3.读入数据到p的数据域；
4.将结点p插入到Head之后。
5.重复步骤2~4。
图文表示：
代码实现：
返回值是链表的头节点；
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18LinkList *CreateLink(){ //头插法 LinkList *head,*p; head=(LinkList *)malloc(sizeof(LinkList));//获得的地址转换为 ListLink *类型 if(head==NULL)return head; head->next=NULL; int x; cin>>x; while(x!=0){ p=(LinkList *)malloc(sizeof(LinkList)); p->data=x; p->next=head->next; head->next=p; cin>>x; } return head; }
2.尾插法创建单链表
尾插法与头插法类似，只是将p结点连入尾结点之后。
代码实现：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20LinkList *CreateLink2(){ //尾插法 LinkList *head,*p,*tail; head=(LinkList *)malloc(sizeof(LinkList));//每次申请空间时，严谨的做法是判断申请是否成功 if(head==NULL)return head; head->next=NULL; tail=head; int x; cin>>x; while(x!=0){ p=(LinkList *)malloc(sizeof(LinkList)); p->data=x; tail->next=p; tail=p; tail->next=NULL; cin>>x; } return head; }
单链表的基本操作
1.单链表的遍历
链表的遍历就是从头节点开始，依次访问链表中的每一个结点；在遍历过程中也可以设置一个计数器，计算链表的长度。
代码实现：
复制代码
1
2
3
4
5
6
7
8
9
10void Print_Link(LinkList *head){ LinkList *p=head->next; int num=0; //num为计数器，其结果为链表长度 while(p!=NULL){ cout<<p->data<<endl; p=p->next; num+=1; } }
2.单链表的查找
查找方式分为两种，一种是根据序号查找；一种是根据值去查找。
根据值查找：
复制代码
1
2
3
4
5
6
7
8
9LinkList *GetByNum(LinkList *head,int num){ LinkList *p=head->next; while(p!=NULL){ if(p->data==num)return p;//找到返回结点指针 p=p->next; } return NULL;//找不到返回NULL }
根据节点查找：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12LinkList *GetById(LinkList *head,int i){ int j=0; if(i<=0)return NULL;//保证序号合法 LinkList *p=head; while(p->next!=NULL){ p=p->next; j+=1;//以头节点指向的节点为序号1对应的节点 } if(i==j)return p; return NULL; }
3.单链表的插入
链表插入方式分为两种，一种是后插；一种是前插。
后插：
示意图
代码实现
复制代码
1
2
3
4
5
6void InsertAfter(LinkList *p,LinkList *s){ //在p节点之后插入s节点 s->next=p->next; p->next=s; }
复制代码
1
2
3
4前插与后插的思想类似： 1.先找出节点p的前驱节点q； 2.对q进行后插；
4.单链表的删除
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20int Delete_LinkList(LinkList *head,LinkList *p){ //删除指定节点p LinkList *r; if(p->next!=NULL){//如果p有后继节点 p->data=p->next->data; r=p->next; p->next=r->next; free(r); //释放空间 return 1; } else {//p没有后继节点 r=head; while(r->next!=p) r=r->next; LinkList *q=r->next; r->next=q->next; free(q); } }
静态链表
与单链表的操作基本一直，只是指针指向下标；用下标作为起到唯一标识作用的“地址”。
复制代码
1
2
3
4
5struct LinkList{ int data; int next; };
循环链表和双向链表
循环链表
双向链表
链表的应用
最后
以上就是清秀灰狼最近收集整理的关于【数据结构】链表的全部内容，更多相关【数据结构】链表内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复