傳智播客C和C與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義

1、傳智播客C和C+丐數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義傳智掃地僧1、數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)相關(guān)概念疑惑1、我學(xué)完了C語言，可是現(xiàn)在感覺還是寫不出代碼。2、為什么會有各種各樣的程序存在？3、程序的本質(zhì)是什么？程序是為了具體問題而存在的程序需要圍繞問題的解決進行設(shè)計同一個問題可以有多種解決方案如何追求程序的“性價比”？是否有可量化的方法判別程序的好壞？數(shù)據(jù)結(jié)構(gòu)起源計算機從解決數(shù)值計算問題到解決生活中的問題'現(xiàn)實生活中的問題涉及不同個體間的復(fù)雜聯(lián)系需要在計算機程序中描述生活中個體間的聯(lián)系數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計算程序問題中的操作對象以及它們之間的關(guān)系不是研究復(fù)雜的算法數(shù)據(jù)結(jié)構(gòu)中的基本概念數(shù)據(jù)-程序的操作對象，用于

2、描述客觀事物(inta,intb,)/數(shù)據(jù)的特點：可以輸入到計算機/可以被計算機程序處理數(shù)據(jù)是一個抽象的概念，將其進行分類后彳#到程序設(shè)計語言中的類型。如：int,float,char數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位數(shù)據(jù)項：一個數(shù)據(jù)元素由若干數(shù)據(jù)項組成數(shù)據(jù)對象-性質(zhì)相同的數(shù)據(jù)元素的集合(比如：數(shù)組，鏈表)歉據(jù)敕據(jù)對象數(shù)據(jù)對象敷搪無費數(shù)據(jù)兀素敦據(jù)元素數(shù)據(jù)元數(shù)據(jù)41數(shù)據(jù)貨2數(shù)據(jù)事1數(shù)據(jù)項2敦希項1數(shù)據(jù)項2敷據(jù)事1數(shù)提項2答：物理結(jié)構(gòu)亦稱t是數(shù)據(jù)的迎再結(jié)構(gòu)在計算機存儲器內(nèi)的表示（或映像）o它JwLjWLrv*-TJHJrIJ"%。存儲結(jié)構(gòu)可分為4大類：順序.斐為親小散列最常用的存骨捕狗為：順序

3、存的轉(zhuǎn)樹借助元素在存儲卷中的相對位置末袤示I數(shù)據(jù)元素間的邏輯關(guān)京鋌式存儲結(jié)構(gòu)借助指示元素存儲地址的指計襄示數(shù)據(jù)元素間的遑輯關(guān)系,數(shù)據(jù)的邃粗結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)算法設(shè)計K超輯結(jié)構(gòu)笄法實現(xiàn)存儲結(jié)構(gòu)解什么是數(shù)據(jù)的運算操作或處理答：在數(shù)據(jù)的逗樽結(jié)構(gòu)上定義的操作,。數(shù)據(jù)的存儲結(jié)構(gòu)上實現(xiàn)-III*BF,最常用的數(shù)據(jù)運算有S種：插入、刪除、修女、查找、排序CM=VO/次at算法C(4H8)法5nDUD(2*1)法DJn2)n112L-_.3I21629I4n3203ig9n=1048102G1IftOnw10040810020001IOOOO森IQOO.4008LJ00020000011。畫)<XK

