[已解决]关于单循环链表的写法

1094570635

#include<iostream>
using namespace std;
#include"time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0


typedef int Status;
typedef int ElemType;

typedef struct Node
{
        ElemType data;
        struct Node* next;

}Node,*LinkList;


Status visit(ElemType c);
Status InitList(LinkList* L);
Status ListEmpty(LinkList L);
Status ClearList(LinkList* L);
Status DestroyList(LinkList* L);


Status visit(ElemType c)
{
        cout << c << " ";
        return 0;
}
Status InitList(LinkList *L)
{
        *L = new Node;
        if (!(*L))
        {
                return ERROR;
        }
        (*L)->next = *L;

}

Status ListEmpty(LinkList L)
{
        if (L->next=L)
        {
                return TRUE;
        }
        else
        {
                return FALSE;
        }


}
Status ClearList(LinkList *L)
{
        LinkList p, q;
        p = (*L)->next;
        while (p!=*L)
        {
                q = p->next;
                delete p;
                p = q;
        }
        (*L)->next = *L;
        return OK;
}

Status DestroyList(LinkList* L)
{
        LinkList p;
        p = (*L);
        while (*L!=(*L)->next)
        {
                p = (*L);
                (*L) = (*L)->next;
                delete p;
        }
       delete *L;

        return OK;
       


}



int main()
{

        return 0;
}

如果判断了*L=*L->next,就是一个空表，循环结束再删除(*L)，有点繁琐，有没有更好解决的办法

最佳答案

月排行榜 / 总排行榜

人造人

2022-11-8 22:53:43

或者把next换成prev更好理解一些？

1. #include <iostream>
   
2. #include <ctype.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <math.h>
   
7. #include <time.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define TRUE 1
    
14. #define FALSE 0
    
15. 
    
16. #define MAXSIZE 20
    
17. 
    
18. typedef int Status;
    
19. typedef int ElemType;
    
20. 
    
21. typedef struct Node {
    
22.     ElemType data;
    
23.     //struct Node *next;
    
24.     struct Node *prev;
    
25. } Node;
    
26. 
    
27. typedef struct Node *LinkList;
    
28. 
    
29. Status InitList(LinkList *L);
    
30. Status DestroyList(LinkList *L);
    
31. Status ClearList(LinkList *L);
    
32. Status ListInsert(LinkList *L, int i, ElemType e);
    
33. Status ListDelete(LinkList *L, int i, ElemType *e);
    
34. Status GetElem(LinkList L, int i, ElemType *e);
    
35. Status SetElem(LinkList L, int i, const ElemType *e);
    
36. int ListLength(LinkList L);
    
37. Status ListEmpty(LinkList L);
    
38. Status ListTraverse(LinkList L);
    
39. 
    
40. Status InitList(LinkList *L) {
    
41.     *L = new Node;
    
42.     if(!*L) return ERROR;
    
43.     (*L)->prev = *L;
    
44.     return OK;
    
45. }
    
46. 
    
47. Status DestroyList(LinkList *L) {
    
48.     ClearList(L);
    
49.     delete *L;
    
50.     return OK;
    
51. }
    
52. 
    
53. Status ClearList(LinkList *L) {
    
54.     ElemType e;
    
55.     while(!ListEmpty(*L)) ListDelete(L, 0, &e);
    
56.     return OK;
    
57. }
    
58. 
    
59. Status ListInsert(LinkList *L, int i, ElemType e) {
    
60.     int length = ListLength(*L);
    
61.     if(i > length) return FALSE;
    
62.     LinkList p = *L;
    
63.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
64.     LinkList q = new Node;
    
65.     if(!q) return FALSE;
    
66.     q->data = e;
    
67.     q->prev = p->prev;
    
68.     p->prev = q;
    
69.     return TRUE;
    
70. }
    
71. 
    
72. Status ListDelete(LinkList *L, int i, ElemType *e) {
    
73.     int length = ListLength(*L);
    
74.     if(i >= length) return FALSE;
    
75.     LinkList p = *L;
    
76.     for(int x = 0; x < length - i - 1; ++x) p = p->prev;
    
77.     LinkList q = p->prev;
    
78.     p->prev = q->prev;
    
79.     delete q;
    
80.     return TRUE;
    
81. }
    
82. 
    
83. Status GetElem(LinkList L, int i, ElemType *e) {
    
84.     int length = ListLength(L);
    
85.     if(i >= length) return FALSE;
    
86.     LinkList p = L;
    
87.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
88.     *e = p->data;
    
89.     return TRUE;
    
90. }
    
91. 
    
92. Status SetElem(LinkList L, int i, const ElemType *e) {
    
93.     ElemType temp;
    
94.     Status s = ListDelete(&L, i, &temp);
    
95.     return s ? ListInsert(&L, i, *e) : s;
    
96. }
    
97. 
    
98. int ListLength(LinkList L) {
    
99.     int i = 0;
    
100.     LinkList p = L;
     
101.     while(p->prev != L) {
     
102.         i++;
     
103.         p = p->prev;
     
104.     }
     
105.     return i;
     
106. }
     
107. 
     
108. Status ListEmpty(LinkList L) {
     
109.     if(ListLength(L) == 0) return TRUE;
     
110.     return FALSE;
     
111. }
     
112. 
     
113. Status visit(ElemType c) {
     
114.     cout << c << " ";
     
115.     return OK;
     
116. }
     
117. 
     
118. Status ListTraverse(LinkList L) {
     
119.     for(int i = 0; i < ListLength(L); ++i) {
     
120.         ElemType e;
     
121.         GetElem(L, i, &e);
     
122.         visit(e);
     
123.     }
     
124.     cout << endl;
     
125.     return OK;
     
126. }
     
127. 
     
