《《数据结构》实验指导书》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验指导书1目录1、实验目的.12、实验要求.23、实验环境.24、实验 一.35、实验 二.56、实验 三.67、实验 四.6实验目的2数据结构实验课是地理信息系统必修课“数据结构”的配套课 程。上机实习是对学生的一种全面综合训练，是与课堂听讲、自学 和练习相辅相成的必不可少的教学环节。本实验课着眼于原理与应 用的结合，使学生学会如何把学到的理论知识应用于解决实际问题。 实验目的是软件设计的综合训练，包括问题分析、总体结构设计、 用户界面设计、程序设计基本技能和技巧，以及一整套软件工程规 范的训练和科学作风的培养。帮助学生巩固和加深理解所学过的理 论知识，熟悉验证常用数据结构的方法与
2、步骤，培养学生分析和解 决现实世界问题在计算机中如何表示和处理的能力，使学生具备良 好的程序设计技能。能够熟练运用 C 语言验证常用数据结构及相应 算法。面对实际问题，能够选择合适的数据结构，并设计相应的算 法。实验要求给出一个现实世界的应用问题要求学生在正确分析问题的基础上， 完成以下任务： 1、熟悉线性表的存储方法及基本操作； 2、熟悉栈和队列的存储方法及基本操作，能综合运用栈和队列 解决实际问题； 3、熟悉树的基本操作； 4、熟悉查找和排序的常用方法。实验环境数据结构实验要求如下环境，软件：Windows 2000、Turboc2。硬件：可供学生上机的 PC 机若干。实验学时数课外上机
3、8 学时。 实 验 一3线性表及其应用 （2 学时） 实验目的：实验目的：熟练掌握线性表的基本操作在两种存储结构上的实现。掌握建立顺序表与链表的基本方法。掌握显示顺序表和链表元素的基本方法。实验内容：实验内容：链表与顺序表的构建、插入、删除等基本操作。 （1）在开始实验之前，先建立一个文件夹（可用自己的班级加 学号或姓名命名）。 （2）建立一个顺序表（或链表），要求从键盘输入 10 个整数 （每一个用空格隔开），负数为输入结束标志。（3）对该线性表进行插入、删除、显示等基本操作 将源程序以实验 1-1 为文件名保存在自己的文件夹里面。 以存储某门课程的成绩为例，线性表链式存储结构的操作(参考)
4、： # define Null 0 # define LEN sizeof(struct Lnode) Typedef struct Lnodeint data;Struct Lnode *next;linklist;Int n;Linklist *create() /*创建线性表*/linklist *head;Linklist *P1,*p2;P1=(linklist *)malloc(LEN);scanf(“%d”,if(p1-data0) head=p1;else head=NULL; return(head);while(p1-data0)p2=p1;P1=(linklist *)m
5、alloc(LEN);scanf(“%d”,p2-next=p1;p2-next=NULL;return(head); Linklist *InsertLinklist(linklist *head, int x, int k) /*插入操作*/linklist *p, *pre, *s;int j;j=1;p=head;pre=NULL;while(p!=NULL 4j+;if (j!=k)printf(“The position is out of the linklist!”);return(NULL);s=(linklist *)malloc(LEN);if(s=Null)printf
6、(“have not enough capacity!”);return(NULL);s-data=x; if(pre=Null)s-next=head;head=s;elses-next=pre-next;pre-next =s;return head;Linklist *DeleteLinklist(linklist *head, int x)/*删除操作*/linklist *p,*q;q=Null;p=head;while(p!=Null p=p-next;if(p=NULL)printf(“The position doesnt exist!”);return(NUll);elsei
7、f(q=Null) head=head-next;elseq-next=p-next;free(p);return(head);printout(linklist *head) /*打印输出*/linklist *p;p=head;while(p-next!=0)printf(“%dn”, p-data);p=p-next; printf(“%d”,p-data);main()linklist *p,*head;int cmd,y,i,t;printf(“n please input data, negative data(like “-1”) forinput endn”);p=head=c
8、reat();loop: printf(“n input 1 for print data, 2 for insert data,53 for delete data,4 for quiten”)Scanf(“%d”,if(cmd=1)printout(head);goto loop;else if(cmd=2)printf(“please input the data and position to insert:n”);scanf(“%d,%d”,Insertlinklist(head,y,i);Goto loop;else if(cmd=3)printf(“please input th
9、e data to delete:n”);Scanf(“%d”,Deletelinklist(head,t);goto loop;实 验 二 栈和队列的应用 （2 学时） 实验目的：实验目的：深入了解栈和队列的特性，并在实际背景中灵活应用栈和队列。 实验内容：实验内容：Hanoi 塔问题。问题描述：有 A,B,C 三个塔座，A 上套有 n 个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号 1,2,3n。要求将 n个圆盘从 A 移到 C，叠放顺序不变，移动过程中遵循下列原则：（1）每次只能移一个圆盘；（2）圆盘可在三个塔座上任意移动；（3）任何时刻，每个塔座上不能将大盘压到小盘上。 解决方法
10、：n=1 时，直接把圆盘从 A 移到 C；n1 时，先把上面 n-1 个圆盘从 A 移到 B,然后将 n 号盘从 A 移到 C,再将 n-1 个盘从 B 移到 C。即把求解 n 个圆盘的 Hanoi 问题转化为求解 n-1 个圆盘的 Hanoi 问题，依次类推，直至转化成只有一个圆盘的 Hanoi 问题 程序（参考）：int c; void hanoi(int n,char x,char y,char z) if(n=1)move(x,1,z);elsehanoi(n-1,x,z,y); move(n,x,z);hanoi(n-1,y,x,z); move(char s,int a, char
11、 c) printf(“%d move i% from %c to %cn”, +c,a,s,t) main() char a,b,c;6int n; c=0; printf(“*n”);printf(“Input number of disks”);scanf(“%d“,printf(”Steps : %3d disks”,m);a=A; b=B; c=C ;hanoi(n,a,b,c); 实 验 三 树及其应用 （2 学时） 实验目的：实验目的：熟悉树的各种存储结构特性，应用树结构解决具体问题。掌 握构造二叉链表树的算法；掌握遍历二叉树的三种递归算法。掌握 基于先序遍历构造二叉链表的算法。
12、实验内容：实验内容： 1.二叉树的构造与遍历： (1)建立二叉链表树：从键盘输入结点编号及对应的结点值，分 别以 0 和#作为结束标志。（2）分别调用先序、中序和后序遍历递归算法对前面建立好的 二叉链表树进行遍历。要求分别显示遍历后的结点序列。 2.二叉树的构建（基于先序）：构造基于先序遍历的二叉链表： 按先序遍历规则，从键盘连续输入二叉树的先序序列，若无孩子结 点，则用#代替，以示空指针的位置；然后调用构造二叉链表的递归 算法，从屏幕显示该二叉链表的先序序列。实 验 四查找和排序（2 学时） 实验目的：实验目的：熟悉典型的查找与排序算法。实验内容：实验内容：内部排序法比较。 待排序的数据类型
13、定义： #define MAXSIZE 20 Typedef int KeyType; Typedef structKeyType key;InfoType otherinfo;RedType; typedef structRedType rMAXSIZE+1;int length; SqList;7插入排序： Void InsertSort(SqList i=pivotkey）- -high;L.rlow 交换 L.rhighwhile(lowhigh L.rlow 交换 L.rhighreturn low; Void QSort(SqList QSort(L, low, pivotloc-1);QSort(L, pivotloc+1,high); Void QuickSort(SqList
