人的記憶力會隨著歲月的流逝而衰退,，寫作可以彌補(bǔ)記憶的不足,，將曾經(jīng)的人生經(jīng)歷和感悟記錄下來,，也便于保存一份美好的回憶,。相信許多人會覺得范文很難寫？接下來小編就給大家介紹一下優(yōu)秀的范文該怎么寫,，我們一起來看一看吧,。

數(shù)據(jù)結(jié)構(gòu)講義篇一

第一章：數(shù)據(jù)結(jié)構(gòu)概述

1、掌握數(shù)據(jù)結(jié)構(gòu)的定義,，即數(shù)據(jù)結(jié)構(gòu)三要素：數(shù)據(jù)的邏輯結(jié)構(gòu),、存儲結(jié)構(gòu)、操作,；

2,、數(shù)據(jù)結(jié)構(gòu)包括：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；

3,、數(shù)據(jù)之間的關(guān)系：表（一對一之間的關(guān)系）,、樹（一對多之間的關(guān)系）、圖（多對多之間的關(guān)系）,；

4,、算法的定義：算法衡量的標(biāo)準(zhǔn)：時間復(fù)雜度和空間復(fù)雜度；

5,、算法時間復(fù)雜度的求法：給定一段程序,，求其時間復(fù)雜度；時間復(fù)雜度的比較,；

6、為什么學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”,？“數(shù)據(jù)結(jié)構(gòu)”課程主要學(xué)了哪些知識,？

第二章：線性表

1、線性表按照存儲結(jié)構(gòu)不同分為順序表,、鏈?zhǔn)奖?；順序表的特點(diǎn)：邏輯上相鄰的兩個元素在物理上也相鄰；鏈?zhǔn)奖淼奶攸c(diǎn)：邏輯上相鄰的兩個元素在物理上未必相鄰,；（“未必”的含義是可相鄰也可以不相鄰）

2,、比較線性表順序存儲和鏈?zhǔn)酱鎯Φ膬?yōu)缺點(diǎn),。

第三章：棧和隊列

1、棧和隊列的特點(diǎn)：棧：后進(jìn)先出,，隊列：先進(jìn)先出

2,、熟悉棧和隊列的基本操作：初始化棧、入棧操作,、出棧操作,、判斷棧是否為空、取棧頂元素等,。

3,、根據(jù)實(shí)例，能夠容易的判斷出是棧的應(yīng)用還是隊列的應(yīng)用,？

4,、重點(diǎn)掌握棧的應(yīng)用：進(jìn)制轉(zhuǎn)換算法的思想或程序。

第四章：數(shù)組

1,、牢記對稱矩陣,、三角矩陣、對角矩陣的特點(diǎn),，掌握矩陣中的元素aij與一維數(shù)組sa[k]的對應(yīng)關(guān)系,。

2、掌握稀疏矩陣的三元組表示法,。

第五章：串

1,、掌握上課介紹的9種函數(shù)名稱及其實(shí)現(xiàn)結(jié)果；

第六章：樹

1,、二叉樹的5個性質(zhì),；

2、二叉樹前序,、中序和后序遍歷,，根據(jù)2種遍歷結(jié)果求第3種遍歷結(jié)果。

3,、完全二叉樹,、滿二叉樹、哈弗曼樹的定義,；

4,、給定一組葉子權(quán)值，求帶權(quán)路徑長度最小的多少,？

第七章：圖

1,、掌握圖的術(shù)語：無向完全圖、有向完全圖、頂點(diǎn)的度等,；

2,、圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷；

3,、圖的鄰接矩陣存儲,，給定一個圖，求出鄰接矩陣,；或者給定一個鄰接矩陣,，構(gòu)造圖；

4,、圖的最小生成樹,；

第八章：查找

1、查找的定義：靜態(tài)查找和動態(tài)查找

2,、折半查找算法的思想,；

第九章：排序

1、掌握排序的分類：插入排序,、交換排序,、選擇排序；

2,、重點(diǎn)掌握希爾排序,、快速排序、簡單選擇排序,；

數(shù)據(jù)結(jié)構(gòu)講義篇二

數(shù)據(jù)結(jié)構(gòu)】二叉排序樹的建立,，查找，插入和刪除實(shí)踐題 /*sy53.c*/

#include

typedef struct node{

keytype key;

struct node *lchild,*rchild;

}bstnode;