4、)次數(shù)M»G(in1)舞法H(3n+i施I(2r>z*3n+11246。Z81715:n5501666n«1020031231n=1002000030120301n-LOOO20000(1030Ot2003001n-IdOOO200000000wool200030001n-100t0002000000000030000120000300001n-1.000,00020000000000003OOOOOl2000001000OOI執(zhí)行次她離政Iat非正式水*巴，0(1)2m+3LOCn)城業(yè)階3nJ+2n+l0(/)平方階51ogjn+201OClop/j)H數(shù)降2n+

5、5nio£n+19Ot/iloRrt)nlogu階6n*+2nJ+ln+4。(“)二.r0(2")立方階2Tt找4t階0(1)<0(Jogn)<Oln)<O(dogn)<0(/)<0()<02"0")UJ.工J-口U口XJ.UJ._l數(shù)字n出現(xiàn)的次數(shù)放在新開辟的內(nèi)存空間倒色n-1的位置把每一個數(shù)字的中間結(jié)果給堞存下來一先來一個大家最感興趣的.一年里的星座列表，是不是線性表呢？如圖3-2-2所白金雙巨獅處天射庫水雙羊牛,子蟹子女,稗手羯瓶魚級中同學(xué)的友誼關(guān)系N:NB.公司中的上下級關(guān)系1:NC冬天圖書館排隊占座關(guān)系D.花

6、名冊上名字之間的關(guān)系1:1線性表的操作創(chuàng)建線性表銷毀線性表清空線性表將元素插入線性表將元素從線性表中刪除獲取線性表中某個位置的元素獲取線性表的長度線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型線性表的操作在程序中的表現(xiàn)為一組函數(shù)C語言描述=»線性表的設(shè)計與實現(xiàn)ADT抽象層數(shù)據(jù)Z勾（C語言版）.嚴蔚敏_吳偉民.掃描版.pdfp44頁人生財富庫積累#ifndef_WBM_LIST_H_#define_WBM_LIST_HtypedefvoidList;typedefvoidListNode;341順序存儲定義說這么多的線性表，我們來看看線性表的兩種物理結(jié)構(gòu)的第一種一序存儲結(jié)構(gòu)*性衰的總體存佛堵胸

7、,指的是用一段地址連嫌的存簿元依次存儲畿性裳的鼓據(jù)元素r線性衣（皿,而）的喉序存儲示意圖如下：薪a?Ab.ia$圖"I*表以序寺施，健者溝曜口和也我的身臨長F是網(wǎng)，'不同打假把t5|口0"69夕/Ir方隹for（i=lenBthi；i2眠；1）Ifill.-uLl-1.“-LEJ/i-3".卷五1奉-P“I國/&&）?I巧口0k喇余空間n個結(jié)點（新的存儲映像）蟒結(jié)成一個鏈表，即為線性裘（皿，I,，"）的情式存儲結(jié)構(gòu)，因為此錯表的每個結(jié)點中只包含一個指針域，所以叫做單鏈表.單榜表正是通過每個給點的指針域?qū)⒕€惟表的數(shù)據(jù)元素技其邏輯次序

8、鏈接在一起，如圖324ixkfltypedefstruct.tas.LinkListN?deLinkListtlode;struct_taf_LinkListNod&LinkLi£tNod&*rityt.：端點指針域正乂typedefstruct_tag_LinkList-LinkLi上tN口d自header：intlength;TLinkList;一一定義strictValueLinkListNodeheader:intv：k數(shù)據(jù)元素定義示例插入元素操作*9nade-Miextwcurrent->next;node;eitrrftntcurr«!nf

9、->neitJkcurrenc->nexc=itadecurjreiil因去科"彳年產(chǎn)"一個匕皆保.行，一弓迪百current匚CEGLt“01rijde->£it=LArr&jfLl->nexl,2current>nei1=nod?;:指針搭瞰就把誰的地幽喻指針?分清楚鏈表的操作邏輯和輔聃指曾變量之間的關(guān)卷GUETCDt/理存故地除的下點位置1et=curricnt-z'neat;i指料拈iM蜘:把老的世址廊官推升£片常定范書的挨豐巴羯胡竄毛計克至之同的美第理耦cijrrent->ncxl=ret-&

10、gt;nTzt共結(jié)點尾結(jié)點游標slider近六十年代出生的人，應(yīng)該也就是我們父母那一薪，當年計劃經(jīng)濟制度下，他們的生活祓社會安排好了I先科員再科長、后處長再局長，混到哪算哪；學(xué)徒.技工、高級技工；教師、中皴我?guī)煛⒏遞il教師，總之無論乘個行業(yè)都稔排輩.這鉗的生活如何讓人奮發(fā)努力.所以經(jīng)濟發(fā)展緩慢,就豫苑們的線性表的順序存儲結(jié)構(gòu)一樣，位置是推好的，一切都得慢慢來.可見.夢適環(huán)境是很卷培養(yǎng)出堅強品格，被安排好的人生，也很難做出偉大事業(yè)#市場經(jīng)濟社會下，機會就大參了，你可以從社會的任何一個位置開始起步.只要你真有決心，沒有人可以攔著你.簾實也證期.無論出身是什么,之前是凄苦還是富足，都有出人頭地的一