128. Status ListAppend(LinkList L, const ElemType *e) {
     
129.     return ListInsert(&L, ListLength(L), *e);
     
130. }
     
131. 
     
132. int main() {
     
133.     LinkList L;
     
134.     InitList(&L);
     
135.     for(ElemType i = 0; i < 10; ++i) {
     
136.         ListAppend(L, &i);
     
137.     }
     
138.     ListTraverse(L);
     
139.     ElemType e = 100; SetElem(L, 3, &e);
     
140.     ListTraverse(L);
     
141.     GetElem(L, 5, &e);
     
142.     cout << e << endl;
     
143.     DestroyList(&L);
     
144.     return 0;
     
145. }
     

复制代码

跳转到最佳答案楼层

人造人

好方法？之前不是给你写了吗？你都不看吗？

1. Status DestroyList(LinkList *L) {
   
2.     ClearList(L);
   
3.     delete *L;
   
4.     *L = NULL;
   
5.     return OK;
   
6. }
   

复制代码

人造人

https://fishc.com.cn/forum.php?m ... 216&pid=6036030

人造人

我不能理解，我给你写了那么多东西，你都不看，伤心的说

人造人

我还以为你都看了，都弄懂了

1094570635

人造人 发表于 2022-11-8 21:02
我还以为你都看了，都弄懂了

过一遍单链表以后，想手写一次循环单链表，思维卡主了，在循环链表上，设置头指针和尾指针上思路有些不够清晰

人造人

1094570635 发表于 2022-11-8 21:30
过一遍单链表以后，想手写一次循环单链表，思维卡主了，在循环链表上，设置头指针和尾指针上思路有些不够 ...

都一样，销毁链表就是把链表清空了，然后删除头结点

人造人

1094570635 发表于 2022-11-8 21:30
过一遍单链表以后，想手写一次循环单链表，思维卡主了，在循环链表上，设置头指针和尾指针上思路有些不够 ...

清空链表等于什么呢？
等于一直删除第0个结点，直到链表为空

删除结点就没办法了，得老老实实的操作底层结构

1094570635

人造人 发表于 2022-11-8 21:34
清空链表等于什么呢？
等于一直删除第0个结点，直到链表为空

有没有设置尾节点操作的办法，感觉循环链表用头结点操作比较麻烦orz，还有就是设置了尾节点操作链表插入,删除和单链表对比，需要做些什么修改么

人造人

1094570635 发表于 2022-11-8 21:53
有没有设置尾节点操作的办法，感觉循环链表用头结点操作比较麻烦orz，还有就是设置了尾节点操作链表插入, ...

把思维逆转过来，为什么头结点指向的就必须是第0个元素？
为什么头结点不能是指向最后一个元素？
下面这个代码把头结点指向的元素看成是最后一个元素
也就是那个所谓的 尾节点

1. #include <iostream>
   
2. #include <ctype.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <math.h>
   
7. #include <time.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define TRUE 1
    
14. #define FALSE 0
    
15. 
    
16. #define MAXSIZE 20
    
17. 
    
18. typedef int Status;
    
19. typedef int ElemType;
    
20. 
    
21. typedef struct Node {
    
22.     ElemType data;
    
23.     struct Node *next;
    
24. } Node;
    
25. 
    
26. typedef struct Node *LinkList;
    
27. 
    
28. Status InitList(LinkList *L);
    
29. Status DestroyList(LinkList *L);
    
30. Status ClearList(LinkList *L);
    
31. Status ListInsert(LinkList *L, int i, ElemType e);
    
32. Status ListDelete(LinkList *L, int i, ElemType *e);
    
33. Status GetElem(LinkList L, int i, ElemType *e);
    
34. Status SetElem(LinkList L, int i, const ElemType *e);
    
35. int ListLength(LinkList L);
    
36. Status ListEmpty(LinkList L);
    
37. Status ListTraverse(LinkList L);
    
38. 
    
39. Status InitList(LinkList *L) {
    
40.     *L = new Node;
    
41.     if(!*L) return ERROR;
    
42.     (*L)->next = *L;
    
43.     return OK;
    
44. }
    
45. 
    
46. Status DestroyList(LinkList *L) {
    
47.     ClearList(L);
    
48.     delete *L;
    
49.     return OK;
    
50. }
    
51. 
    
52. Status ClearList(LinkList *L) {
    
53.     ElemType e;
    
54.     while(!ListEmpty(*L)) ListDelete(L, 0, &e);
    
55.     return OK;
    
56. }
    
57. 
    
58. Status ListInsert(LinkList *L, int i, ElemType e) {
    
59.     int length = ListLength(*L);
    
60.     if(i > length) return FALSE;
    
61.     LinkList p = *L;
    
62.     for(int x = 0; x < length - i; ++x) p = p->next;
    
63.     LinkList q = new Node;
    
64.     if(!q) return FALSE;
    
65.     q->data = e;
    
66.     q->next = p->next;
    
67.     p->next = q;
    
68.     return TRUE;
    
69. }
    
70. 
    
71. Status ListDelete(LinkList *L, int i, ElemType *e) {
    
72.     int length = ListLength(*L);
    
73.     if(i >= length) return FALSE;
    
74.     LinkList p = *L;
    
75.     for(int x = 0; x < length - i - 1; ++x) p = p->next;
    
76.     LinkList q = p->next;
    
77.     p->next = q->next;
    
78.     delete q;
    
79.     return TRUE;
    
80. }
    
81. 
    
82. Status GetElem(LinkList L, int i, ElemType *e) {
    
83.     int length = ListLength(L);
    
84.     if(i >= length) return FALSE;
    
85.     LinkList p = L;
    
86.     for(int x = 0; x < length - i; ++x) p = p->next;
    
87.     *e = p->data;
    
88.     return TRUE;
    
89. }
    
