论坛 › 数据结构与算法 › 关于双向不循环链表的插入操作问题

1094570635 发表于 2022-11-12 05:53:15

关于双向不循环链表的插入操作问题

#include <iostream>
using namespace std;


#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
//#define INFEASIBLE -1
//#define OVERFLOW   -2
#define MAXSIZE    100

typedef int Status;
typedef int ElemType;

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

}Node,*LinkList;


Status visit(ElemType e);
Status InitList(LinkList* L);
Status ListEmpty(LinkList L);
Status DestryList(LinkList* L);
Status ClearList(LinkList* L);
Status ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType* e);
int LocateElem(LinkList L, ElemType e);
Node* LocateElem2(LinkList L, ElemType e);

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


Status InitList(LinkList *L)
{
        *L = new Node;
        (*L)->next =NULL;
        (*L)->prior =NULL;
        return OK;
}

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

}


Status DestryList(LinkList* L)
{
        /*LinkList p;
        while ((*L))
        {
                p = (*L);
                (*L) = (*L)->next;
                delete p;
        }
        delete (*L);
        return OK;*/

        ClearList(L);
        delete* L;
        return OK;


}


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

        }
        (*L)->next = NULL;
        return OK;
}

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

}

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


        LinkList p=L->next ;
        int length = ListLength(L);
        if (i<1||i>length)
        {
                return ERROR;
        }

        for (int j=1;j<i;j++)
        {
                p = p->next;
        }
        *e = p->data;
        return OK;

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

        }
        return 0;

}

Node* LocateElem2(LinkList L, ElemType e)
{
        LinkList p = L->next;
        while (p)
        {
                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||length==MAXSIZE)
        {
                return ERROR;
        }
       
        LinkList p, s;
        p = (*L);
        int j = 0;
        while (p &&j<i)
        {
                p = p->next;
        }
       
       
        s = new Node;
        s->data = e;
        s->prior = p->prior;
        p->prior->next = s;
        s->next = p;
        p->prior = s;

        return OK;
       
}

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 j;
        LinkList L;
        InitList(&L);

        cout << ListLength(L) << endl;
        for (j=1;j<=10;j++)
        {
                ListInsert(&L, 1, j);
        }
        ListTravers(L);
       

        return 0;
}

Status ListInsert(LinkList *L ,int i,ElemType e)，没有输出元素,一直在考虑如果是空表的话，插入方式是不是要更改.

人造人 发表于 2022-11-12 09:58:49

一样的，画图，把图画出来代码就会写了
不画图，代码确实不会写
我也是画了图的，画了图我才会写的



#include <iostream>

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
//#define INFEASIBLE -1
//#define OVERFLOW   -2
#define MAXSIZE 100

typedef int Status;
typedef int ElemType;

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

} Node, *LinkList;

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

Status InitList(LinkList *L) {
    *L = new Node;
    (*L)->next = NULL;
    (*L)->prior = NULL;
    return OK;
}

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

Status ListInsert(LinkList L, int i, const ElemType *e) {
    if(i > ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = new Node;
    q->data = *e;
    q->next = p->next;
    q->prior = p;
    p->next = q;
    if(q->next) q->next->prior = q;   // 注意这里
    return TRUE;
}

Status ListDelete(LinkList L, int i, ElemType *e) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = p->next;
    p->next = q->next;
    if(q->next) q->next->prior = p;   // 同样，注意这里
    delete q;
    return TRUE;
}

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

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

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

Status GetElem(LinkList L, int i, ElemType *e) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L->next;
    while(i--) 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;
}

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

Status ListTravers(LinkList L) {
    ElemType e;
    int length = ListLength(L);
    for(int i = 0; i < length; i++) {
      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 e = 0; e < 10; ++e) {
      ListAppend(L, &e);
    }
    ListTravers(L);
    DestryList(L);
    return 0;
}

人造人 发表于 2022-11-12 10:04:26

