《數(shù)據(jù)結構與算法分析》課程設計順序表、單鏈表、順序棧、查找、排序算法

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：52 大?。?49.50KB 人氣指數(shù)：12 舉報 版權申訴

《數(shù)據(jù)結構與算法分析》課程設計順序表、單鏈表、順序棧、查找、排序算法_第1頁

已閱讀1頁，還剩51頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　*******大學　　《數(shù)據(jù)結構與算法分析》課程設計　　題目：數(shù)據(jù)結構上機試題　　學生姓名： 　　學號：</p&g

2、t;　　專業(yè)：信息管理與信息系統(tǒng)　　班級：　　指導教師： 　　2014年04月　　目錄</b&g

3、t;　　一、順序表的操作2　　【插入操作原理】2　　【刪除操作原理】2　　【NO.1代碼】3　　【運行截圖演示】7　　二、單鏈表的操作10<p&g

4、t;　　【創(chuàng)建操作原理】10　　【插入操作原理】10　　【刪除操作原理】10　　【NO.2代碼】11　　【運行截圖演示】20　　三、順序棧的操作25　　【數(shù)值轉換原理】25&

5、lt;/p>　　【NO.3代碼】26　　【運行截圖演示】30　　四、查找算法32　　【順序查找原理】32　　【折半查找原理】32　　【NO.4代碼】33

6、　　【運行截圖演示】38　　五、排序算法40　　【直接插入排序原理】40　　【快速排序原理】40　　【NO.5代碼】41　　【運行截圖演示】

7、46　　一、順序表的操作　?。?）插入元素操作：將新元素x插入到順序表a中第i個位置；　?。?）刪除元素操作：刪除順序表a中第i個元素。　　【插入操作原理】<p&g

8、t;　　線性表的插入操作是指在線性表的第i-1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素，就是要是長度為n的線性表：　　變成長度為n+1的線性表：　　數(shù)據(jù)元素和之間的邏輯關系發(fā)生了變化。　?。ㄆ洹静迦朐怼吭谡n本P23的算法2.3有解釋）　　【刪

9、除操作原理】　　反之，線性表的刪除操作是使長度為n的線性表：　　變成長度為n-1的線性表：　　數(shù)據(jù)元素、和之間的邏輯關系發(fā)生變化，為了在存儲結構上放映這個變化，同樣需要移動元素。　?。ㄆ洹緞h除原理】在課本P24的算法2.4有解釋）

10、　　【NO.1代碼】　　#include<stdio.h>　　#define MAX 100　　typedef int datatype;　　typedef struct<

