第一篇：二叉樹的創建與訪問算法設計

內蒙古工業大學信息工程學院

實 驗 報 告

課程名稱： 數據結構（C語言版）實驗名稱： 二叉樹的創建與訪問算法設計 實驗類型： 驗證性□ 綜合性□ 設計性□ 實驗室名稱： c機房 班級：xxxxxxxxx 學號： xxxxxxxxxxxxxxx 姓名： xxx 組別： 同組人：

成績：

實驗日期： 2011年 6月

內蒙古工業大學信息工程學院

預習報告成績： 指導教師審核（簽名）： 2011年 月 日

預習報告

一.實驗目的

本實驗以二叉樹的創建與訪問算法設計作為實驗內容，掌握樹型結構的實現方法，培養解決負責問題的能力。

二.實驗內容

1、編寫生成二叉樹的函數，二叉樹的元素從鍵盤輸入；

2、編寫在二叉樹中插入元素的函數；

3、編寫在二叉樹中刪除元素的函數；

4、編寫遍歷并輸出二叉樹的函數。

方案一采用遞歸算法實現二叉樹遍歷算法。方案二采用非遞歸算法實現二叉樹遍歷算法。三.實驗要求

1、掌握樹型結構的機器內表示；

2、掌握樹型結構之上的算法設計與實現；

3、列表對比分析兩種數據結構的相應操作的時間復雜度、空間復雜度，闡明產生差異的原因。四.問題描述

從鍵盤輸入二叉樹的元素，建立二叉樹，實現二叉樹的遍歷算法。

五.基本要求

實現以下基本操作：

（1）從鍵盤輸入二叉樹的元素，建立二叉樹。（2）實現二叉樹的先序遍歷算法。

內蒙古工業大學信息工程學院

實驗報告成績： 指導教師審核（簽名）： 2011年 月 日

實驗報告

一 程序清單

#include “stdio.h” #include “string.h” #include #define NULL 0

typedef struct BiTNode{ char data;

struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;

BiTree Create(BiTree T){

char ch;

ch=getchar();if(ch=='#')T=NULL;else{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))printf(“Error!”);T->data=ch;

T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}

return T;}

int Depth(BiTree T){

int dep=0,depl,depr;if(!T)dep=0;else {

depl=Depth(T->lchild);depr=Depth(T->rchild);

dep=1+(depl>depr?depl:depr);}

return dep;}

void main(){ BiTree T;int dep;printf(“請輸入您要創建的二叉樹！!n

'#'表示空元素！n”);T=Create(T);

printf(“nn您要求的二叉樹的深度：”);dep=Depth(T);

printf(“%dnn”,dep);} }

內蒙古工業大學信息工程學院

二 測試結果

三 調試程序出現的問題及解決的方法

編程中出現很多的編譯錯誤，主要采用對每個函數調試，設斷點，運用自己的程序中，讓我更好的掌握了遞歸算法。四 實驗心得體會

通過這次試驗，讓我鞏固了鏈式存儲結構和遞歸算法的使用，用模塊化思路設計程序，編寫程序要小心謹慎，要細化到每個函數，通過多次調試，才使得整個程序正確運行，達到預期結果。

第二篇：實驗一線性表的創建與訪問算法設計

內蒙古工業大學信息工程學院

四、編譯程序：

#include #include #define MAXSIZE 100

typedef char ElemType;typedef struct LNode

//定義單鏈表結點類型 {

ElemType data;

struct LNode *next;}LinkList;

LinkList *CreatlinkR(LinkList *L)

//用尾插法建立帶頭結點的單鏈表 {

LinkList *s, *r;char ch;r =(LinkList *)malloc(sizeof(LinkList));

//創建頭結點

L = r;s = r;r->next = NULL;printf(“單鏈表元素值為單個字符, 連續輸入，$為結束字符:”);while((ch = getchar())!= '$'){

r =(LinkList *)malloc(sizeof(LinkList));

//創建新結點

r->data = ch;

r->next = NULL;

s->next = r;

s = r;

} r->next=NULL;

//終端結點

return(L);}

void Sort(LinkList *h)

//單鏈表元素排序 { LinkList *p=h->next,*q,*t;

if(p!=NULL){

t=p->next;

p->next=NULL;

p=t;

while(p!=NULL)

{

t=p->next;

q=h;

第 頁

內蒙古工業大學信息工程學院

while(q->next!=NULL&&q->next->data

data)

q=q->next;

//在有序表中找插入*p的前驅結點*q

p->next=q->next;

//將*p插到*q之后

q->next=p;

p=t;

} } }

void DispList(LinkList *L)

