《《数据结构》 实验指导书》由会员分享，可在线阅读，更多相关《《数据结构》 实验指导书（17页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验指导书软件学院2011年9月概述实习目的和要求数据结构在计算机科学中是一门实践性较强的专业基础课，上机实习是对学生的 一种全面综合训练，是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。实 习着眼于原理与应用的结合，使学生学会把学到的知识用于解决实际问题，起到深化理解 和灵活掌握教学内容的目的。同时，通过本课程的上机实习，使学生在程序设计方法及上 机操作等基本技能和科学作风方面受到比较系统和严格的训练。实习包括的步骤1简要描述题目要求，对问题的描述应避开算法及所涉及的数据类型，只是对所需 完成的任务做出明确的陈述，例如输入数据的类型、值的范围以及输入的形式，输出数据 的类型
2、、值的范围以及输出的形式。2选定数据结构，写出算法，根据自顶向下发展算法的方法，首先描述算法的基本 思想，然后进行算法细化，再对所设计的算法的时间复杂性和空间复杂性进行简单分析。3. 准备好上机所需的程序，选定一种程序设计语言（如C语言），手工编好上机程序， 并进行反复检查，使程序中的逻辑错误和语法错误减少到最低程度。对程序中有疑问的地 方，应做出标记，以便在上机时给予注意。4. 上机输入和调试程序，在调试程序过程中除了系统的问题以外，一般应自己独立 解决。在程序调试通过后，打印输出程序清单和运行结果。5. 上机结束后，总结和整理实习报告。实习报告的内容1. 简述题目要解决的问题是什么，并说明
3、输入和输出数据的形式。2. 简述存储结构和算法的基本思想。3. 列出调试通过的源程序。4. 列出上面程序对应的运行结果。5. 分析程序的优缺点、时空性能以及改进思想，写出心得体会。实验一 线性表一目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式 存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通 过，并观察其结果，然后独立完成后面的实习题。二例题问题描述 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出 字符串。输入 初始字符串，插入位置，插入字符，删除字符。输出 已建立链表(字符串)，插入字符后链表，删
4、除字符后链表，逆转后链表。存储结构采用链式存储结构算法的基本思想 建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插 到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前； 删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转： 从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表： 从链表的第一个结点开始，依次打印各个结点的数据域。参考源程序#define NULL 0typedef struct nodechar a;struct node *link;node,*nodelink;void
5、readlink(nodelink head)nodelink p,q;char c;p=head;printf(Input a linktable(a string):); scanf(%c,&c);if (c=n)printf(This string is empty ); while(c!=n)q=(nodelink)malloc(sizeof(node);q-a=c;p-link=q;p=q; scanf(%c,&c); p-link=NULL;void writelink(nodelink head)nodelink q;if (head-link=NULL) printf( Thi
6、s link is empty n); for(q=head-link;q;q=q-link)printf(%c,q-a); printf(n);int insert(nodelink head,char k1,char k2) nodelink p,q;p=head-link; while(p-a!=k1&p) p=p-link;if(p)q=(nodelink)malloc(sizeof(node);q-a=k2; q-link=p-link; p-link=q;return 1;else printf(There is no %cn,k1); return 0;int delete(no
7、delink head,char k)nodelink p,q;q=head;p=head-link;while(p-a)!=k)&p)q=q-link;p=p-link;if(p)q-link=p-link;return 1;elseprintf(There is no %cn,k); return 0;void opside(nodelink head)nodelink p,q;p=head-link;while(p-link)q=p-link; p-link=q-link; q-link=head-link; head-link=q;main()char k1,k2,k3;nodelin
8、k head;head=(nodelink)malloc(sizeof(node); head-link=NULL;readlink(head);if (head-link!=NULL)printf(Build link is :); writelink(head); if (head-link!=NULL)printf(Please input a char you want to insert after:); k1=getch();printf(%cn,k1); printf(Please input a char you want to insert:);k2=getch(); pri
9、ntf(%cn,k2);if (insert(head,k1,k2) printf(After %c insert %c,link is:,k1,k2); writelink(head); printf(Please input a char you want to delete:); k3=getch();printf(%cn,k3);if (delete(head,k3) printf(after delete %c,link is:,k3); writelink(head);if (head-link!=NULL) printf(Opsite result is :); opside(h
10、ead);writelink(head); free(head); 三实习题1. 设顺序表A中的数据元素递增有序，试写一程序，将c插入到顺序表的适当位置上， 使该表仍然有序。2. 用单链表ha存储多项式A(x)=a0+a1x1+a2x2+a xn(其中al为非零系数)，用单链表012nIhb存储多项式B (x ) =b0+b1xl+b2x2+b xm(其中b.为非零系数)，要求计算C (x )012mj=A (x ) +B (x )，结果存到单链表he中。试写出程序。3. 设有n个人围坐在一个圆桌周围，现从第个人开始报数，数到第m的人出列，然后 从出列的下一个人重新开始报数，数至m的人又出列，
11、如此重复，直到所有的人全部 出列为止。Josephus问题是：对于任意给定的n, m，s,求出按出列次序得到的n个人 员的顺序表。实验二 树一目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学 及其它工程技术中的应用。二例题问题描述 任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。输入 一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD. EH. CF. I. G.。输出若为空二叉树，则输出:THIS IS A EMPTY BINARY TREE。若二叉树不空，
12、按后序序列输出，对上例，输出结果为:DHEBIFGCA。存储结构采用二叉链表存储。算法的基本思想 采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树， 直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点 参考源程序#include#includestruct nodechar info;struct node *llink,*rlink;typedef struct node NODE;NODE *creat()char x;NODE *p;scanf(%c,&x);printf(%c,x);if(x!=.)p=(NODE *)malloc(si
13、zeof(NODE); p-info=x;p-llink=creat(); p-rlink=creat();elsep=NULL; return p;void run(NODE *t)if(t)run(t-llink);run(t-rlink); printf(%c,t-info);main()NODE *T;printf(PLease input a tree:n);T=creat(); printf(n);if(!T)printf(This is a empty binary tree.);else printf(The result of post travese is:n ); run
14、(T);printf(n);三实习题1 编写递归算法，计算二叉树中叶子结点的数目。2. 编写递归算法，在二叉树中求位于先序序列中JK个位置的结点。3 将上述例题用非递归程序实现。实验三 图一目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的 应用。二例题问题描述给定一个图，设计一个程序，找出一条从某一顶点到另一顶点B边数最少的一条路 径。输入图的顶点个数N,图中顶点之间的关系及要找的路径的起点和终点B。输出若A到B无路径，则输出There is no path,否则输出A到B路径上各顶点。存储结构图采用邻接矩阵的方式存储。算法的基本思想采用广度优先搜索的方法,从顶点A开始，依次访问与A邻接的顶点VA, Va2,.,Vak,A1 A2AK访问遍之后，若没有访问B,则继续访问与VA邻接的顶点VA , VA ,.,VA，再访问与VAA1 A11 A12 A1M A2 邻接顶点.，如此下去，直至找至最先到达B点的路径，一定是边数最少的路径。实 现时采用队列记录被访问过的顶点。每