11、天。當然I這也就意味著，面臨的競爭也是空前激烈的，一不小心，你的位置就可能俄人插足，甚至你就得out出局這也多像我們線性表的鏈式，存儲結(jié)構(gòu),任何位置都可以插入和刪除*a不怕苦，吃苦半輦子，怕吃苦.吃苦一草子*如果你覺得上學(xué)讀書是受罪，假設(shè)你可以活到B0歲.其實你最多也就吃了20年苦,用人生四分之的時間來換取甕余時闞的幸福生活，這點苦不你啥口再說了,跟背我學(xué)習(xí)，這也能算是吃苦？好了，今天課就到這，下i亂I普通插入元素（:和單鏈表是一樣的）I3已經(jīng)存在的和單窿表是一樣的current/®nodeL/*icu匚匚？nt->口匕xt=node;node'>nextnext

12、->prenode'>prenext;node;current:，一A,fcurrentcurrent-'nextnext;next-precurrent;nullnentnesi=current-Jnent若植人第一個匕點，與耳判的打班樽傕否通冏人代和國足rmdje*>prg：-currentntJ?t->pre-2fo.jiE-ie->njexC,一工上工Iwcurrent->neit-口口蛇:nrrentcurrent在尾部地、元京變二.(1母阻甘Liitfit-pre=cumenlJieriemreht-»enrei-5he

13、xT巾體裝出一W律后小蚪或首先它是一個也就是說，棧元素具有線性關(guān)系IWJ前驅(qū)后繼美系.只不過它是一種埼殊的線性表而已-定義中兌是在線性表的表足進行插入用刪除操作，這里表尾是指棧頂，而不是棧底.它的特殊之處就在于限制了這個毅性表的插入和蒯除位置，它始終只在棧頂進行這也就使得：棧底是固定的，最先避棧的只能在棧底.棧的插入操作，叫作進棧，也稱壓錢.人棧。類似產(chǎn)彈人彈求,如圖42*2所示平極的蒯除操作，叫作出棧.也有的叫作彈棧如同彈夾中的子彈出匕w,A23所示.£飛在設(shè)一更部LII!.乩/?。憾?_二"口日二更市、戕的錯點群守inell尹,講完了咳的順序存儲結(jié)構(gòu).我們現(xiàn)在來看，書的

14、鏈式存儲結(jié)構(gòu)，簡稱為鏈棧.想想書,棧只是林劭來做插入和坍除操作，棧頂放在拚去的頭部還是尾部呢？由于單盤表右頭指針，血攫值指斜也是必須的.那十嗎不讓它喃合二為一呢，所跟比較好的辦法是把或順放在單的表的從郵（如國46門所示葭月外，都已芬布了愧頂在頭那廣，甲鏈表中比較常用的頭陸點也就失去了意義，通常對r鏈恍來說，是不需要頭結(jié)點電段底transformtexp)(創(chuàng)述桂5;"Mii=)(it(expUJ為妁字)<OutpuT(expli)；elseifIexpU)為衿號?(岫物explilCUUS<=性及符號伏光版)output(W5n<);poptsn)Pu4h5,exp

15、i)；elseif(已卬門力左括號)(Push(5.expi);elseif(expli)為右插號)(khiletK原存號不為芟括號)(outpu口畫&行號hPop(S>從S甲彈出左括號一else報聃.停止鼻；whileSi?e(S)>“砧(expj-=)叫卬ut(理r®存號片PoMS);J1computE忙卬)翎建樓S;1=0；gillie(expi!空10)if(expfi為野字)(Push(S,expi)helseif(expi為符號)1從柱中彈出右捧作觸；2.從棧中彈出左搔作軟；3,概據(jù)符號進行運算；Push(stack,結(jié)果);)else(報錯停止鬲環(huán);

16、if(Size(5)=L)<expi=)煤作條線和客服系統(tǒng)中，都是應(yīng)用r神數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)剛才提到的先進先出的排隊功能，這就是隊列.隊列(queueI是艮北忤在一端進行插入操作.而在另一端進行除操作的線性衰口隊列是一種先進先出(FietInFiratOut)的線性表，簡稱FIFO.允許插入的一裁稱為隊尾，允許刪除的一端稱為隊頭,唱過隊列是q=(ai,a九.aj.那么位就是隊頭兀素，而小是隊尾元素.這樣我們就可以刪除時，總是從at開始，而插入時，列在后.這也比莪符合我們通常生活中的習(xí)慣，排在第一個的優(yōu)先出列，最后來的當排在隊缶最后，如圖41tM所示.隊列在程序設(shè)計中用得非常頻繁前面我們已經(jīng)舉

17、了兩個例子，再比如用鍵盤進行各種字句或數(shù)字的輸入，到顯示器上如記事本軟件上的輸曲.其實就是隊列的典型鼠頭閑致遍來模按隊列.從迎冕的國史入苴刊從數(shù)盥的。號位百出隊列I-L33456?日I目國對尾廖靚表來使縱隊列，出鼠用肝尾部AKX?J從健老的Q號位置出隊列需要于1,1列羊點=轆表給占=入鏈表率n對阿HPDCPDd.總1j己止所百箱點出隊列，然后輝成籍點的內(nèi)存/蔚敏_吳偉民.掃描版.pdfp124數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)Z構(gòu)（C語言版）.嚴蔚敏_吳偉民.掃描版.pdfp127QIDijTjTX®®<s<a7Xrt7<j)OOG)Q©G©fJkJi

18、f|1JJ,=_x.(fi.o(lj<0XaZWCDQ性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為10g2n+1性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i,其右孩子編號必為2i+1;其雙親的編號必為i/2（i=1時為根，除外）二叉樹的存儲結(jié)構(gòu)/一、順序存儲結(jié)構(gòu)、/按二叉樹的結(jié)點自上而卜、從左至右”編號，用一組連續(xù)的存儲單兀存儲。答：一律轉(zhuǎn)為完全二叉樹！討論：不是完全二叉樹怎么辦？方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上虛結(jié)點”，其內(nèi)容為空二、鏈式存儲結(jié)構(gòu)二叉樹的表示二叉樹表示法P127頁/*typedefstructBiTNode(intdata;str

19、uctBiTNode*lchild,*rchild;BiTNode,*BiTree;*/structBiTNode(intdata;structBiTNode*lchild,*rchild;typedefstructBiTNodeBiTNode;typedefstructBiTNode*BiTree;樹的三叉鏈表表示先序遍歷的結(jié)果是中序遍歷的結(jié)果是DBEAC后序遍歷的結(jié)果是DEBCABCDEFGII先序遍歷中序遍歷后序遍歷BDCEAFHGDECBIIGFAULR先序遍歷，即先根再左再右LDR中序遍歷，即先左再根再右LRD后序遍歷,即先左再右再根從前面的三科遍歷算法可以令道：如果將printf語

20、句抹去T從遞歸的點度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的乂是訪問結(jié)點鞘時機不同.從虛線的出發(fā)點到終點的路徑八上，每個結(jié)點經(jīng)過3次.,第1次經(jīng)過時訪問二先存遍歷B0第2次經(jīng)過時訪問=巾遍歷；第3次經(jīng)過時訪河"后序追歷干俊、/（£2.二叉樹遇歷的時間點率和空間效率時間放率：。（n）每個結(jié)點;；訪問一次FgJ1-t：O（n>"棧占用的最大輔劫空間（精確值：樹深為k的遞歸遍歷需安+1個輔助單元?。┲行虮闅v算法的非遞螞描述BPEXckJc*lhibadxil(HiTreeT.Suick*S)(if!1>t'elum'

21、ILL:while(T-(child)Prhih(S母T-EchRU:1return：),/±2g止冷及的斗:去v*)idhardervoidi-clemType&e»>tHGSlack展tGuLadJitI.S);找到矗左下的好點wliiJrilvisits-dataibifi|t-rchildii=OuKwLeift&rchild.5).dwirIfSluekJimplyIS)1Sk廠、中亭巖巧三堂1明好?卜巴走嗎T(d/時的形狀輪唯一-.、,/*ft*/#并X彳飛-.、/前苫/7Y十/左種的雌有,4/右子樹的根與,J/了搬嶼時，抽右訓(xùn)"

22、/整世滿:的方不柑r巖更呵X播嘉平和右子料邊等分明(1)采用;叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息？(2)二叉鏈表只能找到結(jié)點的左右孩子信息,而不能得到結(jié)點在任一序列中的前驅(qū)和后繼信息r這種信息只有在西歷過程中才能得到，我們可否對二叉鏈去進行改造？f增加兩個域：IXvd和bwd;兩種解決方法I存放前里指不1孱港爨指針利用空鏈域(n+1個空鏈域)我們可以用這IL1個空鏈域未存放當前站點的直接前驅(qū)和后繼等淺索，以加快查找速JL-A二叉線索樹rchilcl懸空？力追免懸空1）若結(jié)點有左子樹，則khUd指向其左孩子；否則，khiWL指向其直接前驅(qū)；2）若結(jié)點有右子樹.則rchild指

23、向其右孩子；否則，Eiild指向其直接后繼（即線索3。了避免混淆.增加兩個標志域.如下圖所示曲山以下二叉樹對應(yīng)的殘索二叉樹該二叉樹中序遍歷結(jié)果為：axLB,E,所以添加線索應(yīng)當檢如下路徑進行：時,表示正常情況;時，表示線索情況.通過圖6-10-4（空心黃頭實線為前驅(qū)，虛線黑箭頭為后繼），就更容易看出,其實線索二義相，等于是把一模二叉樹轉(zhuǎn)變成了一個雙向幡表，這樣對我們的捕人刪除結(jié)點,查找某個結(jié)點都帶來了方便，所以我們對二叉棚以某種次序遍歷使其變?yōu)榫€索二又樹的過程稱做是線索化圖6>ltM#.伸羽再懺變R三智齒寫手有常沮ifCprea>rehiiE=WXL)E”5LrTfhiM-r1有了

