《数据结构》课程设计报告

计算机与信息工程系

20##年 1 月  2日

目录

1、问题描述………………………………………

2、设计思路(数学模型的选择) ……………

3、二叉排序树和平衡二叉树定义…………………………

4、程序清单……………………………

5.程序功能说明……………………………

5.运行与调试分析………………………

    6.总结…………………………………

1.问题描述

输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树，运行并进行调试。

2.设计思路

平衡二叉树的调整方法

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：

⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；

⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；

⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

3.二叉排序树和平衡二叉树定义

二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）（3）左、右子树也分别为二叉排序树；

平衡二叉树

平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称AVL树，它或者是一棵空树，或者是具有以下性质的二叉；它的左子树右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是－1、0或1。

4.程序功能说明

void preorder(bintree t)/*前序遍历*/

void midorder(bintree t)/*中序遍历*/

lastorder(bintree t)/*后序遍历

{bintree a;int j,k;clrscr();textcolor(2);

printf("**************************欢迎您使用本二叉树操作系统**************************\n");

printf("建造一棵二叉树请您输入各个结点的元素值,()表示一个空格键:\n");

printf("输入示例:abc()()de()g()()f()()()回车:\n");a=createbitree();

printf("您输入的二叉数嵌套法表示如下:\n");printree(a);printf("\n");

printf("树的深度为:\n");

j=treedepth(a);printf("%d\n",j);

printf("二叉数的叶子接点个数为:\n");

k=treeleaf(a);printf("%d\n",k);

printf("您所输入的二叉树的前序遍历顺序输出如下:\n");

if(!a) printf("二叉树为空\n");

else{preorder(a);printf("\n");}

printf("您所输入的二叉树的中序遍历顺序如下输出:\n");

if(!a)  printf("二叉树为空\n");else{

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

printf("您所输入的二叉树的后序遍历顺序输出如下:\n");

if(!a)  printf("二叉树为空\n");

else{lastorder(a);printf("\n");}

printf("您所输入的二叉树的层次顺序遍历输出如下:\n");

 if(!a)  printf("二叉树为空\n");

else{

 translevel(a);}}

5.程序清单

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#define NULL 0

int leftdep,rightdep;

typedef struct bitnode

{char data;struct bitnode *lchild,*rchild;}

bintnode,*bintree;bintree createbitree()

{bintree t;char x;scanf("%c",&x);

if(x==' ') t=NULL;

else{t=(bintnode *)malloc(sizeof(bintnode));

 t->data=x;

 t->lchild=createbitree();

 t->rchild=createbitree();

}return(t);}

void preorder(bintree t)/*前序遍历*/

{if(t)

{printf("%2c",t->data);

preorder(t->lchild);

preorder(t->rchild);}}

void midorder(bintree t)/*中序遍历*/

{if(t)

{

midorder(t->lchild);

  printf("%2c",t->data);

  midorder(t->rchild);}}

void printree(bintree t)

{if(t!=NULL)

{printf("%c",t->data);

 if(t->lchild!=NULL||t->rchild!=NULL)

 {printf("(");printree(t->lchild);

  if(t->rchild!=NULL) printf(",");

  printree(t->rchild); printf(")");}}}

int treedepth(bintree t)

 {if(t==NULL) return 0;

  else{leftdep=treedepth(t->lchild);

  rightdep=treedepth(t->rchild);

  if(leftdep>rightdep)return (leftdep+1);

elsereturn(rightdep+1);}}

int treeleaf(bintree t)

{if(t==NULL)return0;else if(t->lchild==NULL&&t->rchild==NULL)

 return1;else return(treeleaf(t->lchild)+treeleaf(t->rchild));}void lastorder(bintree t)/*后序遍历*/{if(t){lastorder(t->lchild);lastorder(t->rchild);printf("%2c",t->data);}}

void translevel(bintree t)

