数据结构算法设计与实现指导(下)ppt.ppt

数据结构算法设计与实现指导(下),李岩芳 何巍 主编,实验五：实验目的及要求,理解特殊的线性结构数组的抽象数据类型的定义，及在C语言环境中的表示方法。 理解数组的基本操作的算法，及在C语言环境中一些主要基本操作的实现。 在C语言环境下实现数组的应用操作： 用基本操作集定义一个三维数组(如A342)， 并输出。 利用三元组存储数组元素，并实现其转置。,实验内容,1.定义一个三维数组 定义存储结构 初始化一个N维数组 销毁一个N维数组 查找某个数组元素的位置 取出某个数组元素 为指定下标元素赋值 2.利用三元组顺序表存储稀疏矩阵，实现其转置 三元组存储结构 创建一个稀疏矩阵 销毁一个稀疏矩阵 输出一个稀疏矩阵 稀疏矩阵转置,定义三维数组,退出,稀疏矩阵主函数,N维数组定义,/定义数组维数最大为8维。 #define MAX_ARRAY_DIM 8 #define ERROR 0 #define OVERFLOW -2 #define UNDERFLOW -2 #define OK 1 typedef int ElemType; typedef int Status; /数组的结构 这里用到了三个概念： dim：维数； bounds：每一维的维界; constants：数组映像函数常量基址，即当某维元素下标加1或减1时, 存放数据元素的地址变动的空间。,N维数组定义,假如有一个三维数组，即dim=3，每一维的维界分别为： bounds0=3,bounds1=4，bounds2=2， 则每维的数组映像函数常量基址为：Constants2=1， Constants1=bounds2*constantds2=2*1=2， Constants0=bounds1*constantds1=4*2=8。 这个三维数组表示为：A342，是一个3页4行2列的数组。 typedef struct ElemType *base; int dim; int *bounds; int *constants; Array;,初始化数组,注意: ： 根据数组的维数及维界，开辟存储空间，定义数组映像函数常量基址。 Status InitArray(Array *A,int dim,.) int elemtotal=1,i; va_list ap; if(dimMAX_ARRAY_DIM) return ERROR; (*A).dim=dim; (*A).bounds=(int *)malloc(dim*sizeof(int); if(!(*A).bounds) exit(OVERFLOW); va_start(ap,dim); for(i=0;idim;+i) (*A).boundsi=va_arg(ap,int);,初始化数组,if(*A).boundsi=0;-i) (*A).constantsi=(*A).boundsi+1*(*A).constantsi+1; return OK; ,销毁数组,Status DestroyArray(Array *A) if(!(*A).base) return ERROR; else free(*A).base); (*A).base=NULL; if(!(*A).bounds) return ERROR;,销毁数组,else free(*A).bounds); (*A).bounds=NULL; if(!(*A).constants) return ERROR; else free(*A).constants); (*A).constants=NULL; return OK; ,查找某个数据元素的位置,算法功能： 参数ap指示某个数组元素的各下标值,如(2,3,1)表示第3页第4行第2列的数据元素。 Status Locate(Array A,va_list ap,int *off) int i,ind; *off=0; for(i=0;i=A.boundsi) return OVERFLOW; *off+=A.constantsi*ind; return OK; ,取出指定下标的数据元素,算法思想： 通过Locate()函数查找指定下标的数据元素，如存在，将其值送入变量e中。 Status Value(Array A,ElemType *e,.) va_list ap; Status result; int off; va_start(ap,*e); if(result=Locate(A,ap, ,为指定下标的元素赋值,该函数同Value()函数一样，利用Locate()函数查找 指定下标是否合法，如合法，将变量e的值赋给该下 标指定的元素。 Status Assign(Array *A,ElemType e,.) va_list ap; Status result; int off; va_start(ap,e); if(result=Locate(*A,ap, ,主函数-定义三维数组,源代码,进入TC,主函数-定义三维数组,void main() Array A; int i,j,k; int *p; int dim=3,bound1=3,bound2=4,bound3=2; ElemType e,*p1; clrscr(); InitArray(,主函数-定义三维数组,for(i=0;ibound1;i+) for(j=0;jbound2;j+) for(k=0;kbound3;k+) Assign( ,三元组存储结构,#define MAXSIZE 100 #define OK 1 typedef int ElemType; typedef int Status; /定义存储结构； i、j为非零元的行下标和列下标，e为非零元的值。 typedef struct int i,j; ElemType e; Triple; / mu为稀疏矩阵的行数，nu为列数，tu为非零元的个数。 dataMAXSIZE+1为存放非零元的三元组，0号单元未用。 typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; TSMatrix;,初始化稀疏矩阵的三元组,算法描述： 在输入非零元时，要求按行、列顺序输入，在本函数中使用两个判断语句实现对输入的非零元的行、列进行判断。第一个判断语句判断输入的非零元的行、列值是否合法，即是否在稀疏矩阵的行、列范围内，第二个判断语句判断是否按顺序输入非零元，即此次输入的非零元的行是否等于或大于上一个元素的行、列是否大于上一元素的列 。,流程图,源代码,初始化稀疏矩阵的三元组,流程图：,初始化稀疏矩阵的三元组,Status CreateSMatrix(TSMatrix *M) int i,m,n; ElemType e; Status k; printf(“Input RowNum, ColumnNum, ElementNum:“); scanf(“%d,%d,%d“,初始化稀疏矩阵的三元组,if(m(*M).mu|n(*M).nu) k=1; if(m(*M).datai-1.i|m=(*M).datai-1.i ,销毁稀疏矩阵的三元组,void DestroySMatrix(TSMatrix *M) (*M).mu=0; (*M).nu=0; (*M).tu=0; ,输出稀疏矩阵的三元组存储的非零元,void PrintSMatrix(TSMatrix M) int i; /*printf(“nMatrix%d%d, %d elementsn“,M.mu,M.nu,M.tu);*/ printf(“nRow Column Valuen“); for(i=1;i=M.tu;i+) printf(“%2d%4d%8dn“,M.datai.i,M.datai.j, M.datai.e); ,稀疏矩阵的转置,Status TransposeSMatrix(TSMatrix M,TSMatrix *T) int p,q,col; (*T).mu=M.nu; (*T).nu=M.mu; (*T).tu=M.tu; if(*T).tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if(M.datap.j=col) (*T).dataq.i=M.datap.j; (*T).dataq.j=M.datap.i; (*T).dataq.e=M.datap.e; +q; return OK; ,主函数,调用基本操作集函数实现稀疏矩阵的转置。 main() TSMatrix A,B; clrscr(); CreateSMatrix( ,进入TC,三维数组执行结果,稀疏矩阵执行结果,实验六：二叉树,理解二叉树的抽象数据类型的定义，及在C语言环境中的表示方法。 理解二叉树的基本操作的算法，及在C语言环境中一些主要基本操作的实现。 在C语言环境下实现二叉树的应用操作： 采用顺序存储创建一棵二叉树。 采用二叉链表存储一棵二叉树，并实现二叉树的先序、中序、后序遍历的递归算法。,实验内容,创建完全二叉树 计算二叉树深度 输出完全二叉树 输出二叉树主函数 完全二叉树遍历简介 建立空二叉树 销毁二叉树 构造二叉树 输出二叉树结点 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 遍历主函数,退出,算法描述： 首先输入建立完全二叉树的结点的个数，通过个数控制输入结点。结点按照完全二叉树的序号存入一维数组中。如输入5个结点，结点分别为： 1-T0，2-T1，3-T2，4-T3，5-T4。,创建完全二叉树,代码段,typedef int TElemType; typedef int Status; typedef TElemType SqBiTree20; Status CreateBiTree(SqBiTree *T) int i=0; int len; printf(“Input NodeNumber:“); scanf(“%d“, ,创建完全二叉树,计算二叉树深度,注：pow(2,j)表示2j。 假设二叉树的深度为j，则有： 2j-1 NodeNumber =pow(2,j); return j; ,算法思想：本函数实现了完全二叉树的分层显示结点。利用二叉树的性质2控制某一层的所有结点的输出。利用性质5通过几个选择判断，输出某结点的有关关容，如该结点是否有双亲结点，没有，则显示该结点为根结点，有，则显示其双亲结点；是否为叶子结点，是，则显示该结点为叶子结点，不是，则显示其左右孩子结点。,输出二叉树,流程图,源代码,void Print(SqBiTree T,int NodeNum) int i,j; clrscr(); for(j=1;j=0) printf(“(Parent is %d) “,T(i+1)/2-1); else printf(“(Root Node) “);,输出二叉树,if(!(Ti*2+1!=0 ,输出二叉树,void main() SqBiTree T; int NodeNum; NodeNum=CreateBiTree( ,主函数,进入TC,二叉树遍历简介,typedef char TElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; /定义二叉树及结点的结构。 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; Status InitBiTree(BiTree *T) /创建一颗空树 *T=NULL; return OK; ,初始化二叉树,void DestroyBiTree(BiTree *T) if(*T) if(*T)-lchild) DestroyBiTree( ,销毁完全二叉树,构造二叉树,void CreateBiTree(BiTree *T) TElemType ch; int i; InitBiTree(T); scanf(“%c“, ,输出二叉树结点,Status visitT(TElemType e) printf(“%c “,e); return OK; ,先序遍历二叉树,Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType) if(T) Visit(T-data); PreOrderTraverse(T-lchild,Visit); PreOrderTraverse(T-rchild,Visit); return OK; else return ERROR; ,中序遍历二叉树,Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType) if(T) InOrderTraverse(T-lchild,Visit); Visit(T-data); InOrderTraverse(T-rchild,Visit); return OK; else return ERROR; ,后序遍历二叉树,Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType) if(T) PostOrderTraverse(T-lchild,Visit); PostOrderTraverse(T-rchild,Visit); Visit(T-data); return OK; else return ERROR; ,main() BiTree T; clrscr(); printf(“Input BiTree by PreOrder:“); CreateBiTree( ,主函数,进入TC,建立完全二叉树执行结果,二叉树遍历执行结果,实验七：实验目的及要求,理解图的抽象数据类型的定义，及在C语言环境中的表示方法。 理解图的基本操作的算法，及在C语言环境中一些主要基本操作的实现。 在C语言环境下实现图的应用操作： 使用邻接矩阵存储结构，实现无向网的创建和输出。 利用基本操作集，实现采用邻接表表示的无向图的非递归的广度优先遍历算法。,实验内容,无向图创建和输出 邻接矩阵存储结构 创建无向图 查找顶点是否在图中 输出无向网的邻接矩阵 主函数-生成无向图并显示 非递归广度优先遍历 存储结构 邻接表存储的无向图 查找指定顶点的邻接点 销毁图 输出图的邻接表 广度优先遍历 主函数-非递归广度优先遍历,退出,邻接矩阵存储结构,#define INFINITY 1024 #define MAX_VERTEX_NUM 20 #define MAX_NAME 3 typedef int VRType; typedef char InfoType; typedef int Status; typedef char VertexTypeMAX_NAME; typedef enumDG,DN,UDG,UDNGraphKind; /有向图、有向网、无向图、无向网,邻接矩阵存储结构,typedef struct VRType adj; /对无权图用1或0表示相邻否；带权图则为权值类型 InfoType *info; /该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /图的结构定义。 typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; /相邻矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 GraphKind kind; /图的种类标志 MGraph;,创建无向图,在本函数创建邻接矩阵时，权值赋为“INFINITY”，当在Display()输出时才显示成“*”，图7.1中直接显示“*”是为了使显示的邻接矩阵更简捷，易懂。 在输入弧时，为了突出修改权值的操作，没有对输错的弧(即图中不存在的顶点的弧)进行判断，只以弧的输入计数对程序进行控制，读者可自行添加。 如读者希望创建无向图，对本函数只需做两点修改： 在初始建立邻接矩阵时，初始值赋为0。 在输入的弧信息中，只输入两个顶点，不需要输入权值，而且在邻接矩阵中将0修改为1。 有向图和有向网的创建与无向图、无向网的创建类似，需注意的是在输入弧信息后修改邻接矩阵时，只修改一条弧的信息，如输入弧(V1、V2、5)，则只将第1行第二列的0或*修改为5。,流程图,源代码,创建无向图,创建无向图,Status CreateUDN(MGraph *G) int i,j,k,w; VertexType va,vb; printf(“Please input vexnum, arcnum:“); scanf(“%d,%d“, ,查找顶点是否在图中,int LocateVex(MGraph G,VertexType u) /查找顶点u是否存在于图的顶点向量中。 int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.vexsi)=0) return i; return -1; ,输出无向网的邻接矩阵,void Display(MGraph G) int i,j; for(i=0;iG.vexnum;+i) printf(“G.vexs%d=%sn“,i,G.vexsi); printf(“G.arcs.adj:n“); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) if(G.arcsij.adj=INFINITY) printf(“ *“); else printf(“%6d“,G.arcsij.adj); printf(“n“); ,主函数-生成无向网并显示,main() MGraph G; clrscr(); CreateUDN( ,进入TC,邻接表存储结构,#define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int InfoType; typedef int Status; typedef int QElemType; typedef char VertexType3; typedef enumDG,DN,UDG,UDNGraphKind; typedef enumFALSE,TRUE Bool; Bool visitedMAX_VERTEX_NUM; /队列结点的结构。 typedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr;,邻接表存储结构,typedef struct/链队列结构。 QueuePtr front,rear; LinkQueue; void(*VisitFunc)(char* v); /弧结点。 typedef struct ArcNode int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType *info; ArcNode; typedef struct/邻接表的顶点结构。 VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; typedef struct /图的结构。 AdjList vertices; /顶点的向量 int vexnum,arcnum; int kind; ALGraph;,邻接表存储无向图,邻接表存储无向图,因无向图中的一条边包含的是两个关系，即在无向图中v1到v2有一条边，描述成(v1，v2)，表示从v1到v2有一弧、从v2到v1也有一条弧。而在有向图中就不是这样，如在有向图中v1到v2有一条弧，描述成，表示从v1到v2有一弧，如果在有向图的定义中没有指明，则不存在从v2到v1的弧。 本函数实现的是无向图的创建，故在处理弧时采用的是每输入一条弧，就生成两个弧结点。如果实现有向图的创建，在此就应该只生成一个弧结点。,流程图,源代码,邻接表存储无向图,邻接表存储无向图,Status CreateGraph(ALGraph *G) int i,j,k; VertexType va,vb; ArcNode *p; (*G).kind = DN; printf(“Please input vexnum, arcnum:“); scanf(“%d,%d“,邻接表存储无向图,for(k=0;kadjvex=j; p-info=NULL; p-nextarc=(*G).verticesi.firstarc; (*G).verticesi.firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=i; p-info=NULL; p-nextarc=(*G).verticesj.firstarc; (*G).verticesj.firstarc=p; return OK; ,查找指定顶点的邻接点,int FirstAdjVex(ALGraph G,VertexType v) ArcNode *p; int v1; v1=LocateVex(G,v); p=G.verticesv1.firstarc; if(p) return p-adjvex; else return -1; 标注：在邻接表的顶点向量中查找指定的顶点v，返回顶点v的第一个邻接点，如存在返回邻接表中弧结点的信息，如没有返回-1,查找指定顶点的邻接点,/返回下一个邻接点。 int NextAdjVex(ALGraph G,VertexType v,VertexType w) ArcNode *p; int v1,w1; v1=LocateVex(G,v); w1=LocateVex(G,w); p=G.verticesv1.firstarc; while(p ,销毁图,注： 将图的顶点数、弧数置为0，将邻接表释放 void DestroyGraph(ALGraph *G) int i; ArcNode *p,*q; (*G).vexnum=0; (*G).arcnum=0; for(i=0;inextarc; if(*G).kind%2) free(p-info); free(p);p=q; ,输出图的邻接表,void Display(ALGraph G) int i;ArcNode *p; printf(“n“); for(i=0;iadjvex); while(p) printf(“-%d“,p-adjvex); p=p-nextarc; printf(“n“); ,广度优先算法,算法思想： 假设在图中某顶点v出发，在访问了v之后依次访问v的各个末曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。 注：这里用到了队列,因为它的先进先出的特点,能够方便地输出图中的顶点,实现“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。队列采用链式结构。关于队列的操作不在描述。,流程图,源程序,广度优先算法,广度优先算法,void BFSTraverse(ALGraph G,void(*Visit)(char*) int v,u,w; VertexType u1,w1; LinkQueue Q; for(v=0;vG.vexnum;+v) visitedv=FALSE; InitQueue(,广度优先算法,while(!QueueEmpty(Q) DeQueue( ,主函数,main() ALGraph G; CreateGraph( ,进入TC,邻接矩阵创建无向图执行结果,广度优先遍历执行结果,实验八：实验目的及要求,理解排序的概念，及直接插入排序、快速排序算法的思想。 在C语言环境中将一个无序序列的数据元素，按照直接插入排序和快速排序的算法分别重新排列成按关键字有序。,实验内容,直接插入排序 快速排序,退出,快速排序,存储结构 快速排序算法函数 输出结果函数 主函数,直接插入排序,注意：对每一个关键字的排序都有输出。开始排序后，第一个输出语句指明是第几趟排序，第二个输出语句指明是哪个关键字排序，第三个输出语句通过循环实现已排序的关键字的输出，并且用括号括起来，以示与未排序的关键字的区别，第四个输出语句也是通过循环输出尚未排序的关键字。,存储结构,源程序,主函数,直接插入排序存储结构,#define MAXSIZE 20 typedef int KeyType; typedef struct KeyType key; ElemType; /用顺序存储的线性表来存储待排序的关键字。 typedef struct ElemType rMAXSIZE+1; int length; SqList;,直接插入排序,void InsertSort(SqList *L) int i,j,k; SqList temp; temp=*L; printf(“ “); for(i=2;i=(*L).length;+i) if (*L).ri.key(*L).ri-1.key) (*L).r0=(*L).ri; for(j=i-1;(*L).r0.key(*L).rj.key;-j) (*L).rj+1=(*L).rj; (*L).rj+1=(*L).r0; ,直接插入排序,printf(“ni=%d: (%d) “,i,temp.ri.key); printf(“(%d“,(*L).r1.key); for(k=2;k=i;k+) printf(“ %d“,(*L).rk.key); printf(“) “); for(;k=(*L).length;k+) printf(“%d “,(*L).rk.key); void SqListPrint(SqList L) /输出顺序存储的线性表 int i; for(i=1;i=L.length;i+) printf(“%d “,L.ri.key); printf(“n“); ,主函数,算法思想： 本函数依然使用输入待排序的关键字个数来控制输入的关键字，输入关键字时用空格分隔。需要注意的是，0号单元作为排序时的哨兵，关键字从1号单元开始存储。,进入TC,主函数,void main() ElemType *d; SqList la; int I; clrscr(); printf(“Input datanum:“); scanf(“%d“, ,快速排序,存储结构： int count=0; #define MAXSIZE 20 typedef int KeyType; typedef struct KeyType key; TElemType; typedef struct TElemType rMAXSIZE+1; int length; SqList;,快速排序,int Partition(SqList *L,int low,int high) /一趟快速排序。 KeyType pivotkey; int i; (*L).r0=(*L).rlow; pivotkey=(*L).rlow.key; while(low=pivotkey) -high; (*L).rlow=(*L).rhigh; while(lowhigh ,快速排序,/对顺序表L中的子序列L.rlowhigh作快速排序。 递归调用快速排序函数实现一个无序序列的关键字的排序。 void QSort(SqList *L,int low,int high) int pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); /对顺序表L作快速排序。 void QuickSort(SqList *L) QSort(L,1,(*L).length); ,快速排序,/输出存储在线性表中的关键字。 void print(SqList L) int i; for(i=1;i=L.length;i+) printf(“%d “,L.ri.key); printf(“n“); ,主函数,在主函数中输入待排序的关键字序列。 主要思想是：在输入关键字时进行判断，有重复的 加以标识。,进入TC,代码段,主函数,void main() TElemType *d;SqList la; int i; clrscr(); printf(“Input datanum:“); scanf(“%d“, ,直接插入排序执行结果,快速排序执行结果,综合训练,迷宫 稀疏矩阵相乘 最优二叉树 最小生成树 关键路径 最短路径,退出,迷宫,在计算机中用下图所示的方块表示迷宫，图中空白方块表示为通道，带阴影线的方块表示为墙，带竖线条的为入口处，横线条的为出口处。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。,迷宫,算法思想：在算法中以二维坐标定义一个当前位置，若当前位置可通，则纳入当前路径（入栈），并按照东南西北的顺序继续下一位置探索，即切换下一位置为当前位置，重复直至到达出口。若当前位置不可通，留下不能通过的标记-1，继续向当前路径的其他方向探索，若四个方向都不通，则删除当前路径的栈顶元素（出栈），再将新的栈顶元素作为当前位置继续探索。 初始定义时若该位置可通用1表示，若该位置不通用0表示。当算法执行时，迷宫的起始点就是所求路径中的第1个通道，所求的路径依次用2、3表示，即通道上的二维坐标的值由1修改为第N个路径值。,进入TC,核心代码,迷宫,若迷宫maze中存在从入口start到出口end的通道，则求得一条。 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE。 Status MazePath(PosType start,PosType end) SqStack S; PosType curpos; SElemType e; InitStack( do if(Pass(curpos) / 当前位置可以通过，即是未曾走到过的通道块,迷宫,FootPrint(curpos); / 留下足迹 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; Push( ,迷宫,else / 当前位置不能通过 if(!StackEmpty(S) Pop( if(e.di3) / 没到最后一个方向(北),迷宫, e.di+; / 换下一个方向探索 Push( ,稀疏矩阵相乘,算法思想：稀疏矩阵采用三元组表作为存储结构。其定义同实验五的稀疏矩阵三元组的定义。创建稀疏矩阵的算法同实验五的算法类似，在这里增加了计算各行非零元素位置表的处理。 矩阵相乘时只需将中的列值和矩阵中行值相等的各对元素分别相乘，其乘积矩阵的元素是个累加值，故须将各对分别相乘的值进行累加到适当的求累计和的变量上。,进入TC,核心代码,稀疏矩阵相乘,Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) int arow,brow,p,q,ccol,ctempMAXRC+1; if(M.nu!=N.mu) / 矩阵M的列数应和矩阵N的行数相等 return ERROR; (*Q).mu=M.mu; (*Q).nu=N.nu; (*Q).tu=0; / Q初始化 M.rposM.mu+1=M.tu+1; / 为方便后面的while循环临时设置 N.rposN.mu+1=N.tu+1; if(M.tu*N.tu!=0) / M和N都是非零矩阵 for(arow=1;arow=M.mu;+arow) / 处理M的每一行 for(ccol=1;ccol=(*Q).nu;+ccol) ctempccol=0; / 当前行的各列元素累加器清零 (*Q).rposarow=(*Q).tu+1;,稀疏矩阵相乘,for(p=M.rposarow;pMAXSIZE) return ERROR; (*Q).data(*Q).tu.i=arow; (*Q).data(*Q).tu.j=ccol;(*Q).data(*Q).tu.e=ctempccol; return OK; ,最优二叉树,算法思想：在设计实现时利用一维数组存储最优二叉树的结点，每个数组元素包含了该结点的权值、双亲结点、左右孩子结点等信息。在选取两个最小权值的元素处理时，利用线性链表将树的结点按权值从小到大排列，这样每次选取两个权值最小的结点就变成了从线性链表中删除两个数据元素，将两个权值最小的结点的和生成一个父结点的操作就变成了在线性链表中插入一个结点，依然使线性链表保持从小到大的排列。这样就将树型结构简化为线性结构来处理。,进入TC,核心代码,最优二叉树,-赫夫曼树和赫夫曼编码的存储表示。 typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树 typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表 /w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC。 void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) if(n=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=*HT+1,i=1;i=n;+i,+p,+w) *p=*w,0,0,0; for(;i=m;+i,+p) (*p).parent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 select(*HT,i-1,最优二叉树,(*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; / 从叶子到根逆向求每个字符的赫夫曼编码 *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i=n;i+) /逐个字符求赫夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) / 从叶子到根逆向求编码 if(*HT)f.lchild=c) cd-start=0; else cd-start=1; (*HC)i=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(*HC)i, ,最小生成树,算法思想：假设N（V，E）是连通网，TE是N上最小生成树中边的集合。算法从Uu0（u0V），TE开始，重复执行下述操作：在所有uU,vV-U的边（u，v）E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直至UV为止。此时TE中必有n-1条边，则T（V，TE）为N的最小生成树。 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。,进入TC,核心代码,最小生成树,用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边。 记录从顶点集U到V-U的代价最小的边的辅助数组定义。 void MiniSpanTree_PRIM(MGraph G,VertexType u) int i,j,k; minside closedge; k=LocateVex(G,u); for(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj.adj; closedgek.lowcost=0; / 初始,U=u printf(“MiniSpanTree;n“);,最小生成树,for(i=1;iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k=minimum(closedge,G); / 求出T的下一个结点：第K顶点 p