当前位置：首页 » 《关注互联网》 » 正文

数据结构--单链表的c语言实现（超详细注释/实验报告）_dream_of_grass的博客

28 人参与  2022年01月19日 13:42  分类 : 《关注互联网》  评论

点击全文阅读


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

知识小回顾

在顺序表中，用一组地址连续的存储单元来一次存放线性表的结点，因此结点的逻辑顺序和物理顺序是一致的。而链表则不然，链表是用一组任意的存储单元来存放线性表的结点，这组储存单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置上。因此链表中结点的逻辑顺序和物理顺序不一定相同。为了正确地表示结点间的逻辑关系，必须存储线性表的每个数据元素值的同时，存储知识其后继结点的地址（位置）信息，这两部分信息组成的存储映像成为结点（Node）。

实验题目

实现单链表表各种基本运算

实验目的

  1. 熟悉将算法转换为程序代码的过程；
  2. 熟练掌握顺序表的基本运算：头插法建表、尾插法建表、按序号查找、按值查找、求表长度、插入元素、删除指定元素等。

实验要求

  1. 以单链表表作为存储结构；
  2. 实现单链表上的数据元素的头插法建表、尾插法建表、按序号查找、按值查找、求表长度、插入元素、删除指定元素等操作。

实验内容和实验步骤

1）需求分析

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

2）概要设计

设计几个函数来实现初始化、头插法建表、尾插法建表、按序号查找、按值查找、求表长度、插入元素和删除指定元素的功能，然后再主函数中调用函数来实现操作。

3）详细设计

导入相关的库

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

单链表的存储结构。
注意：LinkList 和 Node * 同为结构体指针类型，这两种类型是等价的。
通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。
such as 使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。
使用Node * 来定义只想单链表中节点的指针，例如，Node *p,则p为指向单链表中节点的指针变量。

typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node,* LinkList;
/*LinkList 和 Node * 同为结构体指针类型，这两种类型是等价的。
通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。
such as 使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。
使用Node * 来定义只想单链表中节点的指针，例如，Node *p,则p为指向单链表中节点的指针变量。*/

初始化单链表

//初始化单链表
void Init_LinkList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node));//建立头结点
    (*L)->next=NULL;//建立空的单链表
    //注意：L是指向单链表头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，
    //*L相当于主程序中带初始化单链表的头指针变量。
}

头插法建表（逆序建表法）
算法思想：从一个空表开始，每次读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新节点插入到当前链表的表头结点之后，直至读入结束标志为止。

//用头插法建立单链表
void CreateFromHead(LinkList L)
{
    //L是带头结点的空链表头指针，通过键盘输入表中个元素值，利用头插法建单链表L
    Node *s;//s为只想单链表中结点的指针变量
    char c;
    int flag=1;
    while(flag)
    {
        c=getchar();
        if(c!='$')
        {
            s=(Node *)malloc(sizeof(Node));//建立新的结点
            s->data=(int)c;//给s赋值
            s->next=L->next;//把s变成头结点的后一个，后面的话，新的s都是L的后一个，这样也就导致了逻辑顺序和输入元素顺序相反
            L->next=s;
        }
        else flag=0;
    }
}

尾插法建表（顺序）
算法思想：将新节点插到前单链表的表尾上。为此需要增加一个尾指针r，使之只想当前单链表的表尾。

//尾插法建表
void CreateFromTail(LinkList L)
{
    Node *r,*s;//一个动态的尾指针r
    int flag=1;
    r=L;
    char c;
    while(flag)
    {
        c=getchar();
       // printf(" ");
        if(c!='$')
        {
            s=(Node*)malloc(sizeof(Node));
            s->data=(int)c;
            r->next=s;
            r=s;//r始终是在最后的
        }
        else
        {
            flag=0;
            r->next=NULL;//将最后一个结点的next链域设为空，表示链表的结束
        }
    }
}

按序号查找元素。
算法思想：在单链表中，由于每个系欸但的存储位置都放在其前一结点的next域中，所以即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问以为数组中的相应元素，实现随机存取，而只能从来链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。

//在单链表L中查找第i个结点
Node* Get(LinkList L,int i)
{
    int j;
    Node *p;
    if(i<0)
        return NULL;
    p=L;
    j=0;//j是一个计数器，用来与i比较
    while((p->next!=NULL)&&(j<i))//判断条件为：到达表尾或等于要查找的结点
    {
        p=p->next;
        j++;
    }
    if(i==j)
        return p;
    else
        return NULL;
}

