學

　生

　實

　驗

　報

　告

　冊

　課程名稱:算法與數據結構

　實驗項目名稱:

　 順序表

　 實驗學時:

　2

　 同組學生姓名:

　實驗地點: 工科樓 A205

　實驗日期:

　2013 年 10 月 16 日

　 實驗成績:

　批改教師:

　批改時間:

　實驗 1

　順序表 一、實驗目得與要求 掌握順序表得定位、插入、刪除等操作。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　編寫程序建立一個順序表,并逐個輸出順序表中所有數據元素得值。編寫主函數測試結果。

　（2）

　編寫順序表定位操作子函數,在順序表中查找就是否存在數據元素 x。如果存在,返回順序表中與x值相等得第1個數據元素得序號(序號從0開始編號);如果不存在,返回－1。編寫主函數測試結果。

　（3）

　在遞增有序得順序表中插入一個新結點 x,保持順序表得有序性。

　解題思路:首先查找插入得位置,再移位,最后進行插入操作;從第一個元素開始找到第一個大于該新結點值 x 得元素位置 i 即為插入位置;然后將從表尾開始依次將元素后移一個位置直至元素 i;最后將新結點 x 插入到 i 位置。

　（4）

　刪除順序表中所有等于 X 得數據元素。

　2、選做題 （5）

　已知兩個順序表A與B按元素值遞增有序排列,要求寫一算法實現將A與 B 歸并成一個按元素值遞減有序排列得順序表(允許表中含有值相同得元素)。

　程序清單: :

　1、#define maxsize 100 typedef struct{

　 int data[maxsize];

　 int last; }sequenlist; main {

　 int i;

　 sequenlist l={{2,5,6,8,2,8,4,3},7};

　 printf("\nThe list is:");

　 for(i=0;i<=l、last;i++)

　printf("%2d",l、data[i]); }

　2、#define maxsize 100 typedef struct{

　 int data[maxsize];

　 int last; }sequenlist; main {

　 int x,i,s=1;

　 sequenlist l={{2,5,6,7,9,8,4,3},7};

　 printf("\nThe list is:");

　 for(i=0;i<=l、last;i++)

　 printf("%2d",l、data[i]);

　 printf("\nPlease input the number :");

　 scanf("%d",&x);

　 for(i=0;i<=l、last;i++)

　 if(l、data[i]==x)

　{s=i;break;

　}

　printf("%d",s); } 3、#define maxsize 100 typedef struct{

　 int data[maxsize];

　 int last; }sequenlist; main {

　 int i,x,j;

　 sequenlist l={{1,3,5,6,7,9},5};

　 printf("\nThe list is:");

　 for(i=0;i<=l、last;i++)

　printf("%2d",l、data[i]);

　 printf("\nInput the insert number:");

　 scanf("%d",&x);

　 for(i=1;i<=l、last;i++)

　if(l、data[i1]>x) break;

　 for(j=l、last;j>=i1;j)

　l、data[j+1]=l、data[j];

　 l、data[i1]=x;

　 l、last++;

　 printf("the list after insertion is:\n");

　 for(j=0;j<=l、last;j++)

　 printf("%3d",l、data[j]); } 4、#define maxsize 100 typedef struct{

　 int data[maxsize];

　 int last; }sequenlist; main{

　 int i,j,x=0,k=0;

　 sequenlist L={{1,3,5,7,2,4,6,8,2,9},9};

　 printf("\n The list is:");

　 for(i=0;i<=L、last;i++) printf("%3d",L、data[i]);

　 printf("\nPlease input a number x:");

　 scanf("%d",&x);

　 for(i=1;i<=L、last+1;i++)

　 if(L、data[i1]==x){

　 for(j=i;j<=L、last+1;j++) L、data[j1]=L、data[j];

　 L、last;

　 i;

　 k=1;

　 }

　 if(k==1){

　 printf("The list after deletion is:\n");

　 for(j=0;j<=L、last;j++) printf("%3d",L、data[j]);

　 }

　 else

　printf("Not found!\n"); } 四、實驗結果與分析(程序運行結果及其分析) 1、輸出結果:The list is: 2 5 6 8 2 8 4 3 2、輸出結果:The list is: 2 5 6 7 9 8 4 3

　Please input the number:8

　 5 The list is: 2 5 6 7 9 8 4 3

　Please input the number:1

　1 3、輸出結果:The list is: 1 3 5 6 7 9

　Input the insert number:8

　The list after insertion is:

　1

　3

　5

　6

　7

　8

　9 4、輸出結果:The list is:

　1

　3

　5

　7

　2

　4

　6

　8

　2

　9

　Please input a number x:5

　The list after deletion is:

　1

　3

　7

