网站要备案吗,网络营销的产品策略,微商城登录,怎么在年报网站做简易注销数据结构学习笔记---003 数据结构之单链表1、什么是单链表?1.1、概念及结构 2、单链表接口的实现2.1、单链表的SList.h2.1.1、定义单链表的结点存储结构2.1.2、声明单链表各个接口的函数 2.2、单链表的SList.c2.2.1、遍历打印链表2.2.2、销毁单链表2.2.3、打印单链表元素2.2.4… 数据结构学习笔记---003 数据结构之单链表1、什么是单链表?1.1、概念及结构 2、单链表接口的实现2.1、单链表的SList.h2.1.1、定义单链表的结点存储结构2.1.2、声明单链表各个接口的函数 2.2、单链表的SList.c2.2.1、遍历打印链表2.2.2、销毁单链表2.2.3、打印单链表元素2.2.4、单链表的基本操作 3.3、单链表的main.c3.3.1、TestSL1()3.3.2、TestSL2() 4、单链表巩固练习4.1、单链表巩固练习题01 --- 求链表的中间节点4.2、单链表巩固练习题02 --- 移除链表元素4.3、单链表巩固练习题03 --- 链表分割 5、单链表总结 数据结构之单链表
前言 前篇学习了 数据结构的顺序表 那么这篇继续学习数据结构线性表的第二种存储方法链式存储的单链表。 /知识点汇总/
1、什么是单链表?
1.1、概念及结构
概念单链表是一种物理存储结构上非连续、非顺序的存储结构但链表在逻辑上是连续的顺序的而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 由于顺序表的插入删除操作需要移动大量的元素影响了运行效率因此引入了线性表的链式存储——单链表。 单链表通过一组任意的存储单元来存储线性表中的数据元素不需要使用地址连续的存储单元因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。 单链表Singly Linked List是一种常用的数据结构它由若干个节点组成每个节点包含两部分数据域和指针域。 数据域用于存储数据而指针域则用于指向下一个节点的地址。 单链表中每个节点只有一个指针域指向下一个节点最后一个节点的指针域指向NULL表示链表的结尾。 2、单链表接口的实现 在实际应用中单链表的存储思想就是用指针表示各结点之间的逻辑关系。 本质就是掌握好结点间的链式处理。 然后与前篇学的顺序表不同就不存在扩容的问题了但仍然需要注意及时释放动态开辟的内存空间等问题。 实现过程继续采用阶段性测试既方便调试也方便及时解决问题。 另外单链表又分为带头结点和不带头结点的方式这里用不带头的进行编写具体可根据实际符合的应用场景决定。
2.1、单链表的SList.h
2.1.1、定义单链表的结点存储结构
因为是采用的多种类型的数据所以适用于结构体类型。然后知道了需要一个数据域和指针域所以定义结构体如下所示
//定义单链表的动态存储
typedef int SLNDataType;//这里的重命名主要作用是不能保证每次使用都是整型所以只需要改这里为其它类型更健壮和便利
//Single List
typedef struct SLNode //定义单链表结点类型为结构体类型包括数据域和指针域
{SLNDataType val; //结点数据域struct SLNode* next; //结点指针域存放下一个结点的地址
}SLNode;2.1.2、声明单链表各个接口的函数
//遍历打印链表
void SLPrint(SLNode* pphead);
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);
//尾删
void SLTPopBack(SLNode** pphead);
//头删
void SLTPopFront(SLNode** pphead);
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x);
//pphaed NULL ,错误
//*pphead NULL空表
//(*pphead)-next NULL一个结点
//在pos位置的前面插入
void SLTInsert(SLNode** pphead,SLNode* pos, SLNDataType x);
//删除pos的位置结点
void SLTErase(SLNode** pphead, SLNode* pos);
//在pos的位置之后的操作就不存在头插头删的情况参数就不用传plist了
//在pos的位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x);
//在pos的位置之后删除
void SLTEraseAfter(SLNode* pos);
//销毁单链表
void SLTDestory(SLNode** pphead);2.2、单链表的SList.c
主要还是要完成 SList.h 接口对应的 .c 功能函数。 有了前篇的意识和基础对于单链表的初始化可以有但没必要因为不带头结点本身不用就是空表那么就体现在后面建立结点函数的写法中对初始化的处理了。但为了对比和理解把带头结点的常规写法也写一下但后面继续以不带头的结点写。 初始化单链表(带头结点)
Node* InitList()
{Node* first (Node*)malloc(sizeof(Node)); //生成头结点first-next NULL; //头结点的指针域置空return first;
}2.2.1、遍历打印链表
为了打印单链表的元素这里需要像顺序表那样遍历所以引用一个工作指针依次访问指针域打印各个结点的数据域中元素。工作指针的本质是读数据域而不作更改防止写动数据等问题。
//遍历打印链表
void SLPrint(SLNode* phead)
{SLNode* cur phead;//定义工作指针防止更改了phead的地址while (cur ! NULL){printf(%d-, cur-val);//读数据域cur cur-next; //偏移指针域}printf(NULL\n);
}2.2.2、销毁单链表
为了避免忘记销毁开辟的动态内存空间。所以这里使用动态存储方法那么通常把初始化和销毁一块就写出来了。
//顺序表的销毁
void SLDestory(SL* ps1)
{//暴力检查assert(ps1);//一定不能为空if (ps1-a ! NULL){free(ps1-a);ps1-a NULL;ps1-size 0;ps1-capacity 0;}
}2.2.3、打印单链表元素
为了直观的体现数据元素是否成功操作所以接着写出打印接口函数。
//打印顺序表
void SLPrint(SL* ps1)
{//暴力检查assert(ps1);//一定不能为空for (int i 0; i ps1-size; i){printf(%d , ps1-a[i]);}printf(\n);
}2.2.4、单链表的基本操作
完成了上述函数的功能那么就可以实现单链表的基本操作了。插入和删除以及查找无非就是增删改查。 头插和头删尾插和尾删。 其次对于开辟新结点的操作多个函数都涉及到所以可以封装成单独的CreateNode函数如下所示
//开辟新结点且next置空
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);//return;exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}尾插、头插、尾删、头删的操作需要注意一下判空和空表的情况。
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);//空结点的处理SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{//找尾链表不为空只需要下面的部分但尽可能的健壮代码所以需要考虑链表为空的情况SLNode* tail *pphead;//while (tail ! NULL)容易掉的坑这样写画图很清楚的看到链表并没有链接起来而且除了作用域tail销毁尾结点会存在内存泄漏的问题while (tail-next ! NULL){tail tail-next;}//因为多个函数都需要开辟新节点所以直接封装为函数//而且不能直接SLNode* newNode来定义结构体来开辟因为这里只能作用域为局部变量所以需要malloc才行。//SLNode* newNode (SListNode*)malloc(sizeof(SLNode));//SLNode* newnode CreateNode(x);已放开头tail-next newnode;}
}//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLNode** pphead)
{//注意pphead一定不能为空所以需要检查assert(*pphead);assert(pphead);//区分一个结点和多个结点//这两句的位置不同对应的写法不同/*SLNode* tail *pphead;//Node* prev *pphead;//错误初始化为*phead时如果首结点被free时那么prev就会成为野指针。SLNode* prev NULL;if (tail-next NULL)//一个节点{free(tail);tail NULL;}*/if ((*pphead)-next NULL)//一个节点{free(*pphead);*pphead NULL;}else//找尾{//这两句的位置可以写这儿SLNode* tail *pphead;//Node* prev *pphead;//错误初始化为*phead时如果首结点被free时那么prev就会成为野指针。SLNode* prev NULL;while (tail-next ! NULL){/*tail tail-next;prev tail;*///错误注意顺序是不可以交换的因为当tail到空时还赋给prev就导致为野指针了prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;//一种简化写法/*SLNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);//释放的是指针指向的内存空间而不是指针本身tail-next NULL;*/}
}
//头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);assert(pphead);//if ((*pphead)-next NULL)//一个节点//{// free(*pphead);// *pphead NULL;//}//一个以及以上结点都能处理//方法1//SLNode* tail *pphead;//tail tail-next;//free(*pphead);//*pphead tail; //方法2//SLNode* tail *pphead;//*pphead (*pphead)-next;//free(tail);//方法3SLNode* tmp (*pphead)-next;;free(*pphead);//注意顺序不能交换*pphead tmp;
}查找、在pos位置的前面插入、删除pos的位置、在pos的位置之后插入和在pos的位置之后删除操作。
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{assert(phead);SLNode* cur phead;//定义工作指针防止更改了phead的地址while (cur ! NULL){if (cur-val x)return cur;cur cur-next; //偏移指针域}return NULL;
}
//在pos位置的前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{/*assert(pphead);assert(*pphead);assert(pos);*///这种检查严格限定了pos一定为链表里的有效节点assert(pphead);assert((!pos !(*pphead)) ||(pos *pphead));//要么都是空要么都不是空//对空处理if (*pphead pos){//调用头插SLTPushFront(pphead, x);}else//找插入结点的前一个结点{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
}
//删除pos的位置
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//头结点梳理if ((*pphead)-next NULL){//调用头删SLTPopFront(pphead);}else{SLNode* prev *pphead;if (prev pos){//调用头删SLTPopFront(pphead);}else{while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}}
}//在pos的位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newnode CreateNode(x);//经典错误单链表断开自己指向了自己/*pos-next newnode;newnode-next pos-next;*/newnode-next pos-next;pos-next newnode;
}//扩展只给pos位置如何完成想在pos之前插入呢
//只需要在pos后面插入交换pos的结点值即可//在pos的位置之后删除
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos-next);//因为当只有一个结点时curpos-next,为空所以对pos-next访问就非法访问了。SLNode* cur pos-next;pos-next cur-next;free(cur);cur NULL;
}3.3、单链表的main.c
简单的写几个测试应用目的是检测各个接口函数是否满足需求是否存在一些bug。
3.3.1、TestSL1()
主要检测尾插、头插、打印和销毁接口函数以及参数的传址调用和传值调用。
#include SList.h
//测试1
void TestSLT1()
{SLNode* plist NULL;//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作还得使用二级指针所以这里必须传地址 不然phead只是plist的临时拷贝SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);//尾插SLPrint(plist);//打印SLTPopBack(plist);//尾删SLPrint(plist);SLTPushFront(plist, 5);//头插SLPrint(plist);SLTPushFront(plist, 6);//头插SLPrint(plist);SLTPopBack(plist);//尾删SLPrint(plist);SLTPopBack(plist);//尾删SLPrint(plist);
}
int main()
{TestSLT1();//TestSLT2();//TestSLT3();//TestSLT4();//TestSLT5();return 0;
}测试效果展示
3.3.2、TestSL2()
主要检测接口函数是否满足需求并深刻认识指针、二级指针的应用。
#include Seqlist.h
//测试二
void TestSLT2()
{SLNode* plist NULL;//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作还得使用二级指针所以这里必须传地址 不然phead只是plist的临时拷贝SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);//尾插SLPrint(plist);//打印SLTPopFront(plist);SLPrint(plist);
}
int main()
{//TestSL1();TestSL2();//TestSL3();//TestSL4();//TestSL5();//TestSL6();//TestSL7();return 0;
}效果展示
4、单链表巩固练习
4.1、单链表巩固练习题01 — 求链表的中间节点
求链表的中间节点 — 经典快慢指针
#include SList.h
//定义单链表的结构体类型
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}int main()
{SLNode* plist NULL;//SLTPushBack(plist, 1);//传参为SLNode*,要想实现操作还得使用二级指针所以这里必须传地址 不然phead只是plist的临时拷贝SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);//尾插SLPrint(plist);//打印struct ListNode* pos middleNode(plist);printf(pos %d\n, pos-val);return 0;
}4.2、单链表巩固练习题02 — 移除链表元素
移除链表元素 – 返回新的头结点 方法1遍历删除
#include SList.h
//定义单链表的结构体类型
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* removeELements(struct ListNode* head, int val)
{struct ListNode* prev NULL;//prev的作用是在于删除对应结点后能找到next断开之后再链接struct ListNode* cur head;while (cur){if (cur-val val){struct ListNode* tmp cur-next;free(cur);if (prev)//必须判断首节点是否val,被free后可能为空prev-next tmp;else//否则,新的头结点更新head tmp;cur tmp;}else{prev cur;cur cur-next;}}return head;
}int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));n1-val 7;n2-val 7;n3-val 2;n4-val 3;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;struct ListNode* head removeELements(n1, 7);SLPrint(head);return 0;
}方法2遍历把不是val的结点链接到新链表添加尾指针
#include SList.h
//定义单链表的结构体类型
struct ListNode
{int val;struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{struct ListNode* cur phead;//定义工作指针防止更改了phead的地址while (cur ! NULL){printf(%d-, cur-val);//读结点域cur cur-next; //偏移指针域}printf(NULL\n);
}
struct ListNode* removeELements(struct ListNode* head, int val)
{struct ListNode* newnode NULL;struct ListNode* tail NULL;struct ListNode* cur head;while (cur){//如果不是val把结点拿到新链表(新链表为空)if (cur-val ! val){//尾插两种情况if (tail NULL){newnode tail cur;}else{tail-next cur;tail tail-next;}cur cur-next;}else{struct ListNode* tmp cur;cur cur-next;free(tmp);}}if(tail)//注意最后尾节点的判空防止野指针同时判空处理空表tail-next NULL;head newnode;return head;
}int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));n1-val 7;n2-val 7;n3-val 2;n4-val 3;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;struct ListNode* head removeELements(n1, 7);SLPrint1(head);return 0;
}方法3添加哨兵位头结点 哨兵位的头结点不存储有效数据置NULL
#include SList.h
//定义单链表的结构体类型
struct ListNode
{int val;struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{struct ListNode* cur phead;//定义工作指针防止更改了phead的地址while (cur ! NULL){printf(%d-, cur-val);//读结点域cur cur-next; //偏移指针域}printf(NULL\n);
}
struct ListNode* removeELements(struct ListNode* head, int val)
{struct ListNode* newnode NULL;struct ListNode* tail NULL;struct ListNode* cur head;//添加哨兵位newnode tail (struct ListNode*)malloc(sizeof(struct ListNode));while (cur){//如果不是val把结点拿到新链表(新链表为空)if (cur-val ! val){//尾插两种情况tail-next cur;tail tail-next;cur cur-next;}else{struct ListNode* tmp cur;cur cur-next;free(tmp);}}//哨兵位方法前面简化而这里就需要处理tail-next NULL;struct ListNode* tmp newnode;newnode newnode-next;free(tmp);head newnode;//头结点next为首节点符合题目要求return head;
}int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));n1-val 7;n2-val 7;n3-val 2;n4-val 3;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;struct ListNode* head removeELements(n1, 7);SLPrint1(head);return 0;
}4.3、单链表巩固练习题03 — 链表分割
链表分割 — 返回重新排列后的头指针,相对顺序不变 3 6 1 8 4 6 9 — val5分割 3 1 4 (5)6 8 6 9 思路1不带哨兵位比较val小的放一个链表大于等于val的放一个链表再合并两个链表同时注意判断两边链表为空的情况即全比val大或者小的处理所以相对于带头结点的操作就比较复杂。 思路2带2个哨兵位直接比较后执行相应的尾插操作即可最后合并。 建议采用带头结点的方法更好处理这题
#include SList.h
//#include cstddef//定义单链表的结构体类型
struct ListNode
{int val;struct ListNode* next;
};
//打印链表
void SLPrint1(struct ListNode* phead)
{struct ListNode* cur phead;//定义工作指针防止更改了phead的地址while (cur ! NULL){printf(%d-, cur-val);//读结点域cur cur-next; //偏移指针域}printf(NULL\n);
}
struct ListNode* removeELements(struct ListNode* phead, int x)
{struct ListNode* head1;struct ListNode* head2;struct ListNode* tail1;struct ListNode* tail2;//oj题一般malloc不会申请失败可不作检查head1 tail1 (struct ListNode*)malloc(sizeof(struct ListNode));head2 tail2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur phead;while (cur){//尾插 -- val --tail1if (cur-val x){tail1-next cur;tail1 tail1-next;}else//尾插 -- val --tail2{tail2-next cur;tail2 tail2-next;}cur cur-next;//判断一个走一个}//链接tail1和tail2tail1-next head2-next;tail2-next NULL;//更新头结点phead head1-next;free(head1);free(head2);return phead;
}int main()
{struct ListNode* n1 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 (struct ListNode*)malloc(sizeof(struct ListNode));n1-val 7;n2-val 7;n3-val 2;n4-val 3;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;struct ListNode* head removeELements(n1, 6);SLPrint1(head);return 0;
}5、单链表总结
主要有以下两点 与顺序表不同单链表的元素不是连续存储的而是通过指针相连形成链式结构。因此单链表具有以下优缺点。 优点 支持动态内存分配。由于单链表不需要预先分配一段连续的空间因此可以根据实际需求动态地申请、释放节点空间避免浪费内存。 支持高效的插入、删除操作。由于单链表中的节点是通过指针相连的因此在插入、删除一个节点时只需要修改其前驱节点或后继节点的指针即可时间复杂度为O(1)O(1)O(1)。 缺点 不支持随机访问。由于单链表中的节点不是连续存储的因此不能像数组一样通过下标来直接访问一个元素需要从头节点开始遍历整个链表才能访问任意位置的元素。