Status InitList(LinkList* L);
Status ListEmpty(LinkList L);
Status ClearList(LinkList* L);
Status GetElem(LinkList L, int i, ElemType* e);
int LocateElem(LinkList L, ElemType e);

写代码，接口要统一，不要一会有 * 了，一会又没 * 了，一会又有了
你函数调用的时候都不知道要不要取地址了，要不要解引用了
LocateElem(L, &e);
GetElem(L, *e);

人造人 发表于 2022-11-12 10:10:05

忘记写e了
Status ListDelete(LinkList L, int i, ElemType *e) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = p->next;
    p->next = q->next;
    if(q->next) q->next->prior = p;   // 同样，注意这里
    delete q;
    return TRUE;
}

人造人 发表于 2022-11-12 10:12:40

那就不写e了，写什么e ？
删除的时候还要什么e ？
想要e的话，自己调用 GetElem 获取去

#include <iostream>

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
//#define INFEASIBLE -1
//#define OVERFLOW   -2
#define MAXSIZE 100

typedef int Status;
typedef int ElemType;

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

} Node, *LinkList;

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

Status InitList(LinkList *L) {
    *L = new Node;
    (*L)->next = NULL;
    (*L)->prior = NULL;
    return OK;
}

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

Status ListInsert(LinkList L, int i, const ElemType *e) {
    if(i > ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = new Node;
    q->data = *e;
    q->next = p->next;
    q->prior = p;
    p->next = q;
    if(q->next) q->next->prior = q;   // 注意这里
    return TRUE;
}

Status ListDelete(LinkList L, int i) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = p->next;
    p->next = q->next;
    if(q->next) q->next->prior = p;   // 同样，注意这里
    delete q;
    return TRUE;
}

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

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

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

Status GetElem(LinkList L, int i, ElemType *e) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L->next;
    while(i--) p = p->next;
    *e = p->data;
    return TRUE;
}

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

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

Status ListTravers(LinkList L) {
    ElemType e;
    int length = ListLength(L);
    for(int i = 0; i < length; i++) {
      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 e = 0; e < 10; ++e) {
      ListAppend(L, &e);
    }
    ListTravers(L);
    DestryList(L);
    return 0;
}

人造人 发表于 2022-11-12 10:14:03

接口尽量保持简单，功能单一
不提供没有用的功能
删除的时候要什么 e ？

人造人 发表于 2022-11-12 10:18:44

人造人 发表于 2022-11-12 10:10
忘记写e了

'''
忘记写e了
Status ListDelete(LinkList L, int i, ElemType *e) {
    if(i >= ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = p->next;
    p->next = q->next;
    if(q->next) q->next->prior = p;   // 同样，注意这里
    delete q;
    return TRUE;
}
'''

尽量避免直接操作底层结构，因为是真的非常容易出错
这是我一直强调的东西
像这里我就忘了写e了
不过这个函数无法避免直接操作底层结构

1094570635 发表于 2022-11-12 18:18:54

人造人 发表于 2022-11-12 10:18
'''
忘记写e了



插入操作，① q->next = p->next;
    ②q->prior = p;
    ③p->next = q;
④ if(q->next) q->next->prior = q;
可以先完成①④再完成②③么，感觉只要不是先把p->next接到q的前面，赋值操作应该都可以的
之前一直纠结于p指针指向插入位置的前驱和后继问题，思路不够清晰.

人造人 发表于 2022-11-12 18:48:29

1094570635 发表于 2022-11-12 18:18
插入操作，① q->next = p->next;
    ②q->prior = p;
    ③p->next = q;


所以画图是关键，画了图就会写了
可以先 1 4 后 2 3

Status ListInsert(LinkList L, int i, const ElemType *e) {
    if(i > ListLength(L)) return FALSE;
    LinkList p = L;
    while(i--) p = p->next;
    LinkList q = new Node;
    q->data = *e;
    q->next = p->next;
    if(q->next) q->next->prior = q;
    q->prior = p;
    p->next = q;
    return TRUE;
}

查看完整版本: 关于双向不循环链表的插入操作问题