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

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

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

3、修設(shè)計(jì)13棧2必修設(shè)計(jì)14隊(duì)列2必修驗(yàn)證15二叉樹的遍歷2必修驗(yàn)證16查找2必修設(shè)計(jì)17排序4必修設(shè)計(jì)1四、實(shí)驗(yàn)項(xiàng)目說(shuō)明實(shí)驗(yàn)一：順序表一、目的： 熟練掌握線性表的基本操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(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("按要求輸入順序表初始時(shí)的元素(切換用回車),以#結(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個(gè)值與x相等的元素，若找到，則返回其在L中

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

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

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; /空表長(zhǎng)度為0printf("請(qǐng)選擇您要進(jìn)行的操作：n");printf("0:退出n");printf("1:建立順序表Ln");printf(&

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

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

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

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

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

13、 掌握單鏈表的建立、插入、刪除等基本操作；三、示例程序： #include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定義結(jié)點(diǎn) char data10; /結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址畇truct node *next; /結(jié)點(diǎn)的指針域 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é)點(diǎn) scanf("%s",num); if(strcmp(num,"y")=0 | strcmp(num,"Y")=0) printf("Please input Delete_data:"); scanf("%s",ch); /輸入要?jiǎng)h除的字符串 DeleteList(head,ch); printlist(head); DeleteAll(head); /刪除所有結(jié)點(diǎn)，釋放內(nèi)存/=用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=

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

17、ot;#")!=0) pp=LocateNode(head,ch); /按值查找結(jié)點(diǎn)，返回結(jié)點(diǎn)指針 if(pp=NULL) /沒(méi)有重復(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é)點(diǎn)，找到則返回該結(jié)點(diǎn)的位置，否則返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode * p=head->next; /從開始結(jié)點(diǎn)比較 while( p && (strcmp(p->data,key)!=0 ) ) /直到p為NULL或p->data為key止p=p->next; /掃描下一個(gè)結(jié)點(diǎn) return p; /若p=NULL則查找失敗，否則p指向找到的值為key的結(jié)點(diǎn)/=刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=void DeleteList(Lin

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

20、 while(p->next)r=p->next;free(p);p=r; free(p);四、實(shí)驗(yàn)內(nèi)容 1、 分析、理解程序，將void DeleteList(LinkList head,char *key)函數(shù)補(bǔ)充完整。2、 調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)（如：bat，cat，eat，fat，hat，jat，lat，mat，#），測(cè)試程序的如下功能：不允許重復(fù)字符串的插入；根據(jù)輸入的字符串，找到相應(yīng)的結(jié)點(diǎn)并刪除。實(shí)驗(yàn)三 棧一、目的： 掌握棧的基本特點(diǎn)，能把遞歸算法運(yùn)用棧轉(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("請(qǐng)輸入十

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

24、IZE; int front,rear; SqQueue; /初始化隊(duì)void InitQueue(SqQueue *Q) Q->front=Q->rear=-1;int EmptyQueue_C(SqQueue *Q)/若隊(duì)列為空，返回1，否則返回0if(Q->rear=Q->front)return 1;else return 0;/EmptyQueue_C/ 取對(duì)頭元素char GetQueue_C(SqQueue *Q)/若隊(duì)列不為空，則返回隊(duì)首元素，否則返回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/入隊(duì)int EnQueue_C(SqQueue *Q, int e)/將元素e插入到隊(duì)列中，作為新的隊(duì)尾。操作成功返回1，否則返回0if(Q->front=(Q->rear+1)%MAXSIZE)/隊(duì)滿printf("Queue is full.n"); return 0;elseQ->rear=(Q->rear+1)%MAXSIZE; Q->datasQ->rea

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

27、>front;while(i!=Q->rear)i=(i+1)%MAXSIZE;printf("%d ",Q->datasi);elseprintf("當(dāng)前循環(huán)隊(duì)列為空!");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("請(qǐng)輸入楊輝三角的層數(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、); 四、實(shí)驗(yàn)內(nèi)容 1、 分析、理解程序。2、 運(yùn)行、驗(yàn)證示例程序能否打印楊輝三角。試描述什么叫楊輝三角。3、 試輸入不同的行數(shù)調(diào)試程序，當(dāng)行數(shù)超過(guò)11產(chǎn)生什么問(wèn)題，為什么。實(shí)驗(yàn)五 二叉樹的遍歷一、目的： 掌握二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷（遞歸和非遞歸）二、要求： 用遞歸算法實(shí)現(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