设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 关于双向不循环链表的插入操作问题
返回列表 发新帖
查看: 814|回复: 8

[已解决]关于双向不循环链表的插入操作问题

[复制链接]
1094570635
发表于 2022-11-12 05:53:15 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
#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
一样的，画图，把图画出来代码就会写了
不画图，代码确实不会写
我也是画了图的，画了图我才会写的

1.png

  1. #include <iostream>

  3. using namespace std;

  5. #define TRUE 1
  6. #define FALSE 0
  7. #define OK 1
  8. #define ERROR 0
  9. //#define INFEASIBLE -1
  10. //#define OVERFLOW   -2
  11. #define MAXSIZE 100

  13. typedef int Status;
  14. typedef int ElemType;

  16. typedef struct Node {
  17.     ElemType data;
  18.     struct Node *prior, *next;

  20. } Node, *LinkList;

  22. Status InitList(LinkList *L);
  23. Status DestryList(LinkList L);
  24. Status ListInsert(LinkList L, int i, const ElemType *e);
  25. Status ListDelete(LinkList L, int i, ElemType *e);
  26. Status ClearList(LinkList L);
  27. Status ListEmpty(LinkList L);
  28. int ListLength(LinkList L);
  29. Status GetElem(LinkList L, int i, ElemType *e);
  30. Status SetElem(LinkList L, int i, const ElemType *e);
  31. Status ListTravers(LinkList L);
  32. Status ListAppend(LinkList L, const ElemType *e);

  34. Status InitList(LinkList *L) {
  35.     *L = new Node;
  36.     (*L)->next = NULL;
  37.     (*L)->prior = NULL;
  38.     return OK;
  39. }

  41. Status DestryList(LinkList L) {
  42.     ClearList(L);
  43.     delete L;
  44.     return OK;
  45. }

  47. Status ListInsert(LinkList L, int i, const ElemType *e) {
  48.     if(i > ListLength(L)) return FALSE;
  49.     LinkList p = L;
  50.     while(i--) p = p->next;
  51.     LinkList q = new Node;
  52.     q->data = *e;
  53.     q->next = p->next;
  54.     q->prior = p;
  55.     p->next = q;
  56.     if(q->next) q->next->prior = q;     // 注意这里
  57.     return TRUE;
  58. }

  60. Status ListDelete(LinkList L, int i, ElemType *e) {
  61.     if(i >= ListLength(L)) return FALSE;
  62.     LinkList p = L;
  63.     while(i--) p = p->next;
  64.     LinkList q = p->next;
  65.     p->next = q->next;
  66.     if(q->next) q->next->prior = p;     // 同样，注意这里
  67.     delete q;
  68.     return TRUE;
  69. }

  71. Status ClearList(LinkList L) {
  72.     ElemType e;
  73.     while(!ListEmpty(L)) ListDelete(L, 0, &e);
  74.     return OK;
  75. }

  77. Status ListEmpty(LinkList L) {
  78.     return ListLength(L) == 0;
  79. }

  81. int ListLength(LinkList L) {
  82.     int i = 0;
  83.     LinkList p = L->next;
  84.     while(p) {++i; p = p->next;}
  85.     return i;
  86. }

  88. Status GetElem(LinkList L, int i, ElemType *e) {
  89.     if(i >= ListLength(L)) return FALSE;
  90.     LinkList p = L->next;
  91.     while(i--) p = p->next;
  92.     *e = p->data;
  93.     return TRUE;
  94. }

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

  102. Status visit(ElemType e) {
  103.     cout << e << " ";
  104.     return OK;
  105. }

  107. Status ListTravers(LinkList L) {
  108.     ElemType e;
  109.     int length = ListLength(L);
  110.     for(int i = 0; i < length; i++) {
  111.         GetElem(L, i, &e);
  112.         visit(e);
  113.     }
  114.     cout << endl;
  115.     return OK;
  116. }

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

  122. int main() {
  123.     LinkList L;
  124.     InitList(&L);
  125.     for(ElemType e = 0; e < 10; ++e) {
  126.         ListAppend(L, &e);
  127.     }
  128.     ListTravers(L);
  129.     DestryList(L);
  130.     return 0;
  131. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2022-11-12 09:58:49 | 显示全部楼层    本楼为最佳答案   
一样的，画图，把图画出来代码就会写了
不画图，代码确实不会写
我也是画了图的，画了图我才会写的

1.png

  1. #include <iostream>

  3. using namespace std;

  5. #define TRUE 1
  6. #define FALSE 0
  7. #define OK 1
  8. #define ERROR 0
  9. //#define INFEASIBLE -1
  10. //#define OVERFLOW   -2
  11. #define MAXSIZE 100

  13. typedef int Status;
  14. typedef int ElemType;

  16. typedef struct Node {
  17.     ElemType data;
  18.     struct Node *prior, *next;

  20. } Node, *LinkList;

  22. Status InitList(LinkList *L);
  23. Status DestryList(LinkList L);
  24. Status ListInsert(LinkList L, int i, const ElemType *e);
  25. Status ListDelete(LinkList L, int i, ElemType *e);
  26. Status ClearList(LinkList L);
  27. Status ListEmpty(LinkList L);
  28. int ListLength(LinkList L);
  29. Status GetElem(LinkList L, int i, ElemType *e);
  30. Status SetElem(LinkList L, int i, const ElemType *e);
  31. Status ListTravers(LinkList L);
  32. Status ListAppend(LinkList L, const ElemType *e);

  34. Status InitList(LinkList *L) {
  35.     *L = new Node;
  36.     (*L)->next = NULL;
  37.     (*L)->prior = NULL;
  38.     return OK;
  39. }

  41. Status DestryList(LinkList L) {
  42.     ClearList(L);
  43.     delete L;
  44.     return OK;
  45. }

  47. Status ListInsert(LinkList L, int i, const ElemType *e) {
  48.     if(i > ListLength(L)) return FALSE;
  49.     LinkList p = L;
  50.     while(i--) p = p->next;
  51.     LinkList q = new Node;
  52.     q->data = *e;
  53.     q->next = p->next;
  54.     q->prior = p;
  55.     p->next = q;
  56.     if(q->next) q->next->prior = q;     // 注意这里
  57.     return TRUE;
  58. }

  60. Status ListDelete(LinkList L, int i, ElemType *e) {
  61.     if(i >= ListLength(L)) return FALSE;
  62.     LinkList p = L;
  63.     while(i--) p = p->next;
  64.     LinkList q = p->next;
  65.     p->next = q->next;
  66.     if(q->next) q->next->prior = p;     // 同样，注意这里
  67.     delete q;
  68.     return TRUE;
  69. }

  71. Status ClearList(LinkList L) {
  72.     ElemType e;
  73.     while(!ListEmpty(L)) ListDelete(L, 0, &e);
  74.     return OK;
  75. }

  77. Status ListEmpty(LinkList L) {
  78.     return ListLength(L) == 0;
  79. }

  81. int ListLength(LinkList L) {
  82.     int i = 0;
  83.     LinkList p = L->next;
  84.     while(p) {++i; p = p->next;}
  85.     return i;
  86. }

  88. Status GetElem(LinkList L, int i, ElemType *e) {
  89.     if(i >= ListLength(L)) return FALSE;
  90.     LinkList p = L->next;
  91.     while(i--) p = p->next;
  92.     *e = p->data;
  93.     return TRUE;
  94. }

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

  102. Status visit(ElemType e) {
  103.     cout << e << " ";
  104.     return OK;
  105. }

  107. Status ListTravers(LinkList L) {
  108.     ElemType e;
  109.     int length = ListLength(L);
  110.     for(int i = 0; i < length; i++) {
  111.         GetElem(L, i, &e);
  112.         visit(e);
  113.     }
  114.     cout << endl;
  115.     return OK;
  116. }

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

  122. int main() {
  123.     LinkList L;
  124.     InitList(&L);
  125.     for(ElemType e = 0; e < 10; ++e) {
  126.         ListAppend(L, &e);
  127.     }
  128.     ListTravers(L);
  129.     DestryList(L);
  130.     return 0;
  131. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 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);
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-11-12 10:10:05 | 显示全部楼层
忘记写e了
  1. Status ListDelete(LinkList L, int i, ElemType *e) {
  2.     if(i >= ListLength(L)) return FALSE;
  3.     LinkList p = L;
  4.     while(i--) p = p->next;
  5.     LinkList q = p->next;
  6.     p->next = q->next;
  7.     if(q->next) q->next->prior = p;     // 同样，注意这里
  8.     delete q;
  9.     return TRUE;
  10. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-11-12 10:12:40 | 显示全部楼层
那就不写e了，写什么e ？
删除的时候还要什么e ？
想要e的话，自己调用 GetElem 获取去

  1. #include <iostream>

  3. using namespace std;

  5. #define TRUE 1
  6. #define FALSE 0
  7. #define OK 1
  8. #define ERROR 0
  9. //#define INFEASIBLE -1
  10. //#define OVERFLOW   -2
  11. #define MAXSIZE 100

  13. typedef int Status;
  14. typedef int ElemType;

  16. typedef struct Node {
  17.     ElemType data;
  18.     struct Node *prior, *next;

  20. } Node, *LinkList;

  22. Status InitList(LinkList *L);
  23. Status DestryList(LinkList L);
  24. Status ListInsert(LinkList L, int i, const ElemType *e);
  25. Status ListDelete(LinkList L, int i);
  26. Status ClearList(LinkList L);
  27. Status ListEmpty(LinkList L);
  28. int ListLength(LinkList L);
  29. Status GetElem(LinkList L, int i, ElemType *e);
  30. Status SetElem(LinkList L, int i, const ElemType *e);
  31. Status ListTravers(LinkList L);
  32. Status ListAppend(LinkList L, const ElemType *e);

  34. Status InitList(LinkList *L) {
  35.     *L = new Node;
  36.     (*L)->next = NULL;
  37.     (*L)->prior = NULL;
  38.     return OK;
  39. }

  41. Status DestryList(LinkList L) {
  42.     ClearList(L);
  43.     delete L;
  44.     return OK;
  45. }

  47. Status ListInsert(LinkList L, int i, const ElemType *e) {
  48.     if(i > ListLength(L)) return FALSE;
  49.     LinkList p = L;
  50.     while(i--) p = p->next;
  51.     LinkList q = new Node;
  52.     q->data = *e;
  53.     q->next = p->next;
  54.     q->prior = p;
  55.     p->next = q;
  56.     if(q->next) q->next->prior = q;     // 注意这里
  57.     return TRUE;
  58. }

  60. Status ListDelete(LinkList L, int i) {
  61.     if(i >= ListLength(L)) return FALSE;
  62.     LinkList p = L;
  63.     while(i--) p = p->next;
  64.     LinkList q = p->next;
  65.     p->next = q->next;
  66.     if(q->next) q->next->prior = p;     // 同样，注意这里
  67.     delete q;
  68.     return TRUE;
  69. }

  71. Status ClearList(LinkList L) {
  72.     while(!ListEmpty(L)) ListDelete(L, 0);
  73.     return OK;
  74. }

  76. Status ListEmpty(LinkList L) {
  77.     return ListLength(L) == 0;
  78. }

  80. int ListLength(LinkList L) {
  81.     int i = 0;
  82.     LinkList p = L->next;
  83.     while(p) {++i; p = p->next;}
  84.     return i;
  85. }

  87. Status GetElem(LinkList L, int i, ElemType *e) {
  88.     if(i >= ListLength(L)) return FALSE;
  89.     LinkList p = L->next;
  90.     while(i--) p = p->next;
  91.     *e = p->data;
  92.     return TRUE;
  93. }

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

  100. Status visit(ElemType e) {
  101.     cout << e << " ";
  102.     return OK;
  103. }

  105. Status ListTravers(LinkList L) {
  106.     ElemType e;
  107.     int length = ListLength(L);
  108.     for(int i = 0; i < length; i++) {
  109.         GetElem(L, i, &e);
  110.         visit(e);
  111.     }
  112.     cout << endl;
  113.     return OK;
  114. }

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

  120. int main() {
  121.     LinkList L;
  122.     InitList(&L);
  123.     for(ElemType e = 0; e < 10; ++e) {
  124.         ListAppend(L, &e);
  125.     }
  126.     ListTravers(L);
  127.     DestryList(L);
  128.     return 0;
  129. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-11-12 10:14:03 | 显示全部楼层
接口尽量保持简单，功能单一
不提供没有用的功能
删除的时候要什么 e ？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-11-12 10:18:44 | 显示全部楼层
人造人 发表于 2022-11-12 10:10
忘记写e了

'''
忘记写e了
  1. Status ListDelete(LinkList L, int i, ElemType *e) {
  2.     if(i >= ListLength(L)) return FALSE;
  3.     LinkList p = L;
  4.     while(i--) p = p->next;
  5.     LinkList q = p->next;
  6.     p->next = q->next;
  7.     if(q->next) q->next->prior = p;     // 同样，注意这里
  8.     delete q;
  9.     return TRUE;
  10. }
复制代码

'''

尽量避免直接操作底层结构，因为是真的非常容易出错
这是我一直强调的东西
像这里我就忘了写e了
不过这个函数无法避免直接操作底层结构
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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指针指向插入位置的前驱和后继问题，思路不够清晰.


想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

  1. Status ListInsert(LinkList L, int i, const ElemType *e) {
  2.     if(i > ListLength(L)) return FALSE;
  3.     LinkList p = L;
  4.     while(i--) p = p->next;
  5.     LinkList q = new Node;
  6.     q->data = *e;
  7.     q->next = p->next;
  8.     if(q->next) q->next->prior = q;
  9.     q->prior = p;
  10.     p->next = q;
  11.     return TRUE;
  12. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-4-25 17:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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