11、p>　　{　　datatype data[MAX];　　int list;　　} 　　sequenlist; /*

12、順序表*/　　int main()　　{　　int insert( sequenlist *L, int x, int i );　　int deletee( sequenlist *L, int i );<

13、;p>　　int input( sequenlist *L );　　int output( sequenlist *L );　　sequenlist s,*p=&s;　　int indata,inlocate,deletedx;　　inpu

14、t(p);　　printf( "請輸入要插入的數(shù)：" ); 　　scanf( "%d",&indata );　　printf( "請輸入要插入的位置：" );　　sc

15、anf( "%d",&inlocate );　　insert( p,indata,inlocate );　　printf( "插入后的數(shù)據(jù)：" );　　output(p);　　printf( "請輸入要刪除的位置：

16、" );　　scanf( "%d",&deletedx );　　deletee( p, deletedx );　　printf( "刪除后的數(shù)據(jù)：" );　　output(p);<p&

17、gt;　　return 0;　　}　　int output( sequenlist *L ) 　　{　　int i;<

18、/b>　　for( i=0; i<=L->list; i++ ) 　　printf( "%d ",L->data[i] );　　printf( "\n\n" );　　return(1);

19、　　}　　int input( sequenlist *L ) 　　{　　int i;　　printf

20、( "請輸入原始數(shù)據(jù)個數(shù)：" );　　scanf( "%d",&( L->list ) );　　L->list--; 　　printf( "請輸入原始數(shù)據(jù)：" );　　for( i=0; i

21、<= L->list; i++ ) 　　scanf( "%d",&( L->data[i] ) );　　printf( "原始數(shù)據(jù)為：" );　　output(L);　　return (1);</p&

22、gt;　　}　　int insert( sequenlist *L, int x, int i )　　{ 　　int j;　　if (

23、( (*L).list )>=MAX-1 )　　{　　printf( "overflow" ); return 0;　　}　　else

24、;　　{　　if ( (i<1) || (i> ( (*L).list )+1 ) )　　{　　printf( "error\n" ); &

25、lt;p>　　return 0;}　　else 　　{　　for ( j=L->list;j>=i-1;j-- )　　L->data[j+1]=L->data[j];

26、L->data[i-1]=x; L->list++;　　}　　}　　return(1);　　}　　int

27、 deletee( sequenlist *L,int i ) /*定義刪除函數(shù)*/　　{ 　　int j;　　if ( (i<1) || ( i>(L->list)+1 ) )<p

28、>　　{ 　　printf( "error\n" );　　return 0;　　} 　　else</b&g

29、t;　　{ 　　for ( j=i;j<=L->list;j++ )　　L->data[j-1]=L->data[j];　　L->list--;

30、　　}　　return(1);　　}　　【運行截圖演示】　?、?、如下面的運行截圖所示，當輸入的線性表長度設置為12的時候，該線性表最多能輸入12位數(shù)的長度。

31、　　輸入要插入的數(shù)和插入數(shù)的位置下標，便可以進行插入操作；同理當輸入要執(zhí)行刪除操作數(shù)的位置下標，可以將該數(shù)刪除出線性表。　　②、如下面的運行截圖所示，當初始設置的線性表長度為5的時候，其5個數(shù)分別是-3、4、5、0、1。　　若是要執(zhí)行程序中輸入的插入數(shù)字“2”，其插入數(shù)的位置在“-4”的時候，程序是不能執(zhí)行插入操作的。此時的線性表能

32、插入的下標范圍為“1——5”，明顯“-4”數(shù)值<下限“1”數(shù)值，所以程序執(zhí)行“error”。　?、邸⑷缦旅娴倪\行截圖所示，同理該線性表要插入數(shù)的位置“6”數(shù)值>上限“5”數(shù)值，所以程序執(zhí)行“error”。　　④、如下面的運行截圖所示，初始設置的線性表插入數(shù)字2之后，要刪除位置7已超過線性表的最大長度n=6，所以程序執(zhí)行“error”。<

33、/p>　　⑤、如下面的運行截圖所示，同理該線性表要刪除數(shù)的位置“0”下標不存在，所以程序執(zhí)行“error”。　　二、單鏈表的操作　?。?）創(chuàng)建一個帶頭結點的單鏈表；　?。?）插入元素操作：將新元素x插入到單鏈表中第i個元素之后；

34、　?。?）刪除元素操作：刪除單鏈表中值為x的元素。 　　【創(chuàng)建操作原理】　　在單鏈表的第一個結點之前附設一個結點，稱之為頭結點。頭結點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲線性表的長度等的附加信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。&l

35、t;p>　　【插入操作原理】　　為插入數(shù)據(jù)元素x，首先要生成一個數(shù)據(jù)域為x的結點，然后插入在單鏈表中。根據(jù)插入操作的邏輯定義，還需要修改結點a中的指針域，令其指向結點x，而結點x中的指針域應指向結點b，從而實現(xiàn)3個元素a、b和x之間邏輯關系的變化。　　假設s為指向結點x的指針，則上述指針修改用語描述即為：<

36、;/p>　　【刪除操作原理】　　反之，在線性表中刪除元素b時，為在單鏈表中實現(xiàn)元素a、b和c之間邏輯關系的變化，僅需要修改結點a中的指針域即可。　　假設p為指向結點a的指針，則上述指針修改用語描述即為：　　【NO.2代碼】<

37、/b>　　#include<stdio.h>　　#include<malloc.h>　　typedef struct node //定義鏈表　　{ <b&g

38、t;　　int data;　　struct node *next;　　}　　snode;　　snode* creat() //創(chuàng)建鏈表的函數(shù)<p&