typedef bstnode *bstree;

bstree createbst(void);

void searchbst(bstree t,keytype key);

void insertbst(bstree *tptr,keytype key);

void delbstnode(bstree *tptr,keytype key);

void inorderbst(bstree t);

main()

{bstree t;

char ch1,ch2;

keytype key;

printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);

t=createbst();

ch1='y';

while(ch1=='y' || ch1=='y')

{printf(“請選擇下列操作：n”);

printf(“1------------------更新二叉排序樹存儲n”);

printf(“2------------------二叉排序樹上的查找n”);

printf(“3------------------二叉排序樹上的插入n”);

printf(“4------------------二叉排序樹上的刪除n”);

printf(“5------------------二叉排序樹中序輸出n”);

printf(“6------------------退出n”);

scanf(“n%c”,&ch2);

switch(ch2)

{case '1':t=createbst();break;

case '2':printf(“n請輸入要查找的數(shù)據(jù)：”);

scanf(“n%d”,&key);

searchbst(t,key);

printf(“查找操作完畢,。n”);break;

case '3': printf(“n請輸入要插入的數(shù)據(jù)：”);

scanf(“n%d”,&key);

insertbst(&t,key);

printf(“插入操作完畢,。n”);break;

case '4': printf(“n請輸入要刪除的數(shù)據(jù)：”);

scanf(“n%d”,&key);

delbstnode(&t,key);

printf(“刪除操作完畢。n”);break;

case '5': inorderbst(t);

printf(“n二叉排序樹輸出完畢,。n”);break;

case '6':ch1='n';break;

default:ch1='n';

}

}

}

bstree createbst(void)

{bstree t;

keytype key;

t=null;

printf(“請輸入一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“請輸入下一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“n%d”,&key);

}

return t;

}

void searchbst(bstree t, keytype key)

{ bstnode *p=t;

while(p)

{if(p->key==key)

{printf(“已找到n”);

return;

}

p=(key

key)? p->lchild:p->rchild;

}

printf(“沒有找到n”);

}

void insertbst(bstree *t,keytype key)

{bstnode *f,*p;

p=(*t);

while(p)

{if(p->key==key)

{printf(“樹中已有key不需插入n”);

return;

}

f=p;

p=(key

key)?p->lchild:p->rchild;

}

p=(bstnode*)malloc(sizeof(bstnode));

p->key=key;

p->lchild=p->rchild=null;

if((*t)==null)(*t)=p;

else if(key

key)f->lchild=p;

}/*insertbst*/

void delbstnode(bstree *t,keytype key)

{bstnode *parent=null, *p, *q,*child;

p=*t;

while(p)

{if(p->key==key)break;

parent=p;

p=(key

key)?p->lchild:p->rchild;

}

if(!p){printf(“沒有找到要刪除的結(jié)點(diǎn)n”);return;}

q=p;

if(q->lchild && q->rchild)

for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;

if(!parent)*t=child;

else {if(p==parent->lchild)

parent->lchild=child;

else parent->rchild=child;

if(p!=q)

q->key=p->key;

}

free(p);

}

void inorderbst(bstree t){ if(t!=null)

{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}

}

數(shù)據(jù)結(jié)構(gòu)講義篇三

數(shù)據(jù)結(jié)構(gòu)參考題目

一,、選擇

1.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼,，則該結(jié)構(gòu)是（）

a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復(fù)雜度為（）for(i=0;i

next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.兩個字符串相等的條件是（）

c.都是非空串 d.串的長度相等且對應(yīng)的字符相同 5．若以s和x分別表示進(jìn)棧和退棧操作,，則對初始狀態(tài)為空的棧可以進(jìn)行的棧操作系列是（）

xx sx sx xx 6.已知一棵含50個結(jié)點(diǎn)的二叉樹中只有一個葉子結(jié)點(diǎn),，則該樹中度為1的結(jié)點(diǎn)個數(shù)為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對關(guān)鍵字序列（51,，35，93,，24，13，68,，56,，42，77）進(jìn)行排序時,，前兩趟排序的結(jié)果為

（35,，51，24,，13,，68，56,，42,，77，93）

（35,，24,，13，51,，56,，42，68,，77,，93）所采用的排序方法是（）

a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序

8.已知散列表的存儲空間為t[0..16]，散列函數(shù)h（key）=key%17,并用二次探測法處理沖突,。散列表中已插入下列關(guān)鍵字：t[5]=39,，t[6]=57和t[7]=7，則下一個關(guān)鍵字23插入的位置是（）

a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個子表,，整個矩陣看成是一個廣義表l,，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運(yùn)算求取矩陣中的每一個元素,，則求得a21的運(yùn)算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點(diǎn)的有向圖中,，所有頂點(diǎn)的出度之和為dout，則所有頂點(diǎn)的入度之和為（）

-1 +1 d.n 11．從邏輯關(guān)系來看,，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）a線性結(jié)構(gòu) b.樹形結(jié)構(gòu) c.線性結(jié)構(gòu)和樹型結(jié)構(gòu) d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)

