实验六 排序

一、实验目的

1、掌握内部排序的基本算法；

2、分析比较内部排序算法的效率。

二、实验预习

说明以下概念

1、 简单排序：将一组记录按某关键字递增或递减的顺序排序。

2、 希尔排序：又称“缩小增量排序”属于插入排序类的方法。

3、 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

4、堆排序：只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

三、实验内容和要求

1、编程实现直接插入排序算法。

程序代码：

#include<stdio.h>

#include<stdlib.h>

#define ERROR 0

#define OK 1

#define LT(a,b) ((a)<(b))

#define MAXSIZE 20

typedef int KeyType;

typedef struct{

KeyType r[MAXSIZE+1];

int length;

}Sqlist;

int InitList_Sq(Sqlist &L){

    int i=1;

    //printf("请输入待排序的记录的个数：");

    //scanf("%d",&L.length);

    printf("请输入待排序的记录的关键字（整型数）：");

    while(scanf("%d",&L.r[i]))

    {i++ ; }

    L.length=i-1;

      return OK;

}/*InitList*/

void Print_Sq(Sqlist &L) /*输出顺序表*/

{ int i;

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

  printf(" %d",L.r[i]);

}

void InsertSort(Sqlist &L){

 int i,j;

 for(i=2;i<=L.length;++i)

if(LT(L.r[i],L.r[i-1]))//“<”，需将L.r[i]插入有序子表

{

L.r[0]=L.r[i];//复制为哨兵

     L.r[i]=L.r[i-1];

     for(j=i-2;LT(L.r[0],L.r[j]);--j)

     L.r[j+1]=L.r[j];//记录后移

     L.r[j+1]=L.r[0];//插入到正确位置

}

}

 void main()

{

Sqlist S;

InitList_Sq(S);

 Print_Sq(S);

printf(" \n1.简单插入排序\n");

 InsertSort(S);

 Print_Sq(S);

 /*printf(" 3.快速排序\n");

QuickSort(S);

 Print_Sq(S);

 printf(" 5.堆排序\n");

 HeapSort(S);

 Print_Sq(S);*/

}

2、输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

1）直接插入排序运行结果（写出每一趟的状态）：

38 49 65 97 13 27 49

13 38 49 65 97 27 49

13 27 38 49 65 97 49

13 27 38 49 49 65 97

2）堆排序运行结果（写出每一趟的状态）：

3、编程实现快速排序算法。

程序代码：

#include<stdio.h>

#include<stdlib.h>

#define ERROR 0

#define OK 1

#define LT(a,b) ((a)<(b))

#define MAXSIZE 20

typedef int KeyType;

typedef struct{

KeyType r[MAXSIZE+1];

int length;

}Sqlist;

int InitList_Sq(Sqlist &L)

{

    int i=1;

    //printf("请输入待排序的记录的个数：");

    //scanf("%d",&L.length);

    printf("请输入待排序的记录的关键字（整型数）：");

    while(scanf("%d",&L.r[i]))

    {i++ ; }

    L.length=i-1;

      return OK;

}/*InitList*/

void Print_Sq(Sqlist &L) /*输出顺序表*/

{ int i;

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

  printf(" %d",L.r[i]);

}

void InsertSort(Sqlist &L){

 int i,j;

 for(i=2;i<=L.length;++i)

 if(LT(L.r[i],L.r[i-1]))//“<”，需将L.r[i]插入有序子表

 { L.r[0]=L.r[i];//复制为哨兵

 L.r[i]=L.r[i-1];

 for(j=i-2;LT(L.r[0],L.r[j]);--j)  

 L.r[j+1]=L.r[j];//记录后移

 L.r[j+1]=L.r[0];//插入到正确位置

}

}

int Partition(Sqlist &L,int low,int high)

{//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时 //在它之前（后）的记录均不大（小）于它。

    KeyType pivotkey; L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

    pivotkey=L.r[low];//枢轴记录关键字

    while(low<high) {//从表的两端交替地向中间扫描

        while (low<high&&L.r[high]>=pivotkey) --high;

        L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端

        while (low<high&&L.r[low]<=pivotkey) ++low;

        L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端

    }

    L.r[low]=L.r[0];//枢轴记录到位

    return low;//返回枢轴位置

}

void QSort(Sqlist &L,int low,int high)

{//对顺序表L中的子序列L.r[low..high]进行快速排序

int pivotloc; if(low<high) {//长度大于1

pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二

QSort(L,low,pivotloc-1);//对低子表递归排序pivotloc是枢轴位置

QSort(L,pivotloc+1,high);//对高子表递归排序

}

}