39、gt;　　{ 　　snode *head, *p, *q;　　head = (snode *)malloc(sizeof(snode));　　p = head;　　int x;&

40、lt;/b>　　printf("請輸入創(chuàng)建鏈表的值，用“0”結束輸入。\n");　　printf("x = ");　　scanf("%d", &x);　　while (x != 0)</p&g

41、t;　　{　　q = (snode *)malloc(sizeof(snode));　　q->data = x;　　p->next = q;　　p = q;<

42、;/p>　　printf("x = ");　　scanf("%d", &x);　　}　　p->next = NULL; 　　return head;

43、　　}　　int length(snode *head)//測鏈表的結點數(shù)　　{　　int i = 0;　　snode *p = head->nex

44、t;　　while (p != NULL)　　{　　p = p->next;　　i++;　　} </p

45、>　　return i;　　}　　void display(snode *head) 　　{　　snode *p = head-&

46、gt;next;　　for(int i = 0; i < length(head); i++)　　{　　printf("%4d", p->data);　　p = p->next;

47、;　　}　　printf(" ");　　}　　int locate(snode *head, int x) 　　{&

48、lt;/p>　　snode *p = head->next;　　int i = 1;　　while (p != NULL && x != p->data)　　{　　p = p-&

49、gt;next;　　i++;　　}　　if (p == NULL) 　　return 0;

50、　else 　　return i;　　}　　int insnode(snode *head, int x, int i) //把x插入到鏈表的第i的位置

51、;　　{ 　　int j;　　snode *p = head->next, *s;　　if(i < 1 || i > (length(head) + 1))　　retu

52、rn 0;　　else if (i == 1)　　{ 　　s = (snode *)malloc(sizeof(snode)); 　　s->next = p; <p&

53、gt;　　head->next = s; 　　s->data = x;　　}　　else　　{

54、　　for (j = 1; j 　　p = p->next;　　s = (snode *)malloc(sizeof(snode));　　s->next = p->next;　　p->next = s;</

55、p>　　s->data = x; 　　}　　return 1;　　}　　int delnode(snode *head, i

56、nt i)//刪除鏈表中第i個結點　　{　　snode *p = head->next, *q = head;　　if(i < 1 || i > length(head))　　return 0;&l

57、t;/b>　　else if (i == 1)　　{ 　　head->next = p->next;　　free(p);<b&g

58、t;　　} 　　else　　{ 　　for (int j = 1; j < i; j++)　　{

59、　　p = p->next; q = q->next;　　}　　q->next = p->next;　　free(p); 　　}</p&g

60、t;　　return 1;　　}　　void sort(snode *head) //把鏈表中每個結點的值按從小到大排列　　{　　sno

61、de *p, *q;　　int k;　　for(p = head->next; p != NULL; p = p->next)　　for(q = p->next; q != NULL; q = q->next)

62、　　if (p->data > q->data)　　{ 　　k = p->data; 　　p->data = q->data; 　　q->data = k; <

63、;/p>　　}　　}　　void insert(snode *head, int x) //在有序鏈表中插入x,插入后仍保持有序　　{ <

64、;p>　　snode *p = head->next, *s, *q = head;　　while (p != NULL && p->data < x)　　{ 　　q = q->next;<

65、;p>　　p = p->next;　　}　　s = (snode *)malloc(sizeof(snode));　　s->next = q->next; 　　s->data = x; <

66、;/p>　　q->next = s;　　}　　void del_min_max(snode *head, int min, int max) //刪除有序鏈表中值min到值max中的結點　　{</p

