數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計

1、*大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計題 目：數(shù)據(jù)結(jié)構(gòu)上機試題 學(xué)生姓名：學(xué) 號：專 業(yè)：信息管理與信息系統(tǒng)班 級：指導(dǎo)教師：2014 年 04 月目錄一、順序表的操作 2【插入操作原理】 2【刪除操作原理】 2【N0.1代碼】 3【運行截圖演示】 7二、單鏈表的操作10【創(chuàng)建操作原理】 10【插入操作原理】 10【刪除操作原理】 10【N0.2代碼】 11【運行截圖演示】 20三、順序棧的操作25【數(shù)值轉(zhuǎn)換原理】 25【N0.3代碼】 26【運行截圖演示】 30四、查找算法32【順序查找原理】 32【折半查找原理】 32【N0.4代碼】 33【運行截圖演示】 38五、排序算法 40【直接插入排序原

2、理】 40【快速排序原理】 40【N0.5代碼】 41【運行截圖演示】 46亠、順序表的操作(1) 插入元素操作：將新元素x插入到順序表a中第i個位置；(2) 刪除元素操作：刪除順序表 a中第i個元素?！静迦氩僮髟怼烤€性表的插入操作是指在線性表的第i-1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素，就是要是長度為n的線性表：ai , ai 1, ai , an變成長度為n+1的線性表：ai,ai 1,b, ai , an數(shù)據(jù)元素ai i和ai之間的邏輯關(guān)系發(fā)生了變化。(其【插入原理】在課本P23的算法2.3有解釋)【刪除操作原理】反之，線性表的刪除操作是使長度為 n的線性表：ai ,

3、ai 1 , ai , ai 1 , an變成長度為n-1的線性表：ai , ai 1, ai 1 , an數(shù)據(jù)元素ai 1、ai和ai 1之間的邏輯關(guān)系發(fā)生變化，為了在存儲 結(jié)構(gòu)上放映這個變化，同樣需要移動元素。(其【刪除原理】在課本P24的算法2.4有解釋)【NO.1代碼】#in clude#defi ne MAX 100typedef int datatype;typedef structdatatype dataMAX;int list;seque nl ist;/*順序表 */int mai n()int in sert( seque nlist *L, int x, int i )

4、;int deletee( seque nlist *L, int i );int in put( seque nlist *L );int output( seque nlist *L );seque nlist s,*p 二&s;int in data,i nl ocate,deletedx;input(p);printf(請輸入要插入的數(shù)：);sca nf( %d,&in data );printf(請輸入要插入的位置：);sea nf( %d,&in locate );in sert( p,i ndata,i nlocate );prin tf(插入后的數(shù)據(jù)：”)；output(p);

