鱼C论坛

 找回密码
 立即注册
查看: 72|回复: 1

双链表

[复制链接]
最佳答案
0 
发表于 2020-9-20 17:13:33 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
初学数据结构,求大佬解答。不知道为啥VS2019执行程序的时候没有说出错,但程序只运行一半就结束了

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef int DataType;
typedef struct DulNode
{
        DataType data;
        struct DulNode* prior, * next;
}DulNode;

DulNode* Creatlist(DataType a[], int n)
{
        DulNode* s = NULL;
        DulNode* first = (DulNode*)malloc(sizeof(DulNode));
        first->prior = NULL;
        for (int i = 0; i < n; i++)
        {
                s = (DulNode*)malloc(sizeof(DulNode));
                s->data = a[i];
                s->next=first->next;
                first->next = s;
                s->prior = first;
        }
        return first;
}

void PrintList(DulNode* first)
{
        DulNode* p = first->next;
        while (p != NULL)
        {
                printf("%d", p->data);
                p = p->next;
        }
}

int Length(DulNode* first)
{
        DulNode* p = first->next;
        int count = 0;
        while (p != NULL)
        {
                p = p->next;
                count++;
        }
        return count;
}

int Locate(DulNode* first, DataType x)
{
        DulNode* p = first->next;
        int count = 1;
        while (p != NULL)
        {
                if (p->data == x) return count;
                p = p->next;
                count++;
        }
        return 0;
}

int Insert(DulNode* first, int i, DataType x)
{
        DulNode* s = NULL, * p = first;
        int count = 0;
        while (p != NULL && count < i - 1)
        {
                p = p->next;
                count++;
        }
        if (p == NULL) {
                printf("位置错误,插入失败\n"); return 0;
        }
        else {
                s = (DulNode*)malloc(sizeof(DulNode));
                s->data = x;
                s->prior = p;
                s->next = p->next;
                p->next->prior = s;
                p->next = s;
                return 1;
        }
}

int Delete(DulNode* first, int i, DataType* ptr)
{
        DulNode* p = first, * q = NULL;
        int count = 0;
        DataType x;
        while (p != NULL && count < i - 1)
        {
                p = p->next;
                count++;
        }
        if (p == NULL || p->next == NULL)
        {
                printf("位置错误,删除失败\n"); return 0;

        }
        else {
                q = p->next; *ptr = q->data;
                p->prior->next = p->next;
                p->next->prior = p->prior;
                free(q); return 0;
        }
}

void DestroyList(DulNode* first)
{
        DulNode* p = first;
        while (first != NULL)
        {
                first = first->next;
                free(p); p = first;
        }
}

int main()
{
        int r[5] = { 1,2,3,4,5 }, i, x;
        DulNode* first = NULL;
        first = Creatlist(r, 5);
        printf("当前线性表的数据为:");
        PrintList(first);
        Insert(first, 2, 8);
        printf("执行插入操作后数据为:");
        PrintList(first);
        printf("当前双链表的长度为:%d", Length(first));
        printf("请输入查找的元素值:");
        scanf_s("%d", &x);
        i = Locate(first, x);
        if (1 == i)printf("元素中%的元素位置为:%d\n", x, i);
        else printf("双链表中没有元素%d\n", x);
        printf("请输入要删除第几个元素:");
        scanf_s("%d", &i);
        if (Delete(first, i, &x) == 1) {
                printf("删除的元素值是%d,执行删除操作后数据为:", x);
                PrintList(first);
        }
        else printf("删除操作失败\n");
        DestroyList(first);
        return 0;
}

不知为啥只执行了前面的PrintList就不继续了,也没有说出错

不知为啥只执行了前面的PrintList就不继续了,也没有说出错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
67 
发表于 2020-9-21 11:04:02 | 显示全部楼层
本帖最后由 xieglt 于 2020-9-21 11:12 编辑

首先,建立链表的函数有问题
  1. DulNode* Creatlist(DataType a[], int n)
  2. {
  3.         DulNode* s = NULL;
  4.         DulNode* first = (DulNode*)malloc(sizeof(DulNode));

  5.         first->prior = NULL;
  6.         //first->next 没有初始化为NULL;
  7.         first->next = NULL;

  8.         for (int i = 0; i < n; i++)
  9.         {
  10.                 s = (DulNode*)malloc(sizeof(DulNode));
  11.                 s->data = a[i];

  12.                 s->next=first->next;
  13.                 first->next = s;
  14.                 s->prior = first;
  15.         }
  16.         return first;
  17. }
复制代码


另外,你的新节点不是建立在链表末尾,而是在第2的位置,也就是first之后的位置
建议这么建立链表,保证新节点在链表末尾
  1. DulNode* Creatlist(DataType a[], int n)
  2. {
  3.         DulNode* s = NULL;
  4.         DulNode* first = (DulNode*)malloc(sizeof(DulNode));

  5.         first->prior = NULL;
  6.         first->next = NULL;

  7.         DulNode * pNode = first;

  8.         for (int i = 0; i < n; i++)
  9.         {
  10.                 s = (DulNode*)malloc(sizeof(DulNode));
  11.                 s->data = a[i];
  12.                 s->next= NULL;
  13.                 s->prior = pNode;
  14.                 pNode->next = s;
  15.                 pNode = s;
  16.         }

  17.         return first;
  18. }
复制代码


删除节点也有点问题
  1. int Delete(DulNode* first, int i, DataType* ptr)
  2. {
  3.         DulNode* p = first, * q = NULL;
  4.         int count = 0;
  5.         DataType x;

  6.         while (p != NULL && count < i - 1)
  7.         {
  8.                 p = p->next;
  9.                 count++;
  10.         }
  11.         //这个逻辑有问题,p != NULL 且 p->next != NULL 时说明链表里至少还有2个节点
  12.         //也就是说,至少还有一个元素,为什么不能删除?
  13.         if (p == NULL || p->next == NULL)
  14.         {
  15.                 printf("位置错误,删除失败\n"); return 0;

  16.         }
  17.         else
  18.         {               
  19.                 //这个逻辑错了
  20.                 q = p->next;
  21.                 *ptr = q->data;
  22.                 //应该是 *ptr = p->data;

  23.                 p->prior->next = p->next;
  24.                 p->next->prior = p->prior;
  25.                                
  26.                 //free错了,删除的节点应该是p,也就是 free(p);
  27.                 free(q);
  28.                 //返回值错了,按逻辑应该是1
  29.                 return 1;
  30.         }
  31. }
复制代码


主函数中的问题


  1. //这个判断有问题,应该是i > 0
  2.         if (1 == i)
  3.         //这里%后面少了个d
  4.                 printf("元素中%的元素位置为:%d\n", x, i);
  5.         else
  6.                 printf("双链表中没有元素%d\n", x);
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2020-10-26 15:36

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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