当前位置：首页 » 《休闲阅读》 » 正文

数据结构--双链表的c/c++实现（超详细注释/实验报告）_池塘春草梦的博客

7 人参与  2022年02月03日 14:33  分类 : 《休闲阅读》  评论

点击全文阅读


数据结构–双链表的c/c++实现（超详细注释/实验报告）

知识小回顾

如果希望从表中快速确定某一个结点的前去，其中一个解决方法就是在单链表的每个结点再增加一个指向其前去的指针域prior。这样形成的链表中就有两条方向不同的链，称之为双向链表(Double Linked List)。

实验题目

实现双链表各种基本运算

实验目的

  1. 熟悉将算法转换为程序代码的过程；
  2. 了解双链表的逻辑结构特性，熟练掌握双链表存储结构的C语言描述方法；
  3. 熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的前驱结点的特性。

实验要求

  1. 以双链表作为存储结构；
  2. 实现双链表上的数据元素的插入运算；
  3. 实现双链表上的数据元素的删除运算；
  4. 实现双链表上的数据元素的查找运算。

实验内容和实验步骤

1.需求分析

 以菜单的形式作为用户与程序的接口，用户输入菜单号来实行相应的操作。

2. 概要设计

 设计几个函数来实现初始化、插入、删除和查找的功能，然后再主函数中调用函数来实现操作。

3. 详细设计

导入一些库，并定义表中元素的类型。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;

定义线性表链式存储结构

//定义线性表链式存储结构
typedef struct DLnode
{
    ElemType data;//定义数据类型
    struct DLnode *prior;//指向前驱的结点
    struct DLnode *next;//指向后继的结点
}DLnode,*DLinkList;

初始化双链表

//初始化双链表
void Init_DLinkList(DLinkList &L)
{
    L=(DLnode *)malloc(sizeof(DLnode));//生成头结点
    L->prior=L->next=NULL;//初始化头、尾指针，使它们都为NULL
}

头插法创建双链表

//头插法创建双链表
void Create_DLinkList(DLinkList &L,int n)
{
    int i;
    DLinkList p;//新开一个结点
    Init_DLinkList(L);//初始化一下
    for(i=n;i>0;--i)
    {
        p=(DLinkList)malloc(sizeof(DLnode));//下面是头插法算法
        p->data=i;
        p->next=L->next;
        L->next=p;
        if(p->next!=NULL)
            p->next->prior=p;//因为是双链表，所以还要把前指针给设置好
        p->prior=L;//由于是头插法，所以p永远是头结点的下一个结点
    }
}

在双链表中查找某个数据元素

//在双链表中查找某个数据元素
int Locate_DLinkList(DLinkList L,ElemType e)
{
    int i=1;//i为计数器
    DLinkList p=L->next;
    while (p!=NULL&&p->data!=e)
    {
        i++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("双链表中不存在该元素！\n");
        return 0;
    }
    else
        return i;
}

在双链表的第i个元素之前插入新元素

//在双链表的第i个元素之前插入新元素
int Insert_DLinkList(DLinkList &L,int i,ElemType e)
{
    int j=0;
    DLinkList p=L,s;
    while (p!=NULL&&j<i)//注意循环体的编写，每循环一次j++，p往后挪一位。j一开始是0，p是头结点，一次循环之后j是1，p到了第一个结点

    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("插入位置不正确！\n");
        return 0;
    }
    else
    {//注意下面赋值语句的顺序，先把新的线搭好，再把旧的线拆掉
       s=(DLnode *)malloc(sizeof(DLnode));//新开一个结点
       s->data=e;
       s->prior=p->prior;//s的前面是p的前面
       s->next=p;
       p->prior->next=s;//没放s之前的时候p的前面的后面应该为s
       p->prior=s;//p的前面是s
       return 1;
    }
}

删除双链表中第i个数据元素

//删除双链表中第i个数据元素
int Delete_DLinkList(DLinkList &L,int i)
{
    int j=0;
    DLinkList p=L;
    while (j<i&&p!=NULL)//这个循环体和上面插入是一样的
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("删除位置不正确！\n");
        return 0;
    }
    else
    {
        p->prior->next=p->next;//p前面的后面等于p的后面，相当于把p给忽略了
        if(p->next!=NULL)//如果p不是最后一个的话
        {
            p->next->prior=p->prior;//p后面的前面等于p的前面，这句和上句一起把p前后两个结点的指针给设置好了
        }
        free(p);//释放p
        return 1;
    }
}

