C++程序設(shè)計課程設(shè)計指導書計算機工程系二〇〇九年二月-XX.-1—刖百“C++程序設(shè)計”是計算機科學與技術(shù)、通信工程等專業(yè)最重要的一門專業(yè)基礎(chǔ)課程,涉及知識點多,教、學難度非常大,往往費了大量時間而達不到預(yù)期效果。俗語說:學習的最好方法是實踐。本課程設(shè)計正是基于此目的,力求為學生提供ー個理論聯(lián)系實際的機會,通過布置一定難度的課題，要求學生獨立完成。通過實踐，建立課程設(shè)計的整體思想，鍛煉編寫程序、調(diào)試程序的能力,學習文檔編寫規(guī)范,培養(yǎng)獨立學習、吸取他人經(jīng)驗、探索前沿知識的習慣,樹立團隊協(xié)作精神。指導書中的綜合選題可以分成幾個小項目供學生分工合作,其中給出的代碼已經(jīng)有意識地予以變化或刪減,在ー些關(guān)鍵之處有意設(shè)置了一點錯誤，直接復(fù)制一般難以調(diào)試通過,或難以達到預(yù)期的目的。同學們應(yīng)該加以分析,補充完整,并盡可能地增加功能。同學們應(yīng)注意小組成員之間共同研究技術(shù)難題，培養(yǎng)團隊協(xié)作精神。書中給出的實例概念清楚,體系完整,內(nèi)容豐富，采用循序漸進的方式,提高學生實際動手能力,完成“知識+實踐=技能”的整個學習過程。TOC\o"1-5"\h\z刖言 I\o"CurrentDocument"選題ー幻方 1\o"CurrentDocument"ー、奇數(shù)階幻方的制作 1\o"CurrentDocument"二、偶數(shù)階幻方的制作 3\o"CurrentDocument"三、設(shè)計要求 6\o"CurrentDocument"選題二矩陣操作 7\o"CurrentDocument"ー、矩陣翻轉(zhuǎn) 7\o"CurrentDocument"二、矩陣卷動 7\o"CurrentDocument"三、矩陣旋轉(zhuǎn) 8\o"CurrentDocument"四、設(shè)計要求 9\o"CurrentDocument"選題三漢諾塔 10\o"CurrentDocument"一、基本涵義 10\o"CurrentDocument"二、常規(guī)解法 10\o"CurrentDocument"三、設(shè)計要求 11\o"CurrentDocument"選題四ハ皇后 12\o"CurrentDocument"ー、基本涵義 12\o"CurrentDocument"二、設(shè)計要求 12\o"CurrentDocument"選題五成績管理 14\o"CurrentDocument"ー、設(shè)計要求 14\o"CurrentDocument"二、參考イ弋碼 14\o"CurrentDocument"選題六H編碼 29一?、ー兀H碼 29二、m元H碼 30\o"CurrentDocument"選題七數(shù)據(jù)排序 33\o"CurrentDocument"ー、基本概念 33\o"CurrentDocument"二、插入排序 33\o"CurrentDocument"三、交換排序 35\o"CurrentDocument"四、選擇排序 37\o"CurrentDocument"五、歸并排序 39\o"CurrentDocument"六、設(shè)計要求 40\o"CurrentDocument"選題ハ數(shù)據(jù)查找 42\o"CurrentDocument"一、基本概念 42\o"CurrentDocument"二、順序查找 42\o"CurrentDocument"三、二分查找 44\o"CurrentDocument"四、索引查找 46\o"CurrentDocument"五、散列查找 49\o"CurrentDocument"選題九最短路徑 60\o"CurrentDocument"一?、圖概念 60\o"CurrentDocument"二、圖的表示方法 64\o"CurrentDocument"三、帶權(quán)圖的最短路徑 66\o"CurrentDocument"四、設(shè)計要求 69\o"CurrentDocument"選題十表達式求值 70\o"CurrentDocument"ー、基本概念 70\o"CurrentDocument"二、棧的存儲和運算 70\o"CurrentDocument"三、表達式求值 73\o"CurrentDocument"五、參考代碼（不能直接運行） 76\o"CurrentDocument"附錄A課程設(shè)計操作規(guī)程 81\o"CurrentDocument"二、實踐環(huán)境與教學要求 81\o"CurrentDocument"三、實施原則、方案與步驟 81\o"CurrentDocument"五、成績評定規(guī)則..二 83\o"CurrentDocument"六、說明 83\o"CurrentDocument"附錄BC/C++常用函數(shù) 85\o"CurrentDocument"緩沖區(qū)操作函數(shù) 85\o"CurrentDocument"字符分類函數(shù) 86\o"CurrentDocument"數(shù)據(jù)轉(zhuǎn)換函數(shù) 88\o"CurrentDocument"目錄控制函數(shù) 91\o"CurrentDocument"文件處理函數(shù) 92\o"CurrentDocument"數(shù)學函數(shù) 96\o"CurrentDocument"輸入和輸出函數(shù) 101\o"CurrentDocument"進程控制函數(shù) 116\o"CurrentDocument"查找和分類函數(shù) 116\o"CurrentDocument"字符串操作函數(shù) 117選題ー幻方所謂幻方,就是一個n行n列的正方形,共有ザ個格子,將1、2、3 ザ這些數(shù)字放到這些格子里，使其每行的和、每列的和及兩條對角線的和都是一個相同的數(shù)S,S稱為幻和。當n為奇數(shù)時，稱為奇數(shù)階幻方，當n為偶數(shù)時，稱為偶階幻方。當n可被4整除時，稱方為雙偶幻方。當n不可被4整除時，稱為單偶幻方。多少年來，許多數(shù)學家都在研究這個古老而有趣的問題,試圖找出?般的解法，但一般都是針對當n是奇數(shù)和n是4的倍數(shù)的情況。當n是奇數(shù)時的算法:首先，將1放在第一行中間一個格子里。其次，依次將后一個數(shù)放到前一個數(shù)的右上格,如:將2放到1的右上格。將3放到2的右上格等等?？赡艹霈F(xiàn)下面的情況。①若右上格從上面超出,則將后ー?數(shù)放到與右上格同列的最后一行。②若右上格從右面超出,則將后一數(shù)放到與右上格同行的最后一列。③若右上格既從右面超出又從上面超出，則將后一數(shù)放到前數(shù)的下面。④若右上格已被數(shù)字填充,則將后一數(shù)放到前ー數(shù)的下面依以上法則，你可以很快的寫出奇數(shù)階幻方!當然，這中寫法只是其中一個答案，而不是唯一答案。ー、奇數(shù)階幻方的制作.連續(xù)擺數(shù)法例:ー個5/5格子,由最上面一行中間一格開始,依次填1,2,3等等。下ー個格子填在左上位置。但是要注意兩點:出了幻方的范圍，右邊接到左邊，下邊接到上邊。某一格右上已經(jīng)有了數(shù)字，改填在這個格子的下面一格，然后延續(xù)前面的方法。17241815235714164613202210121921311182529也不一定按照斜上方寫字，可以走馬步，或其他方法。下面用的是馬步，得到的是泛對角幻方。

