《數(shù)據(jù)結(jié)構(gòu)》實驗大綱

1、數(shù)據(jù)結(jié)構(gòu)實驗教學(xué)大綱開課單位： 寧德師范學(xué)院計算機系設(shè)置類別： 非獨立設(shè)課學(xué) 時： 16學(xué)時實驗項目總數(shù)： 7實驗教材：數(shù)據(jù)結(jié)構(gòu)習(xí)題集與上機指導(dǎo)，嚴蔚敏，清華大學(xué)出版社主要設(shè)備（環(huán)境）：微機、C語言編程環(huán)境（VC+）一、 教學(xué)目的數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，課程旨在使學(xué)生學(xué)會計算機加工的數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)，并進行相應(yīng)的運算。實驗是該課程實踐教學(xué)的重要環(huán)節(jié)，目的是培養(yǎng)學(xué)生根據(jù)求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，提高分析、設(shè)計、編程以及控制求解算法的時間、空間復(fù)雜性的能力。二、 基本要求數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的專業(yè)核心基

2、礎(chǔ)課程，其先修課程有至少一門高級語言。數(shù)據(jù)結(jié)構(gòu)課程將覆蓋計算機軟件實現(xiàn)中的大部分的基本算法，并具有一定的深度和廣度，使學(xué)生對計算機常用基礎(chǔ)算法有一個全盤的了解；通過此課的學(xué)習(xí)，學(xué)生應(yīng)該具有針對所給的問題設(shè)計和實現(xiàn)高效算法的能力。通過上機實驗，將使學(xué)生熟悉、掌握課堂教學(xué)中所學(xué)的大部分算法。同時，上機實習(xí)是對學(xué)生在軟件設(shè)計方面的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧等，以培養(yǎng)良好的編程風(fēng)格和科學(xué)作風(fēng)。通過理論聯(lián)系實際，以最終提高學(xué)生動手操作的能力以及分析問題的能力。三、 實驗項目設(shè)置實驗序號實驗名稱試驗學(xué)時試驗要求試驗類型每組人數(shù)1順序表2必修設(shè)計12單鏈表2必

3、修設(shè)計13棧2必修設(shè)計14隊列2必修驗證15二叉樹的遍歷2必修驗證16查找2必修設(shè)計17排序4必修設(shè)計1四、實驗項目說明實驗一：順序表一、目的： 熟練掌握線性表的基本操作在順序存儲結(jié)構(gòu)上的實現(xiàn)二、要求： 掌握順序表的建立、查找、插入、刪除等基本操作。三、示例程序：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30 struct SqListchar datasMAXSIZE;int length;typedef struct SqList SqList;/建立順序表Lvoid creat_Sq(SqList *L)

4、 char x; int j;/按要求建立順序表printf("按要求輸入順序表初始時的元素(切換用回車),以#結(jié)束：n"); fflush(stdin);scanf("%c",&x);j=0; while( x!='#') L->datasj=x; L->length+; j+; fflush(stdin);scanf("%c",&x); /查找操作int LocateElem_Sq(SqList *L, char x) /在順序線性表L中查找第1個值與x相等的元素，若找到，則返回其在L中

