《2022年晓庄-数据结构实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年晓庄-数据结构实验报告 .pdf（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构 (C 语言版 ) 实验报告学院信息工程学院班级15 计科 2 班学号15131019 姓名张旭指导教师曹晨名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 31 页 - - - - - - - - - 实验一线性表基本操作和简单程序1 实验目的（1）复习 Visual C+ 6.0上机调试程序的基本方法及C 语言编程；（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在链表存储结构上的程序设计方法。2 实验要求（1） 认真阅读和掌握和本实验相关的教材
2、内容。（2） 分别以头插法和尾插法建立两个数据域定义为整型的升序单链表，再将这两个有序链表合并成一个新的无重复元素的有序链表，最后可以根据输入的数据，先找到相应的结点，后删除之。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#include #include typedef struct node int data; struct node *next; node; node * qbuild(node *first) int i,n,a100; node *s; printf(输入 n:); scanf(%d,&n); first=(node*)m
3、alloc(sizeof(node); first-next=NULL; for(i=0;idata=ai; s-next=first-next; first-next=s; return first; node * hbuild(node *first) int i,n,a100; struct node *s,*r; printf(输入 n:); scanf(%d,&n); first=(node*)malloc(sizeof(node); r=first; for(i=0;idata=ai; r-next=s; r=s; r-next=NULL; return first; node *
4、 hebing(node *La,node *Lb) node *pa,*pb,*pc,*Lc; pa=La-next; pb=Lb-next; Lc=pc=La; while(pa & pb) if(pa-data data) pc-next =pa; pc=pa; pa=pa-next ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 31 页 - - - - - - - - - else if(pa-data pb-data) pc-next =pb; pc=pb
5、; pb=pb-next; else pc-next =pa; pc=pa; pa=pa-next ; pb=pb-next ; pc-next =pa?pa:pb; free(Lb); return Lc; node * shanchu(node *first,int i) node *p,*q; p=first-next; while(p) if(p-next )-data=i) q=p-next ; p-next =q-next; free(q); break; p=p-next; return first; void display(node *first) struct node *
6、p; p=first-next; while(p!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 31 页 - - - - - - - - - printf(%d ,p-data); p=p-next; printf(n); int main() int m; struct node *a,*b,*c; a=qbuild(a); printf(打印链表a：); display(a); b=hbuild(b); printf(打印链表b：); display(
7、b); c=hebing(a,b); printf(打印链表c：); display(c); printf(输入删除的数m:); scanf(%d,&m); c=shanchu(c,m); printf(打印删除后的链表c:); display(c); return 0; 4 实验结果输入 n:5 输入 a0:9 输入 a1:5 输入 a2:4 输入 a3:3 输入 a4:1 打印链表a：1 3 4 5 9 输入 n:5 输入 a0:1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
8、 5 页，共 31 页 - - - - - - - - - 输入 a1:3 输入 a2:4 输入 a3:6 输入 a4:8 打印链表b：1 3 4 6 8 打印链表c：1 3 4 5 6 8 9 输入删除的数m:5 打印删除后的链表c:1 3 4 6 8 9 - Process exited after 32.78 seconds with return value 0 请按任意键继续. . . 5 心得体会本次实验是以后实验的基础，是数据结构中最基本的东西。通过本次试验，我对之前所学习的C 语言知识要点有了进一步实践，加深了我对C 语言的认识。名师资料总结 - - -精品资料欢迎下载 - -
9、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 31 页 - - - - - - - - - 实验二利用栈和队列判断字符串是否是回文1 实验目的（1）深入了解栈和循环队列的特性、栈和递归程序设计的关系。（2）要求能灵活运用两种结构来解决有关的应用问题。y2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 假设正读和反读都相同的字符序列为“回文”，例如，abba和 abcba是回文，abcde 和 ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。（3） 上机运行程序。（
10、4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#include #include #define m 100 typedef struct /定义栈 char datam; int top; zhan; void cshz(zhan *s) /初始化栈 s-top=0; int pdzk(zhan *s) /判断栈是否为空 if(s-top=0) return 0; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 31 页 - - - - -
11、 - - - - return 1; void ruzhan(zhan *s,char x) /入栈 if(s-top=m) printf(栈空 n); else s-data+s-top=x; char chuzhan(zhan *s) /出栈 char y; if(s-top=0) printf(栈空 n); return 0; else y=s-datas-top; s-top=s-top-1; return y; typedef struct /定义队列 char datam; int front; int rear; dui; void cshdl(dui *q) /初始化队列 q-
12、front=q-rear=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 31 页 - - - - - - - - - void rudui(dui *q,char e) /入队 if(q-rear+1)%m=q-front) printf(队列为空 n); else q-dataq-rear=e; q-rear=(q-rear+1); char chudui(dui *q) /出对 char f; if(q-front=q-rear) printf(队列为空 n)
13、; return 0; else f=q-dataq-front; q-front=(q-front+1); return f; int main() char c; int y=0; zhan *s=(zhan *)malloc(sizeof(zhan); dui *q=(dui *)malloc(sizeof(dui); cshz(s); cshdl(q); printf(输入一个字符串:n); while(c=getchar()!=) ruzhan(s,c); rudui(q,c); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
14、 - - 名师精心整理 - - - - - - - 第 9 页，共 31 页 - - - - - - - - - while(pdzk(s) if(chuzhan(s)=chudui(q) y=1; continue; else y=0; break; if(y=1) printf(此字符串为回文n); else printf(此字符串不是回文n); return 0; 4 实验结果输入输出示例：1. 输入一个字符串: abbabba 此字符串为回文- Process exited after 8.796 seconds with return value 0 请按任意键继续. . . 2.
15、输入一个字符串: abbabb 此字符串不是回文- Process exited after 7.968 seconds with return value 0 请按任意键继续. . 5 心得体会名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 31 页 - - - - - - - - - 利用栈和队列进行对回文数的检测，看似简单的问题，却变得更加复杂，但是却给了我们一个深入了解栈和队列的机会，对于其中的知识也相对掌握了。这也说明了实践对课堂上学到的知识有着巩固和加深的作
16、用，想要学好数据结构，不能怕麻烦。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 31 页 - - - - - - - - - 实验三三元组表的转置1 实验目的（1）掌握稀疏矩阵的存储方法和基本运算。（2）掌握三元组表转置的程序设计方法。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 输入一个三元组表，先输出其矩阵形态，然后对其进行转置并输出转置后的矩阵。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#inc
17、lude #define MAXSIZE 100 typedef struct /定义三元组 int hang,lie; int zhi; SAN; typedef struct SAN dataMAXSIZE; int mu,nu,tu; SANYUAN; void zhuanzhi(SANYUAN M,SANYUAN *T) /对三元组进行转置 int col,p,q,t; int numMAXSIZE,cpotMAXSIZE; T-mu=M.nu;T-nu=M.mu;T-tu=M.tu; if(T-tu) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
18、- - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 31 页 - - - - - - - - - for(col=1;col=M.nu;+col) numcol=0; for(t=1;t=M.tu;+t) +numM.datat.lie; cpot1=1; for(col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;pdataq.hang=M.datap.lie; T-dataq.lie=M.datap.hang; T-dataq.zhi=M.datap.zhi; +cpotcol; void
19、 output(SANYUAN *M) /输出三元组 int i,j; int t=1; for(i=1;imu;i+) for(j=1;jnu;j+) if(M-datat.hang=i&M-datat.lie=j) printf(%d ,M-datat.zhi); t+; else printf(0 ); printf(n); int main() SANYUAN A,T;int k; printf(输入矩阵大小n); printf(行： );scanf(%d,&A.mu); printf(列： );scanf(%d,&A.nu); 名师资料总结 - - -精品资料欢迎下载 - - - -
20、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 31 页 - - - - - - - - - printf(非零元素个数:);scanf(%d,&A.tu); printf(输入三元组表:n); /顺序输入三元组 for(k=1;k=A.tu;k+) scanf(%d %d %d,&A.datak.hang,&A.datak.lie,&A.datak.zhi); printf(原矩阵 n); output(&A); zhuanzhi(A,&T); printf(转置后的矩阵：n); output(&T); return 0;
21、 4 实验结果输入矩阵大小行： 8 列： 8 非零元素个数:5 输入三元组表: 1 2 3 2 3 4 3 4 5 5 6 7 7 8 9 原矩阵0 3 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 转置后的矩阵：0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0
22、0 0 0 0 0 0 0 0 0 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 31 页 - - - - - - - - - 0 0 0 0 0 0 9 0 - Process exited after 24.57 seconds with return value 0 请按任意键继续. . . 5 心得体会本次试验相对简单一点，容易理解，只要掌握了三元组表的知识，就完全可以解决。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
23、- - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 31 页 - - - - - - - - - 实验四二叉树的遍历1 实验目的（1） 进一步掌握指针变量的用途和程序设计方法。（2） 掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。（3） 掌握构造二叉树的基本方法。（4） 掌握二叉树遍历算法的设计方法。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 利用二叉链表建立一棵二叉树，分别采用先序、中序和后序遍历该二叉树，并输出遍历的序列。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#i
24、nclude #include #define MAX 100 typedef struct BiTNode / 定义二叉树 char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; void CreateBiTree(BiTree *T) char data; /按先序次序输入二叉树中结点的值（一个字符），#表示空树 scanf(%c,&data); if(data = #) *T = NULL; else *T = (BiTree)malloc(sizeof(BiTNode); 名师资料总结 - - -精品资料欢迎下载 - -
25、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 31 页 - - - - - - - - - / 生成根结点 (*T)-data = data; / 构造左子树 CreateBiTree(&(*T)-lchild); / 构造右子树 CreateBiTree(&(*T)-rchild); void Visit(BiTree T) / 输出 if(T-data != #) printf(%c ,T-data); void PreOrder(BiTree T) / 先序遍历 if(T != NULL) / 访问根节点 Vi
26、sit(T); / 访问左子结点 PreOrder(T-lchild); / 访问右子结点 PreOrder(T-rchild); void InOrder(BiTree T) / 中序遍历 if(T != NULL) / 访问左子结点 InOrder(T-lchild); / 访问根节点 Visit(T); / 访问右子结点 InOrder(T-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 31 页 - - - - - - - - - void P
27、ostOrder(BiTree T) /后序遍历 if(T != NULL) / 访问左子结点 PostOrder(T-lchild); / 访问右子结点 PostOrder(T-rchild); / 访问根节点 Visit(T); int main() BiTree T; printf(以 #代表空先序遍历n 输入二叉树：); CreateBiTree(&T); printf(先序遍历： n); PreOrder(T); printf(n); printf(中序遍历： n); InOrder(T); printf(n); printf(后序遍历： n); PostOrder(T); retu
28、rn 0; 4 实验结果以#代表空先序遍历输入二叉树：ab#c# 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 31 页 - - - - - - - - - 先序遍历：a b c 中序遍历：b a c 后序遍历：b c a - Process exited after 10.89 seconds with return value 0 请按任意键继续. . . 5 心得体会这次的试验让我对二叉树有了更进一步的理解，对二叉树的操作也更加熟悉。本次试验是对二叉树进行建立，
29、并掌握先序遍历，中序遍历和后续遍历，虽然用的是递归的方法相对简单一点， 但是理解起来还是有点困难。二叉树是数据结构中很重要的一部分知识，也是数据结构的重难点，我相信在以后的学习中还会遇到，而我更要进行更深入的学习。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 31 页 - - - - - - - - - 实验五图的遍历1 实验目的（1）加深理解图的非线性结构特点，灵活运用图的存储结构、图的深度优先搜索和广度优先搜索来解决有关应用问题。（2）加深递归程序设计的训练。（3
30、）注重提高关于模型选择、算法设计和分析方面的能力。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 利用邻接矩阵或邻接表存储一张图，分别采用图的深度优先搜索和广度优先搜索遍历该图，并输出遍历结果。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#include #include #define MAXVEX 100 /最大顶点数#define INFINITY 65535 /用 65535 来代表无穷大int visitedMAXVEX=0; typedef struct char vexsMAXVEX; / 顶点表 int arcMA
31、XVEXMAXVEX; /邻接矩阵，可看作边 int numVertexes, numEdges; / 图中当前的顶点数和边数Graph; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 31 页 - - - - - - - - - void CreateGraph(Graph *g) int i,j,k,w,t; printf(输入顶点数，边数和t （中间用空格）:); scanf(%d %d %d, &(g-numVertexes), &(g-numEdges),&
32、t); printf(n); for(i=1;inumVertexes;i+) getchar(); printf(输 入 第 %d 顶 点 信 息vexs%d=,i,i); scanf(%c,&(g-vexsi); printf(n); for(i=1;inumVertexes;i+) for(j=1;jnumVertexes;j+) if (t2) g-arcij = INFINITY; else g-arcij=0; for(k=1;knumEdges;k+) printf(输入 i j（中间用空格）:); scanf(%d %d,&i,&j); if(ig-numVertexes |j
33、g-numVertexes) exit(0); if(t2) printf(输入 w:); scanf(%d,&w); g-arcij=w; if(t=3) g-arcji=w; else g-arcij=1; if (t=1) g-arcji=1; printf(n); printf(输出邻接矩阵 :n); for(i=1;inumVertexes ;i+) for(j=1;jnumVertexes ;j+) printf(%8d,g-arcij); if(t2&g-arcij=65535) g-arcij=0; else if(t2&g-arcij!=65535) 名师资料总结 - - -
34、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 31 页 - - - - - - - - - g-arcij=1; printf(n); void dfs (Graph g,int i) /广度优先搜索，从顶点i 开始遍历 int j; printf(%d-,i); /输出访问顶点 visitedi=1; / 全局数组访问标记置1 表示已经访问 for(j=1; j,i); visitedi=1 ; r+; qr=i ; while (fr) f+; i=qf ; for (j=1; j,j)
35、; ; visitedj=1 ; r+; qr=j ; int main() Graph g; int i; printf(t为 14, 分别表示无向图、有向图、带权无向图、带权有向图n); CreateGraph(&g); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 31 页 - - - - - - - - - printf(n输入 i:); scanf(%d,&i); printf(n深度优先搜索遍历：); dfs (g,i); printf(NULLn); p
36、rintf(广度优先搜索遍历：); bfs (g,i); printf(NULLn); return 0; 4 实验结果1. 无向图t 为 14, 分别表示无向图、有向图、带权无向图、带权有向图输入顶点数，边数和t （中间用空格）:8 10 1 输入第 1 顶点信息vexs1=1 输入第 2 顶点信息vexs2=2 输入第 3 顶点信息vexs3=3 输入第 4 顶点信息vexs4=4 输入第 5 顶点信息vexs5=5 输入第 6 顶点信息vexs6=6 输入第 7 顶点信息vexs7=7 输入第 8 顶点信息vexs8=8 输入 i j（中间用空格）:1 2 输入 i j（中间用空格）:1
37、 3 输入 i j（中间用空格）:2 4 输入 i j（中间用空格）:2 5 输入 i j（中间用空格）:3 6 输入 i j（中间用空格）:3 7 输入 i j（中间用空格）:4 8 输入 i j（中间用空格）:5 8 输入 i j（中间用空格）:6 8 输入 i j（中间用空格）:7 8 输出邻接矩阵: 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2
38、3 页，共 31 页 - - - - - - - - - 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 输入 i:1 深度优先搜索遍历：1-2-4-8-5-6-3-7-NULL 广度优先搜索遍历：1-2-3-4-5-6-7-8-NULL - Process exited after 74.92 seconds with return value 0 请按任意键继续. . . 2. 带权无向图t 为 14, 分别表示无向图、有向图、带权无向图、带权有向图输入顶点数，边数和t （中间用空格）:5 8 3 输入第 1
39、顶点信息 vexs1=1 输入第 2 顶点信息vexs2=2 输入第 3 顶点信息vexs3=3 输入第 4 顶点信息vexs4=4 输入第 5 顶点信息vexs5=5 输入 i j（中间用空格）:1 2 输入 w:6 输入 i j（中间用空格）:1 3 输入 w:1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 31 页 - - - - - - - - - 输入 i j（中间用空格）:1 5 输入 w:3 输入 i j（中间用空格）:2 5 输入 w:9 输入 i
40、j（中间用空格）:2 4 输入 w:8 输入 i j（中间用空格）:4 5 输入 w:7 输入 i j（中间用空格）:4 3 输入 w:2 输入 i j（中间用空格）:3 5 输入 w:4 输出邻接矩阵: 65535 6 1 65535 3 6 65535 65535 8 9 1 65535 65535 2 4 65535 8 2 65535 7 3 9 4 7 65535 输入 i:3 深度优先搜索遍历：3-1-2-4-5-NULL 广度优先搜索遍历：3-1-4-5-2-NULL - Process exited after 42.63 seconds with return value 0
41、 请按任意键继续. . . 5 心得体会图在数据结构中也是一个重要的知识点，是一种较线性表和树更加复杂的数据结构。本次试验相对来说比较有难度，也是写了很长时间才写完，掌握了对各种图的构建和遍历。虽然也做出了结果，但掌握的还不够充分，不能很好的理解和掌握。概念性的东西非常多，还得加名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 31 页 - - - - - - - - - 紧学习名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -
42、- - - - - 名师精心整理 - - - - - - - 第 26 页，共 31 页 - - - - - - - - - 实验六查找和排序1 实验目的（1）提高关于查找、排序算法的运用、比较与分析能力。（2）顺序查找与二分查找的比较，ASL 的分析。（3）直接插入排序、冒泡排序、选择排序（三选一）与快速排序的分析比较。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 自举一个数列，对其进行排序和查找，分析算法的优缺点。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3 程序代码#include #define MAXSIZE 20 /* 一个用
43、作示例的小顺序表的最大长度 */ #define N 10 typedef struct int key; /* 关键字项 */ RedType; /* 记录类型 */ typedef struct RedType rMAXSIZE+1; /* r0闲置或用作哨兵单元 */ int length; /* 顺序表长度 */ SqList; /* 顺序表类型 */ void InsertSort(SqList *L) /* 对顺序表 L 作直接插入排序。算法10.1 */ int i,j; for(i=2;i=(*L).length;+i) if (*L).ri.key(*L).ri-1.key)
44、 /* ,需将 L.ri插入有序子表 */ (*L).r0=(*L).ri; /* 复制为哨兵 */ for(j=i-1;(*L).r0.key(*L).rj.key);-j) (*L).rj+1=(*L).rj; /* 记录后移 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 31 页 - - - - - - - - - (*L).rj+1=(*L).r0; /* 插入到正确位置 */ int SelectMinKey(SqList L,int i) /* 返回
45、在 L.ri.L.length中 key 最小的记录的序号 */ int min; int j,k; k=i; /* 设第 i 个为最小 */ min=L.ri.key; for(j=i+1;j=L.length;j+) if(L.rj.keymin) /* 找到更小的 */ k=j; min=L.rj.key; return k; void SelectSort(SqList *L) /* 对顺序表 L 作简单选择排序。算法10.9 */ int i,j; RedType t; for(i=1;i0)&(flag=1) flag=0; for(j=1;j(*L).rj+1.key) 名师资料
46、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 31 页 - - - - - - - - - flag=1; x=(*L).rj; (*L).rj=(*L).rj+1; (*L).rj+1=x; m-; int Partition(SqList *L,int low,int high) /* 交换顺序表L 中子表 L.rlow.high的记录，使枢轴记录到位， */ /* 并返回其所在位置，此时在它之前 ( 后) 的记录均不大 ( 小) 于它。算法 10.6(a) */ Red
47、Type t; int pivotkey; pivotkey=(*L).rlow.key; /* 用子表的第一个记录作枢轴记录 */ while(lowhigh) /* 从表的两端交替地向中间扫描 */ while(low=pivotkey) -high; t=(*L).rlow; /* 将比枢轴记录小的记录交换到低端 */ (*L).rlow=(*L).rhigh; (*L).rhigh=t; while(lowhigh&(*L).rlow.key=pivotkey) +low; t=(*L).rlow; /* 将比枢轴记录大的记录交换到高端 */ (*L).rlow=(*L).rhigh;
48、 (*L).rhigh=t; return low; /* 返回枢轴所在位置 */ void QSort(SqList *L,int low,int high) /* 对顺序表 L 中的子序列L.rlow.high作快速排序。算法10.7 */ int pivotloc; if(lowhigh) /* 长度大于 1 */ pivotloc=Partition(L,low,high); /* 将 L.rlow.high一分为二 */ QSort(L,low,pivotloc-1); /* 对低子表递归排序，pivotloc是枢轴位置 */ QSort(L,pivotloc+1,high); /*
49、 对高子表递归排序 */ void QuickSort(SqList *L) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 31 页 - - - - - - - - - /* 对顺序表 L 作快速排序。算法10.8 */ 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); int main() printf
50、(输入%d个数n,N); RedType dN=0; SqList L1,L2,L3,L4; int i; for(i=0;iN;i+) /* 给 l1.r赋值 */ printf(输入 d%d=,i); scanf(%d,&di); L1.ri+1=di; L1.length=N; L4=L3=L2=L1; printf(排序前 :n); print(L1); InsertSort(&L1); printf(直接插入排序后 :n); print(L1); printf(简单选择排序后 :n); SelectSort(&L2); print(L2); printf(冒泡排序后 :n); bub