67、>　　snode *p = head->next, *q = head;　　while (p != NULL && p->data <= min)　　{　　q = p;<

68、/p>　　p = p->next; 　　}　　while (p != NULL && p->data < max)　　{ 　　q-

69、>next = p->next;　　free(p);　　p = q->next;　　}　　}　　v

70、oid del_min(snode *head) 　　{　　snode *p = head->next, *q = head;　　snode *p_min, *q_min;　　p_min = p;<

71、p>　　q_min = q;　　while (p != NULL)　　{　　q = p; p = p->next;　　if (p != NULL && p->data < p_min->

72、;data)　　{　　q_min = p_min;　　p_min = p;　　}　　}<

73、;p>　　q_min->next = p_min->next;　　free(p_min);　　}　　int main()　　{

74、　int min, max;　　snode *headl = creat(); //創(chuàng)建鏈表　　printf("最初的鏈表如下：");　　display(headl);　　printf("\n\n");<

75、;p>　　int num, location;　　printf("請輸入您要查找的數(shù)：");　　scanf("%d", &num);　　if (locate(headl, num))　　printf("數(shù)字%

76、d在鏈表中的位置為：%d\n\n", num, locate(headl, num));　　else　　printf("數(shù)字%d在鏈表中不存在!\n\n", num);　　printf("請分別輸入您要插入到鏈表中的數(shù)以及想插入的位置（

77、用空格號間隔開）：");　　scanf("%d %d", &num, &location);　　if (insnode(headl, num, location))　　{ 　　p

78、rintf("插入新值以后的鏈表如下：");　　display(headl);　　printf("\n\n");　　} 　　else printf("輸入有誤!\n\n"

79、;);　　printf("請輸入您想刪除的結點位置：");　　scanf("%d", &location);　　if (delnode(headl, location))　　{

80、;　　printf("刪除第%d個結點后的鏈表如下：", location);　　display(headl);　　printf("\n\n");　　} <p

81、>　　else　　printf("輸入有誤! \n\n");　　}　　【運行截圖演示】　?、佟⑷缦旅娴倪\行截圖所示，創(chuàng)建帶有頭結點且

82、長度為8的單鏈表：4、8、2、-4、-6、1、9、-1。　　輸入要查詢的數(shù)“-6”，則查詢到單鏈表中數(shù)“-6”的存儲位置為“5”的下標號。　　輸入要插入的數(shù)和插入數(shù)的位置下標，便可以進行插入操作。程序中要求插入的數(shù)是“3”，插入數(shù)的位置下標為“5”，兩者之間用空格號隔開，則插入后的新單鏈表為：4、8、2、-4、3、-6、1、9、-1。

83、　　同理當輸入要執(zhí)行刪除操作的數(shù)位置下標，可以對該數(shù)刪除出線性表。程序中要求刪除的數(shù)下標是7，則執(zhí)行該刪除操作之后的新單鏈表為：4、8、2、-4、3、-6、9、-1。　?、?、如下面的運行截圖所示，創(chuàng)建帶有頭結點且長度為8的單鏈表，要查詢的數(shù)“3”不在該單鏈表中，所以程序執(zhí)行“error”。　?、?、如下面的運行截圖所示，創(chuàng)建帶頭結點且

84、長度為8的單鏈表，要插入數(shù)的位置下標“-1”不在該單鏈表中，所以程序執(zhí)行“error”。　?、?、如下面的運行截圖所示，創(chuàng)建帶頭結點且長度為8的單鏈表，要插入的位置下標“9”為單鏈表最大長度，所以程序執(zhí)行插入操作。　?、?、如下面的運行截圖所示，創(chuàng)建帶頭結點且長度為8的單鏈表，要插入的位置下標“10”超出單鏈表長度，所以程序不執(zhí)行插入操作。

85、;　?、?、如下面的運行截圖所示，創(chuàng)建帶頭結點且長度為8的單鏈表，要刪除數(shù)的位置下標“-2”不在該單鏈表中，所以程序執(zhí)行“error”。　?、?、如下面的運行截圖所示，創(chuàng)建帶頭結點且長度為8的單鏈表，要刪除數(shù)的位置下標“10”超出單鏈表長度，所以程序執(zhí)行“error”。　　三、順序棧的操作</

