[已解决]链表问题求解思路

Icetone

自己的理解的有两个方法，希望大家可以一起进步
新手又犯了低级错误，第二个方法一直报错误，检查了半天，结果就是if()判断那里，把 == 写成了 = ，一直是内存错误，好心塞

1. #pragma once
   
2. 
   
3. #include <stdio.h>
   
4. #include <iostream>
   
5. #define        MAXSIZE        20
   
6. #define        WRONG        -1
   
7. #define        OK                0
   
8. typedef int ElemType;
   
9. typedef int Status;//返回结果
   
10. 
    
11. using namespace std;
    
12. 
    
13. //链式存储线性表，单链表
    
14. typedef class LinkNode* MyLinkList;
    
15. 
    
16. class LinkNode
    
17. {
    
18. public:
    
19.         ElemType data;
    
20.         LinkNode *next;
    
21. public:
    
22.         LinkNode() :data(0), next(nullptr) {}
    
23.         Status ListCreateTail(MyLinkList *list, int length)
    
24.         {
    
25.                 MyLinkList node, tail;//创建一个临时结点和一个尾结点；
    
26. 
    
27.                 //(*list) = (MyLinkList)malloc(sizeof(LinkNode));//给头结点开辟空间；
    
28.                 *list = new LinkNode();//同上，给头结点开辟空间；
    
29.                 (*list)->data = length;//头结点数据为链表总结点数，不包括头结点;
    
30.                 tail = *list;//空链表的头结点即尾结点；
    
31.                 for (int i = 0; i < length; i++)
    
32.                 {
    
33.                         //cout << "第" << i << "个元素" << endl;
    
34.                         /*node = (MyLinkList)malloc((sizeof(LinkNode)));
    
35.                         node->data = i;
    
36.                         node->next = nullptr;*/
    
37.                         node = new LinkNode(i);
    
38.                         if (node == nullptr)        return        WRONG;
    
39. 
    
40.                         tail->next = node;
    
41.                         tail = node;
    
42.                 }
    
43.                 tail->next = nullptr;
    
44.                 return OK;
    
45.         }
    
46.         /*显示链表*/
    
47.         Status ListShow(MyLinkList *list)
    
48.         {
    
49.                 MyLinkList tempNode = *list;
    
50.                 if (!tempNode || tempNode->next == nullptr)
    
51.                 {
    
52.                         cout << "无该链表或者链表为空" << endl;
    
53.                         return WRONG;
    
54.                 }
    
55. 
    
56.                 cout << "链表中数据为：";
    
57.                 while (tempNode->next != nullptr)
    
58.                 {
    
59.                         cout << tempNode->data << " ";
    
60.                         tempNode = tempNode->next;
    
61.                 }
    
62.                 cout << tempNode->data << " ";
    
63.                 cout << endl;
    
64. 
    
65.                 return OK;
    
66.         }
    
67.         /*销毁链表*/
    
68.         Status ClearLinkList(MyLinkList* list)
    
69.         {
    
70.                 LinkNode *p,*q;
    
71.                 p = (*list)->next;
    
72.                 while (p)
    
73.                 {
    
74.                         q = p->next;
    
75.                         delete(p);
    
76.                         p = q;
    
77.                 }
    
78.                 delete(*list);
    
79.                 (*list) = nullptr;
    
80.                 return OK;
    
81.         }
    
82. 
    
83.         //方法一：依次向后赋值，相当于赋值一份头结点插入到第一个结点前面，再把最后一个结点删除;
    
84.         void MyChangeTest(MyLinkList* list)
    
85.         {
    
86.                 LinkNode *tempNode;//临时结点
    
87.                 LinkNode *head = new LinkNode(**list);//新复制一个头结点
    
88. 
    
89.                 (*list)->next = head;//链表指向新的头结点
    
90.                 tempNode = head->next;//临时结点赋值
    
91.                 if (tempNode->next == nullptr)
    
92.                         cout << "空链表" << endl;
    
93. 
    
94.                 while (tempNode->next->next!=nullptr)//找倒数第二个结点
    
95.                 {
    
96.                         tempNode = tempNode->next;
    
97.                 }
    
98.                 delete(tempNode->next);//删除最后一个结点
    
99.                 tempNode->next->next = nullptr;
    
100.                 tempNode->next = nullptr;//现在最后一个结点，原倒数第二个结点的next赋空
     
101.         }
     
102. 
     
103.         //方法二：按照题目要求，依次向后赋值;
     
104.         void MyChangeTest2(LinkNode* node,ElemType d)
     
105.         {
     
106.                 if (node->next == nullptr)//递归条件，当结点下一个指向空的时候返回
     
107.                 {
     
108.                         node->data = d;//先赋值再返回
     
109.                         return;
     
110.                 }
     
111.                 ElemType tempData = node->data;//保存当前结点的数据，用来传给下一个结点
     
112.                 node->data = d;//当前结点赋值上一个结点传过来的值
     
113.                 MyChangeTest2((node->next), tempData);//递归
     
114.         }
     
115. };
     
116. int main()
     
117. {
     
118.         MyLinkList *lklist = new MyLinkList();
     
119.         (*lklist)->ListCreateTail(lklist, 10);
     
120.         (*lklist)->ListShow(lklist);
     
121.         cout << "===============================" << endl;
     
122.         (*lklist)->MyChangeTest(lklist);//方法1
     
123.         (*lklist)->ListShow(lklist);
     
124.         (*lklist)->ClearLinkList(lklist);
     
125.         delete(lklist);
     
126.         lklist = nullptr;
     
127.         cout << "=================================================" << endl;
     
128.         MyLinkList *lklist2 = new MyLinkList();
     
129.         (*lklist2)->ListCreateTail(lklist2, 10);
     
130.         (*lklist2)->ListShow(lklist2);
     
131.         cout << "===============================" << endl;
     
132.         (*lklist2)->MyChangeTest2((*lklist2), (*lklist2)->data);//方法2
     
133.         (*lklist2)->ListShow(lklist2);
     
134.         (*lklist2)->ClearLinkList(lklist2);
     
135.         delete(lklist2);
     
136.         lklist2 = nullptr;
     
137. 
     
138.         int pause;
     
139.         cin >> pause;
     
140.         return 0;
     
141. }

复制代码