《数据结构》实验报告
实验题目：线性表的操作
实验目的：
1.掌握上机调试线性表的基本方法；
2.掌握线性表的一些基本操作；
实验内容：将两个有序链表合并为一个有序链表
一、需求分析
1.实验程序中先创建两个有序链表，演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入两个链表中的相应数据。
2.将两个链表合并时可按数据从大到小或从小到大合并，用户根据提示可选择一种排序方式。
3.程序执行命令包括：
（1）构造链表；（2）输入数据；（3）合并两个链表，根据用户需求选择一种排序方式；（4）将合并结果输出；（5）结束
4.测试数据：
链表1数据为：2，4，6，7，10
链表2数据为：1，3，5，6，7，12
按从小到达合并为：1，2，3，4，5，6，6，7，7，10，12；
按从大到小合并为：12，10，7，7，6，6，5，4，3，2，1；
二、概要设计
1.基本操作
Linklist creat（）
操作结果：构造一个链表，并输入数据，返回头节点指针。
void print(Linklist head)
初始条件：链表已存在；
操作结果：将链表输出。
void MergeList_1(Linklist La,Linklist Lb)
初始条件：有序线性链表La和Lb已存在；
操作结果：将La和Lb两个链表按从小到大的顺序合并。
void MergeList_2(Linklist La,Linklist Lb)
初始条件：有序线性链表La和Lb已存在；
操作结果：将La和Lb两个链表按从大到小的顺序合并。
2.本程序包括四个模块：
（1）主程序模块；
（2）链表数据输入模块；
（3）链表合并模块；
（4）链表输出模块；
三、详细设计
1.元素类型，节点类型，指针类型
typedef struct LNode //定义节点
{
int data;
struct LNode *next;
}LNode,* Linklist;
2.每个模块的分析
（1）主函数模块
int main()
{
Linklist head1,head2;
int i;
printf("请输入链表1数据（由小到大，输入0表示输入结束）：\n");
head1=creat(); //创建链表1，将头结点指针返回为head1
printf("请输入链表2数据（由小到大，输入0表示输入结束）：\n");
head2=creat();
printf("请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：");
scanf("%d",&i); //创建链表2，将头结点指针返回为head2
if(i==1) //选择两种排序方式，如果输入1，则合并后按从小到大输出；输入其它数，合成链表按从大到小输出
{
printf("按小到大将两表合并得：\n");
MergeList1(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数
}
else
{ printf("按从大到小将两表合并得：\n");
MergeList2(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数
}
return 0;
}
（2）数据输入创建链表模块
Linklist creat() //创建链表函数，并将创建链表的头结点指针返回
{
Linklist head,p,s;
int z=1,x;
head=(LNode *) malloc(sizeof(LNode));
p=head;
while(z)
{
scanf("%d",&x);
if(x!=0) //输入0表示链表数据输入结束
{
s=(LNode *)malloc(sizeof(LNode));
s-＞data=x;
p-＞next=s;
s-＞next=NULL;
p=s;
}
else
z=0;
}
return(head);
}
（3）合并链表模块，两个函数分别表示两种排序方式，将链表合并后直接在函数中调用链表输出函数void print(Linklist head)将链表输出
void MergeList_1(Linklist La,Linklist Lb)
//已知链表La和Lb元素都按从小到大排列，将La和Lb合并成新链表，其中元素也按从小到大排列
{
Linklist pa,pb,pc,Lc;
pa = La-＞next; pb = Lb-＞next;
Lc = pc = La; //把La的头节点作为新建链表Lc的头结点
while (pa && pb)
{
if (pa-＞data ＜= pb-＞data)
{
pc-＞next = pa;
pc = pa;
pa = pa-＞next;
}
else
{
pc-＞next = pb;
pc = pb;
pb = pb-＞next;
}
}
pc-＞next = pa ? pa : pb; //插入剩余段
print(Lc); //将链表Lc输出
}
void MergeList_2(Linklist La,Linklist Lb)
//已知链表La和Lb的元素都按从小到大排列，合并La和Lb得到新链表，其中元素按照从大到小的顺序排列
{
Linklist pa,qa,pb,qb,Lc; //设指针qa,qb,分别作为pa,pb的前驱的指针
pa=La-＞next;
pb=Lb-＞next;
Lc=La;
Lc-＞next=NULL;
while(pa&&pb)
{
if(pa-＞data＜=pb-＞data)
{
qa=pa;
pa=pa-＞next;
qa-＞next=Lc-＞next;
Lc-＞next=qa;
}
else
{
qb=pb;
pb=pb-＞next;
qb-＞next=Lc-＞next;
Lc-＞next=qb;
}
}
while(pa) //如果pa不为空，则将La链的剩余段倒叙插入到头节点的后面
{
qa=pa;
pa=pa-＞next;
qa-＞next=Lc-＞next;
Lc-＞next=qa;
}
while(pb) //如果pb不为空，则将Lb链的剩余段倒叙插入到头结点的后面
{
qb=pb;
pb=pb-＞next;
qb-＞next=Lc-＞next;
Lc-＞next=qb;
}
print(Lc); //将新合成的链表Lc输出
}
(4)链表输出模块，实现最终链表的输出
void print(Linklist head) //链表输出函数，将链表输出
{
LNode *p;
p=head-＞next;
if(head!=NULL)
do
{
printf("%d ",p-＞data);
p=p-＞next;
} while (p);
printf("\n");
四、程序使用说明及测试结果
1.程序使用说明
（1）本程序的运行环境为VC6.0；
（2）进入演示程序后显示提示信息：
请输入链表1数据（由小到大，输入0表示输入结束）：
按要求输入数据
请输入链表2数据（由小到大，输入0表示输入结束）：
按要求输入数据
请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：
输入数据选择合并方式
2.测试结果
对链表1输入数据2，4，6，7，10，0
对链表2输入数据1，3，5，6，7，12，0
输入数据选择排序方式：
如果输入：1 输出结果为：1，2，3，4，5，6，6，7，7，10，12
如果输入：3（整数非1） 输出结果为：12，10，7，7，6，6，5，4，3，2，1
3.调试中遇到的错误分析
第一次运行时有问题，看以看出它的排序方式是对的，但是输出是多出前面一个很大的数，
可能是输出函数void print(Linklist head)有问题，检查程序：
此处逻辑出错，直接将p指针指向head，然后就将p-＞data输出，因此第一个数是头指针head所对应节点的值，所以可将p=head;改为p=head-＞next;这样p就指向第一个节点。
4.运行界面
五、实验总结
1.大部分的时间都用在了编程上，主要是因为C语言掌握的问题，C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练，导致在编程过程中还要不断的拿着c语言的教材查找，所以今后还要对C语言多练习，多动手，多思考。
2.数据结构有很强的逻辑性，因此我认为如果在上机之前先把逻辑搞清楚很重要，不管是对算法的设计还是对程序的调试都有很大帮助。
3.经过一次上机实践，我认为实践课很重要，上理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的。
教师评语：
实验成绩：
指导教师签名：
批阅日期：
第二篇：数据结构顺序表操作实验报告
实验1 顺序表的操作
一、实验要求
1.输入一组整型元素序列，建立顺序表。
2.实现该顺序表的遍历。
3.在该顺序表中进行顺序查找某一元素，查找成功返回1，否则返回0。
4.判断该顺序表中元素是否对称，对称返回1，否则返回0。
5.实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。
6.* 输入整型元素序列利用有序表插入算法建立一个有序表。
7.* 利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。
8.编写一个主函数，调试上述算法。
二、源代码
#include"stdio.h"
#include"stdlib.h"
#define ElemType int//int类型宏定义
#define MAXSIZE 100
//顺序结构
typedef struct
{
ElemType elem[MAXSIZE]; //元素数组
int length; //当前表长
}SqList;
//建立顺序表
void BuildList(SqList &L)
{
int n;
printf("请输入建立顺序表的大小。n=");
scanf("%d",&n);
L.length=n;
printf("\n开始建立顺序表...\n");
for(int i=0;i＜L.length;i++)//循环建立顺序表
{
printf("\n请输入第%d个元素：",i+1);
scanf("%d",&L.elem[i]);
}
printf("\n建立顺序表完毕！...\n");
}
//遍历顺序表
void ShowList(SqList &L)
{
int i;
printf("\n开始遍历顺序表...\n");
for(i=0;i＜L.length;i++)
printf("%d ",L.elem[i]);
printf("\n遍历结束...\n");
}
//在顺序表中寻找X元素
int FindList(SqList &L,int x)
{
int a=0;
for(int i=0;i＜L.length;i++)
{
if(L.elem[i]==x)
a=1;
}
if(a==1)
printf("1\n");
else
printf("0\n");
return 0;
}
//判断是否对称
int Duichen(SqList &L)
{
int j,b=1,n;
n=L.length;
if(n%2==0)
{
for(j=0;j＜n/2;j++)
{
if(L.elem[j]!=L.elem[L.length-j-1])
b=0;
}
}
else
for(j=0;j＜(n-1)/2;j++)
{
if(L.elem[j]!=L.elem[L.length-j-1])
b=0;
}
if(b==1)
printf("1\n");
else
printf("0\n");
return 0;
}
//前面为奇数，后面为偶数
void PaixuList(SqList &L)
{
int i,j,a;
for(i=1;i＜L.length;i++)
{
if(L.elem[i]%2==1)
{
a=L.elem[i];
for(j=i;j＞0;j--)
{
L.elem[j]=L.elem[j-1];
}
L.elem[0]=a;
i++;
}
}
for(i=0;i＜L.length;i++)
printf("%d ",L.elem[i]);
printf("\n");
}
int main()
{
SqList List;
int n;
while(1)
{
printf("\n 实验一：顺序表\n");
printf("\n ******************************************************************");
printf("\n 1.创建顺序表");
printf("\n 2.遍历顺序表");
printf("\n 3.在该顺序表中进行顺序查找某一元素，查找成功返回1，否则返回0");
printf("\n 4.判断该顺序表中元素是否对称，对称返回1，否则返回0");
printf("\n 5.该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数");
printf("\n 0.退出");
printf("\n ******************************************************************\n");
printf("\n请输入选择序号：");
scanf("%d",&n);
switch(n)
{
case 0:
return 0;
case 1:
BuildList(List);
break;
case 2:
ShowList(List);
break;
case 3:
int X;
printf("请输入要查找值：X=");
scanf("%d",&X);
FindList(List,X);
break;
case 4:
Duichen(List);
break;
case 5:
PaixuList(List);
break;
default:
printf(" 请输入数字0-5 \n");
}
}
return 0;
}
三、运行结果
1）程序主界面
2）选择1建立顺序表
3）选择2遍历顺序表
4）选择3查询元素X
5）选择4判断是否对称
6）选择5奇数在前，偶数在后
7）选择0退出