//輸出單鏈表L {

LinkList *p=L->next;

while(p!=NULL){

printf(“%c ”,p->data);

p=p->next;} }

LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)

{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;

Lc=(LinkList *)malloc(sizeof(LinkList));

tc=Lc;while(pa!=NULL&&pb!=NULL){

if(pa->data

data)

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pa->data;

tc->next=s;

tc=s;

pa=pa->next;

}

else if(pa->data>pb->data)

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pb->data;

tc->next=s;

tc=s;

pb=pb->next;

}

else

{

第 頁

//求兩有序集合的并集 //復制結點

內蒙古工業大學信息工程學院

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pa->data;

tc->next=s;

tc=s;

pa=pa->next;

//重復元素只復制一個

pb=pb->next;

} } if(pb!=NULL)

//復制余下結點

pa=pb;while(pa!=NULL){

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pa->data;

tc->next=s;

tc=s;

pa=pa->next;

} tc->next=NULL;return(Lc);}

LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)

//求兩有序集合的交集 {

LinkList *pa=La->next,*pb,*s,*tc;

Lc=(LinkList *)malloc(sizeof(LinkList));

tc=Lc;

while(pa!=NULL){

pb=Lb->next;

while(pb!=NULL&&pb->data

data)

pb=pb->next;

if(pb!=NULL&&pb->data==pa->data)

//若pa結點值在pb中

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pa->data;

tc->next=s;

tc=s;

}

pa=pa->next;}

tc->next=NULL;return(Lc);

第 頁

內蒙古工業大學信息工程學院

}

LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)

//求兩有序集合的差集 {

LinkList *pa=La->next,*pb,*s,*tc;

Lc=(LinkList *)malloc(sizeof(LinkList));

tc=Lc;

while(pa!=NULL){

pb=Lb->next;

while(pb!=NULL&&pb->data

data)

pb=pb->next;

if(!(pb!=NULL&&pb->data==pa->data))

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=pa->data;

tc->next=s;

tc=s;

}

pa=pa->next;} tc->next=NULL;return(Lc);}

void main(){

LinkList *La,*Lb,*Lc;

int num=0,loop,j;loop=1;La=CreatlinkR(La);Lb=CreatlinkR(Lb);Sort(La);Sort(Lb);

printf(“有序集合A＝{ ”);

DispList(La);

printf(“}n”);

printf(“有序集合B＝{ ”);

DispList(Lb);printf(“}n”);while(loop){

printf(“請選擇您要執行的操作：1.求并集

scanf(”%d“,&j);printf(”n%d“,j);

第 頁

//若pa結點值不在pb中 2.求交集

3.求差集n”);

內蒙古工業大學信息工程學院

if(j>=1&&j<=3)

switch(j)

{

case 1: Lc=Union(La,La,Lc);

printf(“集合A與集合B的并集C＝{ ”);

DispList(Lc);

printf(“}n”);

break;

case 2: Lc=InsterSect(La,Lb,Lc);

printf(“集合A與集合B的交集C＝{ ”);

DispList(Lc);

printf(“}n”);

break;

case 3: Lc=Subs(La,Lb,Lc);

printf(“集合A與集合B的差集C＝{ ”);

DispList(Lc);

printf(“}n”);

break;

} printf(“0.結束

1.繼續n”);scanf(“%d”,&loop);printf(“n”);} }

五、運行結果：

1．輸入兩個無序集合，排序后輸出：

第 頁

內蒙古工業大學信息工程學院

2．求集合的并集：

3．選1繼續：

第 頁

內蒙古工業大學信息工程學院

4．求集合的交集：

5．求集合的差集：

第 頁

內蒙古工業大學信息工程學院

6．選0結束：

第 頁

第三篇：二叉樹的構造函數算法BiTree

template

BiTree ::BiTree(BiNode *root){

creat(root)；

}

template

void BiTree ::Creat(BiNode *root){

cin>>ch;

if(ch=='# ')root=NULL;//建立一棵空樹else {

root=new BiNode;//生成一個結點root->data=ch;

Creat(root->lchild);//遞歸建立左子樹Creat(root->rchild);//遞歸建立右子樹}

}

第四篇：算法描述與設計教案

課型：新課 《算法與程序設計》（選修）人教版

教學目標：

1.進一步理解什么是；算法，知道算法的多樣性

2.能夠對設計的算法做簡裝的評價

3.學會利用自然語言、流程圖和偽代碼來描述算法

教學內容

1.了解什么是算法及其特征 2.學習三種描述算法語言

教學重點:通過例子設計算法

教學難點:三種描述算法語言的使用

課時數：1課時

正課講解

