论坛 › 数据结构与算法 › 关于单循环链表的写法

1094570635 发表于 2022-11-8 20:45:09

关于单循环链表的写法

#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 20:58:43

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

Status DestroyList(LinkList *L) {
    ClearList(L);
    delete *L;
    *L = NULL;
    return OK;
}

人造人 发表于 2022-11-8 20:59:18

https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=220216&pid=6036030

人造人 发表于 2022-11-8 21:01:00

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

人造人 发表于 2022-11-8 21:02:03

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

1094570635 发表于 2022-11-8 21:30:01

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

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

人造人 发表于 2022-11-8 21:32:50

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

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

人造人 发表于 2022-11-8 21:34:39

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

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

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

1094570635 发表于 2022-11-8 21:53:00

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



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

人造人 发表于 2022-11-8 22:47:55

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

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

#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

using namespace std;

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

#define MAXSIZE 20

typedef int Status;
typedef int ElemType;

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

typedef struct Node *LinkList;

Status InitList(LinkList *L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList *L);
Status ListInsert(LinkList *L, int i, ElemType e);
Status ListDelete(LinkList *L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);

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

Status DestroyList(LinkList *L) {
    ClearList(L);
    delete *L;
    return OK;
}

Status ClearList(LinkList *L) {
    ElemType e;
    while(!ListEmpty(*L)) ListDelete(L, 0, &e);
    return OK;
}

Status ListInsert(LinkList *L, int i, ElemType e) {
    int length = ListLength(*L);
    if(i > length) return FALSE;
    LinkList p = *L;
    for(int x = 0; x < length - i; ++x) p = p->next;
    LinkList q = new Node;
    if(!q) return FALSE;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return TRUE;
}

Status ListDelete(LinkList *L, int i, ElemType *e) {
    int length = ListLength(*L);
    if(i >= length) return FALSE;
    LinkList p = *L;
    for(int x = 0; x < length - i - 1; ++x) p = p->next;
    LinkList q = p->next;
    p->next = q->next;
    delete q;
    return TRUE;
}

Status GetElem(LinkList L, int i, ElemType *e) {
    int length = ListLength(L);
    if(i >= length) return FALSE;
    LinkList p = L;
    for(int x = 0; x < length - i; ++x) p = p->next;
    *e = p->data;
    return TRUE;
}

Status SetElem(LinkList L, int i, const ElemType *e) {
    ElemType temp;
    Status s = ListDelete(&L, i, &temp);
    return s ? ListInsert(&L, i, *e) : s;
}

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

Status ListEmpty(LinkList L) {
    if(ListLength(L) == 0) return TRUE;
    return FALSE;
}

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

Status ListTraverse(LinkList L) {
    for(int i = 0; i < ListLength(L); ++i) {
      ElemType e;
      GetElem(L, i, &e);
      visit(e);
    }
    cout << endl;
    return OK;
}

Status ListAppend(LinkList L, const ElemType *e) {
    return ListInsert(&L, ListLength(L), *e);
}

int main() {
    LinkList L;
    InitList(&L);
    for(ElemType i = 0; i < 10; ++i) {
      ListAppend(L, &i);
    }
    ListTraverse(L);
    ElemType e = 100; SetElem(L, 3, &e);
    ListTraverse(L);
    GetElem(L, 5, &e);
    cout << e << endl;
    DestroyList(&L);
    return 0;
}

人造人 发表于 2022-11-8 22:53:43

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

#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

using namespace std;

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

#define MAXSIZE 20

typedef int Status;
typedef int ElemType;

typedef struct Node {
    ElemType data;
    //struct Node *next;
    struct Node *prev;
} Node;

typedef struct Node *LinkList;

Status InitList(LinkList *L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList *L);
Status ListInsert(LinkList *L, int i, ElemType e);
Status ListDelete(LinkList *L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);

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

Status DestroyList(LinkList *L) {
    ClearList(L);
    delete *L;
    return OK;
}

Status ClearList(LinkList *L) {
    ElemType e;
    while(!ListEmpty(*L)) ListDelete(L, 0, &e);
    return OK;
}

Status ListInsert(LinkList *L, int i, ElemType e) {
    int length = ListLength(*L);
    if(i > length) return FALSE;
    LinkList p = *L;
    for(int x = 0; x < length - i; ++x) p = p->prev;
    LinkList q = new Node;
    if(!q) return FALSE;
    q->data = e;
    q->prev = p->prev;
    p->prev = q;
    return TRUE;
}

Status ListDelete(LinkList *L, int i, ElemType *e) {
    int length = ListLength(*L);
    if(i >= length) return FALSE;
    LinkList p = *L;
    for(int x = 0; x < length - i - 1; ++x) p = p->prev;
    LinkList q = p->prev;
    p->prev = q->prev;
    delete q;
    return TRUE;
}

Status GetElem(LinkList L, int i, ElemType *e) {
    int length = ListLength(L);
    if(i >= length) return FALSE;
    LinkList p = L;
    for(int x = 0; x < length - i; ++x) p = p->prev;
    *e = p->data;
    return TRUE;
}

Status SetElem(LinkList L, int i, const ElemType *e) {
    ElemType temp;
    Status s = ListDelete(&L, i, &temp);
    return s ? ListInsert(&L, i, *e) : s;
}

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

Status ListEmpty(LinkList L) {
    if(ListLength(L) == 0) return TRUE;
    return FALSE;
}

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

Status ListTraverse(LinkList L) {
    for(int i = 0; i < ListLength(L); ++i) {
      ElemType e;
      GetElem(L, i, &e);
      visit(e);
    }
    cout << endl;
    return OK;
}