　2

　4

　6

　8

　2

　9

　The list is:

　1

　3

　5

　7

　2

　4

　6

　8

　2

　9

　Please input a number x:11

　Not found！

　五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:讀取數據元素時,誤將==寫成=,導致錯誤。實驗過程中,順序表得賦值沒有弄懂,以致輸出多個 0 或者少輸出。格式運算符也要正確控制,否則系統會停止工作。

　實驗體會:通過實驗掌握了順序表得基本操作,如初始化、插入、讀取元素、刪除等等。并了解到線性表順序存儲結構得特點,即邏輯關系上相鄰得兩個元素在物理位置上也相鄰,然而從另一方面來瞧,在做插入與刪除時需要移動大量元素。本次實驗基本完成了實驗要求得目得,順序表得初始化,定義,插入,查找等,更好得了解了順序表基本操作得算法,以及更直觀得了解了數據結構在 C 語言環境下得體現。

　實驗項目名稱:

　 單鏈表

　 實驗學時:

　2

　 同組學生姓名:

　實驗地點: 工科樓 A205

　實驗日期:

　2013 年 10 月 23 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 2

　單鏈表 一、實驗目得與要求 1、實驗目得 掌握單鏈表得定位、插入、刪除等操作。

　2、實驗要求 (1)注意鏈表得空間就是動態分配得,某結點不用之后要及時進行物理刪除,以便釋放其內存空間。

　(2)鏈表不能實現直接定位,一定注意指針得保存,防止丟失。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　編寫程序建立一個單鏈表,并逐個輸出單鏈表中所有數據元素。

　（2）

　在遞增有序得單鏈表中插入一個新結點 x,保持單鏈表得有序性。

　解題思路:首先查找插入得位置然后進行插入操作;從第一個結點開始找到第一個大于該新結點值得結點即為插入位置;然后在找到得此結點之前插入新結點;注意保留插入位置之前結點得指針才能完成插入操作。

　（3）

　編寫實現帶頭結點單鏈表就地逆置得子函數,并編寫主函數測試結果。

　2、選做題 已知指針 LA 與 LB 分別指向兩個無頭結點單鏈表得首元結點。要求編一算法實現,從表 LA 中刪除自第 i 個元素起共 len 個元素后,將它們插入到表 LB中第 j 個元素之前。

　程序清單: :

　1、#include<stdlib、h> typedef int datattype; typedef struct node{

　 char data;

　 struct node *next; }linklist; main{

　 char ch;linklist *head,*s,*r,*p;

　 head=malloc(sizeof(linklist));

　 r=head;

　 scanf("%c",&ch);

　while(ch!="$"){

　 s=malloc(sizeof(linklist));

　 s>data=ch;

　 r>next=s;

　 r=s;

　 scanf("%c",&ch);

　 }

　 r>next=NULL;

　 r=head>next;

　 while(r!=NULL){

　 printf("%c",r>data);

　 r=r>next;

　 } } 2、#include "stdio、h" #include "stdlib、h" typedef struct node{

　 int data;

　 struct node *next; }linklist; main{

　 int x,y;

　 linklist *head,*s,*r,*p,*q,*m,*n;

　 clrscr;

　 head=malloc(sizeof(linklist));

　 r=head;

　 printf("input the order numbers :");

　 scanf("%d",&x);

　 while(x!=0){

　 s=malloc(sizeof(linklist));

　 s>data=x;

　 r>next=s;

　 r=s;

　 scanf("%d",&x);

　 }

　 r>next=NULL;

　 printf("Please input the insert value:");

　scanf("%d",&y);

　 p=head>next;

　 while(p!=NULL){

　 if (p>data<y) p=p>next;

　 else break;

　 }

　 q=malloc(sizeof(linklist));

　 q>data=y;

　 m=head;

　 while(m>next!=p) m=m>next;

　 q>next=p;

　 m>next=q;

　 n=head>next;

　 printf("the list are:");

　 while(n!=NULL){

　 printf("%3d",n>data);

　 n=n>next;

　 } } 3、#include "stdio、h" #include "stdlib、h" typedef struct node{

　 int data;

　 struct node *next; }linklist; main{

　 int a;

　 linklist *head,*s,*r,*p,*q,*t;

　 clrscr;

　 head=malloc(sizeof(linklist));

　 r=head;

　 printf("Input some numbers:");

　 scanf("%d",&a);

　 while(a!=0){

　 s=malloc(sizeof(linklist));

　 s>data=a;

　 r>next=s;

　r=s;

　 scanf("%d",&a);

　 }

　 r>next=NULL;

　 printf("\n The linklist before changed is:\n ");

　 p=head>next;

　 while(p){

　 printf("%d",p>data);

　 p=p>next;

　 }

　 p=head>next;

　 q=p>next;

　 while(q!=NULL){

　 t=q>next;

　 q>next=p;

　 p=q;

　 q=t;

　 }

　 head>next>next=NULL;

　 head>next=p;

　 printf("\nAfter changed:\n");

　 p=head>next;

　 while(p!=NULL){

　 printf("%d",p>data);

　 p=p>next;

　 } } 四、實驗結果與分析(程序運行結果及其分析) 1、輸入:1 2 3 a b c $ 輸出結果:1 2 3 a b c