86、p>　　在順序棧上實現(xiàn)將非負十進制數(shù)轉換成二進制數(shù)。　　【數(shù)值轉換原理】　　十進制數(shù)N和其他d進制數(shù)的轉換時計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：　?。ㄆ渲校篸iv為整除運算，mod為求余運算）

87、　　假設現(xiàn)在要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的二進制數(shù)。　　由于上述計算過程是從低位到高位順序產生二進制數(shù)的各個數(shù)位，而打印輸出，一般來說應從高位到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的二進制數(shù)的各位順序進棧，則按出棧序列打印輸出的即為輸入對應的二進制數(shù)。　?。ㄆ洹緮?shù)

88、值轉換】在課本P48的算法3.2有解釋）　　【NO.3代碼】　　#include <stdio.h>　　#include <stdlib.h>　　#define MaxSize 50&l

89、t;p>　　typedef char ElemType;　　char digit[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";　　typedef struct　　{

90、　ElemType data[MaxSize];　　int top;　　}　　SqStack;　　void InitStack(SqStack *&s

91、)　　{　　s = (SqStack *)malloc(sizeof(SqStack));　　s -> top = -1;　　}　　int Push

92、(SqStack *&s, ElemType e)　　{　　if(s -> top == MaxSize - 1)　　return 0;　　s -> top++;</p&

93、gt;　　s -> data[s -> top] = e;　　return 1;　　}　　int Pop(SqStack *&s, ElemType &e)<

94、p>　　{　　if(s -> top == -1)　　return 0;　　e = s -> data[s -> top];　　s -> top--;return

95、1;　　}　　int GetTop(SqStack *s, ElemType &e)　　{　　if(s -> top == -1)<

96、b>　　return 0;　　e = s -> data[s -> top];　　return 1;　　}　　void DispStack(SqStack *

97、s)　　{ 　　int i;　　for(i = s -> top; i >= 0; i--) 　　printf("%c", s -> data[i]);&

98、lt;/p>　　printf("\n");　　}　　int fun(SqStack *s,int num, int k) //可將十進制轉換成任意進制　　{<p

99、>　　static int count = 0;　　int n;　　if(num < k)　　{　　Push(s, digit[num]);

100、　return count;　　}　　n = num % k;　　Push(s, digit[n]);　　fun(s,num/k, k);　　}</

101、p>　　int main()　　{　　SqStack *t;　　int i;　　InitStack(t);　　printf(&

102、quot;請輸入一個非負十進制數(shù)：");　　scanf("%d", &i);　　fun(t, i, 2); 　　printf("其二進制數(shù)為：");　　DispStack(t);<p

103、>　　free(t);　　return 0;　　}　　【運行截圖演示】　?、?、如下面的運行截圖所示，輸入非負十進制

104、整數(shù)“14”，經過數(shù)值轉換之后的二進制數(shù)為“1110”。　?、?、如下面的運行截圖所示，輸入十進制整數(shù)“-2”，由于“-2”為負數(shù)，所以無法經過數(shù)值轉換為二進制數(shù)。　　③、如下面的運行截圖所示，輸入非負十進制整數(shù)“0”，經過數(shù)值轉換之后的二進制數(shù)為“0”。　　四、查找算法<

105、;/p>　　在順序表中采用順序查找算法和折半查找算法尋找關鍵字X在順序表中的位置。　　【順序查找原理】　　從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關鍵字和給定值比較都不等，則表明表中

106、沒有所查記錄，查找不成功。　　在等概率情況下順序查找的平均長度為：　　【折半查找原理】　　先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。　　折半查找過程是以處于區(qū)間中間位置記錄的關鍵字和給定值比較，若相

107、等，則查找成功，若不等，則縮小范圍，直至新的區(qū)間中間位置記錄的關鍵字等于給定值或者查找區(qū)間的大小小于零時（表明查找不成功）為止。　　假設表中每個記錄的查找概率相等，則查找成功時折半查找的平均查找長度：　　【NO.4代碼】　　#include <stdio.h>&l

108、t;/p>　　#include <math.h>　　#define MAXL 1000　　#define INF 32767　　int process[MAXL],pn;　　//順序表的存儲結構<p&g

109、t;　　typedef int KeyType;　　typedef int InfoType;　　typedef struct　　{ 　　KeyType key;　　InfoType d

110、ata;　　} 　　NodeType;　　typedef NodeType SeqList[MAXL];　　//索引表的存儲結構　　typedef str

111、uct　　{ 　　KeyType key;　　int link;　　} 　　IdxType;

112、　　typedef IdxType IDX[MAXL];　　//順序查找算法　　int SeqSearch(SeqList R,int n,KeyType k)　　{</

113、p>　　int i=0;　　pn=0;　　while(i<n&&R[i].key!=k)　　{

114、process[pn++]=R[i].key;　　i++;　　} 　　if(i>=n) return -1;　　else return i;&l

115、t;b>　　} 　　//折半查找算法　　int BinSearch(SeqList R,int n,KeyType k)　　{ 　　int low=0,hig

