數(shù)據(jù)結構實驗大綱

1、數(shù)據(jù)結構實驗教學大綱課程編號：課程名稱： 數(shù)據(jù)結構/ Data Structure實驗總學時數(shù)： 16學時適應專業(yè)： 計算機科學與技術、軟件工程承擔實驗室：計算機科學與技術學院實驗中心一實驗教學的目的和任務上機實習是對學生的一種全面綜合訓練，是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環(huán)節(jié)。通常，實習題中的問題比平時的練習題要復雜，也更接近實際。數(shù)據(jù)結構這門課程安排的4次上機實驗都屬于一種設計類型的實驗，每個實驗的訓練重點在于基本的數(shù)據(jù)結構，而不強調面面俱到；實驗的目的是旨在使學生進一步鞏固課堂上所學的理論知識，深化理解和靈活掌握教學內容；培養(yǎng)學生編制算法的能力和編程解決實際問題的動手

2、能力。 要求學生在上機前應認真做好各種準備工作，熟悉機器的操作系統(tǒng)和語言的集成環(huán)境，獨立完成算法編制和程序代碼的編寫；上機時應隨帶有關的高級語言教材或參考書；要學會程序調試與糾錯；每次實驗后要交實驗報告，實驗報告的內容應包括：（1）實驗題目、班級、學號、姓名、完成日期；（2）簡要的需求分析與概要設計；（3）詳細的算法描述；（4）程序清單與運行結果；（5）收獲與體會。 實驗成績占數(shù)據(jù)結構結業(yè)成績的10-20%。二實驗項目及學時分配序號實 驗 項 目 名 稱實驗學時實驗類型開出要求1針對鏈式或順序存儲的線性表實現(xiàn)指定的操作4設計必開2使用?；蜿犃薪鉀Q一個應用問題4設計必開3實現(xiàn)對二叉樹的一個指定的

3、操作或用二叉樹解決一應用問題4設計必開4實現(xiàn)對圖的一個指定的操作或用圖解決一個應用問題4設計必開說明：上述實驗項目僅列出實驗內容的范圍，具體內容可根據(jù)教學情況而指定，可以一個實驗項目下安排多個不同的實驗題（參見本大綱的第三部分所述） 。 三、每項實驗的內容和要求 要求每個實驗保證每個學生一臺微機實驗一：針對鏈式或順序存儲的線性表實現(xiàn)指定的操作題1 問題描述：有兩個指數(shù)遞減的一元多項式，寫一程序先求這兩個多項式的和，再求它們的積。基本要求：用帶表頭結點的單鏈表作為多項式的存儲表示；要建立兩個單鏈表；多項式相加就是要把一個單鏈表中的結點插入到另一個單鏈表中去，要注意插入、刪除操作中指針的正確修改。

4、題2 問題描述：編號為1，2，···，n的n個人圍坐在一圓桌旁，每人持有一個正整數(shù)的密碼。從第一個人開始報數(shù)，報到一個預先約定的正整數(shù)m時，停止報數(shù)，報m的人退席，下一個人又重新從1開始報數(shù)，依此重復，直至所有的人都退席。編一程序輸出他們退席的編號序列。例如，設m=20，n=7，7個人的密碼依次是3，1，7，2，4，8，4，則退席的人的編號依次為6，1，4，7，2，3，5?；疽螅河貌粠П眍^結點的循環(huán)單鏈表表示圍成圓圈的n個人；要求建立此循環(huán)單鏈表；某人離席相當于刪除一個結點，要正確設置程序中循環(huán)終止的條件和刪除結點時指針的修改變化。/可運行的代碼#includ

5、e<iostream>#include<malloc.h>using namespace std;/定義多項式中某一項的系數(shù)和指數(shù)/兩個一元多項式相加或相乘/定義多項式的節(jié)點struct counterfloat coefficient;int exponent;counter *next;/用來保存系數(shù)和指數(shù)struct numberfloat a; int b;/創(chuàng)建一個多項式鏈表counter* createLinkList(int n)counter *head;number *q=(number*)malloc(n*sizeof(number);cout<

6、;<"請分別輸入"<<n<<"對系數(shù)和指數(shù)"<<endl;for(int k=0;k<n;k+)cin>>qk.a; cin>>qk.b;/輸入各項的系數(shù)和指數(shù)并排序for(int i=0;i<n;i+)for(int j=i;j<n;j+)if(qi.b<qj.b)qi.b=qi.b+qj.b;qj.b=qi.b-qj.b;qi.b=qi.b-qj.b;qi.a=qi.a+qj.a;qj.a=qi.a-qj.a;qi.a=qi.a-qj.a;counter *p;