90. 
    
91. Status SetElem(LinkList L, int i, const ElemType *e) {
    
92.     ElemType temp;
    
93.     Status s = ListDelete(&L, i, &temp);
    
94.     return s ? ListInsert(&L, i, *e) : s;
    
95. }
    
96. 
    
97. int ListLength(LinkList L) {
    
98.     int i = 0;
    
99.     LinkList p = L;
    
100.     while(p->next != L) {
     
101.         i++;
     
102.         p = p->next;
     
103.     }
     
104.     return i;
     
105. }
     
106. 
     
107. Status ListEmpty(LinkList L) {
     
108.     if(ListLength(L) == 0) return TRUE;
     
109.     return FALSE;
     
110. }
     
111. 
     
112. Status visit(ElemType c) {
     
113.     cout << c << " ";
     
114.     return OK;
     
115. }
     
116. 
     
117. Status ListTraverse(LinkList L) {
     
118.     for(int i = 0; i < ListLength(L); ++i) {
     
119.         ElemType e;
     
120.         GetElem(L, i, &e);
     
121.         visit(e);
     
122.     }
     
123.     cout << endl;
     
124.     return OK;
     
125. }
     
126. 
     
127. Status ListAppend(LinkList L, const ElemType *e) {
     
128.     return ListInsert(&L, ListLength(L), *e);
     
129. }
     
130. 
     
131. int main() {
     
132.     LinkList L;
     
133.     InitList(&L);
     
134.     for(ElemType i = 0; i < 10; ++i) {
     
135.         ListAppend(L, &i);
     
136.     }
     
137.     ListTraverse(L);
     
138.     ElemType e = 100; SetElem(L, 3, &e);
     
139.     ListTraverse(L);
     
140.     GetElem(L, 5, &e);
     
141.     cout << e << endl;
     
142.     DestroyList(&L);
     
143.     return 0;
     
144. }
     

复制代码

人造人

或者把next换成prev更好理解一些？

1. #include <iostream>
   
2. #include <ctype.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <math.h>
   
7. #include <time.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define TRUE 1
    
14. #define FALSE 0
    
15. 
    
16. #define MAXSIZE 20
    
17. 
    
18. typedef int Status;
    
19. typedef int ElemType;
    
20. 
    
21. typedef struct Node {
    
22.     ElemType data;
    
23.     //struct Node *next;
    
24.     struct Node *prev;
    
25. } Node;
    
26. 
    
27. typedef struct Node *LinkList;
    
28. 
    
29. Status InitList(LinkList *L);
    
30. Status DestroyList(LinkList *L);
    
31. Status ClearList(LinkList *L);
    
32. Status ListInsert(LinkList *L, int i, ElemType e);
    
33. Status ListDelete(LinkList *L, int i, ElemType *e);
    
34. Status GetElem(LinkList L, int i, ElemType *e);
    
35. Status SetElem(LinkList L, int i, const ElemType *e);
    
36. int ListLength(LinkList L);
    
37. Status ListEmpty(LinkList L);
    
38. Status ListTraverse(LinkList L);
    
39. 
    
40. Status InitList(LinkList *L) {
    
41.     *L = new Node;
    
42.     if(!*L) return ERROR;
    
43.     (*L)->prev = *L;
    
44.     return OK;
    
45. }
    
46. 
    
47. Status DestroyList(LinkList *L) {
    
48.     ClearList(L);
    
49.     delete *L;
    
50.     return OK;
    
51. }
    
52. 
    
53. Status ClearList(LinkList *L) {
    
54.     ElemType e;
    
55.     while(!ListEmpty(*L)) ListDelete(L, 0, &e);
    
56.     return OK;
    
57. }
    
58. 
    
59. Status ListInsert(LinkList *L, int i, ElemType e) {
    
60.     int length = ListLength(*L);
    
61.     if(i > length) return FALSE;
    
62.     LinkList p = *L;
    
63.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
64.     LinkList q = new Node;
    
65.     if(!q) return FALSE;
    
66.     q->data = e;
    
67.     q->prev = p->prev;
    
68.     p->prev = q;
    
69.     return TRUE;
    
70. }
    
71. 
    
72. Status ListDelete(LinkList *L, int i, ElemType *e) {
    
73.     int length = ListLength(*L);
    
74.     if(i >= length) return FALSE;
    
75.     LinkList p = *L;
    
76.     for(int x = 0; x < length - i - 1; ++x) p = p->prev;
    
77.     LinkList q = p->prev;
    
78.     p->prev = q->prev;
    
79.     delete q;
    
80.     return TRUE;
    
81. }
    
82. 
    
83. Status GetElem(LinkList L, int i, ElemType *e) {
    
84.     int length = ListLength(L);
    
85.     if(i >= length) return FALSE;
    
86.     LinkList p = L;
    
87.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
88.     *e = p->data;
    
89.     return TRUE;
    
90. }
    
91. 
    
92. Status SetElem(LinkList L, int i, const ElemType *e) {
    
93.     ElemType temp;
    
94.     Status s = ListDelete(&L, i, &temp);
    
95.     return s ? ListInsert(&L, i, *e) : s;
    
96. }
    
97. 
    
98. int ListLength(LinkList L) {
    
99.     int i = 0;
    
100.     LinkList p = L;
     
101.     while(p->prev != L) {
     
102.         i++;
     
103.         p = p->prev;
     
104.     }
     
105.     return i;
     
106. }
     
107. 
     
108. Status ListEmpty(LinkList L) {
     
109.     if(ListLength(L) == 0) return TRUE;
     
110.     return FALSE;
     
111. }
     
112. 
     
