第一篇：数据结构电子教案 第七章
同步综合练习及参考答案
（一）基础知识题
7．1 在图7.23所是的各无向图中：
（1）找出所有的简单环。
（2）那些图是连通图？对非连通图给出其连通分量。
（3）那些图是自由树（或森林）？ //自由树的概念见 7.4节 解：
（1）简单环
（a）(1 2 3 1)(b)无
(c)（1 2 3 1）（2 3 4 2）（1 2 4 3 1）(d)无
（2）连通图（a）（c）（d）
非连通图（b）的连通分量为（3）自由树（d）
森林（b）
7．2 在图7.24所是的有向图中：
（1）该图是强连通的码？若不是，则给出其强连通分量。（2）请给出所有简单路径及有向环。（3）请给出每个顶点的度、入度和出度。（4）请给出其邻接表、邻接矩阵及逆邻接表。解：
（1）图是强连通的。
（2）所有简单路径（重复环未计算）
（v1）（v2）（v3）（v4）
(v1 v2)(v2 v3)(v3 v1)(v1 v4)(v4 v3)(v1 v2 v3)(v2 v3 v1)(v3 v1 v4)(v3 v1 v2)(v1 v4 v3)(v4 v3 v1)（v1 v2 v3 v1）（v2 v3 v1 v4）（v3 v1 v4 v3）（v4 v3 v1 v2）有向环
（v1 v2 v4 v1）（v4 v1 v4 v4）(3)各顶点的度、入度、和出度。(4)①邻接表
① 邻接矩阵集。② 逆邻接表
7．3 假设图的顶点是A,B,„,请根据下属的邻接矩阵画出相应的无向图或有向图。
解：
7．4 假设一颗完全二叉树包含A,B,„,G第七个结点，写出其邻接表和邻接矩阵。解：
① 完全二叉树 ② 邻接矩阵 ③ 邻接表
7．5 对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：
（1）图中有多少条边？（2）任意两个顶点I和j是否有边相连？（3）任意一个顶点的度是多少？ 解：
① 对于无向图
（1）图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的一半。
（2）若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。
（3）顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j.② 对于有向图
（1）图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。（2）若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连 ；
邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。
（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；
邻接表中i得出边表结点个数加上边表中结点I的个数之和。
7．6 n个顶点的连通图至少有几条边？强连通图呢？ 解：
①n个顶点的连通图至少有n-1条边。②n个顶点的强连通图至少有n条边。
7．7 DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？ 解：
①DFS采用了栈；BFS采用了队列。
②采用BFS。
7．8画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。解：
7．9按顺序输入顶点对：（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4），（6，5），（4，5），（1，5），（3，5），根据第7.2.2节中算法CreateALGraph画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。解：
依题意构造有向图： ①邻接表
②DFS和BFS序列
DFS序列：4 5 3 1 6 2 BFS序列：4 5 3 6 1 2 ③DFS和BFS生成树
DFS生成树 BFS生成树
7.10什么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成数的时间各为多少？他们分别适合于哪个图？
解：①具有n的结点，n-1条边的连通图其生成树是唯一的。① 的结点，e条边的无向连通图求最小生成树的时间分别为
Prim: O(n2);Kruskal:O(e*log2e)② Prim适应于稠密图（点少边多）；Kruskal 适应于稀疏图（点多边少）。
7．11 对图7.26所示的连通图，请分别用Pirm和Kruskal 算法构造其最小生成树。解：
① Pirm算法构造的生成树。② Kruskal 算法构造的生成树。
7．12 对图7.27所示的有向网，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行短发过程中扩充红点集的每天次循环状态（类似表7.2）.解：
7．13 是写出图7.28所示有向图的所有拓扑序列，并指出应用教材中 NonPrefirtTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。解：
NonPreFirtTopSort算法求得的序列是： V0 V1 V5 V2 V6 V3 V4 其余序列有多种（略）。
7．14 什么样的DAG的拓扑序列是唯一的？ 解：
设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。
7．15 以V4为源点，给出用DFS搜索7.28的道德你拓扑序列。V4 V3 V2 V0 V1 V5 V6.（二）算法设计题
7．16 试在无向图的邻接矩阵和邻接表上实现如下算法：（1）往图中插入一个顶点（2）往图中插入一条边（3）删去图中某顶点（4）删去图中某条边 解：
（1）插入给定结点
① 邻接表
viod Inser-ALGraph(ALGraph *G,int k){ int i;G->n++;for(i=G->n;i>k;i--){ G->adjlist[i].vertex=G->adjlist[i-1].vertex;G->adjlist[i].firstedge=G->adjlist[i-1].Firstedge;} G->adjlist[i].vertex=getchar();G->adjlist[i].firstedge=Null;} ② 邻接矩阵
void Inser-Mgraph(mGraph *G,int k){int i,j;G->n++;for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1];G->cexs[k]=getchar();for(i=G->n;i>k;i--){ for(j=G->n;j>k;j--)G->e[i][j]=G->e[i-1][j-1];G->e[i][j]=0;for(j=k-1;j>=0;j--)G->e[i][j]=G->e[i-1][j];} for(j=G->n;j>=0;j--)G->e[i][j]=0;for(i=k-1;i>=0;j--){ for(j=g->n;j>k;j--)G->e[i][j]=G->e[i][j-1];G->e[i][j]=0 } } ⑵插入一条边 ① 邻接表
InsertLAGraph(ALGraph *G,int m,INT n){ EdgeNode *E;EdgeNode *sm=new EdgeNode;EdgeNode *sn=new Edgenode;Sm->adjvex=n;sm->next=Null;Sn->adjvex=m;sn->next=Null;for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next){ } E=sm;for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next){ } E=sn;} ② 邻接矩阵
void InsertLMGraph(mGraph *G,int m,int n){ G->e[m][n]=1;}（3）删除某结点 ① 邻接表
void DelVALGraph(ALGraph *g,int k){ int I;G->n--;EdgeNode *e *s;for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next){ for(s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next)if(s->adjvex==k){s=s->next;break;} } for(i=k;i
void delvMGraph(mGraph *G,int k){int i,j;G->n--;for(i=k;i<=g->n;i++)G->vexs[i]=G->vexs[i+1];for(i=0;i
void dellALGraph(ALGraph *G,int m,int n){EdgeNode *s;for(S=G->adjlist[m].firstedge;s->adjvex!=k;s=s->next)s=s->next;for(s=G->adjlist[n].firstedge;s->adjvex!=k;s=s->next)s=s->next;} ②邻接矩阵
void InsertLMGraph(mGraph *G,int m,int n){G->e[m][n]=0;G->e[n][m]=0;} 7.17 下面的伪代码是一个广度优先搜索算法,试以图7.29中的V4为源点执行该算法,请回答下述问题:(1)对图中顶点Vn+1,它需要入队多少次?它被重复访问多少次?(2)若要避免重复访问同一个顶点的错误,应如何修改此算法? Void BFS(ALGraph *G,int k){//以下省略局部变量的说明,visited各分量初值为假
InitQueue(&Q);//置空队列 EnQueue(&Q,k);//k入队 While(!QueueEmpty(&Q)){I=DeQueue(&Q);//vi出队
visited[I]=true //置访问标记// printf(“%c”,G->adjilist[i],vertes);//访问j for(p=G->adjilist[i],firstedge;p;p=p->adjves=j)//依次搜索vi的邻接点vj(不妨设p->adjves=j)if(!Visited[p->adjves])//若vj未被访问 EnQueue(&Q,p->adjves);//vj入队 } //endwhile } //BFS 解：
对图中顶点vn+1,它需入队n次？它被重复访问n-1次。若要避免重复访问同一个顶点的错误，应修改算法如下： Void BFS(ALGraph*G,int K){ /*以下省略局部变量得说明，visited各分量初值为假*/ InitQueue(&Q);/*置空队列*/ EnQueue(&Q,k);/*k队列*/ While(!QueueEmpty(&Q)){I=DeQueue(&Q);/*vi出队*/ visited[I]=true /*置访问标记*/ printf(“%c”,G->adjilist[i],vertes);/*访问vi*/ for(p=G->adjlist[i],firstedge;p;p->adjves=j)/*依次搜索vi的邻接点vj（不妨设p->adjves=j）*/ if(!Vvisit[p->adjves])/*若vj未访问过*/ { EnQueue(&Q,p->adjves);/*/vj入队*/ Visited[p->adjvex]=TRUE;} } /*endwhile*/ } /*BFS*/ 7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(I<>j)之间是否有路径。
解：
/*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex;int vertex;setuct node *list;} vertexNode vertexNode *head[maxvn];bool JUDGE(vertexNode *adjl[maxvn],int n,int j);/*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn];bool visit[maxvm];int top,k;vertexNODE *p;bool yes;for(k=1;k<=n;k++)visit[k]=false;top=1;stack[top]=i;visit[i]=True;yes=false;do{ p=adjl[stack[top]];while(!p=NULL&&visit[p->vertex]p=p->link);if(p==NULL)top=top-1;/*p之后无邻接结点，退栈*/ else {i=p->vertex;/*p指向的顶点未访问*/ if(i==j)yes=true;else { visit[i]=true;top=top+1;stack[top]=i;} }while(top1=0&&!yes);return(yes);} 7．19 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。解：
①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int){ int j;printf(“visit vertex:%c”,G->vexs[i]);visitcd[i]=True;for(j=0;j<=G->n;j++)if(G->edges[i][j]==1&&!visit[j]){ print(“edye:%d%dn”,i,j);DESM(G,j);} } ②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int k){ int i,j;SETNULL(Q);/*置空队Q*/ Printf(‘%/“，G.vexs[k]);Visited[k]=True;/*标志Vk+1已经访问过*/ ENQUEUE(Q,k);/* 已经访问过的顶点如队列*/ While(!EMPTY(Q))/*队列非空时执行*/ {i=DEQUEUE(Q);/*队头元素序号出队列*/ for(j=0;j /*修改DFS函数，每当使visited[i]=true时打印printf（“%D”，i）；可输出各连通分量顶点集。*/ {int i;int m=0;for(i=0;i 要求输出路径上的所有顶点（提示：利用BFS遍历的思想）解： 利用BFS的遍历思想，同时构造一棵树，使每个孩子结点均指向双亲，当搜索到目标结点时，则从目标回溯到根结点即可，具体算法如下 ： typedef struct node { int data;struct node *parent;}Tree;void Path(ALGraph,*G,int i,int j)/*以邻接点存储*/ { int k;/*求vi到vj的最短路径*/ CirQueue Q;/*将DataType改为 int */ EdyeNode P;InitQueue(&Q)/*队列初始化*/ Visit[i]=TRVE;/*源点*/ S=(tree)mallo((sizeof(Tree));新建一个结点 s->data=i /*树根*/ s->patent=NULL;EnQueue(&Q,i);/*入队列*/ While(!Queue Empty(&Q)){ k=DeQueue(&Q);p=G->dajlist[k]->firstdeye;while(P){ if(!Visited[p->adjvex]){ visited[p->adjvex]=TRVE;*S=(Tree*)mallo((sizeof(Tree));/*新结点*/ s->data=p->adkvex;s->parent->data=k;EnQueue(&Q,p->adjvex);} /*end if */ if(p->adjvex==j)bread;/*已搜索到j点*/ p-=p->next;} /*end if */ if(p->adjvex==j)break;/*已搜索到j点，结束搜索*/ } /*end if */ while(s!=NULL)/*此时打印出来的路径为反序*/ { printf(“%d”,G->adjlist[s->data]->vertex)s=s->parent;}（2）求源点到其余各顶点最短路径，则可调用上面算法。 Void PathALL(ALGraph *G.int i){int j, for(j=0;f 算法思想，采用弗洛伊德算法，可表示为 A[K][i,j]=Min(A k-1[i,j],A k-1[i,k]+A k-1[k.j])(1<=i<=n,1<=j<=n)其中k表示第k次迭代运算。A[0][i,j]=A[i,j].#define MAXVEX 100 void floyd(a,c,n)/*c为已知邻接矩阵，a为待求矩阵，n为源点数*/ int a[MAXVEX][MAXVEX] c[MAXVEX][MAXVEX],n;{int i,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=c[i][j];for(i=1;i<=n;i++)a[i][j]=0;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][k]+a[k][j] 算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。 Void dfscycle(ALGrph *G,int V4){int i,j,top=0,V=V4,found=0,w;int Visitde[100],cycle[100];EdgeNode *P;i=1;cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1;P=G[v]->firstedge;While(p!=NULL！top>0)&&!found){ while(p!=NULL&&!found)if(p->adjvex==V4&&i<2)found=1;/*找到回路*/ else if(visited[p->adjvex]==0)p=p->next;/*找到下一个邻接点*/ elst {w=p->adjvex;/*记下路径，继续搜索*/ visited[w]=1;i++;cycle[i]=w;top++;stack[top]=p;p=G[w]->firstedge;} if(!found&&top>0)/*沿原路径退回后，另选路径进行搜索*/ { p=attack[top];top--;p=p->next;i--;} } /*end while*/ if(found){for(j=1;j<=i;j++)printf(“%d,”,cycle[j]);/*打印回路的顶点序列*/ printf(“%d,n”,V);} else printf(“设有通过点V4的回路！n”)} 7．23 写一算法求有向图的所有根（若存在），分析算法的时间复杂度。解： 算法思想：以有向图的每一个结点为源点对圆进行搜索，若能搜索到每个结点。则该结点为根。否则不是。 Void searchroot（ALGraph *G）{ int i;for(i=0;i 使用栈暂存路径 void Ptint(PathP,Distance D){ int i,pre;seqstack *S;s->top=-1 /*置空栈*/ for(i=0;i 解： 使用栈暂存路径 void Print(PathP,Distance D){ int ,pre;seqstack *s;s->top=-1 /*置空栈*/ for(i=0;i ① 用逆邻接表作为G的存储结构。Void NonSuccPirstTopSort(G){int outdehree[maxvertexNum];/*出度向量，Maxvertexnum>=G,n*/ seqstack S,T;/*应将栈中data向量改为int类型*/ int i,j,count=0;Edgenode *P;for(i=0;i Void NoSucePirstTopSort(Mgraph *G){seqstack s,T;int i,j,count=0; /*用i,j代表Vi,Vj*/ Initstack(&S); Initstack(&T); for(i=0;i for(j=0;j if(G->edges[i][j]= =0) push(&S,i); /*出度为0，入栈*/ while(!sruckEmpty(&S)) { i=po(&S); push(&T,i); count+ +; for(j=0;j G->edges[i][j]=0; /*修改邻接矩阵*/ for(i=0;i for(j=0;j if(G->edges[i][j]= =0) push(&S,i); } /*end while */ if(count printf(“n The Graph is not a DAG.n”);else {while(!stackEmpty(&T)) /*输出拓扑序列*/ {i=pop(&T); printf(“%d”,G->adjlist[i]->vertex);} } } 7.26设有向图一个DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精的算法。问什么有向图不是DAG时，该算法不能正常工作？ 解： ① 用邻接矩阵作为存储结构。 Void DPSTopSort(Mgraph*G,i,Setstack T){int j;visited[i]=true;for(j=0;j /*栈所i有的邻接点j*/ if(G->edges[i][j]= =1)if(!visited[j])DPSTopSort(G,j,T);Push(&T,i); /*从I出发的搜索已完成，保存i*/ } ② 用邻接表作为存储结构。 Void DPSTopSort(ALGraph G,i,T){int j;visited[i]=true;for(p=G->adjlist[i]->firstedge;p;p=p->next)if(!visited[p->adjvex])DPSTopSort(G,p->adjvex,T);Push(&T,i);} 由于有向图不是DAG时，从某点出发的搜索将陷入循环状态，所以算法不能正常工作。 7．27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环 存在时，输出构成环的顶点。解： 设有向图用邻接表存储 Void SearckCycle(ALGraph G){int i;EdgeNode *P;for(i=0;i /*对每一个顶点i*/ for(p=G->adjlist[i]->firstedge;p;p=p->next) /*扫描i的出边表*/ if(p->next=G->adjlist[i]->firstedge) /*存在环*/ printf(“%d”,G->adjlist[i]->vertex);} 同步综合练习及参考答案 （一）基础知识题 6.1 加设在树中，结点x是结点y的双亲时，用(x,y)来表示树变。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题： （1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？ （7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次各是多少？（9）树的深度是多少？ （10）以结点c为根的子树的深度是多少？（11）树的度数是多少？ 解： （1）a是根结点。 （2）m,n,j,k,l是叶结点。（3）c是g的双亲。（4）a,c是g的祖先。（5）g的孩子是j,k.。（6）e的子孙是 i,m,n.。 （7）e的兄弟是a,f的兄弟是g。（8）h,b在第五层。（9）树的深度为3。 （10）以C为根的子树的深度为3。（11）树的度数为3。 6．2 一棵度为2的有序属于一棵二叉树有何区别？ 解： 区别：度为2的树有二个分支，没有左右之分；以可二叉树也有两个分支，但有左右之分，且左右不能交换。 6．3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。解： 3个结点树形态： 3个结点的二叉树： 6．4已知一棵树为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该书中有多少片叶子？ 解： 因为 n1+n2+…+nM+n0+=1+n1+2n2+…+mnM =>n0+=1+n2+…+(m-1)nM 6.5 一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：（1）各层的结点数目是多少？ （2）编号为i的结点的双亲结点（若存在）的编号是多少？ （3）编号为i的结点的第j个孩子结点（若存在）的编号是多少？ （4）编号为i的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 解： （1）Ki-1（2） （3）Ki+j-1 （4）(i-1)MOD K<>0 ,i+1 6．6 高度为h的完全二叉树至少有多少个结点？至多有多少个结点？ 解： 至少有：2h-1，至多有：2h-1 6．7 在具有n个结点的k叉树（k≥2）的k叉树链表表示中，有多少个空指针？ 解： （k-1）n+1个空指针 6．8 假设二叉树包含的结点数据为1，3，7，2，12。（1）画出两棵高度最大的二叉树； （2）画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。6．9 试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； （2）中序序列和后序序列相同；（3）前序序列和后序序列相同； （4）前序、中序、后序序列均相同。解： （1）空二叉树或任一结点均无左子树的非空二叉树（2）空二叉树或任一结点均无左子树的非空二叉树（3）空二叉树或仅有一个结点的二叉树（4）同（3） 6．10 试采用顺序存储方法和链接存储方法分别画出6.30所示各二叉树的存储结构。 解：①顺序存储： (a)1 2 φφ 3 φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ 5(b)1 φ 2 φ φ 3 φ φ φ φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ φ φ 5(c)1 φ 2 φ φ 3 4 φ φ φ φ 5 6 φ φ φ φ φ φ φ φ φ φ φ 7 8(d)1 2 3 4 φ 5 6 φ 7 φ φ φ φ 8 9 ②连接存储： 6．11 分别写出图6.30所示各二叉树的前序、中序和后序序列。 解： 6．12 若二叉树中个结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列的中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。 （1）已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。 （2）已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。 （3）已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树。解： 6．13 对二叉树中结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。解： 6．14 试画出图6.30所示各二叉树的前序、中序和后序线索树及相应的线索链表。解： （以c为例） ① 前序：1 2 3 5 7 8 6 4 ② 前序：1 7 5 8 3 6 2 4 6．15 在何种线索树中，线索对所求指定结点在相应次序下的前趋和后继并无帮助？ 解： 在前序线索树中找某一点的前序前趋以及在后序线索树中寻找某一点的后继，线索并无多大帮助。 6．16 对图6.31所示的森林： （1）求各树的前序序列和后序序列：（2）求森林的前序序列和后序序列：（3）将此森林转换为相应的二叉树： （4）给出（a）所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？ 解： (1) a b c 前序 ABCDEF GHIJK LMPQRNO 后序 BDEFCA IJKHG QRPMNOL(2)前序： ABCDEFGHIGKLMPQRNO 后序： BDEFCAIJKHGQRPMNOL(3)二叉树(4)1 ① 孩子链表表示发： ② 双亲链表表示发： 结点 0 1 2 3 4 5 6 data A B C D E F parent -1 0 1 1 3 3 3 ③ 双亲孩子链表： ④ 孩子兄弟链表表示： ⑤ 易于求祖先：双亲链表面 双亲孩子 ⑥ 易于求后代：孩子链表 双亲孩子 6．17 画出图6.32所示的各二叉树所应的森林 6．18 高度为h的严格二叉树至少有多少个结点？至多有多少个结点？ 解： 最多有2n-1 最少有 2n-1 6．19 在什么样的情况下，等长编码是最优的前缀码？ 解： 当字符集中的各字符使用频率均匀时。6．20 下属编码哪一组不是前缀码？ {00，01，10，11}，{0，1，00，11}，{0，10，110，111} 解： 因为前缀码中不可能存在一个元素是另一个的前面部分。 所以第二组不是。 6．20 假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}（1）为这8个字母设计哈夫曼编码。 （2）若用三位二进制数（0~7）对这个8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？ 解： ① ②哈夫曼编码码长： 4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71 等长码长： 3 905平均缩了10% （二）算法设计题 6.22 二叉树的遍历算法可写为通用形式。例如，通用的中序遍历为： void Inorder(BinTree T,void(*Visit)(Datatype x)){ if(T){Inorder(T->lchild,Visit);/*遍历左子树*/ Visit(T->data);/*通过函数指针调用它所指的函数来访问结点*/ Inorder(T->rchild,Visit);/*遍历右子树*/ } } 其中Visit是一个函数指针，它指向形如void f（DdataType x）的函数。因此我们可以将访问结点的操作写在函数f中，通过调用语句Inorder（root，f）将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。 解： #include“stdio.h” #define Null 0 typedef char DataType;typedef struct node { DataType data;Struct node lchild,rchild;}BinTree;BinTree *root;BinTree *Q[100];BinTree CreateBinTree()/*建立二叉树*/ { char ch;int front,rear;BinTree root,s;Root=Null;front=1;rear=0;ch=getchar();while(ch!=’#’){ s=Null;if(ch!=’@’){ s=(BinTree*)malloc(sizeof(BinTree));s->data=ch;s->lchild=Null;s->rchild=Null;} rear ++;Q[rear]=s;if(rear==1)root=s;else { if(s&&Q[front])if(rear%2==0)Q[front]->lchild=s;else Q[front]->rchild=s;if(rear%2==1)front++;} ch=getchar();} return root;} main(){ root=CreateBinTree();Inorder(root);} ① 中序遍历法之一 Inorder(BinTree *t){ if(t){ Inorder(t->lchild);Visit(t->data);Inorder(t->rchild);} } Vist(int i){ printf(“%c”,i);} ② 中序遍历法之二 Inorder(BinTree *t){ if(t){ Inorder(t->lchild);printf(“%c”,t->data);Inorder(t->rchild);} } 6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。解： ① 计算结点总数 int CountNode(BinTree *root){ int num1,num2;if(root==Null)return(0);else if(root->lchild==Null&&rooot->rchild==Null)return(1);else { num1=CountNode(root->lchild);num2=CountNode(root->rchild);return(num1+num2+1);} } ② 计算叶子总数 int CountLeafs(BinTree *root){ int num1,num2;if(root==Null)return(0);else if(root->lchild==Null&&root->rchild==Null)return(1);else { num1=CountLeafs(root->lchild);num2=CountLeafs(root->rchild);return(num1+num2);} } 6.24 以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。解： ① 求树的高度 思想：对非空二叉树，其深度等于左子树的最大深度加1。 Int Depth(BinTree *T){ int dep1,dep2;if(T==Null)return(0);else { dep1=Depth(T->lchild);dep2=Depth(T->rchild);if(dep1>dep2)return(dep1+1);else return(dep2+1);} ② 求树的宽度 思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。int Width(BinTree *T){ int front=-1,rear=-1;/* 队列初始化*／ int flag=0,count=0,p;/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null){ rear++;q[rear]=T;flag=1;p=rear;} while(front lchild!=Null){ rear++;q[rear]=T->lchild;count++;} if(T->rchild!=Null){ rear++;q[rear]=T->rchild;count++;} if(front==p)/* 当前层已遍历完毕*/ { if(flag /* p指向下一层最右边的结点*/ } } /* endwhile*/ return(flag);} 6.25 以二叉链表为存储结构，写一算法交换各结点的左右子树。 解： 思想：借助栈来进行对换。 Swap(BinTree*T){ BinTree *stack[100], *temp;int top=-1;root=T;if(T!=Null)} top++;stack[top]=T;while(top>-1){ T=stack[top];top--;if(T->child!=Null||T->rchild!=Null){ /*交换结点的左右指针*/ temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;} if(T->lchild!=Null){ top++;stack[top]=T->lchild;} if(T->rchild!=Null){ top++;stack[top]=T->rchild;} } } /*endwhile*/ } /*endif*/ main(){ int I,j,k,l;printf(“n”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(root);l=Width(root);printf(“nThe Node ’s Number:%d”,i);printf(“nThe Leafs’s Number:%d”,j);printf(“nThe Depth is:%d”,k);printf(“nThe width is:%d”,l);Swap(root);Printf(“nThe swapTree is:”);Inorder(root);} 6．26 以二叉表为存储结构，写一个拷贝二叉表的算法 哦（BinTree root,BinTree *newroot）,其中新树的结点是动态申请的，为什么newroot要说明为BinTree形指针的指针？ 解： CopyTree(BinTree root,BinTree *(newroot))} if(root!=Null){ *newroot=(BinTree *)malloc(sizeof(BinTree));(*newroot)->data=root->data;CopyTree(root->lchild,&(*newroot)->lchild);CopyTree(root->rchild,&(*newroot)->rchild);Inorder(*newroot);} else return(Null);} main(){ BinTree *newroot;int I,j,k,l;printf(“n”); root=CreateBinTree();Inorder(root);Printf(“n”);/*Swap(root);*/ &(*newroot)=Null;CopyTree(root,&*newroot);} 6．27 以二叉树表为存储结构，分别写处在二叉树中查找值为x的结点在树中层数的算法。解： int h=-1,lh=1,count=0;charx=’c’;/*赋初值*/ Level(BinTree T,int h,int lh)/*求X结点在树只的层树*/ { if(T==Null)h=0;else if(T->data==x){ h=lh;count=h;} else { h++;Level(T->lchild,h,lh);If(h==-1)Level(T->rchild,h,lh);} } main(){ BinTree *(*newroot);Printf(“n”); Root=CreateBinTree();Inorder(root);Printf(“n”);Level(root,h,lh);Printf(“%d”,count);} 6.28一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。解： 思想：采用栈，先让跟结点如栈，然后退栈，如有左右孩子，则先让右孩子如栈，然后左孩子如栈，如此反复实现前序遍历。 typedef struct { int data[100];int top;}seqstack;seqstack *s;Perorder(char a[],int n){ int i=1,count=1;s->top=-1;if(n==0)return(0);else { if(I<=n){ s->top++;s->data[s->top]=a[I];} while(count void TransLevel(BinTree *T){ int front=0,rear=0;int p;if(T!=Null){ printf(“%c”,T->data);q[rear]=T;rear++;} while(front root=CreateBinTree();Inorder(root);Printf(“n”);TransLevel(root);} 6．30 以二叉树表为存储结构，写一算法用括号形式（keyLT,RT）打印二叉树，其中key是根结点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一给结点x的树打印形式是x，而不应是（x，）d的形式。解： viod Print(BinTree T)/*哟感括号形式打印二叉树*/ { if(T!=Null){ if(T->lchild==Null&&T->rchild==Null)/*只有根结点*/ printf(“%c”,T->data);else /*T->lchild!=Null||T->rchild!=Null*/ { printf(“(”); printf(“%c”,T->data);if(T->lchild->lchild==Null&&T->lchild->rchild==Null)printf(“)”);Print(T->lchild);if(T->rchild!=Nulll)printf(“,”); printf(“)”); printf(“)”);} } } main(){ printf(“n”); root=CreateBinTree();Inorder(root);printf(“n”);Print(root);} 6.31以线索链表为存储结构，分别写出在前序线索树中查找给定结点*p的后继，以及在后序线索树中查找*p的后序前趋的算法。解： ① 找结点p的前序后继 BinTheNode * PreorderSuccessor(BinThrNode *p){ BinThrNode *q;if(p->rtag==Thread)q=p->rchild;/*右子树为空*/ else { if(p->ltag==list)q=p->lchild； /*左子树非空*/ if(p->ltag==Thread)q=p->rchild;/*左子树为空*/ } return(q);} ②找结点p的后序继 BinTheNode * PostorderSuccssor(BinThrNode *p){ BinThrNode *q;if(p->ltag==Thread)q=p->lchild;/*左子树为空*/ else {if(p->rtag==list)q=p->rchild;/*右子树非空*/ if(p->ltag==Thread)q=p->lchild;/*右子树为空*/ } return(q);} /*说明：listThread为特殊标志，其值分别为0与1.*/ 6．32 完成6.6.1 节算法CreateHuffmanTree中调用的三个函数：InputWeight,SelecMin和InitHuffmanTree.解： ① 初始化 InitHuffmanTree(HuffmanTree T){ int i;for(i=0;i SelecMin(HuffmanTree T,i-1,&p1,&p2)int i,p1,p2;{ int j,small1,small2;small1=small2=max;/*设max为整型最大值*/ for(j=0;j ① 编码算法 设哈夫曼树已求出。 HuffmanCode(code,tree)Codetype code[];Huffmantype tree[] /*以求出*/ { int I,j,c,p;codetype cd;/*缓冲区变量*/ for(i=0;i c=p;p=tree[p-1]->parent;} code[i]=cd;} } 注：结构体 typedef struct { char bit[n];/*位串*/ int start;/*编码在位串的起始位置*/ char ch;/*字库*/ }codetype;codetype code[n];② 译码算法 Decode(code,tree)Codetype code[];Huffmantype tree[];{ int I,j,c,p,b;int endfily=-1;/*电文结束标志*/ i=m;/*从根结点开始往下搜索*/ scanf(“d”，&b);/*读入一个二进制代码*/ while(b!=endfily){ if(b==0)i=tyee[i]->lchild-1;/*走向左孩子*/ else i=tyee[i]->rchild-1;/*走向右孩子*/ if(tyee[i].child==0)/*tyee[i]为叶结点*/ { outchar(code[i]->ch);/*译码，即输出叶结点对应的字符*/ i=m;/*回归根结点*/ P=tyee[p-1]->parent;} scanf(“%d”,&b);/*读入下一个二进制代码*/ } if(tyee[i].lchild!=0)/*电文读完但未到叶结点*/ printf(“n ERRoRn”);/*输出电文有错信息*/ } 第一次实验 线性表 （一）实验目的和要求： 1.熟悉VC集成环境 2.会定义线性表的顺序结构和链式结构 3.熟悉对线性表的基本操作，如插入、删除等 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现线性表的建立、插入、删除等功能。 写出线性表、顺序表、链表的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的顺序表算法有： 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有： 1.建立链表 2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第二次实验 栈和队列 （一）实验目的和要求： 1.熟练掌握栈和队列的结构，以及这种数据结构的特点 2.会定义顺序栈、循环队列，能实现栈、队列的基本操作 3.会利用栈解决典型问题，如数制转换等 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现栈（或者队列）的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等 写出栈的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.初始化栈 2.入栈 3.出栈 4.判断栈是否为空 5.十进制转换为八进制 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第三次实验 二叉树 （一）实验目的和要求： 1.熟练掌握二叉树的结构，以及这种数据结构的特点 2.会定义二叉树的链式存储结构 3.能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现二叉树的各种基本操作，如二叉树的建立（头插法或者尾插法），遍历等 写出二叉树的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第四次实验 查找 （一）实验目的和要求： 1.熟练掌握查找算法的基本思想，以及算法的适用条件 2.会定义静态查找表的顺序结构，能实现顺序查找、二分查找 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现顺序查找、二分查找。 写出静态查找表的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.建立静态查找表 2.顺序查找 3.建立有序的静态查找表 4.二分查找 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 实验一 预备实验 一、实验项目的目的和要求： 1． 复习C语言指针的用法 2． 复习C语言结构体的用法 3． 理解时间复杂度分析的基本方法 二、实验内容： 1．用指针方式编写程序：从键盘输入N个整型数据，并存入数组，要求将N个数中最大的数与第一个数交换；将其中最小的数最后一个数交换。 基本思想：设两个指针分别指向最大数组元素和最小数组元素。再设一个移动指针从数组的第一个元素开始，依次与最大数组元素指针、最小数组元素指针的内容进行比较，作出相应的变化，一直到移动指针移到最后一个元素。 2．有N 个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求从键盘依次输入N 个学生的学号、姓名、三门课的成绩，自动计算三门课的平均分数，并将N 个学生的数据输出。 基本思想：对每一名学生循环，再对三门课程循环求平均成绩 三、实验中存在的问题： 实验二 线性表的基本操作 一、实验项目的和要求： 1． 掌握线性表的特点 2． 掌握线性表的顺序存储结构和链式存储结构的基本运算。3． 尽可能考虑算法的健壮性 4． 实验报告中要写出测试数据、错误分析以及收获。 二、实验内容一：线性表两种存储结构的基本运算 1.用结构体类型描述线性表的两种存储结构 2.完成课堂上所讲的两种存储结构的基本运算 3.要求用二级菜单实现 ***************************** * 1-------顺序表 * * 2-------链 表 * * 0-------退 出 * ***************************** 请输入的选择：(0-2)： 线性表的链式存储 ## # 1----前插建立链表 # # 2----后插建立链表 # # 3----访问第i个元素 # # 4----插入 # # 5----删除 # # 6----求线性表的表长 # # 0----退出 # ## 请输入选择(0-6)： 分析：1．使用循环建立菜单 ２．使用switch语句进行选择，执行相应的子函数（每一个运算编写一个子函数） 实验内容二：超市密码存储箱系统的设计与实现 1.顾客使用箱子的流程为“投一元硬币”--------“找到一个空箱子，同时产生密码”（系统完成）--------“打印密码，打开箱子”（系统完成）--------“取密码纸存包，并关闭箱子，入超市购物”--------“购物结束”--------“输入密码”--------“找到对应箱子并打开”（系统完成）--------“取包”。2.现要求设计程序模拟以上系统完成的功能 ①界面：在我们的模拟系统中，箱子在屏幕上被画出来，并编号，空箱为蓝色，被使用时变成红色，再变为空后则恢复蓝色； ②通过按“1”键模拟顾客投币； ③当空箱子被顾客申请得到的同时，系统自动生成6位数密码，此密码不能与正在被使用的任何一个箱子的密码相同。3.设计分析 在设计时，可利用链表来组织所有的箱子，所有的箱子以结点的形式表示，结点中存放箱号、密码（满箱有，空箱无）以及指向下一个结点的指针。空箱结点放在一个链表1中，满箱结点放在另一个链表2中。 若有顾客投币（这里按下“1”键模拟），查看链表1是否为空，若为空，则显示“箱满，请稍侯！”，若非空，则取出一个结点，随机产生一个六位数密码，并将些密码和链表2中所有结点的密码相比较，若有重复，则再随机产生一个新密码，直到无重复；将密码信息写入此结点，并将其插入链表2；将此箱的颜色改为红色。4.密码箱的存储结构类型定义 typedef struct node { int num;/*箱子的号码*/ int password;/*箱子的密码（满箱有，空箱无）*/ struct node *next;/*指向下个结点的指针*/ }Node,*LinkList； 分析：１．初始化，建立一个代表空箱子链表，建立一个只有头结点的实箱子链表． ２．如果想要存包时，就在空箱子链表中进行查找，如果为空，代表箱子已满，否则从空箱子链表中删除一个结点，并给它赋值，将该结点插入到实箱子链表中． ３．如果想要取包时，就输入密码，在实箱子链表中进行匹配，如果成功，就从实箱子链表中删除相应的结点，插入到空箱子链表中． ４．另外还需要的函数有：随意产生密码函数，匹配密码函数 实验内容三：员工通讯录管理系统 1.为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的办公室电话号码、手机号码及电子邮箱。 2.现要求设计程序模拟以上系统完成的功能 其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的输出。3.设计分析 在本设计中，整个通讯录可以采用顺序表或链表方式存储。采用前者，可以提高查询速度；采用后者，可以提高插入与删除记录的效率。 4.员工通讯信息的结构类型定义和通讯录链表的结点类型 typedef struct { char num[5];/*员工编号*/ char name[8];/*员工姓名*/ char phone[9];/*办公室电话号码*/ char call[12];/*手机号码*/ }DataType；/*员工通讯信息的结构类型*/ typedef struct node { DataType data;/*结点的数据域*/ struct node *next;/*结点的指针域*/ }ListNode,*LinkList；/*通讯录链表的结构类型*/ 分析：１．建立一个可循环的菜单 ２．使用switch语句，调用子函数实现以下功能 针对每一位员工作为一个结点建立链表． 在该链表上进行查找、插入、删除、修改及输入／出。实验内容四：运动会记分子系统或学生成绩管理子系统 1.参加运动会的N个学校编号为1~N。比赛分成M个男子项目和W个女子项目，每个项目取前3名，得分分别为5，3，2。写一个程序产生各种成绩单和得分报表。2.完成功能包括如下： ①产生一总成绩表，包括：学校编号名、男子团体总分、女子团体总分、团体总分 存储结构要求用线性表的顺序存储。 ②实验报告中要写出测试数据、错误分析以及收获。 ③若选择学生成绩管理子系统，可仿照运动会记分子系统完成相关的插入、删除、查找及各种统计工作。 分析：１．分析顺序表中每个元素的结构（数组元素是一个结构体） ２．建立顺序表 ３．在顺序表进行插入、删除、查找 ４．进行统计 实验中存在的问题： 实验三 栈和队列的应用 一、实验目的和要求： 1． 掌握栈和队列的概念和特点 2． 掌握栈和队列在顺序和链式存储结构下的插入、删除算法 3． 认真分析项目实例中的内容，将相关程序在计算机上运行实现 二、实验内容一：表达式求值问题 1．求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”、“—”、“*”、“/”）的算术表达式，计算其结果。2．设计分析 首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）3．结点结构类型描述如下 typedef struct { char *base,*top;int stacksize;}sqstack;分析：１．判断输入的字符是否为数值 2.比较判断运算符的优先级 3.何时结束循环，不再运算 实验内容二：迷宫求解问题 1.迷宫是一个m行n列的矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m,n），即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则 沿原路退回，换一个方向再继续探索，直到出口为止。2.迷宫的功能 要求随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圏障碍，设置东南西北四个方向，采用链栈进行操作。最后迷宫如不是通路给出“此迷宫元解”，如是通路要求输出所走过的路径。3．结点结构类型描述如下 typedef struct node { int row;int col; struct node *next;};分析：１．建立迷宫，使用二维数组，第一行／列，最后一行／列均初始化为０代表墙不通，这样使其内部的元素均有四个方向进行统一判断，其余元素进行随机产生０代表不通，１代表通． ２．确定入口，出口的坐标． ３．判断该元素是否可通（元素值等于１，一方面代表通，另一方面未走过）． ４．标记每一个走过的元素，将其元素值加１． ５．元素的四个方向用０－３表示，下一个方向的坐标可以从当前坐标及方向就可以确定． 三、实验中存在的问题： 实验四 二叉树两种存储结构的应用 一、实验目的和要求： 1． 掌握二叉树的遍历思想及二叉树的存储实现。2． 掌握二叉树的基本操作：建立二叉树、二叉树的遍历 3． 选择一种形式完成二叉树的显示 4． 掌握二叉树的常见算法的程序实现 5． 实验报告中要写出测试数据、错误分析以及收获 二、实验内容一：二叉树的建立及相关算法的实现 1．完成的功能包括如下几点： ①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。 分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在结点则输入@ ②显示二叉树 ③求二叉树的高度及二叉树的叶子个数等等 ④在主函数中设计一个简单的菜单，分别调试上述算法 实验内容二：哈夫曼编码/译码系统 1．要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。2．设计分析 在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信息的翻译。要求设置发送者和接收者两个功能。 发送者的功能包括： ①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出现的次数（频率）；③根据字符的种类数和各字符出现的次数建立哈夫曼树；④利用以上哈夫曼树求出各字符的哈夫曼编码；⑤将字符信息转换成对应的编码信息进行传送。接收者的功能包括： ①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信息还原成发送前的字符信息。3．结点的类型定义 ①哈夫曼树的存储结构类型定义为： typedef struct { char data;/*编码对应的字符*/ int weight;/*结点的权值*/ int lchild,rchild,parent;/*左右孩子及双亲的下标*/ }HTNode;②哈夫曼编码的存储结构类型定义为： typedef struct { char bits[N];/*存放哈夫曼编码的字符数组*/ int start;/*记录编码的起始位置，因为每种字符的编码长度不同*/ }HCode; 三、实验中存在的问题： 实验五 图子系统一、实验目的和要求： １．掌握图的存储思想及其存储实现 ２．掌握图的深度、广度优先遍历算法思想及其程序实现 ３．掌握图的常见应用算法的思想及其程序实现 二、实验内容一：图的遍历问题 1．键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。建立一个有向图或无向图（自定）的邻接表并输出该邻接表 2．在图的邻接表的基础上计算各顶点的度，并输出 3．以有向图的邻接表为基础实现输出它的拓扑排序序列 4．采用邻接表存储实现无向图的深度优先遍历 5．采用邻接表存储实现无向图的广度优先遍历 6．采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 7．在主函数中设计一个简单的菜单，分别调试上述算法 实验内容二：所有顶点对的最短路径 1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这 4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2．设计分析 用有向加权图表示的交通图中，有向边 typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct { vextype vex[maxsize];edgetype arc[maxsize][maxsize];int vexnum,arcnum;}Mgraph; 三、实验中存在的问题： 实验六 数据结构综合性实验 一、实验目的和要求： 掌握小型系统开发方法，提高学生综合开发能力。根据实际问题，设计方案，综合运用课程知识，完成《学生成绩管理系统》或《数据结构算法演示系统》的设计、编程与调试工作。 二、实验内容一： 分析、调研数据结构课程所学的算法（功能模块）或学生成绩管理的相关功能模块，采用结构化设计思想、模块分解的规则构成一个易使用的小型管理系统。具体要求见《数据结构实验》课程设计 实验内容二：手机短信中电话号码和手机号码的识别与提取 1.在使用手机收发短信时，收到的短信内容中常会包含对方发来的电话号码或手机号码，为了方便用户能直接提取其中的号码并存入到其手机的通讯录中，现要求开发手机系统软件中的一个子功能，实现从手机短信内容中识别和提取电话号码（7位或8位）和手机号码(11位)，并将其存入通讯录中。2.设计分析 要从手机短信的内容中识别电话号码或手机号码，必须从短信的第一个字符开始查找，找到第一个数值型字符（‘0’～‘9’），然后依次判断其后的字符，若其后有连续的6个或7个数值型字符，则将其识别成电话号码并提取，若其后有连续的10个数值型字符，则将其识别成手机号码并提取。继续向后搜索直到整个短信查找完毕。3.存储结构类型定义 ①短信的存储结构类型定义 typedef struct { char word[200];/*短信内容*/ int length;/*短信长度*/ }Message;②通讯录中记录的存储结构类型的定义 typedef struct { char name[8];/*姓名*/ char phone[11];/*电话号码或手机号码*/ }Note;实验内容三：药店的药品销售统计系统 1.设计一系统，实现医药公司定期对各药品的销售记录进行统计，并按药品编号、单价、销售量或销售额做出排序。2.设计分析 在设计中，首先从数据文件读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药品名称、单价、销售量、销售额。其中药品编号共4位，采用字母和数字混合编号，如：B125，前一位为大写字母，后三位为数字。3.存储结构类型定义 ①药品信息的存储结构类型定义 typedef struct node { char num[4];/*药品编号*/ char name[10];/*药品名称*/ float price;/*单价*/ int count;/*销售量*/ float sale;/*销售额*/ }DataType;②存储药品信息的顺序表的定义 typedef struct { DataType r[maxsize];int length;}sequenList;实验内容四：电视大赛观众投票及排名系统 1.在很多电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排列，从而自动产生冠军、亚军和季军。现要求编写一程序模拟实现上述系统的功能。2.设计分析 在本系统中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依次存入顺序表单元中，观众通过按键进行投票，按“1”表示为1号选手投票，按“2”表示为2号选手投票，依次类推。以按“0”作为投票结束标志。投票结束后进行排序。3.存储结构类型定义 ①选手信息的存储结构类型定义 typedef struct node { char name[8];/*选手姓名*/ int num;/*选手编号*/ int score;/*选手得分*/ int tax;/*选手名次*/ }Node;②开辟空间用于构造存放选手信息的顺序表R：R=(Node *)malloc(n*sizeof(Node));其中n 为参赛选手的人数，在此采用动态空间分配，而不是在开始时直接开辟静态数组，这样是为了避免空间的不足造成浪费。 在投票时，按“1”为1号选手投票的实现： Scanf(“%c”,&k);/*观众按键*/ R［K-48］.score= R［K-48］.score+1;若观众输入的是“1”，则“1”-48即为ASCII-48=1，因此可以实现对1号选手的票数加1，即R［1］=R［1］+1。其他选手类似。 课程教案 课程名称： 数据结构 授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章 绪论 教学内容： 1）什么是数据结构 2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3）数据结构的抽象层次 4）算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章 线性表 教学内容： 1）线性表的定义和特点 2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 第三章 栈和队列 教学内容： 1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示 2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 3）队列的应用举例 教学要求： 熟练掌握：栈的定义及实现 熟练掌握：队列的定义及实现 掌握：能运用栈和队列解决简单实际问题 第四章 串 教学:内容： 1)字符串的抽象数据类型 2)字符串操作的实现 3)字符串的模式匹配 教学要求： 熟练掌握：字符串的定义方式 熟练掌握：字符串的各种操作的实现 了解：字符串的模式匹配算法 第五章 数组和广义表 教学:内容： 1)数组的定义和初始化 2)作为抽象数据类型的数组的顺序存储方式 教学要求： 了解：作为抽象数据类型的数组的定义 熟练掌握：顺序表的数组定义方式及实现 第六章 树和二叉树 教学内容： 1)树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念 2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 3)二叉树的表示：数组表示；链表存储表示 4)二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法 5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化 6)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历 7)二叉树的计数 8)霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码 教学要求： 了解：树和森林的概念 掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法 掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握：树和森林的实现及遍历方法 掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握：霍夫曼树的实现方法及霍夫曼编码的概念 第七章 图 教学内容： 1）图的基本概念：图的基本概念；图的抽象数据类型 2）图的存储表示：邻接矩阵；邻接表；邻接多重表 3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量 4）最小生成树：克鲁斯卡尔算法；普里姆算法 教学要求： 掌握：图的基本概念和图的存储表示 熟练掌握：图的两种遍历方法与求解连通性问题的方法 掌握：构造最小生成树的Prim和Kruskal方法 第九章 查找 教学内容： 1)静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找 2)二叉排序树：二叉排序树上的搜索、插入和删除 教学要求： 熟练掌握：静态搜索表的顺序搜索和折半搜索方法 熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 第十章 内部排序 教学内容： 1)概述 2)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序 3)选择排序：直接选择排序；堆排序 教学要求： 掌握：排序的基本概念和性能分析方法 掌握：插入排序、选择排序、等内排序的方法及性能分析方法 单元名称：第 一 讲：绪论 一、教学目标 1.了解《数据结构》课程的体系结构 2.掌握本章介绍的各种基本概念和术语 3.了解数据结构的二元组表示 4.掌握逻辑结构与物理结构之间的映像关系。 二、重点与难点 重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。难点：逻辑结构与物理结构之间的映像关系。 三、教学内容与教学过程 介绍本学期课程的内容及安排 本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。 成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占 30%，平时成绩为：作业成绩+出勤率+上机成绩。 讲授新课 1.1 什么是数据结构 讲解：（数据结构课程的研究背景） 从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。 讲解：（数据结构课程的研究对象） 例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题 1-3多叉路口交通灯的管理问题 总结： 从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而 是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 介绍数据结构课程的发展以及与其他课程之间的关系。 1.2基本概念和术语 基本概念：数据、数据元素、数据项、数据对象、数据结构、结构 （1）常见基本结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构 数据结构的形式定义： 数据结构一般用一个二元组来表示： Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集 DS表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中： K{Ki|0in,n0}是数据元素的有限集合，n为DS中数据元素的个数。 R{Rj|0jm,m0}的取值为1。 是K上关系的有限集合，m为K上关系的个数，通常情况下mK上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶 数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解： 例 数据结构line={K，R}，其中K={01，02，03，04，05，06，07，08，09，10}，R={r}，r={<01，02>，<02，03>，<03，04>,<04，05>，<05，06>，<06，07>，<07，08>，<08，09>，<09，10>}。 例数据结构tree={K，R}，其中K={01，02，03，04，05，06，07，08，09，10}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<04，07>，<04，08>，<06，09>，<06，10>}。 例 数据结构graph={K，R}，其中K={01，02，03，04，05}，R={r}，r={<01，02>，<02，01>，<01，04>，<04，01>，<01，03>，<03，01>，<02，04>，<04，02>，<03，05>，<05，03>}。 介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式(2)逻辑结构 上述数据结构的定义是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。 (3)物理结构 数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。 （4）数据结构一般包括三方面内容： 数据的逻辑结构、数据的存储结构、数据的运算 （举例讲解）小结： 总结本讲的主要内容 四、作业布置 见习题集 单元名称：第 二 讲：线性表的类型定义，线性表的顺序存储 一、教学目标 掌握线性表的顺序表示和实现 二、重点与难点 线性表的顺序表示和实现。 三、教学过程的具体安排 讲授新课 2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表（图2.1）等。 例如线性表（a1,…,ai-1,ai,ai+1,…,an），称ai-1是ai的直接前驱元素，ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。 线性表的长度：线性表中元素的个数（n≥0），n=0为空表。线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。 抽象数据类型线性表的定义： 讲解定义中的数据对象，数据关系以及基本操作（教材P19），重点讲解常用的基本操作含义。 通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。2.2 线性表的顺序表示和实现 （1）线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。 （2）顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(a i+1)和第i个数据元素的存储位置LOC(a i)之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。 （3）顺序表及其特点, 顺序储存结构是一种随机存取的存储结构。（4）线性表的动态分配顺序存储结构。 #define LIST_INIT_SIZE #define LISTINCREMENT 10 Typedef struct { ElemType *elem;int length;int listsize;}SqList;(1)基于顺序存储结构的基本操作的实现 主要介绍下面的基本操作并且分析时间复杂度。 InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e); ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重点讲解： 顺序存储结构上实现线性表的插入操作 12i1ii1n，为了保证线性表的有序性，当在位设线性表置i1in1之前插入一个新的数据元素x时，需要将第i个到第n个数据元Aa,a,,a,a,a,,a素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表的长度。 Status ListInsert_Sq(SqList &L, int i, ElemType e){ // 在顺序线性表L的第i个元素之前插入新的元素e，// i的合法值为1≤i≤Listlength_Sq(L)+1 if(i < 1 || i > L.length+1)return ERROR;// 插入位置不合法 if(L.length >= L.listsize){// 当前存储空间已满，增加分配 newbase =(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);// 存储分配失败 L.elem = newbase;// 新基址 L.listsize += LISTINCREMENT;// 增加存储容量 } q = &(L.elem[i-1]);// q指示插入位置 for(p = &(L.elem[L.length-1]);p >= q;--p)*(p+1)= *p;// 插入位置及之后的元素右移 *q = e;// 插入e ++L.length;// 表长增1 return OK;} // ListInsert_Sq 平均时间复杂度分析：f(n)(012n)/(n1)n/2O(n) 顺序存储结构上实现线性表的删除操作 12i1ii1n，设线性表为了保证线性表的有序性,当删除第i(1in)个位置上的元素后，需要将第i+1个到第n个数据元素均向前移动Aa,a,,a,a,a,,a一个位置并改变线性表的长度。 Status ListDelete_Sq(SqList &L, int i, ElemType &e){ // 在顺序线性表L中删除第i个元素，并用e返回其值。// i的合法值为1≤i≤ListLength_Sq(L) if((i < 1)||(i > L.length))return ERROR;// 删除位置不合法 p = &(L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1;// 表尾元素的位置 for(++p;p <= q;++p)*(p-1)= *p;// 被删除元素之后的元素左移--L.length;// 表长减1 return OK;} // ListDelete_Sq 平均时间复杂度分析：f(n)(012(n1))/nn1/2O(n)总结： 顺序存储结构的优缺点 顺序结构的优点是结构简单，对数据元素既可以实现顺序访问，又可以实现随机访问；缺点是插入和删除操作需要移动大量的数据元素。 小结：本讲主要介绍了线性表的逻辑结构定义和基本运算，线性表的插入和删除操作在顺序存储结构上的实现。 小结：总结本讲的主要内容 四、作业布置 见习题集 实验作业见实验指导 单元名称：第 三 讲：线性表链式存储 一、教学目标 掌握单链表的表示和实现 二、重点与难点 单链表的存储结构和基本操作实现。 三、教学内容与教学过程 复习线性表的顺序存储结构的特点引入另一种表示方法链式存储结构。 讲授新课 2.3.1线性链表（1）线性链表 线性链表：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。 线性链表的存储结构： 以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象)，其中指针域只有一个。 举例讲解：教材图2.5 线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。线性表为空时，头结点的指针域为空。举例如图2.7.线性表的单链表存储结构的C语言描述： typedef struc LNode{ // 定义单链表结点 ElemType data; struct LNode *next； // 指向后继的指针域 }LNode, *LinkList； 单链表操作的实现： GetElem(L, i, e) // 取第i个数据元素 ListInsert(&L, i, e) // 插入数据元素 ListDele CreateList(&L, n)// 生成含 n 个数据元素的链表 CreateList(&L, n)// 生成含 n 个数据元素的链表 MergeList(&La,&Lb,&Lc)//合并两个有序链表 (1)建立单链表（要求从头部插入）void CreateList_L(LinkList &L, int n){ // 逆位序输入n个元素的值，建立带表头结点的单链线性表L。L =(LinkList)malloc(sizeof(LNode));L->next = NULL;// 先建立一个带头结点的单链表 for(i = n;i > 0;--i){ p =(LinkList)malloc(sizeof(LNode));// 生成新结点 scanf(&p->data);// 输入元素值 p->next = L->next;L->next = p;// 插入到表头 } } // CreateList_L 注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。(2)建立单链表（要求从尾部插入）void CreateList_L(LinkList &L, int n){ //正位序输入n个元素的值，建立带表头结点的单链线性表L。L =(LinkList)malloc(sizeof(LNode));r = L;L->next = NULL;// 先建立一个带头结点的单链表 for(i = n;i > 0;--i){ p =(LinkList)malloc(sizeof(LNode));// 生成新结点 scanf(&p->data);// 输入元素值 p->next=r->next;r->next=p;r = p;// 插入到表尾 } } // CreateList_L(3)在带头结点的单链表中插入结点 分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的情况。 Status ListInsert_L(LinkList L, int i, ElemType e){ // 在带头结头的单链表L中第i位置之前插入元素e p = L;j = 0;while(p && j < i-1){ p = p->next;++j;} // 寻找第i-1个结点 if(!p || j > i-1)return ERROR;// i小于1或者大于表长 s =(LinkList)malloc(sizeof(LNode));// 生成新结点 s->data = e;s->next = p->next;// 插入L中 p->next = s;return OK;} // LinstInsert_L(4)在带头结点的单链表中删除结点 Status ListDelete_L(LinkList L, int i, ElemType &e){ p = L;j = 0;while(p->next && j < i-1){ p = p->next;++j;} //寻找第i个结点并令p指向其前趋 if(!(p->next)|| j > i-1)return ERROR;// 删除位置不合理 q = p->next;p->next = q->next;// 删除并释放结点 e = q->data;free(q);return OK;} // ListDelete_L 注：上述两个算法的时间复杂度均为O(n)。单链表的优点： 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 插入、删除操作方便 单链表的缺点： 指针占用额外存储空间 不能随机存取，查找速度慢 小结：本讲主要介绍了单链表的存储结构，以及的基本操作（建立、插入和删除）的实现。 四、作业布置 见习题集 实验作业见实验指导。 第四讲 循环链表，双向链表，链表应用 一、教学目标 1．了解循环链表和的基本概念； 2．掌握双向链表的插入和删除操作； 3．掌握一元多项式的表示及加法在链式存储结构上的实现。 二、重点与难点 双向链表的存储结构和基本操作实现。 三、教学内容与教学过程 讲授新课 单向循环链表 设指针p指向单向链表中最后一个结点，则p->next的值是0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最后一个结点，则p->next的值不是0而是等于指向循环链表中的第一个结点head的值。双向链表 如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下： typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior;// 指向前驱的指针域 struct DuLNode *next;// 指向后继的指针域 } DuLNode, *DuLinkList;设指针p指向双向链表中的某个结点，则显然有以下的结论： p->prior->next==p==p->next->prior(1)双向链表的插入操作 设指针变量p指向双向链表中的结点A，指针变量q指向被插入的新结点B，则在结点A的后面插入结点B的操作序列为： (1)q->next=p->next； (2)p->next->prior=q；(3)p->next=q； (4)q->prior=p； (2)双向链表的删除操作 设指针变量p指向双向链表中被删除的结点X，则删除结点X的操作序列为：(1)p->prior->next=p->next； (2)p->next->prior=p->prior； (3)free(p)； 注：在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指针域的操作次序，以免丢失链域信息而造成链表中断的错误。链式存储结构的应用：一元多项式的表示及相加 一元多项式Pn(x)可按升幂写成： 2n Pn(x)P0Px1P2xPnx它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示： P(P0,P1,P2,,Pn) 每项系数i隐含在系数Pi的序号里。 若Qm(x)为一个一元多项式，同样用线性表Q表示： Q(Q0,Q1,Q2,,Qm) 这两个多项式可以相加，结果为Rn(x)Pn(x)Qm(x)，其中设nm，则用线性表表示R为： R(P0Q0,P1Q1,P2Q2,,PmQm,Pm1,,Pn) 我们可以采用顺序存储结构存放P、Q和R，使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如S(x)=1+3x10001+2x20000的多项式时，要用长度为20001的线性表来表示。如果对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成： P((P0,e0),(P1,e1),(P2,e2),,(Pn,en)) 因此上式S(x)可表示成((1, 0),(3, 1001),(2, 20000))。显然这样的线性表应采用链式存储结构。课本 P41 图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x8+5x11和一元多项式B(x)=8x+22x7-9x8，由这两个多项式得到的和多项式如图课本 P412.18所示。 用链表表示多项式时，链表中的数据类型描述成： typedef struct polynomial{ float coef;int expn; struct polynomial *next;}ElemType;根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项则分别抄到和多项式中去。 第一步：分别从A表和B表的表头开始，根据比较pa->expn和pb->expn的比较结果分三种情况讨论，直到A表或B表全部处理完。 (1)pa->expn==pb->expn：则相加此两项的系数，如果相加后该项系数不等于0，则在C表中生成一个新结点存放该项，修改pa和pb使其指向各自的下一个结点。 (2)pa->expn > pb->expn：则复制A表中pa所指向的结点到C表中，修改pa使其指向下一个结点。 (3)pa->expn < pb->expn：则复制B表中pb所指向的结点到C表中，修改pb使其指向下一个结点。 第二步：若B表没有处理完，将B表中剩余结点复制到C表中；反之则将A表中剩余结点复制到C表中。 void create_item(LinkList &pc,float coef,int expn){ p=(LinkList)malloc(sizeof(LNode));p->coef=coef;p->expn=expn;pc->next=p;pc=p;} void ploy_add(LinkList pah,LinkList pbh,LinkList &pch){ pa = pah;pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode));// 为c链表添加一个头结点 while(pa!=0 && pb!=0){ if(pa->expn==pb->expn){ x=pa->coef+pb->coef;if(x!=0)create_item(pc,x,pa->expn);pa=pa->next;pb=pb->next;} else if(pa->expn>pb->expn){ create_item(pc,pa->coef,pa->expn);pa=pa->next;} else {create_item(pc,pb->coef,pb->expn);pb=pb->next;} } while(pa!=0){create_item(pc,pa->coef,pa->expn);pa=pa->next;} while(pb!=0){create_item(pc,pb->coef,pb->expn);pb=pb->next;} pc->next=0;pc=pch;pch=pch->next;free(pc);/* 释放c链中的头结点 */ } 小结：本讲主要介绍了循环链表和双向链表的基本概念，双向链表的插入和删除操作，一元多项式的表示及相加在链式存储结构上的实现。 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第 五 讲：栈 一、教学目标 1．了解栈的基本概念和基本操作； 2．掌握栈的基本操作在两种存储结构上的实现。 二、重点与难点 栈的基本操作在两种存储结构上实现。 三、教学内容与教学过程 首先复习线性表的知识，引入限定性的数据结构栈和队列。讲授新课 3.1 栈 3.1.1 抽象数据类型栈的定义 栈：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。 通过教材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。栈的抽象数据类型定义： ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ 基本操作： InitStack(&S)StackEmpty(S)Push(&S, e) DestroyStack(&S) StackLength(S) ClearStack(&S) GetTop(S, &e) Pop(&S, &e) } ADT Stack 3.1.2 栈的表示和实现 顺序栈 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 栈的顺序存储表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;顺序栈的基本操作的算法描述： 初始化，返回栈顶元素，入栈，出栈。(a)栈空栈满条件 栈空条件：top=base 栈满条件：base-top=stacksize(b)入栈操作 Status Push(SqStack &S, SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;} *S.top++ = e;return OK;}(c)出栈操作 Status Pop(SqStack &S, SElemType &e){ if(S.top==S.base)return ERROR;e=*--S.top;return OK;} 链栈：栈的链式存储结构。栈顶指针就是链表的头指针 栈的链式存储结构类似单链表的存储结构，链表中第一个结点表示栈顶，最后一个结点表示栈底。由于链表的长度可以动态增长，因此进行入栈操作时无需考虑栈的上溢，但进行出栈操作时，必需考虑栈的下溢，下溢的条件是top的值为0。 链式栈的入栈操作 Status Push(LinkList &top, ElemType x){ p=(LinkList *)malloc(sizeof(LNode));p->data=x;p->next=top;top=p;return OK;}(2)链式栈的出栈操作 Status Pop(LinkStack &top, ElemTye &y){ if(top==0)return ERROR;p=top;y=p->data;top=p->next;free(p);return OK;} 小结；本讲主要介绍了栈的基本概念，栈的基本运算，栈在顺序存储结构和链式存储结构上实现基本操作。 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第 六 讲：队列 一、教学目标 1．了解栈的基本概念和基本操作； 2．掌握栈的基本操作在两种存储结构上的实现。 二、重点与难点 栈的基本操作在两种存储结构上实现。 三、教学内容与教学过程 讲授新课 队列的基本概念 队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另一端进行的特殊线性表。允许插入（入队）操作的一端称为队尾，允许删除（出队）操作的一端称为队头。 设队列为q(a1,a2,,an)，则a1是队头元素，an是队尾元素。队列中的元素按照a1,a2,,an的顺序进入队列的，退出队列也只能按照这个次序依次退出，即只有在 a1,a2,,an1都退出队列后，an才能退出队列。因此队列也称为先进先出（FIFO）的线性表。 2、队列的基本操作 InitQueue(&Q)QueueEmpty(Q) DestroyQueue(&Q) ClearQueue(&Q)QueueLength(Q)GetHead(Q, &e)EnQueue(&Q, e)DeQueue(&Q, &e) 3、队列的顺序存储结构和循环队列 在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针front和rear。为了在C语言中描述方便起见，在此我们约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。 讨论：将数据10，20，30，40，50，60按照入队列、入队列、入队列、出队列、出队列、入队列、入队列、入队列、出队列和出队列的顺序，观察队列中队头和队尾指针的变化状态。 假设当前为队列分配的最大空间为6，则不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破环，然而，此时又不宜如顺序栈那样进行存储再分配扩大数组空间，因为队列的实际可用空间并末占满。解决这个问题的巧妙方法是将顺序队列的存储空间想象成一个逻辑上首尾相连的环状空间，这种存储结构称为循环队列。 分析课本P64图3.14可知，Q.front=Q.rear无法判断队列空间是“满”还是“空”。解决这个问题有两种方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的下一个位置上作为队列“满”的标志。因此，判断队列空的条件为Q.front=Q.rear；判断队列满的条件为Q.front =(Q.rear+1)% MAXQSIZE。 (a)顺序循环队列的类型描述 typedef struct { QElemType *base;int front;int rear;} SqQueue;(b)顺序循环队列的入队列操作 status EnQueue(SqQueue&Q, QelemType e){ if((Q.rear+1)%MAXSIZE==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;}(c)顺序循环队列的出队列操作 status DeQueue(SqQueue &Q, QelemType &e){ if(Q.rear==Q.front)return ERROR;e = Q.base[Q.front];Q.front =(Q.front+1)%MAXSIZE;return OK;} 4、队列的链式存储结构 队列的链式存储结构实际上是一个同时带有头指针和尾指针的单向链表，头指针指向队头元素，尾指针指向队尾元素。为了操作方便起见，给链式队列添加一个头结点。空的链式队列的判断条件为头指针和尾指针都指向头结点。 (a)链式循环队列的类型描述 typedef struct QNode { QElemType data; struct QNode *next;} QNode, *QueuePtr;typedef struct { QueuePtr front;// 队头指针 QueuePtr rear;// 队尾指针 } LinkQueue;(b)链式队列的入队列操作 stutus EnQueue(LinkQueue &Q, QelemType e){ p=(QueuePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;}(c)链式队列的出队列操作。 status DeQueue(LinkQueue &Q, QelemType &e){ if(Q.front==Q.rear returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;} 注意：当队列中最后一个元素被删除后，队列尾指针也丢失了，因此需要对队尾指针重新赋值。 小结：主讲主要介绍了队列的基本概念和基本操作，以及队列的基本操作在顺序存储结构和链式存储结构上的实现。 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第 七 讲：串 一、教学目标 1.熟悉串的定义以及基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。 2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆分配存储结构以及在其上实现串操作的基本方法。4.了解串的块链存储结构 二、重点与难点 串的存储结构以及基本操作的实现。 三、教学内容与教学过程 讲授新课 4.1 串类型的定义（1）基本概念： 串（string）：由零个或多个字符组成的有限序列，也称字符串。记为： S = „a1a2a3……an‟(n≥0)如：A= „BEIJING‟，B= „JING‟ 串的长度：串中字符的数目n。 空串：不含任何字符的串，串长度为0，空格串：仅由一个或多个空格组成的串，长度为串中空格字符的个数。 如： „ ‟，C= „ BEI JING ‟ 子串：由串中任意个连续的字符组成的子序列。 主串：包含子串的串。如：A= „ BEIJING ‟ B= „ JING ‟ 字符在串中的位置：字符在序列中的序号。 子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。 如：A= „ BEIJING ‟，B= „JING ‟，B在A中的位置为4。 串相等：当且仅当两个串的值相等。也就是说，只有两个串的长度相等 且各个对应位置的字符都相等时才相等。 （2）串的抽象数据类型定义： ADT String { 数据对象：D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n } 基本操作：（见教材P71）} ADT String 通过基本操作可以实现更复杂的操作。如通过判等、求串长和求子串等操作可以实现定位函数Index。 4.2 串的表示和实现 4.2.1 定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN + 1]; // 0号单元存放串的长度 特点： 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”（通过串联接和求子串来讲解）。 4.2.2 堆分配存储表示 以一组地址连续的存储单元存储串值的字符序列，存储空间在程序执行过程中动态分配。 C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。串堆分配存储表示： typedef struct { char *ch; // 若是非空串，则按串长分配存储区,否则ch为NULL int length;// 串长度 } HString;这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制（以串的复制操作为例）。 讲解串堆分配的表示与实现（P76，77）4.2.3 块链存储表示 以链表存储串值，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的传存储结构为块链结构。 #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE];struct Chunk *next; } Chunk;typedef struct { // 串的链表结构 Chunk *head, *tail;// 串的头和尾指针 int curlen; // 串的当前长度 } LString;讲解块链存储表示在串处理系统中的应用。小结：总结本讲的主要内容 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第九讲 数 组 一、教学目标 1.熟悉数组的定义。 2.掌握数组的顺序表示和基本操作的实现。 3.掌握特殊矩阵的压缩存储和稀疏矩阵三元组顺序表存储。4.了解稀疏矩阵的行逻辑链接的顺序表和十字链表表示储存 二、重点与难点 数组的压缩存储。 三、教学内容与教学过程 讲授新课 5.1 数组的定义 数组的抽象数据类型定义： ADT Array { 数据对象： 数据关系： 基本操作： }ADT Array 数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组 可以看成是线性表的线性表。举例 对于数组的操作一般只有两类：（与线性表对比讲解）（1）获得特定位置的元素值；（2）修改特定位置的元素值。5.2 数组的顺序表示和实现 对于数组A，一旦给定其维数n及各维长度bi（1≤i≤n），则该数组中元素的个数是固 定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。 数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和 PASCAL语言都是以行序为主。另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主。 以二维数组为例，假设每个元素只占L个存储单元，“以行为主”存放数组，下标从 0开始，首元素a00的地址为Loc[0,0] 求任意元素aij的地址，可由如下计算公式得到： Loc[i,j]=Loc[0,0]+b2×i+j 其中b2为第二维的长度。 对于ｎ维数组我们只要把上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存 储地址的计算公式。 Loc[j1，j2，…jn]=Loc[0，0，…，0]+ ci1niji 其中cn=L，ci-1=bi×ci，1 特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，对于零元素不分配空间。 （1）对称矩阵 满足条件：aij=aji 1≤i，j≤n（2）三角矩阵（3）带状矩阵 使用一维数组存储以上特殊矩阵，通过示例讲解矩阵中元素与一维数组中元素的对应关系。 5.3 稀疏矩阵 稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总 数的5或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。（1）稀疏矩阵的三元组表表示法 对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。 稀疏矩阵的三元组顺序存储表示 #define MAXSIZE 1000 typedef struct {int i, j; ElementType e； }Triple;typedef struct {Triple data[MAXSIZE+1]; int mu, nu, tu; }TSMatrix； 用三元组表实现稀疏矩阵的转置运算 矩阵转置：指变换元素的位置，把位于（row，col）位置上的元素换到（col，row）位置上，也就是说，把元素的行列互换。 用三元组实现稀疏矩阵转置运算的两种方式 重点掌握第一种方式：由转置后的矩阵中元素在三元组中的次序依次在转置前的矩阵中找到相应的三元组进行转置。通过程序结合矩阵进行讲解。 （2）矩阵的行逻辑链接的顺序表（了解）（3）十字链表表示 （了解）小结：总结本讲的主要内容 四、作业布置 见习题集 实验作业见实验指导。第二篇：数据结构电子教案 第六章
第三篇：数据结构实验教案
第四篇：数据结构实验教案
第五篇：数据结构教案C语言版
![下载数据结构电子教案 第七章[5篇范文]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 