数据结构 线性表操作实验报告范文.docx

数据结构 线性表操作实验报告 《数据结构》实验报告 实验题目：线性表的操作 实验目的：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 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->datadata) { 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.经过一次上机实践，我认为实践课很重要，上理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的 教师评语： 实验成绩： 指导教师签名： 批阅日期： 。