113. Status visit(ElemType c) {
     
114.     cout << c << " ";
     
115.     return OK;
     
116. }
     
117. 
     
118. Status ListTraverse(LinkList L) {
     
119.     for(int i = 0; i < ListLength(L); ++i) {
     
120.         ElemType e;
     
121.         GetElem(L, i, &e);
     
122.         visit(e);
     
123.     }
     
124.     cout << endl;
     
125.     return OK;
     
126. }
     
127. 
     
128. Status ListAppend(LinkList L, const ElemType *e) {
     
129.     return ListInsert(&L, ListLength(L), *e);
     
130. }
     
131. 
     
132. int main() {
     
133.     LinkList L;
     
134.     InitList(&L);
     
135.     for(ElemType i = 0; i < 10; ++i) {
     
136.         ListAppend(L, &i);
     
137.     }
     
138.     ListTraverse(L);
     
139.     ElemType e = 100; SetElem(L, 3, &e);
     
140.     ListTraverse(L);
     
141.     GetElem(L, 5, &e);
     
142.     cout << e << endl;
     
143.     DestroyList(&L);
     
144.     return 0;
     
145. }
     

复制代码

1094570635

人造人 发表于 2022-11-8 22:53
或者把next换成prev更好理解一些？

Status DestroyList(LinkList *L) {
    ClearList(L);
    delete *L;
    *L = NULL;
    return OK;
}
感谢，另外我能问一下，ClearList(L)函数中，即是函数调用函数的时候，形参L=LinkList L,对么?即是可以直接写L，不用&L接收

人造人

