引言：
明天进军栈和队列，然后咱就开始刷题了
1.完整代码：
#include"标头.h" //1.初始化 //因为此时我有对这个传过来的指针进行改变（进行了初始化）所以此时的头结点是发生的改变的，所以这边一定要有返回值 DLNode* ListInit() { //因为我们是玩带哨兵位的，所以此时我们应该要先malloc出来一个结点（让这个结点成为我的哨兵位） //哨兵位头结点：（但是我函数外面的plist并拿不到这个哨兵位（也就是plist不会发生改变），所以需要有一个返回值来处理这个问题或者用二级指针也行） DLNode* phead = (DLNode*)malloc(sizeof(DLNode)); //因为此时的结构是一个双向的循环，所以(此时结构体中的两个指针应该要有不同的指向) //一个指针指向自己 phead->next = phead; //另一个指针也指向它自己 phead->prev = phead; return phead; }//以上就是对一个带头循环双向链表的初始化（这个就是C语言的魅力，什么都是靠自己来弄，你只是给了我一个概念的模型，剩下的东西都是要靠我自己来搞定这个结构应该是怎样的） //2.尾插 //因为此时我的头结点plist传过来之后我并没有对其进行改变（因为我在初始化那步就已经改变过了，此时的这个plist就是已经拥有了两个指针（已经把哨兵位给创建好了），所以此时我在尾插时，就不会对plist进行任何形式的改变，所以此时我就不需要有返回值，当然也不需要有二进指针（这个也就是哨兵位的好处）） void ListPushBack(DLNode* phead, DSListType x) { assert(phead); //DLNode* tail = phead->prev;//这步就是循环链表的大好处了（直接就可以找到最后一个结点的位置） //DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));//这个就是开辟新结点（尾插就一定要开辟一个新结点不然插什么） //newnode->data = x; 以上就是一个准备工作，下面就是真正的双向的循环的原理实现（最好是附上一幅图） //tail->next = newnode;//这步的意思是因为此时的tail就是尾结点（就是让我的尾结点的最后一个指针去指向我新开辟出来的结点，这样就实现了尾插） //newnode->prev = tail;//这个就是为了实现双向循环链表（因为双向循环链表有两个指针，此时的一个指针就要指向刚刚那个尾结点（tail），只有这样我的newnode才可以取而代之） //newnode->next = phead;//然后此时的另一个指针就去指向我的头指针（为了实现循环，尾—>头） //phead->prev = newnode;//然后这步就是把刚刚的头的其中一个指针指向我的newnoode（还是为了循环）（头->尾），这样就实现了循环双指针链表 //附用任意插 ListInsert(phead, x); } //3.打印 // void ListPrint(DLNode* phead) { //因为此时phead中存的并不是一个有效的数据，所以此时不需要从头结点开始遍历（下一个结点开始） //判断结束条件就是通过：此时的这些数据在循环的过程之中最后会等于我的头结点（哨兵位），因为是循环的，所以不要以为它是一个循环就不能打印（只是停止的条件发生了一些的改变而已） assert(phead); DLNode* cur = phead->next; while (cur != phead) { printf("<-%d->", cur->data); cur = cur->next; } } //4.尾删（经典野指针错误） //void ListPoptBack(DLNode* phead) //{ // DLNode* tail = phead->prev; // free(phead->prev); // tail->prev->next = phead;//这步就是那个道理，自己理解一下就行（先找前面那个，然后链接头结点） // phead->prev = tail->prev; // //} //4.尾删（我的正确写法） void ListPoptBack(DLNode* phead) { assert(phead); assert(phead->next != phead);//这边就是说明我不可以把哨兵位给删掉（就是当phead->next=phead;时，此时就是代表我这个循环双链表就只剩下哨兵位自己了（因为这是一个循环的链表），此时就不能再进行删除了） 首先肯定是不需要开辟新结点的 //DLNode* tail = phead->prev; while (cur->next != tail)//找尾的上一个 { cur = cur->next; } 不敢把这个单链表的理解带过来我们的双链表（因为此时的整体的结构就是不一样的，因为此时的双链表是有两个指针的，一个是next指针，一个是prev指针，所以此时的尾的前一个只需要用prev这个指针去找就可以了） //DLNode* prev = tail->prev; //free(tail); //prev->next = NULL; 此时以上只是大致的把尾给删除了，但是我还没有重新将这个循环链表给链接起来 //prev->next = phead; //phead->prev = prev; //附用任意删 ListDete(phead->prev); } //5.头插 void ListPushFront(DLNode* phead, DSListType x) { assert(phead); //DLNode* newnode = (DLNode*)malloc(sizeof(DLNode)); //newnode->data = x; //DLNode* tail = phead->next; //newnode->next = tail; //tail->prev = newnode; //newnode->prev = phead; //phead->next = newnode; //附用任意插 ListInsert(phead->next, x);//这个位置一定要记住是phead->next,不然就会出问题，因为哨兵位的后一个才是头结点，所以在这个头结点前面插入才是我的头插 } //6.头删 void ListPoptFront(DLNode* phead) { //这边只要是与删除有关的代码，就要多断言一下，防止把哨兵位给删掉 //assert(phead); //assert(phead->next != phead);//表示链表为空就不再需要断言了 // //DLNode* tail = phead->next; //DLNode* next = tail->next; //free(tail);//这个free什么时候free就看你自己的方式了，可以最后free也可以后面free //next->prev = phead; //phead->next = next; //附用任意删 ListDete(phead->next); } //7.查找 DLNode* ListFindname(DLNode* phead, DSListType x)//这个是为了找x，不敢当傻子了 { assert(phead); //这个的逻辑就有点像是print的逻辑，就是靠那个循环条件来完成 DLNode* cur = phead->next; while (cur != phead)//这个循环是在保证我这个链表中不止只有哨兵位，而是有数据结点才开始找 { if (cur->data == x) { return cur; } //这个位置就表示找到了 cur = cur->next; } return NULL; } //8.任意位置插入(pos位置) void ListInsert(DLNode* pos, DSListType x)//这个位置不一定要用pos，用一个int pos的下标也是一样的,但一定注意这个pos是一个DLNode结构体，里面是有两个指针和一个数据的 { assert(pos); DLNode* newnode = (DLNode*)malloc(sizeof(DLNode)); newnode->data = x; DLNode* prev = pos->prev; newnode->prev = prev; prev->next = newnode; newnode->next = pos; pos->prev = newnode; } //9.任意位置删除(pos位置) void ListDete( DLNode* pos) { assert(pos); /*assert(phead->next != phead);*/ DLNode* next = pos->next; DLNode* prev = pos->prev; free(pos); next->prev = prev; prev->next = next; } //10.销毁 void ListDestory(DLNode* phead) { DLNode* cur = phead->next; DLNode* next = NULL; //while (cur->next != phead)//这步一开始你是这样写的，但是如果你写成这样的话，就会导致最后一个结点free不了，所以应该写成下面这样 while (cur != phead) { //可以的怎么野指针怎么来（这就是我吗？） next = cur->next; free(cur); cur = NULL; cur = next; } //并且在你把所有的结点释放完之后（不能把哨兵位这个动态开辟的内存空间给忘记掉释放了），所以这边还要加一步 free(phead);//但是这边要注意一个二级指针的问题（因为这步现在再改变我的函数外部的plist哨兵位） phead = NULL; }
头文件
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int DSListType; typedef struct DSListNode { DSListType data; struct DSListNode* next; struct DSListNode* prev; }DLNode; //以上就是一个高级结构体的创建(但是只是一个双向的概念)，并不能体现出循环的概念 //1.初始化 DLNode* ListInit(); //2.打印 void ListPrint(DLNode* phead); //3.尾插 void ListPushBack(DLNode* phead, DSListType x); //4.尾删 void ListPoptBack(DLNode* phead); //5.头插 void ListPushFront(DLNode* phead, DSListType x); //6.头删 void ListPoptFront(DLNode* phead); //7.查找 DLNode* ListFindname(DLNode* phead, DSListType x); //8.销毁 void ListDestory(DLNode* phead); //9.任意位置插入 void ListInsert(DLNode* pos, DSListType x); //10.任意位置删除 void ListDete(DLNode* pos); //11.上面的这两个函数是整个双向循环链表中最重要的
