数据结构实验指导书源代码.pdf

《数据结构实验指导书源代码.pdf》由会员分享，可在线阅读，更多相关《数据结构实验指导书源代码.pdf（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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=new link；s-data=i；s-n

3、ext=p-next；p-next=s；cini；return p；/输出单链表 void print(1ink*head)1ink*p；p=head-next；while(p-next!=NULL)coutdata”；/输出表中非最后一个元素 p=p-next；coutdata；/输出表中最后一个元素 coutnext；while(p!=NULL)&(p-data!=x)p=p-next；return p；/在 head 为头指针的单链表中，删除值为 x 的结点 void deletel(1ink*head，elemtype x)1ink*p，*q；q=head；p=head-next；wh

4、ile(p!=NULL)&(p-data!=x)q=p；p=p-next；If(p=NULL)coutnext=p-next；delete(p)；/在头指针 head 所指的单链表中，在值为 x 的结点之后插入值为 void insert(1ink*head，elemtype x，elemtype y)link*p,*s;s=new link；s-data=y；if(head-next=NULL)/链表为空 head-next=s；s-next=NULL：p=Locate(head，x)；/调用查找算法 y 的结点 if(p=NULL)coutnext=p-next；p-next=s；/将单链

5、表 p 中所有值为 x 的元素修改成 y void change(1ink*p,elemtype x,elemtype y)link*q；q=p-next；while(q!=NULL)if(q-data=x)q-data=y；q=q-next；void count(1ink*h)/统计单链表中结点个数 1ink*p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；return n;void main()int n；elemtype x，y；link*p，*q；p=hcreat()；/头插法建立链表 print(p)；/输出刚建立的单链表 couty；del

6、etel(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)coutx”不在表中，找不到!”endl；else coutx”在表中，已找到!”endl；n=count(p)；cout”链表中结点个数为：”nendl：/单链表的建立(尾插法)、插入、删除、查找、修改、计数、输出#include#define elemtype int struct link elemtype data；/元素

7、类型 link*next；/指针类型，存放下-个元素地址；/尾插法建立带头结点的单链表 link*rcreat()link*s，*p，*r；elemtype i；couti;p=r=new link；p-next=NULL；while(i)s=new link；s-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；/输出表中最后一个元素 c

8、outendl；link*Locate(1ink*head,int x)/在单链表中查找第 link*p；p=head；int j=0；while(p!=NULL)&(jnext;j+；return p；void delete I(1ink*head，elemtype x)/在 head 为头指针的单链表中，删除值为 x 的结点 link*p,*q；q=head；p=head-next；while(p!=NULL)&(p-data!=x)q=p；x 个结点 p=p-next；)if(p=NULL)coutnext=p-next delete(p)；void insert(1ink*head，i

9、nt x,elemtype y)/在头指针 head 所指单链表中，在第 x 个结点之后插入值为 link*p，*s；s=new link；s-data=y；if(head-next=NULL)/链表为空 head-next=s；s-next=NULL：p=Locate(head，x)；/调用查找算法 if(p=NULL)coutnext=p-next；p-next=s；void change(1ink*p,elemtype x，elemtype y)/将单链表P中所有值为x的元素改成值为y link*q；q=p-next；while(q!=NULL)if(q-data=x)q-data=y；