{struct bitnode{bintree vec[30];

 int f,r;}q;q.f=0;q.r=0;if(t!=NULL)

 printf("%2c",t->data);

 q.vec[q.r]=t;q.r=q.r+1;

 while (q.f<q.r)

 {t=q.vec[q.f];q.f=q.f+1;

  if(t->lchild!=NULL)

  {printf("%2c",t->lchild->data);

  q.vec[q.r]=t->lchild; q.r=q.r+1;}

if(t->rchild!=NULL)

 {printf("%2c",t->rchild->data);

  q.vec[q.r]=t->rchild;

  q.r=q.r+1;}} printf("\n");}

main(){bintree a;int j,k;clrscr();textcolor(2);

printf("**************************欢迎您使用本二叉树操作系统**************************\n");

printf("建造一棵二叉树请您输入各个结点的元素值,()表示一个空格键:\n");

printf("输入示例:abc()()de()g()()f()()()回车:\n");a=createbitree();

printf("您输入的二叉数嵌套法表示如下:\n");printree(a);printf("\n");

printf("树的深度为:\n");

j=treedepth(a);printf("%d\n",j);

printf("二叉数的叶子接点个数为:\n");

k=treeleaf(a);printf("%d\n",k);

printf("您所输入的二叉树的前序遍历顺序输出如下:\n");

if(!a) printf("二叉树为空\n");

else{preorder(a);printf("\n");}

printf("您所输入的二叉树的中序遍历顺序如下输出:\n");

if(!a)  printf("二叉树为空\n");else{

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

printf("您所输入的二叉树的后序遍历顺序输出如下:\n");

if(!a)  printf("二叉树为空\n");

else{lastorder(a);printf("\n");}

printf("您所输入的二叉树的层次顺序遍历输出如下:\n");

 if(!a)  printf("二叉树为空\n");

else{

 translevel(a);}}

5.运行与调试分析

输入几个数据进行运行调试，观察运行结果是否达到预期的目的，运行中可能出现逻辑错误，输入数据合适与否以及相关细节都可能会影响程序的运行，可以试着变换相关数据对二叉排序树和平衡二叉树的转换进行调整，分析实验数据对转换的影响。了解二叉排序树和平衡二叉树的结构和特点，分析运行调试可能出现的问题，可以试着找出这些问题，并改变相关数据试着验证自己的设想。

7.总结

   想起老师的“难事破与易”，再复杂的事折成一个个简单的小部分，逐个击破，然后再凑起来，复杂的事也就变得简单了。在编程时尽可能使用全局变量，避免局部变量的使用。还有就是编程基础还要扎实起来。

 

第二篇：《数据结构》课程设计报告

课程设计(论文)

题 目 名 称 几种常见的排序算法的实现与性能分析 课 程 名 称 数据结构课程设计 学 生 姓 名 龚 云 学 号 0841330022 系 、专 业 信息工程系、电气信息类（信息类） 指 导 教 师

20xx年 1 月 3 日

摘 要

设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数，通过在主函数中调用自定义函数，实现其功能，最后输出相应算法的比较次数和移动次数。从而直观的判断各内部排序算法性能的优劣。

关键词：内部排序；直观；比较次数；移动次数

目 录

1 问题描述 ................................................................... 错误！未定义书签。 2 需求分析 ................................................................... 错误！未定义书签。

3 概要设计 ................................................................................................... 4

3. 1抽象数据类型定义............................................................................ 4

3. 2模块划分........................................................................................... 5

4 详细设计 .................................................................................................. 6

4. 1数据类型的定义 ............................................................................... 6

4. 2主要模块的算法描述 ........................................................................ 6

5 测试分析 ................................................................................................... 9

6 课程设计的总结与体会........................................................................... 10

参考文献..................................................................................................... 11 附录（源程序清单） .................................................... 错误！未定义书签。

1 问题描述

设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于10，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。

2 需求分析

（1）用数组S来存放系统随机产生的10个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。

（2）利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。

（3）在主函数中调用用户自定义函数，输出比较结果。

（4）本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。 3 概要设计

3．1抽象数据类型定义

排序数据类型定义：

ADT paixu{

数据对象：D={aij|aij属于{1，2，3…},i,j>0}

数据关系：R={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}

基本操作：

Insertsort();

初始条件：数组已经存在。

操作过程：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。

Bubblesort();

初始条件：数组已经存在。

操作过程：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，知道全部满足顺序要求为止。

Shellsort();

初始条件：数组已经存在。

操作过程：先取定一个正整数d1<n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行插入排序，然后取d2<d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。 Selectsort();

初始条件：数组已经存在。

操作过程：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已经排序的记录序列的最好，直到全部排完。

Heap();

初始条件：数组已经存在。

操作过程：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。

QuickSort(int low,int high)；

初始条件：数组已经存在。

操作过程：在待排序的n个记录中任取一个记录，以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的放在一边，大的放另一边，并把该记录放在中间，然后重复至完成。

}ADT 排序

3．2模块划分

本程序包括两个模块：

（1）主程序模块

void main()

{

初始化；

随机数的产生；

调用子函数

}；

（2）子函数模块：实现各种排序的抽象数据类型。 4 详细设计

4．1数据类型的定义

(1)直接插入排序类型：

void Insertsort();

(2)冒泡排序类型：

void Bubblesort();

(3)快速排序类型：

void QuickSort(int low,int high);

(4)希尔排序类型：

void Shellsort();

(5)选择排序类型：

void Selectsort();

(6)堆排序类型：

void Heap();

4．2主要模块的算法描述

以下是源程序的流程图：

图4.21

图

4.22

图4.23 5 测试分析

6 课程设计的总结与体会

看到这个课程设计的题目的时候，我觉得很亲切。因为这个学期的第七章我们学了几种内部排序方法并进行了比较。对这几种算法的比较主要是通过其算法的时间复杂度以及其算法是否稳定。但是我们所进行的比较主要是通过主观比较

而并没有编写相应的算法。而此次课程设计正好为我们提供了这样一个平台。一个排序的关键字比较次数和移动次数的算法很容易实现。但是如何将多个内部排序关键字比较次数和移动次数的算法实现并得到美观的结果则成了我们此次课程实际的难点和重点。我初次自主完成改课题源程序的时候并没有考虑到其输出结果的美观性，经过黄老师的指点后。我联想到了排序子系统的菜单，并插入到了实现该课程设计的算法中。但是在后来的运行中却出现了某一排序的结果不正确的情况。算法对应程序，算法结果不正确,肯定是程序没有正确体现算法思想。在黄老师的帮助之下，我们做了相应的修改，最后终于顺利的完成了此次源程序的编写。在数据结构这个奇妙的世界容不得有一点小小的错误，否则将前功尽弃。因此在以后的学习当中我一定会认真仔细的学好每一个环节。而此次课程设计也让我看到了数据结构这门学科的魅力所在，我甚至喜欢上了这门学科。此次课程设计得以顺利的完成，不但与我们个人及小组其他成员的努力息息相关，而且指导老师黄老师对我们的帮助也让我们受益匪浅。再次我向黄同成老师表示深深的谢意。谢谢您,黄老师！

参考文献

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2002

[2] 刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003

[3] 李春葆．数据结构习题与解析（C语言篇）[M]．北京：清华大学出版社，2000

附录（源程序清单）

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #define L 10

#define FALSE 0 #define TRUE 1 /*typedef struct {

int key; char otherinfo; }RecType;*/

