青岛科技大学考研内部资料《数据结构》

1、栈的应用举例编程序判断一个字符序列是否是回文。编程序判断一个字符序列是否是回文。编程思想：编程思想：设字符数组设字符数组str中存放了要判断的字符中存放了要判断的字符串。把字符数组中的字符串。把字符数组中的字符逐个逐个分别分别存入存入队队列和堆栈列和堆栈，然后逐个出队列和退栈并，然后逐个出队列和退栈并比较比较出队列的字符和退栈的字符出队列的字符和退栈的字符是否相等，若是否相等，若全部相等则该字符序列是回文，否则就不全部相等则该字符序列是回文，否则就不是回文。是回文。 算法思想： 1、初始化一个栈和队列 2、将字符数组输入栈和队列 3、 从栈和队列分别删除一个元素，并比较2个元素： 若相同，则重

2、复步骤3，直到栈和队列空为止； 若不相同，则退出。 void HuiWen(char str) length = strlen(str); QueueInitiate(&myQueue); StackInitiate(&myStack); for(i = 0; i kind); switch (G-kind) case DG : return CreateDG(G); case DN : return CreateDN(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : re

3、turn ERROR; Status CreateUDN(Mgraph *G) /建立无向网建立无向网 scanf(G- vexnum,G-arcnum,&info);/info为为0,表示各弧无信息表示各弧无信息 for (i=0 ; ivexnum; +i) scanf(G-vexsi); /构造顶点向量构造顶点向量 for (i=0 ; ivexnum; +i) /初始化邻接矩阵初始化邻接矩阵 for(j=0 ; jvexnum; +j) G-arcsij=INFNITY,NULL; for (k=0;karcnum;k+) scanf(&v1,&v2,&

4、w); /输入一条边依附的及权值输入一条边依附的及权值 i=LocateVex(G,v1) ; j= LocateVex(G,v2) ; /确定确定v1、v2在图中的在图中的位置位置 G-arcsij.adj=w; /弧的弧的的权值的权值 if (info) InPut(*G-); /若弧有相关信息若弧有相关信息 G-arcsji= G-arcsij; /置置的对称弧的对称弧 /END 在邻接矩阵存储结构上实现在邻接矩阵存储结构上实现FIRST-ADJ(G,V)FIRST-ADJ(G,V)算算法法: : 1 1、用、用LocatVexLocatVex（G G，V V）找到

5、）找到V V在图中的位置在图中的位置i i； 2 2、找出二维数组中第、找出二维数组中第i i行第一个非零值对应的行第一个非零值对应的列号列号j j； 3 3、j j就是就是V V的第一个邻接点在图中的位置；的第一个邻接点在图中的位置； 4 4、G.VexG.Vex（j j）就是）就是V V的第一个邻接点的第一个邻接点. . 在邻接矩阵存储结构上实现在邻接矩阵存储结构上实现FIRST-ADJ(G,V)FIRST-ADJ(G,V)算算法法: : 1 1、用、用LocatVexLocatVex（G G，V V）找到）找到V V在图中的位置在图中的位置i i； 2 2、找出二维数组中第、找出二维数组

6、中第i i行第一个非零值对应的行第一个非零值对应的列号列号j j； 3 3、j j就是就是V V的第一个邻接点在图中的位置；的第一个邻接点在图中的位置； 4 4、G.VexG.Vex（j j）就是）就是V V的第一个邻接点的第一个邻接点. .二、图的邻接表存储表示它是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边（或弧的信息）adjvex nextarc info弧的结点结构 data firstarc顶点的结点结构typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNod

7、e *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义

8、 对于下面的对于下面的AOE网：网： 1、求出各个事件的最早发生时间和最晚、求出各个事件的最早发生时间和最晚发生时间，并回答完成整个工程最少需发生时间，并回答完成整个工程最少需要多少时间？要多少时间？ 2、计算各个活动的最早开始时间和最迟、计算各个活动的最早开始时间和最迟开始时间，并找出所有的关键活动和关开始时间，并找出所有的关键活动和关键路径。键路径。v0v1v3v2v4v5v6v7v8v93585644 27365893#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存

9、储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示例如例如: A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 130ABCDEF1413261、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想: : 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。void CountLeaf (BiTree T, int& coun

10、t) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf 在一棵以二叉链表表示的二叉树上，试写在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计出用按层次顺序遍历二叉树的方法，统计树中具有度为树中具有度为1的结点数目的算法。的结点数目的算法。 int Level(BiTree *bt) int num=0; /num统计度为1的结点的个数 if(bt) Que

11、ueInit(Q); QueueIn(Q,bt)；/Q是以二叉树结 点指针为元素的队列 while(!QueueEmpty(Q) p=QueueOut(Q); printf(p-data); /出队,访问结点 if(p-lchild & !p-rchild |!p-lchild & p-rchild) num+; /度为1的结点 if(p-lchild) QueueIn(Q,p-lchild); /非空左子女入队 if(p-rchild) QueueIn(Q,p-rchild); /非空右子女入队 /if(bt) return(num); /返回度为1的结点的个数 在一棵以二叉

12、链表表示的二叉树上，试写出用按层次在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为顺序遍历二叉树的方法，统计树中具有度为1 1的结点数的结点数目的算法。目的算法。int Level(BiTree int Level(BiTree * *bt) bt) int num=0; /numint num=0; /num统计度为统计度为1 1的结点的个数的结点的个数 if(bt)if(bt) QueueInit(Q); QueueIn(Q,bt) QueueInit(Q); QueueIn(Q,bt)； while(!QueueEmpty(Q)while(!Queue

13、Empty(Q)p=QueueOut(Q); printf(p-data);/p=QueueOut(Q); printf(p-data);/出队出队, ,访问结点访问结点if(p-lchild & !p-rchild |!p-lchild &p-rchild)if(p-lchild & !p-rchild |!p-lchild &p-rchild) num+; / num+; /度为度为1 1的结点的结点if(p-lchild) QueueIn(Q,p-lchild);/if(p-lchild) QueueIn(Q,p-lchild);/非空左子女入队非空左子女

14、入队if(p-rchild) QueueIn(Q,p-rchild);/if(p-rchild) QueueIn(Q,p-rchild);/非空右子女入队非空右子女入队 /if(bt) /if(bt) return(num); /return(num); /返回度为返回度为1 1的结点的个数的结点的个数 typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTE

15、X_NUM MAX_VERTEX_NUM;typedef struct / 图的定义图的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点信息顶点信息 AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;Status CreateGraph(Mgraph *G) /建立图的邻接矩阵结构 scanf(G-kind); switch (G-kind) case DG : return CreateDG(G); case DN : return CreateD

16、N(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : return ERROR; Status CreateUDN(Mgraph *G) /建立无向网 scanf(G- vexnum,G-arcnum,&info);/info为0,表示各弧无信息 for (i=0 ; ivexnum; +i) scanf(G-vexsi); /构造顶点向量 for (i=0 ; ivexnum; +i) /初始化邻接矩阵 for(j=0 ; jvexnum; +j)G-arcsij=INFNITY

17、,NULL; for (k=0;karcnum;k+) scanf(&v1,&v2,&w); /输入一条边依附的及权值 i=LocateVex(G,v1) ; /确定v1,v2在图中的位置 j= LocateVex(G,v2) ; /确定v1,v2在图中的位置 G-arcsij.adj=w; /弧的的权值 if (info) InPut(*G-); /若弧有相关信息G-arcsji= G-arcsij; /置的对称弧 /END在邻接矩阵存储结构上实现在邻接矩阵存储结构上实现FIRST-ADJ(G,V)FIRST-ADJ(G,V)算法算法: :(1)

18、(1)用用LocatVexLocatVex（G G，V V）找到）找到V V在图中的位置在图中的位置i i；(2)(2)找出二维数组中第找出二维数组中第i i行第一个非零值对应的列号行第一个非零值对应的列号j j；(3)j(3)j就是就是V V的第一个邻接点在图中的位置；的第一个邻接点在图中的位置；(4)G.Vex(4)G.Vex（j j）就是）就是V V的第一个邻接点。的第一个邻接点。2. 2. 图的邻接表存储表示图的邻接表存储表示它是一种顺序存储与链式存储相结合的存储方法，顺它是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分序存储部分用来保存图中顶

19、点的信息，链式存储部分用来保存图中边（或弧的信息用来保存图中边（或弧的信息）adjvex nextarc info弧的结点结构弧的结点结构 data firstarc顶点的结点结构顶点的结点结构typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构顶点的结点结构typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义图的结