第一篇：數(shù)據(jù)結(jié)構(gòu)試驗報告
實驗一：ADT的類C描述向C程序的轉(zhuǎn)換實驗(2學(xué)時)
實驗?zāi)康模?/p>
(1)復(fù)習(xí)C語言的基本用法；
(2)學(xué)會用類C的語言對算法進行描述的方法，將類C算法轉(zhuǎn)換成C源程序的方法和過程；
(3)抽象數(shù)據(jù)類型的定義和表示、實現(xiàn)；
(4)加深對數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間關(guān)系的理解；(5)初步建立起時間復(fù)雜度和空間復(fù)雜度的概念。實驗內(nèi)容：(類C算法的程序?qū)崿F(xiàn))(1)輸入一組數(shù)據(jù)存入數(shù)組中，并將數(shù)據(jù)元素的個數(shù)動態(tài)地由輸入函數(shù)完成。求輸入數(shù)據(jù)的最大值、最小值，并通過函數(shù)參數(shù)返回所求結(jié)果； 實驗準(zhǔn)備：
1)計算機設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實驗內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實驗步驟：
1.安裝TC并設(shè)置好環(huán)境，如果已安裝好，可以跳過此步； 2.錄入程序代碼并進行調(diào)試和算法分析；
對實驗內(nèi)容(1)的操作步驟：1)用類C語言描述算法過程；2)用C語言環(huán)境實現(xiàn)該算法。
對實驗內(nèi)容(2)的操作步驟：1)完成算法的C實現(xiàn)；2)分析其時間復(fù)雜度和空間復(fù)雜度。
3.編寫實驗報告。
實驗結(jié)果：// 動態(tài)分配數(shù)組空間 #include
int size,i;int *pArray;int *p;void malloc_size(){ pArray=(int *)malloc(size*(sizeof(int)));}
int input_size(){ printf(“please input the size:n”);printf(“size= ”);scanf(“%d”,&size);return 0;}
int input_data(){ printf(“please input the value:n”);for(i=0;i printf(“pArray[%d]= ”,i); scanf(“%d”,&pArray[i]);} return *pArray;} int Compare(){ int x,y,i;x=y=p[0];for(i=0;i if(x>=p[i])x=p[i]; if(y<=p[i])y=p[i];} printf(“min= %dt max=%dn”,x,y);return 0;} int Output_data(){ p=pArray;printf(“before ofpaixu :n”);for(i=0;i printf(“%dt”,*pArray); pArray++;} printf(“n”);return *pArray;} void paixu(){ int x=0;int i,j;printf(“l(fā)ater of paixu:n”);for(i=0;i for(j=i+1;j { if(p[i]>=p[j]) { x=p[i];p[i]=p[j];p[j]=x; } } printf(“%dt”,p[i]);} printf(“n”);} void main(){ clrscr();input_size();malloc_size();input_data();Output_data();Compare();paixu();} 實驗結(jié)果： 實驗二 線性表及其基本操作實驗(2學(xué)時)實驗?zāi)康模?/p> (1)熟練掌握線性表ADT和相關(guān)算法描述、基本程序?qū)崿F(xiàn)結(jié)構(gòu)；(2)以線性表的基本操作為基礎(chǔ)實現(xiàn)相應(yīng)的程序； (3)掌握線性表的順序存儲結(jié)構(gòu)和動態(tài)存儲結(jié)構(gòu)之區(qū)分。 實驗內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其一。具體要求參見教學(xué)實驗大綱)(1)一元多項式運算的C語言程序?qū)崿F(xiàn)(加法必做，其它選做)；(2)有序表的合并；(3)集合的并、交、補運算； 實驗準(zhǔn)備： 1)計算機設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實驗內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實驗步驟： 1.錄入程序代碼并進行調(diào)試和算法分析； 2.編寫實驗報告。實驗結(jié)果：//線性鏈表 #include typedef struct node { int data;struct node *next;}*Sqlist; void Initlialize(Sqlist &L){ L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;} int Getlength(Sqlist L){ int i=0;Sqlist p=L->next;while(p!=NULL){ i++; p=p->next;} return i;} int Getelem(Sqlist L,int i){ int j=1,e;Sqlist p=L->next;while(j p=p->next; j++;} e=p->data;printf(“第 %d 個元素是：%dn”,i,e);return 1;} int Locatelem(Sqlist L,int x){ int i=0;Sqlist p=L->next;while(p!=NULL&&p->data!=x){ p=p->next; i++;} if(p==NULL) return 0;else { printf(“%d 是第 %d 個元素n”,x,i);return i;} } void CreatlistF(Sqlist &L,int a[ ],int n){ Sqlist s;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;for(i=0;i s=(Sqlist)malloc(sizeof(Sqlist)); } } void CreatlistR(Sqlist &L,int a[],int n){ Sqlist s,r;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;r=L;for(i=0;i s=(Sqlist)malloc(sizeof(Sqlist)); s->data =a[i]; s->next=NULL; r->next =s;r =s;} } int Inselem(Sqlist &L,int i,int x){ int j=1;Sqlist s,p=L->next;s=(Sqlist)malloc(sizeof(Sqlist));s->data =x;s->next =NULL;if(i<1||i>Getlength(L)) return 0;while(j p=p->next;j++;} printf(“在第 %d 個位置插入數(shù)據(jù)：%dn”,i,x);s->next =p->next; p->next =s;return 1;} int Delelem(Sqlist &L,int i){ int j=1; Sqlist p,q; p=L; if(i<1||i>Getlength(L)) return 0;s->data =a[i]; s->next =L->next;L->next =s; while(j { p=p->next; j++; } q=p->next; p->next =q->next; free(q); return 1;} void Displist(Sqlist L){ Sqlist p=L->next; while(p!=NULL) { printf(“%dt”,p->data); p=p->next; } printf(“n”);} void input(int *pArray,int n){ printf(“請輸入數(shù)組數(shù)據(jù)(共含 %d 個元):n”,n); for(int i=0;i Scanf(“%d”,&pArray[i]); } int main(int argc, char* argv[]){ Sqlist L; int Array[M],Select;initlialize(L);do{ printf(“請輸入選擇方法（1表示頭插法，2表示尾插法,0表示結(jié)束）：n”); scanf(“%d”,&Select); switch(Select) { case 1: printf(“按頭插法建立線性表:n”); input(Array,M); creatlistF(L,Array,M); break;case 2: printf(“按尾插法建立線性表:n”); input(Array,M); creatlistR(L,Array,M); break; } printf(“原線性表數(shù)據(jù)為:n”);Displist(L); Getelem(L,3); Locatelem(L,2); Inselem(L,5,5); printf(“修改后的線性表數(shù)據(jù)為:n”); Delelem(L,4); Displist(L);}while(Select!=0);return 0;} 運行結(jié)果: 實驗三 棧和隊列實驗(6學(xué)時)實驗?zāi)康模?/p> (1)熟練掌握棧和隊列的抽象數(shù)據(jù)類型及其結(jié)構(gòu)特點；(2)實現(xiàn)基本的棧和隊列的基本操作算法程序。實驗內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，任選其一)(1)設(shè)計與實現(xiàn)基本的堆棧和隊列結(jié)構(gòu)下的各種操作（如堆棧的PUSH、POP等操作）(必做)； (2)以表達式計算為例，完成一個可以進行算術(shù)表達式計算功能的算法設(shè)計與實現(xiàn)（選做）； 實驗準(zhǔn)備： 1)計算機設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3)實驗內(nèi)容的算法分析與代碼設(shè)計與分析準(zhǔn)備。實驗步驟： 1.錄入程序代碼并進行調(diào)試和算法分析； 2.編寫實驗報告。實驗結(jié)果：//隊列存儲 #include typedef struct sqqueue { char data[QueueSize];int front,rear;}SqQueue; void InitQueue(SqQueue &qu){ qu.front =qu.rear =0;} status EnQueue(SqQueue &qu,char x){ if((qu.rear +1)%QueueSize==qu.front) return 0;qu.rear =(qu.rear+1)%QueueSize;qu.data[qu.rear]=x;return 1;} status DeQueue(SqQueue &qu,char &x){ if(qu.rear==qu.front) return 0;qu.front =(qu.front +1)%QueueSize;x=qu.data[qu.front];return 1;} status GetHead(SqQueue qu,char &x){ if(qu.rear ==qu.front) return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;} status QueueEmpty(SqQueue qu){ if(qu.rear==qu.front) return 1;else return 0;} void main(){ SqQueue qu;char e;InitQueue(qu);printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”)); printf(“inser an”); EnQueue(qu,'a'); printf(“inser bn”); EnQueue(qu,'b'); printf(“inser cn”); EnQueue(qu,'c'); printf(“inser dn”); EnQueue(qu,'d'); printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”)); GetHead(qu,e); printf(“Queue of top elem is: %cn”,e); printf(“show of Queue:n”); while(!QueueEmpty(qu)){ DeQueue(qu,e); printf(“%ct”,e);} printf(“n”);} 實驗結(jié)果： （2）//用棧實現(xiàn)對表達式的求值運算 #include #define TRUE 1 #define FALSE 0 #define OK #define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 #define STACK_INIT_SIZE #define STACKINCREMENT 10 typedef int Status;typedef char ElemType; typedef ElemType OperandType; typedef char OperatorType; typedef struct { ElemType *base; ElemType *top; int stacksize;}SqStack; Status InitStack(SqStack &S){ S.base =(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;} Status GetTop(SqStack S){ ElemType e; if(S.top == S.base)return ERROR; e = *(S.top-1); return e;} Status Push(SqStack &S,ElemType e) { if(S.top1 < n){ merge(r, r1, i, i+length-1, i + 2*length1 < n-1) merge(r, r1, i, i+length-1, n-1); else for(j = i;j < n;j++)r1[j] = r[j];} void MergeSort(SortObject * pvector){ RecordNode record[MAXNUM]; int length = 1; while(length < pvector->n){ mergePass(pvector->record, record, pvector->n, length); length *= 2; mergePass(record, pvector->record, pvector->n, length); length *= 2; } } SortObject vector = {8, 49,38,65,97,76,13,27,49}; int main(){ int i;printf(“排序前序列為：”); for(i = 0;i < 8;i++) printf(“%d ”, vector.record[i]);printf(“n”); MergeSort(&vector);printf(“采用歸并排序為：”); for(i = 0;i < 8;i++) printf(“%d ”, vector.record[i]); getchar(); return 0;} 實驗結(jié)果： 實驗十 查找實驗(2學(xué)時)* 實驗?zāi)康模?/p> (1)熟練掌握各種靜態(tài)查找表方法(順序查找、折半查找、索引順序表等)；(2)熟練掌握二叉排序樹的構(gòu)造方法和查找算法； (3)了解和掌握其它查找方法。 實驗內(nèi)容：(類C算法的程序?qū)崿F(xiàn)，除順序查找算法之外，任選一個)(1)順序查找算法的實現(xiàn)(必做)；(2)折半查找算法的實現(xiàn)(選做)； 實驗結(jié)果：//查找實驗 1、順序查找： #include void SequenceSearch(int *fp,int Length){ int data; printf(“開始使用順序查詢.請輸入你想要查找的數(shù)據(jù): ”); scanf(“%d”,&data); for(int i=0;i if(fp[i]==data) { printf(“數(shù)據(jù)%d 是第 %d 個數(shù)據(jù)n”,data,i+1); return; } printf(“未能查找到數(shù)據(jù)%d.n”,i,data);} void main(){ int count; int arr[LENGTH]; printf(“請輸入你的數(shù)據(jù)的個數(shù):”); scanf(“%d”,&count); printf(“請輸入 %d 個數(shù)據(jù):”,count); for(int i=0;i scanf(“%d”,&arr[i]); SequenceSearch(arr,count);} 實驗結(jié)果： 2、折半查找： #include typedef struct { char *elem; int length; }SStable; void Create(char **t) { int i;static char a[M+1];*t=a;for(i=1;i<=M;i++){ printf(“A[%d] is:”,i); scanf(“%c”,&a[i]); if(a[i]!= 'n')getchar();} } int Searth(char *t,char k){ int i;for(i=M;i>=0 && t[i]!=k;i--); Return i;} void output(char *t){ int i;for(i=1;i<=M;i++) printf(“n A[%d] is %c”,i,t[i]);} void px(char *t) { char s;int i,j;for(i=1;i<=M;i++) for(j=i+1;j<=M;j++) { if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;} } } int Search_bin(char *t,char k){ int low=1,high=M,mid;while(low<=high){ mid=(low+high)/2; if(k==t[mid])return mid; else if(k else low=mid+1;} return 0;} void main(){ char *t,k;int s;Create(&t);output(t);printf(“nplease input you search char:”);k=getchar();s=Searth(t,k);if(s>=0)printf(“1: use search find is A[%d]n”,s);else printf(“1:can not find itn”);px(t);output(t);s=Search_bin(t,k);if(s==0)printf(“n1:can not find it n”);else printf(“n2:use Search_bin find is A[%d]n”,s);getchar();} 實驗結(jié)果： 線性表上機實習(xí) 1、實驗?zāi)康?/p> （1）熟悉將算法轉(zhuǎn)換為程序代碼的過程。 （2）了解順序表的邏輯結(jié)構(gòu)特性，熟練掌握順序表存儲結(jié)構(gòu)的C語言描述方法。 （3）熟練掌握順序表的基本運算：查找、插入、刪除等，掌握順序表的隨機存取特性。（4）了解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，熟練掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的C語言描述方法。（5）熟練掌握線性鏈表（單鏈表）的基本運算：查找、插入、刪除等，能在實際應(yīng)用中靈活選擇適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。 2、實驗要求 （1）熟悉順序表的插入、刪除和查找。（2）熟悉單鏈表的插入、刪除和查找。 3、實驗內(nèi)容: ① 順序表 （1）抽象數(shù)據(jù)類型定義 typedef struct { TypeData data[maxsize]; //容量為maxsize的靜態(tài)順手表 int n; //順序表中的實際元素個數(shù) }SeqList; //靜態(tài)順序表的定義 在本次實驗中，首先建立一個空的靜態(tài)順序表，然后鍵盤輸入數(shù)據(jù)存入表中，然后進入菜單選擇界面，通過不同的數(shù)字輸入，實現(xiàn)對順序表，刪除，插入，查找，顯示等操作。 （2）存儲結(jié)構(gòu)定義及算法思想 在順序表結(jié)構(gòu)體的定義中，typedef int TypeData 為整型，存儲結(jié)構(gòu)如下： for(n=0;n cout<<“請輸入線性表數(shù)據(jù)”< cin>>L.data[n]; //順序?qū)?shù)據(jù)存入順序表 } //其他存儲與此類似，都是直接賦值與數(shù)組的某一位 插入版塊子函數(shù)： void insert(SeqList &L) //插入數(shù)據(jù) { int a,b,c,k; cout<<“請輸入插入的數(shù)及其插入的位置”< cin>>a>>b; if(b<=0||b>(L.n+1)){cout<<“不能在該位置插入”< k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1; while(c>b){ L.data[c]=L.data[c-1];c--; //通過循環(huán)，實現(xiàn)插入位置后的數(shù)據(jù)挨個往后移動一位 } L.data[b]=k;} 順序表的插入與刪除操作類似，在插入與刪除后，都要循環(huán)調(diào)整后面數(shù)組的每一位元素，同時記錄數(shù)據(jù)元素的長度的標(biāo)示符也要跟著改變。顯示操作是通過循環(huán)實現(xiàn)表中第一個元素到最后一個元素的輸出，查找操作是直接取數(shù)組中的查找位輸出。 （3）實驗結(jié)果與分析 ② 單鏈表 （1）抽象數(shù)據(jù)類型定義 typedef struct node{ DataType data; //鏈表的數(shù)據(jù)類型 struct node *link; //鏈表的結(jié)點指針 }linknode,*linklist; //定義了結(jié)構(gòu)體linklode和結(jié)構(gòu)體指針linklist 在本次實驗中，首先程序自己建立一個空的頭結(jié)點，通過菜單的功能選擇“添加鏈表數(shù)據(jù)”可自由添加鏈表的節(jié)點數(shù)及元素值。在菜單選擇中，有“添加鏈數(shù)據(jù)”，“插入鏈表數(shù)據(jù)”，“刪除鏈表數(shù)據(jù)”，“查找鏈表數(shù)據(jù)”和“顯示鏈表數(shù)據(jù)”功能，選擇不能的功能選擇就能實現(xiàn)不同的操作。其中“添加鏈表數(shù)據(jù)”可反復(fù)批量輸入鏈表數(shù)據(jù)。 （2）存儲結(jié)構(gòu)定義及算法思想 在單鏈表中，typedef int DataType;DataType data;定義鏈表存儲數(shù)據(jù)位整型。存儲結(jié)構(gòu)如下： while(p->link!=NULL){ p=p->link; k++; //首先找到單鏈表的最后結(jié)點（如果是只有頭結(jié)點 } 的單鏈表則直接跳過），以便后面接著輸入數(shù)據(jù) for(int i=0;i { cout<<“請輸入數(shù)據(jù)”< //開辟新的結(jié)點空間并轉(zhuǎn)化為linklist指針型 cin>>q->data; q->link=p->link; //將前面一個結(jié)點的指向(及NULL)賦給新開辟的結(jié)點的指向 p->link=q; //將插入點前面一個結(jié)點指向新開辟的的結(jié)點 p=q; //將指明的最后一個一個結(jié)點向后移1位到最后一位，以便后面接著輸入 } 刪除結(jié)點子函數(shù)： void delate(linklist &l){ //刪除單鏈表數(shù)據(jù) linklist p;int m,n,i=0; cout<<“請輸入想要刪除的結(jié)點位置”< cin>>m; p=l; //將頭結(jié)點賦給轉(zhuǎn)移指針p while(p&&i //查找刪除結(jié)點的位置 p=p->link; //當(dāng)在單鏈表中間已查到刪除結(jié)點或p=NULL時跳出循環(huán) i++; } if(p==NULL){ //當(dāng)p=NULL跳出循環(huán)時，表明鏈表中沒有該結(jié)點 cout<<“該結(jié)點不存在，刪除錯誤”< } n=p->link->data;//找到刪除接結(jié)點將數(shù)據(jù)取出并顯示出來（找結(jié)點時是找的前一個結(jié)點） cout<<“被刪除的結(jié)點元素為: ”< p->link=p->link->link; //將刪除結(jié)點的前后結(jié)點鏈接起來 } 鏈表的刪除，插入操作是類似的，要考慮到加入或減少一個結(jié)點后，前后結(jié)點的鏈接關(guān)系，以及刪除或插入的是最后一個結(jié)點時，新空間的開辟與結(jié)點收尾等問題。其中刪除功能的一部分就是查找功能，顯示功能也是從鏈表的頭結(jié)點遍歷至最后一個，依次輸出。 （4）實驗結(jié)果與分析 ③ 心得體會 本次數(shù)據(jù)結(jié)構(gòu)實習(xí)我收獲頗豐，以前學(xué)過c語言與c++也有經(jīng)常上機，但以往都是偏向于程序整體的算法設(shè)計，沒有像這次的實習(xí)這樣是著重在線性表，鏈表結(jié)構(gòu)的算法設(shè)計上面。這次上機實習(xí)，讓我更加熟練了結(jié)構(gòu)體及結(jié)構(gòu)體指針的用法，線性表的設(shè)計等等，同時在這次實習(xí)中，引用，指針，地址這三個的用法曾一度讓我混淆，在查閱書籍后才得以解決，也希望老師在課堂上有時間時給我們詳細講解一下，指針，地址，引用三者的使用。 附錄： 順序表源代碼: #include void makeSeq(SeqList &L)// 據(jù) { int m,n,k;cout<<“請輸入線性表長度”< 輸入線性表數(shù)輸出線性表數(shù)據(jù) void insert(SeqList &L)//插入數(shù)據(jù) { int a,b,c,k;cout<<“請輸入插入的數(shù)及其插入的位置”< cout<<“刪除 2”< 單鏈表源代碼： #include linklist chushihua(){ linklist L;L=(linklist)malloc(sizeof(linknode));L->link=NULL;cout<<“開辟空間成功，頭結(jié)點建立”< p=l;while(p->link!=NULL){ p=p->link;k++;} for(int i=0;i data<<“ ”;p=p->link;} cout< { linklist p,q;int m,n,i=0; cout<<“請輸入您要插入的結(jié)點位置及插入的數(shù)據(jù)”< q=(linklist)malloc(sizeof(linknode));q->data=n;q->link=p->link;p->link=q;} void delate(linklist &l){ linklist p;int m,n,i=0;cout<<“請輸入想要刪除的結(jié)點位置”< L=chushihua(); while(1){ cout<<“請選擇功能”< case 1: shuru(L);break;case 2: insert(L);break;case 3: delate(L);break;case 4: find(L);break;case 5: show(L);break;default :break;} } } 一、1)功能描述 輸入數(shù)據(jù)（設(shè)為整型）建立單鏈表，并求相鄰兩節(jié)點data值之和為最大的第一節(jié)點。2)詳細設(shè)計 遵循鏈表建立的基本思想，建立一個新的鏈表，H為表頭，r為新節(jié)點，p為表尾節(jié)點指針，沒存入一個新的數(shù)據(jù)則申請一個新的節(jié)點，知道沒有數(shù)據(jù)輸入，利用循環(huán)和打擂臺法，比較和的大小，并輸出。3)測試分析 程序調(diào)試完成后，選取兩組數(shù)據(jù)進行測試，都得出了正確結(jié)果（數(shù)據(jù)以0為結(jié)束符，若有相同和，則取第一組）結(jié)果截圖 4)心得體會 通過做第一題，學(xué)習(xí)到鏈表的建立以及鏈表里指針的使用，并且復(fù)習(xí)了比較法里面的打擂臺法。 二、1)功能描述 實現(xiàn)算術(shù)表達式求值程序（棧的運用），輸入中綴表達式，可將其轉(zhuǎn)換成后綴表達式 2)詳細設(shè)計 本題目的程序是根據(jù)課本上的程序改進之后得出的，課本上有完整的程序，但是有bug，按照課本上的程序，結(jié)果會出現(xiàn)“燙燙燙燙燙”，原因是對于優(yōu)先級的比較沒有處理好，因此加了兩行代碼，將優(yōu)先級的比較處理好，即現(xiàn)在的程序。3)測試分析 程序調(diào)試完成后，選取題目所給的式子進行測試，得出了正確后綴表達式結(jié)果 結(jié)果截圖 4)心得體會 通過做第二題，對于課本上的知識表示得出“實踐出真知”的真理，即使書上的東西也不一定就是正確的，尤其是代碼，最好是個人自己真正實踐一下。 三、1)功能描述 實現(xiàn)鏈?zhǔn)疥犃羞\算程序（隊列的運用）2)詳細設(shè)計 本題目是隊列相關(guān)應(yīng)用，隊列和棧是相反的，隊列是先進的先出，因此輸入12345，先出的是1，本著隊列的這一特性，根據(jù)課本所學(xué)的隊列的算法，設(shè)計了如下程序。3)測試分析 程序調(diào)試完成后，選取12345進行測試，后綴加0，則一個字符出隊，只輸入0，則繼續(xù)出隊，輸入@，則打印剩余全部元素。結(jié)果截圖 4)心得體會 通過做第三題，對于隊列的特點有了更加深刻的認識，尤其區(qū)分隊列與棧的不同點，需要特別注意。 四、1)功能描述 ①構(gòu)造關(guān)于F的Huffman樹； ②求出并打印D總各字符的Huffman編碼。2)詳細設(shè)計 本題目是Huffman樹的應(yīng)用以及Huffman編碼的應(yīng)用，參照課本上關(guān)于Huffman樹的建立以及Huffman編碼的應(yīng)用的實現(xiàn)，將所給數(shù)據(jù)依權(quán)值最小原則建立Huffman樹，并實現(xiàn)Huffman編碼。3)測試分析 程序調(diào)試完成后，給出數(shù)據(jù)abcdefgh，相應(yīng)頻率為12345678，運行代碼得出結(jié)果如圖。同時選取另一組數(shù)據(jù)測試也得出了正確結(jié)論 結(jié)果截圖 4)心得體會 通過做第四題，對于Huffman樹有了更加深刻的體會，同時練習(xí)也使得對課本知識進行實踐，有助于更好的理解Huffman樹的算法。 五、1)功能描述 設(shè)英文句子：“everyone round you can hear you when you speak.”（1）依次讀入句中各單詞，構(gòu)造一棵二叉排序樹；（2）按LDR遍歷此二叉排序樹。 LDR： can everyone hear round speak when you（有序） 2)詳細設(shè)計 本題目是有關(guān)二叉樹的建立和中序遍歷的，二叉樹作為數(shù)據(jù)存儲一個很重要的結(jié)構(gòu)，它的建立也是很重要的。本題目代碼設(shè)計上采用課本上的對于二叉樹建立的方法，將所給單詞以二叉樹形式建立并存儲，然后中序遍歷的到字典順序。3)測試分析 程序調(diào)試完成后，給出單詞串everyone round you can hear you when you speak，運行代碼得出中序遍歷結(jié)果如圖。結(jié)果截圖 4)心得體會 通過做第五題，練習(xí)運用二叉樹模型解決了一些實際問題如現(xiàn)實中字典的編排問題，在熟悉算法的基礎(chǔ)上，同時得出結(jié)論，好的算法可以應(yīng)用與實際生活生產(chǎn)，使之更為便捷。 附錄 程序代碼 實驗一： #include“stdio.h” #include“malloc.h” typedef struct node { int data; struct node *next;}list,*List;List Creatlist() //建立鏈表函數(shù) { List H,p,r; //H為表頭，r為新節(jié)點，p為表尾節(jié)點指針 H=(List)malloc(sizeof(list)); //建立頭節(jié)點 r=H; p=(List)malloc(sizeof(list)); //申請新節(jié)點 while(scanf(“%d”,p)&&p->data!=0)//輸入數(shù)據(jù)，直到為零（結(jié)束標(biāo)志） { r->next=p;//新節(jié)點鏈入表尾 r=p; p=(List)malloc(sizeof(list)); } r->next=NULL;//將尾節(jié)點的指針域置空 return H; //返回已創(chuàng)建的頭節(jié)點 } List Adjmax(List H)//比較相鄰兩數(shù)之和 { //返回相鄰兩數(shù)之和最大的第一個數(shù)指針 List p,r,q;int sum=0;p=H->next;if(H->next ==NULL)//判斷是否為空 { printf(“Empty List!”); q=(List)malloc(sizeof(list)); q->data =0;} while(p!=NULL)//比較相鄰兩數(shù)之和 { r=p->next; if(p&&r) if(r->data+p->data>sum) { q=p; sum=r->data +p->data;}//不斷賦給sum新的最大值 else; p=p->next;} return q;} int main(){ char ch;printf(“/// 請輸入整形數(shù)據(jù)，以空格隔開，0結(jié)束。/// n”);printf(“Ready? nY/N(enter 'y' or 'Y' to continue)n”);while(scanf(“%c”,&ch)&&(ch=='Y'||ch=='y')) { List H,pmax; H=Creatlist(); pmax=Adjmax(H); printf(“相鄰兩數(shù)之和最大的第一個數(shù)為：%dnContinue? Y/N free(H); scanf(”%c“,&ch);} return 0;} ”,pmax->data);實驗二： #include struct node *next;//后繼指針 }snode,*slink;int Emptystack(slink S)//檢測?？?{ if(S==NULL)return(1);else return(0);} char Pop(slink*top)//出棧 { char e;slink p;if(Emptystack(*top))return(-1);//棧空返回 else { e=(*top)->data;//取棧頂元素 p=*top;*top=(*top)->next;//重置棧頂指針 free(p);return(e);} } void Push(slink*top,char e)//進棧 { slink p;p=(slink)malloc(sizeof(snode));//生成進棧p節(jié)點 p->data=e;//存入元素e p->next=*top;//p節(jié)點作為新的棧頂鏈入 *top=p;} void Clearstack(slink*top)//置空棧 { slink p;while(*top!=NULL){ p=(*top)->next; Pop(top);//依次彈出節(jié)點直到?？?/p> *top=p;} *top=NULL;} char Getstop(slink S)//取棧頂 { if(S!=NULL)return(S->data);return(0);} //符號優(yōu)先級比較 int Precede(char x,char y)//比較x是否“大于”y { switch(x){ case '(':x=0;break;case '+': case '-':x=1;break;case '*': case '/':x=2;break;default: x=-1;} switch(y){ case '+': case '-':y=1;break;case '*': case '/':y=2;break;case '(':y=3;break;default: y=100;} if(x>=y)return(1);else return(0);} //中后序轉(zhuǎn)換 void mid_post(char post[],char mid[])//中綴表達式mid到后綴表達式post的轉(zhuǎn)換的算法 { int i=0,j=0;char x; slink S=NULL;//置空棧 Push(&S,'#');//結(jié)束符入棧 do { x=mid[i++];//掃描當(dāng)前表達式分量x switch(x){ case '#': { while(!Emptystack(S)) post[j++]=Pop(&S); } }break;case ')': { while(Getstop(S)!='(') post[j++]=Pop(&S);//反復(fù)出棧直至遇到'（' Pop(&S);//退掉'（' }break;case '+': case '-': case '*': case '/': case '(': { while(Precede(Getstop(S),x))//棧頂運算符（Q1）與x比較 post[j++]=Pop(&S);//Q1>=x時，輸出棧頂符并退棧 Push(&S,x);//Q1 }break;default:post[j++]=x;//操作數(shù)直接輸出 } }while(x!='#');post[j]='
第二篇：數(shù)據(jù)結(jié)構(gòu)線性表試驗報告
第三篇：北京科技大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗報告(附錄含代碼)