[DOC] 链式存储结构上冒泡排序算法的研究与实现word免费下载

全国最大的共享资料库，等您下载。本资料为[DOC] 链式存储结构上冒泡排序算法的研究与实现.doc文档c语言单链表冒泡排序，由爱问共享资料用户提供c语言单链表冒泡排序，以下为正文内容。

DOC链式存储结构上冒泡排序算法的研究与推动链式存储结构上冒泡排序算法的研究与推动第卷第l期年lO月通化师范学院JOURNALOFTNGHUANORMALUNIVERSITYVolOctl链式存储结构上冒泡排序算法的研究与推动胡新海(陇南师范高等专科学校计算机系,甘肃成县)摘耍:线性表上进行的冒泡排序法是一种较简单的内部排序算法,计算机工作者经常研究跟讨论顺序表中冒泡排序算法的推动以及优化,很少研究冒泡排序法在递归上的实现文中讨论了冒泡排序在单链表上和静态链表上的算法及推动过程最终预测了算法时间复杂度跟空间复杂度关键词:冒泡排序存储结构单链表静态链表算法分析中图分类号:TP文献标志码:A文章编号:lo()O一收稿日期:l一o一O作者简介:胡新海(一),男,甘肃西和人,在读博士,陇南师范高等专科学校讲师冒泡排序是一种较简洁的交换类排序算法在相关文献中探讨了其在排序表上的推动过程】它借助对相邻元素的交换,逐步将待排序列成为有序序列其算法的主要观念是:反复扫描待排序记录序列,在扫描过程中顺次比较相邻的两个元素的大小,若逆序就交换位置在顺序的研究上近几年来也是一些新的方式,在顺序时与链表结构结合,得出一些新的次序思路J在排序表上冒泡排序的实现较简洁,在链表上的次序思想基本跟顺序表上的相同本文讨论了冒泡排序在单链表上和静态链表上的算法及推动过程最终预测了算法时间复杂度跟空间复杂度与排序表上推动的不同之处是必须标记链尾结点的地址冒泡排序算法在单链表上的推动针对链表每一个结点看成竖着排列的”气泡”,然后分别从头结点向尾节点扫描在扫描的过程中时刻留意两个相邻元素的次序,保证前一节点元素的数据域小于后一节点元素的数据,这样经过一趟扫描后就让较大的元素沉到链尾,然后记住链尾结点的位置以后又从头结点向后扫描,由于在前一趟扫描过程中最大的元素尚未沉到链尾并记住了该元素的地址,所以现在扫描最大的元素不再参加排序,将剩下的元素进行顺序,排序的过程中确保使得后一节点元素的数据域大于前一节点元素的数据域这样反复的扫描,并不断缩小排序空间,直到整个序列有序位置为止这种看来,在顺序中,只需记住最后排好序的元素的位置即可定义的链式结构跟详细算法设计如下:typedefintelemtypestmctnode{elemtypedata数据域streetnodenext指针域}Hnklist单链表名voidBubblesoa(Lnklisthead)单链表上的冒泡排序算法{hnklistend,P,qend用来记录排好序的最后一个结点的地址,P,q保持前驱与后继的关系elem~petempP=head一nextq=P一nextend=~序前end指向链尾while(end!=head一next)如果head所指结点的nem成员为end,则结束循环{p=head一ne~p结点总是从链表的头结点开始q:P一ne~q总是指向”P所指结点”的下一结点while(p一next!=end)当P一next的值为end时,表示未到链尾{if(P一dataq一dma)按照数据域从小到大排序{tempP一dataP一damq一dataq一data=temp:}Pqqq一next:}end=p使end指向”每次排序后的q所指的节点即尾结点”}}冒泡排序算法也可在静态链表上的实现在静态单链表中,也可以进行冒泡排序操作,对于静态数组每一个结点同样看成竖着排列的”气泡”,然后分别从静态链表的头结点开始向尾节点扫描在扫描的过程中时刻留意两个相邻元素的次序,保证前一节点元素的数据域小于后一节点元素的数据,这样经过一趟扫描后就让较大的元素沉到链尾,然后记住链尾结点的位置以后又从头结点向后扫描,由于在前一趟扫描过程中最大的元素尚未沉到链尾并记住了该元素的地址,所以现在扫描最大的元素不再参加排序,将剩下的元素进行顺序,排序的过程中确保使得后一节点元素的数据域大于前一节点元素的数据域这样反复的扫描,并不断缩小排序空间,直到整个序列有序位置为止这种看来,在顺序中,只需记住最后排好序的元素的位置即可针对静态数组进行定义和准确算法设计如下:鼻defineNN为链表可能超过的最大长度typedefintelemtypetypedefstructnode{ehmtypedata数据域intnext}slinklistvoidBubblesort(slinklistsN)静态数组上的冒泡排序算法{inthead=一,end,P,qend用来记录排好序的最后一个元素位置的地址,p,q分别为前驱,后继的关系elemtypetempPsheadnextqsPnextend=一排序前end指向链尾while(end!=sheadnext)如果head所指结点的next成员为end,则结束循环{P=sheadnextp结点总是从数组的头结点开始q=sPnextq总是指向”P所指结点”的下一结点while(Pnext!=end)当sPnext的值为end时,表示未到链尾{if(sPdatasqdata)按照数据域从小到大排序{tempsPdatasPdata:sqdatasqdata=temp}Pqq=qnext}end=p使end指向”每次排序后的q所指的节点即尾结点”}}总结性表上的冒泡排序,最好情况下的时间复杂度是O(n),最差和平均状况下的时间复杂度是O(n),辅助空间为O(),算法非常稳定在单链表和静态链表上的冒泡排序的时间复杂度,稳定性与在排序表上完全相似但是从推动过程跟算法的剖析,可以很明显的看到两种算法的设计观念跟实现过程相同也是在单链表上跟静态链表上需记住最后排好序的元素的位置(即尾指针)链式结构上每个数据元素占用一个结点,而不会有多余的节点存在,所以数据元素所占内存空间不会浪费参考文献:严蔚敏,吴伟民数据结构M北京:清华大学出版社,耿国华数据结构(c语言版)M西安:西安电子科技大学出版社,Robe~LKlu~,AlexanderJRybaDataSlrdcturesandProgramDesigninCMUSA:PearsonEducation,傅清祥,王晓东算法与数据结构M北京:电子工业出版社,任志国,等插入排序算法的双链表模拟J电脑编程与维护,()(责任编辑:翟胜)ResearchandRealizationofBubbleSortAlgorithmonLinkStorageStructureHUXinhai(DepartmentofComputerScience,LongnanTeachersCollege,Chengxian,Gansu,China)Abstract:BubblesortwhichproceedonlinearlistisakindofinnersortalgorithmsComputerworkersalwaysresearchanddiscusstherealizationaswellasimprovementonlinearlistinsteadoflinklistInthisarticlewediscussthealgorithmandrealizationproceededonsinglelinklistandstaticlinklistFinallyweanalyzethecomplexityoftimeandspaceofthetwomethodsKeywords:Bubblesortstoragestructuresinglelinkliststaticlinklistalgorithmanalysis

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-135573-1.html