课程设计终极版Word文件下载.docx
《课程设计终极版Word文件下载.docx》由会员分享，可在线阅读，更多相关《课程设计终极版Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。
return（H）;
}
voidOutputlist（structLinkList*Head）
{structLinkList*H;
H=Head;
链表是：
\n"
while（H!
=NULL）
{printf（"
%d"
H->
data）;
H=H->
next;
printf（"
LengthLList（structLinkList*L）
{intLength=0;
structLinkList*p=L;
while（p!
{p=p->
Length++;
returnLength;
voidDeleteLList（structLinkList*L）
{inta;
structLinkList*p,*s;
输入要删除的数：
a）;
if（L->
next==NULL）return;
p=L;
s=p;
while（（p->
next!
=NULL）&
&
（p->
data!
=a））
{s=p;
p=p->
if（p==NULL）{printf（"
链表中无此数\n"
return;
}
s->
next=p->
free（p）;
已删除\n"
structLinkList*NIXU（structLinkList*h）
{structLinkList*p,*r,*s;
r=h;
p=r->
s=p->
if（h==NULL）printf（"
空链表\n"
while（s!
=NULL&
h!
{p->
next=r;
r=p;
p=s;
s=s->
h->
p->
returnp;
voidmain（）
structLinkList*head;
while
（1）
{printf（"
功能：
1:
建立链表\n"
2:
输出链表\n"
3:
计算链表长度\n"
4:
删除链表结点\n"
5:
链表逆序\n"
6:
退出\n"
输入功能:
scanf（"
if（a<
=6&
a>
=1）
{switch（a）
{case1:
head=CreatLList（）;
break;
case2:
Outputlist（head）;
case3:
链表长度是:
%d\n"
LengthLList（head））;
case4:
DeleteLList（head）;
case5:
head=NIXU（head）;
case6:
exit（0）;
break;
default:
}
else{printf（"
错误的功能号码\n"
实验二
1、动态交互建立二叉树，结点个数任意；
2、分别用DLR、LDR、LRD三种方式对二叉树进行便利并输出结果；
3、计算二叉树中的结点个数并输出；
4、计算二叉树的深度并输出；
#include"
stdio.h"
malloc.h"
structBTNode
{
intdata;
structBTNode*Lchild,*Rchild;
structBTNode*build（structBTNode*p）;
structBTNode*creatrent（structBTNode*p）;
voidDLR（structBTNode*T）;
structBTNode*creatrent（structBTNode*p）
intx;
输入根：
rent="
if（x==1000）{p=NULL;
else
{
p->
p->
Lchild=（structBTNode*）malloc（sizeof（structBTNode））;
Rchild=（structBTNode*）malloc（sizeof（structBTNode））;
if（p==NULL）returnp;
Lchild=build（p->
Lchild）;
Rchild=build（p->
Rchild）;
returnp;
structBTNode*build（structBTNode*p）
输入数据（输入值为时999，表示该结点为空）：
value="
if（x==999）{p=NULL;
if（p==NULL）returnp;
returnp;
voidDLR（structBTNode*T）
if（T==NULL）return;
T->
DLR（T->
voidLDR（structBTNode*T）
LDR（T->
voidLRD（structBTNode*T）
LRD（T->
structBTNode*rent=NULL;
intflag;
while
（1）
{
printf（"
选择输入的操作：
\n1：
创建；
\n2：
先序；
\n3：
中序;
\n4：
后序\n"
flag）;
switch（flag）
case1:
rent=（structBTNode*）malloc（sizeof（structBTNode））;
rent=creatrent（rent）;
case2:
DLR（rent）;
case3:
LDR（rent）;
LRD（rent）;
实验三
1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果；
2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果；
#include<
malloc.h>
#defineK1000
#defineVNum6
structGLink
{intNo;
intRight;
structGLink*Relat;
};
intG[VNum][VNum]=//初始化//
{
0,50,10,K,45,K,
K,0,15,50,10,K,
20,K,0,15,K,K,
K,20,K,0,35,K,
K,K,K,30,0,K,
K,K,K,3,K,0
structGLink*GL[VNum];
intVisited[VNum];
voidCreateGLink（intG[VNum][VNum]）//建立邻接表//
{inti,j;
structGLink*p,*q;
for（i=0;
i<
VNum;
i++）
{GL[i]=q=NULL;
for（j=0;
j<
j++）
{if（i!
=j）
if（（G[i][j]>
0）&
（G[i][j]<
K））
//该两点存在有向路径//
{p=（structGLink*）malloc（sizeof（structGLink））;
p->
No=j;
//将该点加入邻接表//
Right=G[i][j];
if（GL[i]==NULL）
GL[i]=p;
else
q->
Relat=p;
q=p;
}
}
}
voidDFS（intA[VNum][VNum],intV）//用于进行深度优先遍历的子函数，V是起点//
{inti;
[%d]"
V）;
Visited[V]=1;
//将其标记为已访问//
for（i=0;
i<
VNum;
if（（A[V][i]>
（A[V][i]<
K）&
（Visited[i]!
=1））//该结点未被访问过//
DFS（A,i）;
//访问该点//
for（i=0;
i++）
if（Visited[i]!
=1）DFS（A,i）;
//仍有未必访问过的点，访问该点//
voidBFS（intA[VNum][VNum],intV）//广度优先遍历的子函数//
{intCQ[VNum];
inta=0,b,c;
inti,k=1;
i<
i++）
CQ[i]=K;
//标志为访问过//
CQ[0]=V;
[%d]"
V）;
//将该结点放入队列//
while（k<
6&
a<
k）//仍有结点未被访问并且队列中仍有结点的后继结点未被访问//
{b=CQ[a];
for（c=0;
c<
c++）//依次将队列中以结点为首的邻接表中的结点插入队列//
if（Visited[c]==0&
A[b][c]<
K&
A[b][c]!
=0）
{printf（"
c）;
CQ[++k]=c;
//未被访问过，将其插入到队列中//
Visited[c]=1;
a++;
for（i=0;
if（Visited[i]==0）
BFS（A,i）;
voidShort（intA[VNum][VNum],intV）//用于计算最短路径的子函数，V是起点//
{intDist[VNum],Path[VNum];
intS=0;
inti,k;
intwm,u;
{Dist[i]=A[V][i];
//默认这两点之间即为最短路径//
if（Dist[i]<
K）Path[i]=V;
//存储该路径//
S=S|（1<
<
V）;
for（k=0;
k<
k++）
{wm=K;
u=V;
for（i=0;
if（（（S&
（1<
i））==0）&
（Dist[i]<
wm））
//该两点间存在路径//
{u=i;
wm=Dist[i];
}
S=S|（1<
u）;
for（i=0;
（（Dist[u]+A[u][i]）<
Dist[i]））
{Dist[i]=Dist[u]+A[u][i];
//找到新的最短路径//
Path[i]=u;
//更新路径长度//
i++）//输出该源结点到其他各点的最短路径//
if（（S&
i））!
=0）
{k=i;
while（k!
=V）
{printf（"
%d<
-"
k）;
k=Path[k];
}
printf（"
%d"
=%d\n"
Dist[i]）;
elseprintf（"
NoPath:
%d"
i）;
main（）
{inti,j,a,b;
//a为功能号，i用作循环，j，b为函数参数
CreateGLink（G）;
1.深度查找\n"
//功能选择//
2.广度查找\n"
3.最短路径\n"
4.退出exit\n"
while
（1）
\npleaseinputanumfrom1to4:
"
scanf（"
if（a==1）//深度查找
{for（i=0;
Visited[i]=0;
pleaseinputthefirstnode:
j）;
\nTheresultofDFSis:
DFS（G,j）;
if（a==2）//广度查找
\nTheresultofBFSis:
BFS（G,j）;
if（a==3）//最短路径
pleaseinputthesourcenode:
b）;
\nTheresultofshortestpathis:
Short（G,b）;
if（a==4）break;
实验四
在交互方式下完成下类任务：
1、任意给定无序系列，用快速排序法对其进行排序，并统计交换次数。
2、任意给定的无序序列，用对半检索法交互检索任意给定的关键字KEY
3、任意给定无序系列，用冒泡排序法对其进行排序，并统计交换次数和排序的趟数
intji;
voidhalfhalf（inta[8],intn,intkey）//对半检索
{intlow,high,mid,flag;
low=0;
high=n-1;
flag=0;
while（low<
=high）
{mid=（low+high）/2;
if（a[mid]==key）{flag=1;
elseif（key>
a[mid]）low=mid+1;
elsehigh=mid-1;
if（flag==1）printf（"
是第%d个元素"
mid+1）;
elseprintf（"
没有此数?
!
voidpop（inta[8],intn）//冒泡检索
{inti,j,temp,flag;
intjiao,tang;
jiao=tang=0;
n-1;
{flag=1;
for（j=0;
j<
n-i-1;
j++）
if（a[j+1]<
a[j]）{temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
jiao++;
tang++;
if（flag==1）break;
\n交换次数和排序的趟数分别是%d和%d"
jiao,tang）;
voidquick（inta[8],intlow,inthigh）//快速检索
{inti,j;
inttemp;
if（low>
=high）return（0）;
i=low;
j=high;
temp=a[i];
while（i!
=j）
{while（（a[j]>
=temp）&
（j>
i））j--;
if（j>
i）{a[i++]=a[j];
ji++;
}
while（（a[i]<
i））i++;
i）{a[j--]=a[i];
a[i]=temp;
quick（a,low,i-1）;
quick（a,i+1,high）;
inti,a[8],n,q,p,t;
do{printf（"
\n1.对半检索检索关键字KEY"
\n2.快速排序法排序，统计交换次数"
\n3.冒泡排序法排序，统计交换次数"
\n4.退出"
\n请输入功能号:
i）;
while（i<
1||i>
4）
{printf（"
\nTheorderyouprintiswrong!
pleaseprintagain!
switch（i）
{case1:
输入数据\n"
for（n=0;
n<
8;
n++）scanf（"
a[n]）;
do{printf（"
输入检索关键字\n"
scanf（"
q）;
halfhalf（a,8,q）;
printf（"
\n输入1则继续检索:
p）;
}while（p==1）;
case2:
i=0;
quick（a,0,7）;
\快速排序交换次数是"
\n排序结果是"
for（n=0;
n++）printf（"
a[n]）;
case3:
pop（a,8）;
\n结果是"
for（n=0;
break;
case4:
再见"
}while（i!
=4）;
升级会员 