数据结构C语言冒泡排序和直接插入排序实验报告

1．掌握常用的排序方法，并用高级语言实现排序算法。

2．理解排序的定义和各种排序的特点。

3．了解排序过程及依据的原则，并了解各种排序方法的时间复杂度分析。

二、实验任务

1．设计一待排序的线性表以顺序存储结构存储，试写出冒泡排序和直接插入排序算法。

三、程序流程图

开始 线性表指针p 定义循环体i,j i=2 i++ i<=last 否 是 elem[0]=elem[i] elem[j+1]=elem[0] 结束 j=i-1 否 elem[0]开始 线性表指针p 定义循环变量i,j 定义交换变量x 定义循环标志flag i=1 elem[j+1]=x flag=1 i四、测试过程及结果

五、总结

1．程序特点：最小化、模块化、for循环。

2．直接插入排序特点：双循环，从第二项起执行n-1趟,每趟开始将第i项赋给第0项作为循环终点，每趟最大执行i-1次。每趟将前i+1项排序

3．冒泡排序特点：双循环，从第一项起最大执行n-1趟，每趟开始将循环符号flag置零。每趟从第一项起，执行n-i次。每趟将第i大的项移到第n-i+1位。

附录程序清单

//直接插入排序

#define MAXLEN 100 #include struct sqlisttp{

int elem[MAXLEN]; int last; };

sqlisttp *create() {

int i;

sqlisttp v;

scanf(\"%d\ for(i=1;i<=v.last;i++) scanf(\"%d\ return &v; }

void print(sqlisttp *p) {

int i;

for(i=1;i<=p->last;i++) printf(\"%d \ printf(\"\\n%d\\n\}

void insertsort(sqlisttp *p) {

int i,j;

for(i=2;i<=p->last;i++) { p->elem[0]=p->elem[i];

for(j=i-1;p->elem[0]elem[j];j--) p->elem[j+1]=p->elem[j]; p->elem[j+1]=p->elem[0]; } }

void main() { printf(\"直接插入排序\\n\"); sqlisttp v=*create(); insertsort(&v); print(&v); }

//冒泡排序

#define MAXLEN 100 #include struct sqlisttp{

int elem[MAXLEN]; int last; };

sqlisttp *create() {

int i;

sqlisttp v;

scanf(\"%d\ for(i=1;i<=v.last;i++) scanf(\"%d\ return &v; }

void print(sqlisttp *p) {

int i;

for(i=1;i<=p->last;i++) printf(\"%d \ printf(\"\\n%d\\n\}

void bubblesort(sqlisttp *p) {

int i,j,x,flag;

for(i=1;(ilast)&&flag;i++) { flag=0; for(j=1;j<=p->last-i;j++)

if(p->elem[j]>p->elem[j+1]) { x=p->elem[j];

p->elem[j]=p->elem[j+1];

p->elem[j+1]=x; flag=1; } } }

void main() {

printf(\"冒泡排序\\n\");

}

sqlisttp v=*create(); bubblesort(&v); print(&v);