按值查找元素。
算法思想：从单链表的头指针指向的头结点出发，顺链逐个将结点值和给定值 e e e作比较，打印出查找结果。

//在单链表中查找值为x的结点
int Locate(LinkList L,int x)
{
    LinkList p;
    int j=1;
    p=L->next;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
        j++;
    }
    if(p)
    {
        printf("%d在链表中，是第%d个元素",p->data-48,j);//由于是ascii，所以-48
    }
    else
    {
        printf("该数值不在链表里。\n");
        return 0;
    }
}

求单链表的长度。
算法思想：采用“数结点”的方法求出带头结点单链表的长度。即从“头”开始“数”（p=l->next）,用指针p依次指向各个结点，并附设计数器j技术，一直“数"到最后一个结点（p->next==NULL），从而得到单链表的长度。

//求单链表的长度
int ListLength(LinkList L)
{
    Node *p;
    p=L->next;
    int j=0;//计数器j
    while(p!=NULL)
    {
        p=p->next;
        j++;
    }
    printf("%d",j);
    return 0;
}

单链表插入操作。
算法思想：

  1. 查找：在单链表中找到第i-1个结点，并由指针p表示。
  2. 申请：申请新结点s，将其数值域的值置为e。
  3. 插入：尾插法插入。
//单链表插入操作
int Insert_LinkList(LinkList L,int i,char x)
{
    Node *p,*s;
    p=Get(L,i-1);//这是一个小细节，如果设为i的话就不能实现在第1个元素前面插入的操作了
    if(p==NULL)
    {
        printf("参数i输入有误！\n");
        return 0;
    }
    else
    {
        //其实就是尾插法
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
}

单链表删除操作。
算法思想：

  1. 查找：通过计数方式找到第i-1个基点，并由pre指示。
  2. 删除第i个结点并释放空间。
//单链表删除操作
int Delete_LinkList(LinkList L,int i)
{
    //在带头结点的单链表L中删除第i个元素
    Node *pre,*r;
    int k;
    pre=L;k=0;
    while(pre->next!=NULL&&k<i-1)
    {
        pre=pre->next;
        k++;
    }
    if(pre->next==NULL)
    {
        printf("删除结点的位置i不合理!\n");
        return 0;
    }
    r=pre->next;//r指向要删除的第i个结点
    pre->next=r->next;//第i个结点前的结点的后一个结点变成第i个结点后一个结点
    free(r);//释放r
    return 1;
}

显示单链表。
算法思想：顺着指针一个一个地打印。

//display单链表
void Display_LinkList(LinkList L)
{
    //printf("display调用开始\n");
    Node *p;
    ElemType s;
    p=L;
    while(p->next)
    {
        //p=p->next;
        printf("%c  ",p->next->data);//由于前面是getchar（），所以%c
        //printf("  ");
        p=p->next;
    }
    //printf("display调用结束\n");
}

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

int main()
{


    LinkList L;
    ElemType e,x;
    int i=1,k,j;
    Init_LinkList(&L);
    printf("尾插法建立单链表如下：\n(输入规则：一个数字一个数字地输入，不用加空格和回车，空格和回车也会被当作是一个字符，结束的时候请输入'$')\n");
    CreateFromTail(&L);
    system("cls");//清屏
    while(i)//保证一直进行
    {
        printf("\n现在的链表:  ");
        Display_LinkList(&L);
        printf("\n-------------------------------------\n");
        printf("             Main Menu         \n");
        printf("    1   在单链表中查找第i个结点    \n");
        printf("    2   在单链表中查找值为key的结点   \n");
        printf("    3   求单链表的长度   \n");
        printf("    4   单链表插入(在第i个结点插入e)   \n");
        printf("    5   单链表删除操作   \n");
        printf("    6   清屏   \n");
        printf("    0   结束程序      \n");
        printf("--------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 4, 5, 6, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入要查找的结点：");
            scanf("%d",&x);
            Node *p1;
            p1=Get(&L,x);
            //printf("%d",p1->data-48);
            printf(p1);
            printf("\n");
            break;
        case 2:
            printf("请输入要查找的值x：");
            scanf("%d",&x);
            Locate(&L,x+48);
            printf("\n\n");
            break;
        case 3:
            printf("长度为");
            //ListLength(&L);
            int p3=ListLength(&L);
            //printf(ListLength(&L));
            //Display_LinkList(&L);
            //printf("%d",p3);
            printf("\n\n");
            break;
        case 4:
            printf("要插入到哪个结点前？\n");
            int i;
            scanf("%d",&i);
            //ElemType e;
            int e;
            printf("要插入哪个值呢？\n");
            scanf("%s",&e);
            Insert_LinkList(&L,i,e);
            printf("\n\n");
            break;
        case 5:
            printf("要删除到哪个结点呢？\n");
            int ii;
            scanf("%d",&ii);
            ElemType ee;
            Delete_LinkList(&L,ii);
            //Display_LinkList(&L);
            printf("\n\n");
            break;
        case 6:
            system("cls");
            break;
        case 0:
                exit(0);
                break;
        default:
            printf("输入有误~");
        }
    }
return 0;
}

