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

知识小回顾

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

实验题目

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

实验目的

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

实验要求

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

实验内容和实验步骤

1）需求分析

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

2）概要设计

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

3）详细设计

导入相关的库

#include#include#include

单链表的存储结构。
注意：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$作比较，打印出查找结果。

//在单链表中查找值为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");}

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

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#include#include//用typedef 给int定义个名字为ElemType，意思是表中元素的typetypedef 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    {        <