双链表的显示

//双链表的显示
void Display_DLinkList(DLinkList L)
{//没什么可说的，一个接着一个打印
    DLinkList p;
    p=L->next;
    while (p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}

主函数部分，用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。
双链表

int main()
{

    DLinkList L;
    int i=0,j,e,x,t;
    char ch;
    //Init_DLinkList(L);
    Create_DLinkList(L,5);
    printf("初始化\n建立双链表如下：\n");
    //Display_DLinkList(L);
    while(i<5)
    {
        Display_DLinkList(L);
        printf("\n------------------------------------\n");
        printf("\n         主菜单         \n");
        printf("    1   查找指定元素    \n");
        printf("    2   插入元素到指定位置   \n");
        printf("    3   删除某一指定位置元素   \n");
        printf("    4   清屏      \n");
        printf("    0   退出      \n");
        printf("------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 4, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入查找元素：");
            scanf("%d",&x);
            j=Locate_DLinkList(L,x);
            if(j!=0)
            {
                printf("指定元素位置是 %d",j);
            }
            printf("\n\n");
            break;
        case 2:
            printf("请输入插入元素位置：");
            scanf("%d",&t);
            printf("请输入插入元素值：");
            scanf("%d",&x);
            j=Insert_DLinkList(L,t,x);
            if(j!=0)
            {
                printf("插入后顺序表如下显示：\n");
                Display_DLinkList(L);
                printf("\n");
            }
            printf("\n\n");
            break;
        case 3:
            printf("请输入删除元素位置：");
            scanf("%d",&t);
            //j=Delete_DLinkList(L,t,x);
            j=Delete_DLinkList(L,t);
            if(j!=0)
            {
                printf("删除后顺序表如下显示：\n");
                Display_DLinkList(L);
                printf("\n");
            }
            printf("\n\n");
            break;
        case 4:
            system("cls");
            break;
        case 0:
            exit(0);
            break;
        default:
            printf("输入有误~");
        }
    }
}

4. 调试分析

遇到的问题及解决方法

-双链表这一个程序主要是依托实验指导书，但是实验指导书上有一些代码设计的不合理，有一些无用的代码，占用了不必要的空间，然后我就改了一下。

算法的时空分析

  • 都是比较基础的操作，没有涉及很复杂的算法，故时空复杂度也还不算很大。

实验结果

实验结果很不错，所有操作都能正常执行，并且自己加入了“清屏”选项，使得界面更加的整洁。

实验总结

这是第三个数据结构的代码实现，主要还是跟着实验指导书上写，原创性不足，不过也学到了很多知识，也为之后的程序编写搭建了一个不错的框架！多多重复，百炼成钢！

最后附上完整的代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
//定义线性表链式存储结构
typedef struct DLnode
{
    ElemType data;//定义数据类型
    struct DLnode *prior;//指向前驱的结点
    struct DLnode *next;//指向后继的结点
}DLnode,*DLinkList;

//初始化双链表
void Init_DLinkList(DLinkList &L)
{
    L=(DLnode *)malloc(sizeof(DLnode));//生成头结点
    L->prior=L->next=NULL;//初始化头、尾指针，使它们都为NULL
}

//头插法创建双链表
void Create_DLinkList(DLinkList &L,int n)
{
    int i;
    DLinkList p;//新开一个结点
    Init_DLinkList(L);//初始化一下
    for(i=n;i>0;--i)
    {
        p=(DLinkList)malloc(sizeof(DLnode));//下面是头插法算法
        p->data=i;
        p->next=L->next;
        L->next=p;
        if(p->next!=NULL)
            p->next->prior=p;//因为是双链表，所以还要把前指针给设置好
        p->prior=L;//由于是头插法，所以p永远是头结点的下一个结点
    }
}

//在双链表中查找某个数据元素
int Locate_DLinkList(DLinkList L,ElemType e)
{
    int i=1;//i为计数器
    DLinkList p=L->next;
    while (p!=NULL&&p->data!=e)
    {
        i++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("双链表中不存在该元素！\n");
        return 0;
    }
    else
        return i;
}