116、h=n-1,mid;　　pn=0;　　while(low<=high)　　{　　mid=(low+high)/2;　　if(R[mid].key==

117、k) return mid;　　if(R[mid].key>k)　　{　　process[pn++]=R[mid].key;　　high=mid-1;　　} </p

118、>　　else　　{ 　　process[pn++]=R[mid].key;　　low=mid+1;　　}

119、;　　} 　　return -1;　　} 　　int main()　　{ 　　int n,i,k,m;&l

120、t;/p>　　SeqList R;　　IDX I;　　printf("(1)請輸入有/無序順序表的元素個數(shù)：\n");　　while(scanf("%d",&n)!=EOF)&

121、lt;p>　　{　　printf("請輸入有/無序順序表的%d個元素：\n",n);　　for(i=0;i<n;i++) 　　scanf("%d",&R[i].key);

122、printf("請輸入要查找的關鍵字：\n");　　scanf("%d",&k);　　printf("使用順序查找算法，");　　if(SeqSearch(R,n,k)!=-1)　　{&

123、lt;/b>　　printf("關鍵字%d的下標為：\n%d\t\n查找過程為：\n",k,SeqSearch(R,n,k));　　for(i=0;i<pn;i++) printf("%d ",process[i]);　　printf("%d\n\n&

124、quot;,k);　　}　　else printf("要查找的關鍵字%d不在無序順序表中\(zhòng)n\n",k);　　printf("(2)請輸入有序順序表的元素個數(shù)：\n");//10　　scanf(

125、"%d",&n);　　printf("請輸入有序順序表的%d個元素：\n",n);　　for(i=0;i<n;i++) 　　scanf("%d",&R[i].key);　　printf(&q

126、uot;請輸入要查找的關鍵字：\n");　　scanf("%d",&k);　　printf("使用折半查找算法，");　　if(BinSearch(R,n,k)!=-1)　　{

127、　　printf("關鍵字%d的下標為：\n%d\t\n查找過程為：\n",k,BinSearch(R,n,k));　　for(i=0;i<pn;i++) 　　printf("%d ",process[i]);　　printf

128、("%d\n\n",k);　　}　　else printf("要查找的關鍵字%d不在有序順序表中\(zhòng)n\n",k);　　return 0;

129、　}　　}　　【運行截圖演示】　?、?、如下面的運行截圖所示，使用順序查詢算法和折半查找算法，查找數(shù)“5”，其查找過程分別為：-3、5、8、9、-2、-1；3、-2、-1。　?、?/p>