　2、輸入:input the order numbers : 1 3 5 7 8 9 0 Please input the insert value::4

　輸出結果:the list are:

　1

　3

　4

　5

　7

　8

　9 3、輸入:Input some numbers:1 3 4 5 8 0

　輸出結果:The linklist before changed is:

　 13458

　After changed:

　 85431 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:編寫成功后運行時,沒有加入$導致程序運行不成功,不能夠退出。后注意到這個問題才繼續運行下去。

　實驗體會:在編寫程序時,設置了結束字符一定要牢牢記住,并且在輸入時觀察仔細類型就是什么,以及就是否就是輸入一串有順序得數字,編寫成功不難,但就是要規范格式,不能僅僅以完成程序為目得。而完成這一章得實驗也讓我了解了,順序表便于查找不便于插入刪除,而鏈表恰恰相反,鏈表得插入刪除只需要移動指針,而順序表要從后往前依次移動,二者各有優劣。

　實驗項目名稱:

　堆棧與隊列

　實驗學時:

　2

　 同組學生姓名:

　實驗地點:

　工科樓 A205

　實驗日期:

　2013 年 10 月 30 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 3

　堆棧與隊列 一、實驗目得與要求 (1)掌握應用棧解決問題得方法。

　(2)掌握利用棧進行表達式求與得算法。

　(3)掌握隊列得存儲結構及基本操作實現,并能在相應得應用問題中正確選用它們。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　判斷一個算術表達式中開括號與閉括號就是否配對。

　（2）

　測試“漢諾塔”問題。

　（3）

　假設稱正讀與反讀都相同得字符序列為”回文”,試寫一個算法判別讀入得一個以’’為結束符得字符序列就是否就是“回文”。

　2、選做題 在順序存儲結構上實現輸出受限得雙端循環隊列得入列與出列算法。設每個元素表示一個待處理得作業,元素值表示作業得預計時間。入隊列采取簡化得短作業優先原則,若一個新提交得作業得預計執行時間小于隊頭與隊尾作業得平均時間,則插入在隊頭,否則插入在隊尾。

　程序清單: :

　1、typedef int datatype; #define M 100 typedef struct{

　 char data[M];

　 int top; } seqstack; main{

　 char str[M];

　 int result=0,i=0;

　 seqstack s;

　 s、top=0;

　 gets(str);

　 while(str[i]!="\0"){

　 if(str[i]=="("){

　 s、top++;

　s、data[s、top]="(";

　 }

　 if(str[i]==")"){

　 if(s、top==0){

　result=1;

　break;

　 }

　 else

　s、top;

　 }

　 i++;

　 }

　 if(result==0 && s、top==0) printf("Match!\n");

　 else if(result==1) printf("Missing left!\n");

　 else if(s、top>0) printf("Missing right!\n"); } 2、#include<stdio、h> void hanoi(int n,char a,char b,char c){

　 if(n==1)

　 printf("\n Move disk %d from pile %c to pile %c",n,a,c);

　 else{

　 hanoi(n1,a,c,b);

　 printf("\n Move disk %d from pile %c to pile %c",n,a,c);

　 hanoi(n1,b,a,c);

　 } } void main{

　 int n;

　 clrscr;

　 printf("\n Please enter the number of disks to be moved:");

　 scanf("%d",&n);

　 hanoi(n,"A","B","C"); } 3、#include<stdio、h> #define M 100 typedef struct{

　 char data[M];

　 int top;

　}seqstack; main{

　 char str[M];

　 int i=0,n;

　 seqstack s;

　 s、top=0;

　 gets(str);

　 while(str[i]!="") i++;

　 if(i==1){

　 printf("Yes\n");

　 return;

　 }

　 n=i;

　 for(i=0;i<n/2;i++){

　 s、top++;

　 s、data[s、top]=str[i];

　 }

　 i=i1;

　 if(n%2==0)

　 i++;

　 else

　 i=i+2;

　 while(i<n && s、data[s、top]==str[i]){

　 i++;

　 s、top;

　 }

　 if(i==n) printf("Yes\n");

　 else printf("No\n"); } 四、實驗結果與分析(程序運行結果及其分析) 1、輸入:(a) 輸出結果:Match！