81711524112591821931221102262041351423716哪些“步子”是可行的,是需要注意的?個問題。.階梯法例:以5階為例。第一步:畫一個9x9的方格。如下斜著填數(shù)字。注意中間的5x5格子オ是要作的幻方的位置,已經(jīng)涂成了黃色。第二步:第二步:去掉外圍的格子,就得到所要作的幻方。

3|22~二、偶數(shù)階幻方的制作偶數(shù)階幻方的制作比較復(fù)雜,下面介紹幾個方法。し對稱法,適用于雙偶數(shù)階幻方例:以8階幻方為例。第一步:在左上4,4格子中,取一半的格子,要求每行每列都取到2個。如下圖黃色格子所示。第二步：按照左右對稱、上下對稱、中心對稱的方法把這8個格子擴充為32個格子。第三步：從左上角開始，從左到右從上到下，從1開始填數(shù)。不過只填沒有選中的格子（即沒有涂黃色的格子）

第四步:從右卜角開始從右到左從ド到上在選中的格子里填進剛オ沒有填的數(shù)字。64262455975795511535214501617471945442242244026382829353133323430363727392541234321204618484915511312541056858660613631制作成功。這個方法可以產(chǎn)生不同的雙偶數(shù)階幻方。思考:能否算出這個方法可以產(chǎn)生多少個8階幻方?2.斯特雷奇法,適用于單偶數(shù)幻方例：設(shè)階數(shù)n=2(2m+1)=6,m=!〇第一步：把方陣分為4個小方陣,位置依次為A左上,B右下,C右上,D左下。用連續(xù)擺數(shù)法,把1一aA2放在A中成第一個幻方;把aA2+l?2aA2放在B中成第二個幻方。把2aA2+1?3aA2放在C中成第三個幻方。把3aA2+1?4aA2放在D中成第四個幻

3516261924332721232531922227208283317101530534121416436291318223.LUX方法這是劍橋大學康韋教授發(fā)明的方法例:設(shè)階數(shù)n=2(2m+l)=10,m=2?1L23L16L4L21L15L14L7L18L11L24L17L13U9L2L20U8U19L12U6U5X3X10X22X25X第三步:作一個10x1。方格,設(shè)想為每2*2為ー個單位,每個單位相應(yīng)于上面一個格子。

對應(yīng)于5階幻方中數(shù)字1的單位填1,2,3,4。對應(yīng)于5階幻方中數(shù)字2的填5,6,7,8〇等等。但是標有字母L的按照“右上一左下ー右下一左上’’次序:標有字母U的按照“左上三、設(shè)計要求編寫代碼,實現(xiàn)奇、偶數(shù)幻方的制作。運行程序后,出現(xiàn)下面的參考界面:幻方制作.奇數(shù)階幻方.偶數(shù)階幻方請選擇（1或2,0：退出）:選擇ー個菜單后,要求輸入幻方的階數(shù)n。n的取值范圍為3?10。輸入n后,首先判斷是否存在對應(yīng)階的幻方，如果存在,則顯示幻方制作效果。選題二矩陣操作一、矩陣翻轉(zhuǎn)沿某中心軸翻轉(zhuǎn),或垂直,或水平翻轉(zhuǎn)。翻轉(zhuǎn)的實質(zhì)是,矩陣的每行(或每列)元素進行倒序排放。0123012312'4112124,12165:923239；5638:734347:834556：67787867：5645二、矩陣卷動可以左右、上下卷動。如下圖:012301231241224121659235923638734873434556677856677845矩陣卷動涉及二個問題:(1)卷動方向,或左右卷動,或上下卷動。(2)卷動幅度T,如上下卷動行數(shù)，左右卷動列數(shù)。卷動的實質(zhì)是將某行或某列元素循環(huán)移位。上下卷動時,是將每列元素循環(huán)移位,左右卷動時是將每行元素循環(huán)移位,卷動方向決定是左移還是右移。ー維數(shù)組的循環(huán)移位問題:如，已知inttemp[10],將其循環(huán)右移一位。顯然,移位后,

temp[8]?temp[〇]依次存入temp[9]?temp[l]而原來的temp[9]則返冋數(shù)組起始部位,存入temp[〇]〇那么,循環(huán)右移W位呢?循環(huán)左移W位呢?了解了一維數(shù)組循環(huán)移位問題后,顯然,矩陣卷動無非是多個ー維數(shù)組循環(huán)移位,只要在外層加個大循環(huán)就解決了。三、矩陣旋轉(zhuǎn)矩陣旋轉(zhuǎn)(繞中心點)涉及二個方面:(1)旋轉(zhuǎn)方向，順時針還是逆時針。(2)旋轉(zhuǎn)角度，如90°、180°、270°、360°等。分析:(1)考慮旋轉(zhuǎn)方向、角度(2)此處僅考慮方陣情況，即矩陣行、列數(shù)相同。(3)考慮是奇次方陣還是偶(3)考慮是奇次方陣還是偶次方陣。(4)旋轉(zhuǎn)時，實質(zhì)是數(shù)組元素的重新組合，(5)設(shè)方陣有K圈,每圈操作過程相似。因此,問題的關(guān)鍵是某圈元素的旋轉(zhuǎn)、交換如下圖。i=0VV對應(yīng)交換元素值。/彳階方陣,N=5,\/,共3圈,實際只\!需考慮2圈,即 i\i=0、1的情況。23\34\、 、 \所以,階數(shù)括5*8 與圈數(shù)的關(guān)廠! 系為:K=N/2o7丿34夕考慮幾種特殊情況,如90°,180°,270°,360°等。（1）其它角度都是90°的整數(shù)倍。因此,設(shè)計時僅需要考慮90°情況,其它情況只需重復(fù)操作若干次即可。以順時針旋轉(zhuǎn)為例，如需旋轉(zhuǎn)180°,只需將旋轉(zhuǎn)90°操作連續(xù)執(zhí)行兩次即能實現(xiàn)。（2）逆時針旋轉(zhuǎn)可以看作為“過度”旋轉(zhuǎn)，如逆時針90°,可認為是順時針旋轉(zhuǎn)2700。當然，也可設(shè)計新的交換規(guī)則。四、設(shè)計要求編寫代碼,實現(xiàn)矩陣的翻轉(zhuǎn)、卷動和旋轉(zhuǎn)。運行程序后，隨機生成一個元素為三位正整數(shù)的5X5矩陣，并顯現(xiàn)下面的參考界面:矩陣操作矩陣翻轉(zhuǎn)

矩陣卷動