24、線索二丈的后，我們對它進行遍街時發(fā)現(xiàn)，其實就等于是操作一個雙向鏈表結(jié)構(gòu).voidIrThrcading(Bi1nrNndeJ(if)ifCprcddld=即叮)/前朋校懿菽：:pie->KTai=L;pre->rchild=p;/)Pre=P；"爆拽卬善同g的3IThrcaiTi(p->rdnLd);/1ii®在既麒Ki3后/卻骷岐b）/FInThrcadingchild)；/化if(p->lchild=WULL)/凌魅P->LTm=1；p->lchild=K"O線盍鬲近微推醐孤和雙向鏈表結(jié)構(gòu)一樣，在二又樹線索鏈表上添加一個頭錯

25、點.如圖6-1牛6所示，并令其國匍域的指針指向二乂網(wǎng)的根結(jié)點（圖中的）,KrchiU域的指針指向中序遍行時訪問的最后一個結(jié)點（圖中的）.反之1令二叉周的中序序列中的第一個結(jié)點中，上hiH域指針和最后一個結(jié)點的rchild域指均指向頭結(jié)點（圖中的和I這樣定義的好處就是我們既可以從第一個結(jié)點起順后儺進行遍歷，也可以從最后一個結(jié)點起搬前驅(qū)迸行遍歷*我何能把這兩耀4闊筒化成葉f給點帶投的一叉羯，如圖6-12-4所示.牝中A妻示不及桃、B或示及格.C衷不中等.D襄示良好、E襄示優(yōu)秀.每個葉干的分支錢上的數(shù)字就是剛才我們提到的五緞分制的成績所占比例般.用641薛夫堂大叔說，從樹中一個結(jié)點到另一個結(jié)點之間的