void QuickSort(Sqlist &L)

{//对顺序表L作快速排序。

QSort(L,1,L.length);

}

void main()

{

 Sqlist S;

 InitList_Sq(S);

 Print_Sq(S);

 printf(" \n1.简单插入排序\n");

 InsertSort(S);

 Print_Sq(S);

 printf("\n 2.快速排序\n");

 QuickSort(S);

 Print_Sq(S);

/* printf(" 5.堆排序\n");

 HeapSort(S);

 Print_Sq(S);*/

 }

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

运行结果（写出每一趟的状态）：

初始关键字  ：     49 38 65 97 13 27 49

完成一趟排序：     {27 38 13} 49 {97 65 49}

分别进行快速排序： {13} 27 {38}  {49 65} 9749 65

有序序列：13 27 38 49 49 65 97

四、实验小结

请比较各个排序算法的性能。

时间性能上，  快速排序 > 堆排序 > 合并排序 > 插入排序 > 冒泡排序 交换次数上，  合并排序 > 快速排序 > 堆排序 > 冒泡排序 > 插入排序

五、教师评语

第二篇：数据结构实验6报告

数据结构实验报告

第  6 次实验

一、 实验目的

1． 理解栈是操作受限（插入push，删除pop）的线性表，受限的是插入删除的位置。

2． 在链式存储结构下实现：StackEmpty，Push,Pop, 几个基本操作。

3． 通过调用基本操作实现括号匹配算法。

二、实验内容（问题）

写一个算法，识别依次读入的一个字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而’1+3&3-1’则不是。

测试数据：’1+3&3-1’; ’a+b+c&c+b+a’; ’a+b+c&c+b’; ’b+c&c+b+a’;

提示：利用栈 ，利用已实现的基本操作

三、算法描述（给出自然语言描述的算法）

1.向后依次扫描字符序列，如果考察的字符不等于‘&’则入栈，遇到‘&’则停止。

2.从‘&’后继续扫描，考察字符的时候，栈顶元素出栈，若二者相等，继续扫描；不等，模式不成立。

3.扫描结束后，栈空则模式成立

四、详细设计（画流程图）

五、程序代码

#include<stdio.h>

#include<stdlib.h>

#define True 1

#define False 0

#define OK 1

#define ERROR 0

typedef int status;

typedef char ElemType;

typedef struct SNode{

  ElemType data;

  struct  SNode  *next;

}SNode, *LinkStack;

status InitStack(LinkStack &S);

int StackEmpty(LinkStack S);

status Push(LinkStack &S, ElemType e);

status Pop(LinkStack &S, ElemType &e);

status Is_Match(ElemType f[20]);

main(){

 ElemType formula[20];int i;

 for(i=0;i<=3;i++)

 {printf("\n请输入一个字符序列表达式：");

 scanf("%s",formula);

 if(Is_Match(formula)==1) printf(" \n这个表达式符合‘序列1&序列2’模式！\n");

 else printf("\n 这个表达式不符合‘序列1&序列2’模式！\n");}

 return(1);

 }

status InitStack(LinkStack &S){        

  S=NULL;

  return(OK);

}

int StackEmpty(LinkStack S){        

  if(S==NULL) return(True);

  else return(False);

}

status Push(LinkStack &S, ElemType e){

 LinkStack p;

 p=(LinkStack)malloc(sizeof(SNode));

 if(!p) return(ERROR);

 p->data=e;

 p->next=S;

 S=p;

 return(OK);

} 

status Pop(LinkStack &S, ElemType &e){

 LinkStack p;

 if(!S) return(ERROR);

 e=S->data;

 p=S;

 S=S->next;

 free(p);

 return(OK);

}

status Is_Match(ElemType f[20]){

 LinkStack St; ElemType *p,c;

 InitStack(St);

 p=f;

 for(;*p!='&';p++)

 { Push(St,*p);

 if(!Push(St, *p)) return(ERROR);}p++;

 for(;*p!='\0';p++)

 {

        Pop(St,c);

        if(!Pop(St,c)) return(ERROR);

        else if(c!=*p) return(ERROR);}

 if(StackEmpty(St)) return(OK);

 else return(ERROR);

}

七、用户手册

  （教用户怎么用这个程序）

用途：判断字符串是否是“ 序列1&序列2’模式 ”

用法：启动此程序，屏幕会提示你输入数据，输入数据并按下回车键即可。程序的执行结果就会显示在屏幕中。