佛山营销网站设计,建设公司网站价格,dede仿网站目录,优设网的吉祥物单链表的实现#xff08;Single Linked List#xff09;—直接拿下#xff01; 文章目录 单链表的实现#xff08;Single Linked List#xff09;---直接拿下#xff01;一、单链表的模型二、代码实现#xff0c;接口函数实现①初始化②打印链表③创建一个结点④尾插⑤尾…单链表的实现Single Linked List—直接拿下 文章目录 单链表的实现Single Linked List---直接拿下一、单链表的模型二、代码实现接口函数实现①初始化②打印链表③创建一个结点④尾插⑤尾删⑥头插⑦头删⑧查找结点⑨在pos位置的结点处插入一个新节点不删除pos结点在pos结点前插入⑩删除pos位置的结点。⑪在pos位后面插入⑫删除pos位后面的结点⑬销毁链表⑭测试用例 三、总结 一、单链表的模型
链表也是一种线性表和我们之前讲过的顺序表属于一个大类。 这是之前有关顺序表的介绍如果大家有兴趣的话可以点击下面链接。 顺序表的实现 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 存储结构实际存在的非线性的逻辑结构人们想象出来的是线性的。 注意pList只是一个指针它本身不是一个结点。最后一个包含数值4的结点指向的下一个结点的指针就是NULL。 而且这些结点都是从堆上申请而来的从堆上申请空间是按照一定策略分配的两次申请的空间可能连续也可能不连续。
typedef int SLDataType;
typedef struct SLNode
{SLDataType val;struct SLNode* next;
}SL;二、代码实现接口函数实现
①初始化
void SLIni(SL** phead)
{assert(phead);*phead NULL;
}②打印链表
void SLPrint(SL* phead)
{SL* cur phead;//我们要养成一个良好的习惯这样多创建一个变量。while (cur)//注意此处打印不需要assert断言//因为空链表也需要打印出一个NULL{printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}相信大家已经发现了我的备注空链表是什么鬼不急大家先来看一下尾插的实现后我就给大家详细解释一下。 ③创建一个结点
SL* SLCreateNode(x)
{SL* newnode (SL*)malloc(sizeof(SL));if (newnode NULL){perror(malloc);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}④尾插
void SLPushBack(SL** phead, SLDataType x)
{assert(phead);SL* newnode SLCreateNode(x);if (*phead NULL){*phead newnode;}else{SL* tail *phead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}相信大家经过尾插后一下子就看懂了空链表就是首结点的指针直接指向NULL而这样的链表在尾插时我只需要把首结点的指针指向新创建的结点就啦。 ⑤尾删 大家先来思考两个问题 1.空结点还能删吗当然是不能呀家都没了就别拆了。 2.一个结点的链表删了之后是不是就只剩一个NULL了对所以头结点指针需要改变了指向NULL。 void SLPopBack(SL** phead)
{assert(phead);assert(*phead);//避免空节点SL* tail *phead;SL* cur tail;if (cur-next NULL)//只有一个结点的链表{free(*phead);*phead NULL;}else{while (tail-next){cur tail;tail tail-next;}free(tail);cur-next NULL;}
}相信大家已经看出来了单链表有几个特殊的情况也就是空链表和只有一个结点的链表所以无论大家以后在写代码或者OJ题的过程中切记要考虑三个情矿空链表一个结点和正常多个结点的链表 。
⑥头插
void SLPushFront(SL** phead, SLDataType x)
{assert(phead);SL* newnode SLCreateNode(x);newnode-next *phead;*phead newnode;
}⑦头删
void SLPopFront(SL** phead)
{assert(phead);assert(*phead);SL* next (*phead)-next;free(*phead);*phead next;
}单链表进行头插、头删真的很方便。 ⑧查找结点
SL* SLFind(SL* phead, SLDataType x)
{while (phead){if (phead-val x){return phead;}phead phead-next;}return NULL;
}⑨在pos位置的结点处插入一个新节点不删除pos结点在pos结点前插入
void SLInsert(SL** phead, SLDataType x, SL* pos)//在pos位置之前插入
{//一定要保证pos是链表里的一个有效结点。assert(pos);assert(phead);assert(*phead);if (*phead pos)//头插需要单独拎出来要不然这种情况就会被漏掉。{SLPushFront(phead, x);}else{SL* cur *phead;while (cur-next ! pos){cur cur-next;}SL* newnode SLCreateNode(x);cur-next newnode;newnode-next pos;}
}⑩删除pos位置的结点。
void SLErase(SL** phead, SL* pos)
{assert(phead);assert(*phead);assert(pos);if (*phead pos)//头删需要单独拎出来要不然这种情况会被漏掉。{SLPopFront(phead);}else{SL* cur *phead;while (cur-next ! pos){cur cur-next;}cur-next pos-next;free(pos);pos NULL;}
}⑪在pos位后面插入
void SLInsertAfter(SLDataType x, SL* pos)
{assert(pos);//这么一步已经把空链表刨除在外了//因为严格限制pos必须是链表里的一个有效结点。SL* newnode SLCreateNode(x);newnode-next pos-next;pos-next newnode;
}这种情况就不需要传头结点指针了因为在保证pos是链表里的一个有效结点后不像在pos位置前插入需要遍历链表找到pos位前一位的结点这种情况直接在pos位后面插入就好了。这个是因为受限于单链表的性质单向走无法回溯。 ⑫删除pos位后面的结点
void SLEraseAfter(SL* pos)
{assert(pos);assert(pos-next);SL* tmp pos-next;pos-next tmp-next;free(tmp);tmp NULL;
}⑬销毁链表
void SLDestroy(SL** phead)
{assert(phead);SL* cur *phead;while (cur){SL* next cur-next;free(cur);cur next;}*phead NULL;
}⑭测试用例
#define _CRT_SECURE_NO_WARNINGS
#includeSList.hvoid test1()
{SL P;SL* p1 P;SL** phead p1;SLIni(phead);SLPushBack(phead, 1);SLPushBack(phead, 2);SLPushBack(phead, 3);SLPushBack(phead, 4);SLPushBack(phead, 5);SLPrint(p1);SLPopBack(phead);SLPopBack(phead);SLPopBack(phead);SLPopBack(phead);SLPopBack(phead);SLPrint(p1);
}void test2()
{SL P;SL* p1 P;SL** phead p1;SLIni(phead);SLPushFront(phead, 1);SLPushFront(phead, 2);SLPushFront(phead, 3);SLPushFront(phead, 4);SLPushFront(phead, 5);SLPrint(p1);SLPopFront(phead);SLPopFront(phead);SLPopFront(phead);SLPopFront(phead);SLPopFront(phead);SLPrint(p1);
}void test3()
{SL P;SL* p1 P;SL** phead p1;SLIni(phead);SLPushBack(phead, 1);SLPushBack(phead, 2);SLPushBack(phead, 3);SLPushBack(phead, 4);SLPushBack(phead, 5);SL* ret SLFind(p1, 3);SL* ret1 SLFind(p1, 1);printf(%d\n, ret-val);//SLErase(phead, ret);SLErase(phead, ret1);SLInsert(phead, 100, ret);SLPrint(p1);
}int main()
{//test1();//test2();test3();
}三、总结
最重要的一点一定要考虑单链表空链表、一个结点(也包括需要单独考虑尾结点NULL前的结点和单独考虑头结点和正常的情况。初次之外还有很重要的一点一定不要对空指针解引用。 单链表在实现头插和头删真的很方便但是大家相信大家也会发现实现尾插和尾删找尾的过程时间复杂度是O(n)。 所以这就引出我们的神中神链表双向带头循环链表。 l带头双向循环链表
