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

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 头插法创建链表实现插入操作结果不对，尾插法确是对的
返回列表 发新帖
查看: 827|回复: 1

[已解决]头插法创建链表实现插入操作结果不对，尾插法确是对的

[复制链接]
ZXPoo
发表于 2022-11-13 19:03:29 | 显示全部楼层 |阅读模式

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

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

x
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef int status;

typedef struct DouLnode
{
        ElemType data;
        struct DouLnode* next;
        struct DouLnode* prior;
}DouLnode,*DouLinklist;

void InitDL(DouLinklist* L);                        //初始化双向链表
void hCreateDL(DouLinklist L, int length);                //头插法创建
void tCreateDL(DouLinklist L, int length);                //尾插发创建
status insertDL(DouLinklist L, int position, ElemType e);                        //插入       
status deleteDL(DouLinklist L, int position, ElemType* e);                //删除

void InitDL(DouLinklist* L)
{
        *L = (DouLinklist)malloc(sizeof(DouLnode));
        (*L)->next = NULL;
        (*L)->prior = NULL;
}

void hCreateDL(DouLinklist L, int length)
{
        printf("请输入%d个数据： \n", length);
        for (int i = 0; i < length; i++)
        {
                DouLinklist p = (DouLinklist)malloc(sizeof(DouLnode));
                ElemType data;
                scanf("%d", &data);
                p->data = data;
                p->next = L->next;
                p->prior = L;
                L->next = p;
        }
}

void tCreateDL(DouLinklist L, int length)
{
        DouLinklist ptail = L;
        printf("请输入%d个数据： \n", length);
        for (int i = 0; i < length; i++)
        {
                DouLinklist p = (DouLinklist)malloc(sizeof(DouLnode));
                ElemType data;
                scanf("%d", &data);
                p->data = data;
                p->next = NULL;
                p->prior = ptail;
                ptail->next = p;
                ptail = p;
        }
}

status insertDL(DouLinklist L, int position, ElemType e)
{
        DouLinklist s = (DouLinklist)malloc(sizeof(DouLnode));
        s->data = e;
        DouLinklist p = L;
        int i = 0;
        while (p && i < position)
        {
                p = p->next;
                i++;
        }
        s->prior = p->prior;
        p->prior->next = s;
        s->next = p;
        p->prior = s;
}

status deleteDL(DouLinklist L, int position, ElemType* e)
{
        DouLinklist p = L;
        int i = 0;
        while (p && i < position)
        {
                p = p->next;
                i++;
        }
        *e = p->data;
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
}

void traverseDL(DouLinklist L)
{
        DouLinklist p = L->next;
        while (p)
        {
                printf("%4d", p->data);
                p = p->next;
        }
        printf("\n");
}

int main()
{
        DouLinklist L;
        InitDL(&L);
        //tCreateDL(L, 5);
        hCreateDL(L, 6);
        traverseDL(L);
        insertDL(L, 2, 9);
        traverseDL(L);
        ElemType a;
        deleteDL(L, 1, &a);
        traverseDL(L);

        return 0;
}

