单个链接表 - 单个链接表的定义和基本操作(头部插入、尾部插入以建立表格、查找、插入、删除等)
前言
上一篇我们已经完成了顺序表的实现和基本操作<元素的增加、删除和查找>
(链接直达:线性表元素的基本操作(C语言)【数据结构】-****博客)
我们知道顺序表支持随机访问,可以通过下标来直接访问,同时也可以进行排序等优点;但是仍存在局限性,对顺序表的中部进行增加或删除元素的时间复杂度高,均为O(n);同时要求大片连续空间进行存储,改变容量也不是很方便。
因为我们引入新的线性表——链表。
单链表
一、单链表的基本概念
单链表(Singly Linked List)是一种常用的数据结构,它由若干个结点组成,每个结点包含两部分:数据域和指针域。数据域用于存储数据,而指针域则用于指向下一个节点的地址。单链表中每个结点只有一个指针域,指向下一个结点,最后一个结点的指针域指向 NULL,表示链表的结尾。
从这里我们可以很清楚的看见每个结点分为数据域和指针域。
//在结构体中定义数据域和指针域
typedef struct LNode {
int data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
相比于顺序表,单链表的存储不要求大片连续存储空间,因此改变容量十分方便。
对比下图便可直观感受到单链表易更改性。
二、单链表的实现
1.单链表的创建
单链表的创建分为头插法和尾插法。
(1)头插法:
输入的数据次序生成的链表结点次序相反,例如:按{1,2,3}顺序进行头插之后,最终排序却变成了{3,2,1},换言之就是逆序插入。
以下便是代码图解,e为需要插入到单链表L中的结点
头插法代码实现:
//利用头插法创建链表
LNode *Init_LinkList_head(LinkList L) {
//创建头结点
LinkList head = (LinkList) malloc(sizeof(LinkList));
//保证头结点没有存储脏数据
head->next = NULL;
//创建输入数据的常量
int val = -1; //定义-1表示输入结束标志
int len = 0; //观察单链表的长度
while (true) {
printf("请输入链表中的元素:");
scanf("%d", &val);
if (val == -1) {
break;
}
//创建新的结点
LinkList s = (LinkList) malloc(sizeof(LinkList));
s->data = val; //将输入的数据赋值到新结点的数据域中
s->next = head->next;
head->next = s; //将新结点连接到头指针中
len++;
}
printf("链表的长度为:%d\n", len);
return head; //返回单链表
}
int main() {
LinkList L = Init_LinkList_head(L);
PrintLinkList(L);
return 0;
}
例:向空链表中插入{10,20,30,40,50,60}构成新的单链表。
(2)尾插法:
输入的数据次序生成的链表结点次序相同,例如:按{1,2,3}顺序进行头插之后,最终排序还是{1,2,3},换言之就是顺序插入。
以下便是代码图解,e为需要插入到单链表L中的结点
尾插法的代码实现:
在此方法中我们添加了一个尾结点,设置尾结点的目的是为了提高插入操作的效率。如果没有尾结点,每次进行尾插入操作时,都需要遍历整个链表找到最后一个结点,然后再进行插入操作。这样的时间复杂度是O(n),其中n是链表的长度。
而如果设置了尾结点,每次进行尾插入操作时,只需要直接将新结点插入到尾结点之后,并更新尾结点的指针即可,不需要遍历整个链表。这样的时间复杂度是O(1),效率更高。
//利用尾插法创建链表
LinkList Init_LinkList_tail(LinkList L) {
//创建头结点
LinkList head = (LinkList) malloc(sizeof(LinkList));
//头结点的指针域置空,说明当前链表是空的
head->next = NULL;
int val = -1;
int len = 0;
//创建尾节点
LinkList ptr = (LinkList) malloc(sizeof(LinkList));
ptr = head; //开始时指向头节结点,中间没有数据
//循环的向链表中添加元素,直至找到结束标志后退出输入环节
while (true) {
printf("请输入链表中的元素:");
scanf("%d", &val);
if (val == -1) { //输入结束标志
break;
}
LinkList s = (LinkList) malloc(sizeof(LinkList)); //申请新的结点
s->data = val;
s->next = NULL;
ptr->next = s; // 将新的结点链接到尾结点中
ptr = s; //更新尾结点,添加完新的结点后将新的结点设为尾结点
len++;
}
printf("链表的长度为:%d\n", len);
return head;
}
int main() {
LinkList L = Init_LinkList_tail(L);
PrintLinkList(L);
return 0;
}
例:向空链表中插入{10,20,30,40,50,60}构成新的单链表。
一般地,头插法的重要应用便是链表的逆置,尾插法可能多用于自己的学习研究,接下来单链表的基本操作我们均以尾插法来创建链表并加以阐述。
2.单链表的查找
单链表的查找分为按值查找和按位查找。
我们这里默认讨论带头结点的单链表。
(1)按位查找
单链表不具备“随机访问“的特性,只能依次扫描每个结点并对比数据域中是否为目标值。
基本思路:从单链表中的第一个结点出发,顺时针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。
平均时间复杂度:O(n)
创建一个指针P,并从头结点开始遍历单链表,直至找到目标元素。
代码实现:
//按位查找元素
void Search_LinkList_site(LinkList L) {
//创建新的结点
LinkList p = (LinkList) malloc(sizeof(LinkList));
//结点p从头结点的下一个结点开始遍历,即第一个存储数据的结点开始遍历
p = L->next;
int j = 1;
printf("请输入想要查找元素的位置:");
int i;
scanf("%d", &i);
while (p != NULL && j < i) { // p若为空则说明链表已遍历结束
j++;
p = p->next; //依次指向下一个结点
}
int elem = p->data; //获取目标位置的元素
printf("链表中第%d元素是%d\n", i, elem);
}
例:查找链表{10,20,30,40,50,60}中第3位元素。
(2)按值查找
基本思路:从单链表中的第一个结点出发,顺时针next域逐个往下搜索,直到找到第i个结点的数据域与目标值相等为止,否则返回最后一个结点指针域NULL。
平均时间复杂度:O(n)
创建一个指针p,从单链表的第一个结点开始遍历,每次比较结点的数据域和目标值。
代码实现:
//按值查找元素
void Search_LinkList_value(LinkList L) {
LinkList p = (LinkList) malloc(sizeof(LinkList));
p = L->next;
int cnt = 1;
int e;
printf("请输入需要查找的元素:");
scanf("%d", &e);
while (p != NULL && p->data != e) { //比较每个结点的数据域是否为目标值
cnt++;
p = p->next;
}
printf("元素%d是链表中第%d位元素。\n", e, cnt);
}
例:查找链表{10,20,30,40,50,60}中{60}元素所在位置。
单链表的查找主要思想是遍历整个链表,从而找到目标数值或目标位置。
3.单链表的元素插入
单链表的插入分为按位序插入和按指定结点插入两大类。
(1)按位序插入
在单链表L中的第i个位置上插入指定元素e。要在第i个位置上插入指定元素,那就应该要找到第i-1个结点,并将新结点插入其后。
过程分析:
1.要找到第i-1个结点;(若i=2,就需要找到i=1的第一个结点)
2.然后需要用malloc函数申请一个新的结点s;
3.将数据元素e存入到这个结点;
4.假设第i-1的结点为*p;
5.新结点s的指针域指向p的后继结点;
6.令p的指针域指向新插入结点s; (5与6的顺序不能颠倒)
7.按位序插入成功;
代码实现:
//按位序插入
void Insert_LinkList_appoint(LinkList L) {
LinkList p = (LinkList) malloc(sizeof(LinkList));
p = L;
int j = 0;
int site;
printf("请输入需要插入的位置:");
scanf("%d",&site);
//通过循环找到指定元素的前驱
while (p != NULL && j < site - 1) {
j++;
p = p->next;
}
//判断接下来插入位置是否合法
if (p == NULL) {
//site值不合法,超出链表长度,说明第site-1个结点不存在
printf("插入的位置不合法!\n");
} else {
printf("请输入需要插入的元素:");
//创建需要插入的节点
LinkList s = (LinkList) malloc(sizeof(LinkList));
scanf("%d", &(s->data));
s->next = p->next;
p->next = s;
}
}
例:向链表{10,20,40,50,60}中的第3号位置插入元素{30}。
健壮性测试:输入的site值不合法,例在链表{10,20,30}的第8号位置插入元素。
(2)按指定结点的插入操作
a.在指定结点之后插入(后插)
后插操作:给定一个指定结点,在此结点之后插入一个数据元素e。单链表的结点结构使得单链表的链接指针只能往后寻找,所以如果给定一个指定结点p,那么p结点之后的结点都是可知的,p结点之前的结点都是未知的。
代码实现:
//后插操作,在p结点之后插入元素e.
bool InsertNextNode(LinkList p,int e){
if(p==NULL) //结点p不合法
return false;
LinkList s = (LinkList) malloc(sizeof(LinkList));//申请新结点
s->data=e; //在新结点中存入数据元素e
s->next =p->next; //结点p的下一个结点由新结点s来链接;
p->next=s;
return true; //插入成功!
}
实现之后的效果:
后插操作主要找到指定结点之后便可以直接执行插入操作,因此时间复杂度是O(1)。
b.在指定结点之前插入(前插)
在指定某一结点的前面插入一个新的结点。由于单链表只能从头向尾遍历,那么我们怎么找到指定结点的前驱结点呢?(后面的双链表可以直接指向p-prior)
此时我们可以传入一个头指针,利用头指针循环查找结点p;找到p的前驱结点q,再对结点q进行后插;从而完成结点q的前插操作。
时间复杂度:O(n)
代码实现:
//前插操作,在p结点之前插入元素e.
bool InsertPriorNode(LinkList p,int e){
if(p==NULL) //结点p不合法
return false;
LinkList s = (LinkList) malloc(sizeof(LinkList));//申请新结点
s->next=p->next;
p->next=s; //将新结点连接到p之后
s->data=p->data; //将p中元素复制到s中
p->data=e; //将p中元素被覆盖为e
return true; //插入成功!
}
4.单链表的元素删除
单链表的删除分为按位序删除和指定结点的删除。
(1)按位序删除
找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点
检查删除位置的合法性;
查找表中的第i-1个结点——被删结点的前驱结点
修改指针域和返回被删数据域的元素
删除成功!
最坏、最好时间复杂度:O(n)
最好时间复杂度:O(1)——被删结点是第一个结点。
代码实现:
//按位序删除
void ListDelete(LinkList L) {
//判断L是否存在元素
if (L == NULL) {
printf("链表为空,无法删除结点\n");
return;
}
LinkList p = (LNode *) malloc(sizeof(LinkList));
p = L; //指针P指向当前结点
int j = 0;
int site;
printf("请输入需要删除结点的位置:");
scanf("%d",&site);
while (p != NULL && j < site - 1) { //通过循环遍历到site - 1的结点处
p = p->next;
j++;
}
// 如果位置超出链表长度
if (p == NULL || p->next == NULL) {
printf("位置超出链表长度,无法删除结点\n");
return;
}
LinkList q = (LNode *) malloc(sizeof(LinkList));
q = p->next->next; //令q指向被删除的结点
int e = p->next->data; //获取被删除结点的数据
free(p->next); //释放结点的存储空间
p->next = q;
printf("成功删除元素%d\n", e);
}
例:将链表{10,20,30,40,50}中的第4个结点进行删除。
健壮性测试:若输入的位置超过链表的长度则会删除失败!
(2)指定结点删除
删除单链表中指定结点的基本原理如下:
- 遍历链表,找到要删除的结点以及其前驱结点。
- 将前驱结点的
next
指针指向要删除结点的下一个结点,跳过要删除的结点。 - 释放要删除的结点的内存空间,防止内存泄漏。
代码实现:
//指定结点删除操作
void ListDelete_point(LinkList L) {
//初始化两个指针p和s,分别指向链表的头结点和空指针。
LinkList p = (LNode *) malloc(sizeof(LinkList));
LinkList s = (LNode *) malloc(sizeof(LinkList));
p = L;
s = NULL;
//定义目标结点的值
int key;
printf("请输入需要目标结点的值:");
scanf("%d",&key);
//头结点便是目标位置的情况,直接将头指针指向下一个结点
if(p != NULL && p->data == key){
L = p->next;
free(p);
return;
}
//遍历链表直到找到要删除的结点
while (p != NULL && p->data != key){
s = p;
p = p->next;
}
if(p == NULL){
printf("没有找到目标结点的值,删除失败!\n");
return;
}
s->next = p->next; //跳过要删除的结点
free(p); //释放要删除的结点的内存空间
printf("删除成功!\n删除后的链表为:");
}
例:将链表{10,20,30,40,50}中的数据域为40的结点进行删除。
如果整个链表中都没有找到目标值则会返回查找失败!
注意区分这两种删除的区别:
- 指定结点删除是根据结点的数值来确定要删除的结点,即删除具有特定数值的结点。
- 按照位序删除是根据结点在链表中的位置(位序)来确定要删除的结点,即删除链表中的第n个结点。
上一篇: 链表的回文结构OJ