5、printf(請輸入要刪除的位置：);sea nf( %d,&deletedx);deletee( p, deletedx );prin tf(刪除后的數(shù)據(jù)：”)；output(p);return 0;int output( seque nlist *L )int i;for( i=0; ilist; i+ )pri ntf( %d 丄-datai);prin tf( nn);retur n(1);int in put( seque nlist *L )int i;prin tf(請輸入原始數(shù)據(jù)個數(shù)：”);seanf( %d,&( L-list);L-list-;prin tf(請輸入原始數(shù)據(jù)

6、：”)；for( i=0; i list; i+ )seanf( %d,&( L-datai);printf(原始數(shù)據(jù)為：);output(L);return (1);int in sert( seque nlist *L, int x, int i )int j;if ( ( (*L).list )=MAX-1 )pr in tf( overflow ); return 0;elseif ( (i ( (*L).list )+1 )prin tf( err orn ”);retur n 0;elsefor ( j二L-list;j=i-1;j-)L-dataj+1=L-dataj;L-dat

7、ai-1=x;L-list+;retur n(1);int deletee( sequenlist *L,int i )/*定義刪除函數(shù) */int j;if ( (i(L-list)+1 )pr in tf( error n);return 0;elsefor ( j=i;jlist;j+ )L-dataj-1=L-dataj;L-list-;retur n(1);【運行截圖演示】 、如下面的運行截圖所示，當輸入的線性表長度設(shè)置為12的時候，該線性表最多能輸入12位數(shù)的長度。輸入要插入的數(shù)和插入數(shù)的位置下標， 便可以進行插入操作；同 理當輸入要執(zhí)行刪除操作數(shù)的位置下標，可以將該數(shù)刪除出線性表

8、。 、如下面的運行截圖所示，當初始設(shè)置的線性表長度為5的時候，其5個數(shù)分別是-3、4、5、0、1。若是要執(zhí)行程序中輸入的插入數(shù)字“2”，其插入數(shù)的位置在“-4 ”的時候，程序是不能執(zhí)行插入操作的。此時的線性表能插入的下標范 圍為“ 15”明顯“-4 ”數(shù)值下限“T數(shù)值，所以程序執(zhí)行“error 、如下面的運行截圖所示，同理該線性表要插入數(shù)的位置“6”數(shù)值上限“ 5”數(shù)值，所以程序執(zhí)行“ errorerror插入旨的數(shù)據(jù)：T 4請諭入寒刪除的位盍. 鋳一Xhuangzli iDc bu g hmangzhi.exeP4rlt圭冃丙U4 II馮4 、如下面的運行截圖所示，初始設(shè)置的線性表插入數(shù)子2

9、之后,要刪除位置7已超過線性表的最大長度n=6,所以程序執(zhí)行“error ”F G 51 42 4 0 S s Z =- 鐵.盲4 -4 曙-3 1 的的. 1 AAffi 始雪HI嘗的 A人數(shù)入人后 H1啟S土片主卷T 既吃導(dǎo)一 .hcargrhiUesughuangzhi.ewe1請輸人要冊瞧的7emo r 7.1菽蒼滲一nlangrh Denug、huangzhi.exe刪除后的數(shù).-345201Press anyp key to continueH半:、如下面的運行截圖所示，同理該線性表要刪除數(shù)的位置“0”原原據(jù)人IA數(shù)請土啟宜*-3501EH J3-3入話婪常AAK霽八is2452

10、:HJEL4請輸入要咄除的螢置：error*刪除后的-3 4 5 2 G 1P.re3 3 ainijp key to conti.nueH下標不存在，所以程序執(zhí)行“ error ”。二、單鏈表的操作(1) 創(chuàng)建一個帶頭結(jié)點的單鏈表；(2) 插入元素操作：將新元素x插入到單鏈表中第i個元素之后；(3) 刪除元素操作：刪除單鏈表中值為 x的元素。【創(chuàng)建操作原理】在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱之為頭結(jié)點。頭結(jié) 點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲線性表的長度等的附加 信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針 (即第一個元素結(jié) 點的存儲位置)?！静迦氩僮髟怼繛椴迦霐?shù)據(jù)元素x，首先

11、要生成一個數(shù)據(jù)域為x的結(jié)點，然后插 入在單鏈表中。根據(jù)插入操作的邏輯定義，還需要修改結(jié)點a中的指 針域，令其指向結(jié)點x,而結(jié)點x中的指針域應(yīng)指向結(jié)點b,從而實 現(xiàn)3個元素a、b和x之間邏輯關(guān)系的變化。假設(shè)s為指向結(jié)點x的指針，則上述指針修改用語描述即為：s next p next; p next s【刪除操作原理】反之，在線性表中刪除元素 b時，為在單鏈表中實現(xiàn)元素 a、b 和c之間邏輯關(guān)系的變化，僅需要修改結(jié)點 a中的指針域即可。假設(shè)p為指向結(jié)點a的指針，則上述指針修改用語描述即為：pn ext pn extn ext;【N0.2代碼】#in clude#i ncludetypedef st

12、ruct node /定義鏈表int data;struct node *n ext;sno de;sn ode* creat() / 創(chuàng)建鏈表的函數(shù)snode *head, *p, *q;head = (snode *)malloc(sizeof(s no de);p = head;int x;printf(請輸入創(chuàng)建鏈表的值，用“ 0”結(jié)束輸入。n);prin tf(x =);scanf(%d, &x);while (x != 0)q = (snode *)malloc(sizeof(s no de);q-data = x;p-n ext = q;p = q;prin tf(x = ”);

13、sea nf(%d, &x);p- next = NULL;retur n head;int len gth(s node *head)測鏈表的結(jié)點數(shù)int i = 0;snode *p = head-n ext;while (p != NULL)p = p-n ext;i+;retur n i;void display(s node *head)snode *p = head-n ext;for(i nt i = 0; i data);p = p-n ext;prin tf();int locate(s node *head, int x)snode *p = head-n ext;int

14、i = 1;while (p != NULL & x != p-data)p = p-n ext;i+;if (p = NULL)return 0;elsereturn i;把x插入到鏈表的第int insno de(s node *head, int x, int i) /i的位置int j;snode *p = head-n ext, *s;if(i (length(head) + 1)return 0;else if (i = 1)s = (snode *)malloc(sizeof(s no de);s-n ext = p;head-n ext = s;s-data = x;elsef

15、or (j = 1; j n ext;s = (snode *)malloc(sizeof(s no de);s-n ext = p-n ext;s-data = x;return 1;int del no de(s node *head, i nt i)刪除鏈表中第 i 個結(jié)點snode *p = head-n ext, *q = head;if(i length(head)return 0;else if (i = 1)head-n ext = p-n ext;free(p);elsefor (i nt j = 1; j n ext; q = q-n ext;q-n ext = p-n e

16、xt;free(p);return 1;void sort(s node *head) /把鏈表中每個結(jié)點的值按從小到大排列snode *p, *q;int k;for(p = head-n ext; p != NULL; p = p-n ext)for(q = p-n ext; q != NULL; q = q-n ext)if (p-data q-data)k = p-data;p-data = q-data;q-data = k;void insert(snode *head, int x) /在有序鏈表中插入 x,插入后仍保持有序snode *p = head-n ext, *s, *

17、q = head;while (p != NULL & p-data n ext;s = (snode *)malloc(sizeof(s no de);s-n ext = q-n ext;s-data = x;q-n ext = s;刪除有序鏈void del_min_max(s node *head, int min, i nt max) II表中值min到值max中的結(jié)點snode *p = head-n ext, *q = head;while (p != NULL & p-data n ext;while (p != NULL & p-data n ext = p-n ext;fre

18、e(p);void del_m in(snode *head)snode *p = head-n ext, *q = head;snode *p_mi n, *q_mi n;p_min = p；q_min = q；while (p != NULL)q = p; p = p-n ext;if (p != NULL & p-data data)q_min = p_mi n;p_min = p;q_min-n ext = p_min-n ext;free(p_mi n);int mai n()創(chuàng)建鏈表int mi n, max;snode *headl = creat(); /prin tf(最初的

19、鏈表如下：”)；display(headl);prin tf(nn);int num, locati on;prin tf(請輸入您要查找的數(shù)：);scanf(%d, &num);if (locate(headl, num)num,printf(數(shù)字%d在鏈表中 的位置為：%dnn,locate(headl, nu m);elseprintf(數(shù)字在鏈表中不存在！nn, num);printf(請分別輸入您要插入到鏈表中的數(shù)以及想插入的位置(用空格號間隔開)：)；sca nf(%d %d, &num, & ocatio n);if (insno de(headl, num, locatio n

20、)prin tf(插入新值以后的鏈表如下：);display(headl);prin tf(nn);else printf(輸入有誤!nn);printf(請輸入您想刪除的結(jié)點位置：);sea nf(%d, &l ocatio n);if (de Ino de(headl, locati on)printf(”刪除第個結(jié)點后的鏈表如下：, location);display(headl);prin tf(nn);elseprintf(輸入有誤! nn);【運行截圖演示】 、如下面的運行截圖所示，創(chuàng)建帶有頭結(jié)點且長度為8的單鏈 表：4、8、2、-4、-6、1、9、-1。輸入要查詢的數(shù)“ -6 ”

21、，則查詢到單鏈表中數(shù)“ -6 ”的存儲位置 為“5”的下標號。輸入要插入的數(shù)和插入數(shù)的位置下標， 便可以進行插入操作。程 序中要求插入的數(shù)是“3”，插入數(shù)的位置下標為“5”，兩者之間用空 格號隔開，則插入后的新單鏈表為：4、& 2、-4、3、-6、1、9、-1。同理當輸入要執(zhí)行刪除操作的數(shù)位置下標， 可以對該數(shù)刪除出線性表。程序中要求刪除的數(shù)下標是 7,則執(zhí)行該刪除操作之后的新單鏈表為:4、8、2、-4、3、-6、9、-1。7.畝珥謂fch La r.gzhiXDe Dughuangzhi.刊畝MPVM =同請輸入刨建犍表的值，用估結(jié)臾軻入。K = 4 K = flit = -4X = -6K

22、 =1ic - 9K = 1K = A最初的越裘如4 S 2-4 -G 19 -1憧分別到糙表中的數(shù)以及祖插入的位直（用主恪號間隔開）：3 5 禰/新看必后冏理表如F=4 S 2 -+ 3 -t 1 -1鶴翹2 Y 3 f -1Precs antj kay to continueH半: 、如下面的運行截圖所示，創(chuàng)建帶有頭結(jié)點且長度為8的單鏈表，要查詢的數(shù)“ 3”不在該單鏈表中，所以程序執(zhí)行“ error1- Sh uangzhiXDe bughuan gz H, ee請輸入創(chuàng)建犍表的值，用絕結(jié)克輸入- IK = 4LK = 8K = 2K - -4K = -6X = 1K = 9K1K = M

23、最初的徒丟如F:4 S 2 -4 -61? -1鱷it分利輸入您要霍人到鏈表巾的數(shù)以鳳i插人的位置（用空格號剛蔚D :-半：- 、如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為8的單鏈表,要插入數(shù)的位置下標“-1 ”不在該單鏈表中，所以程序執(zhí)行“error 、如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為8的單鏈表,要插入的位置下標“ 9”為單鏈表最大長度，所以程序執(zhí)行插入操作 i 註 蒼信 h ca ng rhiDe&ug huangshi.txe 請輸人刨建槌表的值，舟 結(jié)臾輸入 k = 4K = 8K =2k4K = fIt = 1K = 9最初的鏈丟如F:4 S 2 -4 -6 1 9 -1鱷

24、溜瞬威5常分別領(lǐng)人建烹霍人到槌表巾的數(shù)以及想插人的位首用空格號聞覊開八3 9厲人嶄宣以眉藥礁血卞；4 0 2 -4 L 9 -1 3請騎I入您想刪除的結(jié)點位宣= 、如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為8的單鏈表,要插入的位置下標“ 10”超出單鏈表長度，所以程序不執(zhí)行插入操作。P 譴盤-.h.argrhiD亡sughuangzhi.ext請輸人創(chuàng)建鋰表的值，用“X結(jié)臾輸入。K = 4K = flK = -4K - -6rt 1 =9K = -182-4 -G 19 -L翰備犍表如=請分創(chuàng)軸入您要插入到糙表中的數(shù)以及祖插入的位直（用主恪號間隔開）:3請輸入您祖刪除的結(jié)點位置:半: 、如下面

25、的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為8的單鏈表,要刪除數(shù)的位置下標“-2 ”不在該單鏈表中，所以程序執(zhí)行“error ”、如下面的運行截圖所示，創(chuàng)建帶頭結(jié)點且長度為8的單鏈表,要刪除數(shù)的位置下標“ 10”超出單鏈表長度，所以程序執(zhí)行“error三、順序棧的操作在順序棧上實現(xiàn)將非負十進制數(shù)轉(zhuǎn)換成二進制數(shù)?！緮?shù)值轉(zhuǎn)換原理】十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換時計算機實現(xiàn)計算的基本問 題，其解決方法很多，其中一個簡單算法基于下列原理：N （N div d） d N mod d（其中：div為整除運算，mod為求余運算） 假設(shè)現(xiàn)在要編制一個滿足下列要求的程序：對于輸入的任意一個 非負十進制整數(shù)，打印輸出與其

26、等值的二進制數(shù)。由于上述計算過程是從低位到高位順序產(chǎn)生二進制數(shù)的各個數(shù) 位，而打印輸出，一般來說應(yīng)從高位到低位進行，恰好和計算過程相 反。因此，若將計算過程中得到的二進制數(shù)的各位順序進棧，則按出 棧序列打印輸出的即為輸入對應(yīng)的二進制數(shù)。（其【數(shù)值轉(zhuǎn)換】在課本P48的算法3.2有解釋）【N0.3代碼】#i nclude #i nclude #defi ne MaxSize 50typedef char ElemType;char digit = 0123456789ABCDEFGHIJKLMNOPQRSTUVWX YZ;typedef structElemType dataMaxSize;int

27、 top;SqStack;void In itStack(SqStack *&s)s = (SqStack *)malloc(sizeof(SqStack);s - top = -1;int Push(SqStack *&s, ElemType e)if(s - top = MaxSize - 1)return 0;s - top+;s - datas - top = e;return 1;int Pop(SqStack *&s, ElemType &e)if(s - top = -1)return 0;e = s - datas - top;s - top-; return 1;int Ge

28、tTop(SqStack *s, ElemType &e)if(s - top = -1)return 0;e = s - datas - top;return 1;void DispStack(SqStack *s)int i;for(i = s - top; i = 0; i-)prin tf(%c, s - datai);prin tf(n);int fun (SqStack *s,i nt num, i nt k) /可將十進制轉(zhuǎn)換成任意進制static int count = 0;int n;if(num k)Push(s, digit nu m);return count;n 二

29、num % k;Push(s, digit n);fun(s,num/k, k);int mai n()SqStack *t;int i;In itStack(t);printf(請輸入一個非負十進制數(shù)：);sea nf(%d, & i);fun(t, i, 2);printf(”其二進制數(shù)為：);DispStaek(t);free(t);return 0;【運行截圖演示】 、如下面的運行截圖所示，輸入非負十進制整數(shù)“14”，經(jīng)過數(shù)值轉(zhuǎn)換之后的二進制數(shù)為“ 1110”。 、如下面的運行截圖所示，輸入十進制整數(shù)“ -2 ”，由于“ -2 為負數(shù)，所以無法經(jīng)過數(shù)值轉(zhuǎn)換為二進制數(shù)。 、如下面的運行截

30、圖所示，輸入非負十進制整數(shù)“ 0”經(jīng)過數(shù)值轉(zhuǎn)換之后的二進制數(shù)為“ 0”四、查找算法在順序表中采用順序查找算法和折半查找算法尋找關(guān)鍵字X在順序表中的位置【順序查找原理】從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比 較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查 記錄；反之，若直至第一個記錄，其關(guān)鍵字和給定值比較都不等，則 表明表中沒有所查記錄，查找不成功。在等概率情況下順序查找的平均長度為:nASL ssPi Cii 1【折半查找原理】先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止折半查找過程是以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比 較，

31、若相等，則查找成功，若不等，則縮小范圍，直至新的區(qū)間中間 位置記錄的關(guān)鍵字等于給定值或者查找區(qū)間的大小小于零時（表明查找不成功）為止。假設(shè)表中每個記錄的查找概率相等1P -，則查找成功時折半n查找的平均查找長度:Log2 n 11 Log2 n 1nAS-pgi 1【N0.4代碼】#i nclude #in elude #defi ne MAXL 1000#defi ne INF 32767int processMAXL,p n;/順序表的存儲結(jié)構(gòu)typedef int KeyType;typedef int In foType;typedef structKeyType key;In foT

32、ype data;NodeType;typedef NodeType SeqListMAXL;/索引表的存儲結(jié)構(gòu)typedef structKeyType key;int link;IdxType;typedef IdxType IDXMAXL;/順序查找算法int SeqSearch(SeqList R,i nt n, KeyType k)int i=0;pn=O;while(i=n) return -1;else return i;/折半查找算法int Bin Search(SeqList R,i nt n,KeyType k)int low=0,high=n-1,mid;pn=O;whi

33、le(lowk)processp n+=Rmid.key;high二mid-1;elseprocessp n+=Rmid.key;low=mid+1;retur n -1;int mai n()int n ,i,k,m;SeqList R;IDX I;n);prin tf(1) 請輸入有/無序順序表的元素個數(shù):while(sca nf(%d,&n )!=EOF)printf(請輸入有/無序順序表的小個元素：n,n);for(i=0;i n ;i+)sea nf(%d,&Ri.key);printf(”請輸入要查找的關(guān)鍵字：n);sea nf(%d,&k);prin tf(使用順序查找算法，);

34、if(SeqSearch(R, n,k)!=-1)printf(關(guān)鍵字d的下標為：n%dtn 查找過程為：n,k,SeqSearch(R ,n ,k);for(i=0;ip n;i+) prin tf(%d ”,process);prin tf(%dnn,k);else prin tf( 要查找的關(guān)鍵字%d不在無序順序表中nn,k);prin tf(2)請輸入有序順序表的元素個數(shù)：n);/10sca nf(%d,&n);printf(請輸入有序順序表的個元素：n,n);for(i=0;i n ;i+)sca nf(%d,&Ri.key);printf(請輸入要查找的關(guān)鍵字：n);sea nf(

35、%d,&k);prin tf(使用折半查找算法，);if(Bi nSearch(R, n,k)!=-1)printf(”關(guān)鍵字d的下標為：n%dtn 查找過程為：n,k,Bi nSearch(R, n,k);for(i=0;ip n;i+)prin tf(%d ”,processi);prin tf(%dnn,k);elseprin tf(要查找的關(guān)鍵字%d不在有序順序表中nn,k);return 0;【運行截圖演示】 、如下面的運行截圖所示，使用順序查詢算法和折半查找算法,查找數(shù)“ 5”，其查找過程分別為：-3、5、& 9、-2、-1 ； 3、-2、-1i囂敘b nghu 弓n gz h.u

36、請輸入百請輸入有L序|礪表的元素個數(shù):is請瑜入有丿無序1耐表的辺個元素k3 5 0 92 -1 0 5 4 ? G請輸入要查萩的戔進字 便舟頗序藥箕法，寒查找的關(guān)犍字不在無序順序耒中站請輔入有序順序表的兀素個歡，無序|所的元素個數(shù):1A請瑜人有丿元序慣序表的丄時力重s-S E 8 9 -2 -1 0 9 4 7請輸入娶査我的戔鍵字，使年幀序查找耳扛 壬鋌字7的下標m-3 5 H 9 -2 -13請輸入和W游表的兀隸個數(shù)，19請諒入有序順.子表刖1呼兀尋，-3-2-10345787請輸人要査找的關(guān)鍵宇雀灰折半査找算法，關(guān)鍵宇T的下標知 暮枝討1衲:3 -2 -1aniy key tolnue.

37、 、如下面的運行截圖所示，在無序順序表中使用順序查詢算法,查找數(shù)“ 6”，因數(shù)“6”位置下標超過表最大長度，即程序查找不到 G,IJ5fii?RK&huiing7hiiDFbug! huangzhi.=*& 、如下面的運行截圖所示，在無序順序表中使用順序查詢算法,查找數(shù)“ 1”，因為數(shù)“ T不在該表中，所以程序查找不到數(shù)“ 13請輸人有產(chǎn)元予順序表的冗羔個垃：請輸入有隹序JI礪夷的偽個元素-3569-210947請輸入要查找的卻字：順序查找算去 罷查找的關(guān)健字久不在無序順序裘中匸即請tl入有序順序喪於元素彳婪: 、如下面的運行截圖所示，在有序順序表中使用折半查詢算法,查找數(shù)“ 1”，因為數(shù)“

38、T不在該表中，所以程序查找不到數(shù)“ 1GXKiEfiZ.hLarigzhDcbugXhuiingz-ii.eKeU h諦人有噴序順序表的元素個數(shù)：16諳輸八有丿無序順丿減的訶卜元素；-3 5 W 9 -2 -1 0 3 4 7肯輸人要查找的關(guān)犍字=崔用順序查找算迄關(guān)鍵宇詢下標為; 蚤找過程為*-3 5 B 9 -2 -1煉請輸入有序順序表的元素個類1A諳輸人有序頃序表的侗個元素！-3 -2 -1 0 3 4 5 7 8 9諳輸人要查找的關(guān)鍵字乜1便用折半查找算注，要査找的關(guān)鍵宇丄不在有啄K予表中Press 曰n 申 kei to con tin Lie五、排序算法將無序數(shù)列使用直接插入排序算法

39、和快速排序算法將其排成遞 增有序數(shù)列?！局苯硬迦肱判蛟怼渴且环N最簡單的排序方法，它的基本操作是將一個記錄插入到已 排好序的有序表中，從而得到一個新的、記錄數(shù)增 1的有序表。排序的基本操作為：比較兩個關(guān)鍵字的大小和移動記錄。 先分析 一趟插入排序的情況。For循環(huán)的次數(shù)取決于待插記錄的關(guān)鍵字與前 i-1個記錄的關(guān)鍵字之間的關(guān)系。則在整個排序過程（進行 n-1趟插 入排序）中，當待排序列中記錄按關(guān)鍵字非遞減有序排列，所需進行 關(guān)鍵字間比較的次數(shù)達最小值 n-1，記錄不需移動；反之，當待排序 列中記錄按關(guān)鍵字非遞增有序排列是， 總的比較次數(shù)達到最大值，記 錄移動的次數(shù)也達最大值。若待排序記錄是隨機

40、的，即待排序列中的 記錄可能出現(xiàn)的各種排列的概率相同，則我們可取上述最小值和最大 值的平均值，作為直接插入排序時所需進行關(guān)鍵字間的比較次數(shù)和移 動記錄的次數(shù)?！究焖倥判蛟怼靠焖倥判蚴菍ζ鹋菖判虻囊环N改進。 它的基本思想是，通過一趟 排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均 比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排 序，以達到整個序列有序?！綨0.5代碼】#i nclude#in clude#defi ne MAX 100/將無序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列typedef structint dataMAX;int len g

41、th;sqlist;void ini t(sqlist & a)/線性表初始化aen gth=0;void insert(sqlist &a ,int i,int x)插入元素，構(gòu)造無序數(shù)列int j;if(ia.le ngth+1|a.le ngth=100);elsefor(j=aen gth+1;ji;j-)a.dataj=a.dataj-1;a.dataj=x;aen gth+;/放在a.datan中，被排序的記錄放在a.data0.n-1中，直接插入排序算法。void in sertsort(sqlist & a)直接插入排序算法int i,j;int n二aen gth;for(i

42、=n-2;i=0;i-)if(a.dataia.datai+1)a.data n=a.datai;/a.data n是哨兵j=i+1;doa.dataj-1=a.dataj;j+;while(a.dataja.data n);a.dataj-1=a.data n;int Partiti on( sqlist &a,i nt i,i nt j)int pivot二a.datai;while(ij)while(i=pivot)j-；if(ij)a.datai+=a.dataj;while(ij&a.datai=pivot)i+;if(ij)a.dataj-=a.datai;a.datai=pivot;retur n i;快速排序 void QuickSort(sqlist &a,int low,int high)/int pivotpos; /劃分后的基準記錄的位置if(lowvhigh)/僅當區(qū)間長度大于1時才須排序pivotpos二Partiti on (a,low,high);QuickSort(a,low,pivotpos-1);QuickSort(a,pivotpos+1,high);void mai n()sqlist sq1,sq2;