1094570635 发表于 2022-11-8 23:30
Status DestroyList(LinkList *L) {
    ClearList(L);
    delete *L;

就初始化的时候需要取地址，其他的都不需要

1. #include <iostream>
   
2. #include <ctype.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <math.h>
   
7. #include <time.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define TRUE 1
    
14. #define FALSE 0
    
15. 
    
16. #define MAXSIZE 20
    
17. 
    
18. typedef int Status;
    
19. typedef int ElemType;
    
20. 
    
21. typedef struct Node {
    
22.     ElemType data;
    
23.     //struct Node *next;
    
24.     struct Node *prev;
    
25. } Node;
    
26. 
    
27. typedef struct Node *LinkList;
    
28. 
    
29. Status InitList(LinkList *L);
    
30. Status DestroyList(LinkList L);
    
31. Status ClearList(LinkList L);
    
32. Status ListInsert(LinkList L, int i, ElemType e);
    
33. Status ListDelete(LinkList L, int i, ElemType *e);
    
34. Status GetElem(LinkList L, int i, ElemType *e);
    
35. Status SetElem(LinkList L, int i, const ElemType *e);
    
36. int ListLength(LinkList L);
    
37. Status ListEmpty(LinkList L);
    
38. Status ListTraverse(LinkList L);
    
39. 
    
40. Status InitList(LinkList *L) {
    
41.     *L = new Node;
    
42.     if(!*L) return ERROR;
    
43.     (*L)->prev = *L;
    
44.     return OK;
    
45. }
    
46. 
    
47. Status DestroyList(LinkList L) {
    
48.     ClearList(L);
    
49.     delete L;
    
50.     return OK;
    
51. }
    
52. 
    
53. Status ClearList(LinkList L) {
    
54.     ElemType e;
    
55.     while(!ListEmpty(L)) ListDelete(L, 0, &e);
    
56.     return OK;
    
57. }
    
58. 
    
59. Status ListInsert(LinkList L, int i, ElemType e) {
    
60.     int length = ListLength(L);
    
61.     if(i > length) return FALSE;
    
62.     LinkList p = L;
    
63.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
64.     LinkList q = new Node;
    
65.     if(!q) return FALSE;
    
66.     q->data = e;
    
67.     q->prev = p->prev;
    
68.     p->prev = q;
    
69.     return TRUE;
    
70. }
    
71. 
    
72. Status ListDelete(LinkList L, int i, ElemType *e) {
    
73.     int length = ListLength(L);
    
74.     if(i >= length) return FALSE;
    
75.     LinkList p = L;
    
76.     for(int x = 0; x < length - i - 1; ++x) p = p->prev;
    
77.     LinkList q = p->prev;
    
78.     p->prev = q->prev;
    
79.     delete q;
    
80.     return TRUE;
    
81. }
    
82. 
    
83. Status GetElem(LinkList L, int i, ElemType *e) {
    
84.     int length = ListLength(L);
    
85.     if(i >= length) return FALSE;
    
86.     LinkList p = L;
    
87.     for(int x = 0; x < length - i; ++x) p = p->prev;
    
88.     *e = p->data;
    
89.     return TRUE;
    
90. }
    
91. 
    
92. Status SetElem(LinkList L, int i, const ElemType *e) {
    
93.     ElemType temp;
    
94.     Status s = ListDelete(L, i, &temp);
    
95.     return s ? ListInsert(L, i, *e) : s;
    
96. }
    
97. 
    
98. int ListLength(LinkList L) {
    
99.     int i = 0;
    
100.     LinkList p = L;
     
101.     while(p->prev != L) {
     
102.         i++;
     
103.         p = p->prev;
     
104.     }
     
105.     return i;
     
106. }
     
107. 
     
108. Status ListEmpty(LinkList L) {
     
109.     if(ListLength(L) == 0) return TRUE;
     
110.     return FALSE;
     
111. }
     
112. 
     
113. Status visit(ElemType c) {
     
114.     cout << c << " ";
     
115.     return OK;
     
116. }
     
117. 
     
118. Status ListTraverse(LinkList L) {
     
119.     for(int i = 0; i < ListLength(L); ++i) {
     
120.         ElemType e;
     
121.         GetElem(L, i, &e);
     
122.         visit(e);
     
123.     }
     
124.     cout << endl;
     
125.     return OK;
     
126. }
     
127. 
     
128. Status ListAppend(LinkList L, const ElemType *e) {
     
129.     return ListInsert(L, ListLength(L), *e);
     
130. }
     
131. 
     
132. int main() {
     
133.     LinkList L;
     
134.     InitList(&L);
     
135.     for(ElemType i = 0; i < 10; ++i) {
     
136.         ListAppend(L, &i);
     
137.     }
     
138.     ListTraverse(L);
     
139.     ElemType e = 100; SetElem(L, 3, &e);
     
140.     ListTraverse(L);
     
141.     GetElem(L, 5, &e);
     
142.     cout << e << endl;
     
143.     DestroyList(L);
     
144.     return 0;
     
145. }
     

复制代码

1094570635

人造人 发表于 2022-11-8 23:55
就初始化的时候需要取地址，其他的都不需要

在循环链表中，插入位置的合理性不能用p！=NULL,能否用p！=L来判断？，还是只能通过表长的长度来判断元素的插入位置是否合理？

人造人

1094570635 发表于 2022-11-9 19:33
在循环链表中，插入位置的合理性不能用p！=NULL,能否用p！=L来判断？，还是只能通过表长的长度来判断元素 ...

整那么复杂干嘛
通过表长的长度来判断

人造人

获取链表长度的函数已经写了，写了函数为什么不用呢，直接用链表长度判断不是更好？

1094570635

人造人 发表于 2022-11-9 19:40
获取链表长度的函数已经写了，写了函数为什么不用呢，直接用链表长度判断不是更好？

稍微自己写了下，加了点功能
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef  int ElemType;
typedef struct Node
{
        ElemType  data;
        /*struct Node* next;*/
        struct Node* last;

}Node,*LinkList;


Status visit(ElemType c);
Status InitList(LinkList* L);
Status EmptyList(LinkList L);
Status DestroyList(LinkList* L);
Status ClearList(LinkList* L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType* e);
int LocateElem(LinkList L, ElemType e);
Node* LocateElem2(LinkList L, ElemType e);
Status ListInsert(LinkList* L, int i, ElemType e);
Status ListDelete(LinkList* L, int i, ElemType* e);
void CreatListHead(LinkList* L, int n);
void CreatListTail(LinkList* L, int n);
Status ListTraverse(LinkList L);

Status visit(ElemType c)
{
        cout << c << " ";
        return OK;
}

Status InitList(LinkList *L)
{
        *L = new Node;
        if(!(*L))
        {
                return ERROR;
        }
        (*L)->last = *L;
        return OK;
}

Status EmptyList(LinkList L)
{
        if (L->last!=L)
        {
                return FALSE;
        }
        else
        {
                return TRUE;
        }

}

Status DestroyList(LinkList *L)
{
        LinkList p = (*L);
        while ((*L)->last!=(*L))
        {
                p = (*L);
                (*L) = (*L)->last;
                delete p;

        }
        return OK;

}

Status ClearList(LinkList *L)
{
        LinkList p, q;
        p = (*L)->last;
        while (p!=(*L))
        {
                q = p->last;
                delete p;
                p = q;
        }
        (*L)->last =(*L);
        return OK;
}

int ListLength(LinkList L)
{
        int i = 0;
        LinkList p = L->last;
        while (p!=L)
        {
                i++;
                p = p->last;

        }
        return i;
       
}

Status GetElem(LinkList L,int i, ElemType *e)
{
        int j = 1;
        LinkList p = L->last;
        while (p != L&&j<i )
        {
                p = p->last;
                j++;

        }
        if (p==L||j>i)
        {
                return ERROR;
        }
        *e = p->data;
        return OK;

}

int LocateElem(LinkList L, ElemType e)
{
        LinkList p = L->last;
        int i = 0;
        while (p!=L)
        {
                ++i;
                if (p->data==e)
                {
                        return i;
                }
                p = p->last;

        }
        return i;

}

Node* LocateElem2(LinkList L, ElemType e)
{
        LinkList p = L->last;
        while (p!=L)
        {
                if (p->data==e)
                {
                        return p;
                }

        }
        return p;

}

Status ListInsert(LinkList* L, int i, ElemType e)
{
        int length = ListLength(*L)+1;
        if (i > length||i<1)
        {
                return ERROR;
        }

        LinkList p, s;
        p = (*L);
        int j = 0;
        while (j<i-1)
        {
                ++j;
                p = p->last;

        }
        /*if (j>i-1)
        {
                return ERROR;
        }*/
        s = new Node;
        s->data=e;
        s->last = p->last;
        p->last = s;
        return OK;

}

Status ListDelete(LinkList* L, int i, ElemType* e)
{
        int length = ListLength(*L);
        if (i>length||i<1)
        {
                return ERROR;
        }

        int j=0;
        LinkList p, q;
        p = *L;
        while (p->last!=*L &&j<i-1)
        {
                p = p->last;
                ++j;
        }
        /*if (j > i - 1)
        {
                return ERROR;
        }*/

        q = p->last;
        p->last = q->last;
        *e = q->data;
        delete q;
        return OK;

}
Status ListTraverse(LinkList L)
{
        LinkList p = L->last;
        while (p!=L)
        {
                visit(p->data);
                p = p->last;
        }
        cout << endl;
        return OK;
       


}
void CreatListHead(LinkList* L, int n)
{
        *L = new Node;
        (*L)->last = *L;
        LinkList p;

        for (int i=0;i<n;i++)
        {
                p = new Node;
                cin >> p->data;
                p->last = (*L)->last;
                (*L)->last = p;


        }


}



void CreatListTail(LinkList* L, int n)
{
        LinkList p, r;
        *L = new Node;
        (*L)->last = (*L);
        r = (*L);
        for (int i=0;i<n;i++)
        {
                p = new Node;
                cin >> p->data;
                r->last = p;
                r = p;

        }
        r->last = *L;

}


Node* FindLast(Node* L)
{
        Node* p = L->last;
        while (p->last != L)
        {
                p = p->last;
        }
        return p;

}

LinkList Connect(LinkList*La,LinkList*Lb)
{
        LinkList La_last, Lb_Last;
        LinkList p;
        La_last = FindLast(*La);
        Lb_Last = FindLast(*Lb);

        p = La_last->last;
        La_last->last = Lb_Last->last->last;
        delete Lb_Last->last;
        Lb_Last->last = p;
        return Lb_Last;


}



int main()
{
        int i;
        int j;
        int k;
        ElemType e;
        LinkList L;
        LinkList p;
        LinkList La, Lb;
        i = InitList(&L);
        cout << "初始化链表(1.成功 0.失败)"<<i<< endl;
       
        for (j=1;j<=5;j++)
        {
                ListInsert(&L, 1, j);
        }
        cout << "表头插入5个元素后，L.data=";
        ListTraverse(L);


        i = EmptyList(L);
        cout << "L是否为空(1.是 0.否)" << i << endl;

        i = ClearList(&L);
        cout << "清空L后ListLength(L)=" << ListLength(L) << endl;

        i = EmptyList(L);
        cout << "L是否为空(1.是 0.否)" << i << endl;


        for (j = 1; j <= 10; j++)
        {
                ListInsert(&L, j, j);
        }
        cout << "表尾插入10个元素后，L.data=";
        ListTraverse(L);


        GetElem(L, 5, &e);
        cout << "第5个元素的值为" << e << endl;

        e = 9;
        i=LocateElem(L, e);
       
        if (i == 0)
        {
                cout << "没有找到值为" << e << "的元素" << endl;
        }
        else
        {
                cout << "值为" << e << "的元素的位序为" << i << endl;
        }
        /*p=LocateElem2(L, e);
        cout << "值为" << e << "元素的地址为" << p<< endl;*/

       
        for (i = 1; i <= 2; i++)
        {
                ListDelete(&L, 1, &e);

        }
        cout << "删除第一和第二个元素以后,L.date=";
        ListTraverse(L);

        k = ListLength(L);
        int T = 0;
        for (int j=1;j<=k+1;j++)
        {
                T++;
                i = ListDelete(&L, 1, &e);
                        if(i==ERROR)
                        {
                                cout << "删除第" << T << "个元素失败" << endl;
                        }
                        else
                        {
                                cout << "删除第" << T << "个元素的值为" << e << endl;
                        }

        }

        i = EmptyList(L);
        cout << "L是否为空(1.是 0.否)" << i << endl;

        cout << "插入元素（头插法）" << endl;
        CreatListHead(&La, 5);
        cout << "整体创建L的元素（头插法）" << endl;
        ListTraverse(La);

        cout << "插入元素（尾插法）" << endl;
        CreatListTail(&Lb, 5);
        cout << "整体创建L的元素（尾插法）" << endl;
        ListTraverse(Lb);
       
        L = Connect(&La, &Lb);//Lb合并到La之后
        cout << "合并La,Lb后，L=";
        ListTraverse(L);



        return 0;
}
发现合并La，Lb以后L的元素出错，还有就是p指针接收不了locateElem2()函数的地址.

人造人

1094570635 发表于 2022-11-9 22:15
稍微自己写了下，加了点功能
#include
using namespace std;

问题不大
4个问题
1. DestroyList 函数漏了个 delete *L; 为什么会这样呢？
2. 不释放内存，也就是没有调用 DestroyList 函数，为什么会这样呢？
3. date ? or data ?
4. Connect 函数最后返回的结点错了，这里你应该是大意了吧，上面4个步骤都没问题，说明你应该是理解了这个合并的过程了，就是最后返回错结点了

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. #define OK 1
   
6. #define ERROR 0
   
7. #define TRUE 1
   
8. #define FALSE 0
   
9. 
   
10. typedef int Status;
    
11. typedef int ElemType;
    
12. typedef struct Node {
    
13.     ElemType data;
    
14.     struct Node *last;
    
15. 
    
16. } Node, *LinkList;
    
17. 
    
18. Status visit(ElemType c);
    
19. Status InitList(LinkList *L);
    
20. Status EmptyList(LinkList L);
    
21. Status DestroyList(LinkList *L);
    
22. Status ClearList(LinkList *L);
    
23. int ListLength(LinkList L);
    
24. Status GetElem(LinkList L, int i, ElemType *e);
    
25. int LocateElem(LinkList L, ElemType e);
    
26. Node *LocateElem2(LinkList L, ElemType e);
    
27. Status ListInsert(LinkList *L, int i, ElemType e);
    
28. Status ListDelete(LinkList *L, int i, ElemType *e);
    
29. void CreatListHead(LinkList *L, int n);
    
30. void CreatListTail(LinkList *L, int n);
    
31. Status ListTraverse(LinkList L);
    
32. 
    
33. Status visit(ElemType c) {
    
34.     cout << c << " ";
    
35.     return OK;
    
36. }
    
37. 
    
38. Status InitList(LinkList *L) {
    
39.     *L = new Node;
    
40.     if(!(*L)) {
    
41.         return ERROR;
    
42.     }
    
43.     (*L)->last = *L;
    
44.     return OK;
    
45. }
    
46. 
    
47. Status EmptyList(LinkList L) {
    
48.     if(L->last != L) {
    
49.         return FALSE;
    
50.     } else {
    
51.         return TRUE;
    
52.     }
    
53. }
    
54. 
    
55. Status DestroyList(LinkList *L) {
    
56. #if 0
    
57.     LinkList p = (*L);
    
58.     while((*L)->last != (*L)) {
    
59.         p = (*L);
    
60.         (*L) = (*L)->last;
    
61.         delete p;
    
62.     }
    
63.     // 这里是不是少了这一句？
    
64.     // 我不知道你为什么就是坚持要这么写，你看出错了吧
    
65.     // 早跟你说过了，尽量避免直接操作底层结构
    
66.     // 因为这样很容易出错，代码也不好理解，出了问题调试的时候也很麻烦
    
67.     // 你就是不听
    
68.     // 你看这里你就少写了这一句，这样就内存泄露了
    
69.     delete *L;
    
70. #endif
    
71.     // 你看下面就两行代码，而且逻辑也非常清晰
    
72.     // 这样写代码怎么可能会出问题呢？
    
73.     ClearList(L);       // 清空链表
    
74.     delete *L;          // 删除头结点
    
75.     return OK;
    
76. }
    
77. 
    
78. Status ClearList(LinkList *L) {
    
79.     LinkList p, q;
    
80.     p = (*L)->last;
    
81.     while(p != (*L)) {
    
82.         q = p->last;
    
83.         delete p;
    
84.         p = q;
    
85.     }
    
86.     (*L)->last = (*L);
    
87.     return OK;
    
88. }
    
89. 
    
90. int ListLength(LinkList L) {
    
91.     int i = 0;
    
92.     LinkList p = L->last;
    
93.     while(p != L) {
    
94.         i++;
    
95.         p = p->last;
    
96.     }
    
97.     return i;
    
98. }
    
99. 
    
100. Status GetElem(LinkList L, int i, ElemType *e) {
     
101.     int j = 1;
     
102.     LinkList p = L->last;
     
103.     while(p != L && j < i) {
     
104.         p = p->last;
     
105.         j++;
     
106.     }
     
107.     if(p == L || j > i) {
     
108.         return ERROR;
     
109.     }
     
110.     *e = p->data;
     
111.     return OK;
     
112. }
     
113. 
     
114. int LocateElem(LinkList L, ElemType e) {
     
115.     LinkList p = L->last;
     
116.     int i = 0;
     
117.     while(p != L) {
     
118.         ++i;
     
119.         if(p->data == e) {
     
120.             return i;
     
121.         }
     
122.         p = p->last;
     
123.     }
     
124.     return i;
     
125. }
     
126. 
     
127. Node *LocateElem2(LinkList L, ElemType e) {
     
128.     LinkList p = L->last;
     
129.     while(p != L) {
     
130.         if(p->data == e) {
     
131.             return p;
     
132.         }
     
133.     }
     
134.     return p;
     
135. }
     
136. 
     
137. Status ListInsert(LinkList *L, int i, ElemType e) {
     
138.     int length = ListLength(*L) + 1;
     
139.     if(i > length || i < 1) {
     
140.         return ERROR;
     
141.     }
     
142. 
     
143.     LinkList p, s;
     
144.     p = (*L);
     
145.     int j = 0;
     
146.     while(j < i - 1) {
     
147.         ++j;
     
148.         p = p->last;
     
149.     }
     
150.     /*if (j>i-1)
     
151.     {
     
152.             return ERROR;
     
153.     }*/
     
154.     s = new Node;
     
155.     s->data = e;
     
156.     s->last = p->last;
     
157.     p->last = s;
     
158.     return OK;
     
159. }
     
160. 
     
161. Status ListDelete(LinkList *L, int i, ElemType *e) {
     
162.     int length = ListLength(*L);
     
163.     if(i > length || i < 1) {
     
164.         return ERROR;
     
165.     }
     
166. 
     
167.     int j = 0;
     
168.     LinkList p, q;
     
169.     p = *L;
     
170.     while(p->last != *L && j < i - 1) {
     
171.         p = p->last;
     
172.         ++j;
     
173.     }
     
174.     /*if (j > i - 1)
     
175.     {
     
176.             return ERROR;
     
177.     }*/
     
178. 
     
179.     q = p->last;
     
180.     p->last = q->last;
     
181.     *e = q->data;
     
182.     delete q;
     
183.     return OK;
     
184. }
     
185. Status ListTraverse(LinkList L) {
     
186.     LinkList p = L->last;
     
187.     while(p != L) {
     
188.         visit(p->data);
     
189.         p = p->last;
     
190.     }
     
191.     cout << endl;
     
192.     return OK;
     
193. }
     
194. void CreatListHead(LinkList *L, int n) {
     
195.     *L = new Node;
     
196.     (*L)->last = *L;
     
197.     LinkList p;
     
198. 
     
199.     for(int i = 0; i < n; i++) {
     
200.         p = new Node;
     
201.         cin >> p->data;
     
202.         p->last = (*L)->last;
     
203.         (*L)->last = p;
     
204.     }
     
205. }
     
206. 
     
207. void CreatListTail(LinkList *L, int n) {
     
208.     LinkList p, r;
     
209.     *L = new Node;
     
210.     (*L)->last = (*L);
     
211.     r = (*L);
     
212.     for(int i = 0; i < n; i++) {
     
213.         p = new Node;
     
214.         cin >> p->data;
     
215.         r->last = p;
     
216.         r = p;
     
217.     }
     
218.     r->last = *L;
     
219. }
     
220. 
     
221. Node *FindLast(Node *L) {
     
222.     Node *p = L->last;
     
223.     while(p->last != L) {
     
224.         p = p->last;
     
225.     }
     
226.     return p;
     
227. }
     
228. 
     
229. LinkList Connect(LinkList *La, LinkList *Lb) {
     
230.     LinkList La_last, Lb_Last;
     
231.     LinkList p;
     
232.     La_last = FindLast(*La);
     
233.     Lb_Last = FindLast(*Lb);
     
234. 
     
235.     p = La_last->last;
     
236.     La_last->last = Lb_Last->last->last;
     
237.     delete Lb_Last->last;
     
238.     Lb_Last->last = p;
     
239.     //return Lb_Last;
     
240.     return Lb_Last->last;
     
241. }
     
242. 
     
243. int main() {
     
244.     int i;
     
245.     int j;
     
246.     int k;
     
247.     ElemType e;
     
248.     LinkList L;
     
249.     LinkList La, Lb;
     
250.     i = InitList(&L);
     
251.     cout << "初始化链表(1.成功 0.失败)" << i << endl;
     
252. 
     
253.     for(j = 1; j <= 5; j++) {
     
254.         ListInsert(&L, 1, j);
     
255.     }
     
256.     cout << "表头插入5个元素后，L.data=";
     
257.     ListTraverse(L);
     
258. 
     
259.     i = EmptyList(L);
     
260.     cout << "L是否为空(1.是 0.否)" << i << endl;
     
261. 
     
262.     i = ClearList(&L);
     
263.     cout << "清空L后ListLength(L)=" << ListLength(L) << endl;
     
264. 
     
265.     i = EmptyList(L);
     
266.     cout << "L是否为空(1.是 0.否)" << i << endl;
     
267. 
     
268.     for(j = 1; j <= 10; j++) {
     
269.         ListInsert(&L, j, j);
     
270.     }
     
271.     cout << "表尾插入10个元素后，L.data=";
     
272.     ListTraverse(L);
     
273. 
     
274.     GetElem(L, 5, &e);
     
275.     cout << "第5个元素的值为" << e << endl;
     
276. 
     
277.     e = 9;
     
278.     i = LocateElem(L, e);
     
279. 
     
280.     if(i == 0) {
     
281.         cout << "没有找到值为" << e << "的元素" << endl;
     
282.     } else {
     
283.         cout << "值为" << e << "的元素的位序为" << i << endl;
     
284.     }
     
285.     /*p=LocateElem2(L, e);
     
286.     cout << "值为" << e << "元素的地址为" << p<< endl;*/
     
287. 
     
288.     for(i = 1; i <= 2; i++) {
     
289.         ListDelete(&L, 1, &e);
     
290.     }
     
291.     //cout << "删除第一和第二个元素以后,L.date=";   // date ?
     
292.     cout << "删除第一和第二个元素以后,L.date=";     // data ?
     
293.                                                     // date ? or data ?
     
294.     ListTraverse(L);
     
295. 
     
296.     k = ListLength(L);
     
297.     int T = 0;
     
298.     for(int j = 1; j <= k + 1; j++) {
     
299.         T++;
     
300.         i = ListDelete(&L, 1, &e);
     
301.         if(i == ERROR) {
     
302.             cout << "删除第" << T << "个元素失败" << endl;
     
303.         } else {
     
304.             cout << "删除第" << T << "个元素的值为" << e << endl;
     
305.         }
     
306.     }
     
307. 
     
308.     i = EmptyList(L);
     
309.     cout << "L是否为空(1.是 0.否)" << i << endl;
     
310. 
     
311.     cout << "插入元素（头插法）" << endl;
     
312.     CreatListHead(&La, 5);
     
313.     cout << "整体创建L的元素（头插法）" << endl;
     
314.     ListTraverse(La);
     
315. 
     
316.     cout << "插入元素（尾插法）" << endl;
     
317.     CreatListTail(&Lb, 5);
     
318.     cout << "整体创建L的元素（尾插法）" << endl;
     
319.     ListTraverse(Lb);
     
320. 
     
321.     DestroyList(&L);    // ******************************** 要释放内存的说 **********************
     
322.     L = Connect(&La, &Lb); // Lb合并到La之后
     
323.     cout << "合并La,Lb后，L=";
     
324.     ListTraverse(L);
     
325. 
     
326.     DestroyList(&L);    // ******************************** 要释放内存的说 **********************
     
327.     return 0;
     
328. }
     

复制代码

1094570635

人造人 发表于 2022-11-9 23:39
问题不大
4个问题
1. DestroyList 函数漏了个 delete *L; 为什么会这样呢？

LinkList Connect(LinkList* La, LinkList* Lb) {
    LinkList La_last, Lb_Last;
    LinkList p;
    La_last = FindLast(*La);
    Lb_Last = FindLast(*Lb);

    p = La_last->last;
    La_last->last = Lb_Last->last->last;
    delete Lb_Last->last;
    Lb_Last->last = p;
    return Lb_Last->last;
}最后这个return 是否可以返回*La,或者*Lb?我发现返回*La程序似乎可以运行，*Lb则会引发 异常“ p 是 0xFFFFFFFFFFFFFFF7“

关于这个
p=LocateElem2(L, e);
    cout << "值为" << e << "元素的地址为" << p<< endl;，我无法获取e的地址，并且输出cout以后往后的命令也不会显示

人造人

1094570635 发表于 2022-11-10 00:33
LinkList Connect(LinkList* La, LinkList* Lb) {
    LinkList La_last, Lb_Last;
    LinkList p;

你是没有理解了这个合并的过程吗？你上面那4行代码怎么写出来的？
delete Lb_Last->last;
这都把Lb的头结点删除了
多画图，不理解的地方画画图就理解了



‘‘‘
关于这个
p=LocateElem2(L, e);
    cout << "值为" << e << "元素的地址为" << p<< endl;，我无法获取e的地址，并且输出cout以后往后的命令也不会显示

’’’

什么？