5、的位序，否則返回0int k;k=1; /k的初值為第1個元素的位序while(k<=L->length && L->datask-1!=x) k+;if(k<=L->length) return k;else return 0;/求順序表長度int Get_length(SqList *L)return L->length;/插入操作void ListInsert_Sq (SqList *L,int i,char e)/在順序表L的第i個位置前插入一個新的元素e */刪除操作void ListDelete_Sq(SqList *L,int

6、i)/在順序表L中刪除第i個數(shù)據(jù)元素int k;if(i<1)|(i>L->length)|(L->length=0)/出錯處理，考慮算法的健壯性printf("error"); /i值不合法或表已空則出錯elsefor (k=i; k<L->length; k+)/將第i+1至第n個元素逐一向前移一個位置L->datask-1=L->datask;L->length=L->length-1; /將順序表的長度減1/輸出順序表void PRINT(SqList *L)int i;printf("順序表的當

7、前值為：n");for(i=0;i<L->length;i+)printf("%c ",L->datasi);printf("n");main()SqList * L;int k;int i;char x;/初始化順序表 L=(SqList *)malloc(sizeof(SqList); L->length=0; /空表長度為0printf("請選擇您要進行的操作：n");printf("0:退出n");printf("1:建立順序表Ln");printf(&

8、quot;2:查找操作(查找某個元素的位序)n");printf("3:求順序表的長度n");printf("4:插入操作(在順序表L的第i個位置前插入一個新元素e)n");printf("5:刪除操作(刪除順序表L中的第i元素)n");printf("6:輸出操作(輸出順序表的當前值)n");scanf("%d",&k);while( k<0 | k>6)printf("您只能選擇0-6，請重新輸入:");scanf("%d"

9、;,&k);while( k>=0 && k<=6)switch(k) case 0: exit(0);case 1: creat_Sq(L); break;case 2: printf("請輸入待查找的元素x:"); fflush(stdin); scanf("%c",&x);printf("%d在順序表中的位序為:%dn",x,LocateElem_Sq(L, x);break;case 3: printf("順序表的長度為：%dn",Get_length(L); b

10、reak;case 4: printf("請輸入待插入元素的位置i及元素的值x:"); scanf("%d",&i); fflush(stdin); scanf("%c",&x); ListInsert_Sq (L,i,x);break;case 5: printf("請輸入待刪除元素的位置i:"); scanf("%d",&i); ListDelete_Sq(L,i);break;case 6: PRINT(L); break;default: printf("

11、;您只能選擇0-6，請重新輸入:"); printf("*n");printf("請選擇您要進行的操作：n");printf("0:退出n");printf("1:建立順序表Ln");printf("2:查找操作(查找某個元素的位序)n");printf("3:求順序表的長度n");printf("4:插入操作(在順序表L的第i個位置前插入一個新元素e)n");printf("5:刪除操作(刪除順序表L中的第i元素)n");p

12、rintf("6:輸出操作(輸出順序表的當前值)n");scanf("%d",&k);四、實驗內(nèi)容 1、 分析、理解程序。2、 完成插入操作的函數(shù)設(shè)計。3、 調(diào)試程序：建立12個元素的順序表SqList=c,h,i,n,a,w,e,l,c,o,m,e，分別實現(xiàn)以下操作：1) 查找元素y在SqList中的位序，輸出為O則表示“y不在SqList中”；2) 在SqList的元素6之前插入一個新元素#，輸出插入后的結(jié)果；3) 刪除SqList中第8個元素，輸出刪除后的結(jié)果實驗二 單鏈表一、目的： 熟練掌握線性表的基本操作在鏈式存儲結(jié)構(gòu)上的實現(xiàn)二、要求：

13、 掌握單鏈表的建立、插入、刪除等基本操作；三、示例程序： #include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定義結(jié)點 char data10; /結(jié)點的數(shù)據(jù)域為字符串struct node *next; /結(jié)點的指針域 ListNode;typedef ListNode* LinkList; / 自定義LinkList單鏈表類型LinkList CreatListR1(void);Li

14、stNode *LocateNode(LinkList head, char *key);void DeleteList(LinkList head,char *key);void printlist(LinkList head);void DeleteAll(LinkList head);/=主函數(shù)=void main() char ch10,num2; LinkList head; head=CreatListR1(); /用尾插入法建立單鏈表，返回頭指針 printlist(head); /遍歷鏈表輸出其值 printf(" Delete node (y/n):");

15、 /輸入"y"或"n"去選擇是否刪除結(jié)點 scanf("%s",num); if(strcmp(num,"y")=0 | strcmp(num,"Y")=0) printf("Please input Delete_data:"); scanf("%s",ch); /輸入要刪除的字符串 DeleteList(head,ch); printlist(head); DeleteAll(head); /刪除所有結(jié)點，釋放內(nèi)存/=用尾插入法建立帶頭結(jié)點的單鏈表=

16、LinkList CreatListR1(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成頭結(jié)點 ListNode *s,*r,*pp; r=head; r->next=NULL; printf("Input # to end "); /輸入"#"代表輸入結(jié)束 printf("Please input Node_data:"); scanf("%s",ch); /輸入各結(jié)點的字符串 while(strcmp(ch,&qu

17、ot;#")!=0) pp=LocateNode(head,ch); /按值查找結(jié)點，返回結(jié)點指針 if(pp=NULL) /沒有重復(fù)的字符串，插入到鏈表中 s=(ListNode *)malloc(sizeof(ListNode); strcpy(s->data,ch); r->next=s; r=s; r->next=NULL; printf("Input # to end "); printf("Please input Node_data:"); scanf("%s",ch); return hea

18、d; /返回頭指針/=按值查找結(jié)點，找到則返回該結(jié)點的位置，否則返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode * p=head->next; /從開始結(jié)點比較 while( p && (strcmp(p->data,key)!=0 ) ) /直到p為NULL或p->data為key止p=p->next; /掃描下一個結(jié)點 return p; /若p=NULL則查找失敗，否則p指向找到的值為key的結(jié)點/=刪除帶頭結(jié)點的單鏈表中的指定結(jié)點=void DeleteList(Lin

19、kList head,char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找結(jié)點的 */=打印鏈表=void printlist(LinkList head) ListNode *p=head->next; /從開始結(jié)點打印 while(p)printf("%s, ",p->data);p=p->next; printf("n");/=刪除所有結(jié)點，釋放空間=void DeleteAll(LinkList head) ListNode *p=head,*r;

20、 while(p->next)r=p->next;free(p);p=r; free(p);四、實驗內(nèi)容 1、 分析、理解程序，將void DeleteList(LinkList head,char *key)函數(shù)補充完整。2、 調(diào)試程序，并設(shè)計輸入數(shù)據(jù)（如：bat，cat，eat，fat，hat，jat，lat，mat，#），測試程序的如下功能：不允許重復(fù)字符串的插入；根據(jù)輸入的字符串，找到相應(yīng)的結(jié)點并刪除。實驗三 棧一、目的： 掌握棧的基本特點，能把遞歸算法運用棧轉(zhuǎn)換成非遞歸算法二、要求： 掌握順序棧的建立、入棧、出棧等操作三、示例程序： #include<stdio.h

21、>#include<stdlib.h>#define MAXSIZE 10typedef structint datasMAXSIZE;int top;SqStack;void InitStack(SqStack *s)s->top=-1;/InitStackint EmptyStack(SqStack *s) /若?？辗祷?；否則返回0。if (s->top=-1)return 1; elsereturn 0;/EmptyStack void Push(SqStack *s, int e) /若棧滿返回0；否則將e入棧，并返回1。if(s->top=MAX

22、SIZE-1) printf("Overflown"); else s->top+; s->datass->top=e;/Pushint Pop(SqStack *s)/若?？談t返回NULL；否則返回棧頂元素，棧頂指示器遞減。int e;if (EmptyStack(s) printf("Underflown"); return(0);else e=s->datass->top; s->top-; return e; /Popmain() SqStack *s; int k,t; * printf("請輸入十

23、進制的數(shù):");scanf("%d",&k);while(k!=0)*while (!(EmptyStack(s)*printf("n"); 四、實驗內(nèi)容 補充主函數(shù)實現(xiàn)：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。實驗四 隊列一、目的： 掌握隊列的特點和隊列的基本操作二、要求： 熟練掌握順序隊列的建立、入隊、出隊等操作。三、示例程序： #include<stdio.h>#include<stdlib.h>#define MAXSIZE 20typedef structint datasMAXS

24、IZE; int front,rear; SqQueue; /初始化隊void InitQueue(SqQueue *Q) Q->front=Q->rear=-1;int EmptyQueue_C(SqQueue *Q)/若隊列為空，返回1，否則返回0if(Q->rear=Q->front)return 1;else return 0;/EmptyQueue_C/ 取對頭元素char GetQueue_C(SqQueue *Q)/若隊列不為空，則返回隊首元素，否則返回NULLint e;if(EmptyQueue_C(Q) printf("Queue is e

25、mptyn"); return(0);else e=Q->datas(Q->front+1)%MAXSIZE; return e;/GetQueue_C/入隊int EnQueue_C(SqQueue *Q, int e)/將元素e插入到隊列中，作為新的隊尾。操作成功返回1，否則返回0if(Q->front=(Q->rear+1)%MAXSIZE)/隊滿printf("Queue is full.n"); return 0;elseQ->rear=(Q->rear+1)%MAXSIZE; Q->datasQ->rea

26、r=e; return 1;/EnQueue_C/出隊int DeQueue_C(SqQueue *Q) /刪除隊頭元素，若操作成功返回1，否則返回0if(EmptyQueue_C(Q)printf("Queue is empty.n"); return 0;elseQ->front=(Q->front+1)%MAXSIZE; return 1;/DeQueue_C/輸出隊void PRINT(SqQueue *Q)int i;if(Q->front!=Q->rear)printf("當前循環(huán)隊列中從頭到尾的元素為：");i=Q-

27、>front;while(i!=Q->rear)i=(i+1)%MAXSIZE;printf("%d ",Q->datasi);elseprintf("當前循環(huán)隊列為空!");putchar('n');main()SqQueue *Q;int n;int i,j,k,s1,s2; Q=(SqQueue *)malloc(sizeof(SqQueue);InitQueue(Q);EnQueue_C(Q,1);printf("請輸入楊輝三角的層數(shù)：n"); scanf("%d",&am

28、p;n); printf("1n"); for(i=2;i<=n;i+) / for(k=0;k<n-i;k+) / printf(" "); for(j=1,s1=0;j<i;j+) int s2; s2=GetQueue_C(Q);DeQueue_C(Q); printf("%d",s1+s2); printf(" "); EnQueue_C(Q,s1+s2); s1=s2; printf("1"); EnQueue_C(Q,1); printf("n"

29、); 四、實驗內(nèi)容 1、 分析、理解程序。2、 運行、驗證示例程序能否打印楊輝三角。試描述什么叫楊輝三角。3、 試輸入不同的行數(shù)調(diào)試程序，當行數(shù)超過11產(chǎn)生什么問題，為什么。實驗五 二叉樹的遍歷一、目的： 掌握二叉樹的存儲結(jié)構(gòu)和遍歷（遞歸和非遞歸）二、要求： 用遞歸算法實現(xiàn)二叉樹的遍歷三、示例程序： #include<stdio.h> #include<stdlib.h> #define MAXCSIZE 100 typedef int TElemType; typedef struct BitNode TElemType data; struct BitNode *l

30、child,*rchild; BitNode,*BitTree; /*二叉樹的構(gòu)建*/BitTree CreateBiTree(void) BitTree bt; TElemType x; scanf("%d",&x); if(x=-1) bt=NULL; else bt=(BitTree)malloc(sizeof(BitNode); bt->data=x; bt->lchild=CreateBiTree(); bt->rchild=CreateBiTree(); return bt; /*二叉樹的中序遍歷*/ void InOrderTraverse(BitTree bt) if(bt!=NULL) InOrderTraverse(bt->lchild); printf("%d",bt->data); InOrderTraverse(bt->rchild); /*二叉樹的后序遍歷*/ void PostOrderTraver