[已解决]线性表合并头尾结点指向同一地址陷入死循环

homeskating

/*
结构体
*/
using namespace std;
#define ElemType int
#define Status int
constexpr auto SUCCESS = 1;
constexpr auto ERROR = -1;
typedef struct LNode {
        ElemType data;
        struct LNode* next;
}*Link, * Position;
typedef struct {
        Link head, tail;
        int len;
}LinkList;
/*
初始化一个已经声明链表L
*/
Status InitList(LinkList& L) {
        L.head = new LNode;
        L.head->next = nullptr;
        L.tail = L.head;
        L.len = 0;
        if (L.head)
        {
                cout << "初始化成功" << endl;
                return SUCCESS;
        }
        return ERROR;
}
/*
返回链表当中头结点的位置
*/
Position GetHead(LinkList L) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        return L.head;
}
/*
由当前p指向的位置，查找p的下一个邻接元素的位置
*/
Position NextPos(LinkList L, Link p) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        if (p == L.tail)
        {
                return nullptr;
        }
        return p->next;
}
/*
获取当前指针p指向的元素的数据域的值，以e返回
*/
ElemType GetCurElem(Link p) {
        return p->data;
}
/*
将头结点删除
*/
Status DelFirst(Link h, Link& q) {
        q = h->next;
        if (q)
        {
                h->next = q->next;
                return SUCCESS;
        }
        else
        {
                return ERROR;
        }
}
/*
向链表内插入数据，s以后得一个或若干个结点
插入链表的尾部
*/
Status Append(LinkList& L, Link s) {
        //修改链表的tail指针
        L.tail->next = s;
        while (L.tail->next != nullptr)
        {
                L.len++;
                L.tail = L.tail->next;
        }
        return SUCCESS;
}
/*
由当前p指向的位置，查找p的下一个邻接元素的位置
*/
Position NextPos(LinkList L, Link p) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        if (p == L.tail)
        {
                return nullptr;
        }
        return p->next;
}
/*
释放p指向的结点
*/
void FreeNode(Link& p) {
        delete p;
        p = nullptr;
}
/*
归并La和Lb得到新的单链线性表Lc，
Lc的元素也按值非递减排列
*/
Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc,
        int (*compare)(ElemType, ElemType)) {
        if (!InitList(Lc))
        {
                return ERROR;
        }
        Link ha = nullptr, hb = nullptr, pa = nullptr,
                pb = nullptr, q = nullptr;
        ha = GetHead(La);
        hb = GetHead(Lb);
        pa = NextPos(La, ha);
        pb = NextPos(Lb, hb);
        ElemType a = 0, b = 0;
        while (pa && pb)
        {
                a = GetCurElem(pa);
                b = GetCurElem(pb);
                if ((*compare)(a, b) <= 0)
                {
                        DelFirst(ha, q);
                        Append(Lc, q);
                        pa = NextPos(La, ha);
                }
                else
                {
                        DelFirst(hb, q);
                        Append(Lc, q);
                        pb = NextPos(Lb, hb);
                }
        }
        if (pa)
        {
                Append(Lc, pa);
        }
        else {
                Append(Lc, pb);
        }
        FreeNode(ha);
        FreeNode(hb);
        return SUCCESS;
}
/*
主函数
*/
int main(void) {
        LinkList list = {}, list2 = {}, list3;
        Link link = nullptr, p = nullptr;
        InitList(list);
        InitList(list2);
        cout << "插入成功状态为" << (ListInsert_L(list, 1, 100)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list, 2, 200)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list, 3, 300)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 1, 400)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 2, 500)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 3, 600)) << endl;
        cout << "头结点位置为：" << (GetHead(list)) << endl;
        cout << "头结点2位置为：" << (GetHead(list2)) << endl;
        cout << "线性表长度为:" << (ListLength(list)) << endl;
        ListTraverse(list, visit);
        cout << endl;
        ListTraverse(list2, visit);
        cout << endl;
        cout << "索引为：" << (LocateElem(list, 200, compare)) << endl;
        LocatePos(list, 1, p);
        cout << "p=" << p << endl;
        MergeList_L(list, list2, list3, compare2);
        ListTraverse(list3, visit);
}

最佳答案

月排行榜 / 总排行榜

jhq999

2023-3-13 22:59:10

homeskating 发表于 2023-3-13 23:04
补一下代码

你的注释习惯太好了，bug很容易找出来

Status DelFirst(Link h, Link& q) {
        q = h->next;
        if (q)
        {
                h->next = q->next;
                q->next=nullptr;////////////////////////
                return SUCCESS;
        }
        else
        {
                return ERROR;
        }

}

跳转到最佳答案楼层

jhq999

homeskating 发表于 2023-3-13 23:04
补一下代码

你的注释习惯太好了，bug很容易找出来