26、分支構(gòu)成兩個特點之間的躇靜，路役上的分支數(shù)自稱懶路徑長度，ffi6-12-4的二式豺m中.根結(jié)點到結(jié)點D的路及長度就為4,二義樹b中根結(jié)點到站點D的路徑長度為入梅的路徑長度就是從捌根到每一結(jié)點的路徑長度之和已二又附a的樹臍役長度就為1+V2+2+3+3+4+4=20,二叉弱卜的鋤路徑長度就為1*»3+3+2+1+2*2=1幾如果考慮到帶役的緒點.結(jié)點的帶杈的踣徑長度為從填結(jié)點到輔福之間的路段張度與結(jié)點上權(quán)的秦極，幡的帶權(quán)踣經(jīng)長度為例中所者葉子結(jié)盒的帶極痣徑長度之和.假慢仃仆個枇值wwu-Wn),構(gòu)造一棵百口個葉子結(jié)點的二叉樹，吊個明了結(jié)點嘴權(quán)Wk.每個葉子的路徑長度為1k,我解通軒汜

27、作.則其中帶權(quán)踣住長度WL最小的二叉稱做麟關(guān)曼物也在不少好中他棟為最優(yōu)義榜，我個人黨得為了紀念瓢出巨大頁*的科學(xué)家,既然用他仃的名字命名，就座簟9!堅持用他們的名字稱呼,害怕我優(yōu)"史籍體現(xiàn)這操擲的品質(zhì)也應(yīng)垓只作為別名.ABCDEF01100110100111000BADCADFEEDI;1001010010101001000111100定n個數(shù)值v1,v2,，vn2 .根據(jù)這n個數(shù)值構(gòu)造二叉樹集合FF=T1,T2,TnTi的數(shù)據(jù)域為vi,左右子樹為空3 .在F中選取兩棵根結(jié)點的值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，這棵二叉樹的根結(jié)點中的值為左右子樹根結(jié)點中的值之和4 .在F中刪除