12．棧的插入和刪除操作在()進(jìn)行,。

a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權(quán)值分別為11，8,，6,，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹,，它的帶權(quán)路徑長度為（）a.24 b.71 c.48 d.53 14．一個棧的輸入序列為1 2 3,，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關(guān)于棧和隊列的說法中正確的是（）

a．棧和隊列都是線性結(jié)構(gòu) b.棧是線性結(jié)構(gòu),，隊列不是線性結(jié)構(gòu) c.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu) d.棧和隊列都不是線性結(jié)構(gòu) 16．關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（）a．順序存儲比鏈?zhǔn)酱鎯ι僬伎臻g b.順序存儲比鏈?zhǔn)酱鎯Χ嗾伎臻g

c.順序存儲和鏈?zhǔn)酱鎯Χ家笳加谜麎K存儲空間 d.鏈?zhǔn)酱鎯Ρ软樞虼鎯﹄y于擴(kuò)充空間

17．已知一個單鏈表中,，指針q指向指針p的前趨結(jié)點(diǎn),，若在指針q所指結(jié)點(diǎn)和指針p所指結(jié)點(diǎn)之間插入指針s所指結(jié)點(diǎn)，則需執(zhí)行（）a.q→next=s,；p→next=s,； b.q→next=s；s→next=p,； c.q→next=s,；q→next=p； d.q→next=s,；s→next=q,；

18．設(shè)一組記錄的關(guān)鍵字key值為{62，50,，14,，27，19,，35,，47，56,，83},，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個數(shù)是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時,，s語句被執(zhí)行的次數(shù)為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結(jié)點(diǎn)的時間復(fù)雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個棧的輸入序列是a,，b，c,，d,，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）

a.a，b,，c,，d b.a，b,，d,，c c.d，c,，b,，a d.c，d,，a,，b 22．關(guān)于串的敘述中,，正確的是（）a．空串是只含有零個字符的串 b.空串是只含有空格字符的串

c.空串是含有零個字符或含有空格字符的串

d.串是含有一個或多個字符的有窮序列

23．在具有m個單元的循環(huán)隊列中，隊頭指針為front,，隊尾指針為rear,，則隊滿的條件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front 24．設(shè)有二維數(shù)組

?1????a［n］［n］表示如下：?23456??????????，則a［i］［i］（0≤i≤n-1）的d.i2/2 值為（）

a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中,，結(jié)點(diǎn)數(shù)最多為（）

ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結(jié)點(diǎn)數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹,，則該二叉樹中根結(jié)點(diǎn)的右子樹上具有的結(jié)點(diǎn)個數(shù)是（）

-1 c.n(m-1)d.m(n-1)27．在一個具有n個頂點(diǎn)的無向圖中,，每個頂點(diǎn)度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）a.矩陣中非全零元素的行數(shù)等于圖中的頂點(diǎn)數(shù)

b.第i行上與第i列上非零元素總和等于頂點(diǎn)vi的度數(shù) c.矩陣中的非零元素個數(shù)等于圖的邊數(shù)

d.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等

29．設(shè)一組記錄的關(guān)鍵字key值為{62，50,，14,，28，19,，35,，47，56,，83},，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個數(shù)是（）a.1 b.2 c.3 d.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49,，81,，55，36,，44,，88），則利用快速排序的方法,，以第一個關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）

a.36,，44，49,，55,，81，88 b.44,，36,，49，55,，81,，88 c.44，36,，49,，81,，55，88 d.44,，36,，49，55,，88,，81

二、填空題

1.數(shù)據(jù)是計算機(jī)加工處理的對象（）,。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu),、數(shù)據(jù)在計算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個方面()。