10、q=q-next；void main()int n;link p,q;p=rcreat()；/尾插法建立链表 print(p)；/输出刚建立的单链表 couty；deletel(p，y)；print(p)；/输出删除后的结果 要删除的结点不存在 y 的结点 void count(1ink*h)/统计单链表中结点个数(1ink*p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；retum n;coutx；couty；insert(p，x，y)；print(p)；/输出插入后的结果 coutxy；change(p，x，y)；print(p)；coutx；q=

11、Locate(p,x)；if(q=NULL)coutx”不在表中,找不到!”endl；else coutx”在表中，已找到!”endl；n=count(p)；cout”链表中结点个数为：”nendl;六、选作实验 试设计一元多项式相加(链式存储)的加法运算。A(X)=7+3X+9X 8+5X 9 B(X)=8X+22X 7-9X 8 1 建立一元多项式；2 输出相应的一元多项式；3 相加操作的实现。实验二 循环链表的操作 一、实验目的：通过本实验中循环链表和双向链表的使用，使学生进一步熟练掌握链表的操作方式。二、实验内容：本次实验可以从以下两个实验中任选一个：1 建立一个单循环链表并实现单循环

12、链表上的逆置。所谓链表的逆置运算（或称为逆转运算）是指在不增加新结点的前提下，依次改变数据 元素的逻辑关系，使得线性表（ai,a2,a3，an）成为（an，a3,a2,ai）。2.构建一个双向链表，实现插入、查找和删除操作。三、实验要求：1.根据实验内容编写程序，上机调试、得出正确的运行程序。2.写出实验报告（包括源程序和运行结果）。四、实验学时：2 学时 五、实验步骤：1 进入编程环境，建立一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。建立一个带头结点的单循环链表，从头到尾扫描单链表 L,把p作为活动指针，沿 着链表向前移动，q 作为 p 前趋结点，r 作为 q 的前趋结点。

13、其中，q 的 next 值为 r；r 的 初值置为 head。双向链表的构造与单链表相同，至于它的插入与删除运算比单链表复杂，插入运算 需要 4 步操作，删除运算需要 2 步操作，注意语句的次序，不要任意交换位置，以免不能 正确插入或删除结点。部分参考程序/循环链表/头文件hi.h的内容#define NULL 0#include#include typedef struct node int num；struct node*next；linklist；/以下是主程序#include”h1 h”/输出循环链表的信息 void output(linklist*head)linklist*p；p=

14、head-next；while(p!=head)printf(”d”，p-num)；p=p-next；printf(”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；r=p；p-next=head；return(head)；/逆置函数 linklist*invert(linklist*head)Linklist*p，*q，*r；p=head-next；q=head；

15、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”)；scanf(“%d”，n)；head=creat(n)；printf(”输出建立的单循环链表：n”)；output(head)；printf(”现在进行逆置!n”)；head=invert(head)；printf(”输出进行逆置运算后的单循环链表的结点信息 output(head)；/双向链表参考程序/以下是头文件 hh h 的内容#include

16、#include typedef struct dupnode!n”)；int data；struct dupnode*next,*prior；dulinklist；/以下是主程序的内容#include”hh h”/create 函数用来构建双向链表 dulinklist*create()dulinklist*head,*p，*r;int i，n；head=(dulinklist*)malloc(sizeof(dulinklist)；head-next=NULL；head-prior=NULL；r=head；printf(“请输入所建双向链表中结点的个数：n”)；scanf(“d”,n)；fo

17、r(i=l；idata)；p-next=NULL；r-next=p；p-prior=r；r=r-next；return(head)；/find 函数用来实现在双向链表中按序号查找某个结点的功能。void find(dulinklist*h)int k,i；dulinklist*p；p=h；i=0：printf(”输入要查找结点的序号：n”)；scanf(”%d”,&k)；while(p!=NULL)&(inext；i+：if(p)printf(”所查到的结点的值为：n”)；printf(”%dn”,p-data)；else printf(”没找到该结点!n”)；/insdulist 函数用来实

18、现在双向链表中按序号插入结点的功能 dulinklist*insdulist(dulinklist*head，int i，int x)dulinklist*p，*s；int j；p=head；j=0；whi1e(p-next!=head)&(jnext；j+；If(j=i-1)s=(duli nklist*)malloc(sizeof(duli nklist)；s-data=x；s-prior=p；s-next=p-next；p-next-prior=s；p-next=s；else printf(”errorn”)；return head；/deledulist 函数实现在双向链表中按序号删除

19、某个结点的功能 dulinklist*deledulist(dulinklist*head，int i)dulinklist*p；int j；p=head；j=0 while(p-next!=head)&(jnext；j+；If(j=i)p-prior-next=p-next；p-next-prior=p-prior；free(p)；else printf(”error n”)；return head；/output 函数用来输出整个双向链表的结点值 void output(dulinklist*h)dulinklist*p；p=h-next；while(p!=NULL)printf(”输出该

20、双向链表的结点，分别为：n”)；printf(”%dn”,p-data)；p=p-next；void main()dulinklist*head int flag=l i，k，x；while(flag)/flag 作为判断循环的标志位 printf(”1 建立双向链表 n”)；printf(”2 查找某个结点 n”)；printf(”3 插入一个结点 n”)；prtntf(”4 删除一个结点 n”)；printf(”5 退出 n”）；printf（”请输入选择：n“）；scanf（”%d”，&i）；switch（i）case 1：head=create0；break；case 2：find（h

21、ead）；break；case 3：printf（”输入待插的结点的序号及新插入结点的 data 值.n”）;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 循环结束 此程序不论是插入、查找还是删除运算均是按序号的方式来处理，当然也可改为按结点 的值来作相应的处理，试修改以上程序实现按值操作的功能。六、选作

22、实验 利 用单循 环链表 存储 结构，解决约 瑟夫（Josephus）环问 题。即：将编号 是 1,2,n（n0）的n个人按照顺时针方向围坐一圈，每人持有一个正整数密码。开始时任选 一个正整数作为报数上限值 m,从某个人开始顺时针方向自 1 开始顺序报数，报到 m 时停 止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重 新从 1 报数，如此下去，直到所有的人全部出列为止。令 n 最大值取 30。设计一个程序，求出出列顺序，并输出结果。实验三 树形结构 一、实验目的：1掌握二叉树的数据类型描述及二叉树的特性。2 掌握二叉树的链式存储结构（二叉链表）的建立算法

23、。3 掌握二叉链表上二叉树的基本运算的实现。二、实验内容：从以下 1、2 和 3、4 中各选择一项内容 1.用递归实现二叉树的先序、中序、后序 3 种遍历。2.用非递归实现二叉树的先序、中序、后序 3 种遍历。3.实现二叉树的层次遍历。4.将一棵二叉树的所有左右子树进行交换。三、实验要求：1.根据实验内容编程，上机调试、得出正确的运行程序。2.写出实验报告（包括源程序和运行结果）。四、实验学时：4 学时 五、实验步骤：1进入编程环境，建立一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。将建立二叉树及先序、中序、后序 3 种遍历算法都写成子函数，然后分别在主函数 中调用它，但在建立

24、二又树中，必须把二叉树看成完全二叉树的形式。若不是完全 二叉树，则在输入数据时，用虚结点（不存在）表示（本算法中，用“，”号代替）。用非递归法实现二叉树的遍历 非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈 顶指针。实现二叉树的层次遍历 用一个一维数组代替队列，实现二叉树的层次遍历。将一棵二叉树的所有左右子树进行交换。本算法只要增加一个实现二叉树左右子树交换的子函数即可。为了便于查看，在主 函数将交换前后的三种遍历效果，分别输出。以下为部分参考程序：/递归实现二叉树的 3 种遍历#include typedef char elemtype；struct bitree

25、定义二叉树数据类型 elemtype data；/结点信息 bitree*lchild，*rchild；/左右孩子;bitree*create()/建立二叉链表 bitree*root,*s，*q100；/q 为队列，最大空间为 100 int front=l，rear=0；/队列头、尾指针 char ch；root=NULL；cout”请输入结点值(，为虚结点，#结束)：”ch；while(ch!=#)s=NULL；if(ch!=,)s=new bitree；s-data=ch；s-lchild=NULL；s-rchild=NULL；rear+；qrear=s；/进队 if(rear=1)r

26、oot=s；else if(s!=NULL)&(qfront!=NULL)if(rear%2=0)qfront-lchild=s；else qfront-rchid=s；if(rear 2=1)front+；/出队 cinch；return root：bitree*p；p=root；if(p!=NULL)coutdatalchild)；preorder(p-rchild)；void inorderl(bitree*root)bitree*p；p=root；if(p!=NULL)inorder(p-lchild)；coutdatarchild)；void postorder(bitree*roo

27、t)bitree*p；p=root；if(p!=NULL)postorder(p-lchild)；postorder(p-rchild)coutdata“”；void main()bitree*root；root=create()；/建立二叉链表 cout”先序遍历的结果”endl；preorder(root)；coutendl；cout”中序遍历的结果”endl；inorder(root)；coutendl：cout”后序遍历的结果”endl；postorder(root)；cout0)while(p!=NULL)3 种遍历，部分遍历程序如下/先序遍历/s 为堆栈/top 为栈顶指针/中序遍

28、历/后序遍历 coutdatalchild；p=stop-；/退栈 p=p-rchild；void inorderl(bitree*root)/bitree*p，*s100；int top=0；p=root；while(p!=NULL)Il(topO)while(p!=NULL)s+top=p；p=p-lchild；p=stop-；coutdatarchild；void postorderl(bitree*root)(bitree*p*sl100；int s2100，top=0，b；p=root；do while(p!=NULL)s1top=p；s2top+=0；p=p-lchild；)if(

29、top0)(b=s2-top；p=s1top；if(b=0)sltop=p；s2top+=l；p=p-rchild；else coutdata0)；中序遍历/后序遍历/建立二叉链表参考前述程序/按照层次遍历二叉链表#include typedef char elemtype；struct bitree elemtype data；/结点信息 bitree*lchild，*rchild；/左右孩子;/按层次遍历二叉树(建立二叉链表同前)void lorder(bitree*t)bitree q100，*p；/q 代表队列 int f,r;/f，r 类似于队列头、尾指针 q1=t；f=r=l；co

30、ut”按层次遍历二叉树的结果为：”;while if=r)p=qf；f+；/出队 coutdatalchild!=NULL)r+；qr=p-lchild；/入队 if p-rchild!=NULLl r+；qr=p-rchild;/入队 coutlchild);leftOright(root-rchild);bitree*t=root-lchild;root-lchild=root-rchild;root-rchild=t;/主函数 void main()bitree*root；root=create()；/建立二叉链表 coutendlendl”左右子树交换前的遍历结果”endl；cout”

31、先序遍历的结果”endl；preorder(root)；coutendl；cout”中序遍历的结果”endl；inorder(root)；coutendl：cout”后序遍历的结果”endl；postorder(root)；coutendl；leftTOright(root)；coutendlendl”左右子树交换后的遍历结果”endl；cout”先序遍历的结果”endl；preorder(root)；coutendl；cout”中序遍历的结果”endl；inorder(root)；coutendl；cout”后序遍历的结果”endl；postorder(root)；coutarcsvw.ad

32、j=l；return；void del_arc(graph*g，int v，int w)g-arcvw.adj=0；retum;/内容 1 参考程序#define maxnode 40#define null 0#include typedef struct st_arc int adjvex；int weight；struct st_arc*nextrac；arcnode；typedef struct int vertex；struct st_arc*firstarc；vernode；typedef vernode adjlistmaxnode；void del_arc(vernode g，

33、int v，int w)/删除从顶点 v 到顶点 w 的边 arcnode*rl,*r 2；rl=gv frrstarc；r2=rl；while(r1!=null&r1-adjvex!=w)r2=rl;rl=rl-nextarc if(rl=null)printf(”no edge v-w”)；return；else if(r1=r2)/当只有一个边结点时 return；gv.firstarc=r1-nextarc else r2-nextarc=r1-nextarc rl=gw.firstarc；r2=rl；while(r1!=null&r1-adjvex!=v)应的 r2=rl；rl=rl

34、-n extarc；if(rl=null)printf(”no edge v-w.”)；/有多个边结点时/在以 v 为头结点的链表中，删除相/边结点 else if(r1=r2)gw.firstarc=rl-nextarc；else r2-nextarc=r1-nextarc；void print(vernode g，int n)/打印图中各结点的结构 arcnode*q；int i；printf(”adjacency list of the graph：n”)；for(i=0；iadjvex)；printf(”%dt”，q-weight)；q=q-nextarc；printf(”n”)；ma

35、in()int i，j，n，k，w，v；arcnode*p，*q；adjlist g；printf(”Input node：”)；/输入图中顶点个数 scanf(”%d”，&n)；for(k=0；kadjvex=j；q-weight=w；q-nextarc=gi.firstarc；/头指针指向新的边结点 gi.firstarc=q；p=(arcnode*)malloc(sizeof(arcnode)；p-nextarc=gi.firstarc；gi.firstarc=q；p=(arcnode*)malloc(sizeof(arcnode)；p-adjvex=i；p-weight=w；p-nex

36、tarc=gj.firstarc；gj.firstarc=p；print(g，n)；printf(”Delete edge V-w：”)；scanf(”%d%d”，v，&w)；del_arc(g，v，w)；print(g，n)；内容 2 的知识要点：构造有向图链接表与无向图链接表的算法区别是：无向图两结点无向对偶，因而邻接表有一定的对偶性；有向图两结点间有向无对偶关系，因而建立邻接表 时应根据输入的顶点及边的有向关系建立（当箭头方向离开结点为有关，当箭头 方向指向结点为无关)/内容 2 的参考程序/有向图链表的存储结构为：typedef struct st_arc int aajvex；/存放

37、依附于该边的另一顶点在一维数组中的序号 int weight；/存放和该边有关的信息，如权值等 struct st_arc*nextarc；/依附于该顶点的下一个边结点的指针 arcnode；typedef struct int vertex；/存放与顶点有关的信息 struct st_arc*firstarc；vernode；/存储顶点信息 typedef vernode adjlistmaxnode；/参考程序见内容 1 内容 3 的知识要点：深度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从 vo 出发，访 问 vo 的一个未被访问过的邻接顶点 w1，再从 w1 出发，访问 w1

38、 的一个未被访 问的顶点 w2，然后从 w2 出发，访问 w2 的一个未被访问的邻接顶点 w3，依此 类推，直到一个所有邻接点都被访问过为止。图采用邻接表作存储结构，图的深度优先遍历次序为-T-一 参考程序运行过程中，深度优先遍历时指针 p 的移动方向示意如图下所示，图中pl、p2、p3、p4、p5和p6为深度优先遍历图的各结点时，指针 p的移 动次序。/内容3的参考程序#defi ne maxnode 40#defi ne null 0#includevsddio.h int adivex；int weigh；struct st_arc*n extarc arcnode;typedef st

39、ruct int vertex；struct st_arc*firstarc;vernode;typedef vernode adjlistmax node void trave(adjlist g,int n)/采用邻接表作存储结构的/深度优先遍 历 访问 void dfs()；p5 typedef struct st_arc/定义结构体 for(i=0；in；i+)visitedi=0;/数组初始化 for(i=0；iadjvex；if(visitedw=0)dfs(g，w，visited)；p=p-nextarc；main()int i，j，n，k，v；arcnode*p,*q;adjl

40、ist g；printf(“Input node：”)；scanf(“%d”，n)；for(k=0；kadjvex=j；q-nextarc=gi.firstarc；gifirstarc=q；p=(arcnode*)malloc(sizeof(arcnode)p-adjvex=i；p-nextarc=gi.firstarc;gi_firstarc=p；printf(“dfs：”)；trave(g，n)；/深度优先遍历图。printf(“n”);内容 4 的知识要点：广度优先遍历图的算法：首先访问指定的起始顶点 v0,从 v0 出发，访问 v0 的所有未被访问的邻接顶点 Wi,W2，Wk，然后再依

41、次从Wi,W2，Wk 出发，访问所有未被访问过的邻接顶点，依此类推，直到图中所有未被访问过的 邻接顶点都被访问过为止。根据广度优点遍历的规则，在其算法实现中，借助一个队列 gqueue 来 存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在 队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依此类 推，直至队列为空且图中结点均被访问过为止。图的广度优先遍历次序为：-T-T-参考程序运行过程中，广度优先搜索时指针 p 的移动示意如下图所示，图 中片 pi、p2、p3、p4、p5 和 p6 为广度优先遍历图的各结点指针 p 的移动次 序。/内容4的参考程序#def

42、i ne maxnode 40#defi ne null 0#includevsddio.h typedef struct st_arc/定义结构体 int adivex；int weigh；struct st_arc*n extarc;arcnode;typedef struct int vertex；struct st_arc*firstarc;vernode;typedef vernode adjlistmax node typedef struct int queuemax no de;int front;int rear;qqtype;void intiate(qqtype*q)q-

43、front=-1;q-rear=-1;/初始化队列 int enter(qqtype*q,int x)if(q-rear=maxnode-1)return(-1);else q-rear+;q-queueq-rear=x;return(0);int delete(qqtype*q)if(q-front=q-rear)return(null);/将 X 入队/出队 else q-front+;return(q-queueq-front);int emtype(qqtype*q)if(q-front=q-rear)return(-1);return(0);void bfs(adjlist g，in

44、t k，int visited)/从顶点 k 出发进行广度优先遍 历 arcnode*p；int w；intiate(g);visitedk=1;/访问点从 k 开始，并把它入队。printf(“%d”,gp-adjvex.vertex);enter(g,k);while(emptye(g)=0)w=delete(g);p=gw.firstarc;while(p!=null)if(visitedp-adjves=0)printf(“%d”,gp-adjvex.verte);visitedp-adjvex=1;enter(g.p-adjvex);p=p-nextarc;void trave(ad

45、jlist g，int n)int i，visitedmaxnode；访问。for(i=0；in；i+)visitedi=0;for(i=0；in；i+)if(visitedi=0)bfs(g，i，visted)；main()int i，j，n，k，v；arcnode*p,*q;adjlist g；printf(“Input node：”)；scanf(“%d”，n)；for(k=0；kadjvex=j；q-nextarc=gi.firstarc；gifirstarc=q；p=(arcnode*)malloc(sizeof(arcnode)p-adjvex=i；p-nextarc=gi.fir

46、starc;gi_firstarc=p；printf(“bfs：”)；trave(g，n)；/广度优先遍历图 printf(“n”);六、选作实验 假设有 n 个城市，要实现 n 个城市之间都能互相通信和构造 n 个城市之间的 通信网，使工程总造价最低。设计一个能满足要求的最低造价方案。实验五 查找 一、实验目的：1.掌握查找的含义。2.掌握基本查找操作的算法与实现。3.掌握二叉排序树查找的算法与实现。4.掌握 Hash 表查找的算法与实现。二、实验内容：从以下 1、2 和3、4 中各选择一项内容 1.建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元 素的关键字进行查找

47、。（为了简化算法，数据元素只含一个整型量关键字字段，数据元 素的其余数据部分忽略不考虑。）2.查找表的存储结构为有序表，即表中记录按关键字大小排序存放。输入待查数据元 素的关键字进行查找。（为了简化算法，记录只含一个整型量关键字字段，记录的其余 数据部分略不考虑。程序要求对整型量关键字数据的输入按从小到大排序输入。）3.编程实现二叉排序树的创建、查找、插入、输出等算法。4.设哈希表长为 20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再 散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。三、实验要求：1.根据实验内容编程，上机调试、得出正确的运行程序。2.写出实验报告（

48、包括源程序和运行结果）。四、实验学时：6 学时 五、实验步骤：1进入编程环境，建立一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。顺序查找的基本思想及程序实现 对于给定的关键字 k，从表的一端开始，逐个进行数据元素的关键字和给定值的比 较，若当前扫描到的结点关键字与 k 相等则查找成功；若扫描结束后，仍未找到关键 字等于 k 的节点，则查找失败。建立一个顺序表，数据元素从下标为 1 的单元开始放入，下标为 0 的单元起监视 哨作用，将待查的关键字存入下标为 0 的单元，顺序表从后向前查找，若直到下标为 0 时才找到关键字则说明查找失败；若不到下标为 0 时就找到关键字，则查找成功

49、。/参考程序#include#define KEYTYPE int#define MAXSIZE 100 typedef struct KEYTYPE key；SSELEMENT；typedef struct SSELEMENT rMAXSIZE int len；SSTABLE；int seq_search(KEYTYPE k int j；j=st-len；st-r0.key=k；while(st-rj.key!=k)j-;return j；，SSTABLE*st)/顺序表查找元素/顺序表元素个数/st-r0 单元作为监视哨/顺序表从后向前查找 j=0，找不到，j丰0找到 main()SSTA

50、BLE a;int i，j，k；printf(”请输入顺序表元素，元素为整型量，用空格分开，-99 为结束标志：”)；j=0；k=1;i=0;scanf（”%d”，i）；while（i!=-99）j+；a.rk.key=i；k+;scanf（”%d”，i）；a.1en=j;printf（”n 顺序表元素列表显示：”）；for（i=1；i=a.1en;i+）printf（”%d”，a.ri.key）；printf（“n”）;printf（”n 输入待查元素关键字：”）；scanf（“%d”，&i）；k=seq_search（i，&a）；if（k=0）printf（“表中待查元素不存在 nn”）；