【数据结构】实验指导书（源代码）

...wd......wd......wd...实验一线性表的链式存储构造实验目的：1．掌握线性表的链式存储构造。2．熟练地利用链式存储构造实现线性表的基本操作。3．能熟练地掌握链式存储构造中算法的实现。二、实验内容：1．用头插法或尾插法建设带头结点的单链表。2．实现单链表上的插入、删除、查找、修改、计数、输出等基本操作。三、实验要求：1.根据实验内容编写程序，上机调试、得出正确的运行程序。2.写出实验报告〔包括源程序和运行结果〕。四、实验学时：2学时五、实验步骤：1．进入编程环境，建设一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。①定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改、计数、输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的结果输出，以查看每一种操作的效果。②局部参考程序//单链表的建设(头插法)，插入，删除，查找、修改、计数、输出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素类型link*next；//指针类型，存放下一个元素地址};//头插法建设带头结点的单链表link*hcreat(){links,p;elemtypei;cout<<〞输入多个结点数值(用空格分隔)，为0时算法完毕〞；cin>>i；p=newlink；p->next=NULL；while(i)//当输入的数据不为0时，循环建单链表{s=newlink；s->data=i；s->next=p->next；p->next=s；cin>>i；}returnp；}//输出单链表voidprint(1ink*head){1ink*p；p=head->next；while(p->next!=NULL){cout<<p->data<<〞->〞；//输出表中非最后一个元素p=p->next；}cout<<p->data；//输出表中最后一个元素cout<<endl；}∥在单链表head中查找值为x的结点Link*Locate(1ink*head，elemtypex){Link*p；p=head->next；while((p!=NULL)&&(p->data!=x))p=p->next；returnp；}//在head为头指针的单链表中，删除值为x的结点voiddeletel(1ink*head，elemtypex){1ink*p，*q；q=head；p=head->next；while((p!=NULL)&&(p->data!=x)){q=p；p=p->next；}If(p==NULL)cout<<“要删除的结点不存在〞；elseq->next=p->next；delete(p)；}}//在头指针head所指的单链表中，在值为x的结点之后插入值为y的结点voidinsert(1ink*head，elemtypex，elemtypey)｛link*p，*s；s=newlink；s->data=y；if(head->next==NULL)//链表为空{head->next=s；s->next=NULL：}p=Locate(head，x)；//调用查找算法‘if(p==NULL)cout<<〞插入位置非法〞：else(s->next=p->next；p->next=s；}}//将单链表p中所有值为x的元素修改成yvoidchange(1ink*p,elemtypex,elemtypey){link*q；q=p->next；while(q!=NULL){if(q->data==x)q->data=y；q=q->next；}}voidcount(1ink*h)//统计单链表中结点个数{1ink*p；intn=0；p=h->next；while(p!=NULL){n++；p=p->next；}returnn;}voidmain(){intn；elemtypex，y；link*p，*q；p=hcreat()；//头插法建设链表print(p)；//输出刚建设的单链表cout<<〞请输入要删除的元素〞；cin>>y；deletel(p，y)；print(p)；//输出删除后的结果cout<<〞请输入插入位置的元素值(将待插元素插入到它的后面)〞;cin>>x；cout<<〞请输入待插元素值〞；cin>>y；insert(p，x，y)；print(p)；//输出插入后的结果cout<<〞请输入要修改前、后的元素值〞;cin>>x>>y；change(p，x，y)；print(p)；cout<<〞请输入要查找的元素值〞；cin>>x；q=Locate(p，x)；if(q==NULL)cout<<x<<〞不在表中，找不到!〞<<endl；elsecout<<x<<〞在表中，已找到!〞<<endl；n=count(p)；cout<<〞链表中结点个数为：〞<<n<<endl：}//单链表的建设(尾插法)、插入、删除、查找、修改、计数、输出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素类型link*next；//指针类型，存放下-个元素地址}；//尾插法建设带头结点的单链表link*rcreat(){link*s，*p，*r；elemtypei；cout<<〞输入多个结点数值(用空格分隔)，为0时算法完毕〞；cin>>i;p=r=newlink；p->next=NULL；while(i){s=newlink；s->data=i；r->next=s；r=s；cin>>i；}r->next=NULL；returnp；}//输出单链表voidprint(1ink*head){link*p；p=head->next；while(p->next!=NULL){cout<<p->data<<"->〞;//输出表中非最后一个元素p=p->next；)cout<<p->data；//输出表中最后一个元素cout<<endl；}link*Locate(1ink*head，intx)∥在单链表中查找第x个结点{link*p；p=head；intj=0；while((p!=NULL)&&(j<x)){p=p->next;j++；}returnp；}voiddeleteI(1ink*head，elemtypex)//在head为头指针的单链表中，删除值为x的结点{link*p,*q；q=head；p=head->next；while((p!=NULL)&&(p->data!=x)){q=p；p=p->next；)if(p==NULL)cout<<〞要删除的结点不存在“;else{q->next=p->next；delete(p)；}}voidinsert(1ink*head，intx,elemtypey)//在头指针head所指单链表中，在第x个结点之后插入值为y的结点{link*p，*s；s=newlink；s->data=y；if(head->next==NULL)//链表为空{head->next=s；s->next=NULL：}p=Locate(head，x)；//调用查找算法if(p==NULL)cout<<〞插入位置非法〞;else{s->next=p->next；p->next=s；}}voidchange(1ink*p,elemtypex，elemtypey){∥将单链表P中所有值为x的元素改成值为ylink*q；q=p->next；while(q!=NULL){if(q->data==x)q->data=y；q=q->next；}}voidcount(1ink*h)//统计单链表中结点个数(1ink*p；intn=0；p=h->next；while(p!=NULL){n++；p=p->next；}retumn;}voidmain(){intn;linkp,q;p=rcreat()；//尾插法建设链表print(p)；//输出刚建设的单链表cout<<〞请输入要删除的元素〞；cin>>y；deletel(p，y)；print(p)；//输出删除后的结果cout<<〞请输入插入位置〞;cin>>x；cout<<〞请输入待插元素值〞；cin>>y；insert(p，x，y)；print(p)；//输出插入后的结果cout<<〞请输入修改前、后的元素值〞;cin>>x>>y；change(p，x，y)；print(p)；cout<<“请输入要查找的元素值〞;cin>>x；q=Locate(p,x)；if(q==NULL)cout<<x<<〞不在表中,找不到!〞<<endl；elsecout<<x<<〞在表中，已找到!〞<<endl；n=count(p)；cout<<〞链表中结点个数为：〞<<n<endl;}六、选作实验试设计一元多项式相加〔链式存储〕的加法运算。A〔X〕=7+3X+9X8+5X9B〔X〕=8X+22X7-9X81．建设一元多项式；2．输出相应的一元多项式；3．相加操作的实现。实验二循环链表的操作实验目的：通过本实验中循环链表和双向链表的使用，使学生进一步熟练掌握链表的操作方式。二、实验内容：本次实验可以从以下两个实验中任选一个：1．建设一个单循环链表并实现单循环链表上的逆置。所谓链表的逆置运算(或称为逆转运算)是指在不增加新结点的前提下，依次改变数据元素的逻辑关系，使得线性表(al，a2，a3，…，an)成为(an，…，a3，a2，a1)。2.构建一个双向链表，实现插入、查找和删除操作。三、实验要求：1.根据实验内容编写程序，上机调试、得出正确的运行程序。2.写出实验报告〔包括源程序和运行结果〕。四、实验学时：2学时五、实验步骤：1．进入编程环境，建设一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。①建设一个带头结点的单循环链表，从头到尾扫描单链表L，把p作为活动指针，沿着链表向前移动，q作为p前趋结点，r作为q的前趋结点。其中，q的next值为r；r的初值置为head。②双向链表的构造与单链表一样，至于它的插入与删除运算比单链表复杂，插入运算需要4步操作，删除运算需要2步操作，注意语句的次序，不要任意交换位置，以免不能正确插入或删除结点。③局部参考程序//循环链表∥头文件h1．h的内容#defineNULL0#include<stdio．h>#include<malloc．h>typedefstructnode{intnum；structnode*next；}linklist；∥以下是主程序#include〞h1．h〞∥输出循环链表的信息voidoutput(linklist*head){linklist*p；p=head->next；while(p!=head){printf(〞％d〞，p->num)；p=p->next；}printf(〞\n〞)；}//建设单循环链表Linklist*creat(intn){intk;linklist*head,*r,*p；p=(linklist*)malloc(sizeof(linklist))；head=p；r=p；p->next=p；for(k=1；k<=n；k++){p=(linklist*)malloc(sizeof(linklist))；p->num=k；r->next=p；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)；}voidmain(){intn；Linklist*head；printf(“输入所建设的循环链表的结点个数：\n〞)；scanf(“%d〞，＆n)；head=creat(n)；printf(〞输出建设的单循环链表：\n〞)；output(head)；printf(〞现在进展逆置!\n〞)；head=invert(head)；printf(〞输出进展逆置运算后的单循环链表的结点信息!\n〞)；output(head)；}//双向链表参考程序//以下是头文件hh．h的内容#include<stdio.h>#include<malloc.h>typedefstructdupnode{intdata；structdupnode*next,*prior；}dulinklist；//以下是主程序的内容#include〞hh．h〞//create函数用来构建双向链表dulinklist*create(){dulinklist*head,*p，*r;inti，n；head=(dulinklist*)malloc(sizeof(dulinklist))；head->next=NULL；head->prior=NULL；r=head；printf(“请输入所建双向链表中结点的个数：\n〞)；scanf(“％d〞,＆n)；for(i=l；i<=n；i++){p=(dulinklist*)malloc(sizeof(dulinklist))；printf(〞输入结点的值：\n〞)；scanf(〞%d’，&p->data)；p->next=NULL；r->next=p；p->prior=r；r=r->next；}return(head)；}//find函数用来实现在双向链表中按序号查找某个结点的功能。voidfind(dulinklist*h){intk,i；dulinklist*p；p=h；i=0：printf(〞输入要查找结点的序号：\n〞)；scanf(〞%d〞,&k)；while((p!=NULL)&&(i<k)){p=p->next；i++：}if(p){printf(〞所查到的结点的值为：\n〞)；printf(〞%d\n〞,p->data)；}elseprintf(〞没找到该结点!\n〞)；}//insdulist函数用来实现在双向链表中按序号插入结点的功能dulinklist*insdulist(dulinklist*head，inti，intx){dulinklist*p，*s；intj；p=head；j=0；whi1e((p->next!=head)&&(j<i-1))//找到第i-1个结点{p=p->next；j++；}If(j==i-1){s＝(dulinklist*)malloc(sizeof(dulinklist))；s->data=x；s->prior=p；s->next=p->next；p->next->prior=s；p->next=s；}elseprintf(〞error\n〞)；returnhead；}//deledulist函数实现在双向链表中按序号删除某个结点的功能dulinklist*deledulist(dulinklist*head，inti){dulinklist*p；intj；p=head；j=0while((p->next!=head)&&(j<i)){p=p->next；j++；}If(j==i){p->prior->next=p->next；p->next->prior=p->prior；free(p)；}elseprintf(〞error\n〞)；returnhead；}//output函数用来输出整个双向链表的结点值voidoutput(dulinklist*h){dulinklist*p；p=h->next；while(p!=NULL){printf(〞输出该双向链表的结点，分别为：\n〞)；printf(〞%d\n〞,p->data)；p=p->next；}}voidmain(){dulinklist*head；intflag=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){case1：head=create0；break；case2：find(head)；break；case3：printf(〞输入待插的结点的序号及新插入结点的data值.\n〞);scanf(〞%d%d〞，＆k，＆x)；head=insdulist(head，k，x)；output(head)；break；case4：printf(〞输入要删除的结点的序号.\n〞)；scanf(〞%d，＆k)；head=deledulist(head，k)；output(head)；break；case5:flag=0；}}//while循环完毕}此程序不管是插入、查找还是删除运算均是按序号的方式来处理，当然也可改为按结点的值来作相应的处理，试修改以上程序实现按值操作的功能。六、选作实验利用单循环链表存储构造，解决约瑟夫〔Josephus〕环问题。即：将编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一个正整数密码。开场时任选一个正整数作为报数上限值m,从某个人开场顺时针方向自1开场顺序报数，报到m时停顿报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开场重新从1报数，如此下去，直到所有的人全部出列为止。令n最大值取30。设计一个程序，求出出列顺序，并输出结果。实验三树形构造实验目的：1．掌握二叉树的数据类型描述及二叉树的特性。2．掌握二叉树的链式存储构造(二叉链表)的建设算法。3．掌握二叉链表上二叉树的基本运算的实现。二、实验内容：从以下1、2和3、4中各选择一项内容1.用递归实现二叉树的先序、中序、后序3种遍历。2.用非递归实现二叉树的先序、中序、后序3种遍历。3.实现二叉树的层次遍历。4.将一棵二叉树的所有左右子树进展交换。实验要求：1.根据实验内容编程，上机调试、得出正确的运行程序。2.写出实验报告〔包括源程序和运行结果〕。四、实验学时：4学时五、实验步骤：1．进入编程环境，建设一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。将建设二叉树及先序、中序、后序3种遍历算法都写成子函数，然后分别在主函数中调用它，但在建设二又树中，必须把二叉树看成完全二叉树的形式。假设不是完全二叉树，那么在输入数据时，用虚结点(不存在)表示(本算法中，用“，〞号代替)。用非递归法实现二叉树的遍历非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。③实现二叉树的层次遍历用一个一维数组代替队列，实现二叉树的层次遍历。④将一棵二叉树的所有左右子树进展交换。本算法只要增加一个实现二叉树左右子树交换的子函数即可。为了便于查看，在主函数将交换前后的三种遍历效果，分别输出。以下为局部参考程序：//递归实现二叉树的3种遍历#include<iostream.h>typedefcharelemtype；structbitree{定义二叉树数据类型elemtypedata；//结点信息bitree*lchild，*rchild；//左右孩子};bitree*create()//建设二叉链表{bitree*root,*s，*q[100]；//q为队列，最大空间为100intfront=l，rear=0；//队列头、尾指针charch；root=NULL；cout<<〞请输入结点值(‘，’为虚结点，‘#’完毕)：〞<<endl；cin>>ch；while(ch!=’#’){s==NULL；if(ch!=’,’){s=newbitree；s->data=ch；s->lchild=NULL；s->rchild=NULL；}rear++；q[rear]=s；//进队if(rear==1)root=s；else{if((s!=NULL)&&(q[front]!=NULL)){if(rear%2==0)q[front]->lchild=s；elseq[front]->rchid=s；}if(rear％2==1)front++；//出队}cin>>ch；｝returnroot：}voidpreorder(bitree*root)//先序遍历{bitree*p；p=root；if(p!=NULL){cout<<p->data<<〞〞；preorder(p->lchild)；preorder(p->rchild)；}}voidinorderl(bitree*root)//中序遍历{bitree*p；p=root；if(p!=NULL){inorder(p->lchild)；cout<<p->data<<“〞;inorder(p->rchild)；}}voidpostorder(bitree*root)//后序遍历{bitree*p；p=root；if(p!=NULL){postorder(p->lchild)；postorder(p->rchild)；cout<<p->data<<“〞；}}voidmain(){bitree*root；root=create()；//建设二叉链表cout<<〞先序遍历的结果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍历的结果〞<<endl；inorder(root)；cout<<endl：cout<<〞后序遍历的结果〞<<endl；postorder(root)；cout<<endl；}//用非递归实现二叉树的3种遍历，局部遍历程序如下：voidpreorderl(bitree*root)//先序遍历{bitree*p，*s[100]；//s为堆栈inttop=0；//top为栈顶指针p=root；while((p!=NULL)||(top>0)){while(p!=NULL){cout<<p->data<<〞〞；s[++top]=p；//进栈p=p->lchild；}p=s[top--]；//退栈p=p->rchild；}}voidinorderl(bitree*root)//中序遍历{bitree*p，*s[100]；inttop=0；p=root；while((p!=NULL)Il(top>O)){while(p!=NULL){s[++top]=p；p=p->lchild；}{p=s[top--]；cout<<p->data<<“〞；p=p－>rchild；｝｝｝voidpostorderl(bitree*root)//后序遍历(bitree*p*sl[100]；ints2[100]，top=0，b；p=root；do{while(p!=NULL){s1[top]=p；s2[top++]=0；p=p->lchild；)if(top>0)(b=s2[--top]；p=s1[top]；if(b==0){sl[top]=p；s2[top++]=l；p=p->rchild；}else{cout<<p->data<<〞〞;p=NULL；}}}while(top>0)；}//建设二叉链表参考前述程序//按照层次遍历二叉链表#include<iostream.h>typedefcharelemtype；structbitree{elemtypedata；//结点信息bitree*lchild，*rchild；//左右孩子};//按层次遍历二叉树(建设二叉链表同前)voidlorder(bitree*t){bitreeq[100]，*p；//q代表队列intf,r;//f，r类似于队列头、尾指针q[1]=t；f=r=l；cout<<〞按层次遍历二叉树的结果为：〞;whileif<==r){p=q[f]；f++；//出队cout<<p->data<<〞〞;if(P->lchild!=NULL){r++；q[r]=p->lchild；}//入队ifp->rchild!=NULLl．{r++；q[r]=p->rchild;}//入队}cout<<endl；}voidmain(){bitree*t；t=create0；//建设二叉链表lorder(t)；//：按层次遍历二叉树}//将二叉树的左右子树进展交换voidleftOright(bitree*r){bitree*root=r;if(root!=NULL){leftOright(root->lchild);leftOright(root->rchild);bitree*t=root->lchild;root->lchild=root->rchild;root->rchild=t;}}//主函数voidmain(){bitree*root；root=create()；//建设二叉链表cout<<endl<<endl<<〞左右子树交换前的遍历结果〞<<endl；cout<<〞先序遍历的结果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍历的结果〞<<endl；inorder(root)；cout<<endl：cout<<〞后序遍历的结果〞<<endl；postorder(root)；cout<<endl；}leftTOright(root)；cout<<endl<<endl<<〞左右子树交换后的遍历结果〞<<endl；cout<<〞先序遍历的结果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍历的结果〞<<endl；inorder(root)；cout<<endl；cout<<〞后序遍历的结果〞<<endl；postorder(root)；cout<<endl；}六、选作实验1.给定权值5,29,7,8,14,23,3,11，建设哈夫曼树，输出哈夫曼编码。2.对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。算法提示：将建设哈夫曼树、实现哈夫曼编、哈夫曼译码都定义成子函数的形式，然后在主函数调用它们。建设哈夫曼树时，将哈夫曼树的构造定义为一个构造型的一维数组，每个元素含有四项：双亲、左孩子、右孩子。给定的权值可以从键盘输入，要输出所建设的哈夫曼树，只要输出哈夫曼树的一维数组中全部元素即可。要实现哈夫曼编码，只要在所建设的哈夫曼树上进展二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中所有0、l排列起来，那么得到该树叶的哈夫曼编码。哈夫曼编码可以用一个构造型的一维数组保存，每个元素包含：编码、编码的开场位置、编码所对应的字符等3项。哈夫曼译码，就是将输入的编码复原成对应的字符。实验四图的遍历操作实验目的：1.掌握图的含义。2.掌握用邻接矩阵和邻接表的方法描述图的存储构造。3.理解并掌握深度优先遍历和广度优先遍历的存储构造。二、实验内容：从以下1、2和3、4中各选择一项内容1.建设无向图的邻接矩阵，并实现插入、删除边的功能。2.建设有向图的邻接表，并实现插入、删除边的功能。3.建设一个包含6个结点的图，并实现该图的深度优先搜索遍历。4.建设一个包含6个结点的图，并实现该图的广度优先搜索遍历。三、实验要求：1.根据实验内容编程，上机调试、得出正确的运行程序。2.写出实验报告〔包括源程序和运行结果〕。四、实验学时：4学时五、实验步骤：1.进入编程环境，建设一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。内容1的知识要点：图由一个非空的顶点的集合和一个描述顶点之间关系(边)的集合组成。它可以定义为G=(V，E)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图是一种复杂的数据构造。对于实际问题，需要根据具体图的构造特点以及所要实施的操作，选择建设适宜的存储构造。图的存储构造包括邻接矩阵和邻接表。邻接矩阵：用一维数据组存储图中顶点的信息，用矩阵表示图中各顶点之间的相邻关系。它属于静态存储方法。邻接表：邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。顺序存储局部用来保存图中顶点的信息，链式存储局部用来保存图中边的信息。//邻接矩阵的存储构造typedefstruct{intvertex；}node；typedefstruct{intadj；}arc；typedefstruct{nodenode[maxnode]；arcarcs[maxnode][maxnode]；}graph；//实现插入、删除边的操作voidins_arc(graph*g，intv，intw){g->arcs[v][w].adj=l；return；}voiddel_arc(graph*g，intv，intw){g->arc[v][w].adj=0；retum;}//内容1参考程序#definemaxnode40#definenull0#include<stdio．h>typedefstructst_arc{intadjvex；intweight；structst_arc*nextrac；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；voiddel_arc(vernodeg[]，intv，intw)//删除从顶点v到顶点w的边{arcnode*rl,*r2；rl=g[v]．frrstarc；r2=rl；while(r1!=null&&r1->adjvex!=w){r2=rl;rl=rl->nextarc；}if(rl==null){printf(〞noedgev-w．〞)；return；}elseif(r1==r2)//当只有一个边结点时g[v].firstarc=r1->nextarc；elser2->nextarc=r1->nextarc；//有多个边结点时rl=g[w].firstarc；r2=rl；while(r1!=null&&r1->adjvex!=v)//在以v为头结点的链表中，删除相应的//边结点{r2=rl；rl＝rl->nextarc；｝if(rl=＝null){printf(〞noedgev-w.〞)；return；}elseif(r1==r2)g[w].firstarc=rl->nextarc；elser2->nextarc=r1->nextarc；}voidprint(vernodeg[]，intn)//打印图中各结点的构造{arcnode*q；inti；printf(〞adjacencylistofthegraph：\n〞)；for(i=0；i<n；i++){printf(〞\t%d\t〞，i)；printf(〞%d\t〞，g[i].vertex)；q=g[i].firstarc；while(q!=null){printf(〞%d\t〞，q->adjvex)；printf(〞%d\t〞，q->weight)；q=q->nextarc；}printf(〞\n〞)；}}main(){inti，j，n，k，w，v；arcnode*p，*q；adjlistg；printf(〞Inputnode：〞)；//输入图中顶点个数scanf(〞%d〞，&n)；for(k=0；k<n；k++)//输入边值和权值{printf(〞node%d=〞，k)；scanf(“%d〞，＆g[k].vertex)；g[k].firstarc=null；//对顺序存储局部初始化}for(；；)//输入各边，并将对应的边结点插入到链表中{printf(〞Insertedgei-j，w：〞)scanf(〞%d〞，＆i)；scanf(〞%d〞，＆j)；scanf(〞%d〞，＆w)；if〔i==-1&＆j=＝-1&&w=-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->weight=w；q->nextarc=g[i].firstarc；//头指针指向新的边结点g[i].firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->nextarc=g[i].firstarc；g[i].firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->weight=w；p->nextarc=g[j].firstarc；g[j].firstarc=p；}print(g，n)；printf(〞DeleteedgeV-w：〞)；scanf(〞%d%d〞，＆v，&w)；del_arc(g，v，w)；print(g，n)；}内容2的知识要点：构造有向图链接表与无向图链接表的算法区别是：无向图两结点无向对偶，因而邻接表有一定的对偶性；有向图两结点间有向无对偶关系，因而建设邻接表时应根据输入的顶点及边的有向关系建设(当箭头方向离开结点为有关，当箭头方向指向结点为无关)。//内容2的参考程序//有向图链表的存储构造为：typedefstructst_arc{intaajvex；//存放依附于该边的另一顶点在一维数组中的序号intweight；//存放和该边有关的信息，如权值等structst_arc*nextarc；//依附于该顶点的下一个边结点的指针}arcnode；typedefstruct{intvertex；//存放与顶点有关的信息structst_arc*firstarc；}vernode；//存储顶点信息typedefvernodeadjlist[maxnode]；//参考程序见内容1内容3的知识要点：深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从vo出发，访问vo的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问的顶点w2，然后从w2出发，访问w2的一个未被访问的邻接顶点w3，依此类推，直到一个所有邻接点都被访问过为止。图采用邻接表作存储构造，图的深度优先遍历次序为①→②→④→⑤→⑥→③参考程序运行过程中，深度优先遍历时指针p的移动方向示意如图下所示，图中p1、p2、p3、p4、p5和p6为深度优先遍历图的各结点时，指针p的移动次序。//内容3的参考程序#definemaxnode40#definenull0#include<sddio．h>typedefstructst_arc//定义构造体{intadivex；intweigh；structst_arc*nextarc；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；voidtrave(adjlistg，intn)//采用邻接表作存储构造的/深度优先遍历{inti，visited[maxnode]；//数组visited标志图中的定点是否已被访问voiddfs()；for(i=0；i<n；i++)visited[i]=0;//数组初始化for(i=0；i<n；i++)if(visited[i]==0)dfs(g，i，visted)；}voiddfs(adjlistg，intk，intvisited[])//从顶点k出发，深度优先遍历图g。{arcnode*p；intw；visited[k]=1；printf(%d，g[k]，vertex)；p=g[k]，firstarc；while(p!=null){w=p->adjvex；if(visited[w]==0)dfs(g，w，visited)；p=p->nextarc；}}main(){inti，j，n，k，v；arcnode*p,*q;adjlistg；printf(“Inputnode：〞)；scanf(“%d〞，＆n)；for(k=0；k<n；k++)//构造图{printf(“node%d=〞，k)；g[k].firstarc=null；}for(；；){printf(“Insertedgei-j:〞)；scanf(“%d〞，＆i)；scanfi(“%d〞，＆j)；if(i==-1&&j==-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->nextarc=g[i].firstarc；g[i]firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->nextarc=g[i].firstarc;g[i]_firstarc=p；}printf(“dfs：〞)；trave(g，n)；//深度优先遍历图。printf(“\n〞);}内容4的知识要点：广度优先遍历图的算法：首先访问指定的起始顶点v0,从v0出发，访问v0的所有未被访问的邻接顶点w1，w2，…，wk，然后再依次从w1，w2，…，wk出发，访问所有未被访问过的邻接顶点，依此类推，直到图中所有未被访问过的邻接顶点都被访问过为止。根据广度优点遍历的规那么，在其算法实现中，借助一个队列g－queue来存放已被访问过的顶点。从指定顶点开场，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依此类推，直至队列为空且图中结点均被访问过为止。图的广度优先遍历次序为：①→②→③→④→⑤→⑥参考程序运行过程中，广度优先搜索时指针p的移动示意如以以下图所示，图中片p1、p2、p3、p4、p5和p6为广度优先遍历图的各结点指针p的移动次序。//内容4的参考程序#definemaxnode40#definenull0#include<sddio．h>typedefstructst_arc//定义构造体{intadivex；intweigh；structst_arc*nextarc；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；typedefstruct{intqueue[maxnode];intfront;intrear;}qqtype;voidintiate(qqtype*q)//初始化队列｛q->front=-1;q->rear=-1;}intenter(qqtype*q,intx)//将X入队{if(q->rear==maxnode-1)return(-1);else{q->rear++;q->queue[q->rear]=x;return(0);}}intdelete(qqtype*q)//出队{if(q->front==q->rear)return(null);else{q->front++;return(q->queue[q->front]);}}intemtype(qqtype*q){if(q->front==q->rear)return(-1);return(0);}voidbfs(adjlistg，intk，intvisited[])//从顶点k出发进展广度优先遍历{arcnode*p；intw；intiate(g);visited[k]=1;//访问点从k开场，并把它入队。printf(“%d〞,g[p->adjvex].vertex);enter(g,k);while(emptye(g)==0){w=delete(g);p=g[w].firstarc;while(p!=null){if(visited[p->adjves]==0){printf(“%d〞,g[p->adjvex].verte);visited[p->adjvex]=1;enter(g.p->adjvex);}p=p->nextarc;}}}voidtrave(adjlistg，intn)//图采用邻接表存储的广度优先遍历{inti，visited[maxnode]；//数组visited标志图中的定点是否已被访问。for(i=0；i<n；i++)visited[i]=0;//数组初始化for(i=0；i<n；i++)if(visited[i]==0)bfs(g，i，visted)；}main(){inti，j，n，k，v；arcnode*p,*q;adjlistg；printf(“Inputnode：〞)；scanf(“%d〞，＆n)；for(k=0；k<n；k++)//构造图{printf(“node%d=〞，k)；scanf(“%d〞,&g[k].vertex);g[k].firstarc=null；}for(；；){printf(“Insertedgei-j:〞)；scanf(“%d〞，＆i)；scanfi(“%d〞，＆j)；if(i==-1&&j==-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->nextarc=g[i].firstarc；g[i]firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->nextarc=g[i].firstarc;g[i]_firstarc=p；}printf(“bfs：〞)；trave(g，n)；//广度优先遍历图。printf(“\n〞);}六、选作实验假设有n个城市，要实现n个城市之间都能互相通信和构造n个城市之间的通信网，使工程总造价最低。设计一个能满足要求的最低造价方案。实验五查找实验目的：1.掌握查找的含义。2.掌握基本查找操作的算法与实现。3.掌握二叉排序树查找的算法与实现。4.掌握Hash表查找的算法与实现。二、实验内容：从以下1、2和3、4中各选择一项内容1.建设一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进展查找。〔为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据局部忽略不考虑。〕2.查找表的存储构造为有序表，即表中记录按关键字大小排序存放。输入待查数据元素的关键字进展查找。〔为了简化算法，记录只含一个整型量关键字字段，记录的其余数据局部略不考虑。程序要求对整型量关键字数据的输入按从小到大排序输入。〕3.编程实现二叉排序树的创立、查找、插入、输出等算法。4.设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建设算法。三、实验要求：1.根据实验内容编程，上机调试、得出正确的运行程序。2.写出实验报告〔包括源程序和运行结果〕。四、实验学时：6学时五、实验步骤：1．进入编程环境，建设一新文件；2.参考以下相关内容，编写程序，观察并分析输出结果。顺序查找的基本思想及程序实现对于给定的关键字k，从表的一端开场，逐个进展数据元素的关键字和给定值的比较，假设当前扫描到的结点关键字与k相等那么查找成功；假设扫描完毕后，仍未找到关键字等于k的节点，那么查找失败。建设一个顺序表，数据元素从下标为1的单元开场放入，下标为0的单元起监视哨作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，假设直到下标为0时才找到关键字那么说明查找失败；假设不到下标为0时就找到关键字，那么查找成功。//参考程序#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey；}SSELEMENT；typedefstruct{SSELEMENTr[MAXSIZE]；intlen；}SSTABLE；intseq_search(KEYTYPEk，SSTABLE*st)//顺序表查找元素{intj；j=st->len；//顺序表元素个数st->r[0].key=k；//st->r[0]单元作为监视哨while(st->r[j].key!=k)//顺序表从后向前查找j--;returnj；//j=0，找不到，j≠0找到}main(){SSTABLEa;inti，j，k；printf(〞请输入顺序表元素，元素为整型量，用空格分开，-99为完毕标志：〞)；j=0；k=1;i=0;scanf(〞%d〞，＆i)；while(i!=-99){j++；a.r[k].key=i；k++;scanf(〞%d〞，＆i)；}a.1en=j;printf(〞\n顺序表元素列表显示：〞)；for(i=1；i<=a.1en;i++)printf(〞%d〞，a.r[i].key)；printf(“\n〞);printf(〞\n输入待查元素关键字：〞)；scanf(“%d〞，&i)；k=seq_search(i，&a)；if(k==0)printf(“表中待查元素不存在\n\n〞)；elseprintf(“表中待查元素存在\n\n〞)；}折半查找的基本思想及程序实现：设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high]，要查找的关键字值为key，中间元素的下标为mid=(low+high)／2(向下取整)，令key与r[mid]的关键字比较：假设key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。假设key<r[mid].key，所要找的记录只能在左半局部记录中，再对左半局部使用折半查找法继续进展查找，搜索区间缩小了一半。假设key>r[mid].key，所要找的记录只能在右半局部记录中，再对右半局部使用折半查找法继续进展查找，搜索区间缩小了一半。重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key说明查找成功；或者出现low的值大于high的情况，说明查找不成功。建设一个有序表，数据元素从下标为1的单元开场放入。实现查找算法时，首先将low赋值为l，high等于最后一个数据元素的下标，然后将给定的关键字的值与查找区间[low，high]中间的数据元素的关键字比较，实现查找过程。//参考程序#include<stdio.h>#defineKEYTYPEjnt#defineMAXSIZE100typedefstruct{KEYTYPEkey；}SEELEMENT；typedefstruct{SSELEMENTr[MAXSIZE]；intlen；}SSTABLE；intsearch_bin(KEYTYPEk，SSTABLE*st)，//有序表上折半查找{intlow，high，mid；low=1；//low=l表示元素从下标为1的单元放起high=st->len；//high=st->len表示最后一个元素的下标while(1ow<=high)//low<=high为继续查找的条件{mid=(1ow+high)／2；if(k==st->r[mid].key)//k==st->r[mid].key表示查找成功retummid；elseif(k<st->r[mid].key)//否那么继续二分查找high=mid－l；elselow=mid+l；｝return0;//查找不成功，返回0}main(){{SSTABLEa;inti，j，k;printf(“请输入有序表元素，元素为整型量(从小到大输入)，用空格分开，-99为完毕标志：〞)；j=0；k=1;I=0;scanf(“%d〞，&i)；while(i!=-99){j++；a.r[k].key=i；k++;scanf(“%d〞,＆i)；//输入有序表元素}a.1en=j；printf(“\n有序表元素列表显示：〞)；for(i=l；i<=a.1en；i++)printf(“%d〞，a.r[i])；printf(“\n〞)；pfintf(〞\n输入待查元素关键字：〞)；scanf[“%d〞，＆i]；k=search_bin(i，&a)；if(k==0)printf("表中待查元素不存在\n\n")；elseprintf(〞表中待查元素存在\n\n")；}二叉排序树基本思想及程序实现二叉排序树就是指将原来已有的数据根据大小构成一棵二叉树，二叉树中的所有结点数据满足一定的大小关系，所有的左子树中的结点均比根结点小，所有的右子树的结点均比根结点大。二叉排序树查找是指按照二叉排序树中结点的关系进展查找，查找关键字首先同根结点进展比较，如果相等那么查找成功；如果比根结点小，那么在左子树中查找；如果比根结点大，那么在右子树中进展查找。这种查找方法可以快速缩小查找范围，大大减少查找关键字的比较次数，从而提高查找效率。算法的关键过程实际上就是二叉排序树的创立和查找两个步骤。首先分析二叉排序树的创立运算，由于二叉排序树中的所有结点都有一个大小关系，因此，每个结点必须在二叉排序树中寻找其适宜的位置。创立二叉排序树的第一步就是创立一个根结点，第二步就是将其他结点不断插入到二叉排序树中的适宜位置。二叉排序树进展结点插入时，首先要为被插入结点寻找适宜的插入位置。这个过程实际上就是一个关键值不断的比较的过程。第一次比较是与二叉排序树的根结点比较，如果比根结点的关键值小，那么插入到他的左子树中；如果比根结点的关键值大，那么插入到它的右子树中。在子树中重复这样过程，直到找到适宜的位置为止。二叉排序树的查找运算实际上同二叉排序树的创立运算是一致的。区别在于，创立过程中要为二叉排序树中没有位置的关键字建设结点，而查找过程中，只是在二叉排序树中查找是否等于查找关键字值的结点存在，不管有还是没有，它都不会创立一个新的结点。//参考程序#include<stdio.h>#include<malloc.h>#definenull0typedefintkeytype；//查找关键字为整型数据sturcBsnode//二叉排序树结点类型{keytypedata；//数据域structBsnode*Lchild,*Rchild；//左右指针};typedefstructBsnodeBST；typedefstructBsnode*BSP；//BSP为二叉排序树结点类型指针BSPcreateBst(keytypekey)//为关键字key创立一个二叉排序树结点{BSPs;s=(BSP)malloc(sizeof(BST))；s->data=key；s->Lchild=s->Rchild=null；return(s)；}BSPBSTinsert(BSPT，BSPS)//将S指向的结点插入到T指向的二叉排序树中{BSPq,p;if(T==null)return(S);else{p=T;q=null;while(p)//在二叉排序树中为s结点寻找插入位置{q=p；if(s->data==p->data)//如果S结点与二叉排序树中根结点的值相等，那么不插入{printf(“Theinputkey(%d)ishavein!〞，s->data)；return(t)；}if(s->data<p->date)//如果比根结点值小，那么在左子树中寻找插入位置p=p->Lchild；else//否那么在右子树中寻找插入位置p=p->Rchild；}if(s->data<q->data)q->Lchild=s；//作为左孩子插入elseq->Rchild=s；//作为右孩子插入return(t)；}}voidsearch(BSPT，keytypex)//在二叉排序树T中查找是否存在关键宇{BSPp；if(T==null){printf(“error\n〞);return;}else{p=Twhile(p){if(p->data==x)//如果根结点是查找的关键字，查找完毕{printf(“searchsuccess!\n〞)；return；}elseif(x<p->-data)//如果小于根结点，那么在左于树中查找p=p->Lchild；elsep=p->Rchild；//否那么，在右子树中查找}if(!p)printf(〞%dnotexist!\n〞，x)；}}voidBSTPrint(BSPT)//输出二叉排序树{if(T){BSTPrint(T->Lchild)；printf(〞%d->〞，T->data)；BSTPrint(T->Rchild)；}}main(){BSPT，S；keytypekey；intselect=0，flag=l；T=null；while(flag)//主菜单{printf(〞1…CreateBsort_tree\n〞)；printf(〞2…Insertkey\n〞)；printf(〞3…Searchkey\n〞)；printf(〞4…Quit\n〞)；printf(〞Pleaseselect：\n〞)；scanf(〞%d〞，＆select)；switch(select){casel：//创立二叉排序树{printf(〞PleaseinputkeytocreateBsort_Tree：\n〞)；scanf(〞%d〞，＆key)；while(key!==0){S=createBst(key)；T=BSTinsert(T，S)；printf(〞continueinput!\n〞)；scanf(“%d〞,＆key)；}printf(〞Bsort_Treeis：\n〞)；BSTPrint(T)；Printf(“\n\n〞)；break；}case2：//在二叉排序树中插入关键字{printf(〞Pleaseinputkeywhichinserted：\n〞)；scanf(“%d〞，&key)；S=createBst(key)；T=BSTinsert(T，S)；printf(〞Bsort_Treeis：\n〞)；BSTPrint(T)；printf(〞\n\n〞)；break；}case3：//在二叉排序树中查找关键字{printf(〞Pleaseinputkeywhichsearched：\n〞)；scanf(“%d〞，＆key)；search(T，key)；printf(〞\n\n);break；}case4：//产退出{flag=0；break；}}}}哈希表查找基本思想及程序实现哈希表查找是一种基于尽可能不通过比较操作而直接得到记录的存储位置的想法而提出的一种特殊查找技术。它的基本思想是通过记录中的关键字的值key为自变量，通过某一种确定的函数h，计算出函数值h(key)作为存储地址，将相应关键字的记录存储到对应的位置上。而在查找时仍需要用这个确定的函数h进展计算，获得所要查找的关键字所在记录的存储位置。除留余数法(DivisionMethod)是用关键字key除以某个正整数M，所得余数作为哈希地址的方法。对应的哈希函数h(key)为h(key)=key%M，一般情况下M的取值为不大于表长的质数。用开放定址法解决冲突，形成下一个地址的形式是Hi=(h(key)+di)%Mi=l，2，…，k(k≤m-1)式中，h(key)为哈希函数；M为某个正整数；di为增量序列。线性探测再散列是将开放定址法中的增量序列di设定为-系列从1开场一直到表长减l的整数序列：l，2，3，…,m－1〔m为表长)。算法的关键过程实际上就是Hash表的创立和查找两个步骤。首先分析Hash表的创立运算：将由键盘输入的关键字key作为自变量，通过除留余数法构造哈希函数h，计算出函数值h(key)作为存储地址，将该关键字存储到对应的位置上。如果产生冲突，那么采用线性探查法，从关键字的哈希地址开场向后扫描，直到找到空位置，将该关键字存储在这个位置，插入成功；假设扫描到哈希表的最后仍没有找到空位置，那么插入失败。查找时仍利用除留余数法构造哈希函数h，计算出函数值h(key)获得所要查找的关键字所在记录的存储位置。假设存储位置对应的数据元素的值与查找关键字相等，那么查找成功，否那么，采用线性探查法，从关键字的哈希地址开场向后扫描，直到找到与关键字相等的数据元素，查找成功；假设扫描到哈希表的最后仍没有找到与关键字相等的数据元素，那么查找失败，不存在与关键字相等的数据元素。//参考程序#include<stdio.h>//哈希表长最大值#defineHM20#defineM19#defineFREE0//空闲标记#defineSUCESS1//成功#defineUNSUCESS0//不成功typedefintkeytype；//keytype为整型typedefstruct//keytype型关键字key{keytypekey；intcn;