{L=(SqList*)malloc(sizeof(SqList));
//分配存放线性表的顺序表空间
L->length=0;
}
（2）销毁线性表DestroyList(&L)
释放线性表L占用的内存空间。
voidDestroyList(SqList*&L)
{
free(L);
（3）判定是否为空表ListEmpty(L)
返回一个值表示L是否为空表。若L为空表，则返回true，否则返回false。
boolListEmpty(SqList*L)
return(L->length==0);
（4）求线性表的长度ListLength(L)
返回顺序表L的长度。只需返回length成员的值即可。
intListLength(SqList*L)
return(L->length);
（5）输出线性表DispList(L)
按照线性表中元素的逻辑顺序显示L中各元素的值。
voidDispList(SqList*L)
for(inti=0;i
（6）求某个数据元素值GetElem(L，i，&e)
该运算返回L中第i（1≤i≤ListLength(L)）个元素的值，存放在e中。
boolGetElem(SqList*L，inti，ElemType&e)
if(i<1||i>L->length)
returnfalse;
e=L->data[i-1];
returntrue;
（7）按元素值查找LocateElem(L，e)
顺序查找第一个与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。
intLocateElem(SqList*L，ElemTypee)
{inti=0;
while(i
i++;
if(i>=L->length)
return0;
else
returni+1;
（8）插入数据元素ListInsert(&L，i，e)
在顺序表L的第i（1≤i≤ListLength(L)+1）个位置上插入新的元素e。
boolListInsert(SqList*&L，inti，ElemTypee)
{intj;
if(i<1||i>L->length+1||L->length==MaxSize)
returnfalse;//参数错误时返回false
i--;//将顺序表逻辑序号转化为物理序号
for(j=L->length;j>i;j--)//将data[i..n]元素后移一个位置
L->data[j]=L->data[j-1];
L->data[i]=e;//插入元素e
L->length++;//顺序表长度增1
returntrue;//成功插入返回true
（9）删除数据元素ListDelete(&L，i，&e)
该运算删除顺序表L的第i（1≤i≤ListLength(L)）个元素。
boolListDelete(SqList*&L，inti，ElemType&e)
if(i<1||i>L->length)//参数错误时返回false
e=L->data[i];
for(j=i;j
L->data[j]=L->data[j+1];
L->length--;//顺序表长度减1
returntrue;//成功删除返回true
整体建立单链表
（1）头插法建表
voidCreateListF(LinkNode*&L，ElemTypea[]，intn)
{LinkNode*s;
inti;
L=(LinkNode*)malloc(sizeof(LinkNode));
L->next=NULL;//创建头结点，其next域置为NULL
for(i=0;i {s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=a[i];//创建数据结点s s->next=L->next;//将s插在原开始结点之前，头结点之后 L->next=s; （2）尾插法建表 voidCreateListR(LinkNode*&L，ElemTypea[]，intn) {LinkNode*s，*r; L=(LinkNode*)malloc(sizeof(LinkNode));//创建头结点 r=L;//r始终指向尾结点，开始时指向头结点 r->next=s;//将s插入r之后 r=s; r->next=NULL;//尾结点next域置为NULL 线性表基本运算在单链表上的实现 该运算建立一个空的单链表，即创建一个头结点。 voidInitList(LinkNode*&L) L->next=NULL; 释放单链表L占用的内存空间。即逐一释放全部结点的空间。 voidDestroyList(LinkNode*&L) LinkNode*pre=L，*p=L->next;//pre指向p的前驱结点 while(p!=NULL)//扫描单链表L {free(pre);//释放pre结点 pre=p;//pre、p同步后移一个结点 p=pre->next; free(pre);//循环结束时，p为NULL，pre指向尾结点，释放它 （3）判线性表是否为空表ListEmpty(L) 若单链表L没有数据结点，则返回真，否则返回假。 boolListEmpty(LinkNode*L) return(L->next==NULL); 返回单链表L中数据结点的个数。 intListLength(LinkNode*L) intn=0; LinkNode*p=L;//p指向头结点，n置为0（即头结点的序号为0） while(p->next!=NULL) {n++; p=p->next; return(n);//循环结束，p指向尾结点，其序号n为结点个数 逐一扫描单链表L的每个数据结点，并显示各结点的data域值。 voidDispList(LinkNode*L) LinkNode*p=L->next;//p指向开始结点 while(p!=NULL)//p不为NULL，输出p结点的data域 p=p->next;//p移向下一个结点 （6）求线性表L中位置i的数据元素GetElem(L，i，&e) 在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋给变量e。 boolGetElem(LinkNode*L，inti，ElemType&e) intj=0; LinkNode*p=L;//p指向头结点，j置为0（即头结点的序号为0） while(j {j++; if(p==NULL)//不存在第i个数据结点，返回false else//存在第i个数据结点，返回true {e=p->data; 在单链表L中从头开始找第一个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回0。 intLocateElem(LinkNode*L，ElemTypee) inti=1; LinkNode*p=L->next;//p指向开始结点，i置为1 while(p!=NULL&&p->data!=e) {p=p->next;//查找data值为e的结点，其序号为i if(p==NULL)//不存在元素值为e的结点，返回0 return(0); else//存在元素值为e的结点，返回其逻辑序号i return(i); 先在单链表L中找到第i-1个结点p，若存在这样的结点，将值为e的结点结点s插入到其后。 boolListInsert(LinkNode*&L，inti，ElemTypee) {intj=0; LinkNode*p=L，*s;//p指向头结点，j置为0 while(j if(p==NULL)//未找到第i-1个结点，返回false else//找到第i-1个结点p，插入新结点并返回true s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=e;//创建新结点s，其data域置为e s->next=p->next;//将s插入到p之后 p->next=s; 先在单链表L中找到第i-1个结点p，若存在这样的结点，且也存在后继结点，则删除该后继结点。 boolListDelete(LinkNode*&L，inti，ElemType&e) LinkNode*p=L，*q;//p指向头结点，j置为0 while(j else//找到第i-1个结点p {q=p->next;//q指向第i个结点 if(q==NULL)//若不存在第i个结点，返回false e=q->data; p->next=q->next;//从单链表中删除q结点 free(q);//释放q结点 returntrue;//返回true表示成功删除第i个结点 顺序表二路归并示例 voidUnionList(SqList*LA，SqList*LB，SqList*&LC) {inti=0，j=0，k=0;//i、j分别为LA、LB的下标，k为LC中元素个数 LC=(SqList*)malloc(sizeof(SqList));//建立有序顺序表LC while(i {if(LA->data[i] {LC->data[k]=LA->data[i]; i++;k++; else//LA->data[i]>LB->data[j] {LC->data[k]=LB->data[j]; j++;k++; while(i while(j LC->length=k; 单链表二路归并示例 voidUnionList1(LinkNode*LA，LinkNode*LB，LinkNode*&LC) {LinkNode*pa=LA->next，*pb=LB->next，*r，*s; LC=(LinkNode*)malloc(sizeof(LinkNode));//创建LC的头结点 r=LC;//r始终指向LC的尾结点 while(pa!=NULL&&pb!=NULL) {if(pa->data {s=(LinkNode*)malloc(sizeof(LinkNode));//复制结点 s->data=pa->data; r->next=s;r=s;//采用尾插法将s插入到LC中 pa=pa->next; s->data=pb->data; pb=pb->next; while(pa!=NULL) while(pb!=NULL) r->next=NULL//尾结点的next域置空 顺序栈的基本运算 （1）初始化栈InitStack(&s) 建立一个新的空栈s，实际上是将栈顶指针指向-1即可。 voidInitStack(SqStack*&s) {s=(SqStack*)malloc(sizeof(SqStack)); s->top=-1; （2）销毁栈DestroyStack(&s) 释放栈s占用的存储空间。 voidDestroyStack(SqStack*&s) free(s); （3）判断栈是否为空StackEmpty(s) 栈S为空的条件是s->top==-1。 boolStackEmpty(SqStack*s) return(s->top==-1); （4）进栈Push(&s，e) 在栈不满的条件下，先将栈指针增1，然后在该位置上插入元素e。 boolPush(SqStack*&s，ElemTypee) {if(s->top==MaxSize-1)//栈满的情况，即栈上溢出 s->top++;//栈顶指针增1 s->data[s->top]=e;//元素e放在栈顶指针处 （5）出栈Pop(&s，&e) 在栈不为空的条件下，先将栈顶元素赋给e，然后将栈指针减1。 boolPop(SqStack*&s，ElemType&e) {if(s->top==-1)//栈为空的情况，即栈下溢出 e=s->data[s->top];//取栈顶指针元素的元素 s->top--;//栈顶指针减1 （6）取栈顶元素GetTop(s，&e) 在栈不为空的条件下，将栈顶元素赋给e。 boolGetTop(SqStack*s，ElemType&e) if(s->top==-1)//栈为空的情况，即栈下溢出 链栈的基本运算 （1）初始化栈initStack(&s) 建立一个空栈s。实际上是创建链栈的头结点，并将其next域置为NULL。 voidInitStack(LinkStNode*&s) {s=(LinkStNode*)malloc(sizeof(LinkStNode)); s->next=NULL; 释放栈s占用的全部存储空间。 voidDestroyStack(LinkStNode*&s) {LinkStNode*p=s，*q=s->next; while(q!=NULL) {free(p); p=q; q=p->next; free(p);//此时p指向尾结点，释放其空间 栈S为空的条件是s->next==NULL，即单链表中没有数据结点。 boolStackEmpty(LinkStNode*s) return(s->next==NULL); 将新数据结点插入到头结点之后。 voidPush(LinkStNode*&s，ElemTypee) {LinkStNode*p; p=(LinkStNode*)malloc(sizeof(LinkStNode)); p->data=e;//新建元素e对应的结点p p->next=s->next;//插入p结点作为开始结点 s->next=p; 在栈不空的条件下，将头结点的后继结点的数据域赋给e，然后将其删除。 boolPop(LinkStNode*&s，ElemType&e) if(s->next==NULL)//栈空的情况 p=s->next;//p指向开始结点 e=p->data; s->next=p->next;//删除p结点 free(p);//释放p结点 （6）取栈顶元素GetTop(s，e) 在栈不为空的条件下，将头结点后继数据结点的数据域赋给e。 boolGetTop(LinkStNode*s，ElemType&e) {if(s->next==NULL)//栈空的情况 e=s->next->data; 顺序队列的基本运算 （1）初始化队列InitQueue(&q) 构造一个空队列q。将front和rear指针均设置成-1。 voidInitQueue(SqQueue*&q) {q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=-1; （2）销毁队列DestroyQueue(&q) 释放队列q占用的存储空间。 voidDestroyQueue(SqQueue*&q) free(q); （3）判断队列是否为空QueueEmpty(q) 若队列q满足q->front==q->rear条件，则返回true；否则返回false。 boolQueueEmpty(SqQueue*q) return(q->front==q->rear); （4）进队列enQueue(&q，e) 在队列不满的条件下，先将队尾指针rear循环增1，然后将元素添加到该位置。 boolenQueue(SqQueue*&q，ElemTypee) {if(q->rear==MaxSize-1)//队满上溢出 q->rear++; q->data[q->rear]=e; （5）出队列deQueue(&q，&e) 在队列q不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。 booldeQueue(SqQueue*&q，ElemType&e) {if(q->front==q->rear)//队空下溢出 q->front++; e=q->data[q->front]; 链队的基本运算 构造一个空队列，即只创建一个链队头结点，其front和rear域均置为NULL，不创建数据元素结点。 voidInitQueue(LinkQuNode*&q) {q=(LinkQuNode*)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; 释放队列占用的存储空间，包括链队头结点和所有数据结点的存储空间。 voidDestroyQueue(LinkQuNode*&q) {DataNode*p=q->front，*r;//p指向队头数据结点 if(p!=NULL)//释放数据结点占用空间 {r=p->next; while(r!=NULL) p=r;r=p->next; free(p);free(q);//释放链队结点占用空间 若链队结点的rear域值为NULL，表示队列为空，返回true；否则返回false。 boolQueueEmpty(LinkQuNode*q) return(q->rear==NULL); （4）进队enQueue(&q，e) voidenQueue(LinkQuNode*&q，ElemTypee) {DataNode*p; p=(DataNode*)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if(q->rear==NULL)//若链队为空，新结点既是队首结点又是队尾结点 q->front=q->rear=p; {q->rear->next=p;//将p结点链到队尾，并将rear指向它 q->rear=p; （5）出队deQueue(&q，&e) booldeQueue(LinkQuNode*&q，ElemType&e) {DataNode*t; if(q->rear==NULL)returnfalse;//队列为空 t=q->front;//t指向第一个数据结点 if(q->front==q->rear)//队列中只有一个结点时 else//队列中有多个结点时 q->front=q->front->next; e=t->data; free(t); 稀疏矩阵的基本运算 （1）从一个二维矩阵创建其三元组顺序表 按行序扫描二维矩阵A，将其非零的元素逐个插入到三元组顺序表t的尾部。 voidCreatMat(TSMatrix&t,ElemTypeA[M][N]) {inti,j;t.rows=M;t.cols=N;t.nums=0; for(i=0;i {for(j=0;j if(A[i][j]!=0) {t.data[t.nums].r=i; t.data[t.nums].c=j; t.data[t.nums].d=A[i][j]; t.nums++; （2）三元组顺序表元素赋值：A[i][j]=x（x≠0） 分为两种情况： ①将一个非0元素修改为另一个非0值，如A[5][6]=8 ②将一个0元素修改为非0值。如A[3][5]=8 boolValue(TSMatrix&t,ElemTypex,inti,intj) {intk=0,k1; if(i>=t.rows||j>=t.cols) returnfalse;//失败时返回false while(k while(k &&j>t.data[k].c)k++;//查找列 if(t.data[k].r==i&&t.data[k].c==j)//存在这样的元素 t.data[k].d=x; else//不存在这样的元素时插入一个元素 {for(k1=t.nums-1;k1>=k;k1--) {t.data[k1+1].r=t.data[k1].r; t.data[k1+1].c=t.data[k1].c; t.data[k1+1].d=t.data[k1].d; t.data[k].r=i;t.data[k].c=j;t.data[k].d=x; returntrue;//成功时返回true （3）将指定位置的元素值赋给变量执行x=A[i][j] 先在三元组顺序表t中找到指定的位置，再将该处的元素值赋给x。 boolAssign(TSMatrixt,ElemType&x,inti,intj) {intk=0; if(t.data[k].r==i&&t.data[k].c==j) x=t.data[k].d; x=0; （4）输出三元组顺序表 从头到尾扫描三元组顺序表t，依次输出元素值。 voidDispMat(TSMatrixt) {inti; if(t.nums<=0)return; for(i=0;i （5）矩阵转置对于一个m×n的矩阵Am×n，其转置矩阵是一个n×m的矩阵Bn×m,满足bi,j=aj,i，其中0≤i≤m-1，0≤j≤n-1。 voidTranTat(TSMatrixt,TSMatrix&tb) {intp,q=0,v;//q为tb.data的下标 tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums; if(t.nums!=0)//当存在非零元素时执行转置 for(v=0;v for(p=0;p if(t.data[p].c==v) {tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++; 树的存储结构 1、双亲存储结构 typedefstruct {ElemTypedata;//结点的值 intparent;//指向双亲的位置 }PTree[MaxSize]; 2、孩子链存储结构 typedefstructnode structnode*sons[MaxSons];//指向孩子结点 }TSonNode; 3.孩子兄弟链存储结构 typedefstructtnode structtnode*hp;//指向相邻右兄弟结点 structtnode*vp;//指向长子结点 }TSBNode; 二叉树基本运算 （1）创建二叉树CreateBTree(*&b，*str)：根据二叉树括号表示法字符串str生成对应的二叉链存储结构b。 （2）销毁二叉链存储结构DestroyBTree(*&b)：销毁二叉链b并释放空间。 voidDestroyBTree(BTNode*&b) {if(b==NULL) return; {DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b);//剩下一个结点b，直接释放 （3）查找结点FindNode(*b，x)：在二叉树b中寻找data域值为x的结点，并返回指向该结点的指针。 BTNode*FindNode(BTNode*b，ElemTypex) {BTNode*p; if(b==NULL)returnNULL; elseif(b->data==x)returnb; {p=FindNode(b->lchild，x); if(p!=NULL)returnp; elsereturnFindNode(b->rchild，x); （4）找孩子结点LchildNode(*p)和RchildNode(*p)：分别求二叉树中结点p的左孩子结点和右孩子结点。 BTNode*LchildNode(BTNode*p) returnp->lchild; BTNode*RchildNode(BTNode*p) returnp->rchild; （5）求高度BTHeight(*b)：求二叉树b的高度。若二叉树为空，则其高度为0；否则，其高度等于左子树与右子树中的最大高度加l。 intBTHeight(BTNode*b) {intlchilddep，rchilddep; if(b==NULL) return(0);//空树的高度为0 {lchilddep=BTHeight(b->lchild);//求左子树的高度为lchilddep rchilddep=BTHeight(b->rchild);//求右子树的高度为rchilddep return(lchilddep>rchilddep)(lchilddep+1):(rchilddep+1)); （6）输出二叉树DispBTree(*b)：以括号表示法输出一棵二叉树。 voidDispBTree(BTNode*b) {if(b!=NULL) if(b->lchild!=NULL||b->rchild!=NULL) DispBTree(b->lchild);//递归处理左子树 if(b->rchild!=NULL) DispBTree(b->rchild);//递归处理右子树 二叉树的遍历算法 先序遍历的递归算法： voidPreOrder(BTNode*b) PreOrder(b->lchild); PreOrder(b->rchild); 中序遍历的递归算法： voidInOrder(BTNode*b) {InOrder(b->lchild); InOrder(b->rchild); 后序遍历的递归算法： voidPostOrder(BTNode*b) {PostOrder(b->lchild); PostOrder(b->rchild); 层次遍历算法： {BTNode*data[MaxSize];//存放队中元素 intfront，rear;//队头和队尾指针 }SqQueue; voidLevelOrder(BTNode*b) SqQueue*qu;//定义环形队列指针 InitQueue(qu);//初始化队列 enQueue(qu，b);//根结点指针进入队列 while(!QueueEmpty(qu))//队不为空循环 {deQueue(qu，p);//出队结点p if(p->lchild!=NULL)//有左孩子时将其进队 enQueue(qu，p->lchild); if(p->rchild!=NULL)//有右孩子时将其进队 enQueue(qu，p->rchild); 先序遍历非递归算法1： voidPreOrder1(BTNode*b) SqStack*st;//定义栈指针st InitStack(st);//初始化栈st if(b!=NULL) {Push(st，b);//根结点进栈 while(!StackEmpty(st))//栈不为空时循环 {Pop(st，p);//退栈结点p并访问它 if(p->rchild!=NULL)//有右孩子时将其进栈 Push(st，p->rchild); if(p->lchild!=NULL)//有左孩子时将其进栈 Push(st，p->lchild); DestroyStack(st);//销毁栈 先序遍历非递归算法2： voidPreOrder2(BTNode*b) {BTNode*p;SqStack*st;//定义一个顺序栈指针st p=b; while(!StackEmpty(st)||p!=NULL) {while(p!=NULL)//访问结点p及其所有左下结点并进栈 Push(st，p);//结点p进栈 p=p->lchild;//移动到左孩子 //以下考虑栈顶结点 if(!StackEmpty(st))//若栈不空 {Pop(st，p);//出栈结点p p=p->rchild;//转向处理其右子树 中序遍历非递归算法： voidInOrder1(BTNode*b) {while(p!=NULL)//扫描结点p的所有左下结点并进栈 {Push(st，p);//结点p进栈 {Pop(st，p);//出栈结点p，访问结点p 后序遍历非递归算法： voidPostOrder1(BTNode*b)//后序非递归遍历算法 {BTNode*p，*r; boolflag; SqStack*st;//定义一个顺序栈指针st do r=NULL;//r指向刚刚访问的结点，初始时为空 flag=true;//flag为真表示正在处理栈顶结点 while(!StackEmpty(st)&&flag) {GetTop(st，p);//取当前的栈顶结点p if(p->rchild==r)//若结点p的右孩子为空或者为刚访问结点 Pop(st，p); r=p;//r指向刚访问过的结点 {p=p->rchild;//转向处理其右子 flag=false;//表示当前不是处理栈顶结点 }while(!StackEmpty(st));//栈不空循环 二叉树的构造 构造二叉树的算法1： BTNode*CreateBT1(char*pre，char*in，intn) {BTNode*s;char*p;intk; if(n<=0)returnNULL; s=(BTNode*)malloc(sizeof(BTNode));//创建根结点 s->data=*pre; for(p=in;p if(*p==*pre) break; k=p-in; s->lchild=CreateBT1(pre+1，in，k);//构造左子树 s->rchild=CreateBT1(pre+k+1，p+1，n-k-1);//构造右子树 returns; 构造二叉树的算法2： BTNode*CreateBT2(char*post，char*in，intn) {BTNode*b;charr，*p;intk; r=*(post+n-1);//根结点值 b=(BTNode*)malloc(sizeof(BTNode));//创建二叉树结点b b->data=r; for(p=in;p if(*p==r)break; b->lchild=CreateBT2(post，in，k);//递归构造左子树 b->rchild=CreateBT2(post+k，p+1，n-k-1);//递归构造右子树 returnb; 图基本运算算法设计 （1）创建图的运算算法 根据邻接矩阵数组A、顶点个数n和边数e来建立图的邻接表G（采用邻接表指针方式）。 voidCreateAdj(AdjGraph*&G，intA[MAXV][MAXV]，intn，inte) //创建图的邻接表 {inti，j; ArcNode*p; G=(AdjGraph*)malloc(sizeof(AdjGraph)); for(i=0;i G->adjlist[i].firstarc=NULL; for(i=0;i for(j=n-1;j>=0;j--) if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边 {p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点p p->adjvex=j;//存放邻接点 p->weight=A[i][j];//存放权 p->nextarc=G->adjlist[i].firstarc;//采用头插法插入结点p G->adjlist[i].firstarc=p; G->n=n;G->e=e; （2）输出图的运算算法 voidDispAdj(AdjGraph*G)//输出邻接表G for(i=0;i {p=G->adjlist[i].firstarc; while(p!=NULL) p=p->nextarc; （3）销毁图的运算算法 voidDestroyAdj(AdjGraph*&G)//销毁邻接表 {inti;ArcNode*pre，*p; for(i=0;i {pre=G->adjlist[i].firstarc;//p指向第i个单链表的首结点 if(pre!=NULL) {p=pre->nextarc; while(p!=NULL)//释放第i个单链表的所有边结点 {free(pre); pre=p; free(pre); free(G);//释放头结点数组 联通图的遍历算法 深度优先遍历算法 intvisited[MAX]={0};//全局数组 voidDFS(AdjGraph*G，intv) {ArcNode*p;intw; visited[v]=1;//置已访问标记 p=G->adjlist[v].firstarc;//p指向顶点v的第一个邻接点 {w=p->adjvex; if(visited[w]==0) DFS(G，w);//若w顶点未访问，递归访问它 p=p->nextarc;//p指向顶点v的下一个邻接点 广度优先遍历算法 voidBFS(AdjGraph*G，intv) {intw，i; intvisited[MAXV];//定义顶点访问标记数组 visited[i]=0;//访问标记数组初始化 enQueue(qu，v); while(!QueueEmpty(qu))//队不空循环 {deQueue(qu，w);//出队一个顶点w p=G->adjlist[w].firstarc;//指向w的第一个邻接点 while(p!=NULL)//查找w的所有邻接点 {if(visited[p->adjvex]==0)//若当前邻接点未被访问 visited[p->adjvex]=1;//置已访问标记 enQueue(qu，p->adjvex);//该顶点进队 p=p->nextarc;//找下一个邻接点 非连通图的遍历 深度优先遍历 VoidDFS1(AdjGraph*G) for(i=0;i if(visited[i]==0) DFS(G，i); 广度优先遍历 voidBFS1(AdjGraph*G) BFS(G，i); 无向图G是否连通的算法 intvisited[MAXV]; boolConnect(AdjGraph*G)//判断无向图G的连通性 boolflag=true; for(i=0;i visited[i]=0; DFS(G，0);//调用前面的DSF算法，从顶点0开始深度优先遍历 {flag=false; returnflag; 最小生成树构造算法 普里姆（Prim）算法 #defineINF32767//INF表示∞ voidPrim(MatGraphg，intv) {intlowcost[MAXV]; intmin; intclosest[MAXV]，i，j，k; for(i=0;i {lowcost[i]=g.edges[v][i]; closest[i]=v; for(i=1;i {min=INF; for(j=0;j if(lowcost[j]!=0&&lowcost[j] {min=lowcost[j]; k=j;//k记录最近顶点编号 lowcost[k]=0; for(j=0;j if(lowcost[j]!=0&&g.edges[k][j] {lowcost[j]=g.edges[k][j]; closest[j]=k; 克鲁斯卡尔（Kruskal）算法 voidKruskal(MatGraphg) {inti，j，u1，v1，sn1，sn2，k; intvset[MAXV]; EdgeE[MaxSize];//存放所有边 k=0;//E数组的下标从0开始计 for(i=0;i for(j=0;j if(g.edges[i][j]!=0&&g.edges[i][j]!=INF) {E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j]; k++; InsertSort(E，g.e);//用直接插入排序对E数组按权值递增排序 for(i=0;i vset[i]=i; k=1;//k表示当前构造生成树的第几条边 j=0;//E中边的下标，初值为0 while(k u1=E[j].u;v1=E[j].v;//取一条边的头尾顶点 sn1=vset[u1]; sn2=vset[v1];//分别得到两个顶点所属的集合编号 if(sn1!=sn2)//两顶点属于不同的集合 k++;//生成边数增1 for(i=0;i if(vset[i]==sn2)//集合编号为sn2的改为sn1 vset[i]=sn1 j++;//扫描下一条边 改进后的Kruskal算法 voidKruskal(MatGraphg)//改进的Kruskal算法 {inti,j,k,u1,v1,sn1,sn2; UFSTreet[MaxSize]; EdgeE[MaxSize]; k=1;//e数组的下标从1开始计 for(j=0;j<=i;j++) HeapSort(E,g.e);//采用堆排序对E数组按权值递增排序 MAKE_SET(t,g.n);//初始化并查集树t k=1;//k表示当前构造生成树的第几条边,初值为1 j=1;//E中边的下标从1开始 {u1=E[j].u; v1=E[j].v;//取一条边的头尾顶点编号u1和v2 sn1=FIND_SET(t,u1); sn2=FIND_SET(t,v1);//分别得到两个顶点所属的集合编号 if(sn1!=sn2)//两顶点属不同的集合,是最小生成树的边 UNION(t,u1,v1);//将u1和v1两个顶点合并 插入 顺序查找 intSeqSearch(RecTypeR[],intn,KeyTypek) while(i if(i>=n)//未找到返回0 returni+1;//找到返回逻辑序号i+1 带哨兵的顺序查找 intSeqSearch1(RecTypeR[],intn,KeyTypek) R[n].key=k; while(R[i].key!=k)//从表头往后找 if(i==n)//未找到返回0 折半查找 intBinSearch(RecTypeR[],intn,KeyTypek) intlow=0,high=n-1,mid; while(low<=high)//当前区间存在元素时循环 {mid=(low+high)/2; if(R[mid].key==k)//查找成功返回其逻辑序号mid+1 returnmid+1; if(k high=mid-1; low=mid+1;//继续在R[mid+1..high]中查找 采用折半查找索引表的分块查找 intIdxSearch(IdxTypeI[],intb,RecTypeR[],intn,KeyTypek)