网站开发招标技术规范书,网站页面设计规范,黄冈做网站价格,深圳 汽车网站建设目录
前言#xff1a;
链表的定义与结构
单链表的接口实现
显示单链表
创建新结点
单链表尾插
头插的实现简单示例图
尾插经典错误示例1
尾插经典错误示例2
尾插函数的最终实现 单链表头插
单链表尾删
单链表头删
单链表查找
单链表在pos位置之前插入数据x
编…目录
前言
链表的定义与结构
单链表的接口实现
显示单链表
创建新结点
单链表尾插
头插的实现简单示例图
尾插经典错误示例1
尾插经典错误示例2
尾插函数的最终实现 单链表头插
单链表尾删
单链表头删
单链表查找
单链表在pos位置之前插入数据x
编辑
单链表在pos位置之后插入数据x
单链表删除pos位置的值
单链表删除pos位置之后的值 前言 顺序表存在如下问题 顺序表在中间位置或者头部进行元素插入或者删除时由于需要拷贝数据导致时间复杂度为O(N)效率比较低增容需要申请新空间拷贝数据释放旧空间尤其是异地扩容会有不小的消耗增容一般呈两倍增长势必会有一定空间的浪费 上述问题的解决方案会采用另一种线性结构 —— 链表 链表的定义与结构 定义链表是一种物理存储结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 理解思路链表中的每一个数据元素都是独立存储的当需要存储一个数据元素时则向内存的堆区申请一块空间存储当前数据每一个数据元素通过地址串联在一起对于链表这个结构而言不仅需要存储当前的数据元素而且需要存储下一个元素的地址这样才能实现数据元素的串联通常将待存储的数据元素和下一个数据的地址合起来称为链表中的一个节点
示例图 注意事项 链式结构在逻辑上是连续的但是在物理结构上不一定连续结点一般都是在内存的堆区申请堆上申请的空间是按照一定的策略分配俩次申请的空间可能连续也可能不连续 typedef int SLTDatatype;
typedef struct SListNode
{SLTDatatype data;//数据域struct SListNode* next;//存放下一个结点的地址-指针域
}SListNode;
//此结构体大小为8字节
int main()
{//堆区开辟8字节的空间SListNode* p1 (SListNode*)malloc(sizeof(SListNode));//结构体前四个字节存放数据p1-data 10;SListNode* p2 (SListNode*)malloc(sizeof(SListNode));p2-data 20;SListNode* p3 (SListNode*)malloc(sizeof(SListNode));p3-data 30;//结构体后四个字节存放下一个结点的地址p1-next p2;p2-next p3;p3-next NULL;return 0;
}监视窗口 由于结构体的大小为8字节从上图可以看出申请的空间并不一定连续 单链表的接口实现 数据结构无非是对数据进行管理要实现数据的增删查改因此链表的基本功能也是围绕数据的增删查改而展开 显示单链表 顺序表传参时指针必不为空指针而链表传参指针可能为空指针 当链表中没有元素时头指针所指向的就是空指针不可断言指针为空 当链表中存在元素时最后一个结点的指针域必存在空指针当指针域的元素为空停止打印 void PrintSList(SListNode* phead)
{SListNode* cur phead;while (cur ! NULL ){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 显示单链表测试
void Test1()
{SListNode* p1 (SListNode*)malloc(sizeof(SListNode));p1-data 10;SListNode* p2 (SListNode*)malloc(sizeof(SListNode));p2-data 20;SListNode* p3 (SListNode*)malloc(sizeof(SListNode));p3-data 30;p1-next p2;p2-next p3;p3-next NULL;PrintSList(p1);
}
int main()
{Test1();return 0;
}
运行结果 创建新结点 单链表进行头插尾插时插入的是一个结点这个结点包括SLTDatatype数据和SLTDatatype*的指针为防止代码过于冗余单独封装为BuySListNode()函数来创建新结点 SListNode* BuySListNode(SLTDatatype x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
创建新结点测试
void Test2()
{SListNode* n1 BuySListNode(10);SListNode* n2 BuySListNode(20);SListNode* n3 BuySListNode(30);n1-next n2;n2-next n3;PrintSList(n1);
}int main()
{Test2();return 0;
}
运行结果 单链表尾插 实现尾插之前我们先看一个头插的简单的示例并且认知实现尾插时的各种常见错误分析具体原因从而实现真正的尾插函数 头插的实现简单示例图
假设1链表中存在元素如下图所示如何实现头插 首先利用BuySListNode()函数来创建一个新结点newnode; 其次只需要 newnode-next中的NULL变成pList,即newnode-nextpList;
最后使pList指向newnode,即pListnewnode这样便完成链表的头插元素 假设2: 链表中没有元素如何实现头插 1. 首先利用BuySListNode()函数来创建一个新结点newnode; 2. 其次只需要 newnode-next中的NULL变成pList,即newnode-nextpList; 3.最后使pList指向newnode,即pListnewnode这样便完成链表的头插元素 如上所得链表中结点是否存在对于头插的实现逻辑上没有任何区别 尾插经典错误示例1
假设链表中存在结点如何实现尾插? 利用BuySListNode()函数来创建一个新结点newnode找到最后一个元素尾结点尾结点中的指针域赋值为newnode //下述代码正确吗
void SLTpushback(SListNode* phead, SLTDatatype x)
{SListNode* newnode BuySListNode(x);SListNode* tail phead;//查找尾结点 while (tail ! NULL){tail tail-next;}//尾插tail newnode;
} 当调用SLTpushback()函数操作系统会为该函数开辟函数栈帧而phead(形式参数)tail局部变量newnode局部变量的值全部保存在栈空间但是形式参数只是实际参数的一份临时拷贝即值是相同的空间是独立的改变形参并不会影响实参; 局部变量进入作用域创建出作用域由于操作系统回收空间自动销毁 数据结构链表物理图循环结束后内存布局 执行tailnewnode后链表物理图 SLTpushback()函数调用结束链表物理图 如上图所示上述代码不仅没有实现尾插节点的功能 还导致了内存泄漏 假设链表中存在元素实现尾插的思路如下 尾插正确做法1(链表中存在元素) 结点是由malloc()函数在堆区申请的空间,改变堆区的数据随着函数栈帧的销毁数据并不会销毁而形式参数局部变量在栈空间上创建函数栈帧销毁后随之销毁;只需要改变尾结点的指针域存放于堆区使得其指向新结点从而就可以实现尾插; //尾插正确思路(假设链表中存在元素)
void SLTpushback(SListNode* phead, SLTDatatype x)
{SListNode* newnode BuySListNode(x);SListNode* tail phead;while ((tail-next) ! NULL){tail tail-next;}//修改尾结点的指针域tail-next newnode;
}
尾插经典错误示例2
假设链表中没有结点如何实现尾插 利用BuySListNode()函数来创建一个新结点newnode头指针pList赋值为newnode; 链表为空实现尾插物理图 //下述代码正确吗
void SLTpushback(SListNode* phead, SLTDatatype x)
{SListNode* newnode BuySListNode(x);//链表为空,没有结点if (phead NULL){phead newnode;}//链表不为空,存在结点else{SListNode* tail phead;while ((tail-next) ! NULL){tail tail-next;}tail-next newnode;}
}当链表为空时希望实参pList指向新结点但是phead为形式参数对形参phead的修改不会影响实参plist, 而且phead出作用域自动销毁具体见下图所示 传参时物理图 执行pheadnewnode后的物理图 函数调用结束后的物理图 上述代码存在问题它不但丢失了新创建的结点,而且没有修改实参pList没有实现尾插 尾插函数的最终实现 综合上述所有考虑当链表为空时为了能够修改实参pList(头指针我们只能传址调用那么就该采用二级指针来接收参数 ; //尾插新结点
void SLTpushback(SListNode** pphead, SLTDatatype x)
{SListNode* newnode BuySListNode(x);//链表为空,没有结点if (*pphead NULL){*pphead newnode;}//链表不为空,存在结点else{SListNode* tail *pphead;while ((tail-next) ! NULL){tail tail-next;}tail-next newnode;}
}
单链表尾插测试
void Test()
{SListNode* pList NULL;SLTpushback(pList, 1);SLTpushback(pList, 2);SLTpushback(pList, 3);PrintSList(pList);
}
int main()
{Test();return 0;
} 运行结果 单链表头插 正如前文所述单链表中结点是否存在对于头插的实现逻辑上没有任何区别但是由于头插的过程中需要不断的改变单链表中的头结点所以传参时需要头指针的地址方便修改实参 //头插新结点
void SLTpushfront(SListNode** pphead, SLTDatatype x)
{SListNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
单链表头插测试
void Test()
{SListNode* pList NULL;SLTpushfront(pList, 10);SLTpushfront(pList, 20);SLTpushfront(pList, 30);SLTpushfront(pList, 40);PrintSList(pList);
}
int main()
{Test();return 0;
}
运行结果 单链表尾删 链表的核心特性在于前后关联不能只考虑单个结点如果只考虑单个结点该结点前后的结点容易出现错误比如实现尾删时如果只想找到链表最后一个元素进而释放尾结点的空间但是尾结点的前一个节点的指针域并未置空仍然指向一块未知空间造成野指针 假设链表中存在两个及两个以上的结点如何实现尾删
首先找到尾结点的上一个节点 释放tail-next所指向的空间 将tail-nextNULL即可 通过上述三个图发现好像当单链表尾删传参时并不需要二级指针 假设链表中存在1个结点如何实现尾删 当链表中只有一个节点时根本不存在前一个节点上述针对多结点的方式已经失效 当尾删掉这个节点之后需要将pList置为空指针如何改变pList ? 因此传参时只能传址调用只有传址才能改变pList中的值 所以当进行尾删时只能传递二级指针 当链表为空时不能进行尾删操作因此需要对链表进行判空 单链表尾删实现方式一
void SLTpopback(SListNode** pphead)
{//单链表为空assert(*pphead ! NULL);//单链表只有一个结点if ((*pphead)-next NULL){free(*pphead);//其实*pphead就是pList*pphead NULL;}//单链表有多个结点else{SListNode* tailPrev NULL;//记录尾结点的前一个结点SListNode* tail *pphead; //寻找尾结点while (tail-next!NULL){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}
} 单链表尾删实现方式2
void SLTpopback(SListNode** pphead)
{//单链表为空assert(*pphead ! NULL);//单链表只有一个结点if ((*pphead)-next NULL){free(*pphead);//其实*pphead就是pList*pphead NULL;}//单链表有多个结点else{SListNode* tail *pphead;while (tail-next-next!NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}
单链表尾删测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 11);SLTpushback(plist, 22);SLTpushback(plist, 33);PrintSList(plist);SLTpopback(plist);PrintSList(plist);SLTpopback(plist);PrintSList(plist);SLTpopback(plist);PrintSList(plist);
}int main()
{Test();return 0;
}
运行结果 单链表头删 对链表进行头删操作需要对链表的头结点进行改变,所以传参时需要传址调用需要头指针的地址因此参数为二级指针链表为空不能进行头删操作因此需要对链表进行判空 假设链表中存在两个及两个以上的结点如何实现头删 case 1 如果直接释放首结点通过pList无法查找到首节点的下一个结点 case2 如果让pList直接指向首结点的下一个节点由于首结点丢失无法释放首结点 case 1
case 2 单链表头删的实现方式
//单链表头删
void SLTpopfront(SListNode** pphead)
{//判空assert(*pphead!NULL);//非空SListNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
} 单链表头删测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 10);SLTpushback(plist, 20);SLTpushback(plist, 30);PrintSList(plist);SLTpopfront(plist);PrintSList(plist);SLTpopfront(plist);PrintSList(plist);SLTpopfront(plist);PrintSList(plist);
}
int main()
{Test();return 0;
}
运行结果 单链表查找 按照数据进行查找找到返回结点位置找不到返回空指针 SListNode* SListFind(SListNode* phead, SLTDatatype x)
{assert(phead ! NULL);SListNode* cur phead;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
单链表查找测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 10);SLTpushback(plist, 20);SLTpushback(plist, 30);SLTpushback(plist, 40);SLTpushback(plist, 50);printf(请输入要查找的值\n);int x 0;scanf(%d, x);SListNode* pos SListFind(plist, x);if (pos ! NULL){pos-data pos-data * 10;}PrintSList(plist);
}
int main()
{Test();return 0;
}运行结果 查找函数的接口既实现了查找的功能又承担了修改数据的功能 单链表在pos位置之前插入数据x case 1: pos位置处的结点就是首节点需要改变头指针的值传参时应该传址调用 case 2pos位置处的结点非首结点 需要查找pos位置的前一个节点将前一个结点的指针域置为newnode; void SListInsert(SListNode** pphead, SListNode* pos, SLTDatatype x)
{assert(pos ! NULL);if (*pphead pos){SLTpushfront(pphead, x);}else{SListNode* posprev *pphead;while (posprev-next ! pos){posprev posprev-next;}SListNode* newnode BuySListNode(x);newnode-next pos;posprev-next newnode;}
}
SListInsert() 函数测试
void Test9()
{SListNode* plist NULL;SLTpushback(plist, 1);SLTpushback(plist, 2);SLTpushback(plist, 3);SLTpushback(plist, 4);SLTpushback(plist, 5);int x 0;scanf(%d, x);SListNode* pos SListFind(plist, x);if (pos ! NULL){SListInsert(plist, pos, x*10);}PrintSList(plist);
}
int main()
{Test9();return 0;
}运行结果 单链表在pos位置之后插入数据x 当在pos位置之后插入数据不需要查找前一个结点只需要根据pos的位置就可完成插入 void SListInsertAfter(SListNode* pos, SLTDatatype x)
{assert(pos ! NULL);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;} SListInsertAfter()函数测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 1);SLTpushback(plist, 2);SLTpushback(plist, 3);SLTpushback(plist, 4);SLTpushback(plist, 5);int x 0;scanf(%d, x);SListNode* pos SListFind(plist, x);if (pos ! NULL){SListInsertAfter(pos, x * 10);}PrintSList(plist);
}
int main()
{Test();return 0;
}运行结果 单链表删除pos位置的值 假设pos位置处的结点非首结点 查找pos位置处的前一个结点 将pos处的前一个节点的指针域赋值为pos后一个节点 释放pos处的空间 假设pos位置为首结点直接按照头删的逻辑处理 void SListEarse(SListNode** pphead, SListNode* pos)
{assert(pos ! NULL);if (*pphead pos){SLTpopfront(pphead);}else{SListNode* posprev *pphead;while (posprev-next ! pos){posprev posprev-next;}posprev-next pos-next;free(pos);}
}
单链表删除指定结点的值测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 1);SLTpushback(plist, 2);SLTpushback(plist, 3);SLTpushback(plist, 4);SLTpushback(plist, 5);PrintSList(plist);int x 0;scanf(%d, x);SListNode* pos SListFind(plist, x);if (pos ! NULL){SListEarse(plist, pos);}PrintSList(plist);
}
int main()
{Test();return 0;
}运行结果 单链表删除pos位置之后的值
void SListEarseAfter(SListNode* pos)
{assert(pos);// 检查pos是否是尾节点assert(pos-next);SListNode* posnext pos-next;pos-next posnext-next;free(posnext);posnext NULL;}
SListEarseAfter()函数测试
void Test()
{SListNode* plist NULL;SLTpushback(plist, 1);SLTpushback(plist, 2);SLTpushback(plist, 3);SLTpushback(plist, 4);SLTpushback(plist, 5);PrintSList(plist);int x 0;scanf(%d, x);SListNode* pos SListFind(plist, x);if (pos ! NULL){SListEarseAfter(pos);}PrintSList(plist);
}
int main()
{Test()return 0;
}
运行结果:
