第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課教案
數(shù)據(jù)結(jié)構(gòu)教案
實(shí)驗(yàn)一：線性表的順序表示與實(shí)現(xiàn)
實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)
一．實(shí)驗(yàn)?zāi)康模?/p>
1．掌握線性表的順序存儲(chǔ)結(jié)構(gòu)；
2．掌握在順序表上進(jìn)行的插入、刪除、查找、修改等操作。
二．實(shí)驗(yàn)內(nèi)容：
1．分別建立順序表，并輸入初始數(shù)據(jù)；
2．對(duì)順序表分別編寫插入、刪除、查找、修改等函數(shù)。
三．實(shí)驗(yàn)重點(diǎn)：
順序表的建立及操作。
四．實(shí)驗(yàn)要求：
1．用C語(yǔ)言編寫程序源代碼；
2．要分別完成建立、插入、刪除、查找、修改五種功能。3．源程序必須編譯調(diào)試成功，獨(dú)立完成。
五． 實(shí)驗(yàn)器材：
一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。
六．實(shí)驗(yàn)步驟：
順序表 ：
1．定義頭文件和順序表的存儲(chǔ)結(jié)構(gòu)類型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include
return overflow;l->length=0;l->listsize=list_init_size;return ok;}
3．編寫對(duì)順序表進(jìn)行插入操作的函數(shù)： status listinsert(sqlist *l,int i,elemtype e){ elemtype *newbase,*q,*p;if(i<1||i>listlength(*l)+1)
return error;if(l->length==l->listsize)
{ newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype));
if(!newbase)
return overflow;
l->listsize+=listincrement;
} q=&(l->elem[i-1]);for(p=&(l->elem[l->length])-1;p>=q;--p)
*(p+1)=*p;*q=e;++l->length;return ok;}
4．編寫對(duì)順序表進(jìn)行刪除操作的函數(shù)：
status listdelete(sqlist *l,int i,elemtype *e){ elemtype *p,*q;if(i<1||i>l->length)
return error;p=&(l->elem[i-1]);*e=*p;q=l->elem+l->length-1;for(++p;p<=q;++p)
*(p-1)=*p;--l->length;return ok;}
5．編寫對(duì)順序表進(jìn)行查找操作的函數(shù)： status getelem(sqlist l,int i,elemtype *e){ if(i<1||i>listlength(l))return error;*e=l.elem[i-1];return ok;}
6．編寫對(duì)順序表進(jìn)行修改操作的函數(shù)： status locateelem(sqlist l,elemtype e){ int i;for(i=0;i if(l.elem[i]==e) return i+1;return 0;} 7．編寫實(shí)現(xiàn)兩個(gè)線性表的歸并操作的函數(shù) void mergelist(sqlist la,sqlist lb,sqlist *lc){ int i,j,k;int la_len,lb_len;elemtype ai,bj;i=j=1;k=0;listinit(lc);la_len=listlength(la);lb_len=listlength(lb);while(i<=la_len&&j<=lb_len){ getelem(la,i,&ai);getelem(lb,j,&bj);if(ai<=bj) { listinsert(lc,++k,ai); ++i; } else { listinsert(lc,++k,bj); ++j; } } while(i<=la_len){ getelem(la,i++,&ai);listinsert(lc,++k,ai);} while(j<=lb_len) { getelem(lb,j++,&bj);listinsert(lc,++k,bj); } } 8．銷毀線性表、清空線性表、判空、求表長(zhǎng)等 status destroylist(sqlist *l){ if(l->elem)free(l->elem),l->elem=null;return ok;} status clearlist(sqlist *l){ l->length=0;return ok;} status listempty(sqlist l){ return(l.length==0);} status listlength(sqlist l){ return l.length;} 9．打印線性表 void print(sqlist l){ int i;printf(“nlist: ”);for(i=0;i 10． 編寫主函數(shù) void main(){ int i;int n;elemtype a;sqlist l,la,lb,lc;clrscr();listinit(&l);listinit(&la);listinit(&lb); printf(“please input list number”);scanf(“%d”,&n);printf(“n”);for(i=0;i scanf(“%d”,&a); listinsert(&l,i+1,a);} print(l);printf(“nlist length:%d”,listlength(l)); getelem(l,4,&a);printf(“ngetelem(l,4,&a),%d”,a); listdelete(&l,3,&a);printf(“nlistdelete(&l,3,&a),%d”,a);print(l); printf(“ninput list la”); for(i=0;i<5;i++){ scanf(“%d”,&a); listinsert(&la,i+1,a);} printf(“ninput list lb”);for(i=0;i<7;i++){ scanf(“%d”,&a); listinsert(&lb,i+1,a);} mergelist(la,lb,&lc);print(la);print(lb);print(lc);} 實(shí)驗(yàn)二：鏈表 實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí) 一．實(shí)驗(yàn)?zāi)康模?/p> 11． 掌握單、雙向鏈表的存儲(chǔ)結(jié)構(gòu)； 12． 掌握在單、雙向鏈表上進(jìn)行的插入、刪除、查找、修改等操作。 二．實(shí)驗(yàn)內(nèi)容： 4．分別建立單、雙向鏈表，并輸入初始數(shù)據(jù)； 5．對(duì)兩種單、雙向鏈表分別編寫插入、刪除、查找、修改等函數(shù)。 三．實(shí)驗(yàn)重點(diǎn)： 單向鏈表的建立及操作。 四．實(shí)驗(yàn)要求： 1．用C語(yǔ)言編寫程序源代碼； 2．要分別完成建立、插入、刪除、查找、修改五種功能。6．源程序必須編譯調(diào)試成功，獨(dú)立完成。 五． 實(shí)驗(yàn)器材： 一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。 六．實(shí)驗(yàn)步驟： 單鏈表 ： 1．定義頭文件和單鏈表的結(jié)構(gòu)體類型 #include int data; struct LNode *next;}LNode, *LinkList; 2．編寫構(gòu)造單鏈表的函數(shù) void InitList_L(LinkList L){ LinkList p,q;int i,b,j=0;p=L;printf(“請(qǐng)輸入鏈表中元素的值，用-1表示輸入結(jié)束：n”);do { scanf(“%d”,&b);q=(LinkList)malloc(sizeof(LNode));q->data=b;p->next=q;p=p->next;j+=1;} while(b!=-1);p->next=NULL;p=L;for(i=1;i 13． 編寫對(duì)單鏈表進(jìn)行插入操作的函數(shù)： void ListInsert_L(LinkList L,int r,int e){ LinkList p,s; int q=1,i,j=0; p=L; while(q>=1&&q<=r-1) { p=p->next; ++q; } s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; p=L;while(p->next!=NULL) { p=p->next; j+=1; } p=L; printf(“插入一個(gè)新結(jié)點(diǎn)后的鏈表為：n”); for(i=1;i { p=p->next; printf(“%dn”,p->data); } printf(“插入一個(gè)新結(jié)點(diǎn)后鏈表結(jié)點(diǎn)的個(gè)數(shù)為:%dn”,j-1); printf(“***************************************n”);} 14． 編寫對(duì)單鏈表進(jìn)行刪除操作的函數(shù)： void ListDelete_L(LinkList L,int r){ LinkList p,s;int q=1,i,e;p=L;if(r<1||r>k){ printf(“刪除的位置不正確n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;++q;} s=p->next;p->next=s->next;e=s->data;k=k-1;printf(“刪除的結(jié)點(diǎn)的值為：%dn”,e);printf(“刪除一個(gè)結(jié)點(diǎn)后的鏈表為：n”);p=L;for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“刪除一個(gè)結(jié)點(diǎn)后鏈表結(jié)點(diǎn)的個(gè)數(shù)為:%dn”,k);printf(“***************************************n”);} } 15． 編寫對(duì)單鏈表進(jìn)行查找操作的函數(shù)： void GetElem_L(LinkList L,int r){ LinkList p;int q=1,e;p=L;if(r<1||r>k){ printf(“第%d個(gè)元素不存在n”,r);printf(“***************************************n”);} else { while(q>=1&&q<=r){ p=p->next;q++;} e=p->data;printf(“第%d個(gè)元素的值為:n%dn”,r,e);printf(“***************************************n”);} } 16． 編寫對(duì)單鏈表進(jìn)行修改操作的函數(shù)： void UpdateElem_L(LinkList L,int r){ LinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d個(gè)元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“請(qǐng)輸入修改后該結(jié)點(diǎn)的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d個(gè)元素的值后鏈表為：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 17． 編寫主函數(shù) void main(){ int m,n=0;LinkList l;l=(LinkList)malloc(sizeof(LNode));InitList_L(l);while(n!=-1){ printf(“請(qǐng)選擇對(duì)鏈表進(jìn)行何種操作:n輸入1表示對(duì)鏈表進(jìn)行插入操作n輸入2表示對(duì)鏈表進(jìn)行刪除操作n輸入3表示對(duì)鏈表進(jìn)行查找操作n輸入4表示對(duì)鏈表進(jìn)行修改操作n輸入-1表示操作結(jié)束n”);printf(“***************************************n”);scanf(“%d”,&n);printf(“***************************************n”);switch(n){ case 1: printf(“請(qǐng)輸入在第幾個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)：n”);scanf(“%d”,&m);printf(“***************************************n”);ListInsert_L(l,m);break;case 2: printf(“請(qǐng)輸入刪除第幾個(gè)結(jié)點(diǎn)：n”);scanf(“%d”,&m);printf(“***************************************n”);ListDelete_L(l,m);break;case 3: printf(“請(qǐng)輸入查找第幾個(gè)結(jié)點(diǎn)的值：n”);scanf(“%d”,&m);printf(“***************************************n”);GetElem_L(l,m);break;case 4: printf(“請(qǐng)輸入修改第幾個(gè)結(jié)點(diǎn)的值：n”);scanf(“%d”,&m);printf(“***************************************n”);UpdateElem_L(l,m);break;} } printf(“操作結(jié)束!n”);} 雙向鏈表 1．定義頭文件和雙向鏈表的結(jié)構(gòu)體類型 #include 2．編寫構(gòu)造雙向鏈表的函數(shù) void InitList_DuL(DuLinkList L){ DuLinkList p,q;int i,b=0,j=0;p=L;printf(“請(qǐng)輸入鏈表中元素的值，用-1表示輸入結(jié)束：n”);while(b!=-1){ scanf(“%d”,&b);q=(DuLinkList)malloc(sizeof(DuLNode));q->data=b;p->next=q;q->prior=p;p=p->next;j+=1;} k=j-1;p->next=NULL;p=L;printf(“***************************************n”);printf(“創(chuàng)建的雙向鏈表為：n”);for(i=1;i 3．對(duì)雙向鏈表進(jìn)行插入操作的函數(shù) void ListInsert_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,n;p=L;if(r<1||r>k){ printf(“插入的位置不正確!n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;q++;} s=(DuLinkList)malloc(sizeof(DuLNode));printf(“請(qǐng)輸入插入的結(jié)點(diǎn)的值：n”);scanf(“%d”,&n);printf(“***************************************n”);s->data=n;s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;k=k+1;p=L;printf(“插入一個(gè)新結(jié)點(diǎn)后的鏈表為：n”);for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“插入一個(gè)新結(jié)點(diǎn)后鏈表結(jié)點(diǎn)的個(gè)數(shù)為:%dn”,k);printf(“***************************************n”);} } 7． 寫對(duì)雙向鏈表進(jìn)行刪除操作的函數(shù) void ListDelete_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,e;p=L;if(r<1||r>k) { printf(“刪除的位置不正確n”); printf(“***************************************n”);} else { while(q>=1&&q<=r-1) { p=p->next; ++q; } s=p->next; p->next=s->next; s->next->prior=p; e=s->data; k=k-1; printf(“刪除的結(jié)點(diǎn)的值為：%dn”,e); printf(“刪除一個(gè)結(jié)點(diǎn)后的鏈表為：n”); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“刪除一個(gè)結(jié)點(diǎn)后鏈表結(jié)點(diǎn)的個(gè)數(shù)為:%dn”,k); printf(“***************************************n”);} } 8． 編寫對(duì)雙向鏈表進(jìn)行查找操作的函數(shù) void GetElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,e;p=L;if(r<1||r>k) { printf(“第%d個(gè)元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } e=p->data; printf(“第%d個(gè)元素的值為:n%dn”,r,e); printf(“***************************************n”);} } 9． 編寫對(duì)雙向鏈表進(jìn)行修改操作的函數(shù) void UpdateElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d個(gè)元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“請(qǐng)輸入修改后該結(jié)點(diǎn)的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d個(gè)元素的值后鏈表為：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 10． 編寫主函數(shù) void main(){ int m,n=0;DuLinkList l;l=(DuLinkList)malloc(sizeof(DuLNode));InitList_DuL(l);while(n!=-1){ printf(“請(qǐng)選擇對(duì)鏈表進(jìn)行何種操作:n輸入1表示對(duì)鏈表進(jìn)行插入操作n輸入2表示對(duì)鏈表進(jìn)行刪除操作n輸入3表示對(duì)鏈表進(jìn)行查找操作n輸入4表示對(duì)鏈表進(jìn)行修改操作n輸入-1表示操作結(jié)束n”); printf(“***************************************n”); scanf(“%d”,&n); printf(“***************************************n”); switch(n) { case 1: printf(“請(qǐng)輸入在第幾個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)：n”); scanf(“%d”,&m); printf(“***************************************n”); ListInsert_DuL(l,m); break; case 2: printf(“請(qǐng)輸入刪除第幾個(gè)結(jié)點(diǎn)：n”); scanf(“%d”,&m); printf(“***************************************n”); ListDelete_DuL(l,m); break; case 3: printf(“請(qǐng)輸入查找第幾個(gè)結(jié)點(diǎn)的值：n”); scanf(“%d”,&m); printf(“***************************************n”); GetElem_DuL(l,m); break; case 4: printf(“請(qǐng)輸入修改第幾個(gè)結(jié)點(diǎn)的值：n”); scanf(“%d”,&m); printf(“***************************************n”); UpdateElem_DuL(l,m); break; } } printf(“操作結(jié)束!n”);} 實(shí)驗(yàn)三：棧、隊(duì)列 實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí) 一．實(shí)驗(yàn)?zāi)康模?/p> 1．掌握棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)； 2．掌握在棧、隊(duì)列上進(jìn)行的各種操作。 二．實(shí)驗(yàn)內(nèi)容： 1．編寫模擬Hanoi塔函數(shù)計(jì)算的程序，掌握棧在遞歸中的作用； 2．編寫循環(huán)隊(duì)列的進(jìn)隊(duì)、出隊(duì)、初始化等函數(shù)。（2選1） 三．實(shí)驗(yàn)重點(diǎn)： 對(duì)棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)的理解。 四．實(shí)驗(yàn)難點(diǎn)： 循環(huán)隊(duì)列操作函數(shù)的編寫。 五．實(shí)驗(yàn)要求： 1．用C語(yǔ)言編寫程序源代碼； 2．源程序必須編譯調(diào)試成功，獨(dú)立完成。 六．實(shí)驗(yàn)器材： 一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。 七．實(shí)驗(yàn)步驟： Hanoi塔程序的編寫 1．定義頭文件： #include 2．編寫move函數(shù)： void move(char x,char y){ printf(“%c-->%cn”,x,y);} 3．編寫Hanoi塔函數(shù)： void hanoi(int n,char a,char b,char c){ if(n==1) move(a,c); else { hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); } } 4．編寫主函數(shù)： void main(){ int m;printf(“請(qǐng)輸入需要移動(dòng)的盤子數(shù)：n”);scanf(“%d”,&m);printf(“%d個(gè)盤子通過(guò)B從A移動(dòng)到C的過(guò)程如下：n”,m);hanoi(m,'A','B','C');} 循環(huán)隊(duì)列操作函數(shù)的編寫 1．定義頭文件和結(jié)構(gòu)體類型等： #include int front;//順序存儲(chǔ)，即地址，所以用下標(biāo)表示元素，front是第一個(gè)元 //的下標(biāo) int rear;//rear是最后一個(gè)元素的下標(biāo) }SqQueue; 2．編寫初始化函數(shù)： int InitQueue(SqQueue &Q){ Q.base=(int*)malloc(MAXQSIZE*sizeof(int));if(!Q.base) return 0; else { Q.front=0; Q.rear=0; return 1; } } 3．編寫進(jìn)隊(duì)函數(shù)： void EnQueue(SqQueue &Q,char e){ if((Q.rear+1)%MAXQSIZE==Q.front) printf(“隊(duì)列滿”);else { Q.base[Q.rear]=e;//Q.base表示數(shù)組的地址也即數(shù)組名；Q.rear表示引用結(jié)//構(gòu)體類型變量Q中的一個(gè)成員rear ,也即是數(shù)組中下標(biāo)為rear的元素 Q.rear=(Q.rear+1)%MAXQSIZE; } } 4．編寫出隊(duì)函數(shù)： void DeQueue(SqQueue &Q){ char e;if(Q.front==Q.rear) printf(“隊(duì)列空n”);else { e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } } 5．編寫顯示功能函數(shù)： void Display(SqQueue Q){ int i; if(Q.front==Q.rear) printf(“隊(duì)列空n”);else { i=Q.front; printf(“隊(duì)列中的元素如下:”); do { printf(“%c”,Q.base[i]); i=(i+1)%MAXQSIZE; } while(i!=Q.rear); } } 6．編寫主函數(shù)： void main(){ SqQueue Q; char r; int i=0; InitQueue(Q); while(i!=-1) { printf(“請(qǐng)選擇對(duì)隊(duì)列進(jìn)行何種操作:n 輸入1表示進(jìn)行入隊(duì)操作n 輸入2表示進(jìn)行出隊(duì)操作n 輸入-1表示不進(jìn)行任何操作n”); printf(“********************************************n”); scanf(“%d”,&i); printf(“********************************************n”); switch(i) { case 1: printf(“請(qǐng)輸入要入隊(duì)的元素的值,輸入#表示結(jié)束:n”); printf(“****************************************n”); scanf(“%c”,&r); while(r!='#') { EnQueue(Q,r); scanf(“%c”,&r); } printf(“****************************************n”); Display(Q); printf(“****************************************n”); break; case 2: DeQueue(Q); Display(Q); break; } } } 實(shí)驗(yàn)四：樹 實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí) 一．實(shí)驗(yàn)?zāi)康模?/p> 1．掌握二叉樹的存儲(chǔ)結(jié)構(gòu)； 2．掌握在二叉樹上進(jìn)行的各種操作。 二．實(shí)驗(yàn)內(nèi)容與基本要求： 1．編寫二叉樹的各種操作函數(shù)，包括建立、初始化、添加、刪除、查找等； 2．編寫對(duì)二叉樹進(jìn)行三種遍歷的函數(shù)； 3．編寫8皇后的模擬計(jì)算程序。 (3選2) 三．實(shí)驗(yàn)重點(diǎn)： 二叉樹的各種操作及遍歷的函數(shù)。 四．實(shí)驗(yàn)難點(diǎn)： 二叉樹的三種遍歷函數(shù)的編寫。 五．實(shí)驗(yàn)器材： 一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。 六．實(shí)驗(yàn)步驟： 1．建立、初始化二叉樹； struct tree //聲明樹的結(jié)構(gòu) { struct tree *left; int data; struct tree *right;};typedef struct tree treenode;typedef treenode *b_tree; //聲明二叉樹鏈表 //插入二叉樹的節(jié)點(diǎn) b_tree insert_node(b_tree root,int node){ b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_tree)malloc(sizeof(treenode)); //建立新節(jié)點(diǎn)的內(nèi)存空間 newnode->data=node; newnode->right=NULL; newnode->left=NULL;if(root=NULL) return newnode; else { currentnode=root; while(currentnode!=NULL) { parentnode=currentnode; if(currentnode->data>node) currentnode=currentnode->left; else currentnode=currentnode->right; } if(parentnode->data>node) parentnode->left=newnode; else parentnode->right=newnode; return root;} } // 建立二叉樹 b_tree create_btree(int *data,int len){ b_tree root=NULL; int i; for(i=0;i root=insert_node(root,data[i]);//調(diào)用insert_node函數(shù)，參數(shù)為空指針 //root和數(shù)組中元素data[i]，//insert_node函數(shù)的返回值賦給 //create_btree函數(shù)中定義root，并作為 //create_btree函數(shù)的返回值返回 return root;//返回值為root } 2．編寫對(duì)二叉樹進(jìn)行的各種操作的函數(shù)，包括、添加、刪除、查找等； 3．編寫對(duì)二叉樹進(jìn)行三種遍歷的函數(shù)； //二叉樹先序遍歷 void preorder(b_tree point){ if(point!=NULL) { preorder(point->left);//遞歸 printf(“%d”,point->data); preorder(point->right);//遞歸 } } //二叉樹中序遍歷 void inorder(b_tree point){ if(point!=NULL) { inorder(point->left);//遞歸 printf(“%d”,point->data); inorder(point->right);//遞歸 } } //二叉樹后序遍歷 void postorder(b_tree point){ if(point!=NULL) { postorder(point->left);//遞歸 printf(“%d”,point->data); postorder(point->right);//遞歸 } } //主程序 void main(){ b_tree root=NULL; int index; int value; int nodelist[20]; printf(“n please input the elements of binary tree(exit for 0):n”); index=0; //讀取數(shù)值存到數(shù)組中 scanf(“%d”,&value); while(value!=0) { nodelist[index]=value; index=index+1; scanf(“%d”,&value); } //建立二叉樹 root=create_btree(nodelist,index);//主函數(shù)調(diào)用創(chuàng)建函數(shù)，參數(shù)為數(shù)組名和 //長(zhǎng)度，創(chuàng)建函數(shù)的返回值(返回的本身 //是root)賦給主函數(shù)中定義root，并作//為參數(shù)傳給inorder函數(shù) //先序遍歷二叉樹 printf(“nThe preorder traversal result is :”); preorder(root);//主函數(shù)調(diào)用inorder函數(shù) printf(“n”);//中序遍歷二叉樹 printf(“nThe inorder traversal result is :”); inorder(root);//主函數(shù)調(diào)用inorder函數(shù) printf(“n”);//后序遍歷二叉樹 printf(“nThe postorder traversal result is :”); postorder(root);//主函數(shù)調(diào)用inorder函數(shù) printf(“n”);} 4．編寫8皇后的模擬計(jì)算程序。實(shí)驗(yàn)五：圖 實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí) 一．實(shí)驗(yàn)?zāi)康模?/p> 1．掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)； 2．掌握在圖上進(jìn)行的各種操作。 二．實(shí)驗(yàn)內(nèi)容與基本要求： 1．編寫圖的各種操作函數(shù)，包括建立、初始化、添加、刪除、查找等； 2．編寫建立最小生成樹的程序； 3．編寫計(jì)算兩點(diǎn)間最短路徑的程序。（3選2） 三．實(shí)驗(yàn)重點(diǎn)： 掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu) 四．實(shí)驗(yàn)難點(diǎn)： 編寫計(jì)算兩點(diǎn)間最短路徑的程序 五．實(shí)驗(yàn)器材： 一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。 六．實(shí)驗(yàn)步驟 計(jì)算兩點(diǎn)間最短路徑： 1．義頭文件等 #include #define max 10000//設(shè)定一個(gè)極大值 2．編寫主函數(shù) void main(){ int D[vex][vex][vex];//定義一個(gè)三維數(shù)組，用來(lái)一次一次的迭代，按 //FLOYD算法求出結(jié)點(diǎn)之間的最短路徑 int arcs[vex][vex]={0,4,11,6,0,2,3,max,0};//鄰接矩陣 int i,j,k; for(i=0;i //空間進(jìn)行初始化 for(k=0;k for(i=0;i for(j=0;j if(D[k-1][i][j] D[k][i][j]=D[k-1][i][j];else D[k][i][j]=D[k-1][i][k]+D[k-1][k][j];//求出每次迭代最小 //值，最后一次即為兩個(gè)頂點(diǎn)之間的最短路徑 printf(“圖的鄰接矩陣為:n”);for(i=0;i for(j=0;j { printf(“%d ”,arcs[i][j]); } printf(“nn”); }//打印鄰接矩陣 printf(“n”); printf(“表示各點(diǎn)間最短路徑的矩陣為:n”); for(i=0;i { for(j=0;j { printf(“%d ”,D[vex-1][i][j]); } printf(“nn”); } } 實(shí)驗(yàn)六：排序 實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí) 一．實(shí)驗(yàn)?zāi)康模?/p> 1．掌握二叉查找樹的性質(zhì)及其相關(guān)的應(yīng)用； 2．掌握插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的算法實(shí)現(xiàn)。 二．實(shí)驗(yàn)內(nèi)容與基本要求： 1．編寫二叉查找樹的生成及應(yīng)用程序； 2．編寫插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的程序。 三．實(shí)驗(yàn)重點(diǎn)： 掌握各種排序算法的思想 四．實(shí)驗(yàn)器材： 一個(gè)裝有C語(yǔ)言編譯環(huán)境的計(jì)算機(jī)。 五．實(shí)驗(yàn)步驟 插入排序： #include printf(“Please input %d numbers:n”,N);for(i=0;i for(j=i-2;t printf(“%d ”,a[i]);printf(“n”);} 快速排序： #include while(a[i]<=A && i quickSort(a,0,i-1);if(i+1<9) quickSort(&a[i+1],i+1,9);} void main(){ int i,j,a[N]; printf(“Please input %d numbers:n”,N);for(i=0;i printf(“%d ”,a[i]);printf(“n”);} 冒泡排序： #include int a[10];int i,j,t; printf(“input 10 numbers :n”);for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(j=0;j<10;j++)for(i=0;i<10-j;i++)if(a[i]>a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<10;i++)printf(“%d ”,a[i]);printf(“n”);} 選擇排序： #include int i,j,k,t,a[N]; printf(“Please input %d numbers:n”,N); for(i=0;i scanf(“%d”,&a[i]); for(i=0;i for(j=i;j if(a[j] { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } k=a[i]; a[i]=a[j]; a[j]=k;} printf(“the sorted numbers:n”); for(i=0;i printf(“%d ”,a[i]); printf(“n”);} 30 授課教案 （2016—2017學(xué)第一學(xué)期） 課程名稱： 課程編碼： 總學(xué)時(shí)： 課程類別： 任課教師： 開課單位： 職稱： 授課專業(yè)： 授課班級(jí)： 數(shù)據(jù)結(jié)構(gòu) B13040009A 總學(xué)分： 專業(yè)課 李素若 計(jì)算機(jī)工程學(xué)院 教授 計(jì)算機(jī)科學(xué)與技術(shù) 2015級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)1、2班 授課進(jìn)度第3周，第6次課（2學(xué)時(shí)）授課題目 (教學(xué)章、節(jié)實(shí)驗(yàn)一線性表的順序存儲(chǔ)結(jié)構(gòu) 或主題) 授課日期 016年9月14日（9 2 月13日） .掌握線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素其物理位置上也相鄰。1 2.掌握線性表順序存儲(chǔ)結(jié)構(gòu)的插入、刪除操作特點(diǎn)移動(dòng)操作。 教學(xué) 目標(biāo) 1.線性表的順序存儲(chǔ)特點(diǎn) 教學(xué) 2.線性表的順序存儲(chǔ)的基本算法 重點(diǎn) 1.線性表的順序存儲(chǔ)的基本算法 教學(xué) 難點(diǎn) 請(qǐng)選擇你授課時(shí)所采用的教學(xué)方法（在括號(hào)中畫“√”）： 講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學(xué) 談話法﹝﹞，實(shí)驗(yàn)法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學(xué)輔導(dǎo)法﹝﹞，練習(xí) 方法 法（習(xí)題或操作課）﹝√﹞，讀書指導(dǎo)法﹝﹞，聽說(shuō)法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實(shí)習(xí)作業(yè)法﹝﹞，其他﹝﹞ 教學(xué) 實(shí)物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標(biāo)本 手段 ﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè) [ 1]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu).北京:中國(guó)水利水電出版社，2014.[ 2]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu)習(xí)題集及上機(jī)指導(dǎo).北京:中國(guó)水利水 請(qǐng)選擇你授課時(shí)所采用的教學(xué)手段（在括號(hào)中畫“√”）： 參考 電出版社，2014.文獻(xiàn) 教學(xué)過(guò)程及內(nèi)容 一、實(shí)驗(yàn)內(nèi)容 ．輸入一組整型元素序列，建立順序表。1 2 ．遍歷該順序表。3 ．在該順序表中進(jìn)行順序查找某一元素,查找成功返回1,否則返回0。．實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。4 ．判斷該順序表中元素是否對(duì)稱,對(duì)稱返回1,否則返回0。5 ．輸入整型元素序列利用有序表插入算法建立一個(gè)有序表。6 ．利用實(shí)驗(yàn)6建立兩個(gè)遞增有序表并把它們合并成一個(gè)遞增有序表。7 二、實(shí)驗(yàn)指導(dǎo) 1．參考程序?yàn)椋?/p> voidCreateSqList(SqList*L){ intn,i? do{ printf(“請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù):”)? scanf(“%d”,&n)? if(n<=0)printf(“輸入錯(cuò)誤n”)? } while(n<=0)? for(i=0?i } 2 ．參考程序?yàn)椋?/p> voidPrintList(SqListL){ inti? for(i=0?i intFindelems(SqListL,ElemTypee){ inti? for(i=0?i return0? } 4．分析：從順序表表頭開始掃描，當(dāng)數(shù)據(jù)元素為偶數(shù)時(shí)就從該數(shù)開始往后查找，一旦 — 1— 教學(xué)過(guò)程及內(nèi)容 找到奇數(shù)，則將該偶數(shù)與此奇數(shù)交換。順序表中所有數(shù)據(jù)全部掃描結(jié)束后，所有奇數(shù)就排列 在表的前端。參考程序?yàn)椋?/p> voidChangeVal(SqList*L){ inti,j,temp? for(i=0?i if(L->elem[j]%2!=0){ temp=L->elem[i]? L->elem[i]=L->elem[j]? L->elem[j]=temp? break? } } if(j==L->length)break? } } } 5．參考程序?yàn)椋?/p> intYesNo_Symmetry(SqListL){ inti,j? j=L.length-1? for(i=0?i return0? } return1? } 6 ．參考程序?yàn)椋?/p> voidInsert_OrderList(SqList*L,intx){ inti,j? for(i=0?i — 2— 教學(xué)過(guò)程及內(nèi)容 L->elem[j+1]=L->elem[j]? L->elem[i]=x? L->length++? } voidCreate_OrderList(SqList*L){ intn,i,input? do{ printf(“請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù):”)? scanf(“%d”,&n)? if(n<=0)printf(“輸入錯(cuò)誤n”)? while(n<=0)? } for(i=0?i Insert_OrderList(L,input)? } } 7 ．參考程序?yàn)椋?/p> SqList*Merge_OrderList(SqListA,SqListB)//將有序順序表A和B合并到有序順序表C中返回 { inti=0,j=0,k=0? SqList*C=(SqList*)malloc(sizeof(SqList))? C->length=0? while(j C->elem[i++]=A.elem[j++]? else C->elem[i++]=B.elem[k++]? } if(j==A.length) while(k } — 3— 授課進(jìn)度第4周，第8次課（2學(xué)時(shí)）授課題目 (教學(xué)章、節(jié)實(shí)驗(yàn)二單向鏈表 或主題) 授課日期 016年9月21日（9 2 月20日） ．掌握線性鏈表的操作特點(diǎn)，即指針是邏輯關(guān)系的映像。1 ．掌握動(dòng)態(tài)產(chǎn)生單鏈表的方法。2 3 ．熟練掌握單鏈表的插入、刪除操作特點(diǎn)，即指針賦值的先后次序。 教學(xué) 目標(biāo) 1．掌握動(dòng)態(tài)產(chǎn)生單鏈表的方法。 教學(xué) 2．熟練掌握單鏈表的插入、刪除操作特點(diǎn)，即指針賦值的先后次序。重點(diǎn) 1．熟練掌握單鏈表的插入、刪除操作特點(diǎn)，即指針賦值的先后次序。 教學(xué) 難點(diǎn) 請(qǐng)選擇你授課時(shí)所采用的教學(xué)方法（在括號(hào)中畫“√”）： 講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學(xué) 談話法﹝﹞，實(shí)驗(yàn)法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學(xué)輔導(dǎo)法﹝﹞，練習(xí) 方法 法（習(xí)題或操作課）﹝√﹞，讀書指導(dǎo)法﹝﹞，聽說(shuō)法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實(shí)習(xí)作業(yè)法﹝﹞，其他﹝﹞ 教學(xué) 實(shí)物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標(biāo)本 手段 ﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè) [ 1]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu).北京:中國(guó)水利水電出版社，2014.[ 2]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu)習(xí)題集及上機(jī)指導(dǎo).北京:中國(guó)水利水 請(qǐng)選擇你授課時(shí)所采用的教學(xué)手段（在括號(hào)中畫“√”）： 參考 電出版社，2014.文獻(xiàn) 教學(xué)過(guò)程及內(nèi)容 一、實(shí)驗(yàn)內(nèi)容 ．隨機(jī)產(chǎn)生或鍵盤輸入一組元素，建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表（無(wú)序）。1 ．遍歷單向鏈表。2 3 ．把單向鏈表中元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。．在單向鏈表中刪除所有的偶數(shù)元素結(jié)點(diǎn)。4 5 ．編寫在非遞減有序鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建 立一個(gè)非遞減有序單向鏈表。 ．利用實(shí)驗(yàn)5建立兩個(gè)遞增有序單向鏈表，然后合并成一個(gè)遞增鏈表。6 7 ．利用實(shí)驗(yàn)1建立的鏈表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè) 全部為偶數(shù)（盡量利用已知的存儲(chǔ)空間）。 二、實(shí)驗(yàn)指導(dǎo) 1．參考程序?yàn)椋?/p> LinkListCreateListH(void)//頭插法產(chǎn)生帶頭結(jié)點(diǎn)單鏈表 { intch? LinkListhead=(LinkList)malloc(sizeof(LNode))? LinkLists? head->next=NULL? while(scanf(“%d”,&ch)==1)//輸入數(shù)據(jù)類型錯(cuò)誤時(shí)結(jié)束單鏈表的生成 { s=(LinkList)malloc(sizeof(LNode))? s->data=ch? s->next=head->next? head->next=s? } returnhead? } LinkListCreateListRand(void)//利用隨機(jī)函數(shù)產(chǎn)生帶頭結(jié)點(diǎn)單鏈表（頭插法）{ intch,i? LinkListhead=(LinkList)malloc(sizeof(LNode))? LinkLists? head->next=NULL? srand((unsigned)time(NULL))? printf(“PleaseinputCreateNnmbers:”)? scanf(“%d”,&ch)? for(i=0?i s->data=rand()%50?//隨機(jī)產(chǎn)生0~49之間的數(shù) — 1— 教學(xué)過(guò)程及內(nèi)容 s->next=head->next? head->next=s? } returnhead? } 2 ．參考程序?yàn)椋?/p> voidPrintLinkList(LNodeL){ LinkListp? p=L.next? while(p){ printf(“%d”,p->data)? p=p->next? } printf(“n”)? } 3．參考程序?yàn)椋?/p> voidInverse_set(LinkListhead){ LNode*r,*m=NULL,*p? p=head->next? while(p!=NULL){ r=m?m=p? p=p->next? m->next=r? } head->next=m? } 4．參考程序?yàn)椋?/p> voidDelEvenLinkList(LinkListhead){ LinkListq,p? p=head->next? q=head? while(p){ if(p->data%2==0){ q->next=p->next? free(p)? — 2— 教學(xué)過(guò)程及內(nèi)容 p=q->next? } else { q=p? p=p->next? } } } 5 ．參考程序?yàn)椋?/p> voidInsertIncr(LinkListhead,ElemTypex)//將結(jié)點(diǎn)插入遞增的單鏈表 { LinkListq,p,s? s=(LinkList)malloc(sizeof(LNode))? s->data=x? q=head? p=head->next? while(p&&p->data p=p->next? } s->next=q->next? q->next=s? } LinkListCreateListIncr(void)//通過(guò)調(diào)用插入有序鏈表函數(shù)生成遞增單鏈表 { intch? LinkListhead=(LinkList)malloc(sizeof(LNode))? LinkLists? head->next=NULL? while(scanf(“%d”,&ch)==1)//輸入數(shù)據(jù)類型錯(cuò)誤時(shí)結(jié)束單鏈表的生成 InsertIncr(head,ch)? returnhead? } 6 ．參考程序?yàn)椋?/p> LinkListLinkListCat(LinkListhead1,LinkListhead2){ LinkListh1,h2,h? LinkListhead=(LinkList)malloc(sizeof(LNode))? head->next=NULL? — 3— 教學(xué)過(guò)程及內(nèi)容 h1=head1->next? h2=head2->next? h=head? while(h1&&h2){ if(h1->data h1=h1->next? } else { h->next=h2? h=h->next? h2=h2->next? } } if(h1)h->next=h1? if(h2)h->next=h2? returnhead? } 7 ．參考程序?yàn)椋?# include voidPrintLinkList(LNodeL){ LinkListp? p=L.next? while(p){ printf(“%d”,p->data)? p=p->next? — 4— 教學(xué)過(guò)程及內(nèi)容 } printf(“n”)? } voidDecoLinkList(LNodehead,LinkListhead1,LinkListhead2)//將單鏈表head拆分奇數(shù)鏈head1和偶數(shù)鏈head2 { LinkListh,h1,h2? h=head.next? h1=head1? h2=head2? while(h){ if(h->data%2==0){ h2->next=h? h=h->next? h2=h2->next? } else { h1->next=h? h=h->next? h1=h1->next? } } h1->next=NULL? h2->next=NULL? } main(){ LinkListhead? LinkListhead1=(LinkList)malloc(sizeof(LNode))? LinkListhead2=(LinkList)malloc(sizeof(LNode))? head=CreateListIncr()? PrintLinkList(*head)? DecoLinkList(*head,head1,head2)? PrintLinkList(*head1)? PrintLinkList(*head2)? } — 5— 授課進(jìn)度第5周，第10次課（2學(xué)時(shí)）授課題目 (教學(xué)章、節(jié)實(shí)驗(yàn)三棧的存儲(chǔ)及基本運(yùn)算 或主題) 授課日期 016年9月28日（9 2 月27日） .掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。1 2.了解和掌握遞歸程序設(shè)計(jì)的基本原理和方法。 教學(xué) 目標(biāo) .掌握棧的兩種存儲(chǔ)結(jié)構(gòu) 1.棧的基本運(yùn)算 教學(xué) 2.了解棧在遞歸函數(shù)中的作用 重點(diǎn) 3.掌握棧的兩種存儲(chǔ)結(jié)構(gòu) 1 教學(xué) 2.棧的基本運(yùn)算 難點(diǎn) 請(qǐng)選擇你授課時(shí)所采用的教學(xué)方法（在括號(hào)中畫“√”）： 講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學(xué) 談話法﹝﹞，實(shí)驗(yàn)法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學(xué)輔導(dǎo)法﹝﹞，練習(xí) 方法 法（習(xí)題或操作課）﹝√﹞，讀書指導(dǎo)法﹝﹞，聽說(shuō)法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實(shí)習(xí)作業(yè)法﹝﹞，其他﹝﹞ 教學(xué) 實(shí)物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標(biāo)本 手段 ﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè) [ 1]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu).北京:中國(guó)水利水電出版社，2014.[ 2]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu)習(xí)題集及上機(jī)指導(dǎo).北京:中國(guó)水利水 請(qǐng)選擇你授課時(shí)所采用的教學(xué)手段（在括號(hào)中畫“√”）： 參考 電出版社，2014.文獻(xiàn) 教學(xué)過(guò)程及內(nèi)容 一、實(shí)驗(yàn)內(nèi)容 ．采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。1 2 ．采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。3 ．寫一個(gè)程序，將輸入的十進(jìn)制數(shù)據(jù)M轉(zhuǎn)換為八進(jìn)制數(shù)據(jù)M8，將其調(diào)試通過(guò)。在此 基礎(chǔ)上修改程序，實(shí)現(xiàn)十進(jìn)制數(shù)據(jù)M向N進(jìn)制（2或8或16）的轉(zhuǎn)換。（1）采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧。（2）采用鏈表結(jié)構(gòu)實(shí)現(xiàn)棧。 二、實(shí)驗(yàn)指導(dǎo) ．參考程序?yàn)椋?1 # include //用來(lái)存放棧中元素的一維數(shù)組 //用來(lái)存放棧頂元素的下標(biāo) } SqStack? intInitStack(SqStack**s)//初始化順序棧 {(*s)=(SqStack*)malloc(sizeof(SqStack))? if((*s)==NULL)returnERROR?(*s)->top=-1? returnOK? } intEmptyStack(SqStacks)//判斷?？?{ if(s.top==-1) { printf(“stackisempty!n”)? returnOK? } returnERROR? } intGetTop(SqStacks,int*e)//取棧頂元算 { if(EmptyStack(s))returnERROR? *e=s.elem[s.top]? — 1— 教學(xué)過(guò)程及內(nèi)容 returnOK? } intPush(SqStack*s,inte)//入棧 { if(s->top==Stack_Size-1) { printf(“stackisfull!n”)? returnERROR? } s->top++? s->elem[s->top]=e? returnOK? } voidPrintStack(SqStacks)//打印棧中數(shù)據(jù) { inti? for(i=0?i<=s.top?i++)printf(“%d”,s.elem[i])? printf(“n”)? } intPop_Stack(SqStack*s,int*e)//出棧 { if(EmptyStack(*s)) returnERROR? *e=s->elem[s->top]? s->top--? returnOK? } voidmain(){ intcord,e,x,y? SqStack*s? do { printf(“nMainMenun”)? printf(“1----CreatStackn”)? printf(“2----GetTopElementn”)? printf(“3----Pushn”)? printf(“4----Popn”)? printf(“5----Printn”)? printf(“6----quitn”)? scanf(“%d”,&cord)? — 2— 教學(xué)過(guò)程及內(nèi)容 switch(cord){ case1: InitStack(&s)? break? case2: if(GetTop(*s,&y)) printf(“StackTop=[%d]n”,y)? break? case3: printf(“Pleaseinputpushelement:”)? scanf(“%d”,&e)? Push(s,e)? break? case4: if(Pop_Stack(s,&x)) printf(“Popstack=[%d]n”,x)? break? case5: PrintStack(*s)? break? case6: return? } } while(cord<=6)? } 2 ．參考程序?yàn)椋?include structstacknode*next? } StackNode? typedefstruct { StackNode*top?/*棧頂指針*/ LinkStack? } — 3— 教學(xué)過(guò)程及內(nèi)容 voidInitStack(LinkStack*s)//初始化棧 { s->top=NULL? } intEmptyStack(LinkStacks)//判斷棧空 { if(s.top==NULL)returnOK? elsereturnERROR? } intGetTop(LinkStacks,int*e)//取棧頂元素 { if(EmptyStack(s))returnERROR? *e=s.top->data? } voidPush(LinkStack*s,inte)//入棧 { StackNode*p=(StackNode*)malloc(sizeof(StackNode))? p->data=e? p->next=s->top? s->top=p? } intPop_Stack(LinkStack*s,int*e)//出棧 { StackNode*p? if(EmptyStack(*s))returnERROR? p=s->top? *e=p->data? s->top=p->next? free(p)? returnOK? } voidPrintStack(LinkStacks)//打印棧中元素 { StackNode*p=s.top? while(p){ printf(“%d”,p->data)? p=p->next? } } voidmain() — 4— 教學(xué)過(guò)程及內(nèi)容 { intcord,e,x,y? LinkStacks? do { printf(“nMainMenun”)? printf(“1----CreatStackn”)? printf(“2----GetTopElementn”)? printf(“3----Pushn”)? printf(“4----Popn”)? printf(“5----Printn”)? printf(“6----quitn”)? scanf(“%d”,&cord)? switch(cord){ case1: InitStack(&s)? break? case2: if(GetTop(s,&y)) printf(“StackTop=[%d]n”,y)? break? case3: printf(“Pleaseinputpushelement:”)? scanf(“%d”,&e)? Push(&s,e)? case4: break? if(Pop_Stack(&s,&x)) printf(“Popstack=[%d]n”,x)? break? case5: PrintStack(s)? break? case6: return? } } while(cord<=6)? } 3 ．參考程序?yàn)椋?1）（— 5— 教學(xué)過(guò)程及內(nèi)容 voidConversion(SqStack*S){ intN,n1,t? printf(“輸入一個(gè)十進(jìn)制數(shù)字:n”)? scanf(“%d”,&N)?//輸入一個(gè)十進(jìn)制數(shù)字 printf(“輸入要轉(zhuǎn)換的n進(jìn)制數(shù)字(2、8、16):n”)? scanf(“%d”,&n1)?//輸入要轉(zhuǎn)換的進(jìn)制 while(N){ Push(S,N%n1)? N=N/n1? } printf(“該數(shù)轉(zhuǎn)化為%d進(jìn)制數(shù)為:t”,n1)? if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t)? if(t==10){printf(“A”)?continue?} if(t==11){printf(“B”)?continue?} if(t==12){printf(“C”)?continue?} if(t==13){printf(“D”)?continue?} if(t==14){printf(“E”)?continue?} if(t==15){printf(“F”)?continue?} printf(“%d”,t)? } } else PrintStack(*S)? } voidmain(){ SqStack*S? InitStack(&S)? Conversion(S)? }（2） voidConversion(LinkStack*S){ intN,n1,t? printf(“輸入一個(gè)十進(jìn)制數(shù)字:n”)? scanf(“%d”,&N)?//輸入一個(gè)十進(jìn)制數(shù)字 — 6— 教學(xué)過(guò)程及內(nèi)容 printf(“輸入要轉(zhuǎn)換的n進(jìn)制數(shù)字(2、8、16):n”)? scanf(“%d”,&n1)?//輸入要轉(zhuǎn)換的進(jìn)制 while(N){ Push(S,N%n1)? N=N/n1? } printf(“該數(shù)轉(zhuǎn)化為%d進(jìn)制數(shù)為:t”,n1)? if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t)? if(t==10){printf(“A”)?continue?} if(t==11){printf(“B”)?continue?} if(t==12){printf(“C”)?continue?} if(t==13){printf(“D”)?continue?} if(t==14){printf(“E”)?continue?} if(t==15){printf(“F”)?continue?} printf(“%d”,t)? } } else PrintStack(*S)? } voidmain(){ LinkStackS? InitStack(&S)? Conversion(&S)? } — 7— 授課進(jìn)度第8周，第14次課（2學(xué)時(shí)）授課題目 (教學(xué)章、節(jié)實(shí)驗(yàn)四隊(duì)列 或主題) 授課日期 016年10月19日（10 2 月18日） .掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的邏輯特性及其主要存儲(chǔ)結(jié)構(gòu)。1 2.在簡(jiǎn)單情況下會(huì)使用順序結(jié)構(gòu)的實(shí)現(xiàn)隊(duì)列，熟練掌握循環(huán)隊(duì)列的使用。.在復(fù)雜情況下會(huì)使用鏈表結(jié)構(gòu)的隊(duì)列，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。3 教學(xué) 目標(biāo) 1.熟練掌握循環(huán)隊(duì)列的使用。 教學(xué) 2.在復(fù)雜情況下會(huì)使用鏈表結(jié)構(gòu)的隊(duì)列。重點(diǎn) 1.鏈隊(duì)列的使用。 教學(xué) 難點(diǎn) 請(qǐng)選擇你授課時(shí)所采用的教學(xué)方法（在括號(hào)中畫“√”）： 講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學(xué) 談話法﹝﹞，實(shí)驗(yàn)法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學(xué)輔導(dǎo)法﹝﹞，練習(xí) 方法 法（習(xí)題或操作課）﹝√﹞，讀書指導(dǎo)法﹝﹞，聽說(shuō)法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實(shí)習(xí)作業(yè)法﹝﹞，其他﹝﹞ 教學(xué) 實(shí)物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標(biāo)本 手段 ﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè) [ 1]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu).北京:中國(guó)水利水電出版社，2014.[ 2]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu)習(xí)題集及上機(jī)指導(dǎo).北京:中國(guó)水利水 請(qǐng)選擇你授課時(shí)所采用的教學(xué)手段（在括號(hào)中畫“√”）： 參考 電出版社，2014.文獻(xiàn) 教學(xué)過(guò)程及內(nèi)容 一、實(shí)驗(yàn)內(nèi)容 ．采用順序存儲(chǔ)實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。1 2 ．采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。3 ．編寫一個(gè)程序，使用兩個(gè)鏈隊(duì)q1和q2，用來(lái)分別存儲(chǔ)由計(jì)算機(jī)隨機(jī)產(chǎn)生的20個(gè) 100以內(nèi)的奇數(shù)和偶數(shù)，然后每行輸出q1和q2的一個(gè)值，即奇數(shù)和偶數(shù)配對(duì)輸出，直到任 一隊(duì)列為空為止。 二、實(shí)驗(yàn)說(shuō)明 ．循環(huán)隊(duì)列類型采用如下結(jié)構(gòu)： 1 defineMAXSIZE100//最大隊(duì)列長(zhǎng)度 # typedefintElemType? typedefstruct{ ElemTypedata[MAXSIZE]? intfront,rear?//隊(duì)頭、隊(duì)尾指針 SqQueue? } ．鏈隊(duì)類型采用如下結(jié)構(gòu)： 2 typedefstructQNode { ElemTypedata? structQNode*next? QNode,*QueuePtr? } typedefstruct { QueuePtrfront? QueuePtrrear? LinkQueue? } 三、實(shí)驗(yàn)指導(dǎo) 1．參考程序?yàn)椋?/p> intInitQueue(SqQueue**Q)//初始化循環(huán)隊(duì)列 { * Q=(SqQueue*)malloc(sizeof(SqQueue))? if(!(*Q)) return0? *Q)->front=(*Q)->rear=0?(return1? } intQueueEmpty(SqQueueQ)//判斷隊(duì)空 { returnQ.front==Q.rear? } — 1— 教學(xué)過(guò)程及內(nèi)容 intQueueFull(SqQueueQ)//判斷隊(duì)滿 { return(Q.rear+1)%MAXSIZE==Q.front? } intEnQueue(SqQueue*Q,ElemTypee)//入隊(duì)操作 { if(QueueFull(*Q)) /隊(duì)列滿 return0? /Q->data[Q->rear]=e? Q->rear=(Q->rear+1)%MAXSIZE? return1? } intDeQueue(SqQueue*Q,ElemType*e)//出隊(duì)操作 { if(QueueEmpty(*Q))return0? else { *e=Q->data[Q->front]? Q->front=(Q->front+1)%MAXSIZE? return1? } } 2 ．參考程序?yàn)椋?/p> intInitQueue(LinkQueue*Q)//將Q初始化為一個(gè)空的鏈隊(duì)列 { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode))? if(Q->front==NULL) return0? Q->front->next=NULL? return1? } intQueueEmpty(LinkQueueQ)//判斷隊(duì)空 { returnQ.front==Q.rear? } intEnQueue(LinkQueue*Q,ElemTypee)//入隊(duì)操作 { QueuePtrp? p=(QueuePtr)malloc(sizeof(QNode))? if(!p) return0? — 2— 教學(xué)過(guò)程及內(nèi)容 p->data=e? p->next=NULL? Q->rear->next=p? Q->rear=p? return1? } intDeQueue(LinkQueue*Q,ElemType*e)//出隊(duì)操作 { QueuePtrp? if(QueueEmpty(*Q))return0?//若隊(duì)列Q為空隊(duì)列 p=Q->front->next? *e=p->data? Q->front->next=p->next? if(Q->rear==p) Q->rear=Q->front?//若Q只有一個(gè)結(jié)點(diǎn) free(p)? return1? } 3 ．參考程序?yàn)椋?intmain(){ LinkQueueq1,q2? inti=0,j=0,num? InitQueue(&q1)? InitQueue(&q2)? srand((unsigned)time(NULL))? while(i<20||j<20){ num=rand()%100? if(num%2==0&&i<20){ EnQueue(&q1,num)? i++? } if(num%2!=0&&j<20){ EnQueue(&q2,num)? j++? } } while(!QueueEmpty(q1)&&!QueueEmpty(q2)) — 3— 教學(xué)過(guò)程及內(nèi)容 { DeQueue(&q1,&i)?DeQueue(&q2,&j)? printf(“%3d%3dn”,i,j)? } free(q1.front)? free(q2.front)? return0? } — 4— 授課進(jìn)度 授課題目 第9周，第16次課（2學(xué)時(shí)）授課日期 016年10月26日（10 2 月25日） (教學(xué)章、節(jié)實(shí)驗(yàn)五二叉樹（Ⅰ）或主題)．掌握二叉樹的存儲(chǔ)實(shí)現(xiàn)。1 ．掌握二叉樹的遍歷思想。2 教學(xué) 目標(biāo) ．掌握二叉樹的存儲(chǔ)實(shí)現(xiàn)。1 ．掌握二叉樹的遍歷思想。教學(xué) 2 重點(diǎn) 1.掌握二叉樹的遍歷思想。 教學(xué) 難點(diǎn) 請(qǐng)選擇你授課時(shí)所采用的教學(xué)方法（在括號(hào)中畫“√”）： 講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學(xué) 談話法﹝﹞，實(shí)驗(yàn)法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學(xué)輔導(dǎo)法﹝﹞，練習(xí) 方法 法（習(xí)題或操作課）﹝√﹞，讀書指導(dǎo)法﹝﹞，聽說(shuō)法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實(shí)習(xí)作業(yè)法﹝﹞，其他﹝﹞ 教學(xué) 實(shí)物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標(biāo)本 手段 ﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè) [ 1]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu).北京:中國(guó)水利水電出版社，2014.[ 2]李素若，陳萬(wàn)華，游明坤主編.數(shù)據(jù)結(jié)構(gòu)習(xí)題集及上機(jī)指導(dǎo).北京:中國(guó)水利水 請(qǐng)選擇你授課時(shí)所采用的教學(xué)手段（在括號(hào)中畫“√”）： 參考 電出版社，2014.文獻(xiàn) 教學(xué)過(guò)程及內(nèi)容 一、實(shí)驗(yàn)內(nèi)容 1．?dāng)?shù)據(jù)域?yàn)樽址囊豢枚鏄溆脧V義表形式輸入，創(chuàng)建一個(gè)采用二叉鏈表存儲(chǔ)的二叉 樹，并按廣義表的形式輸出這棵二叉樹。 ．在實(shí)驗(yàn)1的基礎(chǔ)上完成這棵二叉樹的中序遍歷的遞歸算法。2 ．在實(shí)驗(yàn)1的基礎(chǔ)上完成這棵二叉樹的中序遍歷的非遞歸算法。3 二、實(shí)驗(yàn)指導(dǎo) ．參考代碼為： 1 # defineMaxSize100 voidCreateBTNode(BTree*b,char*str)//廣義表形式輸入二叉樹，按二叉鏈表存儲(chǔ)二叉樹 { BTNode*St[MaxSize],*p=NULL? inttop=-1,k,j=0? charch? *b=NULL? ch=str[j]? while(ch!='
第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課教案