河南科技大学 数据结构Word格式.docx
- 文档编号:8120144
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:30
- 大小:26.53KB
河南科技大学 数据结构Word格式.docx
《河南科技大学 数据结构Word格式.docx》由会员分享,可在线阅读,更多相关《河南科技大学 数据结构Word格式.docx(30页珍藏版)》请在冰点文库上搜索。
1);
3深度为h的k叉树至多有(kh-1)/(k-1)个结点;
4具有n个结点的k叉树的最小深度为[logk(n(k-1)+1)](k为底数)
四、什么是二叉搜索数:
二叉搜索数又称二叉排序树,它或者是一棵空树,或者是一棵具有如下特性的非空二叉树:
(1)若它左子树非空,则左子树上所有结点的关键字均小于根结点的关键字;
(2)若它的右子树非空,则右子树上所有节点的关键字均大于(若允许具有相同的关键字的结点存在,则大于等于)根结点的关键字;
(3)左、右子树本身又各是一棵二叉搜索树
五、什么是图、子图、完全图、路径、回路、连通、网
1图是一种复杂的非线性数据结构。
2设有两个图G=(V,E)和G’(V’,E’),若V’是V的子集,即V’⊆V,且E’是E的子集,即E’⊆E,则称G’是G的子图。
3若无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方向相反的两条边,则称此图为完全图。
4在一个图G中,从顶点v到顶点v’的一条路径是一个顶点序列vi1,vi2,…,vim,其中v=vi1,v’=vim,若此图是无向图,则(vij-1,vij)∈E(G),(2≤j≤m);
若此图是有向图,则<
vij-1,vij>
∈E(G),(2≤j≤m)。
5若一条路径上的前后两端点相同,则被称为回路。
6在有向图G中,若从顶点vi到vj有路径,则称从vi到vj是连通的。
7边上带有权的图称作带权图,也常称作网。
六、一般从哪几个方面对算法进行评价?
正确性,健壮性,可读性,简单性,时间复杂度,空间复杂度。
七、给出广义表,画出树:
课本118页最上面的广义表,对应的树为图5-1
八、二叉树的性质:
1二叉树上终端结点数等于双分支结点数加1;
2二叉树上第i层上至多有2i-1个结点(i>
3深度为h的二叉树至多有2h-1(2的h次方减1)个结点;
4对完全二叉树中编号为i的结点(1≤i≤n,n>
1,n为结点数)有:
(1)若i≤n/2,即2i≤n,则编号为i的结点为分支结点,否则为叶子结点。
表达式x表示对x进行向下取整。
(2)若n为奇数,则树中每个分支结点都既有左孩子,又有右孩子;
若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有。
(3)若编号为i的结点有左孩子,则左孩子结点的编号为2i;
若编号为i的结点有右孩子,则右孩子结点的编号为2i+1,即遵循对一般二叉树的编号规则。
(4)除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为n/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子。
此点也适合于一般二叉树。
5具有n个(n>
0)结点的完全二叉树的深度为log2(n+1)或log2n+1。
九、二叉树有几种遍历递归算法?
并写出算法。
前序遍历算法
voidPreorder(structBTreeNode*BT)
{if(BT!
=NULL){
printf("
%c"
BT->
data);
Preorder(BT->
left);
right);
}
}
中序遍历算法
voidInorder(structBTreeNode*BT)
{if(BT!
Inorder(BT->
后序遍历递归算法
voidPostorder(structBTreeNode*BT)
Postorder(BT->
printf("
十、什么是哈夫曼树?
写出它的具体算法
哈夫曼(Huffman)树又称作最优二叉树。
它是n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树。
算法如下:
(1)根据与n个权值{w1,w2,…,wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2,…,Tn},其中每棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点,其左、右子树均为空;
(2)在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树,且置新树的根结点的权值为其左、右子树上根结点的权值之和;
(3)从F中删除构成新树的那两棵树,同时把新树加入F中;
(4)重复
(2)和(3)步,直到F中只含有一棵树为止,此树便是哈夫曼树。
十一、什么是栈,栈顶,栈顶元素,栈底,进栈,出栈
1栈(stack)又称堆栈,它是一种运算受限的线性表,其限制是仅允许在表的一端进行插入和删除运算。
2人们把对栈进行运算的一端称为栈顶。
3栈顶的第一个元素被称为栈顶元素。
4相对地,把另一端称为栈底。
5向一个栈插入新元素又称为进栈或入栈,它是把该元素放到栈顶元素的上面,使之成为新的栈顶元素。
6从一个栈删除元素又称为出栈或退栈,它是把栈顶元素删除掉,使其下面的相邻元素成为新的栈顶元素。
普里姆算法
voidPrim(adjmatrixGA,edgesetCT,inta,intn)
{inti,j,k,min,t,m,w;
structedgeElemx;
for(i=0;
i<
n;
i++){
if(i<
a){CT[i].fromvex=a;
CT[i].endvex=i;
CT[i].weight=GA[a][i];
elseif(i>
a){
CT[i-1].fromvex=a;
CT[i-1].endvex=i;
CT[i-1].weight=GA[a][i];
}
for(k=1,k<
k++)
{min=MaxValue;
m=k-1;
for(j=k-1;
j<
n-1;
j++)
if(CT[j].weight<
min){
min=CT[j].weight;
m=j;
x=CT[k-1];
CT[k-1]=CT[m];
CT[m=x];
j=CT[k-1].endvex;
for(i=k;
t=CT[i].endvex;
w=GA[j][t];
if(w<
CT[i].weight){
CT[i].weight=w;
CT[i].fromvex=j;
}
P163向堆中插入一个元素的算法描述为:
voidInsertHeap(structHeapSq*HBT,ElemTypex)
{inti;
if(HBT->
len==HBT->
MaxSize){
ElemType*p;
p=realloc(HBT->
heap,2*HBT->
MaxSize*sizeof(ElemType));
if(!
p){printf("
存储空间用完!
\n"
);
exit
(1);
HBT->
heap=p;
HBT->
MaxSize=2*HBT->
MaxSize;
}
HBT->
heap[HBT->
len]=x;
len++;
i=HBT->
len-1;
while(i!
=0){
intj=(i-1)/2;
if(x>
=HBT->
heap[j])break;
heap[i]=HBT->
heap[j];
i=j;
heap[i]=x;
克鲁斯卡尔算法
voidKruskal(edgesetGE,edgesetC,intn)
{inti,j,k,d;
intm1,m2;
adjmatrixs;
for(i=1;
i++)
{for(j=0;
if(i==j)s[i][j]=1;
elses[i][j]=0;
k=1;
d=0;
while(k<
n)
{for(i=0;
if(s[i][GE[d].fromvex]==1)m1=i;
if(s[i][GE[d].endvex]==1)m2=i);
if(m1!
=m2){
C[k-1]=GE[d];
k++;
for(j=0;
n,j++){
s[m1][j]=s[m1][j]||s[m2][j];
s[m2][j]=0;
}}
d++
P187图的遍历深度优先搜索遍历
voiddfs1(adjmatrixGA,inti,intn)/*从初始点vi出发深度优先搜索由邻接矩阵GA表示图*/
{intj;
printf("
%d"
i);
visited[i]=1;
for(j=0;
j<
j++)
if(GA[i][j]!
=0&
&
GA[i][j]!
=MaxValue&
!
visited[j])
dfs1(GA,j,n);
(以邻接矩阵)广度优先搜索遍历的过程p189
voidbfs1(adjmatrixGA,inti,intn)
{structQueueSqQ;
InitQueue1(&
Q);
printf("
visited[i]=1;
EnQueue(&
Q,i);
while(!
EmptyQueue(&
Q)){
intj;
intk=OutQueue(&
for(j=0;
j++){
if(GA[k][j]!
GA[k][j]!
visited[j]){
j);
visited[j]=1;
EnQueue(&
Q,j);
(以邻接表)广度优先搜索遍历的过程p189
voidbfs2(adjlistGL,inti,intn)
intk=OutQueue(&
structedgenode*p=GL[k];
while(p!
=NULL){
intj=p->
adjvex;
if(!
visted[j]){
visited[j]=1;
p=p->
next;
162初始化堆
voidInitHeap(structHeapSq*HBT,intMS)
{if(MS<
=0){
print(“数组长度参数值不合适,需重新给定\n”);
exit
(1);
HBT->
heap=malloc(MS*sizeof(ElemType));
if(!
heap){
print(“内存空间用完,退出\n”);
MaxSize=MS;
len=0;
157从二叉搜索树中删除等于给定值x的结点,若删除成功则返回1,否则返回0。
intDelete(structBTreeNode**BST,ElemTypex);
152(二叉树的应用)二叉搜索树(查找)
ElemType*Find(structBTreeNode*BST,ElemTypex)
{/*从二叉搜索树中查找等于给定值x的元素*/
if(BST==NULL)returnNULL;
else{
if(x==BST->
data)return&
(BST->
elseif(x<
BST->
data)
returnFind(BST->
left,x);
else
right,x);
向二叉树中插入元素
voidInsert(structBTreeNode**BST,ElemTypex)
/*向二叉搜索树中插入一个元素x*/
{if(*BST==NULL){
structBTreeNode*p=malloc(sizeof(structBTreeNode));
p->
data=x;
left=p->
right=NULL;
*BST=p;
elseif(x<
(*BST)->
data)Insert(&
((*BST)->
left),x);
elseInsert(&
right),x);
142从树中查找结点值
ElemType*FindGTree(structGTreeNode*GT,ElemTypex)
{if(GT==NULL)returnNULL;
else{ElemType*p;
inti;
if(GT->
data==x)return&
(GT->
for(i=0;
i<
kk;
i++)
if(p=FindGTree(GT->
t[i],x))returnp;
returnNULL;
140树的运算出树的先根遍历算法:
voidPreRoot(structGTreeNode*GT)
{inti;
if(GT!
printf("
GT->
for(i=0;
PreRoot(GT->
t[i]);
二叉树后根遍历voidPostRoot(structGTreeNode*GT)
PostRoot(GT->
二叉树树的按层遍历
voidLayerOrder(structGTreeNode*GT)
{structGTreeNode*p;
inti;
structGTreeNode*q[MQ];
intfront=0,rear=0;
rear=(rear+1)%MQ;
q[rear]=GT;
while(front!
=rear){
front=(front+1)%MQ;
p=q[front];
p->
i++)
if(p->
t[i]!
rear=(rear+1)%MQ;
q[rear]=p->
t[i];
139建立树
130建立二叉树
132求二叉树深度的递归算法如下:
intBTreeDepth(structBTreeNode*BT)
{if(BT==NULL)return0;
else{intdep1=BTreeDepth(BT->
intdep2=BTreeDepth(BT->
if(dep1>
dep2)
returndep1+1;
else
returndep2+1;
132二叉树中查找值为x的结点,若存在则返回元素存储位置,否则返回空值
ElemType*FindBTree(structBTreeNode*BT,ElemTypex)
{if(BT==NULL)returnNULL;
else{
if(BT->
(BT->
else{ElemType*p;
if(p=FindBTree(BT->
left,x))returnp;
right,x))returnp;
returnNULL;
129二叉树按层遍历算法(非递归)
voidLevelorder(structBTreeNode*BT)
{structBTreeNode*p;
structBTreeNode*q[QueueMaxSize];
intfront=0,rear=0;
if(BT!
rear=(rear+1)%QueueMaxSize;
q[rear]=BT;
front=(front+1)%QueueMaxSize;
p=q[front];
if(p->
left!
rear=(rear+1)%QueueMaxSize;
left;
right!
right;
队列
106初始化队列
一用于存储队列的固定大小的动态存储空间,假定动态存储空间的大小为10。
voidInitQueue(structQueueSq*Q)
{/*置队列空间初始最大长度为10*/
Q->
MaxSize=10;
Q->
queue=malloc(10*sizeof(ElemType));
Q->
front=Q->
rear=0;
第二种情况是分配由参数指定大小的动态存储空间。
实用中使用任一种初始化算法均可。
voidInitQueue(structQueueSq*Q,intms)
{if(ms<
=0){printf("
ms值非法!
MaxSize=ms;
Q->
queue=malloc(ms*sizeof(ElemType));
queue){
内存空间用完!
2向队列插入元素
voidEnQueue(structQueueSq*Q,ElemTypex)
{if((Q->
rear+1)%Q->
MaxSize==Q->
front)againMalloc(Q);
rear=(Q->
queue[Q->
rear]=x;
againMalloc()算法的具体定义如下:
voidagainMalloc(structQueueSq*Q)
{ElemType*p;
p=realloc(Q->
queue,2*Q->
p){
queue=p;
if(Q->
rear!
=Q->
MaxSize-1){
rear;
Q->
queue[i+Q->
MaxSize]=Q->
queue[i];
Q->
rear+=Q->
MaxSize=2*Q->
3从队列中删除元素并返回
ElemTypeOutQueue(structQueueSq*Q)
{if(Q->
front==Q->
rear){
队列已空,无法删除!
front=(Q->
front+1)%Q->
returnQ->
front];
110向链队中插入一个元素
voidEnQueue(structQueueLk*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 河南科技大学 数据结构 河南 科技大学