一、有头双向循环链表
(一、)我们先讲一些学习的小知识点和注意点
我们不管它昨天几点睡和今天有没有学习,把握好当下,我们今天要进行双向链表的学习
1.什么是双向链表(最主要讲的就是每个节点不仅是上一个结点存了下一个结点的地址(此时后一个结点也存了上一个结点的地址),这个就是双向链表)
2.所以现在我们还是一样不管那么多,我们先进行一个结构体的创建(但是此时的这个结构体不同于单链表的结构体,此时的结构体是多了一个指针的结构体)
3.单链表的题目考察较多,双链表没什么题目
4.二叉树也是两个指针
5.带头和不带头(就看与没有哨兵位),就是看头指针是否存放数据(头指针单独是一个指针就是哨兵位)
6.循环和非循环(如果是双向链表它的头结点和尾结点都是指向空指针的,但是如果是循环链表则不是)
7.循环链表的最后一个结点指向的位置是头结点
8.所以链表为什么会有8中结构(单、双)(带头、不带头)(循环、非循环)这些的排列组合刚好8种
9.但是在这8种中比较有价值(最常用的)的就是(最简单的和最复杂的):无头单向非循环链表、带头双向循环链表
10.所以我们就开始带头双向循环链表的学习(比无头单向非循环链表更简单哦)
(二、)有关的图解(便于理解)
(三、)有头双向循环链表的实现
可以分为一下这些接口:
1.初始化
2.打印
3.尾插
4.尾删
5.头插
6.头删
7.查找
8.销毁
9.任意位置插入
10.任意位置删除
//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.上面的这两个函数是整个双向循环链表中最重要的
1.初始化接口
//1.初始化 //因为此时我有对这个传过来的指针进行改变(进行了初始化)所以此时的头结点是发生的改变的,所以这边一定要有返回值 DLNode* ListInit() { //因为我们是玩带哨兵位的,所以此时我们应该要先malloc出来一个结点(让这个结点成为我的哨兵位) //哨兵位头结点:(但是我函数外面的plist并拿不到这个哨兵位(也就是plist不会发生改变),所以需要有一个返回值来处理这个问题或者用二级指针也行) DLNode* phead = (DLNode*)malloc(sizeof(DLNode)); //因为此时的结构是一个双向的循环,所以(此时结构体中的两个指针应该要有不同的指向) //一个指针指向自己 phead->next = phead; //另一个指针也指向它自己 phead->prev = phead; return phead; }//以上就是对一个带头循环双向链表的初始化(这个就是C语言的魅力,什么都是靠自己来弄,你只是给了我一个概念的模型,剩下的东西都是要靠我自己来搞定这个结构应该是怎样的)
2.打印接口
//3.打印 // void ListPrint(DLNode* phead) { //因为此时phead中存的并不是一个有效的数据,所以此时不需要从头结点开始遍历(下一个结点开始) //判断结束条件就是通过:此时的这些数据在循环的过程之中最后会等于我的头结点(哨兵位),因为是循环的,所以不要以为它是一个循环就不能打印(只是停止的条件发生了一些的改变而已) assert(phead); DLNode* cur = phead->next; while (cur != phead) { printf("<-%d->", cur->data); cur = cur->next; } }
3.尾插接口
//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); }
4.尾删接口
//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.头插接口
//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,不然就会出问题,因为哨兵位的后一个才是头结点,所以在这个头结点前面插入才是我的头插 }
7.查找接口
//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.销毁接口
//8.销毁 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; }
9.任意位置插入接口
//9.任意位置插入(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; }
10.任意位置删除接口
//10.任意位置删除(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; }
附上图解:
(四、)测试代码
void Test1()
中的测试内容:
void Test2()
中的测试内容:
void Test3()
完整的测试代码:
#include"标头.h" void Test1() { //DLNode* plist = NULL;//(此时我的头结点是一个带哨兵位的,) //先初始化 /*ListInit(&plist);*///我们在使用哨兵位的就不用这种传地址的方式 DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式 //再尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); printf("\n"); //再尾删 ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPrint(plist); printf("\n"); //再头插 ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //再头删 ListPoptFront(plist); ListPoptFront(plist); ListPoptFront(plist); //打印 printf("NULL"); ListPrint(plist); printf("NULL\n"); ListDestory(plist); } void Test2() { DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式 //先尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); printf("\n"); //再头插 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //查找 DLNode* pos = ListFindname(plist, 1); printf("\n"); //打印 printf("NULL"); ListPrint(plist); printf("NULL\n"); ListDestory(plist); } void Test3() { DLNode* plist = ListInit(); //先尾插 ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); //再头插 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPushFront(plist, 5); ListPrint(plist); printf("\n"); //再尾删 ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPoptBack(plist); ListPrint(plist); printf("\n"); //再头删 ListPoptFront(plist); ListPoptFront(plist); ListPoptFront(plist); ListPrint(plist); printf("\n"); ListDestory(plist); //可以不使用二级指针,直接自己在外面置空指针(为了保持接口的一致性,所以不使用二级指针) plist = NULL; } int main() { //Test1(); //Test2(); Test3(); return 0; }