3.線性表是由n≥0個相同類型組成的有限序列（）,。4.棧是一種后進(jìn)先出的線性表（）,。

5.從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn),，不能找到它的前驅(qū)結(jié)點(diǎn)（）,。6.單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡化運(yùn)算（）。7.樹的最大特點(diǎn)是一對多的層次結(jié)構(gòu)（）,。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）,。

9.從非循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，既能找到它的后繼結(jié)點(diǎn),，又能找到它的前驅(qū)結(jié)點(diǎn)（）,。

10.單鏈表結(jié)點(diǎn)的指針域是用來存放其直接后繼結(jié)點(diǎn)的首地址的（）

11.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象（）。

12.用順序表來存儲線性表時,，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）,。

13.在非線性結(jié)構(gòu)中，至少存在一個元素不止一個直接前驅(qū)或不止一個直接后驅(qū)（）,。14.樹的最大特點(diǎn)是一對多的層次結(jié)構(gòu)（）,。15.隊列的特點(diǎn)是先進(jìn)先出（）。

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）,。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨(dú)立于計算機(jī)（）,。18.線性表簡稱為”順序表”。（）

19.對數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）,。20.從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā),，可以找到表中的所有結(jié)點(diǎn)（）。21.棧是一種先進(jìn)先出的線性表（）,。22.鏈表的主要缺點(diǎn)是不能隨機(jī)訪問（）,。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對解題方法和步驟的描述（）,。26.算法可以用任意的符號來描述（）,。

27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型（）,。

28.線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進(jìn)后出的線性表（）,。

30.將插入和刪除限定在表的同一端進(jìn)行的線性表是隊列（）,。

三,、畫圖題

1.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)

k={a,b,c,d,e,f,g,h,i,j} r={,,

,

,

,

,

,

,

} 3．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)

k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3）,，(2,4),(2,5),(3,7),(4,6),(5,6),，（6,7）}

四、運(yùn)算題

1．已知一個圖的頂點(diǎn)集v和邊集h分別為：

v＝{0,，1,，2，3,，4，5,，6,，7}

e＝{（0，1）8,，（0,，2）5，（0,，3）2,，（1，5）6,，（2,，3）25，（2,，4）13,，（3，5）9,，（3,，6）10，（4,，6）4,，（5，7）20},；

按照克魯斯卡爾算法得到最小生成樹,，拭寫出在最小生成樹中依次得到的各條邊。______,，______,，______,，______，______,，______,，______。

2.一個線性表為b=（12,，23,，45，57,，20,，03，78,，31,，15，36）,，設(shè)散列表為ht[0..12],，散列函數(shù)為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表,，并計算等概率情況下查找成功的平均查找長度,。

平均查找長度：（寫出計算過程）

3．已知一個圖的頂點(diǎn)集v和邊集h分別為：

v＝{0，1,，2,，3，4,，5,，6，7}

e＝{（0,，1）8,，（0，2）5,，（0,，3）2，（1,，5）6,，（2，3）25,，（2,，4）13，（3，5）9,，（3,，6）10，（4,，6）4,，（5，7）20},；

按照普里姆算法得到最小生成樹,，試寫出在最小生成樹中依次得到的各條邊。（從頂點(diǎn)2出發(fā)）

____

__,，___

_,，___

___，__

____,，___ ___,，__ ____，___ ___,。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：

前序： 中序： 后序：

5.設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起,，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。

五,、編程題

1.請編寫一個算法，實(shí)現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換,。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：

int search_bin(keytype k,sstable st){ 3.請編寫一個算法,，實(shí)現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點(diǎn)）。linklist *invertlink(linklist *h){

數(shù)據(jù)結(jié)構(gòu)講義篇四

實(shí)驗(yàn)：線性表的基本操作

【實(shí)驗(yàn)?zāi)康摹?/p>

學(xué)習(xí)掌握線性表的順序存儲結(jié)構(gòu),、鏈?zhǔn)酱鎯Y(jié)構(gòu)的設(shè)計與操作,。對順序表建立、插入,、刪除的基本操作,，對單鏈表建立、插入,、刪除的基本操作算法,。

【實(shí)驗(yàn)內(nèi)容】

1.順序表的實(shí)踐

1)建立4個元素的順序表s=sqlist[]={1，2,，3,，4，5},，實(shí)現(xiàn)順序表建立的基本操作,。

