引言：
单链表目前有的地方容易写出问题来，所以明天再来一遍，没什么问题之后我们就进军双链表
1. 注意点和易错点的各种详细注释
#include"S.h" //1.打印 void SListPrint(SLTNode* phead)//这个参数不敢不会写（传过来的是一个指针（结构体类型的），所以这边也就是写成一个结构体 类型的指针） { SLTNode* cur = phead; while (cur != NULL)//0.这里错了，这个不可以这样放，因为一开始进来的时候，我此时还没有cur->next这个指针嘞 { printf("%d->", cur->data); cur = cur->next; } } //2.新增结点 SLTNode* SListGreateNewnode(SLTDataType x)//1.这个的传参要明白，这个是不需要头指针的，重要有数字就行 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//2.注意这个不是realloc这里不需要两个参数 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; //这边开完新的结点这边一定要记得把这个结点给返回去 return newnode; } //3.尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SListGreateNewnode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; //尾插就是要找尾 while (tail->next) { tail = tail->next; } //跳到这里，按照当前逻辑就是找到了 //此时首先要开辟一个新的结点 tail->next = newnode; /* newnode->next = NULL;//此时的newnode中已经定义过了，所以不需要再定义 newnode->data = x;*/ } } //4.尾删 void SListPoptBack(SLTNode** pphead, SLTDataType x)//完全正确 { assert(pphead); if (*pphead == NULL) { return; } else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } } //4.尾删 void SListPoptBack(SLTNode** pphead, SLTDataType x)//完全正确 { //尾删另一种方法 assert(pphead); if (*pphead == NULL) { return; } else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next !=NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //5.头插 void SListPushFront(SLTNode** pphead, SLTDataType x)//正确 { assert(pphead); SLTNode* newnode = SListGreateNewnode(x); newnode->next = *pphead; //这个位置容易错（少一步），就是没把头还回去 *pphead = newnode; } //6.头删 //void SListPoptFront(SLTNode** pphead, SLTDataType x) //{ // assert(pphead); // // if (*pphead == NULL) // { // printf("node is empty\n"); // return NULL; // } // else if ((*pphead)->next == NULL) // { // free(*pphead); // *pphead = NULL; // } // else // { // SLTNode* next = NULL; // SLTNode* cur = *pphead; // next = cur->next; // free(*pphead); // *pphead = NULL; // SLTNode* newnode = SListGreateNewnode(x); // newnode = next; // //基本步骤完成之后，就是轮到注意点了 // } //} void SListPoptFront(SLTNode** pphead) { assert(pphead); if (*pphead == NULL) { printf("node is empty"); return; } else { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } } //7.查找接口 //SLTNode* SListFind(SLTNode** pphead, SLTNode* pos, SLTDataType x)//这步问题很大（没有完全理解） //{ // assert(pphead); // // if ((*pphead)->next == NULL) // { // return *pphead; // } // SLTNode* tail = *pphead; // while (tail->data != x) // { // tail = tail->next; // } // //程序来到这个位置说明我找到了 // return tail; //} SLTNode* SListFind(SLTNode* phead, SLTDataType x)//订正，这个函数问题很大（虽然写法很多，但是……） { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } else { cur = cur->next; } } } //8.任意位置插(pos位置) void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//基本对 { assert(pphead); assert(pos); //if (*pphead == NULL)//只有一个元素不能按照上面这样写，应该写成下面这个样子 //{ // //此时就是一个头插 //SLTNode* newnode = SListGreateNewnode(x); //newnode->next = *pphead; //错误的 //} SLTNode* newnode = SListGreateNewnode(x);//订正的 if (*pphead == pos) { newnode->next = *pphead; *pphead = newnode; } else { SLTNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; } /*SLTNode* newnode = SListGreateNewnode(x);*///这步上面有了这边就可以不要 posPrev->next = newnode; newnode->next = pos; //基本操作搞定之后就是注意点 } } //8.任意位置插(pos后一个位置)//多了很多不要的，还是没有得到精髓 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); //if (*pphead == pos) //{ // SLTNode* newnode = SListGreateNewnode(x); // (*pphead)->next = newnode; // newnode->next = NULL; //} //SLTNode* tail = *pphead; SLTNode* newnode = SListGreateNewnode(x); newnode->next = pos->next; pos->next = newnode; //基本条件写完就是注意点 } //9.任意位置删除（pos位置） void SListInsert(SLTNode** pphead, SLTNode* pos)//这几步一直有问题主要是因为没有理解这个pos的意思 { assert(pphead); assert(pos); //if ((*pphead)->next == NULL)//错误写法 //{ // free(*pphead); // *pphead = NULL; //} if (pos == *pphead)//我的订正 { SLTNode* next = pos->next; free(*pphead); *pphead = next; } else { SLTNode* tail = *pphead; SLTNode* next = pos->next;//虽然这步是写对了，但是主要就是还是没有理解pos while (tail->next != pos) { tail = tail->next; } tail->next = next; free(pos); pos = NULL; //写完基本的就是注意点 } } //10.任意位置删（pos的下一个位置） //void SListInsert(SLTNode** pphead,SLTNode* pos)//记住这种形式的删除都是可以不需要给头的，因为他已经给了我pos了，我只要在删pos的后面那个位置就行了 //{ // assert(pphead); // assert(pos); // SLTNode* tail = *pphead; // while (tail->next != pos) // { // tail = tail->next; // } // //程序来到这个位置就是说明我已经找到了 // free(pos->next); // pos->next = NULL; // //} void SListInsert(SLTNode* pos)//这个表示的就是一个结点 { assert(pos->next);//此处传过来的是pos的位置，所以我只需要判断这个结点中的指针就行 assert(pos); SLTNode* next = pos->next->next; free(pos->next); pos->next = NULL; pos->next = next; } //11.销毁 //void SListDestroy(SLTNode** pphead) //{ // SLTNode* cur = *pphead; // while (cur->next != NULL) // { // SLTNode* next = cur->next; // free(cur); // cur = NULL; // } //} void SListDestroy(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur != NULL) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
2.头文件中各个接口的声明
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //1.打印接口 void SListPrint(SLTNode* phead); //2.新增结点接口 SLTNode* SListGreateNewnode(SLTDataType x); //3.尾插接口 void SListPushBack(SLTNode** pphead, SLTDataType x); //4.尾删接口 void SListPoptBack(SLTNode** pphead, SLTDataType x); //5.头插接口 void SListPushFront(SLTNode** pphead, SLTDataType x); //6.头删接口 void SListPoptFront(SLTNode** pphead, SLTDataType x); //7.查找接口 SLTNode* SListFind(SLTNode** pphead, SLTNode* pos, SLTDataType x); //8.任意位置插入（pos位置） void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //9.任意位置插入（pos后一个位置） void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //9.任意位置删除（pos位置） void SListInsert(SLTNode** pphead, SLTNode* pos); //10.任意位置删除（pos后一个位置） void SListInsert(SLTNode** pphead, SLTNode* pos); //11.销毁接口 void SListDestroy(SLTNode** pphead);
3.调试和功能交给你们啦
主要是明天很神奇的需要练习跳舞，这个就不写了啦