Status ListAppend(LinkList L, const ElemType *e) {
    return ListInsert(&L, ListLength(L), *e);
}

int main() {
    LinkList L;
    InitList(&L);
    for(ElemType i = 0; i < 10; ++i) {
      ListAppend(L, &i);
    }
    ListTraverse(L);
    ElemType e = 100; SetElem(L, 3, &e);
    ListTraverse(L);
    GetElem(L, 5, &e);
    cout << e << endl;
    DestroyList(&L);
    return 0;
}

1094570635 发表于 2022-11-8 23:30:15

人造人 发表于 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接收

人造人 发表于 2022-11-8 23:55:35

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


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

#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

using namespace std;

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

#define MAXSIZE 20

typedef int Status;
typedef int ElemType;

typedef struct Node {
    ElemType data;
    //struct Node *next;
    struct Node *prev;
} Node;

typedef struct Node *LinkList;

Status InitList(LinkList *L);
Status DestroyList(LinkList L);
Status ClearList(LinkList L);
Status ListInsert(LinkList L, int i, ElemType e);
Status ListDelete(LinkList L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);

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

Status DestroyList(LinkList L) {
    ClearList(L);
    delete L;
    return OK;
}

Status ClearList(LinkList L) {
    ElemType e;
    while(!ListEmpty(L)) ListDelete(L, 0, &e);
    return OK;
}

Status ListInsert(LinkList L, int i, ElemType e) {
    int length = ListLength(L);
    if(i > length) return FALSE;
    LinkList p = L;
    for(int x = 0; x < length - i; ++x) p = p->prev;
    LinkList q = new Node;
    if(!q) return FALSE;
    q->data = e;
    q->prev = p->prev;
    p->prev = q;
    return TRUE;
}

Status ListDelete(LinkList L, int i, ElemType *e) {
    int length = ListLength(L);
    if(i >= length) return FALSE;
    LinkList p = L;
    for(int x = 0; x < length - i - 1; ++x) p = p->prev;
    LinkList q = p->prev;
    p->prev = q->prev;
    delete q;
    return TRUE;
}

Status GetElem(LinkList L, int i, ElemType *e) {
    int length = ListLength(L);
    if(i >= length) return FALSE;
    LinkList p = L;
    for(int x = 0; x < length - i; ++x) p = p->prev;
    *e = p->data;
    return TRUE;
}

Status SetElem(LinkList L, int i, const ElemType *e) {
    ElemType temp;
    Status s = ListDelete(L, i, &temp);
    return s ? ListInsert(L, i, *e) : s;
}

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

Status ListEmpty(LinkList L) {
    if(ListLength(L) == 0) return TRUE;
    return FALSE;
}

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

Status ListTraverse(LinkList L) {
    for(int i = 0; i < ListLength(L); ++i) {
      ElemType e;
      GetElem(L, i, &e);
      visit(e);
    }
    cout << endl;
    return OK;
}

Status ListAppend(LinkList L, const ElemType *e) {
    return ListInsert(L, ListLength(L), *e);
}

int main() {
    LinkList L;
    InitList(&L);
    for(ElemType i = 0; i < 10; ++i) {
      ListAppend(L, &i);
    }
    ListTraverse(L);
    ElemType e = 100; SetElem(L, 3, &e);
    ListTraverse(L);
    GetElem(L, 5, &e);
    cout << e << endl;
    DestroyList(L);
    return 0;
}

1094570635 发表于 2022-11-9 19:33:02

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

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

人造人 发表于 2022-11-9 19:39:05

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

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

人造人 发表于 2022-11-9 19:40:35

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

1094570635 发表于 2022-11-9 22:15:50

人造人 发表于 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;
typedefint ElemType;
typedef struct Node
{
        ElemTypedata;
        /*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()函数的地址.

人造人 发表于 2022-11-9 23:39:42

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


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

#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 *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) {
#if 0
    LinkList p = (*L);
    while((*L)->last != (*L)) {
      p = (*L);
      (*L) = (*L)->last;
      delete p;
    }
    // 这里是不是少了这一句？
    // 我不知道你为什么就是坚持要这么写，你看出错了吧
    // 早跟你说过了，尽量避免直接操作底层结构
    // 因为这样很容易出错，代码也不好理解，出了问题调试的时候也很麻烦
    // 你就是不听
    // 你看这里你就少写了这一句，这样就内存泄露了
    delete *L;
#endif
    // 你看下面就两行代码，而且逻辑也非常清晰
    // 这样写代码怎么可能会出问题呢？
    ClearList(L);       // 清空链表
    delete *L;          // 删除头结点
    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;
    return Lb_Last->last;
}

int main() {
    int i;
    int j;
    int k;
    ElemType e;
    LinkList L;
    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=";   // date ?
    cout << "删除第一和第二个元素以后,L.date=";   // data ?
                                                    // date ? or data ?
    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);

    DestroyList(&L);    // ******************************** 要释放内存的说 **********************
    L = Connect(&La, &Lb); // Lb合并到La之后
    cout << "合并La,Lb后，L=";
    ListTraverse(L);

    DestroyList(&L);    // ******************************** 要释放内存的说 **********************
    return 0;
}

1094570635 发表于 2022-11-10 00:33:09

人造人 发表于 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以后往后的命令也不会显示

人造人 发表于 2022-11-10 00:42:54

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以后往后的命令也不会显示

’’’

什么？

查看完整版本: 关于单循环链表的写法