一、算法是“靈魂”

1.算法存在于人們生活中，如：上街購物、顧客付款、營業員（主）找銀等。

2.“韓信點兵問題”有不同的求解過程，就有不同的算法。

有N個人，除以3，5，7，分別余2，3，2，求N。

3.算法——解決問題的方法和步驟。

算法是尼克勞斯.沃斯（N.Writh）提出的，他指出：算法+數據結構=程序。

（即算法不能單獨構成程序，它必須和數據結構合二為一）

4.算法的發現

時間：公元前3000年~公元前1500年 地點：巴比倫

巴比倫人求解“算法”的過程：先用解代數方法，再計算實際數目，最后寫上一句短句“這就是一個過程”。

5.算法的特征

我們曾在必須修課中提過一點算法，如：冒泡排序法。

例：計算1+2+3+??+100=？

分析：這個算法有限制范圍，可以在有限時間內完成，這是算法的第一個特征：有窮性。計算此算法可以用紙筆、算盤、運算器

和計算機來完成，且計算過程是多樣的，但結果是唯一的。這就是算法的可行性、確定性。

計算方法：

⑴把這100個數按順序相加。

⑵用湊數法：1+99=100，2+98=100，3+97=100，??，49+51，最后只剩下50和100。

⑶令S=0，使1≤n≤100，先執行S=S+n ⑴，再執行n=n+1 ⑵

n=1，S=0時，S（0）=1 n=2，S=1時，S（0）=3 n=3，S=3時，S（0）=6

n=4，S=6時，S（0）=10 n=5，S=10時，S（0）=15 n=6，S=15時，S（0）=21??

算法的另外一個特征：輸入、輸出。

練習：水仙花數問題，如153=1^3+5^3+3^3，分析它應滿足什么條件才能使用此方法？

二、如何描述算法

1.用自然語言描述算法

⑴自然語言——人們日常生活中使用的語言。

⑵此種語言的特點：通俗語易懂，缺乏直觀性和簡潔，且易產生歧義。

使用此種語言的注意事項：描述要求盡可能精確，詳盡。

例：用自然語言描述凱撒密碼的原理

第1步：輸入26個英文字母，它們分別對應1~26個數學。

第2步：令a=1，k=3，n=26。

第3步：使a的取值范圍為1≤a≤26，F(a)=(a+k)mod n，轉第5步。

第4步：a=a+1，轉第3步。

第5步：輸出F(a)相對應的數字。

第6步：把數學轉化成相當的字母，輸出字母。

第7步：累計字母出現順序，轉第4步。

練習：現有一串字母“PROGRAM”給它加密，請設計算法，用自然語言描述。

2.用流程圖描述算法

⑴特點：描述算法形象、直觀，容易理解。

⑵流程圖符號

3.用偽代碼描述算法

特點：描述的算法簡、易懂，修改容易，容易轉化為程序語言代碼。

例：分析課本經9頁算法描述

第一個條件：y mod 4=0

判斷閏年的條件：⑴y不能被100整除；⑵y能被400整除且y能被400整除。

判斷不是閏年的條件：⑴y mod 4=0 且y mod 100=0,但y不能被400整除；⑵y不能被4整除。

表示條件判斷語句 表示循環處理語句：

IF 條件 THEN 執行語句一 Do While 條件循環語句

ELSE執行語句二 Loop

END IF

條件語句中可以包含多個子語句

實踐：用表格比較自然語言、流程圖和偽代碼3種描述方法的優缺點。

第五篇：數據結構算法設計與分析

數據結構算法設計與分析、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、Oracle、XML程序設計、計算機網絡、SSH（Struts+Spring+Hibernate）框架、Java EE程序設計、Ajax程序設計、Linux+PHP+MySQL程序設計、Android手機開發、UML系統分析與設計、性能測試、自動化軟件測試、軟件質量保證、畢業設計及項目綜合實訓等。

數據結構、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、金融學概論、西方經濟學等基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、SQL Server數據庫、Oracle數據庫、Linux操作系統、UML系統分析與設計、軟件工程、XML程序設計、SSH框架、金融市場學、ERP財務管理、管理信息系統、投資銀行學、商業銀行學、國際金融管理、畢業設計及項目綜合實訓等專業課程。

數據結構、計算機網絡、計算機組成原理、操作系統原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、XML程序設計、Ajax程序設計、SSH框架、Android手機開發、Linux+PHP+MySQL程序設計、SQL Server數據庫、Linux操作系統、UML系統分析與設計、軟件項目管理、行業標準與規范、IT服務管理、IT職業英語、畢業設計及項目綜合實訓等專業課程