2)在sqlist []={1，2,，3,，4,，5}的元素4和5之間插入一個元素9，實(shí)現(xiàn)順序表插入的基本操作,。

3)在sqlist []={1,，2，3,，4,，9，5}中刪除指定位置（i=5）上的元素9,，實(shí)現(xiàn)順序表的刪除的基本操作,。2.單鏈表的實(shí)踐

3.1)建立一個包括頭結(jié)點(diǎn)和4個結(jié)點(diǎn)的（5，4,，2,，1）的單鏈表，實(shí)現(xiàn)單鏈表建立的基本操作,。

2)將該單鏈表的所有元素顯示出來,。

3)在已建好的單鏈表中的指定位置（i=3）插入一個結(jié)點(diǎn)3，實(shí)現(xiàn)單鏈表插入的基本操作,。

4)在一個包括頭結(jié)點(diǎn)和5個結(jié)點(diǎn)的（5,，4，3,，2,，1）的單鏈表的指定位置（如i=2）刪除一個結(jié)點(diǎn)，實(shí)現(xiàn)單鏈表刪除的基本操作,。5)實(shí)現(xiàn)單鏈表的求表長操作,。

【實(shí)驗(yàn)步驟】

1.打開vc++。

2.建立工程：點(diǎn)file->new,，選project標(biāo)簽,，在列表中選win32 console application，再在右邊的框里為工程起好名字,，選好路徑,，點(diǎn)ok->finish。至此工程建立完畢,。

3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽，在列表里選c++ source file,。給文件起好名字,，選好路徑，點(diǎn)ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中,。

4．寫好代碼

5．編譯－＞鏈接－＞調(diào)試

【實(shí)驗(yàn)心得】

線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中,，碰到的第一個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點(diǎn)掌握順序表和單鏈表的各種算法和時間性能分析,。線性表右兩種存儲方式即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu),。通過學(xué)習(xí)我知道了對線性表進(jìn)行建立、插入,、刪除,，同時單鏈表也是進(jìn)行建立、插入,、刪除,。而對于順序表的插入刪除運(yùn)算，其平均時間復(fù)雜度均為0（n）.通過這次的學(xué)習(xí),，掌握的太熟練,，主要是課本上的知識點(diǎn)沒有徹底的理解，回去我會多看書,，理解重要的概念,。總之,，這次實(shí)驗(yàn)我找到了自己的不足之處,，以后會努力的。

實(shí)驗(yàn)二：棧的表示與實(shí)現(xiàn)及棧的應(yīng)用

【實(shí)驗(yàn)?zāi)康摹?/p>

（1）掌握棧的順序存儲結(jié)構(gòu)及其基本操作的實(shí)現(xiàn),。（2）掌握棧后進(jìn)先出的特點(diǎn),，并利用其特性在解決實(shí)際問題中的應(yīng)用。（3）掌握用遞歸算法來解決一些問題,。【實(shí)驗(yàn)內(nèi)容】

1.編寫程序,，對于輸入的任意一個非負(fù)十進(jìn)制整數(shù),，輸出與其等值的八進(jìn)制數(shù)。

2.編寫遞歸程序,，實(shí)現(xiàn)n,！的求解。3.編寫遞歸程序,，實(shí)現(xiàn)以下函數(shù)的求解,。

n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1

4.編寫程序，實(shí)現(xiàn)hanoi塔問題,?！緦?shí)驗(yàn)步驟】 1.打開vc++。

2.建立工程：點(diǎn)file->new，選project標(biāo)簽,，在列表中選win32 console application,，再在右邊的框里為工程起好名字，選好路徑,，點(diǎn)ok->finish,。至此工程建立完畢。

3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽,，在列表里選c++ source file。給文件起好名字,，選好路徑,，點(diǎn)ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中,。

4．寫好代碼

5．編譯－＞鏈接－＞調(diào)試

【實(shí)驗(yàn)心得】

通過這次的學(xué)習(xí)我掌握了棧這種抽象數(shù)據(jù)類型的特點(diǎn),，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它；總的來說,，棧是操作受限的線性表,，是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此,，對棧來說,，表尾端有其特殊含義，稱為棧頂（top）,，相應(yīng)地,，表頭端稱為棧底（botton）；棧又稱為后進(jìn)先出（last in first out）的線性表,簡稱lifo結(jié)構(gòu),，因?yàn)樗男薷氖前春筮M(jìn)先出的原則進(jìn)行的,。