28、這兩棵子樹，并將構(gòu)造的新二叉樹加入F中5 .重復(fù)3和4,直到F中只剩下一個樹為止。這棵樹即霍夫曼樹假設(shè)經(jīng)過統(tǒng)計ABCDEF&需要傳輸?shù)膱笪闹谐霈F(xiàn)的概率如下ABCDEF27%8%15%15%30%5%霍夫曼樹是一種特殊的二叉樹霍夫曼樹應(yīng)用于信息編碼和數(shù)據(jù)壓縮領(lǐng)域霍夫曼樹是現(xiàn)代壓縮算法的基礎(chǔ)5、排序排序基本概念現(xiàn)實生活中排序很重要算法已寫好代碼復(fù)用&和我們需要學(xué)習(xí)前輩們的經(jīng)驗不矛盾，也不代表我們不需要不學(xué)習(xí)。排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的數(shù)據(jù)元素調(diào)整為“有序”的數(shù)據(jù)元素。排序數(shù)學(xué)定義：假設(shè)含n個數(shù)據(jù)元素的序列為R1,R2,，Rn其相應(yīng)的關(guān)鍵字序列為K1,

29、K2,，Kn這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系：Kp1<Kp2<<Kpn按此固有關(guān)系將上式記錄序列重新排列為Rp1,Rp2,，Rpn的操作稱作排序排序的穩(wěn)定性如果在序列中有兩個數(shù)據(jù)元素ri和rj,它們的關(guān)鍵字ki=kj,且在排序之前，對象ri排在rj前面。如果在排序之后，對象ri仍在rj前面，則稱這個排序方法是穩(wěn)定的；否則稱這個排序方法是不穩(wěn)定的。多關(guān)鍵字排序排序時需要比較的關(guān)鍵字多余一個排序結(jié)果首先按關(guān)鍵字1進行排序當關(guān)鍵字1相同時按關(guān)鍵字2進行排序/當關(guān)鍵字n-1相同時按關(guān)鍵字n進行排序/對于多關(guān)鍵字排序，只需要在比較操作時同時考慮多個關(guān)鍵字即

30、可！排序中的關(guān)鍵操作比較任意兩個數(shù)據(jù)元素通過比較操作確定先后次序交換數(shù)據(jù)元素之間需要交換才能得到預(yù)期結(jié)果內(nèi)排序和外排序內(nèi)排序整個排序過程不需要訪問外存便能完成外排序待排序的數(shù)據(jù)元素數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成排序的審判/時間性能關(guān)鍵性能差異體現(xiàn)在比較和交換的數(shù)量輔助存儲空間為完成排序操作需要的額外的存儲空間必要時可以“空間換時間”算法的實現(xiàn)復(fù)雜性過于復(fù)雜的排序法會影響代碼的可讀性和可維護性，也可能影響排序的性能總結(jié)排序是數(shù)據(jù)元素從無序到有序的過程排序具有穩(wěn)定性，是選擇排序算法的因素之一比較和交換是排序的基本操作多關(guān)鍵字排序與單關(guān)鍵字排序無本質(zhì)區(qū)別排序的時間性能是區(qū)分排序算法好

