鱼C论坛

 找回密码
 立即注册
12
返回列表 发新帖
楼主: 1094570635

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

[复制链接]
发表于 2022-11-10 00:52:42 | 显示全部楼层
这个问题是不认真导致的吗?应该是吧

  1. Node *LocateElem2(LinkList L, ElemType e) {
  2.     LinkList p = L->last;
  3.     while(p != L) {
  4.         if(p->data == e) {
  5.             return p;
  6.         }
  7.         p = p->last;    // p 是不是要等于 p 的下一个?
  8.     }
  9.     return p;
  10. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2022-11-10 17:40:18 | 显示全部楼层
人造人 发表于 2022-11-10 00:42
你是没有理解了这个合并的过程吗?你上面那4行代码怎么写出来的?
delete Lb_Last->last;
这都把Lb的头 ...

其实我就是在想删除了Lb头结点以后,是否还能访问链表Lb,再想想应该是不行的,如何不能访问到删除了头结点的Lb,Lb后面的元素计算机存储到了哪里.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-10 17:46:43 | 显示全部楼层
1094570635 发表于 2022-11-10 17:40
其实我就是在想删除了Lb头结点以后,是否还能访问链表Lb,再想想应该是不行的,如何不能访问到删除了头结 ...

什么?
没看懂你在说什么
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-10 21:14:44 | 显示全部楼层
人造人 发表于 2022-11-10 17:46
什么?
没看懂你在说什么

就是在想就是删除了Lb头结点以后,Lb后面的结点有没有办法访问,后面的结点是否还存着
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-10 21:22:01 | 显示全部楼层
1094570635 发表于 2022-11-10 21:14
就是在想就是删除了Lb头结点以后,Lb后面的结点有没有办法访问,后面的结点是否还存着

当然存在了,你只是删除了Lb的头结点,又没有删除Lb后面的结点
你能看懂我画的那个图吗?
执行完那4步后 La_last->last 指向哪里?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-10 21:26:08 | 显示全部楼层
La_last 指向的不是 2 么?
那 La_last->last 指向的是什么?还是 La 的头结点吗? 第2步执行完以后,La_last->last 就不指向 La 的头结点了吧?
La_last->last 指向的是不是 3 这个结点?
3 这个结点是不是 Lb 头结点的后面的结点?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2022-11-19 00:34:22 | 显示全部楼层
人造人 发表于 2022-11-10 00:42
你是没有理解了这个合并的过程吗?你上面那4行代码怎么写出来的?
delete Lb_Last->last;
这都把Lb的头 ...

#include<iostream>
using namespace std;

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

typedef int Status;
typedef int ElemType;

typedef struct Node
{
        ElemType data;
        struct Node* next;
}Node,*LinkList;
//typedef struct Node* LinkList;

Status visit(ElemType e);
Status InitList(LinkList& L);
Status EmptyList(LinkList L);
Status ClearList(LinkList& L);
Status DestroyList(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 CreatHead(LinkList& L, int n);
void CreatTail(LinkList& L, int n);
Node* FindeLast(Node* L);
LinkList Connect(LinkList& La, LinkList& Lb);
Status ListTravers(LinkList L);

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

Status InitList(LinkList &L)
{
        L = new Node;
        if (!L)
        {
                return ERROR;
                cout << "创建内存失败" << endl;
        }
        L->next = L;
        return OK;

}
Status EmptyList(LinkList L)
{
        if (L->next==L)
        {
                return TRUE;
                cout << "链表为空" << endl;
        }
        else
        {
                return FALSE;
                cout << "链表非空" << endl;
        }
}

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;

        /*ElemType e;
        int length = ListLength(L);
        for (int i=1;i<=length;i++)
        {
                ListDelete(L, i, e);
        }
        return OK;*/
       
       
}

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

        }
        delete L;
        return OK;

        /*ClearList(L);
        delete L;
        L= NULL;
        return OK;*/
       
}


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

}


Status GetElem(LinkList L,int i,ElemType &e)
{
        /*LinkList p = L->next;
        int j = 1;
        while (p!=L &&j<i)
        {
                j++;
                p = p->next;
        }
        if (p==L||j>i)
        {
                return ERROR;
        }
        e = p->data;
        return OK;*/

        int length = ListLength(L);
        if (i<1 || i>length||length==0)
        {
                return ERROR;
        }
        LinkList p = L->next;
        for (int j=1;j<i;j++)
        {
                p = p->next;
        }
        e = p->data;
    return OK;

}

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

        int length = ListLength(L);
        LinkList p = L->next;
       
        for (int i=1;i<length;i++)
        {
                if (p->data==e)
                {
                        return i;
                }

                p = p->next;
        }
        return 0;
}

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

                p = p->next;
        }
        return  p;
}



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

        int j = 0;
        LinkList p,q;
        p = L;
        while (j<i-1)
        {
                ++j;
                p = p->next;
        }
        /*if (j>i-1)
        {
                return ERROR;
        }*/
        q = new Node;
        q->data = e;
        q->next = p->next;
        p->next = q;
        return OK;


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

        LinkList p, q;
        p = L;
        int j = 0;
        while (p->next!=L &&j<i-1)
        {
                ++j;
                p = p->next;
        }
        q = p->next;
        e = q->data;
        p->next = q->next;
        delete q;
        return OK;


}

