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

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

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

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

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

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

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ù)元素和之間的邏輯關(guān)系發(fā)生了變化。　?。ㄆ洹静迦朐怼吭谡n本P23的算法2.3有解釋）　　【刪

9、除操作原理】　　反之，線性表的刪除操作是使長度為n的線性表：　　變成長度為n-1的線性表：　　數(shù)據(jù)元素、和之間的邏輯關(guān)系發(fā)生變化，為了在存儲結(jié)構(gòu)上放映這個變化，同樣需要移動元素。　?。ㄆ洹緞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);　　}　　【運(yùn)行截圖演示】　　①、如下面的運(yùn)行截圖所示，當(dāng)輸入的線性表長度設(shè)置為12的時候，該線性表最多能輸入12位數(shù)的長度。

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

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

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

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

35、t;p>　　【插入操作原理】　　為插入數(shù)據(jù)元素x，首先要生成一個數(shù)據(jù)域為x的結(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個元素a、b和x之間邏輯關(guān)系的變化。　　假設(shè)s為指向結(jié)點(diǎn)x的指針，則上述指針修改用語描述即為：<

36、;/p>　　【刪除操作原理】　　反之，在線性表中刪除元素b時，為在單鏈表中實(shí)現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需要修改結(jié)點(diǎn)a中的指針域即可。　　假設(shè)p為指向結(jié)點(diǎn)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”結(jié)束輸入。\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)//測鏈表的結(jié)點(diǎn)數(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個結(jié)點(diǎn)　　{　　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) //把鏈表中每個結(jié)點(diǎn)的值按從小到大排列　　{　　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中的結(jié)點(diǎn)　　{</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("請輸入您想刪除的結(jié)點(diǎn)位置：");　　scanf("%d", &location);　　if (delnode(headl, location))　　{

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

81、>　　else　　printf("輸入有誤! \n\n");　　}　　【運(yùn)行截圖演示】　?、?、如下面的運(yùn)行截圖所示，創(chuàng)建帶有頭結(jié)點(diǎn)且

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

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

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

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

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

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

88、值轉(zhuǎn)換】在課本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) //可將十進(jìn)制轉(zhuǎn)換成任意進(jìn)制　　{<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;請輸入一個非負(fù)十進(jìn)制數(shù)：");　　scanf("%d", &i);　　fun(t, i, 2); 　　printf("其二進(jìn)制數(shù)為：");　　DispStack(t);<p

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

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

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

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

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

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

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

110、ata;　　} 　　NodeType;　　typedef NodeType SeqList[MAXL];　　//索引表的存儲結(jié)構(gòu)　　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("請輸入要查找的關(guān)鍵字：\n");　　scanf("%d",&k);　　printf("使用順序查找算法，");　　if(SeqSearch(R,n,k)!=-1)　　{&

123、lt;/b>　　printf("關(guān)鍵字%d的下標(biāo)為：\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("要查找的關(guān)鍵字%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;請輸入要查找的關(guān)鍵字：\n");　　scanf("%d",&k);　　printf("使用折半查找算法，");　　if(BinSearch(R,n,k)!=-1)　　{

127、　　printf("關(guān)鍵字%d的下標(biāo)為：\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("要查找的關(guān)鍵字%d不在有序順序表中\(zhòng)n\n",k);　　return 0;

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

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

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

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

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

134、部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。　　【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)// 插入元素,構(gòu)造無序數(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è)設(shè)計

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載

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