《数据结构》上机实验指导

《《数据结构》上机实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》实验指导书方义秋编著计算机综合实验中心目录《数据结构》上机实验的目的和要求3实验一、单链表的插入和删除.4实验二、二义树操作.8实验三、图的遍历操作.72实验四、排序.19实验五、查找.25《数据结构》上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1）输入的形式和输出值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入输出结果和错谋的输入及输出结果。2、概要设计：说明

2、用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。4、调试分析：（1）调试过程中所遇到的问题及解决方法；（2）算法的时空分析；（3）经验与体会。5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、测试结果：列出对丁给定的输入所产牛的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。实验一、单链表的插入和删除一、目的:了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基木算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输

3、入的字符串，先找到相应的结点,//定义结点〃结点的数据域为字符串〃结点的指针域三、示例程序：#include/zstdio.h"#include/zstring.h"Sinclude^stdlib.h"#include"ctype.h〃typedefstructnode{chardata[10];structnode*next;}ListNode;typedefListNode*LinkList;LinkListCreatListRl();ListNode*LocateNode();voidDeleteList();voidprintlist();voidDeleteAl1();//=====

4、=====主函数==============//口定义LinkList单链表类型//函数，用尾插入法建立带头结点的单链表//函数，按值查找结点//函数，删除指定值的结点//函数，打印链表中的所有值//函数，删除所有结点，释放内存voidmain()char*ch,*num;LinkListhead;head=CreatListRl();//用尾插入法建立单链表，返冋头指针printlist(head);//遍历链表输出其值printf(z，Deletenode(y/n)：z，);//输入“y”或“n”去选择是否删除结点scanf("%s",nurn);if(strcmp(num,"y")=0

5、

6、

7、strcmp(num,"Y")=0){printf(/zPleaseinputDeletedata:");scanfch);//输入要删除的字符串DeleteList(head,ch);printlist(head);DeleteAll(head);//删除所冇结点，禅放内存〃二====二用尾插入法建立带头结点的单链表-=========LinkListCreatListRl(void){char*ch;LinkListhcad=(LinkList)maHoc(sizeof(ListNode));//生成头结点ListNode*s,*r,*pp;r=head;r-〉next二NULL;pri

8、ntf(Z/Input#toend”)；〃输入代表输入结束printf(Z，P1easeinputNode_data:，z);scanf(〃%s〃,ch);//输入各结点的字符串whi1e(strcmp(ch,"#")!=0){pp=LocateNode(head,ch);//按值查找结点，返回结点指针if(pp==NULL){//没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizoof(ListNode));strcpy(s->data,ch);r->noxt=s;r=s;r->next=NULL;}printf("Input#toend");printf("Ple

9、aseinputNodedata:");seanf(〃％s：ch);}returnhead;//返冋头指针}//==========按值查找结点，找到则返冋该结点的位置，否则返冋NULL—™ListNode*Locateode(LinkListhead,char*key){ListNode*p=head->next;//从开始结点比较whi1e(strcmp(p->data,key)!=0&&p