【数据结构】 |
您所在的位置：网站首页 › 单向链表的删除代码 › 【数据结构】 |
【数据结构】
|
链表的概念： 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 链表的结构：链表是由一个个结点组成的，结点如下图所示：  注意：链表中的最后一个结点的next指向空，next=NULL。 一个个结点串成了链表，如下图所示：  有人可能会有疑问，不是说链表只是在逻辑结构上是连续的，在物理存储结构上是不连续的，那为什么上图中一个个结点明明是挨在一起的，那么它在物理存储结构上肯定是连续的呀，其实不然，上图是为了方便大家理解，才用线条连接了结点，实际上在内存中，每个结点可能会隔得很远，仔细观察每个结点上面的红色文字，那就是这个结点的地址，而蓝色文字是下一个结点的地址，很明显能看到这两个结点并不是相邻的，因此也验证了顺序表在逻辑结构上确实是连续的，但在物理存储结构上确实是不连续的。 链表的实现：1.1定义节点介绍一下单链表的英文名——single linked list，我们简写成SL（区别于顺序表的SeqList或者SQL）。 代码语言：javascript复制typedef int SLTDateType; typedef struct SListNode { SLTDateType Date; SListNode* next; }SListNode;1.2链表的功能链表要实现那些功能呢？其实这些功能我们都很熟悉，数据结构无非是对数据进行管理，要实现数据的增删查改，因此链表的基本功能也都是围绕着数据的增删查改展开。 这里我们要注意一点，链表是不需要进行初始化的 代码语言：javascript复制//创建一个结点 SLTNode* BuyListNode(SLTDateType x); //销毁单链表 void SLTDestory(SLTNode** pphead); //单链表头插 void SLTPushFront(SLTNode** pphead, SLTDateType x); //单链表尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x); //单链表头删 void SLTPopFront(SLTNode** pphead); //单链表尾删 void SLTPopBack(SLTNode** pphead); //单链表结点查找 SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x); //单链表结点删除(删除pos位置的结点) void SLTErase(SLTNode** pphead, SLTNode* pos); //单链表结点插入(在pos之前插入) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 单链表结点插入(在pos之后插入) void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x); //打印单链表 void PrintSLT(SLTNode * phead);链表功能的实现2.1打印单链表注意：链表和顺序不同的是，顺序表传过来的指针是肯定不会为空的，而链表传过来的指针是可能为空的，比如说当链表中没有元素时，头指针所指向的就是NULL，如果在第一行写上断言就会有问题。 当cur指向空的时候就可以停止打印了。 代码语言：javascript复制void PrintSLT(SListNode*phead) { //注意：不需要断言assert(psl)； SListNode* cur = phead; while (cur) { printf("%d->", cur->date); cur = cur->next; } printf("NULL"); printf("\n"); //最后打印出来的效果就是 1->2->3->4->NULL }2.2 创建一个新结点后面我们要在单链表中进行头插和尾插，此时插入的不再是像顺序表一样简单的SLDateType数据了，而是一个结点，这个结点是包括SLTDateType数据以及SLTDateType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。 代码语言：javascript复制//创建一个新结点 SListNode* BuySLTNode(SLDateType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (newNode == NULL) { perror("malloc:"); return; } newNode->date = x; newNode->next = NULL; return newNode; }2.3 单链表尾插注意：在创建结点时，已经让 结点.next=NULL，所以不需要在插入完结点后，再让新结点的next指针为NULL。 有人可能会有疑问，为什么之前打印链表的时候不用断言指针，而在尾插时就要断言指针，以及为什么函数的形参是二级指针，而不使用一级指针。 因为，尾插分为两种情况（下面有写），当链表为空时，头指针phead指向NULL，尾插相当于头插，此时要改变phead的指向，让phead指向这个新结点，此时就需要二级指针来改变一级指针的值（如果我们用一级指针做形参，形参的改变不会影响实参，那么一级指针phead就不会被改变）。 至于这个什么时候要断言指针，什么时候不用断言指针：一级指针也就是phead，当链表为空的时候，phead就是为NULL，而二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以需要断言pphead。 代码语言：javascript复制//单链表尾插 void SLTPushBack(SListNode**pphead, SLDateType x) { assert(pphead); SListNode* newnode = BuySLTNode(x); //1.链表为空 //2.链表不为空 if (*pphead == NULL) { *pphead = newnode; //不需要让newnode->next=NULL,在BuySLTNode中我们就已经进行过这个操作了 } else { //找到链表的尾巴tail SListNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode; } }2.4顺序表头删头删没什么好说的，记住要断言*pphead，保证链表内容不为空。 代码语言：javascript复制//头删 void SListPopFront(SListNode** pphead) { assert(pphead); assert(*pphead); SListNode* cur = *pphead; *pphead = (*pphead)->next; free(cur); cur = NULL; }2.5顺序表头插现在是不是觉得头插很简单了啊！ 代码语言：javascript复制//头插 void SListPushFront(SListNode** pphead,SLDateType x) { assert(pphead); SListNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }2.6查找某个结点这个函数返回值不再是void，而是SListNode*，把找到的结点的地址返回去，这个函数一般会跟结点修改之类的函数一起使用。 代码语言：javascript复制//单链表结点的查找 SListNode* SListNodeFind(SListNode* phead,SLDateType x) { SListNode* cur = phead; while (cur) { if (cur->date == x) { return cur; } cur = cur->next; } return NULL; }2.7删除某个结点代码语言：javascript复制//删除某个结点 void SListNodeErase(SListNode** pphead, SListNode* pos) { assert(pphead); assert(pos); //头删 //非头删 if (*pphead == pos) { SListNode* cur = *pphead; *pphead = (*pphead)->next; free(cur); cur = NULL; } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev->next); //这里为什么要加个断言? } prev->next = pos->next; free(pos); } }注意： pos也要断言，pos可不能为空呀！cur->next也要断言，因为当cur->next为NULL时，说明整个链表的结点都排查完了，最后还是没有找到地址为pos的结点，证明pos传值有误。 2.8单链表结点修改代码语言：javascript复制// 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x) { SLTNode* cur = phead; while (cur != pos) { cur = cur->next; assert(cur); } pos->data = x; }2.9单链表前插入结点代码语言：javascript复制//单链表前插入结点 void SLTInsertFront(SListNode** pphead, SListNode* pos,SLDateType x) { assert(pphead); assert(pos); //头插 //非头插 SListNode* newnode = BuySLTNode(x); if ((*pphead)->next == pos) { newnode->next = *pphead; *pphead = newnode; } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev->next); } newnode->next = pos; prev->next = newnode; } }2.10单链表后插入结点这里我要提醒一下，千万不要忘记判断pos是否正确，不要只单单断言pos是否为NULL，还要判断能不能在链表中找到pos这个地址（我第一次写链表就忘记检查了，第二次写还是忘记了，非常容易忘记 代码语言：javascript复制//单链表后插入结点 void SLTInsertBack(SListNode* phead, SListNode* pos, SLDateType x) { assert(pos); SListNode* cur = phead; //防止pos传错了 while (cur != pos) { cur = cur->next; assert(pos); } SListNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }2.11销毁链表销毁链表这一块，咱可不敢直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。 代码语言：javascript复制//销毁链表 void SLTDestory(SListNode** pphead) { assert(pphead); SListNode* cur = *pphead; while (cur) { SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }总代码：3.1 SLT.h代码语言：javascript复制#pragma once #include #include #include typedef int SLTDateType; typedef struct SLTNode { SLTDateType data; struct SLTNode* next; }SLTNode; //创建一个结点 SLTNode* BuyListNode(SLTDateType x); //销毁单链表 void SLTDestory(SLTNode** pphead); //单链表头插 void SLTPushFront(SLTNode** pphead, SLTDateType x); //单链表尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x); //单链表头删 void SLTPopFront(SLTNode** pphead); //单链表尾删 void SLTPopBack(SLTNode** pphead); //单链表结点查找 SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x); //单链表结点删除(删除pos位置的结点) void SLTErase(SLTNode** pphead, SLTNode* pos); //单链表结点插入(在pos之前插入) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 单链表结点插入(在pos之后插入) void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x); //打印单链表 void PrintSLT(SLTNode * phead);3.2 SLT.c代码语言：javascript复制#include"SLT.h" //建立一个新的结点 //这是链表的缺点：经常需要使用malloc为newnode开辟空间 SLTNode* BuyListNode(SLTDateType x) { //为什么要用malloc，是因为，如果在BuyListNode函数中SLTNode newnode，出了这个函数，newnode就被销毁了， //用malloc开辟空间，只要我们不主动释放这个空间，这个空间的数据一直存在， SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //static SLTNode newnode； if (newnode == NULL) { perror("malloc:"); exit(0); } newnode->data = x; newnode->next = NULL; return newnode; } //头插 void SLTPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead);//phead可能为NULL，但是pphead指向phead，不可能为空 SLTNode* newnode = BuyListNode(x); //这里可不是newnode->next = (*pphead)->next; newnode->next = *pphead; *pphead = newnode; } //尾插 //尾插特别容易出错，当链表中没有数据，即phead=NULL时，尾插就相当于头插了，此时需要改变phead的值 void SLTPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuyListNode(x); //1、空 //2、非空 if (*pphead == NULL) { *pphead = newnode; //newnode->next = NULL;这一步是不需要的，newnode在建立的时候就默认newnode->next=NULL； } else { SLTNode* cur = *pphead; //这是单向链表的缺点，需要去找尾 while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; } } //头删 void SLTPopFront(SLTNode** pphead) { assert(pphead); //温柔的检查 if (*pphead == NULL) return; //暴力的检查 assert(*pphead); SLTNode* head = *pphead; *pphead = (*pphead)->next; free(head); head = NULL; } //尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); //1、一个结点 //2、两个结点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* cur = *pphead; while (cur->next->next) { cur = cur->next; } free(cur->next); cur->next = NULL; } } //打印单向链表 void PrintSLT(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL"); printf("\n"); } //单链表查找某个结点 SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x) { SLTNode* find = phead; //别忘记分析找不到结点的情况 while (find) { if (find->data == x) { return find; } find = find->next; } return NULL; } //删除pos位置的结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; //如果prev->next已经为空了，说明链表已经查完了，还没有查到pos //证明pos传入有误 assert(prev->next); } prev->next = pos->next; free(pos); //pos = NULL;这个没必要，改变不了pos } } //单链表结点前插 //一般插入结点都是在pos之前插入，但单链表在实现前插是比较困难的 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); //头插 if (pos == *pphead) { SLTPushFront(pphead, x); } //非头插 else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev->next); } SLTNode* newnode = BuyListNode(x); prev->next = newnode; newnode->next = pos; } } //单链表结点后插 void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x) { SLTNode* cur = *pphead; while (cur != pos) { cur = cur->next; //防止pos传错了 assert(cur); } SLTNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode; } // 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x) { SLTNode* cur = phead; while (cur != pos) { cur = cur->next; assert(cur); } pos->data = x; } //销毁链表 void SLTDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; //比cur->next!=NULL更好一些 while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }3.3 test.c代码语言：javascript复制#include"SLT.h" void test1() { SLTNode* plist = NULL; SLTPushFront(&plist, 0); SLTPushFront(&plist, -1); SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); PrintSLT(plist); SLTPopFront(&plist); SLTPopBack(&plist); PrintSLT(plist); SLTNode* pos = SLTNodeFind(plist, 0); SLTInsert(&plist, pos, -2); PrintSLT(plist); SLTInsert(&plist, pos, -1); PrintSLT(plist); SLTInsertBack(&plist, pos, 3); PrintSLT(plist); SLTModify(plist, pos, 4); PrintSLT(plist); } int main() { test1(); } |
【本文地址】