　輸入:(a 輸出結果:Missing right！

　輸入:a) 輸出結果:Missing left！

　2、輸入:3

　輸出結果:Move disk 1 from pile A to pile C Move disk 2 from pile A to pile B Move disk 1 from pile C to pile B Move disk 3 from pile A to pile C Move disk 1 from pile B to pile A Move disk 2 from pile B to pile C Move disk 1 from pile A to pile C 3、輸入:qwewq

　輸出結果:Yes

　輸入:qwerewr

　輸出結果 No 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:在本章棧與隊列中編程,有許多得if語句,編寫時一不小心就會少加一個花括號,以致編寫不成功。在本章漢諾塔問題中,使用了棧以及函數得遞歸,這其中得過程一直不就是很了解,在經過老師得講解后,理解了大致過程。

　實驗體會:遞歸函數就是編程中經常會用到得一種函數,它可以實現許多我們在平時言語與解釋上解決不了得問題,我們需要理解并且可以熟練得使用它,這對我們之后得編程會有很大得幫助。而漢諾塔利用棧就是一種很經典得遞歸得算法,這讓我們理解棧與遞歸。

　實驗項目名稱:

　 串

　 實驗學時:

　2

　 同組學生姓名:

　實驗地點:

　工科樓 A205 實驗日期:

　2013 年 11 月 6 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 4

　串 一、實驗目得與要求 掌握串得存儲及應用。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　編寫輸出字符串 s 中值等于字符 ch 得第一個字符得函數,并用主函數測試結果。

　（2）

　編寫輸出字符串 s 中值等于字符 ch 得所有字符得函數,并用主函數測試結果。

　解題思路:可以將第一題程序改進成一個子函數,在本題中循環調用。

　（3）

　設字符串采用單字符得鏈式存儲結構,編程刪除串 s 從位置 i 開始長度為 k 得子串。

　2、選做題 假設以鏈結構表示串,編寫算法實現將串 S 插入到串 T 中某個字符之后,若串T 中不存在這個字符,則將串 S 聯接在串 T 得末尾。

　提示:為提高程序得通用性,插入位置字符應設計為從鍵盤輸入。

　程序清單: :

　1、#define maxsize 100 typedef struct{

　 char ch[maxsize];

　 int curlen; }seqstring; main{

　 int i;

　 char ch;

　 seqstring s={{"asdfghg"},6};

　 for(i=0;i<s、curlen;i++)

　 printf("%c",s、ch[i]);

　 printf("\nPlease input aa character ch:");

　 scanf("%c",&ch);

　 for(i=0;i<s、curlen;i++)

　 if(s、ch[i]==ch){

　 printf("ch=s、ch[%d]=%c\n",i,s、ch[i]);

　break;

　 }

　 if(i>=s、curlen)

　 printf("Not find!\n"); } 2、#define maxsize 100 typedef struct{

　 char ch[maxsize];

　 int curlen; }seqstring; main{

　 int i,flag=0;

　 char ch;

　 seqstring s={{"abadeag"},6};

　 for(i=0;i<s、curlen;i++)

　 printf("%c",s、ch[i]);

　 printf("\nPlease input aa character ch:");

　 scanf("%c",&ch);

　 for(i=0;i<s、curlen;i++)

　 if(s、ch[i]==ch){

　 printf("ch=s、ch[%d]=%c\n",i,s、ch[i]);

　 flag++;

　 }

　 if(flag==0)

　 printf("Not find!\n"); } 3、#include<stdio、h> #include<stdlib、h> typedef struct linknode{

　 char data;

　 struct linknode *next; }linkstring; main{

　linkstring *head,*s,*r,*p,*q;

　int i,b,l,k=0;

　char ch;

　head=NULL;r=NULL;

　 printf("\n Next to creat LinkString,$ as end mark\n");

　ch=getchar;

　while(ch!="$"){

　s=malloc(sizeof(linkstring));

　s>data=ch;

　if(head==NULL) head=s;

　else

　r>next=s;

　r=s;

　ch=getchar;

　}

　if(r!=NULL) r>next=NULL;

　q=head;

　while(q){

　printf("%c",q>data);

　q=q>next;

　k++;

　}

　printf("\n Now input two int for stratpostion and length for deleted:");

　scanf("%d %d",&b,&l);

　if(b>k1||b+l>k){

　printf("Error!\n"); return;

　}

　p=head;

　for(i=0;i<b1;i++){

　p=p>next;

　}

　printf("%c %d %d %d \n",p>data,b,l,k);

　for(i=b1;i<b+l1;i++){

　q=p>next;p>next=q>next;free(q);

　}

　q=head;

　while(q){

　 printf("%c",q>data);

　 q=q>next;

　}

　printf("\n"); }