4）调试分析

遇到的问题及解决方法

  • 有很多细节需要好好琢磨和调试

算法的时空分析

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

实验结果

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

实验总结

这是第二个数据结构的代码实现，这一次就没有直接照着实验指导敲了，是结合教材和实验指导以及同学的代码写出来的，这次写完之后收获很大！多多重复，百炼成钢！

最后附上完整的代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//用typedef 给int定义个名字为ElemType，意思是表中元素的type
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node,* LinkList;
/*LinkList 和 Node * 同为结构体指针类型，这两种类型是等价的
。通常习惯上用LinkList说明指针变量，强调它是某个单链表的头
指针变量。such as 使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。
使用Node * 来定义只想单链表中节点的指针，例如，Node *p,则p为指向单链表中节点的指针变量。*/

//初始化单链表
void Init_LinkList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node));//建立头结点
    (*L)->next=NULL;//建立空的单链表
    //注意：L是指向单链表头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，
    //*L相当于主程序中带初始化单链表的头指针变量。
}

//用头插法建立单链表
void CreateFromHead(LinkList L)
{
    //L是带头结点的空链表头指针，通过键盘输入表中个元素值，利用头插法建单链表L
    Node *s;//s为只想单链表中结点的指针变量
    char c;
    int flag=1;
    while(flag)
    {
        c=getchar();
        if(c!='$')
        {
            s=(Node *)malloc(sizeof(Node));//建立新的结点
            s->data=(int)c;//给s赋值
            s->next=L->next;//把s变成头结点的后一个，后面的话，新的s都是L的后一个，这样也就导致了逻辑顺序和输入元素顺序相反
            L->next=s;
        }
        else flag=0;
    }
}

//尾插法建表
void CreateFromTail(LinkList L)
{
    Node *r,*s;//一个动态的尾指针r
    int flag=1;
    r=L;
    char c;
    while(flag)
    {
        c=getchar();
       // printf(" ");
        if(c!='$')
        {
            s=(Node*)malloc(sizeof(Node));
            s->data=(int)c;
            r->next=s;
            r=s;//r始终是在最后的
        }
        else
        {
            flag=0;
            r->next=NULL;//将最后一个结点的next链域设为空，表示链表的结束
        }
    }
}

//在单链表L中查找第i个结点
Node* Get(LinkList L,int i)
{
    int j;
    Node *p;
    if(i<0)
        return NULL;
    p=L;
    j=0;//j是一个计数器，用来与i比较
    while((p->next!=NULL)&&(j<i))//判断条件为：到达表尾或等于要查找的结点
    {
        p=p->next;
        j++;
    }
    if(i==j)
        return p;
    else
        return NULL;
}

//在单链表中查找值为x的结点
int Locate(LinkList L,int x)
{
    LinkList p;
    int j=1;
    p=L->next;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
        j++;
    }
    if(p)
    {
        printf("%d在链表中，是第%d个元素",p->data-48,j);//由于是ascii，所以-48
    }
    else
    {
        printf("该数值不在链表里。\n");
        return 0;
    }
}

//求单链表的长度
int ListLength(LinkList L)
{
    Node *p;
    p=L->next;
    int j=0;//计数器j
    while(p!=NULL)
    {
        p=p->next;
        j++;
    }
    printf("%d",j);
    return 0;
}

