网站建设 商业价值,南京建设人才网站,哪家微网站建设,上海企业名录地址电话目录
一、顺序表的缺陷
二、链表
1.链表的概念以及结构
2.链表的分类
3.单链表的逻辑结构与物理结构
三、单链表的实现
1.单链表的定义
2.单链表的接口定义
3.单链表的接口实现
四、单链表的实现完整代码 一、顺序表的缺陷 在上一篇文章中#xff0c;我们了解了顺序…目录
一、顺序表的缺陷
二、链表
1.链表的概念以及结构
2.链表的分类
3.单链表的逻辑结构与物理结构
三、单链表的实现
1.单链表的定义
2.单链表的接口定义
3.单链表的接口实现
四、单链表的实现完整代码 一、顺序表的缺陷 在上一篇文章中我们了解了顺序表的结构以及他的接口的实现。但同时我们也发现了他的一些缺陷 问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看 二、链表
1.链表的概念以及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 2.链表的分类 链表一共有八种类型他们可由是单向还是双向是循环还是非循环是带头结点还是不带头结点进行排列组合出八种结构 虽然有很多种结构但是只有两种最为常用 无头单向非循环链表和带头双向循环链表 这里我们先只需要了解无头单向非循环链表其他链表后续了解 3.单链表的逻辑结构与物理结构 如下图所示是链表的实际的物理结构与逻辑结构。物理结构就是实实在在数据在内存中的变化逻辑结构就是为了方便理解形象化出来的 三、单链表的实现
1.单链表的定义 typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode; 如上代码所示单链表有数据域和指针域两部分组成指针是用于指向下一个结点的指针 2.单链表的接口定义 //单链表的打印
void SListPrint(SListNode* plist);
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
//单链表的尾删
void SListPopBack(SListNode** pplist);
//单链表的头删
void SListPopFront(SListNode** pplist);
//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x);
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos);
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos);
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos);
//单链表的销毁
void SListDestroy(SListNode** pplist); 如上代码所示是我们的单链表需要实现的接口对于链表和顺序表一样都是为了实现数据的管理区别就是前者是离散的后者是连续的。我们的目的还是增删查改 3.单链表的接口实现 1.单链表的打印 //单链表的打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 我们先来完成单链表的打印对于单链表的打印还是比较简单的只需要先将头结点的指针给保存下来然后依次去遍历单链表即可 2.单链表的尾插以及获取结点函数 //获取一个结点
SListNode* BuySListNode(SLTDateType x)
{SListNode* tmp (SListNode*)malloc(sizeof(SListNode));if (tmp NULL){perror(malloc fail);return;}tmp-next NULL;tmp-data x;return tmp;
}//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;return;}SListNode* tail (*pplist);while (tail-next ! NULL){tail tail-next;}tail-next newnode;
} 对于单链表的尾插我们要特别注意了。pplist是单链表头结点的地址所以一定不为空 首先是获取结点我们为了方便先直接将其封装为一个函数。 有了结点了那么我们还要思考如何尾插那么我们先完成一般情况假设已经有了一个很长的单链表了我们还想要继续尾插一个值那么只需要先找到原来的尾结点然后将尾结点和新结点进行链接即可 当然还是存在一些特殊情况的比如说原来的单链表压根就没有尾结点也就是说链表是空的那么上面的一般方法肯定行不通这里其实就需要特殊处理一下直接将新节点和链表头链接起来即可 3.单链表的头插 //单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);SListNode* first *pplist;*pplist newnode;newnode-next first;
} 对于单链表的头插就比较简单了我们直接创建一个新结点然后记录下原来的第一个结点的地址然后让链表头与新节点链接起来然后新节点与原来的第一个结点链接起来这里我们会发下其实是不需要处理空链表的情况的这里体现了单链表适合头插 4.单链表的尾删 //单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* tail *pplist;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
} 对于单链表的尾删我们要想清楚了首先是一般情况当链表很长的时候我们想要删除最后一个结点那么得先找到前一个结点然后释放最后一个结点最后让前一个结点指向空。 我们还需要注意链表为空的状态这个肯定是不可以删除的所以我们直接断言掉。 然后是链表为一个结点的情况如果链表只有一个结点那么我们会发现压根找不到前一个结点所以我们也特殊处理我们直接释放掉第一个结点然后置空即可。 5.单链表的头删 //单链表的头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* second (*pplist)-next;free(*pplist);*pplist second;
} 对于单链表的头删我们同样断言掉链表为空的状态 然后我们需要做的就是记录第二个结点然后释放原来的第一个结点最后连接链表头和第二个结点。这样我们就实现了我们的目的。值得注意的是我们发现链表的头删也是比较有优势的。 6.单链表的查找 //单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x)
{SListNode* cur plist;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
} 对于单链表的查找这个也很简单他和单链表的打印思路是一样的不同的是只需要返回结点的地址即可。 7.单链表在pos位置之后的插入 //单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);SListNode* next pos-next;pos-next newnode;newnode-next next;
} 单链表在pos位置之后的插入也是比较简单的我们只需要先申请一个结点然后记录pos位置的下一个结点然后连接就可以了。值得注意的是pos的位置不可能为空。因为他不是一个有效的结点地址 8.单链表在pos位置之前的插入 //单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x)
{assert(pplist);assert(pos);assert(*pplist);SListNode* newnode BuySListNode(x);if (*pplist pos){*pplist newnode;newnode-next pos;}else{SListNode* prev *pplist;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
} 对于在pos位置之前的插入确实是比较繁琐了。我们要思考首先pos和pplist不可能为空然后这个链表也是不可能为空链表的至少也要有一个值。否则如果存在pos这个结点呢 然后我们在来考虑一般情况我们假设链表很长在中间位置pos之前插入一个结点那么毫无疑问的是我们需要先申请一个结点然后在通过遍历的方式要找到pos之前的那个结点。 有了这两个结点那么我们就可以进行连接了。 然后是特殊情况假如这个链表只有一个结点呢这个结点正好就是pos我们发现pos就没有前一个结点其实这个就等效于头插。我们采用头插的方式即可 9.单链表在pos之后删除 //单链表在pos之后删除
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);SListNode* next pos-next;pos-next next-next;free(next);next NULL;
} 单链表在pos之后删除的话首先pos和pos的下一个结点不会为空否则题目就矛盾了。所以我们得断言然后我们直接记录pos 的下一个结点然后连接pos和pos之后的结点。最后释放掉pos的下一个结点即可。 10.单链表在pos之前删除 //单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos)
{assert(pos);assert(pplist);assert(pos ! *pplist);assert(*pplist);if ((*pplist)-next pos){SListNode* del *pplist;*pplist pos;free(del);del NULL;}else{SListNode* prev *pplist;while (prev-next-next ! pos){prev prev-next;}SListNode* del prev-next;prev-next pos;free(del);del NULL;}
} 对于单链表在pos之前删除确实就比较复杂了首先pospplist*pplist肯定不可能为空然后pos也绝不可以是头节点所以pos*pplist 我们现在来思考假设一般情况链表很长在中间位置是pos删除pos的前一个结点那么我们就需要找到pos 的前一个的前一个结点。然后记录pos的前一个结点。释放pos 的前一个结点然后进行连接即可 对于特殊情况也就是pos在第二个结点上这样我们无法找到pos的前一个的前一个结点但是这个就是头删我们直接采用类似的思路即可 11.单链表在pos位置的删除 //单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);assert(*pplist);if (*pplist pos){free(pos);*pplist pos NULL;}else{SListNode* prev *pplist;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
} 这个与上一个接口是基本一致的思路。不同的是pos可以在头结点了如果是头节点就是头删。 如果不是就是先找到前一个结点然后进行删除连接即可 12.单链表的销毁 //单链表的销毁
void SListDestroy(SListNode** pplist)
{SListNode* cur *pplist;while (cur ! NULL){SListNode* next cur-next;free(cur);cur next;}
} 对于单链表的销毁这个也很简单就直接遍历销毁即可与打印和查找的思路是一致的 四、单链表的实现完整代码 SList.h文件 #pragma once#includestdio.h
#includestdlib.h
#includemalloc.h
#includeassert.htypedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;//单链表的打印
void SListPrint(SListNode* plist);
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
//单链表的尾删
void SListPopBack(SListNode** pplist);
//单链表的头删
void SListPopFront(SListNode** pplist);
//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x);
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos);
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos);
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos);
//单链表的销毁
void SListDestroy(SListNode** pplist); SList.c文件 #define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h//单链表的打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//获取一个结点
SListNode* BuySListNode(SLTDateType x)
{SListNode* tmp (SListNode*)malloc(sizeof(SListNode));if (tmp NULL){perror(malloc fail);return;}tmp-next NULL;tmp-data x;return tmp;
}//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;return;}SListNode* tail (*pplist);while (tail-next ! NULL){tail tail-next;}tail-next newnode;
}//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);SListNode* first *pplist;*pplist newnode;newnode-next first;
}//单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* tail *pplist;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}//单链表的头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* second (*pplist)-next;free(*pplist);*pplist second;
}//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x)
{SListNode* cur plist;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);SListNode* next pos-next;pos-next newnode;newnode-next next;
}
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x)
{assert(pplist);assert(pos);assert(*pplist);SListNode* newnode BuySListNode(x);if (*pplist pos){*pplist newnode;newnode-next pos;}else{SListNode* prev *pplist;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);SListNode* next pos-next;pos-next next-next;free(next);next NULL;
}
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos)
{assert(pos);assert(pplist);assert(pos ! *pplist);assert(*pplist);if ((*pplist)-next pos){SListNode* del *pplist;*pplist pos;free(del);del NULL;}else{SListNode* prev *pplist;while (prev-next-next ! pos){prev prev-next;}SListNode* del prev-next;prev-next pos;free(del);del NULL;}
}
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);assert(*pplist);if (*pplist pos){free(pos);*pplist pos NULL;}else{SListNode* prev *pplist;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
//单链表的销毁
void SListDestroy(SListNode** pplist)
{SListNode* cur *pplist;while (cur ! NULL){SListNode* next cur-next;free(cur);cur next;}
} Test.c文件 #define _CRT_SECURE_NO_WARNINGS 1#includeSlist.hvoid TestSList1()
{SListNode* phead NULL;SListPushBack(phead, 1);SListPushBack(phead, 2);SListPushBack(phead, 3);SListPushBack(phead, 4);SListPushBack(phead, 5);SListPrint(phead);SListPushFront(phead, 6);SListPushFront(phead, 7);SListPushFront(phead, 8);SListPushFront(phead, 9);SListPushFront(phead, 10);SListPrint(phead);SListPopBack(phead);SListPopBack(phead);SListPopBack(phead);SListPopBack(phead);SListPrint(phead);SListPopBack(phead);SListPrint(phead);}
void TestSList2()
{SListNode* phead NULL;SListPushBack(phead, 1);SListPushBack(phead, 2);SListPushBack(phead, 3);SListPushBack(phead, 4);SListPushBack(phead, 5);SListPrint(phead);SListPopFront(phead);SListPopFront(phead);SListPopFront(phead);SListPopFront(phead);SListPrint(phead);SListPopFront(phead);SListPrint(phead);
}
void TestSList3()
{SListNode* phead NULL;SListPushBack(phead, 1);SListPushBack(phead, 2);SListPushBack(phead, 3);SListPushBack(phead, 4);SListPushBack(phead, 5);SListPrint(phead);SListNode* pos SListFind(phead, 3);pos-data 100;SListPrint(phead);SListInsertAfter(pos, 200);SListInsertAfter(pos, 300);SListInsertAfter(pos, 400);SListInsertAfter(pos, 500);SListPrint(phead);SListNode* pos2 SListFind(phead, 1);SListInsertPrev(phead, pos2, 101);SListInsertPrev(phead, pos2, 102);SListInsertPrev(phead, pos2, 103);SListInsertPrev(phead, pos2, 104);SListPrint(phead);SListEraseAfter(pos2);SListEraseAfter(pos2);SListEraseAfter(pos2);SListPrint(phead);}void TestSList4()
{SListNode* phead NULL;SListPushBack(phead, 1);SListPushBack(phead, 2);SListPushBack(phead, 3);SListPushBack(phead, 4);SListPushBack(phead, 5);SListPrint(phead);SListNode* pos SListFind(phead, 5);SListErasePrev(phead, pos);SListPrint(phead);SListErasePrev(phead, pos);SListPrint(phead);SListErase(phead, pos);SListPrint(phead);SListDestroy(phead);
}int main()
{//TestSList1();//TestSList2();//TestSList3();TestSList4();return 0;
} 本节内容到此位置感谢您的阅读
如果对你有帮助的话不要忘记点赞加收藏哦