130、、如下面的運行截圖所示，在無序順序表中使用順序查詢算法，查找數(shù)“6”，因數(shù)“6”位置下標超過表最大長度，即程序查找不到。　?、?、如下面的運行截圖所示，在無序順序表中使用順序查詢算法，查找數(shù)“1”，因為數(shù)“1”不在該表中，所以程序查找不到數(shù)“1”。　?、堋⑷缦旅娴倪\行截圖所示，在有序順序表中使用折半查詢算法，查找數(shù)“1”，因為數(shù)“1”不在該表中，所以程序查

131、找不到數(shù)“1”。　　五、排序算法　　將無序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列。　　【直接插入排序原理】　　是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的

132、有序表。　　排序的基本操作為：比較兩個關鍵字的大小和移動記錄。先分析一趟插入排序的情況。For循環(huán)的次數(shù)取決于待插記錄的關鍵字與前i-1個記錄的關鍵字之間的關系。則在整個排序過程（進行n-1趟插入排序）中，當待排序列中記錄按關鍵字非遞減有序排列，所需進行關鍵字間比較的次數(shù)達最小值n-1，記錄不需移動；反之，當待排序列中記錄按關鍵字非遞增有序排列是，總的比較次數(shù)達到最大值，記錄移動的次數(shù)也達最大值

133、。若待排序記錄是隨機的，即待排序列中的記錄可能出現(xiàn)的各種排列的概率相同，則我們可取上述最小值和最大值的平均值，作為直接插入排序時所需進行關鍵字間的比較次數(shù)和移動記錄的次數(shù)。　　【快速排序原理】　　快速排序是對起泡排序的一種改進。它的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一

134、部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。　　【NO.5代碼】　　#include<iostream.h>　　#include<stdlib.h>　　#define MAX 1

135、00　　//將無序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列　　typedef struct 　　{　　int data[MAX];　　int length;

136、;　　}　　sqlist;　　void init(sqlist &a)//線性表初始化　　{　　a.length=0;</

137、p>　　}　　void insert(sqlist &a ,int i,int x)// 插入元素,構造無序數(shù)列　　{　　int j;<

138、;p>　　if(i<0||i>a.length+1||a.length==100);　　else　　{　　for(j=a.length+1;j>i;j--)　　a.data

139、[j]=a.data[j-1];　　a.data[j]=x;　　a.length++;　　}　　} 　　//放在a.data[n]中，被排序的記錄放在a.

140、data[0..n-1]中，直接插入排序算法。　　void insertsort(sqlist &a)//直接插入排序算法　　{　　int i,j;　　int n=a.length;<

141、;/p>　　for(i=n-2;i>=0;i--) 　　if(a.data[i]>a.data[i+1]) 　　{ 　　a.data[n]=a.data[i];//a.data[n]是哨兵<

142、;b>　　j=i+1; 　　do　　{ 　　a.data[j-1]=a.data[j]; 　　j++;<

143、;p>　　}　　while(a.data[j]<a.data[n]);　　a.data[j-1]=a.data[n];　　}　　}</p&

144、gt;　　int Partition(sqlist &a,int i,int j)　　{　　int pivot=a.data[i];　　while(i<j)　　{

145、;　　while(i<j&&a.data[j]>=pivot) 　　j--; 　　if(i<j) 　　a.data[i++]=a.data[j]; </p&

146、gt;　　while(i<j&&a.data[i]<=pivot) 　　i++; 　　if(i<j) 　　a.data[j--]=a.data[i]; <

147、;p>　　} 　　a.data[i]=pivot; 　　return i;　　}　　void QuickSort(sqlist &a,int l

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

《數(shù)據(jù)結構與算法分析》課程設計順序表、單鏈表、順序棧、查找、排序算法

文檔簡介

溫馨提示

最新文檔

評論

《數(shù)據(jù)結構與算法分析》課程設計順序表、單鏈表、順序棧、查找、排序算法

文檔簡介

溫馨提示

最新文檔

評論

免費下載

《數(shù)據(jù)結構與算法分析》課程設計順序表、單鏈表、順序棧、查找、排序算法