//typedef RecType Seqlist[L+1]; int s[100],R[100]; int num;

int times=0,changes=0; //Seqlist R;

void Insertsort(); void Bubblesort();

void QuickSort(int low,int high); void Shellsort(); void Selectsort(); void Heap();

int Partition();

void main()

{

//Seqlist S; int i,k; char ch1,ch2,q;

printf("产生10个随机数：\n");

srand((unsigned)time(NULL));

for(i=1;i<=L;i++)

{

s[i]=rand()%100;

}

for(i=1;i<=L;i++)

{

printf("%4d",s[i]);

}

printf("\n\t排序数据已经输入完毕！");

for(i=1;i<=L;i++)

R[i]=s[i];

ch1='y';

while (ch1=='y'||ch1=='Y') { printf("\n\n\n\n\n\t\t\t排 序 性 能 分 析\n");

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

printf("\t\t* 1--------直接插入排序 ---------*\n"); printf("\t\t* 2--------希 尔 排 序 ---------*\n"); printf("\t\t* 3--------冒 泡 排 序 ---------*\n"); printf("\t\t* 4--------快 速 排 序----------*\n"); printf("\t\t* 5--------选 择 排 序 ---------*\n"); printf("\t\t* 6--------堆 排 序----------*\n"); printf("\t\t* 0--------返 回----------*\n");

printf("\t\t***************************************\n"); printf("\t\t请选择菜单号（0---6）:"); scanf("%c",&ch2);getchar(); for(i=1;i<=L;i++) R[i]=s[i]; switch(ch2)

{ case '1':Insertsort();break; case '2':Shellsort();break; case '3':Bubblesort();break;

case '4':

printf("\n\t\t尚未排序的数据为（回车继续）："); for(k=1;k<=L;k++) printf("%5d",R[k]); getchar();printf("\n"); num=0;QuickSort(1,L); break; case '5':Selectsort();break; case '6':Heap();break; } if(ch2!='0') { if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8') printf("\n\t排序演示输出完毕！\n"); case '0':ch1='n';break; default:printf("\t\t输入错误！请重新输入！\n\t\t"); printf("\n\t请按回车键返回主菜单...");

}

void Insertsort()//直接插入排序

{ } } q=getchar(); if (q!='\xA') { getchar();ch1='n'; }

int i,j,k,m=0;

printf("\n\t\t尚未排序的数据为（回车继续）：");

for(k=1;k<=L;k++) printf("%5d",R[k]); getchar(); printf("\n"); for(i=2;i<=L;i++) { if(R[i]<R[i-1]) { R[0]=R[i];j=i-1; while(R[0]<R[j]) {

times++;

changes++;

R[j+1]=R[j];j--; } R[j+1]=R[0];

changes++;

} printf("\n\n"); } m++; times++; printf("\t第%d趟排序结果为（回车继续）：",m); for(k=1;k<=L;k++) printf("%5d",R[k]); getchar();printf("\n");

printf("\t最终排序结果为：");

for(i=1;i<=L;i++) printf("%5d",R[i]); printf("\n");

printf("\n\t直接插入排序的比较次数为%d",times); printf("\n\t直接插入排序的移动次数为%d",changes); times=0;

changes=0;

}

