《《数据结构》实验指导书(源代码)》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书(源代码)（50页珍藏版）》请在金锄头文库上搜索。
1、1实验一 线性表的链式存储结构一、实验目的： 1掌握线性表的链式存储结构。 2熟练地利用链式存储结构实现线性表的基本操作。 3能熟练地掌握链式存储结构中算法的实现。 二、实验内容：1用头插法或尾插法建立带头结点的单链表。2实现单链表上的插入、删除、查找、修改、计数、输出等基本操作 。三、实验要求：1. 根据实验内容编写程序，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果） 。 四、实验学时：2 学时 五、实验步骤： 1进入编程环境，建立一新文件； 2. 参考以下相关内容，编写程序，观察并分析输出结果。 定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改
2、、计数、 输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的 结果输出，以查看每一种操作的效果。 部分参考程序/单链表的建立(头插法)，插入，删除，查找、修改、计数、输出#include#define elemtype int struct link elemtype data；/元素类型link *next； /指针类型，存放下一个元素地址 ;/头插法建立带头结点的单链表link *hcreat() link s,p;elemtype i;couti； p=new link；p-next=NULL；while(i) /当输入的数据不为 0 时，循环建单链表s=ne
3、w link；s-data=i；s-next=p-next；p-next=s；cini； 2return p； /输出单链表 void print(1ink *head) 1ink *p；p=head-next；while(p-next!=NULL)coutdata” ； /输出表中非最后一个元素 p=p-next；coutdata； /输出表中最后一个元素coutnext；while(p!=NULL) void main() int n；elemtype x，y；link *p， *q；p=hcreat()； /头插法建立链表print(p)； /输出刚建立的单链表4couty；delete
4、l(p，y)；print(p)； /输出删除后的结果coutx；couty；insert(p，x，y)；print(p)； /输出插入后的结果coutxy；change(p，x，y)；print(p)；coutx；q=Locate(p，x)；if(q=NULL)cout #define elemtype int struct link elemtype data；/元素类型link *next；/指针类型，存放下-个元素地址 ；/尾插法建立带头结点的单链表 link *rcreat()link *s， *p， *r；elemtype i； couti;p=r=new link；p-next=N
5、ULL；while(i)s=new link；5s-data=i；r-next=s；r=s；cini； r-next=NULL； return p； /输出单链表 void print(1ink *head) link *p；p=head-next；while(p-next!=NULL)coutdata”; /输出表中非最后一个元素p=p-next；)coutdata； /输出表中最后一个元素coutnext; j+；return p；void delete I(1ink *head，elemtype x) /在 head 为头指针的单链表中，删除值为 x 的结点link *p, *q；q=h
6、ead；p=head-next；while(p!=NULL) void main() int n;7link p,q; p=rcreat()；/尾插法建立链表 print(p)； /输出刚建立的单链表couty； deletel(p，y)； print(p)； /输出删除后的结果coutx；couty； insert(p，x，y)； print(p)； /输出插入后的结果coutxy； change(p，x，y)； print(p)；coutx； q=Locate(p ,x)；if(q=NULL)cout#includetypedef struct nodeint num；struct nod
7、e *next； linklist；以下是主程序#include”h1h” 输出循环链表的信息 void output(linklist *head) linklist *p； p=head-next； while(p!=head)printf(”d” ，p-num)； p=p-next；9printf(”n”)； /建立单循环链表 Linklist *creat(int n) int k;linklist *head,*r,*p；p=(linklist*)malloc(sizeof(linklist)；head=p；r=p；p-next=p； for(k=1；knum=k；r-next=p；
8、r=p；p-next=head； return(head)； 逆置函数 linklist *invert(linklist *head) Linklist *p，*q，*r； p=head-next； q=head； while(p!=head) r=q；q=p；p=p-next；q-next=r；head-next=q；return(head)；void main()int n；Linklist *head；printf(“输入所建立的循环链表的结点个数：n”)；10scanf(“%d”，n)；head=creat(n)；printf(”输出建立的单循环链表：n”)；output(head)
9、；printf(”现在进行逆置! n”)；head=invert(head)；printf(”输出进行逆置运算后的单循环链表的结点信息! n”)；output(head)；/双向链表参考程序/以下是头文件 hhh 的内容#include#includetypedef struct dupnodeint data；struct dupnode *next,*prior； dulinklist；/以下是主程序的内容 #include”hhh” /create 函数用来构建双向链表 dulinklist *create() dulinklist *head,*p，*r;int i，n； head=(
10、dulinklist*)malloc(sizeof(dulinklist )； head-next=NULL； head-prior=NULL； r=head； printf(“请输入所建双向链表中结点的个数：n”)； scanf(“d”,n)； for(i=l；idata)；p-next=NULL；r-next=p；p-prior=r；r=r-next； return(head)； 11/find 函数用来实现在双向链表中按序号查找某个结点的功能。 void find(dulinklist *h) int k,i； dulinklist *p； p=h； i=0：printf(”输入要查找结
11、点的序号：n”)；scanf(”%d”,scanf(”%d%d” ，k，x)；head=insdulist(head，k，x)；output(head)；break；case 4：printf(”输入要删除的结点的序号. n”)；scanf(”%d，k)； head=deledulist(head，k)； output(head)； break； case 5: flag=0； /while 循环结束 此程序不论是插入、查找还是删除运算均是按序号的方式来处理，当然也可改为按结 点的值来作相应的处理，试修改以上程序实现按值操作的功能。六、选作实验利用单循环链表存储结构，解决约瑟夫（Josephu
12、s）环问题。即：将编号是 1,2,n(n0)的 n 个人按照顺时针方向围坐一圈，每人持有一个正整数密码。开始时任选一 个正整数作为报数上限值 m,从某个人开始顺时针方向自 1 开始顺序报数，报到 m 时停止 报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重 新从 1 报数，如此下去，直到所有的人全部出列为止。令 n 最大值取 30。设计一个程序， 求出出列顺序，并输出结果。14实验三实验三 树形结构树形结构一、实验目的：1掌握二叉树的数据类型描述及二叉树的特性。 2掌握二叉树的链式存储结构(二叉链表)的建立算法。 3掌握二叉链表上二叉树的基本运算的实现。 二
13、、实验内容：从以下 1、2 和 3、4 中各选择一项内容 1. 用递归实现二叉树的先序、中序、后序 3 种遍历。 2. 用非递归实现二叉树的先序、中序、后序 3 种遍历。 3. 实现二叉树的层次遍历。 4.将一棵二叉树的所有左右子树进行交换。 三、实验要求：1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果） 。 四、实验学时：4 学时 五、实验步骤：1进入编程环境，建立一新文件； 2. 参考以下相关内容，编写程序，观察并分析输出结果。 将建立二叉树及先序、中序、后序 3 种遍历算法都写成子函数，然后分别在主函 数中调用它，但在建立二又树中，必须把
14、二叉树看成完全二叉树的形式。若不是 完全二叉树，则在输入数据时，用虚结点(不存在)表示(本算法中，用“， ”号代替)。 用非递归法实现二叉树的遍历 非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈 顶指针。 实现二叉树的层次遍历用一个一维数组代替队列，实现二叉树的层次遍历。 将一棵二叉树的所有左右子树进行交换。本算法只要增加一个实现二叉树左右子树交换的子函数即可。为了便于查看，在主 函数将交换前后的三种遍历效果，分别输出。以下为部分参考程序： /递归实现二叉树的 3 种遍历 #include typedef char elemtype； struct bitree 定义
15、二叉树数据类型 elemtype data； /结点信息 bitree *lchild，*rchild； /左右孩子 ; bitree *create() /建立二叉链表 bitree *root, *s，*q100； /q 为队列，最大空间为 100 int front=l，rear=0； /队列头、尾指针15char ch； root=NULL；coutch； while(ch!=#) s=NULL； if(ch!=,)s=new bitree；s-data=ch；s-lchild=NULL；s-rchild=NULL；rear+；qrear=s； /进队if(rear=1) root=s； else if(s!=NULL)/按层次遍历二叉树(建立二叉链表同前) void lorder(bitree *t) bitree q100，*p； /q 代表队列 int f,r; /f，r 类似于队列头、尾指针 q1=t； f=r=l； coutdatalchild!=NULL) r+；qr=p-lchild； /入队if p-