int Insert_LinkList(LinkList L,int i,char x)
{
    Node *p,*s;
    p=Get(L,i-1);//这是一个小细节，如果设为i的话就不能实现在第1个元素前面插入的操作了
    if(p==NULL)
    {
        printf("参数i输入有误！\n");
        return 0;
    }
    else
    {
        //其实就是尾插法
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
}

//单链表删除操作

int Delete_LinkList(LinkList L,int i)
{
    //在带头结点的单链表L中删除第i个元素
    Node *pre,*r;
    int k;
    pre=L;k=0;
    while(pre->next!=NULL&&k<i-1)
    {
        pre=pre->next;
        k++;
    }
    if(pre->next==NULL)
    {
        printf("删除结点的位置i不合理!\n");
        return 0;
    }


    r=pre->next;
    pre->next=r->next;
    //e=r;
    free(r);
    return 1;

}

//display单链表
void Display_LinkList(LinkList L)
{
    //printf("display调用开始\n");
    Node *p;
    ElemType s;
    p=L;
    while(p->next)
    {
        //p=p->next;
        printf("%c  ",p->next->data);
        //printf("  ");
        p=p->next;
    }
    //printf("display调用结束\n");
}




int main()
{
    LinkList L;
    ElemType e,x;
    int i=1,k,j;
    Init_LinkList(&L);
    printf("尾插法建立单链表如下：\n(输入规则：一个数字一个数字地输入，不用加空格和回车，空格和回车也会被当作是一个字符，结束的时候请输入'$')\n");
    CreateFromTail(&L);
    system("cls");
    while(i)//保证一直进行
    {
        printf("\n现在的链表:  ");
        Display_LinkList(&L);
        printf("\n-------------------------------------\n");
        printf("             Main Menu         \n");
        printf("    1   在单链表中查找第i个结点    \n");
        printf("    2   在单链表中查找值为key的结点   \n");
        printf("    3   求单链表的长度   \n");
        printf("    4   单链表插入(在第i个结点插入e)   \n");
        printf("    5   单链表删除操作   \n");
        printf("    6   清屏   \n");
        printf("    0   结束程序      \n");
        printf("--------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 4, 5, 6, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入要查找的结点：");
            scanf("%d",&x);
            Node *p1;
            p1=Get(&L,x);
            //printf("%d",p1->data-48);
            printf(p1);
            printf("\n");
            break;
        case 2:
            printf("请输入要查找的值key：");
            //char key;
            scanf("%d",&x);
            //Node *p2;
            Locate(&L,x+48);
            printf("\n\n");
            break;
        case 3:
            printf("长度为");
            //ListLength(&L);
            int p3=ListLength(&L);
            printf("\n\n");
            break;
        case 4:
            printf("要插入到哪个结点前？\n");
            int i;
            scanf("%d",&i);
            int e;
            printf("要插入哪个值呢？\n");
            scanf("%s",&e);
            Insert_LinkList(&L,i,e);
            printf("\n\n");
            break;
        case 5:
            printf("要删除到哪个结点呢？\n");
            int ii;
            scanf("%d",&ii);
            ElemType ee;
            Delete_LinkList(&L,ii);
            printf("\n\n");
            break;
        case 6:
            system("cls");
            break;
        case 0:
                exit(0);
                break;
        default:
            printf("输入有误~");
        }
    }
return 0;
}

点击全文阅读


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

结点  链表  指针  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

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

最新文章

  • 普通医生：他竟成了一国神医小说，普通医生：他竟成了一国神医京磊京墨墨姜宇秦秀兰
  • 求叶欢欢吴氏叶德荣小说免费资源
  • 完整版《专职奶爸：我娶了女儿的班主任》免费阅读
  • 以权定盘全章节免费在线阅读，杨志远杨石完结版
  • 已完结小说《租车追女神后，他成了真豪门》在线全文阅读
  • 一胎双宝：阴鸷总裁今天又上门求婚（谢逸林）在线免费阅读
  • 主人公叫芊芊肖强秦天的小说哪里免费看
  • 我反派啊！女主演我干嘛？免费阅读，我反派啊！女主演我干嘛？周巧巧许默
  • 男女主人公叶宁杨琳小说被女神截胡后，我是高手这件事全城皆知全文免费阅读
  • 男女主人公叫林宇陈芸的小说免费资源
  • 小说《被丢入乱葬岗：她滔天归来！》全文阅读
  • 《商家真刑啊！这样产品也敢送来直播？》小说大结局免费试读 刻沐沐哥小说

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

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