创建链表：1 2 3 4 5 6
遍历后打印出来是：6 5 4 3 2 1
插入后成了：9 5 4 3 2 1
最佳答案
月排行榜 / 总排行榜
jackz007
2022-11-14 02:46:59
本帖最后由 jackz007 于 2022-11-14 12:09 编辑
  1. #define _CRT_SECURE_NO_WARNINGS

  3. #include<stdio.h>
  4. #include<stdlib.h>

  6. typedef int ElemType           ;
  7. typedef int status             ;

  9. typedef struct DouLnode
  10. {
  11.         ElemType data          ;
  12.         struct DouLnode* next  ;
  13.         struct DouLnode* prior ;
  14. }DouLnode , * DouLinklist      ;

  16. void hCreateDL(DouLinklist * L , int length)
  17. {
  18.         DouLinklist p1 , p2                                      ;
  19.         int i                                                    ;
  20.         printf("请输入%d个数据： \n", length)                    ;
  21.         for(i = 0 , p2 = NULL ; i < length ; i ++)
  22.         {
  23.                 p1 = (DouLinklist) malloc(sizeof(DouLnode))      ;
  24.                 ElemType data                                    ;
  25.                 scanf("%d", & data)                              ;
  26.                 p1 -> data = data                                ;
  27.                 p1 -> prior = NULL                               ;
  28.                 if(! p2) {
  29.                         p1 -> next = NULL                        ;
  30.                 } else {                              
  31.                         p1 -> next = p2                          ;
  32.                         p1 -> next -> prior = p1                 ;
  33.                 }
  34.                 p2 = p1                                          ;
  35.                 * L = p2                                         ;
  36.         }
  37. }

  39. void tCreateDL(DouLinklist * L, int length)
  40. {
  41.         DouLinklist p1 , p2                                      ;
  42.         int i                                                    ;
  43.         printf("请输入%d个数据： \n", length)                    ;
  44.         for (i = 0 , p2 = NULL ; i < length ; i ++)
  45.         {
  46.                 p1 = (DouLinklist) malloc(sizeof(DouLnode))      ;
  47.                 ElemType data                                    ;
  48.                 scanf("%d", & data)                              ;
  49.                 p1 -> data = data                                ;
  50.                 p1 -> next = NULL                                ;
  51.                 if(! p2) {
  52.                         p1 -> prior = NULL                       ;
  53.                         * L = p1                                 ;
  54.                 } else {
  55.                         p1 -> prior = p2                         ;
  56.                         p1 -> prior -> next = p1                 ;
  57.                 }
  58.                 p2 = p1                                          ;
  59.         }
  60. }

  62. status insertDL(DouLinklist * L , int position , ElemType e)
  63. {
  64.         int i                                                    ;
  65.         DouLinklist s = (DouLinklist) malloc(sizeof(DouLnode))   ;
  66.         s -> data = e                                            ;
  67.         DouLinklist p                                            ;
  68.         for(p = * L , i = 0 ; i < position ; i ++) p = p -> next ;
  69.         s -> next = p                                            ;
  70.         s -> prior = p -> prior                                  ;
  71.         s -> prior -> next = s                                   ;
  72.         if(p == * L) * L = s                                     ;
  73. }

  75. status deleteDL(DouLinklist * L, int position, ElemType * e)
  76. {
  77.         DouLinklist p                                            ;
  78.         int i                                                    ;
  79.         for(p = * L , i = 0 ; i < position ; i ++) p = p -> next ;
  80.         p -> prior -> next = p -> next                           ;
  81.         p -> next -> prior = p -> prior                          ;
  82.         * e = p -> data                                          ;
  83.         if(* L == p) * L = p -> next                             ;  
  84.         free(p)                                                  ;
  85. }

  87. void traverseDL(DouLinklist L)
  88. {
  89.         DouLinklist p                                            ;
  90.         for(p = L ; p ; p = p -> next) printf("%4d", p -> data)  ;
  91.         printf("\n")                                             ;
  92. }

  94. int main()
  95. {
  96.         DouLinklist L = NULL    ;
  97.         hCreateDL(& L , 6)      ;
  98.         traverseDL(L)           ;
  99.         insertDL(& L , 2 , 9)   ;
  100.         traverseDL(L)           ;
  101.         ElemType a              ;
  102.         deleteDL(& L , 1 , & a) ;
  103.         traverseDL(L)           ;
  104.         return 0                ;
  105. }
复制代码

        编译运行实况：
  1. D:\[00.Exerciese.2022]\C>g++ -o x x.c

  3. D:\[00.Exerciese.2022]\C>x
  4. 请输入6个数据：
  5. 1 2 3 4 5 6
  6.    6   5   4   3   2   1
  7.    6   5   9   4   3   2   1
  8.    6   9   4   3   2   1

  10. D:\[00.Exerciese.2022]\C>
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