　四、實驗結果與分析(程序運行結果及其分析) 1、輸入:s

　輸出結果:ch=s、ch[1]=s 2、輸入:a

　輸出結果:ch=s、ch[0]=a

　ch=s、ch[2]=a

　ch=s、ch[5]=a 3、輸入:asdfghjkl$

　2 5

　 輸出結果:s 2 5 9

　 askl 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 實驗體會:本章第一題可以作為第二題得子函數,使用調用;也可以從開頭查找對應得字符到結尾,最后全部輸出。前兩題使用順序串,后面一題就是鏈串。串得存儲結構包含有順序存儲結構與鏈式存儲結構。在串得順序存儲結構中,表示串得長度通常有兩種方法:一種方法就是設置一個串得長度參數,其優點在于便于在算法中用長度參數控制循環過程;另一種方法就是在串值得末尾添加結束標記,此種方法得優點在于便于系統自動實現。在串得存儲過程中,串值用雙引號引起來,系統將自動在串值得末尾添加結束標記\0 字符。

　實驗項目名稱:

　 二叉樹

　 實驗學時:

　2

　 同組學生姓名:

　實驗地點: 工科樓 A205

　實驗日期:

　2013 年 11 月 13 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 5

　二叉樹 一、實驗目得與要求 (1)掌握二叉樹得生成,以及前、中、后序遍歷算法。

　(2)掌握應用二叉樹遞歸遍歷思想解決問題得方法。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷,輸出遍歷序列。

　（2）

　在第一題基礎上,求二叉樹中葉結點得個數。

　（3）

　在第一題基礎上,求二叉樹中結點總數。

　（4）

　在第一題基礎上,求二叉樹得深度。

　2、選做題 已知一棵完全二叉樹存于順序表 sa 中,sa、elem[1…sa、last]存儲結點得值。試編寫算法由此順序存儲結構建立該二叉樹得二叉鏈表。

　解題思路:根據完全二叉樹順序存儲得性質來確定二叉樹得父子關系即“還原”了二叉樹,之后再按照二叉樹二叉鏈表得構造方法進行建立。完全二叉樹順序存儲得一個重要性質為,第 i 個結點得左孩子就是編號為 2i 得結點,第 i個結點得右孩子就是編號為 2i+1 得結點。

　程序清單: :

