C语言入土之路|[数据结构]我滴双链表完成辣,Ура


这个是一个标题哦

  • 双链表
  • 那么,开始准备吧
    • 双链表的本体
    • 初始化
    • 得到一个节点
    • 打印链表
    • 销毁链表
  • 经典的增删查改
    • 插入操作
      • 头插
      • 尾插
      • 指定位置前插入
      • 遇到困难偷大懒
    • 删除操作
    • 简单偷个懒吧!
    • 查询和修改
  • 最后

C语言入土之路|[数据结构]我滴双链表完成辣,Ура
文章图片

在淦了四篇刷题笔记之后,菜鸡大学生想起她之前在单链表挖的坑还没填。遂,填。有一说一菜鸡大学生的坑品还是可以的。下一篇是动图教程哦,所以…(暗示) 开搞!
双链表 C语言入土之路|[数据结构]我滴双链表完成辣,Ура
文章图片

(今天的攻略对象)
和上次的单链表相比,今天要写的双链表有以下不同:
  1. 带哨兵位的头结点。
  2. 双向的,每个节点不仅可以指向下一个,还可以指向上一个
  3. 循环链表,最后一个节点指向第一个节点。
那么,开始准备吧 双链表的本体 【C语言入土之路|[数据结构]我滴双链表完成辣,Ура】加上一个前驱的指针,欸嘿嘿。C语言入土之路|[数据结构]我滴双链表完成辣,Ура
文章图片

typedef int ListDataType; typedef struct ListNode { struct ListNode* prev; //* struct ListNode* next; ListDataType data; }ListNode;

初始化 在初始化的时候我们就要带上我们的哨兵位了。
我们先生成一个节点,里面的数据置为0 (数据多少都无所谓,反正都不会用上) 然后将节点的前指针和后指针统统指向自己。
这样,一个循环链表的雏形就出来了。
//初始化 ListNode* ListInit() { ListNode* phead= BuyListNode(0); phead->next = phead; phead->prev= phead; return phead; }

得到一个节点 没啥,就多了一个前指针。
随便写写就好。
//得到一个节点 ListNode* BuyListNode(ListDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = https://www.it610.com/article/x; newnode->next = NULL; newnode->prev = NULL; return newnode; }

打印链表 同上,注意结束条件变成了cur!=phead,因为是循环链表嘛。
//打印 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur!=phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }

销毁链表 整一个cur指针,从头的下一个节点开始删,直到下一个节点是头,然后把头和cur一起删掉。
我决定画个图玩玩。
C语言入土之路|[数据结构]我滴双链表完成辣,Ура
文章图片

//销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; ListNode* next = phead->next; while (next!=phead) { free(cur); cur = next; next = next->next; } free(cur); free(phead); }

经典的增删查改 插入操作 头插
双链表由于结构的优越性,增删查改变得嘎嘎简单,只要我们能找到要插入的节点两侧的节点,然后就是无脑操作。
所以我们就大致画画图,放个代码就好了。
  1. 首先创建新节点C语言入土之路|[数据结构]我滴双链表完成辣,Ура
    文章图片
  2. 接着我们将phead和first与新节点链接。C语言入土之路|[数据结构]我滴双链表完成辣,Ура
    文章图片
  3. 然后就结束了。C语言入土之路|[数据结构]我滴双链表完成辣,Ура
    文章图片
好耶!C语言入土之路|[数据结构]我滴双链表完成辣,Ура
文章图片

//头插 void ListPushFront(ListNode* phead, ListDataType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* first = phead->next; phead->next = newnode; newnode->next = first; newnode->prev = phead; first->prev = newnode; }

尾插
同理。
我连图都懒得画。
//尾插 void ListPushBack(ListNode* phead, ListDataType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* tail = phead->prev; phead->prev = newnode; newnode->next = phead; newnode->prev = tail; tail->next = newnode; }

指定位置前插入
…(暗示)
//某个位置前插入数据 void ListInsert(ListNode* pos, ListDataType x) { ListNode* newnode = BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

遇到困难偷大懒
有了指定位置插入我们可以偷头插和尾插的懒了。
  • 尾插就是在phead的前面插入数据。
  • 头插就是在phead的下一位前面插入数据。
所以:
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); }void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); }

删除操作 似乎更加简单了?但是要检查链表是不是为空即phead->next!=phead.
//头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next!=phead); ListNode* first = phead->next; phead->next = first->next; first->next->prev = phead; free(first); }//尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); }//删除某个位置数据 void ListErase(ListNode* phead, ListNode* pos) { assert(phead); assert(phead->next != phead); //稍微考虑一下phead吧,不考虑也行 ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }

简单偷个懒吧! 这里使用的是不带phead玩的版本。
//尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->prev); }//头删 void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->next); }

查询和修改 很简单哦,只要遍历就可以了。
//查某个值,返回地址 ListNode* ListFind(ListNode* phead, ListDataType x) { ListNode* cur = phead->next; while (cur != phead) { if (cur->data =https://www.it610.com/article/= x) { return cur; } cur = cur->next; } return NULL; }//改某个值 void ListChange(ListNode* phead, ListDataType sourse, ListDataType destination) { assert(phead); ListNode* pos= ListFind(phead, sourse); pos->data = https://www.it610.com/article/destination; }

最后 感觉这一篇好水哦(笑)
看在下一篇是动图教程的份上,捧个小场不过分吧。

    推荐阅读