数据结构之单链表的实现
数据结构之单链表的实现
在上一节 :数据结构之顺序表
我们提到了顺序表的一些缺陷,那有没有什么数据结构可以减少这些问题呢?
答案自然就是今天我们所要说的链表。
本节大纲:
- 链表的概念与结构
- 单链表的实现
- 完整代码展示
一.链表的概念与结构
1.概念
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
2.结构及种类
链表有好多种:单双向链表,带头不带头链表,循环非循环链表 ;它们两两组合可以组成 8 种链表结构,如下图所示:
链表又包括 数据域 和 指针域。
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
1. 无头单向非循环链表:
结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:
结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。
另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
所以我们今天从 无头单向非循环链表 开始:
三.单链表的实现
1.自定义数据类型
首先我们肯定要先创建一个自定义数据类型:
//进行自定义类型,方便修改 typedef int DataType; //进行自定义数据类型 typedef struct SLTNode { DataType data;//存放数据 struct SLTNode* next;//指向下一块空间 }SLTNode;
2.打印函数
假设我们现在有一个数据完全的单链表,但是我们想在看到它的值,这时就需要一个打印函数了。
现在我们来想一想我们刚刚所提到的单链表结构,它是由数据域和指针域组合而成,而它中的指针指向的是下一块储存空间,如果该指针为NULL,就说明该链表已结束。
//单链表打印函数 void SLTPrint(SLTNode *p) { if (p == NULL)//如果该链表为空 { printf("该链表中并无值可供打印\n"); return;//直接退出 } //正常情况下 //cur指向当前位置 SLTNode *cur = p; while (cur)//如果cur是NULL,循环就停止 { printf("%d -> ", cur->data); cur = cur->next;//cur指向下一块空间 } printf("NULL\n"); }
在这会有一些人问 :while 中的判断条件是否可以写为 cur->next ,我们来看一下:
从上图中,我们可以明显看出:若循环条件为 cur->next ,这样循环到达最后一个节点就退出了,最后一个节点内的值并未打印,当然要是你在循环结束后,再加一句printf,那自然也没错
3.创建节点函数:
因后面的头插、尾插、任意位置插入,都需要去创建节点,所以在这就把它单独列一个模块:
//创建节点函数 SLTNode *BuySLTNode(DataType data) { //动态开辟一块空间 SLTNode *new_node = (SLTNode *) malloc(sizeof(SLTNode)); if (new_node == NULL)//如果未开辟成功 { perror("BuyNode Error!");//打印错误信息 exit(-1); } else { //新结点的值为传进来的值 new_node->data = data; new_node->next = NULL; } //返回新建立的节点 return new_node; }
4.单链表尾插
尾插,我们肯定要先找到该链表的尾,然后将尾的next指向我们新建立的结点,将新节点的next指向NULL;
//单链表尾插函数 void SLTPushBack(SLTNode *p, DataType InsertData) { //创建一个新节点 SLTNode *new_node = BuySLTNode(InsertData); if (p == NULL)//说明该链表为空 { p = new_node; } else//非空就找尾 { SLTNode *cur = p; while (cur->next)//循环遍历找尾,注意在这,我们的循环条件为cur->next,而非cur // 因为我们要用最后一个节点的next // 否则,若是cur的话,就直接走到NULL了,我们无法给将一个节点加在它上面 { cur = cur->next;//指向下一个 } cur->next = new_node;//尾插 } }
可是,上面这段代码有没有问题呢? 我们来运行一下:
void test1() { SLTNode *p = NULL; SLTPushBack(p,0); SLTPushBack(p,1); SLTPushBack(p,2); SLTPushBack(p,3); SLTPrint(p); }
测试代码
我们明明尾插了4次,最后为什么还是无值可供打印呢? 我们再来调试一下:
我们发现,它在函数里都换过了,却出了函数又变为了NULL。我们思来想去总觉得这种情形好像在哪见过 — 哦,原来曾在这个例子中见过:
#include<stdio.h> void swap(int a, int b) { int c = a; a = b; b = c; } int main() { int a = 2, b = 3; printf("before:\na=%d, b=%d\n", a, b); swap(a, b); printf("after:\na=%d, b=%d\n", a, b); return 0; }
当时,我们便已提到,改变其值时,要传值,但要改变其指向,要传址;
在举一个例子:
void change(char *p) { p[0] = '!'; } void change_2(char **p) { static char *a = "12334"; *p = a; } int main() { char a[] = "dadasfsfa"; char *p = a; //改变指针所指向的值 change(p); printf("%s\n", p);//!adasfsfa //改变指针的指向 change_2(&p); printf("%s\n", p);//12334 return 0; }
示例
所以正确的尾插怎么写呢:
1.函数参数为STLNode** ,即改为址传递,因为当 p为空的时候,我们需要改变其指向,指向我们新建的new_node
//单链表尾插函数 void SLTPushBack(SLTNode **p, DataType InsertData) { //创建一个新节点 SLTNode *new_node = BuySLTNode(InsertData); if (*p == NULL)//说明该链表为空 { *p = new_node;//改变p的指向 } else//非空就找尾 { SLTNode *cur = *p; while (cur->next)//循环遍历找尾,注意在这,我们的循环条件为cur->next,而非cur // 因为我们要用最后一个节点的next // 否则,若是cur的话,就直接走到NULL了,我们无法给将一个节点加在它上面 { cur = cur->next;//指向下一个 } cur->next = new_node;//尾插 } }
5.单链表头插
现在有了之前的错误经验,是不是一下就知道这个肯定是传址啊:
//单链表头插函数 void SLTPushFront(SLTNode **p, DataType InsertData) { SLTNode *new_node = BuySLTNode(InsertData);//创建新节点 //在头插中,并不关心*p为不为空,反正最后它们的处理都是一样的 //将原链表内容连接在new_node上 new_node->next = *p; //改变指向 *p = new_node; }
6.单链表尾删
循环遍历找尾,释放,置NULL
//单链表尾删函数 void SLTPopBack(SLTNode **p) { if (*p == NULL)//表示该链表为空 { printf("该链表中并无值可供删除!\n"); return; } else if ((*p)->next == NULL)//表示该链表中只有一个值,删除之后就为空 { free(*p);//释放空间 *p = NULL;//置为NULL; } else { //循环遍历找尾 SLTNode *cur = *p;//指向当前位置 SLTNode *prev = NULL;//指向前一个位置 while (cur->next) { prev = cur; cur = cur->next; } free(cur);//释放空间 cur = NULL;//及时置NULL //删除之后prev便是最后一个节点了 prev->next = NULL; } }
7.单链表头删
释放改指向
//单链表头删函数 void SLTPopFront(SLTNode **p) { if (*p == NULL)//表示该链表为空 { printf("该链表中并无值可供删除!\n"); return; } else { SLTNode* pop_node=*p;//指向头节点 *p=(*p)->next;//指向下一个元素 free(pop_node);//释放空间 pop_node=NULL;//及时置NULL } }
8.单链表查找函数
循环遍历
//单链表查找函数 SLTNode *SLTFindNode(SLTNode *p, DataType FindData) { assert(p);//确保传进来的指针不为空 SLTNode *cur = p; while (cur) { if (cur->data == FindData) { return cur;//找到就返回该节点的地址 } cur = cur->next;//循环遍历 } return NULL;//找不到就返回NULL }
9.单链表修改函数
//单链表修改函数 void SLTModify(SLTNode *pos, DataType ModifyData) { assert(pos);//确保pos不为空 pos->data = ModifyData;//修改 }
10.任意位置插入
1.单链表在pos位置之后插入insertdata
//单链表在pos位置之后插入InsertData void SLTInsertAfter(SLTNode* pos,DataType InsertData) { assert(pos);//保证pos不为NULL SLTNode* new_node=BuySLTNode(InsertData);//创建一个新节点 //该节点的下一个指向原本该位置的下一个 new_node->next=pos->next; //该位置的下一个就是new_node pos->next=new_node; }
2.单链表在pos位置之前插入insertdata
这时就要考虑到若位置是第一个位置时,那就相当于头插了
此外,我们还得找到它的前一个位置
//单链表在pos位置之前插入InsertData void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData) { assert(pos); SLTNode *new_node = BuySLTNode(InsertData); if (pos == *p)//这就说明是第一个位置前插入 { //头插 new_node->next = *p; *p = new_node; } else { SLTNode *cur = *p; SLTNode *prev = NULL; //新节点的下一个指向这个位置 new_node->next = pos; //循环遍历找到它的前一个位置 while (cur != pos) { prev = cur; cur = cur->next; } //前一个位置指向新节点 prev->next = new_node; } }
除此之外,还有哦另外一种方法,可以不用去知道它链表的第一个位置
我们在传过去的那个位置,来进行一个后插,再交换这两个节点的数据 ,这也是一种方法:
//单链表在pos位置之前插入InsertData void SLTInsertBefore_2(SLTNode *pos, DataType InsertData) { assert(pos); SLTNode *new_node = BuySLTNode(InsertData); new_node->next = pos->next; pos->next = new_node; //进行了一个后插 //交换这两个变量的值 DataType tmp = pos->data; pos->data = new_node->data; new_node->data = tmp; }
如图:
11.任意位置删除
1.删除pos位后的数据
//删除pos位后的数据 void SLTEraseAfter(SLTNode *pos) { assert(pos); if (pos->next == NULL) { //说明后面并没有元素了 printf("该位置后无数据可以删除\n"); } else { //创建一个指针指向下一个位置 SLTNode *next = pos->next; //原位置的下一个位置,指向 下一个位置 的下一个位置 pos->next = next->next; //释放内存 free(next); next = NULL; } }
2.删除pos位的数据 — 这就包含了头删
//删除pos位的数据 --- 含有头删 void SLTEraseCur(SLTNode **p, SLTNode *pos) { assert(pos); if (*p == pos) { //说明是头删 *p = pos->next; free(pos); pos = NULL; } else { //普通位置 SLTNode *prev = *p; SLTNode *cur = *p; //找到头一个位置 while (cur != pos) { prev = cur; cur = cur->next; } //头一个位置指向下下个位置 prev->next = pos->next; free(pos); pos = NULL; } }
3.同样可以用之前所提到的方法进行带有头删的任意位置删除
1.把该位置 后一个节点的数据存下;
2.删除该位置后的节点
3.将头节点的值改为之前存下的数据
单链表的实现到这便就结束了
三.完整代码展示
//确保头文件只包含一次 #ifndef FINASLT_SLT_H #define FINASLT_SLT_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <assert.h> //进行自定义类型,方便修改 typedef int DataType; //进行自定义数据类型 typedef struct SLTNode { DataType data;//存放数据 struct SLTNode *next;//指向下一块空间 } SLTNode; //单链表打印函数 void SLTPrint(SLTNode *p); //创建节点函数 SLTNode *BuySLTNode(DataType data); //单链表尾插函数 void SLTPushBack(SLTNode **p, DataType InsertData); //单链表头插函数 void SLTPushFront(SLTNode **p, DataType InsertData); //单链表尾删函数 void SLTPopBack(SLTNode **p); //单链表头删函数 void SLTPopFront(SLTNode **p); //单链表查找函数 SLTNode *SLTFindNode(SLTNode *p, DataType FindData); //单链表修改函数 void SLTModify(SLTNode *pos, DataType ModifyData); //单链表在pos位置之后插入InsertData void SLTInsertAfter(SLTNode *pos, DataType InsertData); //单链表在pos位置之前插入InsertData void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData); //单链表在pos位置之前插入InsertData void SLTInsertBefore_2( SLTNode *pos, DataType InsertData); //删除pos位后的数据 void SLTEraseAfter(SLTNode *pos); //删除pos位的数据 --- 含有头删 void SLTEraseCur(SLTNode **p, SLTNode *pos); #endif //FINASLT_SLT_H
SLT.h
#include "SLT.h" //单链表打印函数 void SLTPrint(SLTNode *p) { if (p == NULL)//如果该链表为空 { printf("该链表中并无值可供打印\n"); return;//直接退出 } //正常情况下 //cur指向当前位置 SLTNode *cur = p; while (cur)//如果cur是NULL,循环就停止 { printf("%d -> ", cur->data); cur = cur->next;//cur指向下一块空间 } printf("NULL\n"); } //创建节点函数 SLTNode *BuySLTNode(DataType data) { //动态开辟一块空间 SLTNode *new_node = (SLTNode *) malloc(sizeof(SLTNode)); if (new_node == NULL)//如果未开辟成功 { perror("BuyNode Error!");//打印错误信息 exit(-1); } else { //新结点的值为传进来的值 new_node->data = data; new_node->next = NULL; } //返回新建立的节点 return new_node; } ////单链表尾插函数 //void SLTPushBack(SLTNode *p, DataType InsertData) //{ // //创建一个新节点 // SLTNode *new_node = BuySLTNode(InsertData); // if (p == NULL)//说明该链表为空 // { // p = new_node; // } // else//非空就找尾 // { // SLTNode *cur = p; // while (cur->next)//循环遍历找尾,注意在这,我们的循环条件为cur->next,而非cur // // 因为我们要用最后一个节点的next // // 否则,若是cur的话,就直接走到NULL了,我们无法给将一个节点加在它上面 // { // cur = cur->next;//指向下一个 // } // cur->next = new_node;//尾插 // } //} //单链表尾插函数 void SLTPushBack(SLTNode **p, DataType InsertData) { //创建一个新节点 SLTNode *new_node = BuySLTNode(InsertData); if (*p == NULL)//说明该链表为空 { *p = new_node;//改变p的指向 } else//非空就找尾 { SLTNode *cur = *p; while (cur->next)//循环遍历找尾,注意在这,我们的循环条件为cur->next,而非cur // 因为我们要用最后一个节点的next // 否则,若是cur的话,就直接走到NULL了,我们无法给将一个节点加在它上面 { cur = cur->next;//指向下一个 } cur->next = new_node;//尾插 } } //单链表头插函数 void SLTPushFront(SLTNode **p, DataType InsertData) { SLTNode *new_node = BuySLTNode(InsertData);//创建新节点 //在头插中,并不关心*p为不为空,反正最后它们的处理都是一样的 //将原链表内容连接在new_node上 new_node->next = *p; //改变指向 *p = new_node; } //单链表尾删函数 void SLTPopBack(SLTNode **p) { if (*p == NULL)//表示该链表为空 { printf("该链表中并无值可供删除!\n"); return; } else if ((*p)->next == NULL)//表示该链表中只有一个值,删除之后就为空 { free(*p);//释放空间 *p = NULL;//置为NULL; } else { //循环遍历找尾 SLTNode *cur = *p;//指向当前位置 SLTNode *prev = NULL;//指向前一个位置 while (cur->next) { prev = cur; cur = cur->next; } free(cur);//释放空间 cur = NULL;//及时置NULL //删除之后prev便是最后一个节点了 prev->next = NULL; } } //单链表头删函数 void SLTPopFront(SLTNode **p) { if (*p == NULL)//表示该链表为空 { printf("该链表中并无值可供删除!\n"); return; } else { SLTNode *pop_node = *p;//指向头节点 *p = (*p)->next;//指向下一个元素 free(pop_node);//释放空间 pop_node = NULL;//及时置NULL } } //单链表查找函数 SLTNode *SLTFindNode(SLTNode *p, DataType FindData) { assert(p);//确保传进来的指针不为空 SLTNode *cur = p; while (cur) { if (cur->data == FindData) { return cur;//找到就返回该节点的地址 } cur = cur->next;//循环遍历 } return NULL;//找不到就返回NULL } //单链表修改函数 void SLTModify(SLTNode *pos, DataType ModifyData) { assert(pos);//确保pos不为空 pos->data = ModifyData;//修改 } //单链表在pos位置之后插入InsertData void SLTInsertAfter(SLTNode *pos, DataType InsertData) { assert(pos);//保证pos不为NULL SLTNode *new_node = BuySLTNode(InsertData);//创建一个新节点 //该节点的下一个指向原本该位置的下一个 new_node->next = pos->next; //该位置的下一个就是new_node pos->next = new_node; } //单链表在pos位置之前插入InsertData void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData) { assert(pos); SLTNode *new_node = BuySLTNode(InsertData); if (pos == *p)//这就说明是第一个位置前插入 { //头插 new_node->next = *p; *p = new_node; } else { SLTNode *cur = *p; SLTNode *prev = NULL; //新节点的下一个指向这个位置 new_node->next = pos; //循环遍历找到它的前一个位置 while (cur != pos) { prev = cur; cur = cur->next; } //前一个位置指向新节点 prev->next = new_node; } } //单链表在pos位置之前插入InsertData void SLTInsertBefore_2(SLTNode *pos, DataType InsertData) { assert(pos); SLTNode *new_node = BuySLTNode(InsertData); new_node->next = pos->next; pos->next = new_node; //进行了一个后插 //交换这两个变量的值 DataType tmp = pos->data; pos->data = new_node->data; new_node->data = tmp; } //删除pos位后的数据 void SLTEraseAfter(SLTNode *pos) { assert(pos); if (pos->next == NULL) { //说明后面并没有元素了 printf("该位置后无数据可以删除\n"); } else { //创建一个指针指向下一个位置 SLTNode *next = pos->next; //原位置的下一个位置,指向 下一个位置 的下一个位置 pos->next = next->next; //释放内存 free(next); next = NULL; } } //删除pos位的数据 --- 含有头删 void SLTEraseCur(SLTNode **p, SLTNode *pos) { assert(pos); if (*p == pos) { //说明是头删 *p = pos->next; free(pos); pos = NULL; } else { //普通位置 SLTNode *prev = *p; SLTNode *cur = *p; //找到头一个位置 while (cur != pos) { prev = cur; cur = cur->next; } //头一个位置指向下下个位置 prev->next = pos->next; free(pos); pos = NULL; } }
SLT.c
#include "SLT.h" void test1() { SLTNode *p = NULL; SLTPushBack(&p, 0); SLTPushBack(&p, 1); SLTPushBack(&p, 2); SLTPrint(p); SLTPushFront(&p, 0); SLTPushFront(&p, 1); SLTPushFront(&p, 2); SLTPrint(p); SLTPopBack(&p); SLTPrint(p); SLTPopFront(&p); SLTPrint(p); SLTNode *pos = SLTFindNode(p, 1); if (pos == NULL) { printf("该链表中无所查找的值!\n"); } else { SLTModify(pos,123); } SLTPrint(p); SLTInsertAfter(pos,321); SLTPrint(p); SLTInsertBefore(&p,pos,000); SLTPrint(p); SLTInsertBefore_2(SLTFindNode(p,1),666); SLTPrint(p); SLTEraseAfter(SLTFindNode(p,1)); SLTEraseAfter(SLTFindNode(p,666)); SLTEraseCur(&p,SLTFindNode(p,0)); SLTEraseCur(&p,SLTFindNode(p,123)); SLTEraseCur(&p,SLTFindNode(p,321)); SLTEraseCur(&p,SLTFindNode(p,0)); SLTEraseCur(&p,SLTFindNode(p,0)); SLTEraseCur(&p,SLTFindNode(p,666)); SLTPrint(p); } int main() { setbuf(stdout, NULL); test1(); return 0; }
main.c
|——————————————————–
关于单链表的知识到这便结束了
因笔者水平有限,若有错误,还望指正!