2024年4月30日发(作者：)

单链表实验报告

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧

重点。

二、实验内容

[问题描述]

实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表

的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的单链表；

（2）输出单链表中的数据元素

（3）求单链表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

三、算法设计

（1）建立带表头结点的单链表；首先输入结束标志，然后建立循环逐个输入数据，

直到 输入结束标志。

（2）输出单链表中所有结点的数据域值；首先获得表头结点地址，然后建立循环

逐个输 出数据，直到地址为空。

（3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表

尾插入结点y;建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结

点， 建立循环扫描链表。当当前结点指针域不为空且数据域等于x的时候，申请结

点并给此结点数 据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指

针域为空的时候，申请结点 并给此结点数据域赋值为y，插入当前结点后面，退出函数。

（4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。建立三个结

构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立

整形变 量l=0；建立循环扫描链表。当当前结点指针域为空的时候，如果当前结点数据

域等于k，删除 此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳

出循环，结束操作。当 当前结点指针域不为空的时候，如果当前结点数据域等于k，删

除此结点，l++，继续循环操作； 如果当前结点数据域不等于k，指针向后继续扫描。

循环结束后函数返回变量l的值，l便是删除的结点的个数。

四、实验结果

1、新建一个链表：

2、输出链表的数据：

（4）插入数据：

在数据为3后面插入一个数据100：

（5）删除数据：

删除刚刚插入的数据100：

五、总结

实验之前由于准备不够充分，所以堂上实验时只完成了建立单链表和数据的输出，

而后面两个实验要求也是用来很多时间长完成的。以后做实验前，一定要做好充分的准

备，有一个清晰的思路，遇到更复杂的实验也一定能轻松完成。

六、源代码

#include "stdio.h"

#include "conio.h"

#define DataType int

typedef struct node

{

DataType data;

struct node *link;

}LNode;

LNode *h;

LNode *createtail()

{

LNode *s,*r;

int x,tag;

system("cls");

printf("input the sign of ending:");

scanf("%d",&tag);

h=(LNode * )malloc(sizeof(LNode));

h->data=tag;

r=h;

printf("input the data:");

scanf("%d",&x);

while(x!=tag)

{

s=(LNode * )malloc(sizeof(LNode));

s->data=x;

r->link=s;

r=s;

scanf("%d",&x);

}

r->link=NULL;

return h;

}

void output(LNode *h)

{

LNode *r;

int i;

system("cls");

r=h;

for(i=0;r->link!=NULL;i++)

{

printf("data[%d]=%dn",i,r->link->data);

r=r->link;

}

getch();

}

void insert(LNode *h)

{

LNode *r,*s;

int x,y;

system("cls");

printf("Input the data that you want to insert:n");

printf("x=");

scanf("%d",&x);

printf("y=");

scanf("%d",&y);

r=h;

r=r->link;

for(;;r=r->link)

{

if(r->data==x)

{

s=(LNode *)malloc(sizeof(LNode));

s->data=y;

s->link=r->link;

r->link=s;

break;

}

if(r->link==NULL)

{

s=(LNode *)malloc(sizeof(LNode));

s->data=y;

s->link=NULL;

r->link=s;

break;

}

}

}

int del(LNode *h)

{

LNode *r,*s,*t;

int k,l=0;

system("cls");

printf("Input the data that you want to delete:");

scanf("%d",&k);

r=h;

s=r;

r=r->link;

for(;;)

{

if(r->link==NULL)

{

if(r->data==k)

{

l++;

s->link=NULL;

free(r);

break;

}

else break;

}

else

{

if(r->data==k)

{

l++;

t=r;

s->link=t->link;

r=t->link;

free(t);

}

else {r=r->link;s=s->link;}

}

}

return l;

}

void nodata()

{

system("cls");

printf("You had not input ");

printf(" Press "Enter" to return");

getch();

}

main()

{

int a,b=1,c,l;

h=-1;

for(;b==1;)

{

system("cls");

printf(" a linear list.n");

printf(" the data of linear list.n");

printf(" data.n");

printf(" data.n");

printf("");

scanf("%d",&a);

switch(a)

{

case 1:createtail();break;

case 2:

{

if(h==-1) nodata();

else output(h);break;

}

case 3:

{

if(h==-1) nodata();

else insert(h);break;

}

case 4:

{

if(h==-1) nodata();

else {l=del(h);printf("You have deleted %d data(s)n",l);}break;

}

default:b=3;break;

}

}

printf("end.");

getch();

}