网站注册信息,怎样制作自己的小程序,wordpress mysql端口,做外汇消息面的网站个人主页#xff1a;平行线也会相交 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 平行线也会相交 原创 收录于专栏【数据结构初阶#xff08;C实现#xff09;】 文章目录链表初始化打印链表尾插尾删新建一个节点头插头删查找在pos之前插入*删除pos位… 个人主页平行线也会相交 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 平行线也会相交 原创 收录于专栏【数据结构初阶C实现】 文章目录链表初始化打印链表尾插尾删新建一个节点头插头删查找在pos之前插入*删除pos位置销毁链表总代码test.cList.hList.c链表初始化
LTNode* ListInit(LTNode* phead)
{//哨兵位头节点phead (LTNode*)malloc(sizeof(LTNode));phead-next phead;phead-prev phead;return phead;//利用返回值的方式
}首先我们需要一个哨兵头节点该头节点的next和prev均指向该头节点本身最后返回这个头节点的地址。
打印链表
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;//从phead-开始遍历链表while (cur ! phead)//为了防止死循环所以终止条件为curphead{printf(%d , cur-data);cur cur-next;}printf(\n);
}由于链表是双向循环链表双向循环链表自身的结构很容易在打印时造成死循环所以我们在打印链表时需要注意循环终止的条件否则程序就会陷入死循环。再次提醒这是一个双向循环链表。当我们循环打印完链表的最后一个数据的时候此时cur就是指向链表中最后一个节点的而cur-next是指向链表的哨兵头节点的所以循环终止条件就是curphead。
尾插
void ListPushBack(LTNode* phead, LTDateType x)
{//链表为空时依然可以处理assert(phead);LTNode* tail phead-prev;//找到尾节点LTNode* newnode (LTNode*)malloc(sizeof(LTNode));newnode-data x;//pheadtail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}尾删
//尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//当链表为空时就表示不能再删除了//找到尾LTNode* tail phead-prev;phead-prev tail-prev;tail-prev-next phead;//最后释放空间free(tail);
}既然是尾删我们首先要先找到尾即LTNode* tail phead-prev;这样会方便很多同时尾删的时候一定要注意**free**的释放时机。 注意一种特殊情况当phead-nextphead的时候此时链表为空就不能继续删除了。所以需要加上 assert(phead-next ! phead);。
新建一个节点
LTNode* BuyListNode(LTDateType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}该函数功能就是新建一个节点把该节点的数据进行赋值即newnode-data x;并把指针均变成空指针newnode-prev NULL; newnode-next NULL;。最后返回这个新节点的地址即可。
头插
void ListPushFront(LTNode* phead, LTDateType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* next phead-next;phead-next newnode;newnode-prev phead;newnode-next next;next-prev newnode;
}还是看一下特殊情况即如果链表是一个空链表我们来简单分析一下链表为空时phead-next就是phead本身。 我们只需要处理phead、next、newnode三者之间的链接关系即可。最后发现链表为空时依然可以进行处理。
头删
void ListPopFront(LTNode* phead)
{assert(phead);//链表为空就不需要头删了LTNode* next phead-next;LTNode* nextNext next-next;phead-next nextNext;nextNext-prev phead;free(next);
}链表为空时就不要进行头删操作了故加上assert(phead);我们最好还是提前定义好next和nextNext即LTNode* next phead-next; LTNode* nextNext next-next; 这样后面会很方便可以减少不必要的麻烦接下来处理phead、next、nextNext三者之间的链接关系就好了。
查找
查找的实现与打印的实现差不太多提前定义一个cur指向phead的next即LTNode* next phead-next;循环终止条件依然是cur phead其它按部就班即可。
LTNode* ListFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}//没找到就返回NULLreturn NULL;
}在pos之前插入*
void ListInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyListNode(x);//处理posPrev newnode pos三者之间的链接关系posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}一定要提前定义一个posPrev即LTNode* posPrev pos-prev;然后进行newnode、pos、posPrev之间的链接就好。 在这里我们还可以利用ListInsert这个函数来完成头插尾插的操作。 首先我们先利用ListInsert来完成尾插的操作。 当pos是我们的哨兵位节点phead的时候由于这个函数是在pos之前插入所以此时就相当于尾插了因为phead-prev就是尾。
void ListPushBack(LTNode* phead, LTDateType x)
{//链表为空时依然可以处理assert(phead);//LTNode* tail phead-prev;//找到尾节点//LTNode* newnode (LTNode*)malloc(sizeof(LTNode));//newnode-data x;phead//tail-next newnode;//newnode-prev tail;//newnode-next phead;//phead-prev newnode;ListInsert(phead, x);
}现在再来看头插 当phead-next和pos相等时此时就相当于头插。
void ListPushFront(LTNode* phead, LTDateType x)
{assert(phead);//LTNode* newnode BuyListNode(x);//LTNode* next phead-next;//phead-next newnode;//newnode-prev phead;//newnode-next next;//next-prev newnode;ListInsert(phead-next, x);
}所以我们以后想要快速的写双向循环链表的时候头插、尾插、或者任意位置的插入都可以利用ListInsert这个函数来快速的实现双向循环链表。把phead-prev传给pos就是尾插把phead-next传给pos就变成了头删。所以双向链表只需要实现两个函数ListInsert和ListErase就都搞定了这也是双向链表结构的一个优势。
删除pos位置
void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;posPrev-next posNext;posNext-prev posPrev;free(pos);
}一般来说我们想要删除某个数据先是调用ListFind来返回一个地址然后才调用ListErase继而把该数据删除请看
void TestList2()
{LTNode* plist NULL;plist ListInit(plist);ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);LTNode* pos ListFind(plist, 2);if (pos ! NULL){ListErase(pos);}ListPrint(plist);
}我们可以看到运行结果成功把第一个2删除了。 然而ListErase的功能不仅仅只有这些我们还可以利用ListErase来完成头删尾删的操作。
请看
//尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//当链表为空时就表示不能再删除了找到尾//LTNode* tail phead-prev;//phead-prev tail-prev;//tail-prev-next phead;最后释放空间//free(tail);ListErase(phead-prev);
}//头删
void ListPopFront(LTNode* phead)
{assert(phead);链表为空就不需要头删了//LTNode* next phead-next;//LTNode* nextNext next-next;//phead-next nextNext;//nextNext-prev phead;//free(next);ListErase(phead-next);
}现在我们来测试一下
void TestList2()
{LTNode* plist NULL;plist ListInit(plist);ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);LTNode* pos ListFind(plist, 2);if (pos ! NULL){ListErase(pos);}ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);
}销毁链表
最后我们再来实现一下销毁链表。
//销毁链表
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);//想要把phead置为空需要再函数外部进行置空当然如果传二级指针也可以在函数内部把//phead置为空不过因为我们这个双向链表都是传的一级指针所以为了保持接口一致性//我们在函数外部把phead置为空即可
}以上就是双向循环链表所以接口函数的实现。
总代码
test.c
#includeList.hvoid TestList1()
{LTNode* plist NULL;//初始化plist ListInit(plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);
}void TestList2()
{LTNode* plist NULL;plist ListInit(plist);ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);LTNode* pos ListFind(plist, 2);if (pos ! NULL){ListErase(pos);}ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);ListDestroy(plist);plist NULL;
}int main()
{//TestList1();TestList2();return 0;
}List.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDateType;typedef struct ListNode
{LTDateType data;struct ListNode* next;struct ListNode* prev;
}LTNode;LTNode* ListInit(LTNode* phead);//初始化
void ListPrint(LTNode* phead); //打印链表//尾插
void ListPushBack(LTNode* phead, LTDateType x);//尾删
void ListPopBack(LTNode* phead);//头插
void ListPushFront(LTNode* phead, LTDateType x);//头删
void ListPopFront(LTNode* phead);//创建新节点
LTNode* BuyListNode(LTDateType x);//查找
LTNode* ListFind(LTNode* phead, LTDateType x);//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);//删除pos位置
void ListErase(LTNode* pos);//销毁聊表
void ListDestroy(LTNode* phead);List.c
#includeList.h//初始化
LTNode* ListInit(LTNode* phead)
{//哨兵位头节点phead (LTNode*)malloc(sizeof(LTNode));phead-next phead;phead-prev phead;return phead;//利用返回值的方式
}void ListPushBack(LTNode* phead, LTDateType x)
{//链表为空时依然可以处理assert(phead);//LTNode* tail phead-prev;//找到尾节点//LTNode* newnode (LTNode*)malloc(sizeof(LTNode));//newnode-data x;phead//tail-next newnode;//newnode-prev tail;//newnode-next phead;//phead-prev newnode;ListInsert(phead, x);
}void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;//从phead-开始遍历链表while (cur ! phead)//为了防止死循环所以终止条件为curphead{printf(%d , cur-data);cur cur-next;}printf(\n);
}//尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//当链表为空时就表示不能再删除了找到尾//LTNode* tail phead-prev;//phead-prev tail-prev;//tail-prev-next phead;最后释放空间//free(tail);ListErase(phead-prev);
}LTNode* BuyListNode(LTDateType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}void ListPushFront(LTNode* phead, LTDateType x)
{assert(phead);//LTNode* newnode BuyListNode(x);//LTNode* next phead-next;//phead-next newnode;//newnode-prev phead;//newnode-next next;//next-prev newnode;ListInsert(phead-next, x);
}//头删
void ListPopFront(LTNode* phead)
{assert(phead);链表为空就不需要头删了//LTNode* next phead-next;//LTNode* nextNext next-next;//phead-next nextNext;//nextNext-prev phead;//free(next);ListErase(phead-next);
}//查找
LTNode* ListFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}//没找到就返回NULLreturn NULL;
}//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyListNode(x);//处理posPrev newnode pos三者之间的链接关系posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}//删除pos位置
void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;posPrev-next posNext;posNext-prev posPrev;free(pos);
}//销毁链表
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);//想要把phead置为空需要再函数外部进行置空当然如果传二级指针也可以在函数内部把//phead置为空不过因为我们这个双向链表都是传的一级指针所以为了保持接口一致性//我们在函数外部把phead置为空即可
}好了双向循环链表的实现就到这里了其实在这里面最重要的两个接口函数就是ListErase和ListInser这两个函数可以帮助我们快速的实现这个链表剩余的就是一些边边角角的问题了。 这块的内容还是要多画图来帮助我们更好的理解。