void Bubblesort()//冒泡排序

{

int i,j,k;

int exchange;

printf("\n\t\t尚未排序的数据为（回车继续）：");

for(k=1;k<=L;k++) printf("%5d",R[k]); getchar(); printf("\n"); for(i=1;i<=L;i++) { exchange=FALSE; for(j=L;j>=i+1;j--) {

times++;

if(R[j]<R[j-1]) { R[0]=R[j]; R[j]=R[j-1]; R[j-1]=R[0]; exchange=TRUE;

changes+=3;

}} if(exchange) printf("\t第%d趟排序结果为（回车继续）：",i); for(k=1;k<=L;k++)

printf("%5d",R[k]); getchar();printf("\n");

} printf("\n\n");

printf("\t最终排序结果为：");

for(i=1;i<=L;i++) printf("%5d",R[i]); printf("\n");

printf("\n\t冒泡排序的比较次数为%d",times);

printf("\n\t冒泡排序的移动次数为%d",changes); times=0;

changes=0;

}

void Selectsort()

{

int i,j,k,h;

printf("\n\t\t尚未排序的数据为（回车继续）：");

for(k=1;k<=L;k++) printf("%5d",R[k]); getchar(); printf("\n"); for(i=1;i<=L;i++) { h=i; for(j=i+1;j<=L;j++) {times++;

if (R[j]<R[h])

h=j;

if(h!=j) { R[0]=R[h];R[h]=R[i];R[i]=R[0];

changes+=3;

}

}

} printf("\n\n"); printf("\t第%d趟排序结果为（回车继续）：",i); for(k=1;k<=L;k++) printf("%5d",R[k]); getchar();printf("\n");

printf("\t最终排序结果为：");

for(i=1;i<=L;i++) printf("%5d",R[i]); printf("\n");

printf("\n\t选择排序的比较次数为%d",times); printf("\n\t选择排序的比较次数为%d",changes); times=0;

changes=0;

}