Status DelFirst(Link h, Link& q) {
        q = h->next;
        if (q)
        {
                h->next = q->next;
                q->next=nullptr;////////////////////////
                return SUCCESS;
        }
        else
        {
                return ERROR;
        }

}

homeskating

补一下代码

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define ElemType int
#define Status int
constexpr auto SUCCESS = 1;
constexpr auto ERROR = -1;
typedef struct LNode {
        ElemType data;
        struct LNode* next;
}*Link, * Position;
typedef struct {
        Link head, tail;
        int len;
}LinkList;
/*
分配一个p指向的值为e的结点，
并返回SUCCESS，如果分配失败，则
ERROR
*/
Status MakeNode(Link& p, ElemType e) {
        p = new LNode;
        p->data = e;
        if (p)
        {
                return SUCCESS;
        }
        else {
                return ERROR;
        }
}
/*
释放p指向的结点
*/
void FreeNode(Link& p) {
        delete p;
        p = nullptr;
}
/*
初始化一个已经声明链表L
*/
Status InitList(LinkList& L) {
        L.head = new LNode;
        L.head->next = nullptr;
        L.tail = L.head;
        L.len = 0;
        if (L.head)
        {
                cout << "初始化成功" << endl;
                return SUCCESS;
        }
        return ERROR;
}
/*
将当前链表L清空，变成一个初始状态的链表
*/
Status ClearList(LinkList& L) {
        Link p = L.head->next;
        while (p)
        {
                L.head->next = p->next;
                delete p;
                p = nullptr;
                L.len--;
                p = L.head->next;
        }
        if (L.head->next == nullptr)
        {
                return SUCCESS;
        }
        else {
                return ERROR;
        }
}
/*
销毁一个链表L
*/
Status DestroyList(LinkList& L) {
        ClearList(L);
        delete L.head;
        L.head = nullptr;
        L.tail = nullptr;
        if (!L.head)
        {
                return ERROR;
        }
        return SUCCESS;
}
/*
在头结点位置插入一个新的结点，
h指向头，s指向新的结点
*/
Status InsFirst(Link h, Link s) {
        s->next = h->next;
        h->next = s;
        return SUCCESS;
}
/*
将头结点删除
*/
Status DelFirst(Link h, Link& q) {
        q = h->next;
        if (q)
        {
                h->next = q->next;
                return SUCCESS;
        }
        else
        {
                return ERROR;
        }
}
/*
向链表内插入数据，s以后得一个或若干个结点
插入链表的尾部
*/
Status Append(LinkList& L, Link s) {
        //修改链表的tail指针
        L.tail->next = s;
        while (L.tail->next != nullptr)
        {
                L.len++;
                L.tail = L.tail->next;
        }
        return SUCCESS;
}
/*
删除链表尾结点元素，由q返回
*/
Status Remove(LinkList& L, Link& q) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return ERROR;
        }
        q = L.head;
        while (q->next != L.tail)
        {
                q = q->next;
        }
        L.tail = q;
        q = q->next;
        L.tail->next = nullptr;
        L.len--;
        delete q;
        q = nullptr;
        return SUCCESS;
}
/*
将元素插入由p指定的位置的前一个位置，
并修改p指向新的结点
*/
Status InsBefore(LinkList& L, Link& p, Link s) {
        Link q = L.head;
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return ERROR;
        }
        while (q->next != p)
        {
                q = q->next;
        }
        q->next = s;
        s->next = p;
        p = s;
        L.len++;
        return SUCCESS;
}
/*
将元素插入由p指定位置的下一个位置，
并修改p指向新结点
*/
Status InsAfter(LinkList& L, Link& p, Link s) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return ERROR;
        }
        s->next = p->next;
        p->next = s;
        if (p == L.tail)
        {
                L.tail = L.tail->next;
        }
        p = s;
        L.len++;
        return SUCCESS;
}
/*
修改当前指针p指向的元素的数据域的值为e
*/
Status SetCurElem(Link& p, ElemType e) {
        p->data = e;
        return SUCCESS;
}
/*
获取当前指针p指向的元素的数据域的值，以e返回
*/
ElemType GetCurElem(Link p) {
        return p->data;
}
/*
将线性表清空
*/
Status ListEmpty(LinkList L) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return 0;
        }
        if (L.head->next == nullptr)
        {
                return SUCCESS;
        }
        else
        {
                return ERROR;
        }
}
/*
获取线性表长度
*/
int ListLength(LinkList L) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return ERROR;
        }
        return L.len;
}
/*
返回链表当中头结点的位置
*/
Position GetHead(LinkList L) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        return L.head;
}
/*
返回链表当中最后一个结点的位置
*/
Position GetLast(LinkList L) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        return L.tail;
}
/*
由当前p指向的位置，查找p的邻接前一个结点位置
*/
Position PriorPos(LinkList L, Link p) {
        Link q = L.head;
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        if (p == L.head)
        {
                return nullptr;
        }
        while (q->next != p)
        {
                q = q->next;
        }
        return q;
}
/*
由当前p指向的位置，查找p的下一个邻接元素的位置
*/
Position NextPos(LinkList L, Link p) {
        if (!L.head)
        {
                cout << "线性链表不存在" << endl;
                return nullptr;
        }
        if (p == L.tail)
        {
                return nullptr;
        }
        return p->next;
}
/*
返回p指示线性链表L中第i个结点的位置并返回SUCCESS,
i值不合法则返回ERROR
*/
Status LocatePos(LinkList L, int i, Link& p) {
        int j = 0;
        Link pt = L.head;
        while (pt && j < i)
        {
                pt = pt->next;
                j++;
        }
        if (!pt || j > i)
        {
                return ERROR;
        }
        else
        {
                p = pt;
                return SUCCESS;
        }
}
Status compare(ElemType x, ElemType y) {
        if (x == y)
        {
                return SUCCESS;
        }
        else {
                return ERROR;
        }
}
Status compare2(ElemType x, ElemType y) {
        return x - y;
}
/*
返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置
*/
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
        Link q = L.head->next;
        int count = 1;
        while (q != nullptr)
        {
                if (compare(q->data, e) == SUCCESS) {
                        return count;
                }
                q = q->next;
                count++;
        }
        return ERROR;
}
Status visit(ElemType x) {
        cout << x << " ";
        return SUCCESS;
}
/*
依次对L的每个元素调用函数visit(),
一但visit()失败，则操作失败
*/
Status ListTraverse(LinkList L, Status(*visit)(ElemType)) {
        Link q = L.head->next;
        while (q)
        {
                if (visit(q->data)) {
                        q = q->next;
                }
                else
                {
                        return ERROR;
                }
        }
        return SUCCESS;
}
/*
在带头结点的单链线性表L的第i个元素
之前插入元素e
*/
Status ListInsert_L(LinkList& L, int i, ElemType e) {
        Link h = nullptr, s = nullptr;
        if (!LocatePos(L, i - 1, h))
        {
                return ERROR;
        }
        if (!MakeNode(s, e))
        {
                return ERROR;
        }
        int inFirstResult = InsFirst(h, s);
        cout << (inFirstResult == SUCCESS ? "插入新结点成功" : "插入新结点失败") << endl;
        Append(L, s);
        return SUCCESS;
}
/*
归并La和Lb得到新的单链线性表Lc，
Lc的元素也按值非递减排列
*/
Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc,
        int (*compare)(ElemType, ElemType)) {
        if (!InitList(Lc))
        {
                return ERROR;
        }
        Link ha = nullptr, hb = nullptr, pa = nullptr,
                pb = nullptr, q = nullptr;
        ha = GetHead(La);
        hb = GetHead(Lb);
        pa = NextPos(La, ha);
        pb = NextPos(Lb, hb);
        ElemType a = 0, b = 0;
        while (pa && pb)
        {
                a = GetCurElem(pa);
                b = GetCurElem(pb);
                if ((*compare)(a, b) <= 0)
                {
                        DelFirst(ha, q);
                        Append(Lc, q);
                        pa = NextPos(La, ha);
                }
                else
                {
                        DelFirst(hb, q);
                        Append(Lc, q);
                        pb = NextPos(Lb, hb);
                }
        }
        if (pa)
        {
                Append(Lc, pa);
        }
        else {
                Append(Lc, pb);
        }
        FreeNode(ha);
        FreeNode(hb);
        return SUCCESS;
}
int main(void) {
        LinkList list = {}, list2 = {}, list3;
        Link link = nullptr, p = nullptr;
        InitList(list);
        InitList(list2);
        int makeNodeResult = MakeNode(link, 100);
        cout << (makeNodeResult == SUCCESS ? "成功分配结点" : "分配结点失败") << endl;
        cout << "插入成功状态为" << (ListInsert_L(list, 1, 100)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list, 2, 200)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list, 3, 300)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 1, 400)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 2, 500)) << endl;
        cout << "插入成功状态为" << (ListInsert_L(list2, 3, 600)) << endl;
        cout << "头结点位置为：" << (GetHead(list)) << endl;
        cout << "头结点2位置为：" << (GetHead(list2)) << endl;
        cout << "线性表长度为:" << (ListLength(list)) << endl;
        ListTraverse(list, visit);
        cout << endl;
        ListTraverse(list2, visit);
        cout << endl;
        cout << "索引为：" << (LocateElem(list, 200, compare)) << endl;
        LocatePos(list, 1, p);
        cout << "p=" << p << endl;
        MergeList_L(list, list2, list3, compare2);
        ListTraverse(list3, visit);
}