- 单链表的相关知识点
- （一）单链表的定义
- （二）单链表的初始化和空表判断
- （三）单链表的输出
- （四）单链表的建立
- （五）单链表的逆序输出
- （六）单链表的插入 *** 作
- （七）单链表的删除 *** 作
- （八）单链表的查找 *** 作
- （九）单链表的求表长 *** 作
- 单链表是
链式存储的，其每个结点除了存放数据元素之外，还存储指向下一个结点的指针；而顺序表是顺序存储的，其每个结点只存放数据元素。【顺序存储结构可以随机存取、顺序存取，而链式存储结构只能顺序存取】
- 顺序存储结构不仅可用于存储线性结构，还能用于树、图。
- 若需对表进行频繁的插入、删除 *** 作，此时适合选
链式存储。 - 一个带头结点的单链表，若
L->next==NULL时，则该单链表为空；一个不带头节点的单链表，若L==NULL时，则该单链表为空。 - 在单链表中，访问后继结点的时间复杂度为O(1)，而访问前驱结点的时间复杂度为O(n)。
（这里可以将单链表与双链表联合记忆，双链表由于每个结点都包含其前驱结点和后继结点，所以访问它们的时间复杂度都为O(1)。
）
- 单链表的插入和删除结点 *** 作，都是要先找到其
前驱结点，即i-1个结点，然后再将其插入或删除，这里的主要时间开销是在寻找第i-1个元素的时间上，时间复杂度为O(n)，从而使插入和删除结点 *** 作的最好时间复杂度为O(1)【要插入或删除的元素位于第一位】，其最坏、平均时间复杂度为O(n)。 - 单链表的插入和删除 *** 作中常用的是
后插 *** 作，可以通过交换两个指针的数据域，从而使时间复杂度为O(1)，这对删除 *** 作也是一样，交换两个指针的数据域，即此时后继结点的值赋予自身，通过free()函数删除后继结点，从而使时间复杂度为O(1)。
带头结点和不带头结点的单链表定义，都为下列代码：
#include1、带头结点的单链表
由于带有头结点，所以要通过malloc()函数分配一个头结点L（注：malloc()函数和free()在头文件#include
L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点
在一个带头结点的单链表，当L->next==NULL时，表示该单链表为空，带头结点的单链表初始化的完整代码如下：
/*初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->next=NULL; //头结点之后暂时还没有任何结点，表示空链表
return true;
}
带头结点的单链表判断是否为空的代码如下：
/*判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
if(L->next==NULL) //若单链表的头结点的指针域为空，则表示单链表为空
return true;
else
return false;
}
2、不带头结点的单链表
因为当L==NULL时，则该单链表为空，所以直接将单链表置为空，如下不带头结点的单链表的初始化代码：
//初始化一个不带头结点的空单链表
bool InitList(LinkList &L) {
L=NULL; //表示这是一个空表，暂时还没有任何结点
return true;
}
判断不带头结点的单链表是否为空，return返回L==NULL是否为true或false，如下代码：
//判断单链表（不带头结点）是否为空
bool Empty(LinkList L) {
return (L==NULL);
}
1、带头结点的单链表
通过设置一个指针p，使其指向头结点的next域，即指向第一个数据元素，经过while()循环输出每次p指针的数据域（p最终不为空时输出每个结点的数据域），然后依次先后移动p指针，从而输出单链表的所有数据元素。
//单链表（带头结点）的输出
void H_DispList(LinkList L) {
LNode *p;
p=L->next;
while(p!=NULL) {
printf("%d ",p->data);
p=p->next;
}
}
2、不带头结点的单链表
（四）单链表的建立1、带头结点的单链表
有两种方式建立带头结点的单链表，分别是头插法和尾插法，头插法即将新结点插入到当前单链表的表头（头结点之后），由于是头插，所以最后生成的元素顺序与原输入的元素顺序刚好相反，这就是头插法和尾插法的区别。
头插法中每次通过malloc()函数生成一个新的结点，通过&s->data读取该新结点的数据域，然后将新结点的next域指向头结点的next域，再将其赋值给L->next即放在头结点其后。
如下代码：
//（1）头插法建立单链表（带头结点）
void H_CreateHead(LinkList L,int n) {
for(int i=0; i<n; i++) {
int number=i+1;
printf("请输入第%d个整数：\n",number);
LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
scanf("%d",&s->data); //读入新结点的数据域
s->next=L->next; //将新结点的指针域存放在头结点的指针域
L->next=s; //将新结点连到头结点之后
}
}
可以加上以下代码，从而使其逆序，从而使头插法建立的单链表与建立的元素顺序是一样的：
void H_CreateHead(LinkList L,int n) {
/*LNode *p,*q;*/
for(int i=0; i<n; i++) {
int number=i+1;
printf("请输入第%d个整数：\n",number);
LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
scanf("%d",&s->data); //读入新结点的数据域
s->next=L->next; //将新结点的指针域存放在头结点的指针域
L->next=s; //将新结点连到头结点之后
}
/*将其逆序排列
p=L->next; //从第一个结点开始（而不是头结点）
L->next=NULL; //将头结点的指针域置NULL
while(p!=NULL) {
q=p; //使p和q的指针结点位置相同
p=p->next; //p指针指向q指针的下一个结点，即q指针存储p指针的指针域
q->next=L->next; //使q结点指向空，将头结点的指针域存放在q结点的指针域中
L->next=q; //将q结点连在头结点后，即q结点赋给头结点的指针域
}*/
}
例如，通过头插法建立一个单链表并输出单链表：
#include运行结果如下：
尾插法建立单链表，通过添加一个尾指针last，指向单链表的最后一个结点，每次申请一个新结点s，将其读取的数据存放到s的数据域中，然后将s的尾指针指向空，将新结点插入到单链表的尾部，从而完成建立单链表。
如下代码：
//尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
LNode *last;
int i;
last=L; //last指针始终指向当前单链表的末尾结点
for(i=0; i<n; i++) {
int number=i+1;
printf("请输入第%d个整数：\n",number);
LNode *s=(LNode *)malloc(sizeof(LNode)); //申请一个新结点s
scanf("%d",&s->data); //将数据读入至新结点s的数据域中
s->next=NULL; //将新结点s的指针域置为空，即空指针NULL
last->next=s; //将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
last=s; //然后将last指针指向单链表的末尾结点，即指向新结点的后面
}
}
例如，通过尾插法建立一个单链表，并输出单链表：
#include运行结果如下：
2、不带头结点的单链表
后续更新分割线…………
1、带头结点的单链表
逆序处理的代码如下：
//单链表的逆序处理
void ReverseList(LinkList L) {
LNode *p,*q;
p=L->next;
L->next=NULL;
while(p!=NULL) {
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
}
当想对一个单链表进行逆序处理，其实可以在创建单链表时，通过头插法建立单链表，从而也可以使得到的结果是逆序的。
对一个通过头插法创建单链表的单链表逆序处理后输出，如下：
#include运行结果如下：
2、不带头结点的单链表
后续更新分割线…………
1、带头结点的单链表
将要插入的结点插到单链表的第i个位置上，也就是要找到其前驱结点，即i-1结点的位置，然后在其后插入新的结点。
代码如下【时间复杂度为O(n)】：
/*按位序插入元素至单链表中（找到i-1个结点【p】，然后将新结点【s】插入其后）*/
bool H_ListInsert(LinkList &L,int i,int e) {
if(i<1)
return false;
LNode *p; //指针p为当前扫描的结点
int j=0; //j的值代表p指向的是第几个结点
p=L; //L指向头结点（第0个结点，不存储结点）
while(p!=NULL&&j<i-1) {
p=p->next; //循环找到i-1个结点，且该结点为不为空
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode *)malloc(sizeof(LNode)); //申请一个新结点s
s->data=e; //将要插入的结点的值赋给该新结点的数据域
s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
p->next=s; //s结点指到p结点的指针域，即将s连到p之后
return true;
}
另一种后插 *** 作如下，参数为将指针s插入到指针p的后面【这种方法的时间复杂度为O(1)】：
/*后插法直接插入新结点*/
bool InserprioNode(LNode *p,LNode *s) {
if(p==NULL||s==NULL)
return false;
s->next=p->next; //修改指针域
p->next=s;
int temp=p->data; //交换数据域
p->data=s->data;
s->data=temp;
return true;
}
例如在单链表的第二个位置插入元素0，最后输出插入后的单链表，通过第一种方法实现如下：
#include运行结果如下：
2、不带头结点的单链表
后续更新分割线…………
1、带头结点的单链表
删除 *** 作，也就是将单链表的第i个结点删除，这里也就是要找到其前驱结点，即i-1结点的位置（要删除的结点的前驱结点），然后将其删除。
（通过free()函数实现，注意要加#include
代码如下：
/*4、单链表（带头结点）删除元素*/
bool ListDelete(LinkList &L,int i) {
if(i<1)
return false;
LNode *p; //指针p为当前扫描的结点
int j=0; //j的值代表p指向的是第几个结点
p=L; //L指向头结点（第0个结点，不存储结点）
while(p!=NULL&&j<i-1) {
p=p->next; //循环找到i-1个结点，且该结点为不为空
j++;
}
if(p==NULL)
return false;
if(p->next==NULL)
return false;
LNode *q=p->next; //令q指向被删除的结点
/*e=q->data;*/ //用e返回元素的值
p->next=q->next; //将*q结点从链表中断开
free(q);
return true;
}
例如删除单链表第三位元素，如下：
#include运行结果如下：
另一种删除方法是删除该结点的后继结点从而实现删除一个结点，首先将其后继结点的值赋给自身，然后再删除后继结点，这样可以使时间复杂度达到O(1)，代码如下：
bool DeleteNode(LNode *p) {
if(p==NULL)
return false;
LNode *q=p->next; //q指向*p的后继结点
p->data=p->next->data; //交换数据域
p->next=q->next; //将*q结点从链表中断开
free(q);
return true;
}
2、不带头结点的单链表
后续更新分割线…………
单链表的查找 *** 作分为按值查找和按位查找（位序是从1开始）。
1、带头结点的单链表
按值查找的 *** 作通过比较data数据域，即从单链表的第一个结点开始（不是头结点，而是p=L->next），依次比较各个结点的data数据域，若某结点的data数据域等于查找值，再通过一个if语句判断该指针是否为空，若为空则表示单链表中有该结点并输出该结点的位序和值，然后返回true；否则返回false。
按值查找的代码如下：
/*4、按值查找（比较data数据域）*/
bool Locatexdata(LinkList L,int x) {
int i=1;
LNode *p=L->next;
while(p!=NULL&&p->data!=x) {
p=p->next;
i++;
}
if(p!=NULL) {
printf("已找到表中第%d位且值为%d的结点",i,x);
return true;
} else
return false;
}
例如创建一个单链表，然后查找值为0的元素，如下：
#include运行结果如下：
按位查找的 *** 作是从头结点开始，通过next指针域依次搜索链表，直到找到第i个结点（要搜索的结点的位序）为止，若找到则输出第i个结点的值和位序并返回true；若没有找到则返回false。
按位查找查找的代码如下：
bool Searchlocate(LinkList L,int i){
int j=1;
LNode *p=L->next;
if(i==0)
return L;
if(i<1)
return false;
while(p!=NULL&&j<i){
p=p->next;
j++;
}
printf("已找到表中第%d位且值为%d的结点",j,p->data);
return true;
}
例如创建一个单链表，查找单链表中位序为3的元素（第三个元素），如下：
#include运行结果如下：
2、不带头结点的单链表
后续更新分割线…………
1、带头结点的单链表
int Listlength(LinkList L){
int len=0;
LNode *p=L;
while(p->next!=NULL){
p=p->next;
len++;
}
return len;
}
2、不带头结点的单链表
后续更新分割线…………
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）