2022年数据结构c语言版实验及源代码整理 .pdf

《2022年数据结构c语言版实验及源代码整理 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构c语言版实验及源代码整理 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验 1 求两个多项式的相加运算（线性表）编写一个程序用单链表存储多项式，并实现两个多项式相加的函数。/*文件名 :实验 1.cpp*/ #include #include #define MAX 20 /*多项式最多项数*/ typedef struct /*定义存放多项式的数组类型*/ float coef; /*系数 */ int exp; /*指数 */ PolyArrayMAX; typedef struct pnode /*定义单链表结点类型*/ float coef; /*系数 */ int exp; /*指数 */ struct pnode *next; PolyNode; v

2、oid DispPoly(PolyNode *L) /*输出多项式 */ PolyNode *p=L-next; while (p!=NULL) printf(%gX%d ,p-coef,p-exp); p=p-next; printf(n); void CreateListR(PolyNode *&L,PolyArray a,int n) /*尾插法建表 */ PolyNode *s,*r;int i; L=(PolyNode *)malloc(sizeof(PolyNode); /*创建头结点 */ L-next=NULL; r=L; /*r 始终指向终端结点,开始时指向头结点*/ for

3、 (i=0;icoef=ai.coef; s-exp=ai.exp; r-next=s; /*将*s 插入 *r 之后 */ r=s; r-next=NULL; /*终端结点 next 域置为 NULL*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - void Sort(PolyNode *&head) /*按 exp 域递减排序 */ PolyNode *p=head-next,*q,*r; if (p!=NULL) /

4、*若原单链表中有一个或以上的数据结点*/ r=p-next; /*r 保存 *p 结点后继结点的指针*/ p-next=NULL; /*构造只含一个数据结点的有序表*/ p=r; while (p!=NULL) r=p-next; /*r 保存 *p 结点后继结点的指针*/ q=head; while (q-next!=NULL & q-next-expp-exp) q=q-next; /*在有序表中找插入*p 的前驱结点 *q*/ p-next=q-next; /*将*p 插入到 *q 之后 */ q-next=p; p=r; void Add(PolyNode *ha,PolyNode *

5、hb,PolyNode *&hc) /*求两有序集合的并*/ PolyNode *pa=ha-next,*pb=hb-next,*s,*tc; float c; hc=(PolyNode *)malloc(sizeof(PolyNode); /*创建头结点 */ tc=hc; while (pa!=NULL & pb!=NULL) if (pa-exppb-exp) s=(PolyNode *)malloc(sizeof(PolyNode); /* 复制结点 */ s-exp=pa-exp;s-coef=pa-coef; tc-next=s;tc=s; pa=pa-next; else if

6、(pa-expexp) s=(PolyNode *)malloc(sizeof(PolyNode); /* 复制结点 */ s-exp=pb-exp;s-coef=pb-coef; tc-next=s;tc=s; pb=pb-next; else /*pa-exp=pb-exp*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - c=pa-coef+pb-coef; if (c!=0) /*系数之和不为0 时创建新结点*/ s

7、=(PolyNode *)malloc(sizeof(PolyNode); /*复制结点 */ s-exp=pa-exp;s-coef=c; tc-next=s;tc=s; pa=pa-next; pb=pb-next; if (pb!=NULL) pa=pb; /*复制余下的结点*/ while (pa!=NULL) s=(PolyNode *)malloc(sizeof(PolyNode); /*复制结点 */ s-exp=pa-exp;s-coef=pa-coef; tc-next=s;tc=s; pa=pa-next; tc-next=NULL; void main() PolyNod

8、e *ha,*hb,*hc; PolyArray a=1.2,0,2.5,1,3.2,3,-2.5,5; PolyArray b=-1.2,0,2.5,1,3.2,3,2.5,5,5.4,10; CreateListR(ha,a,4); CreateListR(hb,b,5); printf( 原多项式A: );DispPoly(ha); printf( 原多项式B: );DispPoly(hb); Sort(ha); Sort(hb); printf( 有序多项式A: );DispPoly(ha); printf( 有序多项式B: );DispPoly(hb); Add(ha,hb,hc);

9、 printf( 多项式相加 : );DispPoly(hc); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - 实验 2 求解迷宫问题的所有路径及最短路径程序（堆栈）改进教材中3.2.4 节中的求解迷宫问题程序，要求输出如图所示的迷宫的所有路径，并求出最短路径成都及最短路径。/*文件名 :实验 2.cpp*/ #include #define M 6 /*行数 */ #define N 6 /*列数 */ #define M

10、axSize 100 /*栈最多元素个数*/ int mgM+1N+1= /*一个迷宫 ,其四周要加上均为1 的外框 */ 1,1,1,1,1,1, 1,0,0,0,1,1, 1,0,1,0,0,1, 1,0,0,0,1,1, 0 1 2 3 4 0 1 2 3 4 5 5 入口出口名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - 1,1,0,0,0,1, 1,1,1,1,1,1 ; struct int i;int j;int

11、 di; StackMaxSize,PathMaxSize; /*定义栈和存放最短路径的数组*/ int top=-1; /*栈指针 */ int count=1; /*路径数计数 */ int minlen=MaxSize; /*最短路径长度 */ void mgpath() /*路径为 :(1,1)-(M-2,N-2)*/ int i,j,di,find,k; top+; /*进栈 */ Stacktop.i=1; Stacktop.j=1; Stacktop.di=-1;mg11=-1; /*初始结点进栈 */ while (top-1) /*栈不空时循环 */ i=Stacktop.i

12、;j=Stacktop.j;di=Stacktop.di; if (i=M-2 & j=N-2) /*找到了出口 ,输出路径 */ printf(%4d: ,count+); for (k=0;k=top;k+) printf(%d,%d) ,Stackk.i,Stackk.j); if (k+1)%5=0) printf(nt); /*输出时每 5 个结点换一行*/ printf(n); if (top+1minlen) /*比较找最短路径*/ for (k=0;k=top;k+) Pathk=Stackk; minlen=top+1; mgStacktop.iStacktop.j=0; /

13、*让该位置变为其他路径可走结点*/ top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; find=0; while (di4 & find=0) /*找下一个可走结点*/ di+; switch(di) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - case 0:i=Stacktop.i-1;j=Stacktop.j;break; case 1:i=Stacktop.i;j=Sta

14、cktop.j+1;break; case 2:i=Stacktop.i+1;j=Stacktop.j;break; case 3:i=Stacktop.i,j=Stacktop.j-1;break; if (mgij=0) find=1; if (find=1) /*找到了下一个可走结点*/ Stacktop.di=di; /* 修改原栈顶元素的di 值*/ top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/*下一个可走结点进栈*/ mgij=-1; /*避免重复走到该结点*/ else /*没有路径可走 ,则退栈 */ mgStacktop.iS

15、tacktop.j=0; /*让该位置变为其他路径可走结点*/ top-; printf( 最短路径如下 :n); printf( 长度 : %dn,minlen); printf( 路径 : ); for (k=0;kminlen;k+) printf(%d,%d) ,Pathk.i,Pathk.j); if (k+1)%5=0) printf(nt); /*输出时每 5 个结点换一行*/ printf(n); void main() printf( 迷宫所有路径如下:n); mgpath(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

16、 - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - /实验 3 求一个串中出现的第一个最长重复字符串（串）编写一个程序，求串s 中出现的第一个最长重复字符串的下标和长度。*文件名 :实验 3.cpp*/ #include #include #include #define MaxSize 100 typedef struct char chMaxSize; int len; /*串长 */ SqString; extern void StrAssign(SqString &,char ); /*在 algo4-1.cpp 文

17、件中 */ extern void DispStr(SqString); SqString *MaxSubstr(SqString s) SqString *sp; int index=0,length=0,length1,i=0,j,k; while (is.len) j=i+1; while (jlength) /* 将较大长度者赋给index 与 length*/ index=i; length=length1; j+=length1; else j+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

18、 - - - - - 第 7 页，共 22 页 - - - - - - - - - i+; /*继续扫描第i 字符之后的字符*/ sp=(SqString *)malloc(sizeof(SqString); sp-len=length; for (i=0;ichi=s.chindex+i; return sp; void main() char strMaxSize; SqString s,*sp; printf( 输入串 :); gets(str); StrAssign(s,str); /*创建串 s*/ sp=MaxSubstr(s); printf( 求最长重复子串:n); print

19、f( 原串 : ); DispStr(s); printf( 最长重复子串 :); /*输出最长重复子串*/ DispStr(*sp); 实验 4 求解背包问题（递归）背包问题： 设有不同价值、 不同重量的物品n 件， 求从这 n 件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。编写一个程序求解背包问题。/*文件名 :实验 4.cpp*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - -

20、 - - #include #define N 100 int limitw; /*限制的总重量*/ int totv; /*全部物品的总价*/ int maxv; int optionN,copN; struct int weight; int value; aN; int n; /*物品种数次 */ void find(int i,int tw,int tv) int k; if (tw+ai.weight=limitw) copi=1; if (in-1) find(i+1,tw+ai.weight,tv); else for (k=0;kmaxv) if (in-1) find(i+1

21、,tw,tv-ai.value); else for (k=0;kn;k+) optionk=copk; maxv=tv-ai.value; void main() int k,w,v; printf( 物品种数 :); scanf(%d,&n); for (totv=0,k=0;kn;k+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - printf( 第 %d 种物品 (重量 ,价值 ):,k+1); scanf(%d,

22、%d,&w,&v); ak.weight=w; ak.value=v; totv+=v; printf( 背包所能承受的总重量:); scanf(%d,&limitw); maxv=0; for (k=0;kn;k+) copk=0; find(0,0,totv); printf( 最佳装填方案是:n); for (k=0;kn;k+) if (optionk) printf( 第%d 种物品 n,k+1); printf( 总价值 =%dn,maxv); 实验 5 求二叉树中从根节点到叶子节点的路径对一棵二叉树，编写程序完成下述功能：输出所有的叶子结点输出所有从叶子结点到根节点的路径输出上述

23、路径中的第一条最长的路径/*文件名 :实验 5.cpp*/ #include #include #define MaxSize 100 typedef char ElemType; typedef struct node ElemType data; /*数据元素 */ struct node *lchild; /*指向左孩子 */ struct node *rchild; /*指向右孩子 */ BTNode; extern void CreateBTNode(BTNode *&b,char *str); /* 在 algo7-1.cpp 文件中 */ 名师资料总结 - - -精品资料欢迎下载

24、 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - extern void DispBTNode(BTNode *b); void AllPath(BTNode *b) struct snode BTNode *node; /*存放当前结点指针*/ int parent; /*存放双亲结点在队列中的位置*/ QuMaxSize; /*定义顺序队列 */ int front,rear,p; /*定义队头和队尾指针*/ front=rear=-1; /*置队列为空队列*/

25、 rear+; Qurear.node=b; /*根结点指针进入队列*/ Qurear.parent=-1; /*根结点没有双亲结点*/ while (frontlchild=NULL & b-rchild=NULL) /*b 为叶子结点 */ printf( %c 到根结点路径 :,b-data); p=front; while (Qup.parent!=-1) printf(%c ,Qup.node-data); p=Qup.parent; printf(%cn,Qup.node-data); if (b-lchild!=NULL) /* 左孩子入队列 */ rear+; Qurear.n

26、ode=b-lchild; Qurear.parent=front; if (b-rchild!=NULL) /* 右孩子入队列 */ rear+; Qurear.node=b-rchild; Qurear.parent=front; void AllPath1(BTNode *b,ElemType path,int pathlen) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - int i; if (b!=NULL) i

27、f (b-lchild=NULL & b-rchild=NULL) /*b 为叶子结点 */ printf( %c 到根结点路径 : %c ,b-data,b-data); for (i=pathlen-1;i=0;i-) printf(%c ,pathi); printf(n); else pathpathlen=b-data; /*将当前结点放入路径中*/ pathlen+; /*路径长度增1*/ AllPath1(b-lchild,path,pathlen); /*递归扫描左子树*/ AllPath1(b-rchild,path,pathlen); /*递归扫描右子树*/ pathlen

28、-; /*恢复环境 */ void LongPath(BTNode *b,ElemType path,int pathlen,ElemType longpath,int &longpathlen) int i; if (b=NULL) if (pathlenlongpathlen) /* 若当前路径更长,将路径保存在longpath 中*/ for (i=pathlen-1;i=0;i-) longpathi=pathi; longpathlen=pathlen; else pathpathlen=b-data; /*将当前结点放入路径中*/ pathlen+; /*路径长度增1*/ Long

29、Path(b-lchild,path,pathlen,longpath,longpathlen); /*递归扫描左子树*/ LongPath(b-rchild,path,pathlen,longpath,longpathlen); /*递归扫描右子树*/ pathlen-; /*恢复环境 */ void DispLeaf(BTNode *b) if (b!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - if (

30、b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); void main() BTNode *b; ElemType pathMaxSize,longpathMaxSize; int i,longpathlen=0; CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(n 二叉树 b:);DispBTNode(b);printf(nn); printf( b 的叶子结点 :);DispLeaf(b);

31、printf(nn); printf( AllPath:n);AllPath(b);printf(n); printf( AllPath1:n);AllPath1(b,path,0);printf(n); LongPath(b,path,0,longpath,longpathlen); printf( 第一条最长路径长度:%dn,longpathlen); printf( 第一条最长路径:); for (i=longpathlen;i=0;i-) printf(%c ,longpathi); printf(nn); 实验 6 构造哈夫曼树构造一棵哈夫曼树， 输出对应的哈夫曼编码和平均查找长度。

32、并对下表所示的数据进行验证。单词Theofatoandinthatheisaton名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - 出现频度1192677541518462450242195190181174/*文件名 :实验 6.cpp*/ #include #include #define N 50 /*叶子结点数 */ #define M 2*N-1 /*树中结点总数 */ typedef struct char dat

33、a5; /*结点值 */ int weight; /*权重 */ int parent; /*双亲结点 */ int lchild; /*左孩子结点 */ int rchild; /*右孩子结点 */ HTNode; typedef struct char cdN; /*存放哈夫曼码 */ int start; HCode; void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) /*所有结点的相关域置初值-1*/ hti.parent=hti.lchild=hti.rchil

34、d=-1; for (i=n;i2*n-1;i+) /*构造哈夫曼树 */ min1=min2=32767; /*lnode 和 rnode 为最小权重的两个结点位置*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - lnode=rnode=-1; for (k=0;k=i-1;k+) if (htk.parent=-1) /*只在尚未构造二叉树的结点中查找*/ if (htk.weightmin1) min2=min1;

35、rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; printf(%dn,rnode); htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+)

36、/*根据哈夫曼树求哈夫曼编码*/ hc.start=n;c=i; f=hti.parent; while (f!=-1) /*循序直到树根结点*/ if (htf.lchild=c) /*处理左孩子结点*/ hc.cdhc.start-=0; else /*处理右孩子结点*/ hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /*start 指向哈夫曼编码最开始字符*/ hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) int i,k; int sum=0,m=0,j; 名师资料总结 - - -精品

37、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - printf( 输出哈夫曼编码:n); /* 输出哈夫曼编码*/ for (i=0;in;i+) j=0; printf( %s:t,hti.data); for (k=hcdi.start;k=n;k+) printf(%c,hcdi.cdk); j+; m+=hti.weight; sum+=hti.weight*j; printf(n); printf(n 平均长度 =%gn,1.0*sum/m);

38、 void main() int n=15,i; char *str=The,of,a,to,and,in,that,he,is,at,on,for,His,are,be; int fnum=1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123; HTNode htM; HCode hcdN; for (i=0;in;i+) strcpy(hti.data,stri); hti.weight=fnumi; printf(n); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(h

39、t,hcd,n); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - - - - - - 实验 7 采用克鲁斯卡尔算法求最小生成树编程序对无向带权图G 采用克鲁斯卡尔算法输出该图的最小生成树/*文件名 :实验 7.cpp*/ #include #include graph.h #define INF 32767 /*INF 表示 */ #define MAXE 100 /*最多边数 */ typedef struct int

40、 u; /*边的起始顶点 */ int v; /*边的终止顶点 */ int w; /*边的权值 */ Edge; extern void DispMat(MGraph); /*外部函数在algo9-1.cpp 中*/ void SortEdge(MGraph g,Edge E) /*从邻接矩阵产生权值递增的边集*/ int i,j,k=0; Edge temp; for (i=0;ig.vexnum;i+) for (j=0;jg.vexnum;j+) if (g.edgesijINF) Ek.u=i; Ek.v=j; Ek.w=g.edgesij; k+; for (i=1;i=0 & t

41、emp.wEj.w) Ej+1=Ej; /*将权值大于Ei.w 的记录后移 */ j-; Ej+1=temp; /*在 j+1 处插入 Ei*/ void Kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXE; for (i=0;in;i+) vseti=i; /*初始化辅助数组*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - - - - - - k=1; /*k

42、表示当前构造最小生成树的第几条边,初值为1*/ j=0; /*E 中边的下标 ,初值为 0*/ while (kn) /*生成的边数小于n 时循环 */ m1=Ej.u;m2=Ej.v; /*取一条边的头尾顶点*/ sn1=vsetm1;sn2=vsetm2; /* 分别得到两个顶点所属的集合编号*/ if (sn1!=sn2) /*两顶点属于不同的集合,该边是最小生成树的一条边*/ printf( (%d,%d):%dn,m1,m2,Ej.w); k+; /* 生成边数增1*/ for (i=0;in;i+) /* 两个集合统一编号*/ if (vseti=sn2) /*集合编号为sn2的改

43、为 sn1*/ vseti=sn1; j+; /*扫描下一条边*/ void main() int i,j,u=3; MGraph g; Edge EMAXE; int AMAXV11; g.vexnum=6;g.arcnum=10; for (i=0;ig.vexnum;i+) for (j=0;jg.vexnum;j+) Aij=INF; A01=5;A02=8;A03=7;A05=3; A12=4; A23=5;A25=9; A34=5; A45=1; for (i=0;ig.vexnum;i+) for (j=0;jg.vexnum;j+) Aji=Aij; for (i=0;ig.v

44、exnum;i+) /*建立图 9.15 的邻接矩阵 */ for (j=0;jg.vexnum;j+) g.edgesij=Aij; SortEdge(g,E); printf(n); printf( 图 G 的邻接矩阵 :n); DispMat(g); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - - - - printf(n); printf( 克鲁斯卡尔算法求解结果:n); Kruskal(E,g.vexnum,g.arcnu

45、m); printf(n); 实验 8 统计一个字符串中出现的字符及其次数编写一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后输出结果。 要求用一个二叉树保存处理结果，字符串中的每个不同的字符用树描述，每个结点包含4 个域，格式为：字符该字符的出现次数指向 ASCII 码小于该字符的左子树指针指向 ASCII 码大于该字符的右子树指针/*文件名 :实验 8.cpp*/ #include #include #include #define MAXWORD 100 typedef struct tnode char ch; /*字符 */ int count; /*出现次数 */ s

46、truct tnode *lchild,*rchild; BTree; void CreaTree(BTree *&p,char c) /*采用递归方式构造一棵二叉排序树*/ if (p=NULL) /*p 为 NULL, 则建立一个新结点*/ p=(BTree *)malloc(sizeof(BTree); p-ch=c; p-count=1; p-lchild=p-rchild=NULL; else if (c=p-ch) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页

47、，共 22 页 - - - - - - - - - p-count+; else if (cch) CreaTree(p-lchild,c); else CreaTree(p-rchild,c); void InOrder(BTree *p) /*中序遍历 BST*/ if (p!=NULL) InOrder(p-lchild); /*中序遍历左子树*/ printf( %c(%d)n,p-ch,p-count);/*访问根结点 */ InOrder(p-rchild); /*中序遍历右子树*/ void main() BTree *root=NULL; int i=0; char strMA

48、XWORD; printf(n); printf( 输入字符串 :); gets(str); while (stri!=0) CreaTree(root,stri); i+; printf( 字符及出现次数:n); InOrder(root); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - 实验 9 实现可变长度的字符串序列快速排序算法某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地

49、存储于唯一的字符数组中。 请改写快速排序算法，对这个字符串进行排序。并编写一个程序对以下数据进行排序。char S= “whileifif-elsedo-whileforcase” struct node int start; /该字符串在S 中的起始位置int length; /该字符串的长度A=0,5,5,2,7,7,14,8,22,3,25,4; /*文件名 :实验 9.cpp*/ #include #include #define MaxL 50 typedef struct node int start,length; RecType; int StringComp(char S,R

50、ecType A,int s1,RecType temp) char str1MaxL,str2MaxL; /*MaxL 是一个常量 ,指定最大的字符串长度*/ int i,j; for (j=0,i=As1.start;iAs1.start+As1.length;i+,j+) str1j=Si; /*将第 s1 个字符串复制到str1 中*/ str1j=0; /*字符串末尾置 0*/ for (j=0,i=temp.start;itemp.start+temp.length;i+,j+) str2j=Si; /*将 temp 所指的字符串复制到str2 中*/ str2j=0; /*字符串