矩陣旋轉(zhuǎn)請選擇（1、2或3,0：退出）:選擇ー個菜單后,要求輸入操作的方向、行數(shù)或列數(shù)或角度,輸入后，顯示操作結(jié)果。選題三漢諾塔ー、基本涵義在印度,有這么ー個古老的傳說:在世界中心貝拿勒斯（在印度北部）的圣廟里,ー塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候,在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔（如下圖）。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片:一次只移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一一概針上時，世界就將在一聲霹靂中消滅,梵塔、廟宇和眾生都將同歸于盡。故漢諾塔問題又被稱為“世界末日問題?！毖蔟埶栴}的沏始模型r2AL1ZL,eL16￡| 1這是一個典型問題。由于問題中給出的圓盤移動條件是:一次僅能移動ー個盤，且不允許大盤放在小盤的上面，這樣64個盤子的移動次數(shù)為:18,446,744,073,709,511,615（次）這是個天文數(shù)字，若每一微秒可以計算（并不輸出）一次移動，那麼也需要幾乎ー百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔，但0前計算機的速度還不能解決64曾的漢諾塔。二、常規(guī)解法按照上面的方法分析問題，找到移動圓盤的的遞歸算法:設(shè)要解決的的漢諾塔共有N個圓盤，對A桿上的全部N個圓盤從小到大順序編號，最小的圓盤為1號,次之為2號,依次類推，則最ド面的圓盤的編號為N。第一步:先將問題簡化。假設(shè)A桿上只有一個圓盤,即漢諾塔只有一層N1.則只要將1號盤從A桿上移到B桿上即可。第二步:對於ー個有N（N>1）個圓盤的漢諾塔,將N個圓盤分成兩部分:上面的N-1個圓盤和最下面的N號圓盤。第三步：將’‘上面的N—1個圓盤”看成一個整體，為了解決N個圓盤的漢諾塔，可以按下面圖示的方式逕行操作：（1）將A桿上面的N—1個盤子，借助B桿，移到C桿上：(2)將A桿上剩余的N號盤子移到B桿上;(3)將C桿上的N-1個盤子,借助A桿,移到B桿上。N-1整理上述結(jié)果,把第一步中化簡問題的條件作為遞歸結(jié)束條件,將第三步分析得到的算法作為遞歸算法,可以寫出如下完整得遞歸算法描述。三、設(shè)計要求編寫代碼，用兩種方法解決盤子的移動。運行程序后，顯現(xiàn)下面的參考界面:漢諾塔.遞歸解法.非遞歸解法請選擇(1或2,0：退出):選擇ー個菜單后,要求輸入盤片數(shù)目,輸入后,顯示移動過程及結(jié)果。選題四 ハ皇后ー、基本涵義ハ皇后問題是ー個古老而著名的問題。該問題是十九世紀著名的數(shù)學家高斯1850年提出:在8X8格的國際象棋上撰放八個皇后,使其不能互相攻擊,即任意兩個皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解,后來有人用圖論的方法解出92種結(jié)果。顯然問題的鍵在于如何判定某個皇后所在的行、歹リ、斜線上是否有別的皇后;可以從矩陣的特點上找到規(guī)律，如果在同一行,則行號相同;如果在同一列上，則列號相同;如果同在“/”斜線上的行列值之和相同;如果同在“ヽ”斜線上的行列值之差相同;如果斜線不分方向，則同一斜線上兩皇后的行號之差的絕對值與列號之差的絕對值相同。從下圖可以驗證上面的說法:對于ー組布局我們可以用一個ー維數(shù)組來表示:X:ARRAY[1..8]OFINTEGER;X國的下標I表示第I個皇后在棋盤的第I行,X[I]的內(nèi)容表示在第I行的第X[I]列，例如:X[3]=5就表示第3個皇后在第3行的第5歹リ。在這種方式下，要表示兩個皇后A和B不在同一列或斜線上的條件可以描述為：X[A]oX[B]ANDABS(A-B)oABS(X[A]-X[B]){A和B分別表示兩個皇后的行號}。二、設(shè)計要求編寫代碼,用至少三種方法解決八皇后問題。運行程序后，顯現(xiàn)ト面的參考界面:ハ皇后問題

.方法一.方法二.方法三