7、head=(counter*)malloc(sizeof(counter);head->next=NULL;head->coefficient=q0.a; head->exponent=q0.b;for(int l=1;l<n;l+)p=(counter*)malloc(sizeof(counter);p->coefficient=ql.a;p->exponent=ql.b;p->next=head->next;head->next=p;return head;/兩個多項式鏈表相加/counter* add(counter *head1,c

8、ounter *head2)/counter *p1=head2; counter *q1=head1;/while(p1)/ while(true)/ if( q1->exponent=p1->exponent )/ q1->coefficient=q1->coefficient+p1->coefficient;/ head2=p1->next;/ free(p1);/ p1=head2;/ break;/ else if(q1->next=NULL)/ counter *s=p1;/ head2=p1->next; p1=p1->nex

9、t;/ s->next=head1->next;/ head1->next=s;/ q1=head1;/ break; / q1=q1->next;/ /counter *r=head1;/ while(true)/ if(head2->exponent=r->exponent)/ r->coefficient+=head2->coefficient; / free(head2);/ break;/ / else if(r->next=NULL)/ head2->next=head1->next;/ head1->next

10、=head2;/ break;/ / r=r->next;/ / return head1;/一個小小的變換，兩個多項式相加counter* add(counter *head1,counter *head2)counter *p1=head2; counter *q1=head1;while(p1) while(true) if( q1->exponent=p1->exponent ) q1->coefficient=q1->coefficient+p1->coefficient; head2=p1->next; free(p1); p1=head2

11、; break; else if(q1->next=NULL) counter *s=p1; head2=p1->next; p1=p1->next; s->next=head1->next; head1->next=s; q1=head1; break; q1=q1->next; /counter *r=head1;/ while(true)/ if(head2->exponent=r->exponent)/ r->coefficient+=head2->coefficient; / free(head2);/ break;/

12、 / else if(r->next=NULL)/ head2->next=head1->next;/ head1->next=head2;/ break;/ / r=r->next;/ return head1;/兩個多項式鏈表相乘counter* multiplication(counter *head1,counter *head2,int n,int m) number *num=(number*)malloc(n*sizeof(number); counter *p=head1; counter *q; counter *s10; for(int i=0

13、;i<n;i+) numi.a=p->coefficient; numi.b=p->exponent; p=p->next; free(head1); head1=p; p=head2; for(int k=0;k<m;k+) for(int j=0;j<n;j+) if(j=0) sk=(counter*)malloc(sizeof(counter); sk->next=NULL; sk->coefficient=numj.a*head2->coefficient; sk->exponent =numj.b+head2->ex

14、ponent ;else q=(counter*)malloc(sizeof(counter); q->next=sk->next; sk->next=q; q->coefficient=(numj.a)*(head2->coefficient); q->exponent=(numj.b)+(head2->exponent); head2=head2->next; free(p); p=head2; for(int y=0;y+1<m;y+) head1=add(s0,sy+1); if(m=1) head1=s0; return head

15、1;int main()int n,m; char ch;counter *head1,*head2;cout<<"請輸入第一個多項式的項數(shù):"<<endl;cin>>n;head1=createLinkList(n);cout<<"請輸入第二個多項式的項數(shù):"<<endl;cin>>m;head2=createLinkList(m);cout<<"輸入+或*選擇進行加法或乘法運算："<<endl;cin>>ch;switch(

16、ch)case '+':cout<<"加法運算后的結果為:"<<endl; head1=add(head1,head2); while(true) if(head1->next=NULL) cout<<head1->coefficient<<"x"<<head1-> exponent<<""<<endl; break; else cout<<head1->coefficient<<&quo

17、t;x"<<head1-> exponent<<"+" head1=head1->next; break;case '*':cout<<"乘法運算后的結果為:"<<endl;head1=multiplication(head1,head2,n,m); while(true) if(head1->next=NULL) cout<<head1->coefficient<<"x"<<head1-> ex

18、ponent<<""<<endl; break; else cout<<head1->coefficient<<"x"<<head1-> exponent<<"+" head1=head1->next; break;return 0;實驗二：使用?；蜿犃薪鉀Q一個應用問題問題描述 設計一個模擬計算器功能的程序，它讀入一個表達式，如果是一個正確的表達式（即它由操作數(shù)、圓括號和+、-、*、/四種運算符組成），則求出該表達式的值；否則給出某種錯誤信息?；?/p>

19、本要求：讀入一個以字符序列形式給出的以等號（=）結尾的表達式；程序中應考慮運算符的優(yōu)先級、運算的合法性。/表達式求值#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct char *base;char *top;int stacksize;OPTR;typedef struct double *base;double *top;int stacksize;OPND;int InitStack(OPTR &S) S.base=(char*)malloc(15*sizeof

20、(char); if(!S.base) exit(-1); S.stacksize=15; S.top=S.base; return 0;int InitStack(OPND &S) S.base=(double*)malloc(15*sizeof(double); if(!S.base) exit(-1); S.stacksize=15; S.top=S.base; return 0;int Push(OPTR &S,char e)if(S.top-S.base>=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize

21、+10)*sizeof(char);if(!S.base) exit(-1);S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=e;return 0;int Push(OPND &S,double e)if(S.top-S.base>=S.stacksize)S.base=(double*)realloc(S.base,(S.stacksize+10)*sizeof(double);if(!S.base) exit(-1);S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=e;retu

22、rn 0;int Pop(OPTR &S,char &e) if(S.top=S.base) return -1; e=*-S.top; return 0;int Pop(OPND &S,double &e) if(S.top=S.base) return -1; e=*-S.top; return 0;char GetTop(OPTR &S) char e1; if(S.top=S.base) return 'f' e1=*(S.top-1); return e1; double GetTop(OPND &S) double e

23、2; if(S.top=S.base) return 0.0; e2=*(S.top-1); return e2; char Precede(char c1,char c2) if(c1='+'|c1='-') if(c2='*'|c2='/'|c2='(') return '<' else return '>' else if(c1='*'|c1='/') if(c2='(') return '<'

24、else return '>' else if(c1='(') if(c2=')') return '=' else return '<' else if(c2=')') return '=' else if(c1='=') if(c2='=') return '=' else return '<' printf("您的輸入有誤！"); return 'f'doubl

25、e Oprate(double a,char c,double b) if(c='+') return a+b; else if(c='-') return a-b; else if(c='*') return a*b; else return a/b;double InNumber(int &ch) char s10; int count=0; while(ch>=48&&ch<=57)|ch=46) scount=ch; count+; ch=getchar(); return atof(s);double

26、 EvaluateExpress(OPTR &optr,OPND &opnd,int c) while(c!='='|GetTop(optr)!='=') if(c>=48&&c<=57) Push(opnd,InNumber(c); else switch(Precede(GetTop(optr),c) case '<': Push(optr,c); c=getchar(); break; case '=': char x; Pop(optr,x); c=getchar(); b

27、reak; case '>':char theta; double a,b; Pop(optr,theta); Pop(opnd,b); Pop(opnd,a); Push(opnd,Oprate(a,theta,b); break; return GetTop(opnd);void main() OPTR optr; OPND opnd; int c=0; InitStack(optr); Push(optr,'='); InitStack(opnd); c=getchar(); printf("運算結果為:%lf",Evaluate

28、Express(optr,opnd,c);實驗三：實現(xiàn)對二叉樹的一個指定的操作或用二叉樹解決一應用問題問題描述：對任意輸入的一段英文，為每個字符編制其相應的赫夫曼編碼；并利用該編碼為任意輸入的0、1序列進行解碼 基本要求：一個完整的系統(tǒng)應具有以下功能：（1）初始化 從終端讀入一段英文字符，統(tǒng)計每個字符出現(xiàn)的頻率，建立赫夫曼樹，并將該樹存入某文件；（2）編碼 利用建好的赫夫曼樹對各字符進行編碼，用列表的形式顯示在屏幕上，并將編碼結果存入另一文件中； （3）解碼 利用保存的赫夫曼編碼，對任意輸入的0，1序列能正確解碼； /赫夫曼樹和赫夫曼編碼#include<stdio.h>#incl

29、ude<malloc.h>/赫夫曼樹的存儲表示typedef structunsigned int weight;unsigned int parent,lchild,rchild;HufNode, *HuffmanTree;/赫夫曼編碼的存儲表示typedef char* HuffmanCode;/獲得0,1序列char* getNum()printf("請輸入需要解碼的0,1序列：n");char *num; int c=getchar(); int count=1;num=(char*)malloc(1*sizeof(char); num0=c;while

30、(c!='n')c=getchar(); count+;num=(char*)realloc(num,count*sizeof(char);numcount-1=c;return num;/獲得需要編碼的字符串int* getsw(int *s,int *w,int &n)s=(int*)malloc(1*sizeof(int); w=(int*)malloc(1*sizeof(int); printf("請輸入需要編碼的字符串：n"); n=0; bool flag=true; int c=getchar(); s0=c; w0=1; n+; wh

31、ile(c!='n') c=getchar(); for(int i=0;i<n;i+) if(c=si) wi+=1; flag=false; break; else flag=true; if(flag) n+; s=(int*)realloc(s,n*sizeof(int); w=(int*)realloc(w,n*sizeof(int); sn-1=c; wn-1=1; n=n-1; int* ch; ch=(int*)malloc(2*sizeof(int*); ch0=s; ch1=w; return ch;/對于傳遞過來的字符串求其真實長度（不包括最后的0或

32、則n字符）int trueLength(char* string) int count=0; while(stringcount!=0&&stringcount!='n') count+; return count;/從赫夫曼樹剩余的節(jié)點中選出權值最小的兩個節(jié)點void Select(HuffmanTree HT,int k,int &s1,int &s2)for(int i=1;i<=k;i+)if(HTi.parent)=0) s1=i; break; for(i=1;i<=k;i+)if(HTi.parent=0)&&a

33、mp;(HTs1.weight>=HTi.weight)s1=i;for(int j=1;j<=k;j+)if(HTj.parent=0)&&j!=s1) s2=j; break; for(j=1;j<=k;j+)if(HTj.parent=0)&&(j!=s1&&HTs2.weight>=HTj.weight)s2=j;/把字符串2復制給字符串1void strcpy(char* string1,char* string2) for(int i=0;i<=trueLength(string2);i+) string

34、1i=string2i;/對輸入的字符串進行赫夫曼編碼void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int *s,int n)/w存放n個字符的權if(n<=1) return;int m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HufNode);int i; HuffmanTree p=HT;for(i=1;i<=n;+i)pi.weight=wi-1; pi.lchild=0;pi.parent=0; pi.rchild=0; /*p=*w,0,0,0

35、;for(;i<=m;+i)pi.weight=0; pi.lchild=0;pi.parent=0; pi.rchild=0; /*p=0,0,0,0;for(int j=n+1;j<=m;+j) /在HT1.i-1選擇parent為0且weight最小的兩個節(jié)點，其序號分別為s1和s2int s1,s2; Select(HT,j-1,s1,s2); HTs1.parent=j; HTs2.parent=j; HTj.lchild=s1; HTj.rchild=s2; HTj.weight=HTs1.weight+HTs2.weight;/從葉子到根逆向求每個字符的赫夫曼編碼HC

36、=(HuffmanCode)malloc(n+1)*sizeof(char *);char *code=(char*)malloc(n*sizeof(char); coden-1='0'for(i=1;i<=n;+i) int start=n-1; unsigned int c,f; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) code-start='0' else code-start='1' HCi=(char*)malloc(n-start)*sizeof(

37、char); strcpy(HCi, &codestart);printf("經過赫夫曼樹編碼后為：n");for(int k=1;k<=n;k+)printf("%c-%sn",sk-1,HCk);free(code);/判斷兩個字符串是否相等，相等則返回true否則返回falsebool isEqual(char* str1,char* str2) for(int i=0;i<trueLength(str1);i+) if(str1i!=str2i) return false; return true;/對輸入的0,1序列求對應的

38、字符串void ReverseHuffmanCode(HuffmanCode Huf,char* num,int *s,int n) int min=trueLength(Huf1); int pos=0; for(int i=1;i<n;i+) if(min>trueLength(Hufi) min=trueLength(Hufi); if(min>trueLength(num) printf("序列輸入有誤！"); return; /printf("adsljf");bool flag=true; while(trueLength(

39、num)-pos>=min) for(int i=0;i<n;i+)/printf("%d",n); if(trueLength(num)-pos>=trueLength(Hufi+1) if(isEqual(Hufi+1,&numpos) pos+=trueLength(Hufi+1); flag=false; printf("%c",si); /打印相應的字符 break; else flag=true; if(flag)pos+; printf("n");/打印剩余的未解析編碼/把編碼的到的赫夫曼編碼輸

40、入到c:編碼.txt中void fileWrite(HuffmanCode Hufcode,int *s,int n)FILE *file; file=fopen("c:編碼.txt","w");if(file=NULL) printf("文件打不開！"); return; fputs("經過赫夫曼樹編碼后為：n", file);for(int i=1;i<=n;i+)fprintf(file,"%c-%sn",si-1,Hufcodei);fclose(file);/從c:編碼.txt中

41、讀取赫夫曼編碼，并對輸入的0,1序列求對應的字符串并輸入到c:解碼.txt中void fileRAndW(char *num,int *s,int n)char* Huf;Huf=(char*)malloc(n+1)*sizeof(char*);for(int k=1;k<=n;k+)Hufk=(char*)malloc(10)*sizeof(char);FILE *file1,*file2; file1=fopen("c:編碼.txt","r");file2=fopen("c:解碼.txt","w");if

42、(file1=NULL|file2=NULL) printf("文件打不開！"); return; fseek(file1,22,0);for(k=1;k<=n;k+)fseek(file1,4,1);fscanf(file1,"%s",Hufk);fclose(file1);int min=trueLength(Huf1); int pos=0; for(int i=1;i<n;i+) if(min>trueLength(Hufi) min=trueLength(Hufi); if(min>trueLength(num) pri

43、ntf("序列輸入有誤！"); return; /printf("adsljf");bool flag=true;fputs("經過赫夫曼樹解碼后為：n", file2); while(trueLength(num)-pos>=min) for(int i=0;i<n;i+)/printf("%d",n); if(trueLength(num)-pos>=trueLength(Hufi+1) if(isEqual(Hufi+1,&numpos) pos+=trueLength(Hufi+1

44、); flag=false; fprintf(file2,"%c",si); /打印相應的字符 break; else flag=true; if(flag)pos+; void main()int *w=NULL,*s=NULL;int n=0; int* c; char *num;HuffmanTree Huf; HuffmanCode Hufcode;c=getsw(s,w,n); s=c0; w=c1;HuffmanCoding(Huf,Hufcode,w,s,n);fileWrite(Hufcode,s,n);num=getNum();fileRAndW(num,

45、s,n);ReverseHuffmanCode(Hufcode,num,s,n);printf("編碼和解碼都已經完成，可以參照屏幕的輸出結果驗證文件的內容是否正確！-TJTn");printf("編碼的路徑為：c:編碼.txt；解碼的路徑為c:解碼.txt：n");實驗四：實現(xiàn)對圖的一個指定的操作或用圖解決一個應用問題問題描述：n個村莊之間的無向圖，邊上的權值w(i,j)表示村莊i和j之間道路長度現(xiàn)要從這n個村莊中選擇一個村莊新建一所醫(yī)院，使離醫(yī)院最遠的村莊到醫(yī)院的路程最短設計一程序求解此問題 基本要求：用鄰接矩陣表示無向網，應顯示所選中的村莊到各村莊

46、的最短距離。#include<iostream>using namespace std;#define INFINITY 10000/即是鄰接矩陣中的無窮大值#define MAX_VERTEX_NUM 20typedef struct ArcCellint adj;/保存權值ArcCell, AdjMarixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar vexsMAX_VERTEX_NUM;AdjMarix arcs;int vexnum, arcnum;MGraph;int LocateVex(MGraph G, char v1

47、)for(int k=0;k<G.vexnum;k+)if(G.vexsk=v1)return k;printf("輸入不合法！");return 0;void CreateMGraph(MGraph &G)/創(chuàng)建圖，每個城鎮(zhèn)的編號默認為 0 到 (頂點數(shù)-1)cout << "請輸入城鎮(zhèn)的數(shù)量(頂點數(shù))" << endl;cin >> G.vexnum;cout << "請輸入城鎮(zhèn)之間的道路數(shù)量(邊的數(shù)目)" << endl;cin >> G.ar

48、cnum;cout<<"請輸入"<<G.vexnum<<"個字符并以回車結束："<<endl;for(int z=0;z<G.vexnum;z+) cin>>G.vexsz;int i, j, k;for (i = 0; i < G.vexnum; i+)for (j = 0; j < G.vexnum; j+)G.arcsij.adj = INFINITY;/初始化鄰接矩陣(均為10000即無窮大)for (k = 0; k < G.arcnum; k+)cout << "請輸入兩個有路的城鎮(zhèn)編號" << endl;char m, n;/將城鎮(zhèn)的編號設置為0開始的整數(shù)cin >> m;cin >> n;/scanf("%c%c",&m,&n);cout << "請輸入兩個城鎮(zhèn)之間的距離(權值)" << endl;int w;cin >> w;int i=0,j=0;i=Lo