void Shellsort() //希尔排序

{

int i,j,gap,x,m=0,k;

printf("\n\t尚未排序的数据为（回车继续）："); for(k=1;k<=L;k++)

printf("%5d",R[k]); getchar();

printf("\n"); gap=L/2; while (gap>0) { for(i=gap+1;i<=L;i++) { j=i-gap; while(j>0) {

times++;

if (R[j]>R[j+gap]) { x=R[j];R[j]=R[j+gap]; R[j+gap]=x; j=j-gap;

changes++; }

else

} gap=gap/2; m++; printf("\t第%d趟排序结果为（回车继续）：",i); } printf("\n\n"); for(k=1;k<=L;k++) printf("%5d",R[k]); } j=0; getchar();printf("\n");

printf("\t最终排序结果为：");

for(i=1;i<=L;i++) printf("%5d",R[i]); printf("\n");

printf("\n\t希尔排序的比较次数为%d",times); printf("\n\t希尔排序的移动次数为%d",changes); times=0;

changes=0;

}

void CreateHeap(int root,int index)//建堆

{

int j,temp,finish; j=2*root; temp=R[root]; finish=0; while (j<=index&&finish==0) { if (j<index) if (R[j]<R[j+1]) {

j++;

times++;

}

if(temp>=R[j]) {

finish=1; //堆建立完成 times++;

}

else { R[j/2]=R[j];//父结点=当前结点

j=j*2;

changes++;

}

void HeapSort()

{

int i,j,temp,k; for(i=(L/2);i>=1;i--)//将二叉树转换成堆 CreateHeap(i,L);//建堆 } R[j/2]=temp; //父结点=root值 }

for(i=L-1,k=1;i>=1;i--,k++)

{ temp=R[i+1];//堆（heap）的root值和最后一个值交换 R[i+1]=R[1]; R[1]=temp;

changes+=3;

}

void Heap()

{ int k;

printf("\n\t尚未排序的数据为（回车继续）："); for(k=1;k<=L;k++)

printf("%5d",R[k]); } CreateHeap(1,i); printf("\t第%d趟排序结果为（回车继续）：",k); for(j=1;j<=L;j++) printf("%5d",R[j]); getchar();printf("\n"); printf("\n\t");

getchar(); HeapSort(); printf("\n\n"); printf("\t最终排序结果为："); for(k=1;k<=L;k++) printf("%5d",R[k]); printf("\n");

printf("\n\t堆排序的比较次数为%d",times); printf("\n\t堆排序的移动次数为%d",changes);

}

int Partition(int i,int j) //快速排序

{

int pirot=R[i]; while(i<j) { while(i<j&&R[j]>=pirot) { j--; times=0; changes=0; times++; } if(i<j) { R[i++]=R[j]; changes++; } while(i<j&&R[i]<=pirot) { i++; times++; } if(i<j) { R[j--]=R[i];

} } changes++; } R[i]=pirot; return i;

void QuickSort(int low,int high)

{

int pirotpos,k,i; if (low<high) { pirotpos=Partition(low,high); num++; printf("\t第%d趟排序结果为（回车继续）\n：",num); for(k=1;k<=L;k++)

printf("%5d",R[k]); getchar();printf("\n"); QuickSort(low,pirotpos-1);

QuickSort(pirotpos+1,high);

} printf("\n\n");

printf("\t最终排序结果为：\n");

for(i=1;i<=L;i++) printf("%5d",R[i]); printf("\n");

printf("\n\t快速排序的比较次数为%d",times);

printf("\n\t快速排序的移动次数为%d",changes);

times=0;

changes=0;

}