請選擇(1、2或3,0：退出)：選擇ー個菜單后,要求輸入棋盤的階層,即N。輸入后,顯示共有多少種布局方案,并顯示每一種方案的具體情況，如下圖:(0,2)(1,0)(2,6)(3,4)(4,7)(5,1)(6,3)(75)(0,7)(1,1)(2,4)(3,2)(4,0)(5,6)(6,3)(7^)第77種第77種狀態(tài)為:*****@**十******。****@*********@*@*********@*****第78種狀態(tài)為:*****@*****@**********@*@*********@*********Q****@*************Q選題五 成績管理ー、設(shè)計要求由于同學們已經(jīng)學習了指針、鏈表、文件讀寫等基本知識,為了與后續(xù)課程,如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)等有一個知識體系上的銜接,特設(shè)置ー個信息管理類的課題《成績管理系統(tǒng)》,其它諸如人事管理、學籍管理、圖書管理、通訊錄管理等,結(jié)構(gòu)類似,僅管理對象有所不同。管理內(nèi)容包括:學號、姓名、班級、五門課成績。主要功能有:添加、修改、刪除、讀出、寫入、查找、排序、計算總分、平均分、分類匯總等。編寫代碼，運行程序后，顯現(xiàn)ト面的參考界面：成績管理.輸入學生成績.修改學生成績.刪除學生成績.計算每位學生的總分.計算每位學生的平均分.按學號或姓名查詢學生成績.按班級查詢學生成績.成績排序.按班級統(tǒng)計學科總分、平均分等請選擇（1?9,0:退出）：選擇ー個菜單后，顯示結(jié)果。二、參考代碼注意：部分代碼被抽去,不能直接運行。#include"stdio.h*'#includc"stdlib.h"#include''string.h"include"conio.h"#include"mem.h"#includc"ctype.h”#include"alloc.hH/*I/O#include"stdio.h*'#includc"stdlib.h"#include''string.h"include"conio.h"#include"mem.h"#includc"ctype.h”#include"alloc.hH/?其它說明?//?字符串函數(shù)?//?屏幕操作函數(shù)?//?內(nèi)存操作函數(shù)?//?字符操作函數(shù)?//?動態(tài)地址分配函數(shù)?/#defineN3 /?定義常數(shù)?/typedefstructzl /?定義數(shù)據(jù)結(jié)構(gòu)?/charno[ll];charname[15];intscore[N];floatsum;floataverage;intorder;structzl*next;}STUDENT;/?以下是函數(shù)原型?/STUDENT*init(); /?初始化函數(shù)?/STUDENT*create(); /?創(chuàng)建鏈表?/STUDENT*delete(STUDENT*h); /*刪除記錄?/voidprint(STUDENT*h); /?顯示所有記錄?/voidsearch(STUDENT*h); /*查找ッvoidsave(STUDENT*h); /?保存?/STUDENT*load(); /?讀入記錄ッvoidcomputer(STUDENT*h);/*計算總分和均分?/STUDENT*insert(STUDENT*h); /*插入記錄ッvoidappend(); /?追加記錄ッvoidcopy(); /?復(fù)制文件?/STUDENT*sort(STUDENT*h); /*排序?/STUDENT*index(STUDENT*h);/*索引?/voidtotal(STUDENT*h); /*分類合計*/intmenu_select(); /?菜單函數(shù)?//******キ函數(shù)開始*******/main()(inti;STUDENT*hcad; /*鏈表定義頭指針ッhead=init(); /*初始化鏈表?/clrscr(); /?清屏?/for(;;) /*無限循環(huán)ッ{switch(menu_select()) /?調(diào)用主菜單函數(shù),返回值整數(shù)作開關(guān)語句的條件?/{ /?值不同,執(zhí)行的函數(shù)不同,break不能省略?/caseO:head=init();break; /?執(zhí)行初始化?/casel:head=create();break;/?創(chuàng)建鏈表?/case2:head=delete(head);break;/?刪除記錄?/case3:print(head);break; /?顯示全部記錄?/case4:search(head);break;/?査找記錄?/case5:save(hcad);break;/?保存文件?/case6:head=load();break;/?讀文件?/case7:computer(head);break;/?計算總分和均分?/case8:head=insert(head);break;/?插入記錄?/case9:copy();break; /?復(fù)制文件?/case10:head=sort(head);break;/?排序?/case11:append();break;/?追加記錄?/case12:head=index(head);break;/?索引?/case13:total(head);break; /?分類合計ッcase14:exit(0); /?如菜單返回值為14程序結(jié)束*//?菜單函數(shù),返回值為整數(shù)?/menu_select()char*menu[]=/char*menu[]=/?定義菜單字符串數(shù)組ッ“0.initlist”, /?初始化?/"1.Enterlist", /?輸入記錄?/"2.Deletearecordfromlist"，/?從表中刪除記錄?/"3.printlistn, /?顯示單鏈表中所有記錄?/"4.Searchrecordonname”， /?按照姓名查找記錄ッ”5.Savethefile”， /?將單鏈表中記錄保存到文件中?/”6.Loadthefile”， /?從文件中讀入記錄?/”7.computethescore”，/?計算所有學生的總分和均分?/”8.insertrecordtolistn,/?插入記錄到表中?/”9.copythefiletonewfile”， /?復(fù)制文件?/”10.sorttomakenewfile", /?排序?/”11.appendrecordtofile”， /?追加記錄到文件中?/M12.indexonnomber”， /*索弓I*/M13.totalonnomber”， /?分類合計?/”14.Quit”}; /?退出?/chars[3]; /?以字符形式保存選擇號?/intc,i; /?定義整形變量?/gotoxy(l,25); /*移動光標*/printfi(”pressanykeyentermenu \n”)； /?壓任一鍵進入主菜單ッgetch(); /*輸入任一鍵ッclrscr(); /?清屏幕?/gotoxy(l,l); /?移動光標ッtextcolor(YELLOW); /*設(shè)置文本顯示顏色為黃色?/textbackground(BLUE); /*設(shè)置背景顏色為藍色?/gotoxy(10,2); /*移動光標?/putch(0xc9); /?輸出左上角邊框廠?/fbr(i=l;i<44;i++)putch(Oxcd); /*輸出上邊框水平線ッputch(Oxbb); /?輸出右上角邊框 */fbr(i=3;i<2O;i++){gotoxy(lO,i)；putch(Oxba); /*輸出左垂直線?/gotoxy(54,i)；putch(0xba);} /*輸出右垂直線?/gotoxy(10,20);putch(0xc8);/?輸出左上角邊框'-*/fbr(>=l；i<44;i++)putch(Oxcd);/?輸出下邊框水平線?/putch(Oxbc);/?輸出右下角邊框」?/window(l1,3,53,19);/?制作顯示菜單的窗口,大小根據(jù)菜單條數(shù)設(shè)計?/clrscr();/?清屏?/fbr(i=0;i<16;i++)/?輸出主菜單數(shù)組?/gotoxy(10,i+l);cprintf("%s",menu[i]);}textbackground(BLACK); /?設(shè)置背景顏色為黑色?/window(1,1,80,25); /*恢復(fù)原窗口大小?/gotoxy(10,21); /?移動光標?/do{printf("\nEnteryouchoice(0~14):"); /?在菜單窗口外顯示提示信息?/scanf("%s",s); /?輸入選擇項?/c=atoi(s); /?將輸入的字符串轉(zhuǎn)化為整形數(shù)?/}while(c<0||c>14); /?選擇項不在0-14之間重輸?/returnc; /?返回選擇項,主程序根據(jù)該數(shù)調(diào)用相應(yīng)的函數(shù)?/}STUDENT*init()(returnNULL;/?創(chuàng)建鏈表?/STUDENT*create()(inti;ints;STUDENT*h=NULL,*info;/*STUDENT指向結(jié)構(gòu)體的指針?/M；；){infb=(STUDENT*)malloc(sizeofl[STUDENT));/?申請空間?/if(!info) /?如果指針infb為空?/(printf("\noutofmemory");/?輸出內(nèi)存溢出?/returnNULL; /?返回空指針?/inputs("enterno:",info->no,ll); /?輸入學號并校驗?/if(infb->no[0]='?')break; /*如果學號首字符為@則結(jié)束輸入?/inputs("entername:",infb->name,15);/*輸入姓名,并進行校驗?/printff'pleaseinput%dscore\n",N);/?提示開始輸入成績?/s=0; /?計算每個學生的總分,初值為0?/fbr(i=O;i<N;i++)/*N門課程循環(huán)N次?/(do(printf(Hscore%d:",i+1); /*提示輸入第幾門課程?/scanfi(n%dn,&infb->score[i]); /*輸入成績ッif(infb->score[i]>K)0||infb->score[i]vO)/?確保成績在0-100之間?/printfi(”baddata,repeatinput\nH);/?出錯提示信息?/}while(infb->score[i]>100||infb->score[i]<0);s=s+info->score[i]; /*累加各門課程成績?/)infb->sum=s; /?將總分保存?/infb->average=(float)s/N;/?求出平均值?/info->order=0; /*未排序前此值為0*/infb->next=h; /*將頭結(jié)點做為新輸入結(jié)點的后繼結(jié)點?/h=infb; /?新輸入結(jié)點為新的頭結(jié)點?/)retum(h); /?返回頭指針ッ}/?輸入字符串,并進行長度驗證?/inputs(char*prompt,char*s,intcount)charp[255];do{printf(prompt);/?顯示提示信息?/scanff%s”,p);/*輸入字符串?/if(strlen(p)>count)printfi(n\ntoolong!\n")；/?進行長度校驗,超過count值重輸入*/}while(strlen(p)>count);strcpy(s,p);/*將輸入的字符串拷貝到字符串s中?/}/?輸出鏈表中結(jié)點信息?/voidprint(STUDENT*h)(inti=0; /?統(tǒng)計記錄條數(shù)?/STUDENT*p;/*移動指針ッclrscr(); /?清屏?/p=h; /*初值為頭指針ッ