jackz007
发表于 2022-11-14 02:46:59 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jackz007 于 2022-11-14 12:09 编辑
  1. #define _CRT_SECURE_NO_WARNINGS

  3. #include<stdio.h>
  4. #include<stdlib.h>

  6. typedef int ElemType           ;
  7. typedef int status             ;

  9. typedef struct DouLnode
  10. {
  11.         ElemType data          ;
  12.         struct DouLnode* next  ;
  13.         struct DouLnode* prior ;
  14. }DouLnode , * DouLinklist      ;

  16. void hCreateDL(DouLinklist * L , int length)
  17. {
  18.         DouLinklist p1 , p2                                      ;
  19.         int i                                                    ;
  20.         printf("请输入%d个数据： \n", length)                    ;
  21.         for(i = 0 , p2 = NULL ; i < length ; i ++)
  22.         {
  23.                 p1 = (DouLinklist) malloc(sizeof(DouLnode))      ;
  24.                 ElemType data                                    ;
  25.                 scanf("%d", & data)                              ;
  26.                 p1 -> data = data                                ;
  27.                 p1 -> prior = NULL                               ;
  28.                 if(! p2) {
  29.                         p1 -> next = NULL                        ;
  30.                 } else {                              
  31.                         p1 -> next = p2                          ;
  32.                         p1 -> next -> prior = p1                 ;
  33.                 }
  34.                 p2 = p1                                          ;
  35.                 * L = p2                                         ;
  36.         }
  37. }

  39. void tCreateDL(DouLinklist * L, int length)
  40. {
  41.         DouLinklist p1 , p2                                      ;
  42.         int i                                                    ;
  43.         printf("请输入%d个数据： \n", length)                    ;
  44.         for (i = 0 , p2 = NULL ; i < length ; i ++)
  45.         {
  46.                 p1 = (DouLinklist) malloc(sizeof(DouLnode))      ;
  47.                 ElemType data                                    ;
  48.                 scanf("%d", & data)                              ;
  49.                 p1 -> data = data                                ;
  50.                 p1 -> next = NULL                                ;
  51.                 if(! p2) {
  52.                         p1 -> prior = NULL                       ;
  53.                         * L = p1                                 ;
  54.                 } else {
  55.                         p1 -> prior = p2                         ;
  56.                         p1 -> prior -> next = p1                 ;
  57.                 }
  58.                 p2 = p1                                          ;
  59.         }
  60. }

  62. status insertDL(DouLinklist * L , int position , ElemType e)
  63. {
  64.         int i                                                    ;
  65.         DouLinklist s = (DouLinklist) malloc(sizeof(DouLnode))   ;
  66.         s -> data = e                                            ;
  67.         DouLinklist p                                            ;
  68.         for(p = * L , i = 0 ; i < position ; i ++) p = p -> next ;
  69.         s -> next = p                                            ;
  70.         s -> prior = p -> prior                                  ;
  71.         s -> prior -> next = s                                   ;
  72.         if(p == * L) * L = s                                     ;
  73. }

  75. status deleteDL(DouLinklist * L, int position, ElemType * e)
  76. {
  77.         DouLinklist p                                            ;
  78.         int i                                                    ;
  79.         for(p = * L , i = 0 ; i < position ; i ++) p = p -> next ;
  80.         p -> prior -> next = p -> next                           ;
  81.         p -> next -> prior = p -> prior                          ;
  82.         * e = p -> data                                          ;
  83.         if(* L == p) * L = p -> next                             ;  
  84.         free(p)                                                  ;
  85. }

  87. void traverseDL(DouLinklist L)
  88. {
  89.         DouLinklist p                                            ;
  90.         for(p = L ; p ; p = p -> next) printf("%4d", p -> data)  ;
  91.         printf("\n")                                             ;
  92. }

  94. int main()
  95. {
  96.         DouLinklist L = NULL    ;
  97.         hCreateDL(& L , 6)      ;
  98.         traverseDL(L)           ;
  99.         insertDL(& L , 2 , 9)   ;
  100.         traverseDL(L)           ;
  101.         ElemType a              ;
  102.         deleteDL(& L , 1 , & a) ;
  103.         traverseDL(L)           ;
  104.         return 0                ;
  105. }
复制代码

        编译运行实况：
  1. D:\[00.Exerciese.2022]\C>g++ -o x x.c

  3. D:\[00.Exerciese.2022]\C>x
  4. 请输入6个数据：
  5. 1 2 3 4 5 6
  6.    6   5   4   3   2   1
  7.    6   5   9   4   3   2   1
  8.    6   9   4   3   2   1

  10. D:\[00.Exerciese.2022]\C>
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-4-20 00:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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