數(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)教師： 2021年04月目錄一、順序表的操作2【插入操作原理】2【刪除操作原理】2【NO.1代碼】3【運行截圖演示】7二、單鏈表的操作10【創(chuàng)立操作原理】10【插入操作原理】10【刪除操作原理】10【NO.2代碼】11【運行截圖演示】20三、順序棧的操作25【數(shù)值轉(zhuǎn)換原理】25【NO.3代碼】26【運行截圖演示】30四、查找算法32【順序查找原理】32【折半查找原理】32【NO.4代碼】33【運行截圖演示】38五、排序算法40【直接插入排序原理】40【快速排序原理】40

2、【NO.5代碼】41【運行截圖演示】46一、順序表的操作1插入元素操作：將新元素x插入到順序表a中第i個位置；2刪除元素操作：刪除順序表a中第i個元素?！静迦氩僮髟怼烤€性表的插入操作是指在線性表的第i-1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素，就是要是長度為n的線性表：變成長度為n+1的線性表：數(shù)據(jù)元素和之間的邏輯關(guān)系發(fā)生了變化。其【插入原理】在課本P23的算法2.3有解釋【刪除操作原理】反之，線性表的刪除操作是使長度為n的線性表：變成長度為n-1的線性表：數(shù)據(jù)元素、和之間的邏輯關(guān)系發(fā)生變化，為了在存儲結(jié)構(gòu)上放映這個變化，同樣需要移動元素。其【刪除原理】在課本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( "請輸入要插入的數(shù)：" ); scanf( "%d",&indata ); printf( "請輸入要插入的位置：" ); scanf( "%d",&inlocate ); insert( p,indata,inlocate ); printf( "插入后的數(shù)據(jù)：" );output(p);printf( "請輸入要刪除的位置：" ); 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( "請輸入原始數(shù)據(jù)個數(shù)：" );

6、 scanf( "%d",&( L->list ) ); L->list-; printf( "請輸入原始數(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);【運行截圖演示】、如下面的運行截圖所示，當輸入的線性表長度設(shè)置為12的時候，該線性表最多能輸入12位數(shù)的長度。輸入要插入的數(shù)和插入數(shù)的位置下標，便可以進行插入操作；同理當輸入要執(zhí)行刪除操作數(shù)的位置下標，可以將該數(shù)刪除出線性表。、如下面的運行截圖所示，當初始設(shè)置的線性表長度為5的時候，

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

10、入元素操作：將新元素x插入到單鏈表中第i個元素之后；3刪除元素操作：刪除單鏈表中值為x的元素。 【創(chuàng)立操作原理】在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱之為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲線性表的長度等的附加信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針即第一個元素結(jié)點的存儲位置。【插入操作原理】為插入數(shù)據(jù)元素x，首先要生成一個數(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的指針，那么上述指針修改用語描述即為： 【刪除操作

11、原理】反之，在線性表中刪除元素b時，為在單鏈表中實現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需要修改結(jié)點a中的指針域即可。假設(shè)p為指向結(jié)點a的指針，那么上述指針修改用語描述即為：【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("請輸入創(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)/測鏈表的結(jié)

13、點數(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個結(jié)點 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) /把鏈表中每個結(jié)點的值按從小到大排列 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é)點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("請輸入您要查找的數(shù)：");scanf("%d", &num); if (locate(headl, num) printf("數(shù)字%d

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

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

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

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

25、現(xiàn)將非負十進制數(shù)轉(zhuǎn)換成二進制數(shù)?！緮?shù)值轉(zhuǎn)換原理】十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換時計算機實現(xiàn)計算的根本問題，其解決方法很多，其中一個簡單算法基于以下原理：其中：div為整除運算，mod為求余運算假設(shè)現(xiàn)在要編制一個滿足以下要求的程序：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的二進制數(shù)。由于上述計算過程是從低位到高位順序產(chǎn)生二進制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從高位到低位進行，恰好和計算過程相反。因此，假設(shè)將計算過程中得到的二進制數(shù)的各位順序進棧，那么按出棧序列打印輸出的即為輸入對應(yīng)的二進制數(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) /可將十進制轉(zhuǎ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("請輸入一個非負十進制數(shù)：");scanf("%d", &i);fun(t, i, 2); printf("其二進制數(shù)為：");DispStack(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)鍵字和給定值的比擬，假設(shè)某個記錄的關(guān)鍵字和給定值比擬相等，那么查找成功，找到所查記錄；反之，假設(shè)直至第一個記錄，其關(guān)鍵字和給定值比擬都不等，那么說明表中沒有所查記錄，查找不成功。在等概率情況下順序查找的平均長度為：【折半查找原理】先確定待查記錄所在的范圍區(qū)間，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找過程是以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比擬，假設(shè)相等，那么查找成功，假設(shè)不等，那

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

32、f NodeType SeqListMAXL;/索引表的存儲結(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)請輸入有/無序順序表的元素個數(shù)：n"); while(scanf("

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

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

36、tf("請輸入要查找的關(guān)鍵字：n");scanf("%d",&k); printf("使用折半查找算法，"); if(BinSearch(R,n,k)!=-1) printf("關(guān)鍵字%d的下標為：n%dtn查找過程為：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;【運行截圖演示】、如下面的運行截圖所示，使用順序查詢算法和折半查找算法，查找數(shù)“5，其查找過程分別為：-3、5、8、9、-2、-1；3、-2、-1。、如下面的運行截圖所示，在無序順序表中使用順序查詢算法，查找數(shù)“6，因數(shù)“6位置下標超過表最大長度，即程序查找不到。、如下面的運行截圖所示，在無序順序表中使用順序查詢算法，查找數(shù)“1，因為數(shù)“1不在該表中，所以程序查找不到數(shù)“1。、如下面的運行截圖所示，在有序順序表中使用折半查詢算法，查找數(shù)“1，因為數(shù)“1不在該表中，所以程序查找不到數(shù)“1。五、排序算法將無序數(shù)列使用直接插入排序算法和快速排序算法將其排成遞增有序數(shù)列

38、?！局苯硬迦肱判蛟怼渴且环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ù)也達最大值。假設(shè)待排序記錄是隨機的，即待排序列中的記錄可能出現(xiàn)的各種排列的概率相同，那么我們

39、可取上述最小值和最大值的平均值，作為直接插入排序時所需進行關(guān)鍵字間的比擬次數(shù)和移動記錄的次數(shù)?！究焖倥判蛟怼靠焖倥判蚴菍ζ鹋菖判虻囊环N改良。它的根本思想是，通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬删植?，其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小，那么可分別對這兩局部記錄繼續(xù)進行排序，以到達整個序列有序?！綨O.5代碼】#include<iostream.h>#include<stdlib.h>#define MAX 100/將無序數(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)造無序數(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; /劃分后的基準記錄的位置if(low<high)/僅當區(qū)間長度大于1時才須排序pivotpos=Partition(a,low,high); QuickSort(a,low,pivotpos-1); QuickSort(a,pivotpos+1,high); void main()sqlist sq1,sq2;/線性表為sq1,sq2int i,