河南中医药大学：《数据结构》课程教学资源（实验指导）实验九 排序方法的实现

《数据结构》实验指导/实验九:排序方法的实现1 《数据结构》实验指导 实验九:排序方法的实现 、实验目的 1、掌握排序的基本概念。 2、掌握不同的排序方法 3、掌握排序方法的比较。 4、了解排序方法的应用。 二、实验学时 、实验类型 综合性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、不同的排序方法 4、排序方法的算法实现 六、实验任务 1、排序方法的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共5页第1页

《数据结构》实验指导 / 实验九：排序方法的实现 1 管理科学与工程学科 / 共5页,第1页 《数据结构》实验指导 实验九：排序方法的实现 一、实验目的 1、 掌握排序的基本概念。 2、 掌握不同的排序方法。 3、 掌握排序方法的比较。 4、 了解排序方法的应用。 二、实验学时 2 学时 三、实验类型 综合性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、不同的排序方法 4、排序方法的算法实现 六、实验任务 1、排序方法的代码实现 2、编写应用程序，用相关数据验证运算算法

《数据结构》实验指导/实验九:排序方法的实现 2 七、实验内容及步骤 任务:代码实现顺序表的创建、显示、排序;编写应用程序,用相关数据验证算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)创建顺序表的存储结构,包括创建、显示、直接插入排序、快速排序、直接选择排序 等方法,代码参考如下 struct RecType public int key; public string data; }; class InterSort class const int MaxSize 10000: public RecTypell r; public int length string sstr; public InterSortClasso R=new recType MaxSize; h= new Radixnodeo; 顺序表的基本运算和排序算法 public void Createlist(stringl l split) for(i=0; i0) string mystr= RO.key. ToString0; for(i=1;i<length; i++) 描顺序表中各元素值 mystr+=+RIi. keyToString 0; return mystr; 管理科学与工程学科/共5页第2页

《数据结构》实验指导 / 实验九：排序方法的实现 2 管理科学与工程学科 / 共5页,第2页 七、实验内容及步骤 任务：代码实现顺序表的创建、显示、排序；编写应用程序，用相关数据验证算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 创建顺序表的存储结构，包括创建、显示、直接插入排序、快速排序、直接选择排序 等方法，代码参考如下： struct RecType { public int key; public string data; }; class InterSortClass { const int MaxSize = 10000; public RecType[] R; public int length; string sstr; public InterSortClass() { R = new RecType[MaxSize]; length = 0; h = new RadixNode(); } //-----------------顺序表的基本运算和排序算法-------------------------------- public void CreateList(string[] split) { int i; for (i = 0; i 0) { string mystr = R[0].key.ToString(); for (i = 1; i < length; i++) //扫描顺序表中各元素值 mystr += " " + R[i].key.ToString(); return mystr; }

《数据结构》实验指导/实验九:排序方法的实现 3 else return"空串"; 各种排序算法 public string Insertsorto ∥)R|0.n1按递增有序进行直接插入排序 J string mystr=; RecT pe tmp; h;i++) 右向左在有序区R01中找R的插入位置 while gj>=0&&RIjI. key>tmp. key) RIj+1=riil; 将关键字大于R[key的元素后移 1j+1l 在j+1处插入R[ for (int k=0; k- mystr+= RIk key ToString+"; return mvstr public string QuickSort ∥)R0.n-的元素按递增进行快速排序 1(0, length-1) private void QuickSortl(int s, int t) ∥)对Rst的元素进行快速排序 RecType tmp; if(si&& Rijn. ke 管理科学与工程学科/共5页第3页

《数据结构》实验指导 / 实验九：排序方法的实现 3 管理科学与工程学科 / 共5页,第3页 else return "空串"; } //---------------各种排序算法-------------------------------------------------- public string InsertSort() //对 R[0..n-1]按递增有序进行直接插入排序 { int i, j; string mystr = ""; RecType tmp; for (i = 1; i = 0 && R[j].key > tmp.key) { R[j + 1] = R[j]; //将关键字大于 R[i].key 的元素后移 j--; } R[j + 1] = tmp; //在 j+1 处插入 R[i] for (int k = 0; k i && R[j].key >= tmp.key) j--;

《数据结构》实验指导/实验九:排序方法的实现 R=RIJI; while(i<j && riil RII=Ril Ri 0: k< length; k sstr+= Rk] key. ToString(+i QuickSort(s, i-1); /对左区间递归排序 QuickSort(i+1, t); )右区间递归排序 public string Selectsorto ∥直接选择排序 string mystr=; RecType tmp; for (i=0: i< length-1; i++) ∥做第i趟排序 iToString+: rg if (rljkey <rImin. key) ∥min记下目前找到的最小关键字所在的位置 if (min ! =i) /交换R和Rmin tmp= r: for(int k=0; k< length; k++) ma mystr +=RIk. key ToString 0+; return mystr; (3)创建窗体应用程序,调用不同的排序方法,显示出排序过程,界面参考如下: 管理科学与工程学科/共5页第4页

《数据结构》实验指导 / 实验九：排序方法的实现 4 管理科学与工程学科 / 共5页,第4页 R[i] = R[j]; while (i < j && R[i].key <= tmp.key) i++; R[j] = R[i]; } R[i] = tmp; for (int k = 0; k < length; k++) sstr += R[k].key.ToString() + " "; sstr += "\r\n"; QuickSort1(s, i - 1); //对左区间递归排序 QuickSort1(i + 1, t); //对右区间递归排序 } } public string SelectSort() //直接选择排序 { int i, j, min; string mystr = ""; RecType tmp; for (i = 0; i < length - 1; i++) //做第 i 趟排序 { mystr += "i=" + i.ToString() + ": "; min = i; for (j = i + 1; j < length; j++) if (R[j].key < R[min].key) min = j; //min 记下目前找到的最小关键字所在的位置 if (min != i) //交换 R[i]和 R[min] { tmp = R[i]; R[i] = R[min]; R[min] = tmp; } for (int k = 0; k < length; k++) mystr += R[k].key.ToString() + " "; mystr += "\r\n"; } return mystr; } } （3） 创建窗体应用程序，调用不同的排序方法，显示出排序过程，界面参考如下：

《数据结构》实验指导/实验九:排序方法的实现 5 排序 操作步骤1建立顺序表 输入排序元素:3225,64,5812.45,15.80,63,20 建立顺序表注意关鍵字必须为数字如输入1,4日53(不超过100元素 操作步骤2输出顺序表 32256458124515806320 输出顺序表 操作步骤3排序 直接插入排序快速排序 ◎直接选择排序 =1:25326458124515806320 排序 =2:25326458124515806320 =3:25325864124515806320 =4:12253258644515806320 =5:12253245586415806320 每趟结果 6:12152532455864806320 =7:12152532455864806320 1=8:12152532455863648020 =9:12152025324558636480 操作提示:数据排序完毕 (4)调试运行,并观察运行情况。 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、不同的排序方法 3、不同排序方法的比较。 九、课外自主实验 1、编写希尔排序、堆排序、基数排序的代码,并通过应用程序调试运行。 管理科学与工程学科/共5页第5页

《数据结构》实验指导 / 实验九：排序方法的实现 5 管理科学与工程学科 / 共5页,第5页 （4） 调试运行，并观察运行情况。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 不同的排序方法； 3、 不同排序方法的比较。 九、课外自主实验 1、编写希尔排序、堆排序、基数排序的代码，并通过应用程序调试运行