　1(1)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{

　 char data;

　 struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{

　 char ch;

　 int front,rear;

　 bitree *root,*s;

　 root=NULL;front=1;rear=0;

　 printf("Now Creat the bitree,input baseing the order top to bottom,left

　to right:\n");

　 ch=getchar;

　 while(ch!="#"){

　 s=NULL;

　 if(ch!=""){

　 s=malloc(sizeof(bitree));

　 s>data=ch;

　 s>lchild=NULL;

　 s>rchild=NULL;

　 }

　 rear++;

　 Q[rear]=s;

　 if(rear==1) root=s;

　 else{

　 if(s && Q[front])

　if(rear%2==0) Q[front]>lchild=s;

　else

　Q[front]>rchild=s;

　if(rear%2==1) front++;

　 }

　 ch=getchar;

　 }

　 return root; } void preorder(t) bitree *t; {

　 if(t) {

　 printf("%c",t>data);

　 preorder(t>lchild);

　 preorder(t>rchild);

　 } } void inorder(t) bitree *t; {

　 if(t){

　inorder(t>lchild);

　 printf("%c",t>data);

　 inorder(t>rchild);

　 } } void postorder(t) bitree *t; {

　 if(t){

　 postorder(t>lchild);

　 postorder(t>rchild);

　 printf("%c",t>data);

　 } } main{

　 bitree *root;

　 clrscr;

　 root=Creatree;

　 printf("preorder is:");preorder(root);

　 printf("\n");

　 printf("inorder is:");inorder(root);

　 printf("\n");

　 printf("postorder is:");postorder(root);

　 printf("\n"); }? (2)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{

　 char data;

　 struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{

　 char ch;

　 int front,rear;

　 bitree *root,*s;

　root=NULL;front=1;rear=0;

　 printf("Now Creat the bitree,input baseing the order top to bottom,left to right:\n");

　 ch=getchar;

　 while(ch!="#"){

　 s=NULL;

　 if(ch!=""){

　 s=malloc(sizeof(bitree));

　 s>data=ch;

　 s>lchild=NULL;

　 s>rchild=NULL;

　 }

　 rear++;

　 Q[rear]=s;

　 if(rear==1) root=s;

　 else{

　 if(s && Q[front])

　if(rear%2==0) Q[front]>lchild=s;

　else

　Q[front]>rchild=s;

　if(rear%2==1) front++;

　 }

　 ch=getchar;

　 }

　 return root; } int left(bitree *t){

　 int num1,num2;

　 if(t==NULL) return 0;

　 else if(t>lchild==NULL && t>rchild==NULL)

　return 1;

　 else{

　 num1=left(t>lchild);

　 num2=left(t>rchild);

　 return(num1+num2);

　 } } main{

　bitree *root;

　 clrscr;

　 root=Creatree;

　 printf("lefts is %d\n",left(root)); }? (3)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{

　 char data;

　 struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{

　 char ch;

　 int front,rear;

　 bitree *root,*s;

　 root=NULL;front=1;rear=0;

　 printf("Now Creat the bitree,input baseing the order top to bottom,left to right:\n");

　 ch=getchar;

　 while(ch!="#"){

　 s=NULL;

　 if(ch!=""){

　 s=malloc(sizeof(bitree));

　 s>data=ch;

　 s>lchild=NULL;

　 s>rchild=NULL;

　 }

　 rear++;

　 Q[rear]=s;

　 if(rear==1) root=s;

　 else{

　 if(s && Q[front])

　if(rear%2==0) Q[front]>lchild=s;

　else

　Q[front]>rchild=s;

　 if(rear%2==1) front++;

　 }

　 ch=getchar;

　 }

　 return root; } int nodes(bitree *t){

　 int num1,num2;

　 if(t==NULL) return 0;

　 else if(t>lchild==NULL &&t>rchild==NULL) return 1;

　 else{

　 num1=nodes(t>lchild);

　 num2=nodes(t>rchild);

　 return (num1+num2+1);

　 } } main{

　 bitree *root;

　 clrscr;

　 root=Creatree;

　 printf("nodes is %d\n",nodes(root)); }? (4)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{

　 char data;

　 struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{

　 char ch;

　 int front,rear;

　 bitree *root,*s;

　 root=NULL;front=1;rear=0;

　 printf("Now Creat the bitree,input baseing the order top to bottom,left to right:\n");

　ch=getchar;

　 while(ch!="#"){

　 s=NULL;

　 if(ch!=""){

　 s=malloc(sizeof(bitree));

　 s>data=ch;

　 s>lchild=NULL;

　 s>rchild=NULL;

　 }

　 rear++;

　 Q[rear]=s;

　 if(rear==1) root=s;

　 else{

　 if(s && Q[front])

　if(rear%2==0) Q[front]>lchild=s;

　else

　Q[front]>rchild=s;

　if(rear%2==1) front++;

　 }

　 ch=getchar;

　 }

　 return root; } int depth(bitree *t){

　 int dep1,dep2;

　 if(t==NULL) return 0;

　 else{

　 dep1=depth(t>lchild);

　 dep2=depth(t>rchild);

　 if(dep1>dep2) return (dep1+1);

　 else return(dep2+1);

　 } } main{

　 bitree *root;

　 clrscr;

　 root=Creatree;

　printf("depth is %d\n",depth(root)); }? 四、實驗結果與分析(程序運行結果及其分析) (1)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# preorder is:abc inorder is:abc postorder is:cba (2)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# lefts is 1 (3)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# nodes is 3 (4)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# depth is 3 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:這章從一開始編寫成功后運行就一直不順利,理論上程序時正確得,但就是輸入運行處得結果卻總就是錯誤一大堆。在詢問老師后,經過運行及測試,才明白我就是對 ch=getchar;這個函數得理解錯誤,在這個函數中,空格也算作一個字符,所以當我輸入得時候,每一個字符中間空一個,輸入五個對于程序我相當于輸入了十個字符。

　實驗體會:這次得實驗讓我明白了基礎理論知識得重要性,沒有堅實得基礎知識,在這種問題上,即使編寫出來了,檢查錯誤調試就要花許多時間。并且我也學會了二叉樹得輸入賦值以及它得各種計算。

　實驗項目名稱:

　 圖

　 實驗學時:

　2

　 同組學生姓名:

　實驗地點: 工科樓 A205

　 實驗日期:

　2013 年 11 月 20 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 6

　圖 一、實驗目得與要求 (1)熟練掌握圖得基本概念、構造及其存儲結構。

　(2)熟練掌握對圖得深度優先搜索遍歷與廣度優先搜索遍歷得算法。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 (1)構造一個無向圖(用鄰接矩陣表示存儲結構)。

　(2)對上面所構造得無向圖,進行深度優先遍歷與廣度優先遍歷,輸出遍歷序列。

　2、選做題 采用鄰接表存儲結構,編寫一個判別無向圖中任意給定得兩個頂點之間就是否存在一條長度為 k 得簡單路徑得算法。簡單路徑就是指其頂點序列中不含有重復頂點得路徑。提示:兩個頂點及 k 值均作為參數給出。

　程序清單: :

　1(1) #include<stdio、h> #define n 6 #define e 8 typedef struct {

　char vexs[n];

　float arcs[n][n]; } graph1; creatgraph{

　graph1 *ga;

　 int i,j,k;

　 float w;

　 clrscr;

　 for(i=0;i<n;i++)

　 ga>vexs[i]=getchar;printf("ok\n");

　for(i=0;i<n;i++)

　 for(j=0;j<n;j++)

　 ga>arcs[i][j]=0;

　 for(k=0;k<e;k++){

　scanf("%d%d%f",&i,&j,&w);

　 ga>arcs[i][j]=w;

　 ga>arcs[j][i]=w;

　 }

　 printf("ok\n");

　 } main{

　 creatgraph; } (2)#include<stdio、h> #define n 3 #define e 2 typedef struct {

　char vexs[n];

　float arcs[n][n]; } graph1; creatgraph{

　graph1 *ga;

　 int i,j,k;

　 float w;

　 clrscr;

　 for(i=0;i<n;i++)

　 ga>vexs[i]=getchar;printf("ok\n");

　for(i=0;i<n;i++)

　 for(j=0;j<n;j++)

　 ga>arcs[i][j]=0;

　 for(k=0;k<e;k++){

　 scanf("%d%d%f",&i,&j,&w);

　 ga>arcs[i][j]=w;

　 ga>arcs[j][i]=w;

　 }

　 printf("ok\n");

　 } int visited[n]={0}; dfs(i); int i; {

　 int j;

　 printf("node:%c\n",g、vexs[i]);

　visited[i]=1;

　 for(j=0;j<n;j++)

　 if(g、arc[i][j] &&(!visited[j])) dfs(j); } typedef struct{

　 int data[10];

　 int front,read; }sequeue; sequeue Q; bfs(i){

　 int i,j;

　 Q、front=1;Q、rear=1;

　 printf("%c\n",g、vexs[k]);

　 visited[k]=1;

　 Q、data[++Q、rear]=k;

　 while(Q、front!=Q、rear){

　 Q、front++;

　 i=Q、front1;

　 for(j=0;j<n;j++)

　 if(g、arcs[i][j] && (!visited[j])){

　printf("%c\n",g、vexs[j]);

　visited[j]=1;

　Q、data[++Q、rear]=j;

　 }

　 } } main{

　 creatgraph; dfs(1);

　 bfs(0); } 四、實驗結果與分析(程序運行結果及其分析) 1(1)abcdef ok 1 2 11 1 3 12 0 1 15 0 2 16 0 3 45 0 4 15 2 3 55 3 4 55 ok

　(2)abc ok 0 1 11 0 2 12 ok

　 深度優先:abc

　 廣度優先:abc 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 遇到問題:這一章編寫得極其得不順利,首先在理論上我認為就是正確得程序在運行時卻一次次得出現 error 與 warning,讓我這章內容進行了兩次課時。耽誤了下一章得編寫。首先就是在文檔中編寫時,首字母自動大寫而沒有發現,其次就是有 clrscr 這個函數但就是頭文件卻忘記寫了,然后老師批評最嚴重得一個問題就是沒有標志語言,這章圖得編寫即使輸入進去也不會顯示出來,因此應該添加標志語言。

　實驗體會:在編寫時需要認真對待,認真檢查 C 語言語法以及在編寫時有可能忘記得內容。最重要得就是在一些程序中,需要添加標志語言,不能因為完成了就就是完成了,需要簡明易懂給人提示。

　實驗項目名稱:

　排序

　實驗學時:

　2

　 同組學生姓名:

　實驗地點:工科樓 A205

　 實驗日期:

　2013 年 11 月 27 日

　 實驗成績:

　批改教師:

　批改時間:

　實驗 7

　排序 一、實驗目得與要求 (1)熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序與基數排序得基本概念。

　(2)掌握以上各種排序得算法。區分以上不同排序得優、缺點。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 用隨機數產生 100000 個待排序數據元素得關鍵字值。測試下列各排序函數得機器實際執行時間(至少測試兩個):直接插入排序、希爾排序(增量為4,2,1)、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序與基于鏈式隊列得基數排序。

　2、選做題 假設含 n 個記錄得序列中,其所有關鍵字為值介于 v 與 w 之間得整數,且其中很多關鍵字得值就是相同得。則可按如下方法排序:另設數組number[v…w],令 number[i]統計關鍵字為整數 i 得紀錄個數,然后按 number重排序列以達到有序。試編寫算法實現上述排序方法,并討論此種方法得優缺點。

　程序清單: :

　1(1)#include<time、h> #include<stdio、h> #include<dos、h> #include<stdlib、h> #include<conio、h> #define M 20000 typedef struct{

　 int a[M];

　 int key; }sequenlist; main{

　 int i,j,k,temp;

　 sequenlist L;

　 time_t first,second;

　 clrscr;

　first=time(NULL);

　 randomize;

　 for(i=0;i<M1;i++) L、a[i]=rand%1000;

　 for(i=0;i<M2;i++){

　 for(j=M1;j>=i;j)

　 if(L、a[j+1]<L、a[j]){

　temp=L、a[j+1];

　L、a[j+1]=L、a[j];

　L、a[j]=temp;

　 }

　 }

　 second=time(NULL);

　 printf("The differece is %f second",difftime(second,first));

　 getch;

　 return 0; } (2)#include<time、h> #include<stdio、h> #include<dos、h> #include<stdlib、h> #include<conio、h> #define M 20000 typedef struct{

　 int a[M];

　 int key; }sequenlist; main{

　 int i,j,k,temp;

　 sequenlist L;

　 time_t first,second;

　 clrscr;

　 first=time(NULL);

　 randomize;

　 for(i=0;i<M1;i++) L、a[i]=rand%1000;

　 for(i=0;i<M1;i++){

　 k=i;

　 for(j=i+1;j<M;j++)

　if(L、a[j]<L、a[k]) k=j;

　 if(k!=i){

　temp=L、a[i];

　L、a[i]=L、a[k];

　L、a[k]=temp;

　 }

　 }

　 second=time(NULL);

　 printf("The differece is %f second",difftime(second,first));

　 getch;

　 return 0; } 四、實驗結果與分析(程序運行結果及其分析) 1.(1)The differece is 2、000000 second

　 (2)The differece is 1、000000 second 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 實驗體會:直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序與基于鏈式隊列得基數排序。這幾種排序各有優缺點,但就是總就是將這幾個弄混,在瞧書后得以解決。在這幾種排序中:若只從存儲空間考慮,則應首先選取堆排序方法,其次選取快速排序方法,最后選取歸并排序方法; 若只從排序結果得穩定性考慮,則應選取歸并排序方法;若只從平均情況下最快考慮,則應選取快速排序方法;若只從最壞情況下最快并且要節省內存考慮,則應選取堆排序方法。

　實驗項目名稱:

　查找

　實驗學時:

　2

　 同組學生姓名:

　實驗地點:工科樓 A205

　 實驗日期:

　2013 年 12 月 4 日

　實驗成績:

　批改教師:

　批改時間:

　實驗 8

　查找 一、實驗目得與要求 (1)掌握順序表查找、有序表查找、索引順序表查找得各種算法。

　(2)掌握哈希表設計。

　二、實驗儀器與設備 Turbo C 2、0 三、實驗內容與過程(含程序清單及流程圖) 1、必做題 （1）

　在一個遞增有序得線性表中利用二分查找法查找數據元素 X。

　2、選做題 （2）

　構造一個哈希表,哈希函數采用除留余數法,哈希沖突解決方法采用鏈地址法。設計一個測試程序進行測試。

　提示:構造哈希表只就是完成查找得第一步,大家應該掌握在哈希表上進行查找得過程,可以試著編程序實現。

　程序清單: :

　1.#define maxsize 100 typedef struct{

　 int data[maxsize];

　 int last; }sequenlist; main{

　 int i,low,mid,high,x;

　 sequenlist L={{1,3,5,7,7,11,15,23},8};

　 for(i=0;i<L、last;i++) printf("%3d",L、data[i]);

　 printf("\n Now please input a number for looking:");

　 scanf("%d",&x);

　 low=0;high=L、last;

　 while(low<=high){

　 mid=(low+high)/2;

　 if(x==L、data[mid]){

　 printf("Find the number %d\n",L、data[mid]);

　 break;

　 }

　 if(x<L、data[mid]) high=mid1;

　 else low=mid+1;

　 }

　 if(low>high) printf("Not Find\n"); }

　四、實驗結果與分析(程序運行結果及其分析) 1.

　1

　3

　5

　7

　7 11 15 23

　Now please input a number for looking:7 Find the number 7

　 1

　3

　5

　7

　7 11 15 23

　Now please input a number for looking:12 Not Find 五、實驗體會(遇到問題及解決辦法,編程后得心得體會) 實驗體會:本章規定要使用二叉查找法查找元素,并沒有太大難度,需要有三個指示器,分別就是:low,high 與 mid。這種查找只適用于順序存儲結構。

推薦訪問： 數據結構 算法 實驗