首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 范文大全
  • 古典文学
  • 职场知识
  • 中国文学
  • 公文书信
  • 外国名著
  • 寓言童话
  • 百家讲坛
  • 散文/诗歌
  • 美文欣赏
  • 礼仪知识
  • 民俗风情
  • 谜语大全
  • 名言警句
    • 蒲公英阅读网 > 寓言童话 > 正文

    《数据结构》实验报告——排序

    时间：2020-07-27 11:47:49 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：数据结构 排序 实验

    　《数据结构》实验报告

    　 排序 实验题目：

    　输入十个数,从插入排序，快速排序,选择排序三类算法中各选一种编程实现。

    　实验所使用得数据结构内容及编程思路：

    　１、插入排序：直接插入排序得基本操作就是,将一个记录到已排好序得有序表中，从而得到一个新得，记录增一得有序表。

    　一般情况下,第 i 趟直接插入排序得操作为:在含有ｉ—1 个记录得有序子序列ｒ［1、、i－1］中插入一个记录 r[i］后,变成含有 i 个记录得有序子序列ｒ[1、、i］；并且,与顺序查找类似，为了在查找插入位置得过程中避免数组下标出界，在 r［0］处设置哨兵。在自 i-1 起往前搜索得过程中,可以同时后移记录.整个排序过程为进行 n—1 趟插入,即:先将序列中得第一个记录瞧成就是一个有序得子序列,然后从第 2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。

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

    　假设待排序得序列为｛L、ｒ[s］，L、r[s+1］,…Ｌ、ｒ［ｔ］｝,首先任意选取一个记录（通常可选第一个记录 L、r［s］）作为枢轴（或支点）（ｐiｖoｔ),然后按下述原则重新排列其余记录:将所有关键字较它小得记录都安置在它得位置之前,将所有关键字较大得记录都安置在它得位置之后。由此可以该“枢轴”记录最后所罗得位置 i 作为界线，将序列{L、r［s］，…，Ｌ、r[ｔ］｝分割成两个子序列{Ｌ、r［ｉ＋1],L、[i+2],…，L、r[ｔ]}。这个过程称为一趟快速排序，或一次划分。

    　一趟快速排序得具体做法就是:附设两个指针 loｗ与ｈigh，她们得初值分别为low与hｉgh,设枢轴记录得关键字为pivｏtkey,则首先从high所指位置起

    　向前搜索找到第一个关键字小于 pivｏｔkey 得记录与枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pｉvoｔkey得记录与枢轴记录互相交换，重复这两不直至 lｏw=high 为止。

    　具体实现上述算法就是，每交换一对记录需进行 3 次记录移动（赋值）得操作。而实际上，在排列过程中对枢轴记录得赋值就是多余得，因为只有在一趟排序结束时,即 low=hｉｇh 得位置才就是枢轴记录得最后位置。由此可以先将枢轴记录暂存在 r［0]得位置上,排序过程中只作 r［low］或ｒ［higｈ］得单向移动,直至一趟排序结束后再将枢轴记录移至正确位置上. 整个快速排序得过程可递归进行。若待排序列中只有一个记录，显然已有序,否则进行一趟快速排序后再分别对分割所得得两个子序列进行快速排序. 3、简单选择排序：其操作为，通过 n-i 次关键字间得比较，从 n—i＋1 个记录中选出关键字最小得记录,并与第 i（1≤i≤n)个记录交换之。

    　显然,对 L、r[1…n]中得记录进行简单选择排序得算法为：令ｉ从１至 n—1,进行 n—1 趟选择操作.可以瞧出，简单选择排序过程中,所需进行记录移动得操作次数较少,其最小值为“0"，最大值为 3(n-1）。然后，无论记录得初始排列如何,所需进行得关键字之间得比较次数相同，均为 n（n—1)/2。

    　程序清单：

    　1．插入排序：

    　＃incluｄe〈ｓｔdｉo、ｈ〉 struct ｓｑｌist ｛int key［11]；

    　int lengtｈ； ｝ insｅrtｓort（stｒucｔ sqlｉsｔ ＊l) ｛ ｉnt i，j;

    　foｒ(i=２;ｉ〈=l—＞length；i++)

    　 ｉf（l－〉keｙ［i］〈l-＞key［i－1］）

    　｛l-＞key[0]=ｌ－〉key[i];

    　 l－＞ｋｅy［i]=l－〉kｅy[i-1］；

    　foｒ(j=i-2;l—>key［0］＜ｌ—>keｙ［j]；j－-）

    　l—〉keｙ[j+１]=l—>key[ｊ］；

    　ｌ—>key[j+1]=l—>ｋeｙ[０]；

    　｝ ｝ ｍain（）

    　｛ ｉnt i,j,k； ｓtｒuct sqｌiｓt num; nuｍ、lｅnｇth=1０； foｒ（i＝1;i<=ｎｕm、lｅｎgｔh；ｉ＋+)scanf（”%ｄ",＆（nuｍ、kｅy［i])）； ｉnsｅrtsｏｒｔ(＆nuｍ); pｒｉntｆ（“ｃｈａru：”）; for(i=１；ｉ<=num、leｎgｔｈ；i+＋）pｒiｎtf （”％ｄ ＂，nuｍ、key[i］); ｝ 测试用例：

    　输入:23 ３4 １2 98 5６ 45 ６７ 8 9 37

    　 输出:charu：８ 9 12 ２3 ３４ ３7 45 56 6７ ９8 2 快速排序：

    　#iｎclｕde<stdio、ｈ> struct sqlist ｛ int ｋey[1１]; ｉnｔ lｅngth； }； int partitｉon(strｕct sqlisｔ ＊l,int low，int ｈigh) ｛ int pｉvotkey； l－＞key[0］=ｌ-〉ｋey[lｏw]; pivotkey=l－＞key［ｌow］； while（low＜high）

    　{ｗhile(low<high&&l-〉key[higｈ］〉=ｐiｖotkｅy)ｈigｈ-－;

    　 ｌ-＞key[lｏｗ］＝l->kｅｙ［hｉgh］；

    　ｗhilｅ(ｌow＜ｈigh＆&l->ｋｅｙ［low］<＝pivotkey）low++;

    　ｌ-〉kｅｙ［hｉｇｈ]=l—＞kｅy［loｗ]; ｝ ｌ->key[low]=ｌ—>ｋey［0]； rｅturｎ ｌow; } void qsoｒt（ｓtruct ｓｑlｉst *l，iｎt low,int high) ｛iｎt ｐivotlｏc;

    　if（low＜ｈｉgh）

    　｛ｐivotｌｏc=partitiｏｎ(l，ｌow，higｈ)；

    　 qsorｔ(ｌ，low，pｉvotloc—1）；

    　 qsorｔ(l,piｖotloc+1，ｈiｇh）;

    　} } void qｕｉcksort（struｃｔ sqｌiｓt *ｌ) { qsort(ｌ,1,l->ｌenｇth）； ｝ main(）

    　{ ｉnｔ i，j; ｓtruｃｔ sｑlist num； nuｍ、ｌeｎgtｈ=10; fｏr(i＝1；i<=ｎｕｍ、lｅngth;i＋＋）scanf（”%d"，＆(ｎuｍ、key[i]))； quicksort（&num）; prｉｎtｆ（“kuaｉsu：”); fｏr（i＝1；i〈＝nuｍ、lｅngth；ｉ＋+）pｒｉnｔf("%d ＂，num、keｙ［i］)； } 测试用例: 输入:23 34 １２ ９8 ５6 45 ６7 ８ ９ 37

    　 输出：chａru：8 9 12 ２3 ３4 ３7 45 5６ 67 98 ３选择排序：

    　＃iｎcludｅ＜stdiｏ、ｈ＞ struct sqlist ｛int kｅｙ［1１]；

    　ｉnｔ leｎgth； ｝； inｔ selectminkey（sｔrｕｃt ｓｑｌiｓt *l，iｎｔ ａ) ｛ int i，j=a; ｆor（i=a;i〈=l－>lenｇｔｈ;i++）

    　ｉｆ（l—>kｅy［i]＜l－>key［ｊ])j=ｉ;

    　 retuｒn j； ｝ void selectsort (ｓtruct sqlist *ｌ）

    　｛iｎt ｉ，j,k;

    　foｒ（i＝1;i<ｌ—＞lｅｎｇtｈ；i+＋）

    　｛j=selecｔmｉnkｅy(ｌ,i）；

    　 if（i!＝j)｛k=l－>kｅy［i];

    　l－〉keｙ[i]=ｌ-＞key[j］；

    　ｌ—〉ｋey[j]＝ｋ；}

    　｝ } main（）

    　｛ iｎｔ i,ｊ; ｓtｒuct sqlｉst num; num、lengｔh=１0； for（i=1；i〈=ｎｕm、leｎgth;i++）scaｎｆ（＂％d”，＆(nｕm、kｅy［i］)); seｌectsort（＆nｕm）； printf(“xuａｎzｅ:”）； ｆｏｒ（ｉ=1；i<＝num、ｌength；i++）prｉntf(”%d ”,ｎum、key［i］）； } 测试用例：

    　输入:23 34 12 98 ５6 4５ 67 8 ９ ３7

    　输出：charu:8 9 12 23 3４ 3７ 45 ５6 67 98 编程感想: 本次编程总共使用了三种排序方法,而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻得了解。

    　首先,三种排序中，我们都像查表那样，设置了哨兵，而哨兵得使用可以减少对整个表得验空操作,使程序更加节省空间。

    　其次,对于插入排序,每次都要对一段序列进行检索，每排一次所要检索得序列长度减一，其时间发杂度为 O（n^2）。

    　接着，对于快速排序，这个程序就是比较复杂得，总共就是３个函数，并且使用了递归得方法,这就是但就是，这种算法却就是最优越得，平均性能也就是最好得,我在编这个程序时，对其排序得思想有了进一步得了解，并努力拿她与冒泡排序进行比较，瞧出了些许其优越性。

    　还有,就就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样,都就是Ｏ(n^2)，性能不如快速排序. 最后,本次试验就是数据结构课得最后一次实验，经过数据结构试验课得锻炼,使我对数据结构有了更深刻得理解,对我对其知识起到了重要得影响，增加了我编程得实践活动，为我将来进一步学习打下了基础。

  • 三反、三查活动个人自查材料:个人自查材料
  • 精准扶贫调研报告范文 [深入推进精准健康
  • 怎样修改文档颜色样式 [Word文档如何修改
  • 【关于秋天的朗诵稿】 关于端午节的朗诵稿
  • 【小米盒子用着很卡怎么解决】 小米盒子卡
  • cd锤石符文出装_LOLS7辅助锤石符文天赋出装
  • 【学唱歌作文200字】学唱歌作文
  • 儿童节手抄报内容资料_6.1儿童节手抄报资料
  • _市物业管理条例学习心得
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文《数据结构》实验报告——排序由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.