复习链表
使用部分C++的语法，写的单链表，发现了一些以前没有真正明白的知识，总的来说各种数据结构难的不是增删查改，难的是数据的存储问题有没有搞懂，怎么存？存在哪？
如果有链表某些方面没搞懂的问题，相信我注释肯定可以帮到你，因为你的坑，我肯定踩过！
人送外号踩坑小王子
//不管是昨天的顺序表，还是今天的链表，我发现一开始难住我的都不是增删查改，而是空间开辟问题，搞懂了空间问题，别的都是水到渠成 #include<iostream> #include<stdlib.h> #include<assert.h> using namespace std; typedef int SLLDataType; typedef struct SLinkedListNode { struct SLinkedListNode* next; SLLDataType data; }SLLNode; SLLNode* GreatSLLNode(SLLDataType x)//此时的这个传参有顾虑（意思：就是开辟了结点之后，给一个数据就行） { SLLNode* newnode = new SLLNode; if (newnode == nullptr) { cout << "new fail" << endl;//此时可以使用perror exit(-1);//这个退出别忘了 } else { newnode->data = x; newnode->next = nullptr; } return newnode;//返回的是new出来的空间的地址（所以返回结构体的地址就要用结构体指针），记住地址和指针是永远挂钩的就行 } SLLNode* GreatSLL1()//下述的代码就是一个链表的最本质的写法（经典，但是有点笨） { SLLNode* n1 = GreatSLLNode(1); SLLNode* n2 = GreatSLLNode(2); SLLNode* n3 = GreatSLLNode(3); SLLNode* n4 = GreatSLLNode(4); n1->next = n2; n2->next = n3; n3->next = n4; n4->next = nullptr; return n1;//搞定链表结构，只要拿到了头结点，就等于拿到了整个链表（因为本质都是通过一个一个指针相连的） } SLLNode* GreatSLL2(size_t n)//此时这个接口就是一个更聪明的写法，连续开辟结点和循环链接 { SLLNode* phead = nullptr; SLLNode* ptail = nullptr;//此时多定义一个ptail的目的就是为了：让phead不同，一直当老大（不会找不到头），这也就是链表结构的特殊性 for (int i = 0; i < n; ++i) { SLLNode* newnode = GreatSLLNode(i);//反正不管怎样，想要存数据就要存在堆区上，就要调用malloc（new） if (phead == nullptr) { phead = ptail = newnode;//替死鬼登场 } else { ptail->next = newnode;//此时newnode->next=nullptr在结点创建的过程就搞定了，这里不需要麻烦 ptail = newnode; } } return phead;//返回头结点就等于返回了整个链表 } void SLListPrint(SLLNode*& plist)//这个位置本质因为不需要修改，所以传什么都是一样的 { //SLLNode* cur = plist; //while (cur != nullptr) //{ // cout << cur->data << "->"; // cur = cur->next; //}//上述这个是while写法（有while写法就要for写法） for (SLLNode* cur = plist; cur; cur = cur->next) { cout << cur->data << "->"; } cout << "nullptr" << endl; } void SLListPushBack(SLLNode*& plist, SLLDataType x) { SLLNode* newnode = GreatSLLNode(x);//插入数据第一步：把结点构建出来 SLLNode* tail = plist; if (plist == nullptr) { //plist->next = newnode;//这步写了一点小问题出来（空指针解引用，人才了） plist = newnode;//空指针就直接赋值就好 } else { while (tail->next != nullptr) { tail = tail->next; } tail->next = newnode; tail = newnode; }//有while循环的写法就一定有for循环的写法 //for (tail; tail->next; tail = tail->next)//if else省略 //tail->next = newnode; //tail = newnode; } void SLListPushFront(SLLNode*& plist, SLLDataType x) { SLLNode* newnode = GreatSLLNode(x); newnode->next = plist; plist = newnode; } void SLListPoptBack(SLLNode*& plist) { //for (SLLNode* tail = plist; tail->next; tail = tail->next) //delete tail;//链表的一个大坑（刚好踩到）原因：就是导致野指针问题（最后一个结点的next） SLLNode* tail = plist; SLLNode* prev = nullptr; if (plist == nullptr) { return; } else if (plist->next == nullptr) { delete plist; plist = nullptr; } else {//1. for (tail; tail->next->next; tail = tail->next); delete tail->next; tail->next = nullptr; //2. //for (tail; tail->next; tail = tail->next) //{ // prev = tail; //} //delete tail; //prev->next = nullptr; } } void SLListPoptFront(SLLNode*& plist) { assert(plist != nullptr); //delete plist; //plist = nullptr;//恭喜你，链表的第二个大坑你又踩到了 SLLNode* next = plist->next; delete plist; plist = next; } SLLNode* SLListFind(SLLNode*& plist,SLLDataType x) { for (SLLNode* cur = plist; cur->next; cur = cur->next) { if (x == cur->data) { return cur; } } } void SLListDestory(SLLNode*& plist) { for (plist; plist; plist = plist->next) { SLLNode* next = plist->next; delete plist; plist = next; } } void SLListInsert(SLLNode*& plist, SLLNode* pos, SLLDataType x)//此时pos代表的不仅仅是一个位置（本质上代表的是一个结构体的位置），和指针也有很大的关系 { //此时千万不敢和数组下标搞混（链表的第三个大坑）（链表中没有下标的概念，那个是data不是下标） SLLNode* newnode = GreatSLLNode(x); SLLNode* cur = plist; if (pos == plist) { newnode->next = plist; plist = newnode; } else { for (cur; cur->next != pos; cur = cur->next); cur->next = newnode; newnode->next = pos; } } void SLListErase(SLLNode*& plist, SLLNode* pos) { if (plist == pos) { SLLNode* next = plist->next; delete pos; plist = next; } else { SLLNode* cur = plist; for (cur; cur->next != pos; cur = cur->next); cur->next = pos->next; delete pos; } } void TestSLList1(SLLNode*& plist)//这个位置因为会涉及到增删查改，所以必须要给二级指针或者传引用 { SLListPushBack(plist, 1); SLListPushBack(plist, 2); SLListPushBack(plist, 3); SLListPushBack(plist, 4); SLListPushBack(plist, 5); SLListPushFront(plist, 1); SLListPushFront(plist, 2); SLListPushFront(plist, 3); SLListPushFront(plist, 4); SLListPushFront(plist, 5); SLListPoptBack(plist); SLListPoptBack(plist); SLListPoptBack(plist); SLListPoptBack(plist); SLListPoptBack(plist); SLListPoptFront(plist); SLListPoptFront(plist); SLListPoptFront(plist); SLListPoptFront(plist); SLListPoptFront(plist); SLListPrint(plist); SLListDestory(plist); } void TestSLList2(SLLNode*& plist) { SLLNode* pos = SLListFind(plist, 5); cout << pos->data << endl;//这个位置傻傻的不会打印（接收一下就可以打印都想不到吗？） } void TestSLList3(SLLNode*& plist) { SLLNode* pos = SLListFind(plist, 5); SLListInsert(plist, pos, 50); SLListPrint(plist); SLListErase(plist, pos); SLListPrint(plist); } int main() { //SLLNode plist;//首先第一个点就把我自己搞懵了（这里是使用SSL指针类型，还是SSL结构体变量类型,可以看出当时确实是没怎么学明白） //百度之后，没有找到答案，可以看出这个问题确实是比较容易被忽视，但是航哥给了我答案： //（与栈帧有关）就是如果我使用单链表结构体定义一个结构体变量，那么此时这个变量的空间就是在栈上申请的（如果使用的是一个指针变量，那么此时这个指针变量就可以指向堆上的空间，这个就是本质原因） //本质的改变就是在结点中的数据不会因为栈帧的销毁而销毁 //并且我们的顺序表虽然没有使用指针，但是它的空间都是通过扩容扩出来的（realloc），本质上还是在堆上，所以我们也要把单链表中的数据存到堆区上 //但是由于链表的特殊结构，此时我们无法直接在堆区上扩容，所以就要使用结构体指针 //所以本质上我们的头结点应该是如下这样写的 //SLLNode* plist = (SLLNode*)malloc(sizeof(SLLNode));//但是这样写比较麻烦，所以一般我们都是直接写成一个函数，每次要用就去调用那个函数就行 //并且上述是一个C语言的写法，下面的是一个C++的写法 //SLLNode* plist = new SLLNode;//会自动调用构造函数，所以不怕 SLLNode* plist1 = GreatSLLNode(1); SLLNode* plist2 = GreatSLL1(); SLLNode* plist3 = GreatSLL2(10);//这个参数此时代表的是个数 SLListPrint(plist1);//开结点 SLListPrint(plist2);//傻傻开 SLListPrint(plist3);//循环开 //搞懂了上述，我敢包票你就搞懂了链表 //因为还是如最上面的那句话，最难的只是开空间问题而已 //所以此时我们开始增删查改（外包函数） //TestSLList1(plist3); //TestSLList2(plist3); TestSLList3(plist3); return 0; }