//在双链表的第i个元素之前插入新元素
int Insert_DLinkList(DLinkList &L,int i,ElemType e)
{
    int j=0;
    DLinkList p=L,s;
    while (p!=NULL&&j<i)//注意循环体的编写，每循环一次j++，p往后挪一位。j一开始是0，p是头结点，一次循环之后j是1，p到了第一个结点

    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("插入位置不正确！\n");
        return 0;
    }
    else
    {//注意下面赋值语句的顺序，先把新的线搭好，再把旧的线拆掉
       s=(DLnode *)malloc(sizeof(DLnode));//新开一个结点
       s->data=e;
       s->prior=p->prior;//s的前面是p的前面
       s->next=p;
       p->prior->next=s;//没放s之前的时候p的前面的后面应该为s
       p->prior=s;//p的前面是s
       return 1;
    }
}

//删除双链表中第i个数据元素
int Delete_DLinkList(DLinkList &L,int i)
{
    int j=0;
    DLinkList p=L;
    while (j<i&&p!=NULL)//这个循环体和上面插入是一样的
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("删除位置不正确！\n");
        return 0;
    }
    else
    {
        p->prior->next=p->next;//p前面的后面等于p的后面，相当于把p给忽略了
        if(p->next!=NULL)//如果p不是最后一个的话
        {
            p->next->prior=p->prior;//p后面的前面等于p的前面，这句和上句一起把p前后两个结点的指针给设置好了
        }
        free(p);//释放p
        return 1;
    }
}

//双链表的显示
void Display_DLinkList(DLinkList L)
{//没什么可说的，一个接着一个打印
    DLinkList p;
    p=L->next;
    while (p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}


int main()
{

    DLinkList L;
    int i=0,j,e,x,t;
    char ch;
    //Init_DLinkList(L);
    Create_DLinkList(L,5);
    printf("初始化\n建立双链表如下：\n");
    //Display_DLinkList(L);
    while(i<5)
    {
        Display_DLinkList(L);
        printf("\n------------------------------------\n");
        printf("\n         主菜单         \n");
        printf("    1   查找指定元素    \n");
        printf("    2   插入元素到指定位置   \n");
        printf("    3   删除某一指定位置元素   \n");
        printf("    4   清屏      \n");
        printf("    0   退出      \n");
        printf("------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 4, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入查找元素：");
            scanf("%d",&x);
            j=Locate_DLinkList(L,x);
            if(j!=0)
            {
                printf("指定元素位置是 %d",j);
            }
            printf("\n\n");
            break;
        case 2:
            printf("请输入插入元素位置：");
            scanf("%d",&t);
            printf("请输入插入元素值：");
            scanf("%d",&x);
            j=Insert_DLinkList(L,t,x);
            if(j!=0)
            {
                printf("插入后顺序表如下显示：\n");
                Display_DLinkList(L);
                printf("\n");
            }
            printf("\n\n");
            break;
        case 3:
            printf("请输入删除元素位置：");
            scanf("%d",&t);
            //j=Delete_DLinkList(L,t,x);
            j=Delete_DLinkList(L,t);
            if(j!=0)
            {
                printf("删除后顺序表如下显示：\n");
                Display_DLinkList(L);
                printf("\n");
            }
            printf("\n\n");
            break;
        case 4:
            system("cls");
            break;
        case 0:
            exit(0);
            break;
        default:
            printf("输入有误~");
        }
    }
}

点击全文阅读


本文链接：http://zhangshiyu.com/post/34235.html

结点  链表  元素  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 林晴王兰凤全文小说最新章节阅读林晴王兰凤
  • 流放？她搬空皇宫，手举炸弹造反免费阅读全文，主角凤清歌君九霄小说完整版
  • 开局成为缚地灵，国运战上我修仙小说在线阅读，主角姬妩噎鸣娘娘精彩段落最新篇
  • 甜宠：抑郁甜妹的救赎男神抖音全本小说秦修聿温南湫抖音免费章节阅读
  • (抖音)圣诞节，老公将怀孕的我赶出家门段祈轩安雨萱小说免费全文阅读
  • 天意弄人，我必灭天未删减阅读
  • 王宏毅李语晴全文最新章节正版小说免费阅读
  • 快手热文《回首望，故人凉》余诗然黎怀州小说推荐
  • 直播冷宫小公主，全网投喂养崽崽是什么小说洛明溪江黎全本免费阅读
  • 《青山勿扰》徐芝芝沈青山-小说未删减阅读
  • 系统越来越诡异关我牧师什么事小说最新章节 鲁伯特张小伟结局是什么
  • 温见瑜季书雪长夜小说全章节最新阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1