数据结构习题

目录

习题一 1习题二 4习题三 7

一元多项式之和实验 8哈夫曼树实验 13

求最小生成树算法实验 17拓扑排序算法 22

求最短路径（迪接斯特算法）关键路径 35快速排序 43

习题一

28①、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。②、已知L为非递减的顺序表，请设计算法删除L中重复的元素（即删除后使L表变为一递增表）。

#include#include#include

#define LIST_SIZE 100#define OK 1

typedef struct{

int *elem;int length;int listsize;}SqList;

int InitList_Sq(SqList &L){

L.elem=(int*)malloc(LIST_SIZE*sizeof(int)); if(!L.elem) exit(0); L.length=0;

L.listsize=LIST_SIZE; return OK;}

void ListCreate(SqList &L,int i){

if(i>L.listsize) exit(0);

for(int j=0;jscanf(\"%d\ L.length++;}}

int SortInsert(SqList &L,int e){

int i,k=0; int *p,*q; p=L.elem;

q=L.elem+L.length-1; for(i=1;i<=L.length;i++) {

if(e<=*p) {

for(q++;q>p;q--) {

*q=*(q-1); } *p=e; k=1; break; } else p++; }

if(k==0) {

*(q+1)=e; }

L.length++; return OK;}

void main(){

void ListCreate(SqList &L,int i); int InitList_Sq(SqList &L); int SortInsert(SqList &L,int e); int i;

SqList La;

InitList_Sq(La); ListCreate(La,3); int a;

printf(\"需要插入的数字： \"); scanf(\"%d\ SortInsert(La,a);

printf(\"插入后的元素列表变为：\\n\"); for(i=0;iprintf(\"%d \ }

printf(\"\\n\");}/*

void SortDeleSame(SqList &L){

int *i; int *p; int *q; p=L.elem;

q=L.elem+L.length-1;

while(pif(*p==*(p+1)) {

for(i=p;i*i=*(i+1); }

L.length--; q--; } else p++; }

}

void main(){

int InitList_Sq(SqList &L); void SortDeleSame(SqList &L); void ListCreate(SqList &L,int i); int i;

SqList Lb;

InitList_Sq(Lb); ListCreate(Lb,5); SortDeleSame(Lb); printf(\"\\n\");

for(i=0;iprintf(\"%d \ }}*/

习题二

③、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。

#include#include#include

typedef struct LNode{

int data;

struct LNode *next;}LNode,*LinkList;

void main(){

void CreatList_LinkList(LinkList &L,int n); void ListInsert_LinkList(LinkList &L,int x); void Print_LinkList(LinkList &L,int n); LinkList La; int a,b;

printf(\"请问要输入多少数：\"); scanf(\"%d\

printf(\"请输入这%d个数：\\n\ CreatList_LinkList(La,a);

printf(\"请问要插入的数是：\"); scanf(\"%d\

ListInsert_LinkList(La,b); printf(\"插入后结果为:\\n\"); Print_LinkList(La,a+1); printf(\"\\n\");}

void CreatList_LinkList(LinkList &L,int n){

int i,a;

LNode *s,*tail;

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;tail=L;

for(i=0;is=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ tail->next=s;

tail=tail->next;}

tail->next=NULL;

}

void Print_LinkList(LinkList &L,int n){

LNode* p; p=L->next;

for(int i=0;iprintf(\"%d \ p=p->next; }}

void ListInsert_LinkList(LinkList &L,int x){

int k=0;

LNode *pre,*p,*s; pre=L; p=L->next; while(pre&&p) {

if(x<=p->data) {

s=(LinkList)malloc(sizeof(LNode)); s->next=pre->next; pre->next=s; s->data=x; k=1; break; }

pre=pre->next; p=p->next; }

if(k==0)

{

s=(LinkList)malloc(sizeof(LNode)); pre->next=s; s->data=x;

s->next=NULL; }}

习题三

④、设计一算法，逆置带头结点的动态单链表L。//La为已知单链表，Lb为新建的一个单链表

void Trunhead_LinkList(LinkList &La,LinkList &Lb,int n){

LinkList p=La->next; LinkList s;

Lb=(LinkList)malloc(sizeof(LNode)); Lb->next=NULL; for(i=0;is=(LinkList)malloc(sizeof(LNode)); s->data=p->data; s->next=Lb->next; Lb->next=s; p=p->next; }}

一元多项式之和实验

#include #include #include typedef struct polynode {

float coef; //系数int expn; //指数struct polynode *next;}polynode,*polylist;

void create(polylist &L) //创建链表{

int m; polylist p;

printf(\"请输入一元多项式项数：\"); scanf(\"%d\

L=(polylist)malloc(sizeof(polynode)); p=L;

for(int i=1;i<=m;i++) //利用循环，依次输入系数和指数 {

p->next=(polylist)malloc(sizeof(polynode));p=p->next;

printf(\"请输入第%d项的系数和指数：\scanf(\"%f %d\ }

p->next=NULL;}

void display(polylist L) //显示链表内容{

polylist p;

p=L->next;

printf(\"%.0fx(%d)\ p=p->next; while(p) {

if(p->coef<0) {

printf(\"%.0fx(%d)\ } else {

printf(\"+%.0fx(%d)\ }

p=p->next; }

printf(\"\\n\");}

void add(polylist La, polylist Lb, polylist &Lc) //加法函数{

polylist pa,pb,pc; float x;

pa=La->next ; pb=Lb->next ;

pc=(polylist)malloc(sizeof(polynode)); Lc=pc;

while (pa&&pb)

{ if(pa->expn==pb->expn) { x=pa->coef+pb->coef; if(x!=0) {

pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next; pc->coef=x;

pc->expn=pa->expn; }

pa=pa->next; pb=pb->next;

}

else // 无同类项可合并，指数小者复制到C表 { pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

if(pa->expn < pb->expn) //a的指数小于b的指数 {

pc->coef=pa->coef; pc->expn=pa->expn; pa=pa->next; } else {

pc->coef=pb->coef; pc->expn=pb->expn; pb=pb->next; } } }

while(pa) //还剩下a多项式

{ pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

pc->coef=pa->coef; pc->expn=pa->expn; pa=pa->next; }

while(pb) //还剩下b多项式

{ pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

pc->coef=pb->coef; pc->expn=pb->expn; pb=pb->next; }

pc->next=NULL;}

void subtract(polylist La,polylist Lb,polylist &Lc) //减法函数{ polylist pa,pb,pc;

float x;

pa=La->next ; pb=Lb->next ;

pc=(polylist)malloc(sizeof(polynode)); Lc=pc;

while(pa&&pb) {

if(pa->expn==pb->expn) {

x=pa->coef-pb->coef; if(x!=0)

{ pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next; pc->coef=x;

pc->expn=pa->expn; }

pa=pa->next; pb=pb->next; }

else //无同类项可合并，指数小者复制到C表 { pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

if (pa->expnexpn) //a的指数小于b的指数 {

pc->coef=pa->coef; pc->expn=pa->expn; pa=pa->next; } else

{ pc->coef=-pb->coef; pc->expn=pb->expn; pb=pb->next; } } }

while(pa) //还剩下a多项式

{ pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

pc->coef=pa->coef;

pc->expn=pa->expn; pa=pa->next; }

while (pb) //还剩下b多项式

{ pc->next=(polylist)malloc(sizeof(polynode)); pc=pc->next;

pc->coef=-pb->coef; pc->expn=pb->expn; pb=pb->next; }

pc->next=NULL;}

void main() //主函数{

polylist La,Lb,Lc,Ld;create(La); create(Lb);

printf(\"一元多项式1：\");display(La);

printf(\"一元多项式2：\");display(Lb);add(La,Lb,Lc);

printf(\"加的结果：\");display(Lc);

subtract(La,Lb,Ld);printf(\"减的结果\");display(Ld);}

哈夫曼树实验

#include#include#include

#include

typedef struct{

char ch;int weight;

int parent,lchild,rchild;}HTNode,*HuffmanTree;

typedef char**HuffmanCode;

void CreateHuffmanTree(HuffmanTree &HT,int w[],char ch[],intn);

void Select(HuffmanTree HT,int n,int &s1,int &s2);void HTCoding(HuffmanTree HT,HuffmanCode &HC,int n);void PrintCode(HuffmanCode HC,int n,char ch[]);

double AverageLength(HuffmanTree HT,HuffmanCode HC,int n);void DeCode(HuffmanTree HT,int n);

void main() //主函数{

int n;int i;

char arrch[20];int arrweight[20]; double avlength;char ch;

HuffmanTree HT;HuffmanCode HC;

printf(\"请输入要输入字母的个数：\");scanf(\"%d\

while((ch=getchar())!='\\n');if(n>20||n<2) exit(0);for(i=0;iprintf(\"请输入第%d个字母：\ scanf(\"%c\

printf(\"请输入该字母权重：\");

scanf(\"%d\ while((ch=getchar())!='\\n');}

CreateHuffmanTree(HT,arrweight,arrch,n);HTCoding(HT,HC,n);PrintCode(HC,n,arrch);

avlength=AverageLength(HT,HC,n);

printf(\"平均编码长度为：%.2f\\n\printf(\"请输入要解码的数据：\");DeCode(HT,n);for(i=0;ivoid CreateHuffmanTree(HuffmanTree &HT,int w[],char n){

int i,m,s1,s2;m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;i++){

HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch=ch[i-1];}

for(i=n+1;i<=m;i++){

HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch='\\0';

ch[],int}

for(i=n+1;i<=m;i++){

Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight; }}

void Select(HuffmanTree HT,int n,int &s1,int &s2){

int i;int min;min=1000;

for(i=1;i<=n;i++){

if(HT[i].parent==0&&HT[i].weight<=min) {

min=HT[i].weight; s1=i; }}

min=1000;

for(i=1;i<=n;i++){

if(HT[i].parent==0&&HT[i].weight<=min&&i!=s1) {

min=HT[i].weight; s2=i; }}}

void HTCoding(HuffmanTree HT,HuffmanCode &HC,int n){

int i,j,k,start;int f;int c;char* cd;

HC=(HuffmanCode)malloc((n)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-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-1]=(char*)malloc((n-start)*sizeof(char)); for(j=start,k=0;jHC[i-1][k]=cd[j]; }}

free(cd);}

void PrintCode(HuffmanCode HC,int n,char ch[]){

for(int i=0;iprintf(\"%c的编码是%s\\n\}}

double AverageLength(HuffmanTree HT,HuffmanCode HC,int n)

{

int i,j;

int s1=0,s2=0;

for(i=1;i<=n;i++){

s1=s1+HT[i].weight;}

for(i=0,j=1;is2=s2+HT[j].weight*strlen(HC[i]);}

return s2*1.0/s1;}

void DeCode(HuffmanTree HT,int n){

int i;

char endflag='#';char ch;i=2*n-1;

scanf(\"%c\while(ch!=endflag){

if(ch=='0')

{i=HT[i].lchild;} else

{i=HT[i].rchild;} if(HT[i].lchild==0) {

printf(\"%c\ i=2*n-1; }

scanf(\"%c\}

if((HT[i].lchild!=0)&&(i!=2*n-1)){printf(\"\\n未能完全解码\\n\");}printf(\"\\n\");

}

求最小生成树算法实验

#include#include

#define INFINITY 10000 //最大值∞

#define MAX_VERTEX_NUM 20 //最大顶点数

typedef struct{

char vexs[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum,arcnum;}MGraph;

typedef struct{

int adjvex;int endvex;int lowcost;

}closedge[MAX_VERTEX_NUM];

void main(){

void CreateUDN(MGraph &G);//创建无向网络

int LocateVex(MGraph G,char v);//结点在顶点向量中的下标 void PrintUDN(MGraph G);//输出存储结构示意图

void MiniSpanTree_PRIM(MGraph G,closedge &minedge);//求最小生成树的算法

void PrintMinEdge(MGraph G,closedge minedge);//输出最小生成树的边

MGraph G;

closedge minedge; CreateUDN(G);

printf(\"\\n该图的邻接矩阵存储示意图如下：\\n\"); PrintUDN(G); printf(\"\\n\");

MiniSpanTree_PRIM(G,minedge); printf(\"该图生成树的边如下：\\n\"); PrintMinEdge(G,minedge); printf(\"\\n\");}

int LocateVex(MGraph G,char v) //结点在顶点向量中的下标{

int i;

for(i=0;iif(v==G.vexs[i]) {

return i; } }}

void CreateUDN(MGraph &G) //创建无向网络{

int i,j,k,w; char v1,v2,ch;

printf(\"请输入该网络的结点数：\"); scanf(\"%d\

printf(\"请输入该网络的边数：\"); scanf(\"%d\

printf(\"请输入这%d个结点：\\n\

while((ch=getchar())!='\\n'); //这条很关键不可少！！！ for(i=0;iscanf(\"%c\ }

for(i=0;ifor(j=0;jG.arcs[i][j]=INFINITY; } }

for(k=0;kprintf(\"请输入第%d条边及它的权重：\

while((ch=getchar())!='\\n'); //这条很关键不可少！！！ scanf(\"%c%c %d\ i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=w; }

for(i=0;iG.arcs[i][i]=0; }}

void PrintUDN(MGraph G) //输出存储结构示意图{

int i,j;printf(\" \");

for(i=0;iprintf(\"%6c\}

printf(\"\\n\");

for(i=0;iprintf(\"%c\ for(j=0;jif(G.arcs[i][j]==10000) {

printf(\" ∞\"); } else {

printf(\"%6d\ } }

printf(\"\\n\");}

}

void MiniSpanTree_PRIM(MGraph G,closedge &minedge) //求最小生成树的算法{

int i,j,k,z; int temp;

int currentmin; k=0;

for(j=1;jminedge[j-1].adjvex=k; minedge[j-1].endvex=j;

minedge[j-1].lowcost=G.arcs[k][j]; }

for(i=0;icurrentmin=minedge[i].lowcost; k=i;

for(j=i+1;j{

if(minedge[j].lowcostcurrentmin=minedge[j].lowcost; k=j; } }

temp=minedge[i].adjvex;

minedge[i].adjvex=minedge[k].adjvex; minedge[k].adjvex=temp;

temp=minedge[i].endvex;

minedge[i].endvex=minedge[k].endvex; minedge[k].endvex=temp;

temp=minedge[i].lowcost;

minedge[i].lowcost=minedge[k].lowcost; minedge[k].lowcost=temp;

for(j=i+1;jz=minedge[i].endvex; k=minedge[j].endvex; if(k!=z) {

if(G.arcs[z][k]minedge[j].adjvex=z;

minedge[j].lowcost=G.arcs[z][k]; } } } }}

void PrintMinEdge(MGraph G,closedge minedge) //输出最小生成树的边

{

int i;

for(i=0;i%d\\n\}}

拓扑排序算法

#include#include

#define MAX_VERTEX_NUM 20

typedef struct ArcNode//表结点{

int adjvex;//该弧所指向的顶点位置

struct ArcNode *nextarc;//指向下一条弧的指针}ArcNode;

typedef struct VNode//头结点{

char data;//顶点信息

ArcNode *firstarc;//指向第一条依附于该顶点的弧的指针}VNode;

typedef VNode AdjList[MAX_VERTEX_NUM];//邻接表

typedef struct //图{

AdjList vertices;//邻接表vertices

int vexnum,arcnum;//图当前的定点数和弧数}ALGraph;

typedef struct //栈的存储结构{

int *base;//在栈构造之前和销毁之后，base的值为NULLint *top;//栈顶指针

int stacksize;//当前已分配的存储空间}SqStack;

void InitStack(SqStack &S) //构造一个空栈{

S.base=(int*)malloc(30*sizeof(int));if(!S.base){exit(0);}S.top=S.base;S.stacksize=30;}

int StackEmpty(SqStack S) //判断是否为空栈，若栈为空返回TRUE，不为空返回FALSE{

if(S.base==S.top){

return true;}else{

return false;}}

void Push(SqStack &S,int e) //插入新的栈顶元素{

if(S.top-S.base>=S.stacksize){

S.base=(int*)realloc(S.base,

(S.stacksize+100)*sizeof(int));//存储空间增加100 if(!S.base) {exit(0);}

S.top=S.base+S.stacksize;

S.stacksize+=100;//栈的容量增加100}

*S.top=e;S.top++;}

void Pop(SqStack &S,int &e) //弹出栈顶元素，用e返回{

if(S.top==S.base){

exit(0);}

S.top--;e=*S.top;}

int LocateVex(ALGraph G,char v) //结点在顶点向量中的下标{

int i;

for(i=0;iif(v==G.vertices[i].data) {

return i; } }}

void FindInDegree(ALGraph G,int array[]) //寻找各个顶点的入度{

int k=0;

ArcNode *p;

p=G.vertices[0].firstarc; //从第一个顶点的第一个表结点开始找

while(1){

if(p) {

array[p->adjvex]++; p=p->nextarc;

}

if(!p) //如果p为空，则从查找下一个顶点 {

k++;

if(kp=G.vertices[k].firstarc; } else {

break; } }}

}

void CreateALGraph(ALGraph &G) //创建一个邻接表{

int i,k,a,b;char ch,v0,v1; ArcNode *p;

printf(\"请输入结点数：\");scanf(\"%d\printf(\"请输入边数：\");scanf(\"%d\

printf(\"请输入顶点信息：\\n\");while((ch=getchar())!='\\n');

for(i=0;iscanf(\"%c\

G.vertices[i].firstarc=NULL; //不知道对不对！！！用点还是用箭头？}

printf(\"请输入有向边：(格式为‘v0’->‘v1’)\\n\");for(k=0;kwhile((ch=getchar())!='\\n'); //这个很关键！！！不

能少！！！

printf(\"请输入第%d条边的起点和终点：\ scanf(\"%c->%c\ a=LocateVex(G,v0); b=LocateVex(G,v1);

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=b;

p->nextarc=G.vertices[a].firstarc; G.vertices[a].firstarc=p;}}

void TopologicalSort(ALGraph G) //拓扑算法{

int i,count;SqStack S;ArcNode *p;

int indegree[MAX_VERTEX_NUM]={0}; FindInDegree(G,indegree);InitStack(S);

for(i=0;iif(!indegree[i]) {

Push(S,i); }}

if(StackEmpty(S)) //如果栈为空，则是有环图，则终止程序{

printf(\"该图是有环图，错误！\"); exit(0);}

count=0;Pop(S,i);

printf(\"%c\count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

indegree[p->adjvex]--; if(!indegree[p->adjvex]) {

Push(S,p->adjvex); }}

while(!StackEmpty(S)) //当栈为空时跳出循环{

Pop(S,i);

printf(\"->%c\ count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

indegree[p->adjvex]--;

if(!indegree[p->adjvex]) //如果该结点入度为0，则压入栈

{

Push(S,p->adjvex); } }}

if(countprintf(\"错误！！！\");}}

void main() //主函数{

ALGraph G;

CreateALGraph(G);

printf(\"\\n拓扑排序的结果为：\");TopologicalSort(G);printf(\"\\n\");}

求最短路径（迪接斯特算法）

#include#include

#define INFINITY 10000 //最大值∞

#define MAX_VERTEX_NUM 20 //最大顶点数

#define MAX_ARCNUM_NUM 20 //最大边数typedef struct{

char vexs[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum,arcnum;}MGraph;

typedef struct //栈的存储结构{

int *base;//在栈构造之前和销毁之后，base的值为NULLint *top;//栈顶指针

int stacksize;//当前已分配的存储空间}SqStack;

void main(){

void CreateDN(MGraph &G);//创建有向网络

int LocateVex(MGraph G,char v);//结点在顶点向量中的下标

void ShortestPath(MGraph G,int v0,bool P[][MAX_VERTEX_NUM],int D[],int pre[]);//用迪杰斯特拉算法求最短路径 void PrintDN(MGraph G);//输出存储结构示意图 void PrintShortestPath(MGraph G,int a,bool P[]

[MAX_VERTEX_NUM],int D[],int pre[]);//输出最短路径 void InitStack(SqStack &S); //构造一个空栈 void Pop(SqStack &S,int &e);

void Push(SqStack &S,int e); //插入新的栈顶元素

int StackEmpty(SqStack S); //判断是否为空栈，若栈为空返回TRUE，不为空返回FALSE

int a;

char ch,v0;

int D[MAX_VERTEX_NUM];

bool P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int pre[MAX_VERTEX_NUM]; MGraph G; CreateDN(G);

printf(\"\\n该图的邻接矩阵存储示意图如下：\\n\"); PrintDN(G); printf(\"\\n\");

printf(\"请输入起点结点：\"); while((ch=getchar())!='\\n'); scanf(\"%c\

a=LocateVex(G,v0); //获取字符V0对应的下标a

ShortestPath(G,a,P,D,pre); //迪杰斯特拉最短路径算法 /*for(int i=0;iprintf(\"%d \ }

printf(\"以上为数组pre中的值\\n\");*/ printf(\"该图最短路径如下：\\n\"); PrintShortestPath(G,a,P,D,pre); printf(\"\\n\");}

void InitStack(SqStack &S) //构造一个空栈{

S.base=(int*)malloc(30*sizeof(int));if(!S.base){exit(0);}S.top=S.base;S.stacksize=30;}

int StackEmpty(SqStack S) //判断是否为空栈，若栈为空返回TRUE，不为空返回FALSE{

if(S.base==S.top){

return true;}else{

return false;

}

}

void Push(SqStack &S,int e) //插入新的栈顶元素{

if(S.top-S.base>=S.stacksize){

S.base=(int*)realloc(S.base,(S.stacksize+100)*sizeof(int));//存储空间增加100

if(!S.base) {exit(0);}

S.top=S.base+S.stacksize;

S.stacksize+=100;//栈的容量增加100}

*S.top=e;S.top++;}

void Pop(SqStack &S,int &e) //弹出栈顶元素，用e返回{

if(S.top==S.base){

exit(0);}

S.top--;e=*S.top;}

int LocateVex(MGraph G,char v) //结点在顶点向量中的下标{

int i;

for(i=0;iif(v==G.vexs[i]) {

return i; }

}}

void CreateDN(MGraph &G) //创建有向网络{

int i,j,k,w; char v1,v2,ch;

printf(\"请输入该网络的结点数：\"); scanf(\"%d\

printf(\"请输入该网络的边数：\"); scanf(\"%d\

printf(\"请输入这%d个结点：\\n\

while((ch=getchar())!='\\n'); //这条很关键不可少！！！ for(i=0;iscanf(\"%c\ }

for(i=0;ifor(j=0;jG.arcs[i][j]=INFINITY; } }

for(k=0;kprintf(\"请输入第%d条边及它的权重：\

while((ch=getchar())!='\\n'); //这条很关键不可少！！！ scanf(\"%c%c %D\ i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w; }

for(i=0;iG.arcs[i][i]=0; }

}

void ShortestPath(MGraph G,int v0,bool P[][MAX_VERTEX_NUM],int D[],int pre[]) //用迪杰斯特拉算法求最短路径{

int i,w,v,min;

bool final[MAX_VERTEX_NUM]; for(v=0;vfinal[v]=false;

D[v]=G.arcs[v0][v]; pre[v]=-1;

for(w=0;wP[v][w]=false;

if(D[v]P[v][v0]=true; //此处要修改，把书上的 P[v][v]=true; pre[v]=v0; } }}

D[v0]=0;

final[v0]=true;pre[v0]=-1;

for(i=1;imin=INFINITY;

for(w=0;wif(!final[w]) {

if(D[w]v=w;

min=D[w];

true改为false } } }

final[v]=true;

for(w=0;wif(!final[w]&&(min+G.arcs[v][w]D[w]=min+G.arcs[v][w]; for(int i=0;iP[w][i]=P[v][i]; }

P[w][w]=true; pre[w]=v; } }}

}

void PrintDN(MGraph G) //输出存储结构示意图{

int i,j;printf(\" \");

for(i=0;iprintf(\"%6c\}

printf(\"\\n\");

for(i=0;iprintf(\"%c\ for(j=0;jif(G.arcs[i][j]==10000) {

printf(\" ∞\");

} else {

printf(\"%6d\ } }

printf(\"\\n\");}

}

void PrintShortestPath(MGraph G,int a,bool P[][MAX_VERTEX_NUM],int D[],int pre[]) //输出最短路径{

int i,j,e;SqStack S;InitStack(S);

for(i=0;iif(pre[i]!=-1) //i的前驱存在 { j=i;

while(pre[j]!=-1) //不断地获取其前驱，并压入栈S中，直到前驱为空停止 {

Push(S,pre[j]); j=pre[j]; }

while(!StackEmpty(S)) //把栈中的元素逐个输出 {

Pop(S,e);

printf(\"%c->\ }

printf(\"%c\

if(D[i]!=INFINITY) //输出路径最短长度 {

printf(\" 长度是：%d\\n \ }

}

else if(i!=a) //i的前驱不存在并且i不是起点下标 {

printf(\"%c->%c 无路径\\n\ }}}

关键路径

#include#include

#define MAX_VERTEX_NUM 20

typedef struct ArcNode//表结点{

int adjvex;//该弧所指向的顶点位置

struct ArcNode *nextarc;//指向下一条弧的指针int info;}ArcNode;

typedef struct VNode//头结点{

char data;//顶点信息

ArcNode *firstarc;//指向第一条依附于该顶点的弧的指针}VNode;

typedef VNode AdjList[MAX_VERTEX_NUM];//邻接表

typedef struct //图{

AdjList vertices;//邻接表vertices

int vexnum,arcnum;//图当前的定点数和弧数

}ALGraph;

typedef struct //栈的存储结构{

int *base;//在栈构造之前和销毁之后，base的值为NULLint *top;//栈顶指针

int stacksize;//当前已分配的存储空间}SqStack;

void InitStack(SqStack &S) //构造一个空栈{

S.base=(int*)malloc(30*sizeof(int));if(!S.base){exit(0);}S.top=S.base;S.stacksize=30;}

bool StackEmpty(SqStack S) //判断是否为空栈，若栈为空返回TRUE，不为空返回FALSE{

if(S.base==S.top){

return true;}else{

return false;}}

void Push(SqStack &S,int e) //插入新的栈顶元素{

if(S.top-S.base>=S.stacksize){

S.base=(int*)realloc(S.base,(S.stacksize+100)*sizeof(int));//存储空间

增加100

if(!S.base) {exit(0);}

S.top=S.base+S.stacksize;

S.stacksize+=100;//栈的容量增加100}

*S.top=e;S.top++;}

void Pop(SqStack &S,int &e) //弹出栈顶元素，用e返回{

if(S.top==S.base){

exit(0);}

S.top--;e=*S.top;}

int LocateVex(ALGraph G,char v) //结点在顶点向量中的下标{

int i;

for(i=0;iif(v==G.vertices[i].data) {

return i; } }}

void FindInDegree(ALGraph G,int array[]) //寻找各个顶点的入度{

int k=0; ArcNode *p;

p=G.vertices[0].firstarc; //从第一个顶点的第一个表结点开始找while(1){

if(p) {

array[p->adjvex]++; p=p->nextarc; }

if(!p) //如果p为空，则从查找下一个顶点 {

k++;

if(kp=G.vertices[k].firstarc; } else {

break; } }}}

void CreateALGraph(ALGraph &G) //创建一个邻接表{

int i,k,a,b;char ch,v0,v1; ArcNode *p;

printf(\"请输入结点数：\");scanf(\"%d\printf(\"请输入边数：\");scanf(\"%d\

printf(\"请输入顶点信息：\\n\");while((ch=getchar())!='\\n');

for(i=0;iscanf(\"%c\

G.vertices[i].firstarc=NULL; //初始化}

printf(\"请输入有向边：(格式为‘v0’->‘v1’)\\n\");for(k=0;kprintf(\"请输入第%d条边的起点和终点：\

while((ch=getchar())!='\\n'); //这个很关键！！！不能少！！！ scanf(\"%c->%c\ a=LocateVex(G,v0); b=LocateVex(G,v1);

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=b;

p->nextarc=G.vertices[a].firstarc; G.vertices[a].firstarc=p; printf(\"该边的权值为：\"); scanf(\"%d\}}

void TopologicalOrder(ALGraph G,SqStack &T,int ve[]) //拓扑算法{

int i,k,count;SqStack S;ArcNode *p;

int indegree[MAX_VERTEX_NUM]={0}; FindInDegree(G,indegree);InitStack(S);InitStack(T);count=0;

for(i=0;iif(!indegree[i]) {

Push(S,i); }}

for(i=0;i{

ve[i]=0;}

if(StackEmpty(S)) //如果栈为空，则是有环图，则终止程序{

printf(\"该图是有环图，错误！\"); exit(0);}

while(!StackEmpty(S)) //当栈为空时跳出循环{

Pop(S,i); Push(T,i); count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; indegree[k]--;

if(!indegree[k]) //如果该结点入度为0，则压入栈 {

Push(S,k); }

if((ve[i]+p->info)>ve[k]) {

ve[k]=ve[i]+p->info; } }}

if(countprintf(\"错误！！！\");}

}

void CriticalPath(ALGraph G) //关键活动{

int i,j,ee,el;int k,dut;

ArcNode *p;

int ve[MAX_VERTEX_NUM]={0};int vl[MAX_VERTEX_NUM]={0};SqStack T;

TopologicalOrder(G,T,ve);

/*printf(\"结点活动值：\"); //测试堆栈T和数组ve的正确性 for(i=0;iprintf(\"%d \ }*/

/*printf(\"\\n\"); int e;

printf(\"堆栈T:\");

while(!StackEmpty(T)) {

Pop(T,e);

printf(\"%d \ }

printf(\"\\n\");*/

for(i=0;ivl[i]=ve[G.vexnum-1];}

/*p=G.vertices[0].firstarc; while(p) {

printf(\"123\\n\"); p=p->nextarc;

printf(\"...%d\ }*/

/*printf(\"vl中的值：\"); //测试vl[]的正确性 for(i=0;ivl[i]=ve[G.vexnum-1]; }*/

//在这之前都正确，错误在下面

while(!StackEmpty(T)) //while()循环没错，错误在下面这个for循环。。。{

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {

k=p->adjvex; dut=p->info;

if((vl[k]-dut)vl[j]=vl[k]-dut; }

//printf(\"%d\

//printf(\"000\\n\"); //验证 }

//printf(\"000\\n\"); //验证}

/*printf(\"vl中的值：\"); //测试vl[]的正确性 for(i=0;ivl[i]=ve[G.vexnum-1]; }*/

for(j=0;jfor(p=G.vertices[j].firstarc;p;p=p->nextarc) {

k=p->adjvex; dut=p->info; ee=ve[j]; el=vl[k]-dut; printf(\"%c->%c %d\ if(ee==el) {

printf(\" 是关键路径\"); }

printf(\"\\n\"); }

权重：}

}

void main() //主函数{

ALGraph G;

CreateALGraph(G);

printf(\"\\n关键活动如下：\\n\");

/*int ve[MAX_VERTEX_NUM]={0}; //测试TopologicalOrder()函数是否正确，T与ve[]是否正确 SqStack T;

TopologicalOrder(G,T,ve); printf(\"结点活动值：\"); for(int i=0;iprintf(\"%d \ }

printf(\"\\n\"); int e;

printf(\"T::::\");

while(!StackEmpty(T)) {

Pop(T,e);

printf(\"%d \ }*/

CriticalPath(G);printf(\"\\n\");}

快速排序

#include#define MAXSIZE 20

typedef struct{

int key;}Red;

typedef struct{

Red r[MAXSIZE+1];int length;}SqList;

void CreateSqList(SqList &L,int n) //{

int i;

L.length=0; for(i=1;i<=n;i++){

scanf(\"%d\ L.length++;

创建线性表}

}

void PrintSqList(SqList &L){

for(int i=1;i<=L.length;i++){

printf(\"%d \}}

int Partition(SqList &L,int low,int high) //快速排序第一趟{

int pivotkey;L.r[0]=L.r[low];

pivotkey=L.r[low].key;while(lowwhile(low=pivotkey) {

--high; }

L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端 while(low++low; }

L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端}

L.r[low]=L.r[0];return low;}

void QSort(SqList &L,int low,int high) //对顺序表L中的子序列作快速排序{

int pivoloc;

if(lowpivoloc=Partition(L,low,high); QSort(L,low,pivoloc-1); QSort(L,pivoloc+1,high);}}

void QuickSort(SqList &L) //对顺序表L作快速排序{

QSort(L,1,L.length);}

void main() //主函数{

int a;SqList L;

printf(\"请问总共有几个数：\");scanf(\"%d\

printf(\"请输入要进行快速排序的这%d个数\\n\ CreateSqList(L,a); QuickSort(L);

printf(\"快速排序后的结果为：\\n\");PrintSqList(L);printf(\"\\n\");}