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

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

2、【NO.5代碼】41【運(yùn)行截圖演示】46一、順序表的操作1插入元素操作：將新元素x插入到順序表a中第i個(gè)位置；2刪除元素操作：刪除順序表a中第i個(gè)元素。【插入操作原理】線性表的插入操作是指在線性表的第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素，就是要是長(zhǎng)度為n的線性表：變成長(zhǎng)度為n+1的線性表：數(shù)據(jù)元素和之間的邏輯關(guān)系發(fā)生了變化。其【插入原理】在課本P23的算法2.3有解釋【刪除操作原理】反之，線性表的刪除操作是使長(zhǎng)度為n的線性表：變成長(zhǎng)度為n-1的線性表：數(shù)據(jù)元素、和之間的邏輯關(guān)系發(fā)生變化，為了在存儲(chǔ)結(jié)構(gòu)上放映這個(gè)變化，同樣需要移動(dòng)元素。其【刪除原理】在課本P24的算法2.4有

3、解釋【NO.1代碼】#include<stdio.h>#define MAX 100typedef int datatype;typedef structdatatype dataMAX;int list; sequenlist; /*順序表*/int main()int insert( sequenlist *L, int x, int i );int deletee( sequenlist *L, int i );int input( sequenlist *L );int output( sequenlist *L ); sequenlist s,*p=&s; int

4、 indata,inlocate,deletedx; input(p); printf( "請(qǐng)輸入要插入的數(shù)：" ); scanf( "%d",&indata ); printf( "請(qǐng)輸入要插入的位置：" ); scanf( "%d",&inlocate ); insert( p,indata,inlocate ); printf( "插入后的數(shù)據(jù)：" );output(p);printf( "請(qǐng)輸入要?jiǎng)h除的位置：" ); scanf( "%d&q

5、uot;,&deletedx );deletee( p, deletedx ); printf( "刪除后的數(shù)據(jù)：" );output(p);return 0;int output( sequenlist *L ) int i;for( i=0; i<=L->list; i+ ) printf( "%d ",L->datai );printf( "nn" );return(1);int input( sequenlist *L ) int i;printf( "請(qǐng)輸入原始數(shù)據(jù)個(gè)數(shù)：" );

6、 scanf( "%d",&( L->list ) ); L->list-; printf( "請(qǐng)輸入原始數(shù)據(jù)：" ); for( i=0; i <= L->list; i+ ) scanf( "%d",&( L->datai ) ); printf( "原始數(shù)據(jù)為：" ); output(L); return (1);int insert( sequenlist *L, int x, int i ) int j; if ( ( (*L).list )>=MAX-

7、1 ) printf( "overflow" ); return 0; else if ( (i<1) | (i> ( (*L).list )+1 ) ) printf( "errorn" ); return 0; else for ( j=L->list;j>=i-1;j- ) L->dataj+1=L->dataj;L->datai-1=x; L->list+; return(1);int deletee( sequenlist *L,int i ) /*定義刪除函數(shù)*/ int j;if ( (i&l

8、t;1) | ( i>(L->list)+1 ) ) printf( "errorn" );return 0; else for ( j=i;j<=L->list;j+ ) L->dataj-1=L->dataj;L->list-; return(1);【運(yùn)行截圖演示】、如下面的運(yùn)行截圖所示，當(dāng)輸入的線性表長(zhǎng)度設(shè)置為12的時(shí)候，該線性表最多能輸入12位數(shù)的長(zhǎng)度。輸入要插入的數(shù)和插入數(shù)的位置下標(biāo)，便可以進(jìn)行插入操作；同理當(dāng)輸入要執(zhí)行刪除操作數(shù)的位置下標(biāo)，可以將該數(shù)刪除出線性表。、如下面的運(yùn)行截圖所示，當(dāng)初始設(shè)置的線性表長(zhǎng)度為5的時(shí)候，

9、其5個(gè)數(shù)分別是-3、4、5、0、1。假設(shè)是要執(zhí)行程序中輸入的插入數(shù)字“2，其插入數(shù)的位置在“-4的時(shí)候，程序是不能執(zhí)行插入操作的。此時(shí)的線性表能插入的下標(biāo)范圍為“15，明顯“-4數(shù)值<下限“1數(shù)值，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，同理該線性表要插入數(shù)的位置“6數(shù)值>上限“5數(shù)值，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，初始設(shè)置的線性表插入數(shù)字2之后，要?jiǎng)h除位置7已超過(guò)線性表的最大長(zhǎng)度n=6，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，同理該線性表要?jiǎng)h除數(shù)的位置“0下標(biāo)不存在，所以程序執(zhí)行“error。二、單鏈表的操作1創(chuàng)立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；2插