void CreatHead(LinkList &L,int n)
{
        LinkList p;
        L = new Node;
        L->next = L;
        for (int i = 0; i < n; i++)
        {
                p = new Node;
                cin >>p->data;
                p->next = L->next;
                L->next = p;
        }

}

void CreatTail(LinkList &L,int n)
{
        LinkList s, r;
        L = new Node;
        L->next = L;
        r = L;
        for (int i=0;i<n;i++)
        {
                s = new Node;
                cin >> s->data;
                r->next = s;
                r = s;  //r移动到尾节点

        }
        r->next = L;

}

Node * FindeLast(Node*L)
{
        Node *p = L;
        while (p->next!=L)
        {
                p = p->next;
        }
        return p;

}

LinkList Connect(LinkList &La,LinkList &Lb)
{
        LinkList La_last, Lb_last;
        LinkList p;
        La_last = FindeLast(La);
        Lb_last = FindeLast(Lb);
        p = La_last->next;
        La_last->next = Lb_last->next->next;
        delete Lb_last->next;
        Lb_last->next = p;
        return Lb_last->next;

       

}

void MerGerList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
        Node* pa, *pb, *pc;
        pa = La->next;
        pb = Lb->next;
        Lc = pc = La;
       
        LinkList  Lb_last;
        Lb_last = FindeLast(Lb);
       


        while (pa!=La&& pb!=Lb)
        {
                if (pa->data <= pb->data)
                {
                        pc->next = pa;
                        pc = pa;
                        pa = pa->next;
                }
                else
                {
                        pc->next = pb;
                        pc = pb;
                        pb = pb->next;
                }

        }
        if (pa!=La)
        {
                pc->next = pa;

        }
        else
        {
                pc->next = pb;
                Lb_last->next = La;
               
        }

        delete Lb;
       

}



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


int main()
{

        int i;
        int j;
        int k;
        ElemType e;
        LinkList L, 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=";
        ListTravers(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=";
        ListTravers(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 << "元素的地址为" << (int)p << endl;

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

        cout << "删除第一和第二个元素以后,L.data=";
        ListTravers(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;

       
        i= DestroyList(L);
       

        cout << "插入元素La(头插法)" << endl;
        CreatHead(La, 5);
        cout << "整体创建La的元素(头插法)" << endl;
        ListTravers(La);

        cout << "插入元素Lb(尾插法)" << endl;
        CreatTail(Lb, 5);
        cout << "整体创建Lb的元素(尾插法)" << endl;
        ListTravers(Lb);

        L=Connect(La, Lb);
        cout << "Lb合并到La后,L=";
        ListTravers(L);
        cout << "Lb合并到La后,La=";
        ListTravers(La);
       

        i = DestroyList(L);
       
       
       

        cout << "插入元素La(尾插法)" << endl;
        CreatTail(La, 5);
        cout << "整体创建La的元素(尾插法)" << endl;
        ListTravers(La);


        cout << "插入元素Lb(尾插法)" << endl;
        CreatTail(Lb, 5);
        cout << "整体创建Lb的元素(尾插法)" << endl;
        ListTravers(Lb);

       
        MerGerList(La, Lb, L);
        cout << "有序合并La,Lb后,L=";
        ListTravers(L);

       


        return 0;


}
大L,我尝试用DestroyList直接操作底层结构,发现出现了“已在 Project1.exe 中执行断点指令(__debugbreak()语句或类似调用)。”这种问题,原因是什么呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-19 12:42:10 | 显示全部楼层
1094570635 发表于 2022-11-19 00:34
#include
using namespace std;

  1. int main() {

  2.     int i;
  3.     int j;
  4.     int k;
  5.     ElemType e;
  6.     LinkList L, p;
  7.     LinkList La, Lb;
  8.     i = InitList(L);
  9.     cout << "初始化链表(1.成功 0.失败)" << i << endl;

  10.     DestroyList(L);   // DestroyList 函数写在这里,运行的时候没有问题
  11.     return 0;

  12.     for(j = 1; j <= 5; j++) {
  13.         ListInsert(L, 1, j);
  14.     }
  15.     cout << "表头插入5个元素后,L.data=";
  16.     ListTravers(L);

  17.     DestroyList(L);   // DestroyList 函数写在这里,运行的时候就报错了
  18.     return 0;

  19.     i = EmptyList(L);
  20.     cout << "L是否为空(1.是 0.否)" << i << endl;
  21.     // ....
  22. }
复制代码


说明了什么问题?
说明要么是 ListInsert 的问题,要么是 ListTravers 的问题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-20 01:15:18 | 显示全部楼层
人造人 发表于 2022-11-19 12:42
说明了什么问题?
说明要么是 ListInsert 的问题,要么是 ListTravers 的问题

我感觉应该是DestroyList(L),或者是ListInsert的问题
Status DestroyList(LinkList& L)
{
   
   
        /*LinkList p;
        while (L->next != L)
        {
            p = L;
            L = L->next;
            delete p;


        }
        delete L;
        return OK;*/

        ClearList(L);
        delete L;
        L = NULL;
        return OK;

   

}我直接调用ClearList(L),再删除头结点,没问题。
调用了底层
Status DestroyList(LinkList& L)
{
        LinkList p;
        while (L->next != L)
        {
                p = L;
                L = L->next;
                delete p;


        }
        delete L;
        return OK;

       

}
就出错了,就不知道问题在哪.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表