算法与数据结构实验指导书.doc

西安工业大学经济管理学院算法与数据结构实验指导书算法与数据结构实验指导书西安工业大学商务信息系马军平目 录算法与数据结构实验大纲1算法与数据结构实验说明2实验一、线性表操作6实验二、栈和队列的应用11实验三、树和二叉树的操作18实验四、图的操作21实验五、各种查找和排序操作27算法与数据结构实验大纲一. 课程名称：数据结构及算法分析课程编号：课程学时：32实验时数：16二. 所属实验室名称：经管学院实验中心三. 实验教材及参考书：【1】数据结构（c语言版） 清华大学出版社【2】本实验指导书四. 实验内容和目的：掌握四种基本数据结构：集合、线性结构、树形结构、网状结构在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。要求学生具有编制相当规模的程序的能力。养成一种良好的程序设计风格。五. 考核方式：上机编程并运行通过、实验报告。六. 实验环境：硬件最低要求：586微型计算机，主频450mhz以上，内存64mb以上，硬盘10g，有软驱。每个学生每次上机实验使用一台计算机。软件：c语言或visual c+6.0七. 实验项目及安排序号实验名称类别学时目的与安排备注必选选开1线性表4插入、删除、合并、排序、查找2栈与队列44树及应用2递规、非递规遍历5图及应用4遍历算法、最小生成树6排序查找2排序、查找算法比较分析30算法与数据结构实验说明一、实验的地位与作用数据结构 是计算机、信息管理和电子商务专业一门重要的专业技术基础课程，是计算机、信息管理和电子商务专业的一门关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了一些性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。数据结构课程内容丰富，学习量大，给学习带来一定的困难；所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；隐含在各部分的技术和方法丰富，也是学习的重点和难点。根据数据结构课程本身的技术特性，设置数据结构课程实验实践环节十分重要。通过实验实践内容的训练，突出学生程序思维训练和动手上机调试程序的能力, 目的是提高学生组织数据及编写大型程序的能力二、实验目的使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在总是分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。三、实验要求1 、阅读实验指导书每一次实验从阅读实验指导书开始。对于本次实验的实验目的、实验题目、实现提示以及思考题目、选做题目等应认真了解。2 、算法设计分析实验题目，参考实现提示，进行算法设计。3 、程序设计根据已完成的算法，用c 语言进行程序设计。4 、调试和测试将所编程序在计算机上调试通过，并选取若干组测试数据对程序进行尽可能全面的测试。5 、整理完成实验报告实验报告一般包括下列内容：l 实验者姓名、学号、专业和班级，课程名称（数据结构课程设计），实验日期等；l 本交实验的实验编号及实验名称（例如：实验一 线性表的应用）l 本次实验的实验目的；l 本次实验的实验地点、设备编号、硬件及软件环境；l 程序结构的描述及各模块的规格说明；l 主要算法及其基本思想；l 调试过程简述（调试过程是否顺利，遇到些什么问题，如何解决的，以及上机操作所花费的时间等）；l 测试数据和相应输出的客观纪录，对运行结果的分析讨论。四、实验环境多媒体微型计算机pentium iv 1ghz 以上，256mb ram 以上;windows/2000,？xp turbo c 或visual c+6.0 五、考核方式采用上机情况、程序质量、实验报告相结合的形式六、实验步骤随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的5 个步骤：1 、问题分析和任务定义通常，实验题目的陈述比较简洁，或者说有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。2 、数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类c 语言写出过程或函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。3 、编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。如何编写程序才能较快地完成调试是特别要注意的问题。程序的每行不要超过60 个字符。每个过程（函数）体一般不要超过40 行，最长不得超过60 行，否则应该分割成较小的过程（函数）。要控制if 语句连续嵌套的深度，分支过多时应考虑使用switch 语句。对函数功能和重要变量进行注释。一定要按格式书写程序，分清每条语句的层次，对齐括号，这样便于发现语法错误。在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的 “精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。对一般的程序设计者而言，当编写的程序长度超过50 行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先检查单个模块）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。4 上机准备和上机调试上机准备包括以下几个方面：l 熟悉c 语言用户手册或程序设计指导书。l 注意turbo c 、vc 与标准c 语言之间的细微差别。l 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便 顺利进行上机的基本活动。l 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。学生应该熟练运用高级语言的程序调试器debug调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。在调试过程中可以不断借助debug 的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思冥想”，而应借助系统提供的调试工具确定错误。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。5 、总结和整理实验报告实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：（1）需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。（2）概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次( 调用) 关系。（3）详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法( 伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序) ；画出函数和过程的调用关系图。（4）调试分析内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；算法的时空分析( 包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。用户使用说明，说明如何使用你编写的程序，详细列出每一步的操作步骤。（5）测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。（6）附录带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写( 当然可以也应该最后用实验报告纸誊清或打印) 七、实验报告示例实验名称：实验一 线性表的操作一、实验目的1、掌握用上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验环境硬件：pc 微型计算机、256m以上内存，40g以上硬盘。软件：windows xp，turbo c/c+ 三、实验内容线性表基本操作的实现当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。四、实验步骤1、本实验的程序清单2、本程序运行的结果根据各位同学的实际调试数据编写3、行分析和改进分析和改进的内容附上五、实验小结实验过程中的体会和收获。实验一、线性表操作一、实验目的1掌握用 c语言调试程序的基本方法。2掌握线性表的基本运算，如插入、删除等。二、实验内容1线性表在顺序存储结构上的插入元素，删除元素运算2线性表在链式存储结构上的建链表，插入结点，删除结点运算三、实验要求1 1 c+/c完成算法设计和程序设计并上机调试通过。2 2 撰写实验报告，提供实验结果和数据。3 3 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）五、程序运行情况写出输入数据及运行结果六、源程序清单 。程序1：顺序存储的线性表和运算#include#define maxsize 100int listmaxsize;int n;/*insert in a seqlist*/int sq_insert(int list, int *p_n, int i, int x)int j;if (i*p_n) return(1);if (*p_n=maxsize) return(2);for (j=*p_n+1; ji; j-)listj=listj-1;listi=x;(*p_n)+;return(0);/*delete in a seq list*/int sq_delete(int list, int *p_n, int i)int j;if (i=*p_n) return(1);for (j = i+1; j=*p_n; j+)listj-1 = listj;(*p_n)-;return(0);void main()int i,x,temp;printf(please input the number for nn);printf(n=);scanf(%d,&n);for (i=0; i=n; i+)printf(list%d=,i); scanf(%d,&listi);printf(the list before insertion isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to insert a valuenposition=);scanf(%d,&i);printf(please input the value you want to insert.nx=);scanf(%d,&x);temp=sq_insert(list,&n,i,x);switch(temp)case 0:printf(the insertion is successful!n);printf(the list is after insertion isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%dn,n);break;case 1:case 2:printf(the insertion is not successful!n);break;/*deleting*/printf(the list before deleting isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to delete a valuenposition=);scanf(%d,&i);temp=sq_delete(list,&n,i);switch(temp)case 0:printf(the deleting is successful!n);printf(the list is after deleting isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%d,n);break;case 1:printf(the deleting is not successful!);break;程序2链式存储的线性表和运算#include#includestruct nodechar data;struct node *next;typedef struct node node;/*this function creates a link_list with n nodes.*/node *create_link_list(int n)int i;node *head, *p, *q;if (n=0) return null;head = (node *) malloc(sizeof(node);p = head; printf(please input %d chars for the link listn,n);for (i=0; idata);q=(node *)malloc(sizeof(node);printf(test3n);p-next=q;p=q;scanf(%c ,&(p-data);getchar();p-next=null;return (head);/*this function inserts a node whose value is b*/*before the node whose value is a, if the node is not exist,*/*then insert it at the end of the list*/void insert(node *p_head, char a, char b)node *p, *q;q = (node *)malloc(sizeof(node);q-data = b;q-next =null;if (* p_head = null) * p_head = q;elsep=(node*)malloc(sizeof(node);p = * p_head;while (p-data != a & p-next != null)p = p-next;q-next = p-next;p-next = q;/*the function deletes the node whose value is a,*/*if success, return 0, or return 1*/int deletenode(node *p_head, char a)node *p, *q;q=*p_head;if (q=null) return(1);if (q-data = a)* p_head = q-next;free(q);return (0);elsewhile (q-data != a & q-next != null)p = q;q = q-next;if (q-data = a)p-next = q-next;free(q);return(0);else return(1);void main()node *my_head,*p;/* create a link list with m nodes */int m;char ch_a,ch_b;printf(please input the number of nodes for the link_listnm=);scanf(%d,&m);getchar();printf(test1n);my_head = (node *) malloc(sizeof(node);my_head=create_link_list(m);/*output the link list*/printf(the link list is like:n);p=my_head;while (p != null)printf(%c ,p-data);p=p-next;printf(n);/*insert a node whose value is b before a*/printf(please input the position for an ch_a=);getchar();scanf(%c,&ch_a);getchar();printf(please input the value that you want to insertn ch_b=);scanf(%c,&ch_b);getchar();insert(&my_head,ch_a,ch_b);printf(the link list after insertion is like:n);p=my_head;while (p != null)printf(%c ,p-data);p=p-next;printf(n);/*delete a node whose value is a*/printf(please input the position for a a=);scanf(%c,&ch_a);getchar();deletenode(&my_head,ch_a);printf(the link list after deleting is like:n);p=my_head;while (p != null)printf(%c ,p-data);p=p-next;printf(n);实验二、栈和队列的应用一、实验目的1、掌握栈的特点(先进后出filo)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点(先进先出fifo)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵。二、实验内容1顺序栈的实现和运算2链栈的实现和运算3顺序队列的实现和运算4链式队列的实现和运算5循环队列的实现和运算三、实验要求1用c+/c完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）程序运行情况五、写出输入数据及运行结果六、源程序清单 。程序1：顺序栈的实现和运算#include#define maxn 26char stackmaxn;int top=0;int push(char x)if (top = maxn)return(1); stacktop+=x; return(0);int pop(char *p_y)if (top = 0)return(1); *p_y = stack-top; return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to pushn);scanf(%c,&ch_x);while(ch_x!=0)if (push(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to pushnch_x=);getchar();scanf(%c,&ch_x);i=0;while(stacki!=0)printf(%c , stacki);i+;if (pop(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(the pop char is %cn,ch_y);for (i=top-1; i=0; i-)printf(%c , stacki);程序2：链栈的实现和运算#include #include struct nodechar data; struct node *link;typedef struct node node;node * top = null;void push_l(char x)node *p; p = (node * )malloc(sizeof(node); p-data = x; p-link = top; top = p;int pop_l(char *p_y)node *p; if (top = null)return(1); * p_y = top-data; p = top; top = top-link; free(p); return(0);void main()node *p;char ch_x,ch_y;printf(input the char you want to pushn);scanf(%c,&ch_x);while(ch_x!=0)push_l(ch_x);getchar();scanf(%c,&ch_x);p=(node*)malloc(sizeof(node);p=top;while(p!=null)printf(%c ,p-data);p=p-link;printf(n);if (pop_l(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(the pop char is %cn,ch_y);p=(node*)malloc(sizeof(node);p=top;while(p!=null)printf(%c ,p-data);p=p-link;printf(n);程序3：顺序队列的实现和运算#include#define maxn 26char qmaxn;int head = -1, tail = -1;int en_queue(char x )if (tail = maxn-1)return(1);q+tail = x;return(0);int de_queue(char *p_y )if (head = tail)return(1);*p_y = q+head;return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)if (en_queue(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to enqueuench_x=);getchar();scanf(%c,&ch_x);i=1;while(qi!=0)printf(%c , qi);i+;if (de_queue(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(the dequeue char is %cn,ch_y);for (i=head+1; i=tail; i+)printf(%c , qi);程序4：链式队列的实现和运算#include#includestruct nodechar data; struct node * link;typedef struct node node;node *head, *tail;void en_queue_l(char x)node *p; p = (node *)malloc(sizeof(node); p-data = x; p-link = null; if (head = null)head = p; elsetail-link = p; tail = p;int de_queue_l(char *p_y)node *p; if (head = null)return(1); *p_y = head-data; p = head; head = head-link; free(p); return(0);void main()node *p;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)en_queue_l(ch_x);getchar();scanf(%c,&ch_x);p=(node*)malloc(sizeof(node);p=head;while(p!=null)printf(%c ,p-data);p=p-link;printf(n);if (de_queue_l(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(the dequeue char is %cn,ch_y);p=(node*)malloc(sizeof(node);p=head;while(p!=null)printf(%c ,p-data);p=p-link;printf(n);程序5：循环队列的实现和运算#include#include#define maxn 26char qmaxn;int head = 0, tail = 0;int en_c_q(char x)tail = (tail + 1) % maxn;if (tail = head)if (tail = 0) tail = maxn-1; else tail-;return(1);qtail = x;return(0);int de_c_q(char *p_y)if (head = tail) return(1); head = (head+1) % maxn; *p_y = qhead; return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)if (en_c_q(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to enqueuench_x=);getchar();scanf(%c,&ch_x);i=1;while(qi!=0)printf(%c , qi);i+;if (de_c_q(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(the dequeue char is %cn,ch_y);for (i=head+1; i=tail; i+)printf(%c , qi);实验三、树和二叉树的操作一、实验目的1进一步掌握树的结构及非线性特点，递归特点和动态性。2进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。二、实验内容1二叉树的实现和运算三、实验要求1用c+/c完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）程序运行情况五、写出输入数据及运行结果六、源程序清单 。程序1：二叉树的实现和运算#include #include #include typedef struct btnode char data; /*suppose the data fields type is char*/ struct btnode *lchild; /*left pointer field */ struct btnode *rchild; /*right pointer field */ node;void main()node *root,*q,n;node *create(node *p);void preorder(node *root);void inorder(node *root);void postorder(node *root); int t;q=&n;root=create(q);printf(at the first,we create a treen);printf(please input nodes of treen);if (root=null) printf(its an empty tree!n);else printf(n1.the preordetraverse n); printf( 2.the inordertraverse n); printf( 3.the postordertraverse n);printf( please choose a kind of ordern);scanf(%d,&t);switch (t) case 1: preorder(root); break;case 2: inorder(root); break;case 3:postorder(root); break;default: printf( the error!); node * create(node *p) /*create the structure of binary tree */ char ch;node *t; scanf(%c,&ch);if(ch= ) p=null;else p-data=ch; t=(node *)malloc(sizeof(node); p-lchild=create(t); t=(node*)malloc(sizeof(node); p-rchild=create(t); return p; void preorder(node *root) /*travel the tree using preorder */if (root!=null) printf( %c, root-data); preorder(root-lchild); preorder(root-rchild); return; void inorder (node *root) /*travel the tree using inorder */if (root!=null) inorder(root-lchild);printf( %c , root-data);inorder(root-rchild); return; void postorder(node *root) /*travel the tree using postorder */if (root!=null) postorder (root-lchild);postorder (root-rchild);printf( %c , root-data); return;实验四、图的操作一、实验目的1进一步掌握图的结构及非线性特点，递归特点和动态性。2进一步巩固图的三种存储结构和二种遍历方法、最小生成树的两种求解算法。二、实验内容1图的遍历2最小生成树3最短路径三、实验要求1用c+/c完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设