10、入元素操作：將新元素x插入到單鏈表中第i個(gè)元素之后；3刪除元素操作：刪除單鏈表中值為x的元素。 【創(chuàng)立操作原理】在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)線性表的長(zhǎng)度等的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置?！静迦氩僮髟怼繛椴迦霐?shù)據(jù)元素x，首先要生成一個(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，然后插入在單鏈表中。根據(jù)插入操作的邏輯定義，還需要修改結(jié)點(diǎn)a中的指針域，令其指向結(jié)點(diǎn)x，而結(jié)點(diǎn)x中的指針域應(yīng)指向結(jié)點(diǎn)b，從而實(shí)現(xiàn)3個(gè)元素a、b和x之間邏輯關(guān)系的變化。假設(shè)s為指向結(jié)點(diǎn)x的指針，那么上述指針修改用語(yǔ)描述即為： 【刪除操作

11、原理】反之，在線性表中刪除元素b時(shí)，為在單鏈表中實(shí)現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需要修改結(jié)點(diǎn)a中的指針域即可。假設(shè)p為指向結(jié)點(diǎn)a的指針，那么上述指針修改用語(yǔ)描述即為：【NO.2代碼】#include<stdio.h>#include<malloc.h>typedef struct node /定義鏈表 int data; struct node *next;snode;snode* creat() /創(chuàng)立鏈表的函數(shù) snode *head, *p, *q;head = (snode *)malloc(sizeof(snode); p = head; int x;

12、 printf("請(qǐng)輸入創(chuàng)立鏈表的值，用“0”結(jié)束輸入。n"); printf("x = "); scanf("%d", &x); while (x != 0)q = (snode *)malloc(sizeof(snode);q->data = x;p->next = q;p = q;printf("x = ");scanf("%d", &x); p->next = NULL; return head;int length(snode *head)/測(cè)鏈表的結(jié)

13、點(diǎn)數(shù)int i = 0;snode *p = head->next;while (p != NULL)p = p->next;i+; return i;void display(snode *head) snode *p = head->next;for(int i = 0; i < length(head); i+)printf("%4d", p->data); p = p->next; printf(" ");int locate(snode *head, int x) snode *p = head->ne

14、xt; int i = 1; while (p != NULL && x != p->data)p = p->next;i+;if (p = NULL) return 0; else return i;int insnode(snode *head, int x, int i) /把x插入到鏈表的第i的位置 int j; snode *p = head->next, *s;if(i < 1 | i > (length(head) + 1) return 0; else if (i = 1) s = (snode *)malloc(sizeof(sn

15、ode); s->next = p; head->next = s; s->data = x; else for (j = 1; j < i - 1; j+) p = p->next; s = (snode *)malloc(sizeof(snode); s->next = p->next; p->next = s;s->data = x; return 1;int delnode(snode *head, int i)/刪除鏈表中第i個(gè)結(jié)點(diǎn) snode *p = head->next, *q = head; if(i < 1

16、| i > length(head) return 0; else if (i = 1) head->next = p->next; free(p); else for (int j = 1; j < i; j+)p = p->next; q = q->next;q->next = p->next;free(p); return 1;void sort(snode *head) /把鏈表中每個(gè)結(jié)點(diǎn)的值按從小到大排列 snode *p, *q; int k; for(p = head->next; p != NULL; p = p->n

17、ext) for(q = p->next; q != NULL; q = q->next) 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->next, *s, *q = head; while (p != NULL && p->data < x) q = q->next; p =

18、 p->next; s = (snode *)malloc(sizeof(snode);s->next = q->next; s->data = x; q->next = s;void del_min_max(snode *head, int min, int max) /刪除有序鏈表中值min到值max中的結(jié)點(diǎn)snode *p = head->next, *q = head; while (p != NULL && p->data <= min)q = p; p = p->next; while (p != NULL &a

19、mp;& p->data < max) q->next = p->next; free(p); p = q->next; void del_min(snode *head) snode *p = head->next, *q = head; snode *p_min, *q_min; p_min = p; q_min = q;while (p != NULL)q = p; p = p->next; if (p != NULL && p->data < p_min->data)q_min = p_min; p_m

20、in = p; q_min->next = p_min->next; free(p_min);int main() int min, max; snode *headl = creat(); /創(chuàng)立鏈表 printf("最初的鏈表如下："); display(headl);printf("nn"); int num, location; printf("請(qǐng)輸入您要查找的數(shù)：");scanf("%d", &num); if (locate(headl, num) printf("數(shù)字%d

21、在鏈表中的位置為：%dnn", num, locate(headl, num); else printf("數(shù)字%d在鏈表中不存在!nn", num); printf("請(qǐng)分別輸入您要插入到鏈表中的數(shù)以及想插入的位置用空格號(hào)間隔開(kāi)："); scanf("%d %d", &num, &location); if (insnode(headl, num, location) printf("插入新值以后的鏈表如下："); display(headl);printf("nn"

22、); else printf("輸入有誤!nn"); printf("請(qǐng)輸入您想刪除的結(jié)點(diǎn)位置："); scanf("%d", &location); if (delnode(headl, location) printf("刪除第%d個(gè)結(jié)點(diǎn)后的鏈表如下：", location); display(headl);printf("nn"); elseprintf("輸入有誤! nn");【運(yùn)行截圖演示】、如下面的運(yùn)行截圖所示，創(chuàng)立帶有頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表：4、8、2

23、、-4、-6、1、9、-1。輸入要查詢的數(shù)“-6，那么查詢到單鏈表中數(shù)“-6的存儲(chǔ)位置為“5的下標(biāo)號(hào)。輸入要插入的數(shù)和插入數(shù)的位置下標(biāo)，便可以進(jìn)行插入操作。程序中要求插入的數(shù)是“3，插入數(shù)的位置下標(biāo)為“5，兩者之間用空格號(hào)隔開(kāi)，那么插入后的新單鏈表為：4、8、2、-4、3、-6、1、9、-1。同理當(dāng)輸入要執(zhí)行刪除操作的數(shù)位置下標(biāo)，可以對(duì)該數(shù)刪除出線性表。程序中要求刪除的數(shù)下標(biāo)是7，那么執(zhí)行該刪除操作之后的新單鏈表為：4、8、2、-4、3、-6、9、-1。、如下面的運(yùn)行截圖所示，創(chuàng)立帶有頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要查詢的數(shù)“3不在該單鏈表中，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，創(chuàng)立

24、帶頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要插入數(shù)的位置下標(biāo)“-1不在該單鏈表中，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，創(chuàng)立帶頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要插入的位置下標(biāo)“9為單鏈表最大長(zhǎng)度，所以程序執(zhí)行插入操作。、如下面的運(yùn)行截圖所示，創(chuàng)立帶頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要插入的位置下標(biāo)“10超出單鏈表長(zhǎng)度，所以程序不執(zhí)行插入操作。、如下面的運(yùn)行截圖所示，創(chuàng)立帶頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要?jiǎng)h除數(shù)的位置下標(biāo)“-2不在該單鏈表中，所以程序執(zhí)行“error。、如下面的運(yùn)行截圖所示，創(chuàng)立帶頭結(jié)點(diǎn)且長(zhǎng)度為8的單鏈表，要?jiǎng)h除數(shù)的位置下標(biāo)“10超出單鏈表長(zhǎng)度，所以程序執(zhí)行“error。三、順序棧的操作在順序棧上實(shí)

25、現(xiàn)將非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)?！緮?shù)值轉(zhuǎn)換原理】十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換時(shí)計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的根本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于以下原理：其中：div為整除運(yùn)算，mod為求余運(yùn)算假設(shè)現(xiàn)在要編制一個(gè)滿足以下要求的程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的二進(jìn)制數(shù)。由于上述計(jì)算過(guò)程是從低位到高位順序產(chǎn)生二進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來(lái)說(shuō)應(yīng)從高位到低位進(jìn)行，恰好和計(jì)算過(guò)程相反。因此，假設(shè)將計(jì)算過(guò)程中得到的二進(jìn)制數(shù)的各位順序進(jìn)棧，那么按出棧序列打印輸出的即為輸入對(duì)應(yīng)的二進(jìn)制數(shù)。其【數(shù)值轉(zhuǎn)換】在課本P48的算法3.2有解釋【NO.3代碼】#include <st

26、dio.h>#include <stdlib.h>#define MaxSize 50typedef char ElemType;char digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"typedef structElemType dataMaxSize;int top;SqStack;void InitStack(SqStack *&s)s = (SqStack *)malloc(sizeof(SqStack);s -> top = -1;int Push(SqStack *&s, El

27、emType 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 GetTop(SqStack *s, ElemType &e)if(s -> top = -1)return 0;e = s -> dat

28、as -> top;return 1;void DispStack(SqStack *s) int i;for(i = s -> top; i >= 0; i-) printf("%c", s -> datai);printf("n");int fun(SqStack *s,int num, int k) /可將十進(jìn)制轉(zhuǎn)換成任意進(jìn)制static int count = 0;int n;if(num < k)Push(s, digitnum);return count;n = num % k;Push(s, digitn);f

29、un(s,num/k, k);int main()SqStack *t;int i;InitStack(t);printf("請(qǐng)輸入一個(gè)非負(fù)十進(jìn)制數(shù)：");scanf("%d", &i);fun(t, i, 2); printf("其二進(jìn)制數(shù)為：");DispStack(t);free(t);return 0;【運(yùn)行截圖演示】、如下面的運(yùn)行截圖所示，輸入非負(fù)十進(jìn)制整數(shù)“14，經(jīng)過(guò)數(shù)值轉(zhuǎn)換之后的二進(jìn)制數(shù)為“1110。、如下面的運(yùn)行截圖所示，輸入十進(jìn)制整數(shù)“-2，由于“-2為負(fù)數(shù)，所以無(wú)法經(jīng)過(guò)數(shù)值轉(zhuǎn)換為二進(jìn)制數(shù)。、如下面的運(yùn)行截圖

30、所示，輸入非負(fù)十進(jìn)制整數(shù)“0，經(jīng)過(guò)數(shù)值轉(zhuǎn)換之后的二進(jìn)制數(shù)為“0。四、查找算法在順序表中采用順序查找算法和折半查找算法尋找關(guān)鍵字X在順序表中的位置?！卷樞虿檎以怼繌谋碇凶詈笠粋€(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比擬，假設(shè)某個(gè)記錄的關(guān)鍵字和給定值比擬相等，那么查找成功，找到所查記錄；反之，假設(shè)直至第一個(gè)記錄，其關(guān)鍵字和給定值比擬都不等，那么說(shuō)明表中沒(méi)有所查記錄，查找不成功。在等概率情況下順序查找的平均長(zhǎng)度為：【折半查找原理】先確定待查記錄所在的范圍區(qū)間，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找過(guò)程是以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比擬，假設(shè)相等，那么查找成功，假設(shè)不等，那

31、么縮小范圍，直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或者查找區(qū)間的大小小于零時(shí)說(shuō)明查找不成功為止。假設(shè)表中每個(gè)記錄的查找概率相等，那么查找成功時(shí)折半查找的平均查找長(zhǎng)度：【NO.4代碼】#include <stdio.h>#include <math.h>#define MAXL 1000#define INF 32767int processMAXL,pn;/順序表的存儲(chǔ)結(jié)構(gòu)typedef int KeyType;typedef int InfoType;typedef struct KeyType key;InfoType data; NodeType;typede

32、f NodeType SeqListMAXL;/索引表的存儲(chǔ)結(jié)構(gòu)typedef struct KeyType key;int link; IdxType;typedef IdxType IDXMAXL;/順序查找算法int SeqSearch(SeqList R,int n,KeyType k) int i=0; pn=0; while(i<n&&Ri.key!=k) processpn+=Ri.key; i+; if(i>=n) return -1; else return i; /折半查找算法int BinSearch(SeqList R,int n,KeyTy

33、pe k) int low=0,high=n-1,mid; pn=0; while(low<=high) mid=(low+high)/2; if(Rmid.key=k) return mid; if(Rmid.key>k) processpn+=Rmid.key;high=mid-1; else processpn+=Rmid.key;low=mid+1; return -1; int main() int n,i,k,m; SeqList R; IDX I; printf("(1)請(qǐng)輸入有/無(wú)序順序表的元素個(gè)數(shù)：n"); while(scanf("

34、%d",&n)!=EOF) printf("請(qǐng)輸入有/無(wú)序順序表的%d個(gè)元素：n",n); for(i=0;i<n;i+) scanf("%d",&Ri.key); printf("請(qǐng)輸入要查找的關(guān)鍵字：n");scanf("%d",&k); printf("使用順序查找算法，"); if(SeqSearch(R,n,k)!=-1) printf("關(guān)鍵字%d的下標(biāo)為：n%dtn查找過(guò)程為：n",k,SeqSearch(R,n,k);

35、for(i=0;i<pn;i+) printf("%d ",processi); printf("%dnn",k); else printf("要查找的關(guān)鍵字%d不在無(wú)序順序表中nn",k); printf("(2)請(qǐng)輸入有序順序表的元素個(gè)數(shù)：n");/10 scanf("%d",&n);printf("請(qǐng)輸入有序順序表的%d個(gè)元素：n",n); for(i=0;i<n;i+) scanf("%d",&Ri.key); prin

36、tf("請(qǐng)輸入要查找的關(guān)鍵字：n");scanf("%d",&k); printf("使用折半查找算法，"); if(BinSearch(R,n,k)!=-1) printf("關(guān)鍵字%d的下標(biāo)為：n%dtn查找過(guò)程為：n",k,BinSearch(R,n,k); for(i=0;i<pn;i+) printf("%d ",processi); printf("%dnn",k); else printf("要查找的關(guān)鍵字%d不在有序順序表中nn&quo

37、t;,k); return 0;【運(yùn)行截圖演示】、如下面的運(yùn)行截圖所示，使用順序查詢算法和折半查找算法，查找數(shù)“5，其查找過(guò)程分別為：-3、5、8、9、-2、-1；3、-2、-1。、如下面的運(yùn)行截圖所示，在無(wú)序順序表中使用順序查詢算法，查找數(shù)“6，因數(shù)“6位置下標(biāo)超過(guò)表最大長(zhǎng)度，即程序查找不到。、如下面的運(yùn)行截圖所示，在無(wú)序順序表中使用順序查詢算法，查找數(shù)“1，因?yàn)閿?shù)“1不在該表中，所以程序查找不到數(shù)“1。、如下面的運(yùn)行截圖所示，在有序順序表中使用折半查詢算法，查找數(shù)“1，因?yàn)閿?shù)“1不在該表中，所以程序查找不到數(shù)“1。五、排序算法將無(wú)序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列

38、。【直接插入排序原理】是一種最簡(jiǎn)單的排序方法，它的根本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。排序的根本操作為：比擬兩個(gè)關(guān)鍵字的大小和移動(dòng)記錄。先分析一趟插入排序的情況。For循環(huán)的次數(shù)取決于待插記錄的關(guān)鍵字與前i-1個(gè)記錄的關(guān)鍵字之間的關(guān)系。那么在整個(gè)排序過(guò)程進(jìn)行n-1趟插入排序中，當(dāng)待排序列中記錄按關(guān)鍵字非遞減有序排列，所需進(jìn)行關(guān)鍵字間比擬的次數(shù)達(dá)最小值n-1，記錄不需移動(dòng)；反之，當(dāng)待排序列中記錄按關(guān)鍵字非遞增有序排列是，總的比擬次數(shù)到達(dá)最大值，記錄移動(dòng)的次數(shù)也達(dá)最大值。假設(shè)待排序記錄是隨機(jī)的，即待排序列中的記錄可能出現(xiàn)的各種排列的概率相同，那么我們

39、可取上述最小值和最大值的平均值，作為直接插入排序時(shí)所需進(jìn)行關(guān)鍵字間的比擬次數(shù)和移動(dòng)記錄的次數(shù)。【快速排序原理】快速排序是對(duì)起泡排序的一種改良。它的根本思想是，通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩局部，其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小，那么可分別對(duì)這兩局部記錄繼續(xù)進(jìn)行排序，以到達(dá)整個(gè)序列有序?！綨O.5代碼】#include<iostream.h>#include<stdlib.h>#define MAX 100/將無(wú)序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列typedef struct int dataMAX;int length;s

40、qlist;void init(sqlist &a)/線性表初始化a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素,構(gòu)造無(wú)序數(shù)列int j;if(i<0|i>a.length+1|a.length=100);elsefor(j=a.length+1;j>i;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; /放在a.datan中，被排序的記錄放在a.data0.n-1中，直接插入排序算法。void insertsort(sqlist &a)/直接插入排序算法int

41、 i,j;int n=a.length;for(i=n-2;i>=0;i-) if(a.datai>a.datai+1) a.datan=a.datai;/a.datan是哨兵 j=i+1; do a.dataj-1=a.dataj; j+;while(a.dataj<a.datan);a.dataj-1=a.datan;int Partition(sqlist &a,int i,int j)int pivot=a.datai;while(i<j)while(i<j&&a.dataj>=pivot) j-; if(i<j) a.

42、datai+=a.dataj; while(i<j&&a.datai<=pivot) i+; if(i<j) a.dataj-=a.datai; a.datai=pivot; return i;void QuickSort(sqlist &a,int low,int high)/快速排序 int pivotpos; /劃分后的基準(zhǔn)記錄的位置if(low<high)/僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序pivotpos=Partition(a,low,high); QuickSort(a,low,pivotpos-1); QuickSort(a,pivotpos+1,high); void main()sqlist sq1,sq2;/線性表為sq1,sq2int i,