1．排序算法比较**
利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。提示：用顺序存储结构。 a)需求分析：
1.建立顺序表结构体
2.建立插入排序函数，参数为顺序表指针。 3.建立选择排序函数，参数为顺序表指针。 4.建立起泡排序函数，参数为顺序表指针。
5.建立快速排序函数，参数为顺序表指针，起始数据位置，结束数据位置。 6.主函数中使用循环结构给顺序表每个元素随机赋值，排序前后测定时间，并统计。 b)概要设计
1.void SelectSort(SqList *L)
此函数主要比较两个关键字的大小，将元素从一个位置移动至另一个位置。 首先，在待排序序列中选择出最小的记录，然后将这个最小的数据元素与第一个记录交换，第一个记录到位，这叫做第一趟排序；
第二趟，就是从第二个记录到最后一个记录中选择最小的记录，之后将最小的记录与第二个记录交换，第二个记录到位；
以此类推，进行n-1趟，序列就有序了。 2.void InsertSort(SqList *L)
在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。
3.void QSort(SqList *L, int s, int t)
(1) 先从数列中取出一个数作为基准数(该记录称为枢轴)。
(2) 将比基准数大的数全放到它的右边，小于或等于基准数的全放到它的左边。
(3) 再对左右两部分重复第(2)步，直到各区间只有一个数，达到整个序列有序。
4. void BubbleSort(SqList *L)
每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 5. void main()
在主函数里建立顺序表。每次调用函数前使用循环结构使用随机函数一一赋值。在调用排序函数前后统计时间并输出所用时间。 c）详细设计 #include { KeyType key; }RecordType; typedef struct void SelectSort(SqList *L) { /*对顺序表L作简单选择排序*/ { RecordType r[MAXSIZE]; int length; }SqList; RecordType temp; for(int i=1; i { int j=i; for(int k=i+1; k<=L->length; k++) if(L->r[k].key if(i!=j) } { temp=L->r[j]; L->r[j]=L->r[i]; L->r[i]=temp; } void InsertSort(SqList *L) { /*对顺序表L作插入排序*/ for(int i=2; i<=L->length; ++i) if(L->r[i].key L->r[0]=L->r[i]; /*将待插入记录复制为哨兵*/ int j=i-1; while(L->r[0].key { L->r[j+1]=L->r[j]; j--; } /*记录后移*/ { L->r[j+1]=L->r[0]; /*插入到正确位置*/ } } int Partition(SqList *L,int low,int high) //快速排序 { */ } L->r[low]=L->r[0]; /*枢轴记录移到正确位置*/ L->r[0]=L->r[low]; /*将枢轴记录移至数组的闲置分量*/ int pivotkey=L->r[low].key; /*枢轴记录关键字*/ while(low --high; L->r[low++]=L->r[high]; /*将比枢轴记录小的记录移到低端*/ while(low ++low; /*将比枢轴记录大的记录移到高端 L->r[high--]=L->r[low]; } return low; /*返回枢轴位置*/ void QSort(SqList *L, int s, int t) { if(s QSort(L, pivotloc+1, t); /*对高端子序列递归排序*/ } } void BubbleSort(SqList *L) /*对记录数组L->r做起泡排序*/ { RecordType temp; bool change; int n=L->length; change=true; for(int i=1;i<=(n-1)&&change;++i) { change=false; /*在第i趟中先设置记录交换标识为FALSE */ for(int j=1; j<=n-i;++j) } void main() { SqList sq,*lp; sq.length=MAXSIZE-1; lp=&sq; for(int i=0;i temp=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=temp; change=true; { } double start,finish; sq.r[i].key=rand(); start=clock(); BubbleSort(lp); finish=clock(); printf(\"冒泡排序：%fseconds\\n\ for(int j=1;j printf(\"选择排序：%fseconds\\n\ sq.r[j].key=rand(); for(int k=1;k printf(\"插入排序：%fseconds\\n\ sq.r[k].key=rand(); } d）调试分析 for(int l=1;l printf(\"快速排序：%fseconds\\n\ sq.r[l].key=rand(); 每次使用30000个随机数，用四种排序方法分别排序，冒泡排序所耗费时间最长，快速排序所耗费时间最短。 时间复杂度分析： 插入排序T(n)=O(n²) 选择排序T(n)=O(n²) 起泡排序T(n)=O(n²) 快速排序：最好情况T(n)=O(nlog2n) 最坏情况T(n)=O(n²) 2. 查找算法测试** a)需求分析： 1.顺序表结构体 2.插入排序函数 3.顺序查找函数 4.折半查找函数 5.建立二叉树函数 6.二叉树中插入元素函数 7.二叉排序树查找函数 8.主函数 b)概要设计 1.void InsertSort(SqList *L) 在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。 2.int SearchSeq(SqList st, KeyType k) 用给定关键字与顺序表中各元素的关键字逐个比较，直到成功或失败(所有元素均不成功)。 3.int BinSearch(SqList st, KeyType key) 将表中间位置的关键字与查找关键字进行比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置的关键字大于查找关键字，则进一步查找前一子表，否则查找后一子表。重复以上过程，直到找到满足条件的记录，查找成功，或直到子表不存在为止，此时查找不成功。 4.建立二叉树函数 5.二叉树中插入元素函数 已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入过程可描述如下： ① 若二叉排序树是空树，则key成为二叉排序树的根。 ② 若二叉排序树是非空树，则将key与二叉排序树的根进行比较，如果key等于根结点的值，则停止插入；如果key小于根结点的值，则将key插入左子树；如果key大于根结点的值，则将key插入右子树。 6.二叉排序树查找函数 对二叉排序树进行查找的过程类似于在折半查找判定树上所进行的查找过程，其不同之处为：折半查找的判定树是静态的，二叉排序树是动态的。 7.主函数 建立顺序表，并使用循环结构给每个数随机赋值，之后对其排序，使用顺序查找和折半查找进行测试。创建二叉树进行查找某个值，进行判定是否存在。 c）详细设计 #include typedef struct { KeyType key; }RecordType; typedef struct { RecordType r[MAXSIZE]; int length; }SqList; void InsertSort(SqList *L) int SearchSeq(SqList st, KeyType k) /*在有序顺序表中查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0 */ { int i; st.r[0].key=k; i=st.length; while(st.r[i].key>k) i--; { /*对顺序表L作插入排序*/ for(int i=2; i<=L->length; ++i) } if(L->r[i].key L->r[0]=L->r[i]; /*将待插入记录复制为哨兵*/ int j=i-1; while(L->r[0].key { L->r[j+1]=L->r[j]; j--; } /*记录后移*/ { L->r[j+1]=L->r[0]; /*插入到正确位置*/ } } if(st.r[i].key==k) return(i); else return(0); int BinSearch(SqList st, KeyType key) { } typedef struct node { KeyType key; struct node *lchild, *rchild; int low, high, mid; low=1; high=st.length; /*置区间初值*/ while(low<=high) { } return(0); mid=(low+high)/2; if(key==st.r[mid].key) return(mid); /*找到待查元素*/ else if(key else low=mid+1; /*继续在后半区间进行查找*/ }BSTNode,*BSTree; void InsertBST(BSTree *bt,KeyType key) /*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/ { } void CreateBST(BSTree *bt) { int i=1; KeyType key; *bt=NULL; BSTree s; if(*bt==NULL) /*递归结束条件*/ { } else if(key<(*bt)->key) InsertBST(&((*bt)->lchild), key); /*将s插入左子树*/ s=(BSTree)malloc(sizeof(BSTNode)); s->key=key; s->lchild=NULL; s->rchild=NULL; *bt=s; else if(key>(*bt)->key) InsertBST(&((*bt)->rchild), key); /*将s插入右子树*/ while(i!=4444) /* ENDKEY为自定义常数，作为结束标识*/ { key=rand(); InsertBST(bt, key); i++; } } BSTree SearchBST(BSTree bt, KeyType key) { if(!bt) return NULL; else if(bt->key==key) return bt; else if(key return SearchBST(bt->lchild, key); /* else return SearchBST(bt->rchild, key); /*} void main() { SqList sq,*lp; lp=&sq; sq.length=MAXSIZE-1; for(int i=1;i 在右子树查找*/ } } InsertSort(lp); //对顺序表排序 printf(\"顺序查找的结果：第%d个位置\\n\printf(\"折半查找的结果：第%d个位置\\n\BSTree bst; CreateBST(&bst); if(SearchBST(bst,22)) printf(\"二叉排序树查找成功\\n\"); else printf(\"二叉排序树查找失败\\n\"); d）调试分析 使用顺序查找的方法查找2222的位置 使用折半查找的方法查找22222的位置 使用二叉排序树查找是否存在22. 平均查找长度分析： 顺序查找：（n+1)/2 折半查找：log2(n+1)-1 6. 建立二叉树，层序、先序遍历 a)需求分析： 1.先序创建二叉树 2.先序输出二叉树 先序遍历的递归过程为：若二叉树为空，遍历结束；否则， (1) 访问根结点， (2) 先序遍历根结点的左子树， (3) 先序遍历根结点的右子树。 3. 层次遍历二叉树T，从第一层开始，每层从左到右遍历 在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，依次执行下面操作： (1) 队列不空，出队列，取队头元素。 (2) 访问该元素所指结点。 (3) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 b)概要设计 1.void CreateBiTree(BiTree *T) 2.void PreOrder(BiTree T) 3.void LevelOrder(BiTree T) c）详细设计 #include typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //先序创建二叉树 void CreateBiTree(BiTree *T) { } //先序输出二叉树 void PreOrder(BiTree T) { if(T) { printf(\"%2c\PreOrder(T->lchild); char ch; ch=getchar(); if(ch=='#') else { } (*T)=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=ch; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); (*T)=NULL; } PreOrder(T->rchild); } //层次遍历二叉树T，从第一层开始，每层从左到右遍历 void LevelOrder(BiTree T) { } void main() { BiTree T=NULL; printf(\"创建一颗二叉树：\\n\"); CreateBiTree(&T); BiTree Queue[MAX],b; int front,rear; front=rear=0; if(T) { } Queue[rear++]=T; while(front!=rear) { } b=Queue[front++]; printf(\"%2c\ if(b->lchild!=NULL) Queue[rear++]=b->lchild; if(b->rchild!=NULL) Queue[rear++]=b->rchild; } printf(\"\\n先序遍历结果：\\n\"); PreOrder(T); printf(\"\\n层次遍历结果：\\n\"); LevelOrder(T); printf(\"\\n\"); d）调试分析 使用先序创建一颗二叉树 课设总结： （保存在word 文档中）总结可以包括 : 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 课设总结 收获：在本次课程设计中，通过对冒泡排序，快速排序，选择排序等排序方法的比较，不同查找方法的比较，体会到不同算法在处理数据量很大的程序时的差异。对二叉树的遍历程序，学习到存储与读取数据的方式多样。对于一个大程序，需要逐步写出，分块调试，将正确的程序一点一点添加在原有的程序上，才能避免出现大量错误而不知从何处修改。 遇到的问题：排序函数中的参数不唯一，有数组，也有指针，需要灵活运用，稍加修改使其统一化。给变量起名时没有特别精简明了，导致后边用的时候模糊不清其含义。对于数组的MAXSIZE与length的长度有些模糊，不能准确把握。解决时采用的办法为先使用较小的数进行调试，确认无误后再用较大数替换。 对数据结构这门课程的思考：数据结构这本书讲如何处理数据，随着学习的深入，对数据的存储结构和遍历方式的学习，对课本的整体内容有了更全面的认识。对于常见一些游戏数据处理的方法有了一些理解，递归算法使用栈的存储结构，对递归算法有了更明确的认识。学习这门课程，可以在编写程序时优化自己的程序，发现更多的改进地方，使其占用时间空间达到最小化。 因篇幅问题不能全部显示，请点此查看更多更全内容