加上這個實(shí)驗(yàn)，我已經(jīng)學(xué)了線性表（順序表,，單鏈表）和棧,，知道它們都是線性表，而且對以后的學(xué)習(xí)有很大的作用,，可以說這是學(xué)習(xí)以后知識的總要基礎(chǔ),。

實(shí)驗(yàn)三：二叉樹的建立及遍歷

【實(shí)驗(yàn)?zāi)康摹?/p>

（1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序,、中序和后序遍歷算法,。【實(shí)驗(yàn)內(nèi)容】

1.編寫程序,，實(shí)現(xiàn)二叉樹的建立,，并實(shí)現(xiàn)先序,、中序和后序遍歷。如：輸入先序序列abc###de###,，則建立如下圖所示的二叉樹,。

并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實(shí)驗(yàn)步驟】 1.打開vc++。

2.建立工程：點(diǎn)file->new,，選project標(biāo)簽,，在列表中選win32 console application，再在右邊的框里為工程起好名字,，選好路徑,，點(diǎn)ok->finish。至此工程建立完畢,。

3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽，在列表里選c++ source file,。給文件起好名字,，選好路徑，點(diǎn)ok,。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中,。

4．寫好代碼

5．編譯－＞鏈接－＞調(diào)試

【實(shí)驗(yàn)心得】

這次試驗(yàn)是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷,，在這次實(shí)驗(yàn)中我按先序方式建立二叉樹的,，而遍歷方式則相對要多一些，有遞歸的先序,、中序,、后序遍歷，和非遞歸的先序,、中序,、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數(shù)的計算和遍歷相差不大,，只是加些判斷條件,，總體來說，本次試驗(yàn)不太好做,，期間出現(xiàn)了很多邏輯錯誤,，變量初始化的問題等,，不過經(jīng)過仔細(xì)排查最后都一一解決了,。

實(shí)驗(yàn)四：查找與排序

【實(shí)驗(yàn)?zāi)康摹?/p>

（1）掌握折半查找算法的實(shí)現(xiàn)。（2）掌握冒泡排序算法的實(shí)現(xiàn),?！緦?shí)驗(yàn)內(nèi)容】

1.編寫折半查找程序,，對以下數(shù)據(jù)查找37所在的位置。5,，13,，19，21,，37,，56，64,，75,，80，88,，92 2.編寫冒泡排序程序,，對以下數(shù)據(jù)進(jìn)行排序。49,，38,，65，97,，76,，13，27,，49 【實(shí)驗(yàn)步驟】 1.打開vc++,。

2.建立工程：點(diǎn)file->new，選project標(biāo)簽,，在列表中選win32 console application,，再在右邊的框里為工程起好名字，選好路徑,，點(diǎn)ok->finish,。至此工程建立完畢。

3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽,，在列表里選c++ source file。給文件起好名字,，選好路徑,，點(diǎn)ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中,。

4．寫好代碼

5．編譯－＞鏈接－＞調(diào)試

（1）查找算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st){ int i,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“輸入元素個數(shù)和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

(maxnum*sizeof

scanf(“%d”,&[i]);}

= n;

return ok;} int seq_search(sstable st,elemtype key){

int i;

[0]=key;

for(i=;[i]!=key;--i);

return i;} int binarysearch(sstable st,elemtype key){

int mid,low,high,i=1;

low=1;

high=;

while(low<=high)

{

mid=(low+high)/2;

if([mid]==key)

return mid;

else if(key

high=mid-1;

else

}

return 0;} void main(){ sstable st;initlist(st);

elemtype key;int n;printf(“ key= ”);

scanf(“%d”,&key);

printf(“nn”);

/*printf(“after seqsearch:: ”);

n=seq_search(st,key);

printf(“position is in %d nn”,n);*/

printf(“after binary search::”);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“position is in %d nn”,n);else

} 實(shí)驗(yàn)結(jié)果如下所示：

（2）排序算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;

(elemtype));

if(!)return(overflow);

printf(“輸入元素個數(shù)和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

scanf(“%d”,&[i]);}

= n;