*************************3)printf(M|rec|nOprintffl—I while(p!=NULL)nameIsel|sc2|sc3|sum|ave|order|\nM);*************************3)printf(M|rec|nOprintffl—I while(p!=NULL)nameIsel|sc2|sc3|sum|ave|order|\nM); 1——I——|\n");i++；printffl%3d|%-10s|%-15s|%4d|%4d|%4d|%4.2f|%4.2f|%3d|\n”,i,p->no,p->name,p->score[0],p->score[1],p->score[2],p->sum,p->average,p->order);p=p->next;)pnnt***********************************end*********************************\n./?刪除記錄?/STUDENT*delete(STUDENT*h)STUDENT*p,*q;/*p為查找到要刪除的結(jié)點指針,q為其前驅(qū)指針ッchars[ll]; /?存放學號?/clrscrO; /?清屏?/printfi(Hpleasedeletedno\nH);/?顯示提示信息?/seanf("％s”,s); /*輸入要刪除記錄的學號?/q=p=h; /*給q和p賦初值頭指針ッwhile(strcmp(p->no,s)&&p!=NULL) /?當記錄的學號不是要找的,或指針不為空時?/q=p;p=p->next;/?將p指針值賦給q作為p的前驅(qū)指針?/

/?將p指針指向下一條記錄ッifi(p=NULL)/?如果p為空,說明鏈表中沒有該結(jié)點?/printf(M\nlistno%sstudent\nH,s);else/*p不為空,顯示找到的記錄信息?/^^und***************************\n”)?printfi(n|noprintffl——name|scl|sc2|sc3|printfi(n|noprintffl——name|scl|sc2|sc3|sumave|order|\nM);W);printfin%?10s|%?15s|%4d|%4d|%4dl%4.2f|%4.2f|%3d|\nM,p->no,p->name,p->seore[0],p->score[1],p->score[2],p->sum,p->average,p->order);print”********************************end*******************************w)getch(); /?壓任ー鍵后,開始刪除*/if(p=h)/*如果p-h,說明被刪結(jié)點是頭結(jié)點?/h=p->next;/?修改頭指針指向下一條記錄?/

elseq?>next=p?>next;/?不是頭指針,將p的后繼結(jié)點作為q的后繼結(jié)點?/free(p); /*釋放p所指結(jié)點空間?/printf("\nhavedeletedNo%sstudent\n",s);printfif'Don'tforgetsave\n");/*提示刪除后不要忘記保存文件?/}retum(h); /?返回頭指針?/}/*査找記錄?/voidsearch(STUDENT*h)(STUDENT*p; /?移動指針?/chars[15]; /?存放姓名的字符數(shù)組?/clrscrO; /?清屏幕?/printfif^pleaseenternameforsearch\nM);scanグ％s”,s); /*輸入姓名?/p=h; /*將頭指針賦給p*/while(strcmp(p->name,s)&&p!=NULL)/?當記錄的姓名不是要找的,或指針不為空時?/p=p->next;/?移動指針,指向下一結(jié)點?/iftp=NULL) /?如果指針為空?/printf(M\nlistno%sstudent\nM,s); /?顯示沒有該學生?/else /?顯示找到的記錄信息?/pr〔n"\n\,n*****************************havei^3und***************************~”).printff'InOprintffl——name|scl|sc2|sc3|sum|ave|order|\nMprintff'InOprintffl—— 1——IーーW);printf(M|%-10s|%-15s|%4d|%4d|%4d|%4.2f|%4.2f|%3d|\nM,p->no,p->name,p->score[0],p->score[l],p->score[2],p->sum,p->average,p->order);”********************************end*******************************、n”)./?插入記錄?/STUDENT*insert(STUDENT*h){STUDENT*p,*q,*info;/*p指向插入位置,q是其前驅(qū),info指新插入記錄?/chars[11];/*保存插入點位置的學號?/intsl,i;printfi("pleaseenterlocationbeforetheno\nH);scanff'%s”,s); /*輸入插入點學號?/printff'\npleasenewrecord\nM); /*提示輸入記錄信息?/info=(STUDENT*)malloc(sizeof(STUDENT));/?申請空間?/if(!info)printfi(n\noutofmemory")； /?如沒有申請到,內(nèi)存溢出?/returnNULL; /?返回空指針ッ)inputs(Menterno:M,infb->no,l1);/?輸入學號?/inputs(Hentername:",infb?>name,15);/?輸入姓名?/printfif^pleaseinput%dscore\n”,N);/?提示輸入分數(shù)*/sl=0; /*保存新記錄的總分,初值為〇*/fbr(i=O;i<N;i++)/*N門課程循環(huán)N次輸入成績ッ|do(/?對數(shù)據(jù)進行驗證,保證在〇?100之間?/printf("score%d:M,i+l);scanf(w%dM,&infb->score[i]);if(infb->score[i]>100||info->seore[i]<0)printff'baddata,repeatinput\nH);}while(infb->score[i]>100||infb->score[i]<0);s1=s1+infb->score[i]; /*計算總分?/)infb->sum=s1; /*將總分存入新記錄中?/infb->average=(float)s1/N;/?計算均分?/infb->order=0; /?名次賦值〇?/info->next=NULL; /?設(shè)后繼指針為空?/p=h; /*將指針賦值給p*/q=h; /?將指針賦值給q*/while(strcmp(p->no,s)&&p!=NULL)/?查找插入位置?/{q=p； /?保存指針p,作為下ー個p的前驅(qū)ッp=p->next; /*將指針p后移?/)iRp=NULL) /?如果p指針為空,說明沒有指定結(jié)點?/if(p=h)/?同時p等于h,說明鏈表為空?/h=infb;新記錄則為頭結(jié)點?/elseq->next=infb;/*p為空,但p不等于h,將新結(jié)點插在表尾字/elseif(p=h)/*p不為空,則找到了指定結(jié)點*/(info->next=p;/*如果p等于h,則新結(jié)點插入在第一個結(jié)點之前?/h=info;/?新結(jié)點為新的頭結(jié)點?/)elseinfb->next=p; /?不是頭結(jié)點,則是中間某個位置,新結(jié)點的后繼為p*/q->next=infb;/?新結(jié)點作為q的后繼結(jié)點?/}printf("\n—haveinserted%sstudent—\n",info->name);printf("—Don'tforgetsave—\n"); /?提示存盤?/retum(h); /?返回頭指針?/}/?保存數(shù)據(jù)到文件?/voidsave(STUDENT*h){FILE*fp; /?定義指向文件的指針?/STUDENT*p; /*定義移動指針?/charoutfile[10];/*保存輸出文件名?/printf("Enteroutfilename,forexamplec:\\fl\\te.txt:\n");/?提示文件名格式信息?/scanf("%s",outfile);if((m=fopen(outfileJwb"))==NULL)/?為輸出打開一個二進制文件，如沒有則建立?/{printff'cannotopenfile\n");exit(1);)printf("\nSavingfile......\n");/*打開文件，提示正在保存?/p=h; /*移動指針從頭指針開始?/while(p!=NULL)/?如p不為空?/(hvrite(p,sizeof(STUDENT),l,fjj);/?寫入一條記錄?/p=p->next;/*指針后移?/)fclose(fp); /*關(guān)閉文件?/printff' savesuccess!! \n");/?顯示保存成功?/}/?從文件讀數(shù)據(jù)?/STUDENT*load()(STUDENT*p,*q,*h=NULL; /?定義記錄指針變量?/FILE*fp; /*定義指向文件的指針?/charinfileu〇]; /?保存文件名?/printff'Enterinfilename,forexamplec:\\fl\\te.txt:\n");scanf("%s",infile); /*輸入文件名?/if((fp=fopen(infile,"rb"))=NULL) /*打開一個二進制文件,為讀方式?/(printf("cannotopenfile\n"); /?如不能打開，則結(jié)束程序?/exit(l);}printf("\n——Loadingfile!ーー\n");p=(STUDENT*)malloc(sizeof(STUDENT));/?申請空間?/if(!p)printf("outofmemory!\n"); /?如沒有申請到,則內(nèi)存溢Hl*/returnh; /?返回空頭指針?/}h=p; /?申請到空間,將其作為頭指針?/while(!feof(fp))/?循環(huán)讀數(shù)據(jù)直到文件尾結(jié)束?/{if<1!=fread(p,sizeof(STUDENT),l,fp))break;/?如果沒讀到數(shù)據(jù)，跳出循環(huán)?/p->next=(STUDENT*)malloc(sizeof(STUDENT));/?為下ー個結(jié)點申請空間?/if(!p->next){printff'outofmemory!\n");/?如沒有申請到，則內(nèi)存溢出?/returnh;}q=p；/?保存當前結(jié)點的指針，作為下ー結(jié)點的前驅(qū)?/p=p->next;/?指針后移，新讀入數(shù)據(jù)鏈到當前表尾?/)q->next=NULL; /*最后一個結(jié)點的后繼指針為空?/fclose(fp); /?關(guān)閉文件?/printff,--Youhavesuccessreaddatafromfile!!!?一\n");returnh; /?返回頭指針?/}/?追加記錄到文件?/voidappend()(FILE*fp;/?定義指向文件的指針?/STUDENT*infb;/?新記錄指針?/intsl,i；charinfile[10]; /?保存文件名?/printf("\npleasenewrecord\n");info=(STUDENT*)malloc(sizeof(STUDENT));/?申請空間?/if(!infb)(printf("\noutofmemory"); /?沒有申請到，內(nèi)存溢出本函數(shù)結(jié)束*/return;)inputs(Henterno:M,infb->no,l1); /?調(diào)用inputs輸入學號?/inputs,entername:",infb?>name15);/?調(diào)用inputs輸入姓名?/printff'pleaseinput%dscore\n",N); /?提示輸入成績ッsl=0;fbr(i=0;i<N;i++)do{printf(Hscore%d:,,,i+l);scanfi(,,%dn,&infb->score[i]);/?輸入成績?/if(infb->score[i]>100||infb->score[i]<0)printff'baddata,repeatinput\nH);}while(infb->score[i]>100||infb?>score[i]v0);/?成績數(shù)據(jù)驗證?/sl=sl+infb->score[i]; /?求總分?/)infb->sum=sl; /?保存總分?/infb->average=(float)sl/N;/?求均分?/info->order=0; /*名次初始值為〇?/infb->next=NULL;/*將新記錄后繼指針賦值為空?/printfif*Enterinfilename,fbrexamplec:\\fl\\te.txt:\nn);scanfi(,,%sH,infile); /*輸入文件名?/ifUm=fopen(inflle,“ab"))=NULL)/?向二進制文件尾增加數(shù)據(jù)方式打開文件?/(printfpcannotopenfile\nM); /?顯示不能打開?/exit(l); /?退出程序?/)printf(M\n Appendingrecord! \nH);if<1!=fwrite(infb,sizeof(STUDENT),1,fp)) /?寫文件操作?/{printR” filewriteerror! \nM);return; /?返回?/)printR” appendsucess!!——\nM);fclose(fp); /?關(guān)閉文件?/}/?文件拷貝ッvoidcopy()(charoutfile[l0],infile[l0];FILE*sfp,*tfp; /?源和目標文件指針ッSTUDENT*p=NULL; /?移動指針?/clrscrO; /?清屏?/printffEnterinfilename,forexamplec:\\fl\\te.txt:\nn);scan^^^%s^^,infile); /*輸入源文件名?/ift(sfp=fopen(infile,nrbH))=NULL) /?二進制讀方式打開源文件?/(printff'cannotopeninputfile\nM);exit(0);}printR”Enteroutfilename,forexamplec:\\fl\\te.txt:\n"); /?提示輸入目標文件名?/scanfC'%sH,outfile);/*輸入目標文件名?/ifi((tfp=fbpen(outfile,"wbM))=NULL)/?二進制寫方式打開目標文件?/{printff'cannotopenoutputfile\nH);exit(O);)while(!feof(sfp)) /?讀文件直到文件尾?/{if(l!=fread(p,sizeof(STUDENT),1,sfp))break;/?塊讀ッfwrite(p,sizeofi(STUDENT),1,tfp)； /*塊寫?/)fclose(sfp);/?關(guān)閉源文件?/fclose(tfp); /*關(guān)閉目標文件?/printf(Hyouhavesuccesscopyfile!!!\nM); /?顯示成功拷貝?/}/*排序?/STUDENT*sort(STUDENT*h)inti=0;/*保存名次?/STUDENT*p,*q,*t,*hl;/*定義臨時指針?/hl=h->next;h->next=NULL;while(hl!=NULL){t=hl;h1=h1->next;P=h；/?將原表的頭指針所指的下ー個結(jié)點作頭指針?//?第一個結(jié)點為新表的頭結(jié)點?//?當原表不為空時，進行排序?//?取原表的頭結(jié)點?//?原表頭結(jié)點指針后移?//?設(shè)定移動指針P,從頭指針開始?/q=h; /?設(shè)定移動指針q做為p的前驅(qū),初值為頭指針?/while(t->sum<p->sum&&p!=NULL)/?作總分比較?/(q=p;/?待排序點值小,則新表指針后移?/p=p->next;}if(p=q)/*P==q,說明待排序點值大,應(yīng)排在首位?/t->next=p;h=t;}/?待排序點的后繼為P*//?新頭結(jié)點為待排序點?/else /?待排序點應(yīng)插入在中間某個位置q和p之間,如p為空則是尾部?/t->next=p;q->next=t;}/*t的后繼是P*//*q的后繼是t*/p=h; /?已排好序的頭指針賦給p,準備填寫名次?/while(p!=NULL)/*當p不為空時,進行下列操作?/{i++； /?結(jié)點序號?/p->order=i; /?將名次賦值?/p=p->next;/?指針后移?/}printf("sortsucess!!!\n"); /*排序成功?/returnh; /?返回頭指針?/}/?計算總分和均值?/voidcomputer(STUDENT*h)(STUDENT*p; /?定義移動指針*/inti=0;/?保存記錄條數(shù)初值為0?/longs=0; /?總分初值為0?/floataverage=0;/?均分初值為〇?/p=h; /?從頭指針開始?/while(p!=NULL)/*當p不為空時處理?/{s+=p->sum; /?累加總分?/i++; /?統(tǒng)計記錄條數(shù)?/p=p->next;/?指針后移?/}average=(float)s/i;/?求均分,均分為浮點數(shù),總分為整數(shù),所以做類型轉(zhuǎn)換?/printf("\n—Allstudentssumscoreis:%ldaverageis%5.2f\n",s,average);)/?索引?/STUDENT*index(STUDENT*h){STUDENT*p,*q,*t,*hl;/?定義臨時指針?/hl=h->next; /?將原表的頭指針所指的下ー個結(jié)點作頭指針?/h->next=NULL; /*第一個結(jié)點為新表的頭結(jié)點?/while(hl!=NULL)/?當原表不為空時,進行排序?/(t=hl; /?取原表的頭結(jié)點?/hl=hl->next;/?原表頭結(jié)點指針后移?/p=h; /?設(shè)定移動指針p,從頭指針開始?/q=h; /?設(shè)定移動指針q做為p的前驅(qū)，初值為頭指針?/while(stremp(t->no,p->no)>0&&p!=NULL)/?作學號比較?/(q=p； /?待排序點值大,應(yīng)往后插,所以新表指針后移?/p=p->next;)if(p=q)/*p==q.說明待排序點值小,應(yīng)排在首位?/t->next=p;/?待排序點的后繼為p*/h=t; /?新頭結(jié)點為待排序點?/)else /?待排序點應(yīng)插入在中間某個位置q和p之間,如p為空則是尾部?/{t->next=p; /*t的后繼是p*/q->next=t; /*q的后繼是t*/})printff'indexsucess!!!\n");/?索引排序成功?/returnh; /?返回頭指針?/)/?分類合計?/voidtotal(STUDENT*h){STUDENT*p,*q; /?定義臨時指針變量?/charsno[9],qno[9],*ptr; /?保存班級號的?/floatsl,ave; /?保存總分和均分?/inti; /?保存班級人數(shù)*/clrscrO; /?清屏?/printW、n\n*******************Total*****************珀printf，…class sum average--\n")；p=h; /?從頭指針開始?/while(p!=NULL)/?當p不為空時做下面的處理?/{memcpy(sno,p->no,8);/?從學號屮取出班級號?/sno[8K0,; /?做字符串結(jié)束標記*/q=p->next; /*將指針指向待比較的記錄?/sl=p->sum; /*當前班級的總分初值為該班級的第一條記錄總分?/ave=p->average;/*當前班級的均分初值為該班級的第一條記錄均分?/i=l； /?統(tǒng)計當前班級人數(shù)?/while(q!=NULL) /?內(nèi)循環(huán)開始?/(memcpy(qno,q->no,8); /?讀取班級號?/qno[8]=W; /*做字符串結(jié)束標記ッif(strcmp(qno,sno)=0)/?比較班級號?/{s1+=q->sum; /?累加總分?/ave+=q->average;/*累加均分*/iH; /?累加班級人數(shù)*/q=q->next; グ指針指向下一條記錄ッelsebreak;/?不是ー個班級的結(jié)束本次內(nèi)循環(huán)ッ)printf(H%s%10.2f %5.2f\n*',sno,sl,ave/i);if(q=NULL)break; /*如果當前指針為空,外循環(huán)結(jié)束,程序結(jié)束?/elsep=q； /?否則,將當前記錄作為新的班級的第一條記錄開始新的比較ッ)printグ XrT);選題六H編碼—、ー兀H碼在通信領(lǐng)域,信息編碼是ー種最基本的理論基礎(chǔ)與技術(shù)手段,可以針對文字、聲音、圖像、視頻、模型等，分為信源編碼、信道編碼。編碼的方法有很多。1952年，一位外國人提出了一ー種逐個符號的編碼方法,姑且稱為H編碼方法。其基本思想如下:設(shè)有n個信號ui,u2,...,un,其概率分布依次為p（uj,p（u,）,...,p（un）,稱為信號值，且滿足下式:p（U］）+p（u2）+...+P（Un）=1簡記為:H碼的編碼步驟可以簡述為：（1）首先將n個信號按值的大小排列。（2）將最小的兩個信號合并成一個新的信號,新信號的值為該兩信號值的和，從而將原n個信號縮減為n—l個信號。（3）把縮減后的信號仍按值遞減排列,然后再將其中最小的兩個信號合并成一個新信號,這樣又縮減為n—2個信號。（4）依此類推，直至只剩下1個信號為止。（5）將每次合并的兩個信號分別用“0”和“ド兩個符號表示。（6）從最后ー級開始，向前返回，就得出各信號所對應(yīng)的符號序列，即為各信號對應(yīng)的碼字。例如:已知U%U2“3 ”4P「［〇.50.250.1250.125其對應(yīng)的H碼如圖所示:信號值縮減后信號值 碼字碼長123325⑵125

信號值縮減后信號值 碼字碼長123325⑵125有兩種編碼過程:信號值 縮減后信號值 碼字碼長%盯%0.10.100101101000.10.1001011010011（め9)碼字碼長0010400114方法⑶的具體原則是,把合并后的信號總是放在其他相同值的信號之上（或之左）,方法（b）則是把合并后的信號值放在其他相同值的信號之下（或之右）。通過分析,方法（a）優(yōu)于方法（b）?方法（a）的方差比方法（b）的方差要小許多。二、m兀H碼上面討論的編碼方法可稱為二元編碼,其思想可推廣到，”元編碼。不同的只是每次把值最小的，n個信號合并成一個新的信號,并分別用0,1,…,團一1等m個符號來表示。對于，n元編碼,信號個數(shù)”必須滿足下式:n=(m-1)Q+m式中:n__信號個數(shù)m——碼元數(shù)Q-縮減次數(shù)對于二元碼,總能找到ー個Q,滿足上式。但對于m元碼,當n為任意正整數(shù)時,不一定

能找到ー個Q滿足上式,此時,可以人為地增加一些值為零的信號以滿足上式。然后取值最小的m個信號合并成一個新信號,并把這些信號的值相加作為該新信號的值，重新由大到小排序，再取最小的m個信號合并,如此下去。m元的H碼編碼步驟如下:(1)驗證所給n是否滿足上式，若不滿足，可以人為地增加一些值為零的信號，以使最后一步有m個信號;(2)取最小的m個符號合并成一個新信號，并分別用0,1，…，m-l給各分支賦值,把這些信號的值相加作為該新信號的值:(3)將新信號和剩下信號重新排序，重復(fù)(2)。(4)從最后ー級開始，向前返回,就得出各信號所對應(yīng)的符號序列，即為各信號對應(yīng)的碼字。后來新加的值為零的信號,雖也賦ア碼字，但實際上是冗余碼字，并未用上，但這樣編成的碼，仍是最佳的,也就是平均碼長最短，如果等值信號排隊時注意到順序，則碼長的方差也是最小的。例如:已知V差也是最小的。例如:已知VP其三元編碼如下圖所示：符號槪率Uj0.4?20.3u30.2u40.05u50.05四元編碼如ド圖：?以］ u2 以3 以4 %,0.4 0.3 0.2 0,05 0.05碼字碼長 0.4 —0 1 A0.3 1 10 2—ノ0.3 —20 2屮 21 2―22 20.400.300.200.050.050.000.00 ―0.30 -0.20碼字0.400.300.200.050.050.000.00 ―0.30 -0.20碼字01230313233碼長1112222要求:編寫代碼,H碼編碼.方法A.方法B請選擇（1或2,0:退出）:選擇ー個菜單后,要求輸入碼元數(shù)N,N取值范圍為2?16。輸入后，顯示編碼結(jié)果。選題七 數(shù)據(jù)排序ー、基本概念排序是數(shù)據(jù)處理中經(jīng)常使用的ー種重要運算。設(shè)文件由n個記錄｛&,R2,……，Rn｝組成,如n個學生記錄,每個學生記錄包括學號、姓名、班級等。n個記錄對應(yīng)的關(guān)鍵字集合為｛K，K2,……，Kn!,如學生的學號。所謂排序就是將這n個記錄按關(guān)鍵字大小遞增或遞減重新排列。當待排序記錄的關(guān)鍵字均不相同時,排序結(jié)果是惟ー的,否則排序結(jié)果不唯一。如果文件中關(guān)鍵字相同的記錄經(jīng)過某種排序方法進行排序之后，仍能保持它們在排序之前的相對次序，則稱這種排序方法是穩(wěn)定的;否則,稱這種排序方法是不穩(wěn)定的。由于文件大小不同使排序過程中涉及的存儲器不同，可將排序分成內(nèi)部排序和外部排序兩類。整個排序過程都在內(nèi)存進行的排序，稱為內(nèi)部排序;反之，若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換,則稱之為外部排序。內(nèi)排序適用于記錄個數(shù)不是很多的小文件,而外排序則適用于記錄個數(shù)太多，不能一次性放人內(nèi)存的大文件。按策略劃分，內(nèi)部排序方法可以分為五類:插入排序、選擇排序、交換排序、歸并排序和分配排序。幾乎所有的排序都有兩個基本的操作:(1)關(guān)鍵字大小的比較。(2)改變記錄的位置。具體處理方式依賴于記錄的存儲形式，對于順序型記錄，一般移動記錄本身，而鏈式存儲的記錄則通過改變指向記錄的指針實現(xiàn)重定位。為了簡化描述,在下面的講解中，我們只考慮記錄的關(guān)犍字，則其存儲結(jié)構(gòu)也簡化為數(shù)組或鏈表。并約定排序結(jié)果為遞增。排序的算法很多,不同的算法有不同的優(yōu)缺點,沒有哪種算法在任何情況下都是最好的。評價ー種排序算法好壞的標準主要有兩條;(1)執(zhí)行時間和所需的輔助空間，即時間復(fù)雜度和空間復(fù)雜度；(2)算法本身的復(fù)雜程度，比如算法是否易讀、是否易于實現(xiàn)。二、插入排序插入排序的基本思想是:每次將一個待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序,直到所有待排序記錄全部插入完成。1.直接插入排序假設(shè)待排序數(shù)據(jù)存放在數(shù)組中，則A[l]可看作是ー個有序序列，讓i從2開始,依次將A[i]插入到有序序列中,A[n]插入完畢則整個過程結(jié)束,成為有序序列。排序過程示例 (用【】表示有序序列)待排序數(shù)據(jù)：【25】548542119727315 (n=10)i=2： [2554] 8 54 21 1 97 2 73 15i=3： [82554] 54 21 1 97 2 73 15i=4[8255454] 2119727315i=5[821255454] 19727315i=6[1821255454] 9727315i=7[182125545497] 27315i=8[1282125545497] 7315i=9[128212554547397] 15i=10： [12815212554547397] 排序結(jié)束算法實現(xiàn)可在數(shù)組中增加元素A[0]作為關(guān)鍵值存儲器和循環(huán)控制開關(guān)。第i趟排序,即A[i]的插入過程為:①保存A[iLA[0]②j=i-1③如果A[j]<=A[0]（即待排序的A[i]）,則A[〇]fA[j+1],完成插入;否則,將A[j]后移ー個位置:A[j]fA[j+l]；j=j-1!繼續(xù)執(zhí)行③對于上面的數(shù)據(jù)實例,i從2依次變化到10的過程中,j值分別為{1,0,3,1,0,6,1,7,3}算法分析穩(wěn)定性:穩(wěn)定時間復(fù)雜度:①原始數(shù)據(jù)正序,總比較次數(shù):n-1原始數(shù)據(jù)逆序,總比較次數(shù):X/,=- =。（パ）i=2 2原始數(shù)據(jù)無序，第i趟平均比較次數(shù)=Z，/i=3,川2總次數(shù)為：-——=0（n2）④可見，原始數(shù)據(jù)越趨向正序，比較次數(shù)和移動次數(shù)越少。?空間復(fù)雜度：僅需ー個單元A[0]2?希爾排序基本思想任取ー個小于n的整數(shù)S,作為增量,把所有元素分成S,個組。所有間距為S,的元素放在同一個組中。第一組：{A[l],A[S]+1],A[2*S）+1],……}第二組：{A[2],A[S,+2],A[2*S（+2], }第三組：（A[3],A[Si+3],A[2*S付3],……}第Si組:{A[S1],A[2*S|],A口?Si],……}先在各組內(nèi)進行直接插入排序;然后,取第二個增量S2(<S|)重復(fù)上述的分組和排序,直至所取的增量St=l(St<S,1<St.2<-<S2<S1),即所有記錄放在同一組中進行直接插入排序為止。序號12345678910原始數(shù)據(jù)1289573296375457957S]=5組別@②③④⑤①②③④⑤排序結(jié)果1254532573789577996S2=3組別①②③①②③①②③①排序結(jié)果1254532573789577996S3=2組別①②①②①②1'②①②排序結(jié)果5321237575479578996S「1組別1①>?