实验单链表操作验证.doc

实 验 报 告

课程名称 数据结构
实验名称 单链表操作验证
实验类型 验证型实验
实验地点 计304机房 实验日期 2011.10.28
指导教师 魏海平

专业 计算机科学与技术
班级 算计1001
学号 1011010113
姓名 张强

辽宁石油化工大学计算机与通信工程学院

数据结构实验报告评分表

项目
要求
分数
有无项目（√）
得分
预习报告
（30分）
实验目的明确
5

实验内容理解透彻
5

实验方案设计完整合理
程序总体框架设计完整
10

完成相关辅助代码
5

测试方案合理
5

实验过程
（30分）
发现问题
5

问题的分析
15

问题的解决方法
10

实验报告
（20分）
内容翔实无缺漏
5

如实记录实验过程
10

撰写规整
5

实验总结
（10分）
实验结果的分析
5

按照结果对原实验方案的改进意见
5

实验体会
（10分）
实验的收获
5

实验内容的发散考虑
5

总分

实验一 单链表操作验证
一．实验目的
(1)掌握线性表的链接存储结构；
(2)验证单链表及其基本操作的实现；
(3)进一步掌握数据结构及算法的程序实现的基本方法。
二．实验内容
(1)用头插法（或尾插法）建立带头结点的单链表；
(2)对已建立的单链表实现插人、删除、查找等基本操作。
三.实验步骤
1．需求分析
　 本演示程序用VC++编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。
④ 测试数据：
（1） 生成单链表 1 23 2 34 3 45 4 56
（2） 查找1 位置为23
（3） 删除数据 2
（4） 插入 2 67
（5） 输出数据 1 23 2 67 3 45 4 56
2. 源程序如下：
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#define NULL 0
struct data
{
int num;
int d;
struct data *next;
};
struct data *head,*p,*tail;
int len,i;
struct data *creat()
{
int n;
len=sizeof( struct data);
printf("len=");
scanf("%d",&n);
printf("输入创建单链表:\n");
head=(struct data*)malloc(len);
printf("数据位置和数据:\n");
scanf("%d%d",&head->num,&head->d);
tail=head;
for(i=2;i<=n;i++)
{
p=(struct data *)malloc(len);
scanf("%d%d",&p->num,&p->d);
tail->next=p;
tail=p;
}
tail->next=NULL;
return(head);
}
void output(struct data *head)
{
int j;
struct data *p0,*p1;
p=head;
for(j=0;j<len;j++)
{
for(i=0;i<len-j;i++)
p0=p->next;
if(p->num>p0->num)
{p1=p;p=p0;p0=p1;}
}
for(p=head;p!=NULL;p=p->next)
printf("%d: %d\n",p->num,p->d);
}
struct data *ins(struct data *head)
{
struct data *p0,*p1,*p2;
struct data *ins;
printf("输入插入的位置和数据:");
ins=(struct data * )malloc(len);
scanf("%d%d",&ins->num,&ins->d);
p1=head;
p0=ins;
if(head==NULL)
{head=p0;p0->next=NULL;}
else
{
while((p0->num>p1->num)&&(p1->next!=NULL))
{p2=p1;
p1=p1->next;
}
if(p0->num<=p1->num)
{
if(head==p1) head=p0;
else p2->next=p0;
p0->next=p1;
}
else {p1->next=p0;p0->next=NULL;}
}
for(p=head;p!=NULL;p=p->next)
printf("%d: %d\n",p->num,p->d);
return(head);
}
struct data * del(struct data *head)
{
struct data *p1,*p2;
int num;
printf("输入删除位置:");
scanf("%d",&num);
if(head==NULL)
{printf("链表空!\n");goto end;}
p1=head;
while(p1->num!=num&&p1->next!=NULL)
{p2=p1;p1=p1->next;}
if(p1->num==num)
{
if(p1==head) head=p1->next;
else p2->next=p1->next;
}
else printf("没有发现%d!\n",num);
for(p=head;p!=NULL;p=p->next)
printf("%d: %d\n",p->num,p->d);
end:return(head);
}
void find(struct data *head)
{
struct data *p1;
int num;
printf("输入查找位置:");
scanf("%d",&num);
if(head==NULL)
{printf("链表空!\n");goto end;}
p1=head;
while(p1->num!=num&&p1->next!=NULL)
{p1=p1->next;}
if(p1->num==num)
{
printf("这数据信息\n");
printf("%d: %d\n",p1->num,p1->d);
}
else printf("%d 没有发现!\n",num);
end:;
}
void main()
{
struct data *head;
int select;
head=NULL;
while(1)
{
printf("1:创建 2:插入 3:删除 4:查找 5:输出 6:退出\n");
printf("please input select:");
scanf("%d",&select);
switch(select)
{
case 1:head=创建();break;
case 2:head=插入(head);break;
case 3:head=删除(head);break;
case 4:查找d(head);break;
case 5:输出(head);break;
case 6:退出(0);
}
}
}
3. 使用说明：
===================================
1:————创建
2:————插入
3:————删除
4:————查找
5:————输出
6:————退出
===================================
Select：在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。
选择1.创建一个单链表。
选择2.选择插入的位置和和数据。
选择3.输入要删除的位置，程序将删除该位置的数据。
选择4.输入查找到位置，程序将显示该位置的数据。
选择5.程序将自动输出经过变化后的单链表。
选择6.退出程序。
4. 测试结果截图：

四、实验总结（结果分析和体会）
1. 我又进一步巩固了C语言的基础，尤其是指针那部分；
2. 通过实验加深了对线性表的操作方面知识的认识。更深层次了解了单链表的操作特点及优缺点；
3. 通过实验达到了理论与实践结合的目的，提高了自己的编程能力；
4. 通过实验是我进一步对单链表进行了复习与巩固。这是在实践中对自我能力的提高。
5. 程序可能不够完善需要在学习过程中不断去完善，这需要平时的努力。