return ok;} void sort(sstable st){

int i,j,t;

for(i=1;i

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

if([i]>[j]){ t=[i];=

(elemtype*)

malloc

(maxnum*sizeof

}

} [i]=[j];[j]=t;void display(sstable st){ int i;

for(i=1;i<=;i++){

printf(“%d

”,[i]);}

} void main(){

sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 實(shí)驗(yàn)結(jié)果如下所示：

【實(shí)驗(yàn)心得】

通過這次實(shí)驗(yàn),我明白了程序里的折半查找和冒泡查找.其實(shí)排序可以有很多種,，但是其目的應(yīng)該都是為了能夠在海量的數(shù)據(jù)里迅速查找到你要的數(shù)據(jù)信息，折半查找是種比較快的方式,，但前提是要是有 序的排序才可以,。對于有序表,，查找時先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較，若相等,，則查找成功,；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進(jìn)行折半查找,；否則在前半部分進(jìn)行折半查找,，直到查找范圍為空而查不到為止。折半查找的過程實(shí)際上死先確定待查找元素所在的區(qū)域,，然后逐步縮小區(qū)域,，直到查找成功或失敗為止。算法中需要用到三個變量,，low表示區(qū)域下界,，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.

數(shù)據(jù)結(jié)構(gòu)講義篇五

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

模塊一：計算題

一.一棵二叉樹的先序,、中序和后序序列分別如下,，其中有一部分未顯示出來。試求出空格處的內(nèi)容,，并畫出該二叉樹,。先序序列： b f iceh g 中序序列：d kfia ejc 后序序列： k fbhj g a 解：在先序序列空格中依次填adkj，中序中依次填bhg,，后序中依次填diec,。

二叉樹自畫！

二．試列出如下圖中全部可能的拓?fù)渑判蛐蛄小?/p>

123456 解：全部可能的拓?fù)渑判蛐蛄袨椋?52364,、152634,、156234、561234,、516234,、512634、512364 三．已知哈希表地址空間為0..8,，哈希函數(shù)為h(key)=key%7,，采用線性探測再散列處理沖突，將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中,，列出插入時的比較次數(shù),，并求出在等概率下的平均查找長度以及查找因子。

解：哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：

asl=1(4×1+1×2+1×4+2×5)=2.5

8a=8/9

四．已知關(guān)鍵字序列{23,，13,，5，28,，14,，25}，試構(gòu)造二叉排序樹,。

解：

五．設(shè)有序列：w={23,24,27,80,28},，試給出哈夫曼樹； 哈夫曼樹如下圖所示：

六：已知一棵二叉樹的先序序列與中序序列分別如下,，試畫出此二叉樹,。先序序列：abcdefghij 中序序列：cbedaghfji

解：先由先序序列的第一個結(jié)點(diǎn)確定二叉樹的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部分為左子樹結(jié)點(diǎn),，在右側(cè)部分為右子樹結(jié)點(diǎn),，再由先序序列的第一個結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，由類似的方法可確定其他結(jié)點(diǎn),，如下圖所示,。

七．（本題8分）

對于如下圖所示的g，用kruskal算法構(gòu)造最小生成樹,，要求圖示出每一步的變化情況,。

解：用kruskal算法構(gòu)造最小生成樹的過程如下圖所示：

八．給出一組關(guān)鍵字29、18,、25,、47、58,、12,、51、10,，寫出歸并排序方法進(jìn)行排序時的變化過程,。

解：

(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58)

九．

三、（本題8分）

請畫出如下圖所示的鄰接表,。

解：鄰接表如下圖所示：

***45454∧∧∧∧5∧ 十．判斷以下序列是否是小根堆? 如果不是,，將它調(diào)整為小根堆。（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 解：（1）不是小根堆,。調(diào)整為：{12,24,33,65,33,56,48,92,86,70}

（2）是小根堆,。

十一． 設(shè)有如下圖所示的aoe網(wǎng)（其中vi（i=l，2,，…,，6）表示事件，弧上表示活動的天數(shù)）,。

v26v14v48217v311v693v5 找出所有的關(guān)鍵路徑,。

解：所有的關(guān)鍵路徑有：v1→v2→v3→v5→v6，以及v1→v4→v6,。十二.對給定的有7個頂點(diǎn)的有向圖的鄰接矩陣如下：（l）畫出該有向圖,；

（2）若將圖看成是aoe-網(wǎng),，畫出關(guān)鍵路徑。

??????????????????252?2???1?????????????????8???35???

5????39????5??????

解：（1）由鄰接矩陣所畫的有向圖如下圖所示：

2212523***5）關(guān)鍵路徑如下圖所示：

22213715945 4（2