31、壞的主要因素選擇法基本思想每一趟（例如第i趟，i=0,1,n-2）在后面n-i個待排的數(shù)據(jù)元素中選出關(guān)鍵字最小的元素，作為有序元素序列的第i個元素。排序過程'首先通過n-1次關(guān)鍵字比較，從n個記錄中找出關(guān)鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關(guān)鍵字次小的記錄，將它與第二個記錄交換重復(fù)上述操作，共進行n-1趟排序后，排序結(jié)束i-2一趟二二趟;三趟二四趟二五趟:六趟:排序結(jié)束;例i=l初始:耳7764965132738132738132738132738132738494949766597977665769749657697假設(shè)排序過程中，待排數(shù)

32、據(jù)元素序列的狀態(tài)為:有序序列R0-i-l無序序列Ri+*n第i瓶簡單選擇排序從中選出關(guān)鍵字最小的元素有序序列HO.i無序序列Ri+l.n插入排序基本思想：元素i個元素，排序過程：整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列,然后從第2個記錄開始，逐個進行插入，直至整個序列有序?qū)嵸|(zhì)：對線性表執(zhí)行n-1次插入操作，只是先要找到插入位置V0,V1,，Vi-1已經(jīng)排好序。這時已經(jīng)排好序。這時，用Vi的關(guān)鍵字與Vi-1,Vi-2,的關(guān)鍵字進行比較，找到插入位置即將Vi插入，原來位置上的對象向后順移。插入排序關(guān)鍵點：1、拿出一個元素，留出位置、2符合條件的元素后移例i=l(493

33、86597761327I戶238(3849)6597761327尸365(384965)977613271-497(38496597)761327j=576(3849657697)1327i=613(133849657697)彳7>«»»«JJJJJJ排序結(jié)果：(13273849657697)冒泡排序排序過程將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)餞字進行比較，著為逆序r1.key>r2.key,則交換：然后比較第二個記錄與第三個記錄；依次類推1r宜至第n-1個記錄和第0個記錄比較為止弟一越冒泡排序.結(jié)果關(guān)鍵字般大的記錄被安置在Jft后一個記錄上

34、對前n，1個記錄進行第二趟官泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置重復(fù)上述過程，宜到“在一趟排序過程中沒有迸行過交換記聲的蜂作好為止TnstmE)intaQl1J5，inti.；t;prinvfCinpul1。numbers=nw);for(i=1iVl1;"+)scan£C”%d.&a：i)孑printf<n”>?for<j=1；j<l=9;jHfor(i=1?i=joj*i-1-十)if£«iQAai+J二)t=aCil(aLi21=aIi-l-1Jprintf<thesortednumbers

35、士forG=1TVI：i十+)printf(%d。白口).算法冉改進123654上述冒泡排序還可做如下改進：即記住最后一次交換發(fā)生位置lastExchangc泡排序.在“自下向上”冒泡車布趟掃描中，記住最后一次交換發(fā)生的位一置：lastExchange,位置之前的相鄰記錄均已有序).下一趟排序開始時，R|L.lastExchange-11是有序區(qū)，RlastExchangcj是無序區(qū).這樣一趟排序可能使當前有序區(qū)擴充多個記錄，從而減少排序的趟數(shù)，有獎?wù)骷摮绦騋希爾排序排序過程：先取一個正整數(shù)d1<n,把所有相隔di的記錄放一組，組內(nèi)進行直接插入排序;然后取d2<d1,重復(fù)上述分組

36、和排序操作；直至di=1,即所有記錄放進一個組中排序為止OQ(nlogn)希爾排序是不穩(wěn)定的。例初始t4938659776132748554取dl=5一趟分組：49386597613274S554一趟排序：13274855449386、9776取d2=3二趟分組：1327485544938659776二趟排序：1344838274955659776取d3=l二趟分組：13448382749556597761三趟排序：4132738484955657697快速排序思想：快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，基準數(shù)據(jù)排在這兩個子序列的中間；然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。：對rst中記錄進行一趟快速排序,附設(shè)兩個指針i和j,設(shè)x-rp.key而始辭令仁s產(chǎn)t首先從j所指位置向前才的記錄，并和rp交換:記錄rp=rs.第一個關(guān)鍵字從后向刖再犍字位置起向后搜索，找到第一個關(guān)記錄，和甲交換；從前向