在日常學(xué)習(xí)、工作或生活中，大家總少不了接觸作文或者范文吧，通過文章可以把我們那些零零散散的思想，聚集在一塊。范文書寫有哪些要求呢？我們怎樣才能寫好一篇范文呢？下面我給大家整理了一些優(yōu)秀范文，希望能夠幫助到大家，我們一起來看一看吧。

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

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

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

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

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

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

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

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

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

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

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

4)在一個(gè)包括頭結(jié)點(diǎn)和5個(gè)結(jié)點(diǎn)的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個(gè)結(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。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中。

4．寫好代碼

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

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

線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中，碰到的第一個(gè)數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點(diǎn)掌握順序表和單鏈表的各種算法和時(shí)間性能分析。線性表右兩種存儲方式即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。通過學(xué)習(xí)我知道了對線性表進(jìn)行建立、插入、刪除，同時(shí)單鏈表也是進(jìn)行建立、插入、刪除。而對于順序表的插入刪除運(yùn)算，其平均時(shí)間復(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.編寫程序，對于輸入的任意一個(gè)非負(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。至此一個(gè)源文件就被添加到了你剛創(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)行的。

加上這個(gè)實(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。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中。

4．寫好代碼

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

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

這次試驗(yàn)是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實(shí)驗(yàn)中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個(gè)數(shù)的計(jì)算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗(yàn)不太好做，期間出現(xiàn)了很多邏輯錯(cuò)誤，變量初始化的問題等，不過經(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。至此一個(gè)源文件就被添加到了你剛創(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(“輸入元素個(gè)數(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(“輸入元素個(gè)數(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ù)信息，折半查找是種比較快的方式，但前提是要是有 序的排序才可以。對于有序表，查找時(shí)先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較，若相等，則查找成功；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進(jìn)行折半查找；否則在前半部分進(jìn)行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實(shí)際上死先確定待查找元素所在的區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。算法中需要用到三個(gè)變量，low表示區(qū)域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.

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

云淡風(fēng)清 http:///

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

1.1概述

以下為某市部分院校的交通地圖情況，要求找出從出發(fā)點(diǎn)到目的地之間的最短路徑及其長度。

對于此問題，如果手工去做，速度慢(特別地，現(xiàn)實(shí)中實(shí)際地圖信息要比此例復(fù)雜許多)，還容易出錯(cuò)，此時(shí)可借助于計(jì)算機(jī)完成。

計(jì)算機(jī)進(jìn)行此類信息的處理時(shí)，涉及到兩個(gè)問題：一是現(xiàn)實(shí)當(dāng)中的信息在計(jì)算機(jī)中如何表示，二是如何對信息進(jìn)行處理。

信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問題不斷復(fù)雜化，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。

1.1.1編寫解決實(shí)際問題的程序的一般流程

如何通過編寫程序，以比手工更為高效精確的方式解決實(shí)際問題呢？一般流程如下：

1、由具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型；

2、分析問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系；

3、確定如何在計(jì)算機(jī)中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系？

4、確定處理問題時(shí)需要對數(shù)據(jù)作何種運(yùn)算？

5、確定算法并編寫程序；

5、分析所編寫的程序的性能是否良好？若性能不夠好則重復(fù)以上步驟。

云淡風(fēng)清 http:/// 上面所列舉的問題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來回答。

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中的一門綜合性專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的一門核心課程，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。

1.1.2數(shù)據(jù)結(jié)構(gòu)的例子

1、電話號碼查詢系統(tǒng)

設(shè)有一個(gè)電話號碼薄，它記錄了n個(gè)人的名字和其相應(yīng)的電話號碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告沒有這個(gè)人的標(biāo)志。

姓名

電話號碼

陳偉海 *** 李四鋒 ***。。

這是一種典型的線性結(jié)構(gòu)。

2、磁盤目錄文件系統(tǒng)

磁盤根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類推。

。。

本問題中各目錄從上到小形成了一種一對多的關(guān)系，是一種典型的樹形結(jié)構(gòu)。

云淡風(fēng)清 http:///

3、交通網(wǎng)絡(luò)圖

下圖表明了若干個(gè)城市之間的聯(lián)系：

從圖中可看出，一個(gè)地方到另外一個(gè)地方可以有多條路徑，是一種典型的網(wǎng)狀結(jié)構(gòu)，數(shù)據(jù)與數(shù)據(jù)成多對多的關(guān)系。

4、排序問題

對100000個(gè)整數(shù)進(jìn)行降序排序。冒泡法程序： #include

#include

#include

#define n 100000 void main(){ int i,j;int a[n+1];srand(time(null));for(i=1;i<=n;i++)

printf(“%8d”,a[i]);system(“pause”);for(j=1;j

for(i=n;i>j;i--)

if(a[i]>a[i-1])

{

a[0]=a[i];

a[i]=a[i-1];

a[i-1]=a[0];

} printf(“n按新次序輸出：n”);

云淡風(fēng)清 http:/// for(i=1;i<=n;i++)

printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include

#include

#include

#define n 100000

{

//將劃分子集的元素(此處選中間元素)移動到最左邊

temp=a[left];

a[left]=a[(left+right)/2];

a[(left+right)/2]=a[left];

last=left;//用last記錄比關(guān)鍵字小的元素的最右位置

for(j=left+1;j<=right;j++)//劃分子集

if(a[j]>a[left])

{

temp=a[last];

a[last]=a[j];

a[j]=temp;

last++;

}

//對形成的新子集遞歸進(jìn)行快速排序

quick_sort(a,left,last-1);

quick_sort(a,last+1,right);} } void main(){ int i;int a[n+1];srand(time(null));for(i=1;i<=n;i++)

a[i]=rand();printf(“n按原序輸出：n”);for(i=1;i<=n;i++)

printf(“%8d”,a[i]);system(“pause”);

云淡風(fēng)清 http:/// quick_sort(a,1,n);printf(“n按新次序輸出：n”);for(i=1;i<=n;i++)

printf(“%8d”,a[i]);printf(“n”);} 運(yùn)行可知，兩者速度差異非常明顯，主要是排序所花的時(shí)間差別很大?？煽闯觯瑯拥膯栴}，采用不同方法進(jìn)行處理，有可能呈現(xiàn)出非常大的性能方面的差異。

還可以找到許多其它例子，如圖書館的書目檢索系統(tǒng)自動化問題，教師資料檔案管理系統(tǒng)，多叉路口交通燈的管理問題等。

1.2基本概念和術(shù)語 1.2.1數(shù)據(jù)(data)：

是客觀事物的符號表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。

1.2.2數(shù)據(jù)元素(data element)：

是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(data item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對客觀事物某一方面特性的數(shù)據(jù)描述。

1.2.3數(shù)據(jù)對象(data object)：

是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集，其中的數(shù)據(jù)元素可以是有限的，也可以是無限的。如整數(shù)集合：n={0，±1，±2，…}，是無限集，而字符集合：c={ˊaˊ，bˊ，…，ˊzˊ}則為有限集。

1.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)：

指對數(shù)據(jù)元素之間邏輯關(guān)系的描述。

數(shù)據(jù)元素之間的關(guān)系可以是一種或多種。

數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為定義的關(guān)系，這種自然或人為定義的“關(guān)系”稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。其要點(diǎn)有兩個(gè)方面：一是元素本身，二是元素之間的關(guān)系。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如下：

云淡風(fēng)清 http:///

①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在一對一的關(guān)系。③樹型結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在一對多的關(guān)系。

④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在多對多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)形式的定義是一個(gè)二元組： datastructure=(d，s)其中：d是數(shù)據(jù)元素的有限集，s是d上關(guān)系的有限集。例：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)b=(k，r)，其中： k={k1, k2, …, k9}

r={

，

，

，

，

，

，

，

，

，

，

} 畫出這邏輯結(jié)構(gòu)的圖示，并確定哪些是起點(diǎn)，哪些是終點(diǎn)。

又稱存儲結(jié)構(gòu)，指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲方式。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關(guān)系的存儲。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。

例：設(shè)有數(shù)據(jù)集合a={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲結(jié)構(gòu)。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；

鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。

在c語言中，用一維數(shù)組表示順序存儲結(jié)構(gòu)；通過結(jié)構(gòu)體類型實(shí)現(xiàn)的鏈表來表示鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1.2.6數(shù)據(jù)結(jié)構(gòu)(data structure)：

按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。

1.2.7數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：

邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述：d_s=(d，s)。

存儲結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對數(shù)據(jù)要進(jìn)行的運(yùn)算。

本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲結(jié)構(gòu)如下圖所示。

云淡風(fēng)清 http:///

邏輯結(jié)構(gòu)與所采用的存儲結(jié)構(gòu)

數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖

1.2.8數(shù)據(jù)類型(data type)：

指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱。

數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念。在c語言中數(shù)據(jù)類型有：基本類型(如int，float，double，char等)和構(gòu)造類型(如數(shù)組，結(jié)構(gòu)體，共用體等)。

數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。

1.3數(shù)據(jù)結(jié)構(gòu)的運(yùn)算

數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括： ⑴建立(create)一個(gè)數(shù)據(jù)結(jié)構(gòu)； ⑵消除(destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)；

⑶從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(delete)一個(gè)數(shù)據(jù)元素； ⑷把一個(gè)數(shù)據(jù)元素插入(insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中； ⑸對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(access)；

⑹對一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(modify)； ⑺對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(sort)； ⑻對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(search)。

以上只列舉了一些常見運(yùn)算，實(shí)際應(yīng)用當(dāng)中可能會遇到許多其它運(yùn)算。

云淡風(fēng)清 http:/// 1.4抽象數(shù)據(jù)類型(abstract data type)1.4.1抽象數(shù)據(jù)類型簡介：

簡稱adt，是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。adt的定義僅是一組邏輯特性描述，與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無關(guān)。因此，不論adt的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

adt的形式化定義是三元組：adt=(d，s，p)其中：d是數(shù)據(jù)對象，s是d上的關(guān)系集，p是對d的基本操作集。說明：

⑴adt和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，其區(qū)別是：adt的范疇更廣,它不再局限于系統(tǒng)已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶自己定義的數(shù)據(jù)類型。

⑵adt的定義是由一個(gè)值域和定義在該值域上的一組操作組成。包括定義，表示和實(shí)現(xiàn)三個(gè)部分。⑶adt的最重要的特點(diǎn)是抽象和信息隱蔽。抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細(xì)節(jié)，使所設(shè)計(jì)的結(jié)構(gòu)更具有一般性，可以解決一類問題。信息隱蔽就是對用戶隱藏?cái)?shù)據(jù)存儲和操作實(shí)現(xiàn)的細(xì)節(jié)，使用者了解抽象操作或界面服務(wù)，通過界面中的服務(wù)來訪問這些數(shù)據(jù)。

adt不考慮物理結(jié)構(gòu)以及算法的具體實(shí)現(xiàn)。

例：整數(shù)的數(shù)學(xué)概念和對整數(shù)所能進(jìn)行的運(yùn)算構(gòu)成一個(gè)adt，c語言中的變量類型int就是對這個(gè)抽象數(shù)據(jù)類型的一種物理實(shí)現(xiàn)。

1.4.2adt的一般定義形式：

adt的一般定義形式是： adt<抽象數(shù)據(jù)類型名> { 數(shù)據(jù)對象：<數(shù)據(jù)對象的定義> 數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義> 基本操作：<基本操作的定義> }adt<抽象數(shù)據(jù)類型名> 其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述?；静僮鞯亩x是： <基本操作名>(<參數(shù)表>)初始條件：<初始條件描述> 操作結(jié)果：<操作結(jié)果描述> 說明：

初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件；若不滿足，則操作失敗，返回相應(yīng)的出錯(cuò)信息。

操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。

1.5算法(algorithm)1.5.1算法基本概念：

算法是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或

云淡風(fēng)清 http:/// 多個(gè)操作。

1.5.2算法的基本特征：

算法具有以下五個(gè)特性

①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。

②確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。

③可行性：一個(gè)算法是能行的。即算法描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。

④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對象集合。

⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

1.5.3算法的基本描述方法：

一個(gè)算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語言描述等。

1.5.4算法與程序的異同比較：

算法和程序是兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)程序是對一個(gè)算法使用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。算法必須可終止意味著不是所有的計(jì)算機(jī)程序都是算法。

1.5.5評價(jià)算法好壞的幾個(gè)標(biāo)準(zhǔn)：

評價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)

①正確性(correctness)：算法應(yīng)滿足具體問題的需求。

②可讀性(readability)：算法應(yīng)易于供人閱讀和交流?？勺x性好的算法有助于對算法的理解和修改。

③健壯性(robustness)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。

④通用性(generality)：算法應(yīng)具有一般性，即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立。⑤效率與存儲容量需求：效率指的是算法執(zhí)行的時(shí)間；存儲容量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關(guān)。

1.6算法效率的度量

解決同一個(gè)問題的算法可能有多種，如何選擇一個(gè)效率高的算法呢？應(yīng)該來講，與算法效率相關(guān)的因素有很多，如下：

云淡風(fēng)清 http:///

1、算法選用何種策略；

2、問題的規(guī)模；

3、程序設(shè)計(jì)的語言；

4、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；

5、內(nèi)存的大?。?/p>

6、外存的大小；

7、機(jī)器執(zhí)行指令的速度；

8、其它。

而確定算法效率的方法通常有兩種：

1.6.1事后統(tǒng)計(jì)：

先實(shí)現(xiàn)算法，然后運(yùn)行程序，測算其時(shí)間和空間的消耗。缺點(diǎn)：

1、必須先依據(jù)算法編制程序并運(yùn)行程序，耗費(fèi)人力物力；

2、依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣。由于算法的運(yùn)行與計(jì)算機(jī)的軟硬件等環(huán)境因素有關(guān)，不容易發(fā)現(xiàn)算法本身的優(yōu)劣。同樣的算法用不同的編譯器編譯出的目標(biāo)代碼數(shù)量不同，完成算法所需的時(shí)間也不同；若計(jì)算機(jī)的存儲空間較小，算法運(yùn)行時(shí)間也就會延長；

3、沒有實(shí)際價(jià)值。測試花費(fèi)不少時(shí)間但并沒有解決現(xiàn)實(shí)中的實(shí)際問題。

1.6.2事前分析：

僅僅通過比較算法本身的復(fù)雜性來評價(jià)算法的優(yōu)劣，不考慮其它的軟硬件因素，通常考查算法所用的時(shí)間和所需的存儲空間。

算法復(fù)雜性的度量可以分為時(shí)間復(fù)雜度和空間復(fù)雜度。

1.6.3算法的時(shí)間復(fù)雜度(time complexity)

1、算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度用于度量一個(gè)算法所用的時(shí)間。

算法所用的時(shí)間主要包括程序編譯時(shí)間和運(yùn)行時(shí)間。由于一個(gè)算法一旦編譯成功可以多次運(yùn)行，因此可以忽略編譯時(shí)間，只討論算法的運(yùn)行時(shí)間。

算法的運(yùn)行時(shí)間依賴于加、減、乘、除、等基本的運(yùn)算以及參加運(yùn)算的數(shù)據(jù)量的大小，另外，與計(jì)算機(jī)硬件和操作環(huán)境等也有關(guān)系。要想準(zhǔn)確地估算時(shí)間是不可行的，而影響算法時(shí)間最為主要的因素是問題的規(guī)模，即輸入量的多少。同等條件下，問題的規(guī)模越大，算法所花費(fèi)的時(shí)間也就越長。例如，求1+2+3+?+n的算法，即n個(gè)整數(shù)的累加求和，這個(gè)問題的規(guī)模為n。因此，運(yùn)行算法所需的時(shí)間t是問題規(guī)模n的函數(shù)，記作t(n)。

同等條件下，相同或類似的基本操作在真正程序運(yùn)行過程中所花費(fèi)的時(shí)間也差不多，這樣，如果兩個(gè)不同算法中一個(gè)所含基本操作多而另一個(gè)所含基本操作少，則包含基本操作少的算法其花費(fèi)時(shí)間也就較少。因此，通常用算法中基本語句的執(zhí)行次數(shù)來作為度量算法速度快慢的依據(jù)，而這種度量時(shí)間復(fù)雜度的方法得出的不是時(shí)間量，而是一種增長趨勢的度量，即當(dāng)問題規(guī)模n增大時(shí)，t(n)也隨之變大。換言之，當(dāng)問題規(guī)模充分大時(shí)，算法中基本語句的執(zhí)行次數(shù)為在漸進(jìn)意義下的階，稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，通常用大o記號表示。用數(shù)學(xué)語言通常描述為：若當(dāng)且僅當(dāng)存在正整數(shù)n和n0，對于任意n≥n0，都有t(n)≤c×f(n)，則稱該算法的漸進(jìn)時(shí)間復(fù)雜度為t(n)=o(f(n))。

一般地，常用最內(nèi)層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示時(shí)間復(fù)雜度。

2、時(shí)間復(fù)雜度分析舉例： 例：兩個(gè)n階方陣的乘法。

云淡風(fēng)清 http:/// for(i=1;i<=n;++i)for(j=1;j<=n;++j){

c[i][j]=0;

for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j];} 分析：由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為： n×n×n=n3，時(shí)間復(fù)雜度為t(n)=o(n3)。

例： { ++x;s=0;} 分析：將x自增看成是基本操作，則語句頻度為1，即時(shí)間復(fù)雜度為o(1)。

如果將s=0也看成是基本操作，則語句頻度為2，其時(shí)間復(fù)雜度仍為o(1)，即常量階。只要t(n)不是問題規(guī)模n的函數(shù)，而是一個(gè)常數(shù)，它的時(shí)間復(fù)雜度則均為o(1)。例：以下程序段： for(i=1;i<=n;++i){ ++x;s+=x;} 分析：基本語句的語句頻度為：n，其時(shí)間復(fù)雜度為：o(n)，即為線性階。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){

++x;

s+=x;} 分析：基本語句的語句頻度為：n2，其時(shí)間復(fù)雜度為：o(n2)，即為平方階。

定理：若t(n)=amnm+am-1nm-1+?+a1n+a0是一個(gè)m次多項(xiàng)式，則t(n)=o(nm)，即復(fù)雜度表達(dá)式只取一個(gè)n趨向于無窮大時(shí)的同階無窮小表達(dá)式即可。

通過對算法復(fù)雜度的分析，總結(jié)出這樣一條結(jié)論，在計(jì)算任何算法的復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)，這樣可以簡化算法分析，并使注意力集中在增長率上。

從本質(zhì)上來講，此種策略也就是只考慮對算法復(fù)雜度影響最大的因素而忽略次要因素。例：以下程序段：

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

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

{

++x;

a[i,j]=x;

}

云淡風(fēng)清 http:/// 分析：基本語句的語句頻度為： 1+2+3+?+n-2 =(1+n-2)×(n-2)/2

=(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，時(shí)間復(fù)雜度為o(n2)，即此算法的時(shí)間復(fù)雜度為平方階。

一個(gè)算法時(shí)間復(fù)雜度為o(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)(即零次多項(xiàng)式)來界定。而一個(gè)時(shí)間為o(n2)的算法則由一個(gè)二次多項(xiàng)式來界定。

3、常見表示時(shí)間復(fù)雜度的階： o(1)：常量時(shí)間階 o(n)：線性時(shí)間階 o(㏒n)：對數(shù)時(shí)間階

o(n㏒n)：線性對數(shù)時(shí)間階 o(nk)：k≥2，k次方時(shí)間階

4、常見時(shí)間復(fù)雜度大小關(guān)系分析：

以下六種計(jì)算算法時(shí)間復(fù)雜度的多項(xiàng)式是最常用的，其大小關(guān)系通常為： o(1)

當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。

有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨輸入數(shù)據(jù)集的不同而不同。例：素?cái)?shù)的判斷算法。

void prime(int n)//n是一個(gè)正整數(shù) { int i=2;while((n%i)!=0 && i*1.0

i++;if(i*1.0>sqrt(n))

printf(“&d 是一個(gè)素?cái)?shù)n”,n);else

printf(“&d 不是一個(gè)素?cái)?shù)n”,n);} 此例中執(zhí)行頻率最高的語句為i++;，此語句最少執(zhí)行0次，最多執(zhí)行sqrt(n)次，對于不同的n，執(zhí)行次數(shù)不確定。

對于此類算法，如果輸入數(shù)據(jù)不同，則算法運(yùn)行時(shí)間也不同，因此要全面分析一個(gè)算法，需要考慮算法在最好、最壞、平均情況下的時(shí)間消耗。由于最好情況出現(xiàn)的概率太小，因此不具代表性，但是，當(dāng)最好情況出現(xiàn)的概率大時(shí)，應(yīng)該分析最好情況；雖然最壞情況出現(xiàn)的概率也太小，不具代表性，但是分析最壞情況能夠讓人們知道算法的運(yùn)行時(shí)間最壞能到什么程度，這一點(diǎn)在實(shí)時(shí)系統(tǒng)中很重要；分析平均情況是比較普遍的，特別是同一個(gè)算法要處理不同的輸入時(shí)，通常假定輸入的數(shù)據(jù)是等概率分布的。

例：冒泡排序法。

void bubble_sort(int a[],int n)

云淡風(fēng)清 http:/// { int temp;change=false;for(i=n-1;change=ture;i>1 && change;--i)

for(j=0;j

if(a[j]>a[j+1])

{

temp=a[j];

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

a[j+1]=temp;

change=ture;

} } 最好情況：0次

最壞情況：1+2+3+?+n-1=n(n-1)/2平均時(shí)間復(fù)雜度為：o(n2)1.6.4算法的空間復(fù)雜度(space complexity)

1、算法的空間復(fù)雜度

算法的空間復(fù)雜度是指在算法的執(zhí)行過程中需要的輔助空間數(shù)量。輔助空間數(shù)量指的不是程序指令、常數(shù)、指針等所需要的存儲空間，也不是輸入數(shù)據(jù)所占用的存儲空間，輔助空間是除算法本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時(shí)開辟的存儲空間。算法的空間復(fù)雜度分析方法同算法的時(shí)間復(fù)雜度相似，設(shè)s(n)是算法的空間復(fù)雜度，通常可以表示為：

s(n)=o(f(n))其中：n為問題的規(guī)模(或大小)。該存儲空間一般包括三個(gè)方面： 指令常數(shù)變量所占用的存儲空間； 輸入數(shù)據(jù)所占用的存儲空間； 輔助(存儲)空間。

一般地，算法的空間復(fù)雜度指的是輔助空間。如：

一維數(shù)組a[n]：空間復(fù)雜度o(n)二維數(shù)組a[n][m]：空間復(fù)雜度o(n*m)例：數(shù)組a中有10000個(gè)數(shù)，要求將所有數(shù)據(jù)逆置(即順序倒過來存放)。為達(dá)到逆置目的，有以下兩種方案： 方案一：

int a[10000],b[10000],i;for(i=0;i<10000;i++)b[10000-i-1]=a[i];for(i=0;i<10000;i++)a[i]=a[b];方案二：

int a[10000],t,i;for(i=0;i<10000/2;i++)

云淡風(fēng)清 http:/// { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明顯，方案二中的輔助空間數(shù)量為1，而方案一中的輔助空間數(shù)量為10000，方案二的空間復(fù)雜度優(yōu)于方案一。

在算法的時(shí)間復(fù)雜度和空間復(fù)雜度中，我們更注重算法的時(shí)間性能。因此，在對算法性能的分析當(dāng)中，通常均主要針對算法時(shí)間性能進(jìn)行分析。

1.6.5學(xué)習(xí)算法的原因

講述了這么多關(guān)于算法的基礎(chǔ)知識，究竟為什么要學(xué)習(xí)算法呢？

首先，算法無處不在。算法不僅出現(xiàn)在數(shù)學(xué)和計(jì)算機(jī)程序中，更普遍地出現(xiàn)在我們的生活中，在生活中做什么事情都要有一定的順序，然而不同的順序帶來的效率和成果可能都會不同，只有學(xué)好了算法，才能讓生活更有趣、更有效率。

其次，算法是程序的靈魂。學(xué)習(xí)計(jì)算機(jī)編程，必須要掌握好其靈魂，否則，寫出來的程序就像是沒有靈魂的軀體。

再次，算法是一種思想。掌握了這種思想，能夠拓展思維，使思維變得清晰、更具邏輯性，在生活以及編程上的很多問題，也就更易解決。

最后，算法的樂趣。學(xué)習(xí)算法不僅僅是為了讓它幫助人們更有效地解決各種問題，算法本身的趣味性很強(qiáng)，當(dāng)通過煩瑣的方法解決了一個(gè)問題后會感覺到有些疲憊，但是面對同一個(gè)問題，如若學(xué)會使用算法，更簡單有效地解決了這個(gè)問題，會發(fā)現(xiàn)很有成就感，算法的速度、思想會讓人覺得很奇妙。每一個(gè)奇妙的算法都是智慧的結(jié)晶。

學(xué)習(xí)算法的理由成千上萬，不同的人可能出于不同的目的去學(xué)習(xí)算法，希望大家能夠通過對課程的學(xué)習(xí)對算法有進(jìn)一步的理解。

習(xí)題一

1、簡要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型。

2、數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？

3、數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括哪些？

4、算法分析的目的是什么？算法分析的主要方面是什么？

云淡風(fēng)清 http:///

第2章 線性表

下表為某電臺提供給聽眾的若干首英文歌曲名及相關(guān)點(diǎn)播情況統(tǒng)計(jì)信息：

由于實(shí)際的歌曲庫可能很大，手工管理效率低，不方便，現(xiàn)請?jiān)O(shè)計(jì)一個(gè)軟件系統(tǒng)實(shí)現(xiàn)對此類歌曲庫的管理。

分析：

此例中相鄰的兩首歌之間是一種一對一的關(guān)系，屬于典型的線性結(jié)構(gòu)，可按線性結(jié)構(gòu)進(jìn)行組織及管理。

2.1線性結(jié)構(gòu)與線性表 2.1.1線性結(jié)構(gòu)

如果一個(gè)數(shù)據(jù)元素序列滿足：

⑴除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)數(shù)據(jù)元素和一個(gè)直接后繼數(shù)據(jù)元素；

⑵第一個(gè)數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素； ⑶最后一個(gè)數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。則稱這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。

線性表、棧、隊(duì)列、串和數(shù)組都屬于線性結(jié)構(gòu)。如下圖：

云淡風(fēng)清 http:/// 2.1.2線性表

線性表(linear list)是一種最簡單、最常用的線性結(jié)構(gòu)，是一種可以在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作的、由n(n≥0)個(gè)相同類型數(shù)據(jù)元素a1，a2，?，an組成的線性結(jié)構(gòu)。在這種結(jié)構(gòu)中：

⑴存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素； ⑵存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素； ⑶除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)； ⑷除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼。線性表中的數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表?？站€性表用符號()表示。

當(dāng)n>0時(shí)，將非空的線性表記作：(a1，a2，?an)，其中符號ai(1≤i≤n)表示第i個(gè)抽象數(shù)據(jù)元素。

a1稱為線性表的第一個(gè)(頭)結(jié)點(diǎn)，an稱為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。a1，a2，?ai-1都是ai(2≤i≤n)的前驅(qū)，其中ai-1是ai的直接前驅(qū)；

ai+1，ai+2，?an都是ai(1≤i ≤n-1)的后繼，其中ai+1是ai的直接后繼。

線性結(jié)構(gòu)是最常用、最簡單的數(shù)據(jù)結(jié)構(gòu)，而線性表是一種典型的線性結(jié)構(gòu)，其基本特點(diǎn)是可以在任意位置進(jìn)行插入和刪除等操作，且數(shù)據(jù)元素是有限的。

線性表可以用順序存儲結(jié)構(gòu)或鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)。用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的線性表稱為順序表，用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的線性表稱為鏈表。鏈表主要有單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表三種。順序表和鏈表各有優(yōu)缺點(diǎn)，并且優(yōu)缺點(diǎn)剛好相反，在實(shí)際應(yīng)用中要根據(jù)情況選擇對操作及性能有利的存儲結(jié)構(gòu)。

線性表中的數(shù)據(jù)元素ai所代表的具體含義隨實(shí)際應(yīng)用領(lǐng)域的不同而不同，在線性表的定義中，只不過是一個(gè)抽象的表示符號。

◆線性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例1：26個(gè)英文字母組成的字母表：(a，b，c、?、z)例2：某校從1978年到1983年各種型號的計(jì)算機(jī)擁有量的變化情況：(6，17，28，50，92，188)例3：一副撲克的點(diǎn)數(shù)：(2，3，4，?，j，q，k，a)◆線性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng)，每個(gè)項(xiàng)稱為結(jié)點(diǎn)的一個(gè)域。每個(gè)元素有一個(gè)可以唯一標(biāo)識每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱為關(guān)鍵字。

例4：某校2001級同學(xué)的基本情況：{(‘2001414101’，‘張里戶’，‘男’，06/24/1983)，(‘2001414102’，‘張化司’，‘男’，08/12/1984)?，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} ◆若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的?！艟€性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，其長度可根據(jù)需要增長或縮短。

◆對線性表的基本操作如下(實(shí)際應(yīng)用中要根據(jù)需要選擇相應(yīng)操作或者添加未列出的操作)： ⑴建立空表l ⑵返回表l的長度，即表中元素個(gè)數(shù) ⑶取線性表l中位置i處的元素(1≤i≤n)⑷取i的直接前驅(qū)元素 ⑸取i的直接后繼元素

⑹查詢元素x在l中的邏輯位置

⑺在線性表l的位置i處插入元素x，原位置元素后移一個(gè)位置 ⑻從線性表l中刪除位置i處的元素 ⑼判斷線性表是否為空 ⑽清空已存在的線性表 ⑾遍歷所有元素

云淡風(fēng)清 http:/// ⑿根據(jù)所給關(guān)鍵字查詢元素并返回其詳細(xì)信息 ⒀修改表中元素

⒁對所有元素按條件排序

2.1.3線性表的抽象數(shù)據(jù)類型定義

adt list { 數(shù)據(jù)對象：d = { ai | ai∈elemset, i=1,2,?,n, n≥0 } 數(shù)據(jù)關(guān)系：r = { | ai-1, ai∈d, i=2,3,?,n } 基本操作： initlist(&l)初始條件：無

操作結(jié)果：構(gòu)造一個(gè)空的線性表l； listlength(l)初始條件：線性表l已存在；

操作結(jié)果：返回線性表中的元素個(gè)數(shù)； getelem(l,i,e)初始條件：線性表l已存在，1≤i≤listlength(l)； 操作結(jié)果：用e返回l中第i個(gè)數(shù)據(jù)元素的值； listinsert(l,i,e)初始條件：線性表l已存在，1≤i≤listlength(l)+1，線性表未滿；

操作結(jié)果：在線性表l中的第i個(gè)位置插入元素e，原來位置及以后的元素都后移； listlocate(l,e)初始條件：線性表l已存在；

操作結(jié)果：返回元素e在l中的邏輯位置，不存在則返回0； listdelete(l,i)初始條件：線性表l已存在，1≤i≤listlength(l)； 操作結(jié)果：從表l中刪除位置i處的元素； listclear(l)初始條件：線性表l已存在； 操作結(jié)果：清空已存在的表； listtraverse(l)初始條件：線性表l已存在； 操作結(jié)果：遍歷輸出所有元素； listupdate(l,i,e)初始條件：線性表l已存在,1≤i≤listlength(l)； 操作結(jié)果：將線性表l中第i個(gè)位置的值置為e； listsort(l)初始條件：線性表l已存在；

操作結(jié)果：按一定條件對所有元素重新排序； listdestroy(l)初始條件：線性表l已存在； 操作結(jié)果：釋放線性表空間； …

云淡風(fēng)清 http:/// } adt list 2.2線性表的順序存儲 2.2.1線性表的順序存儲結(jié)構(gòu)

順序存儲：把線性表的結(jié)點(diǎn)按邏輯順序依次存入地址連續(xù)的一組存儲單元里。用這種方法存儲的線性表簡稱順序表。

順序存儲的線性表的特點(diǎn)：

◆線性表的邏輯順序與物理順序一致；

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來體現(xiàn)的。設(shè)有非空的線性表：(a1，a2，?an)。順序存儲如下圖所示。

在具體的機(jī)器環(huán)境下，設(shè)線性表的每個(gè)元素需占用len個(gè)存儲單元，以所占的第一個(gè)單元的存儲地址作為數(shù)據(jù)元素的存儲位置，則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲位置loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲位置loc(ai)之間滿足下列關(guān)系：

loc(ai+1)=loc(ai)+l 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲位置為： loc(ai)=loc(a1)+(i-1)*len 高級語言中同一個(gè)數(shù)組的各個(gè)元素占用連續(xù)存儲單元，具有隨機(jī)存取(指存取同一數(shù)組各元素的時(shí)間開銷相同，不受所處位置的限制)的特性，故而在高級語言中通常用數(shù)組來存儲順序表。除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該表示線性表的長度屬性以方便某些操作，所以用結(jié)構(gòu)體類型來定義順序表類型。

#include

#include

#define ok #define error

typedef int elemtype;//元素類型，可根據(jù)實(shí)際需要更改 typedef struct sqlist { elemtype *elem_array;//線性表存儲空間地址

int length;//線性表長度 } sqlist;注意：c語言中數(shù)組的下標(biāo)值是從0開始，第i個(gè)元素的下標(biāo)值是i-1。

2.2.2順序表的基本操作

順序存儲結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。

以下將對幾種主要的操作進(jìn)行討論。#include

#define ok #define error

typedef int elemtype;//元素類型，可根據(jù)實(shí)際需要更改 typedef struct sqlist { elemtype elem_array[max_size];//線性表存儲空間地址

int length;//線性表長度 } sqlist;/*

1、初始化

構(gòu)造一個(gè)空的線性表 */ status init_sqlist(sqlist *l){ l->length=0;return ok;} /*

2、測長度

返回線性表中的元素個(gè)數(shù) */ int length_sqlist(sqlist *l){ return l->length;} /*

3、取元素

用e返回l中第i個(gè)數(shù)據(jù)元素的值，1≤i≤listlength(l)*/ status get_sqlist(sqlist *l,int i,elemtype *e){ if((i>=1)&&(i<=l->length)){

*e=l->elem_array[i-1];//i位置對應(yīng)的元素下標(biāo)為i-1

return ok;} else

return error;}

云淡風(fēng)清 http:/// /*

4、順序線性表的插入

在線性表l中的第i個(gè)位置插入元素e，原來位置及以后的元素都后移。要求1≤i≤listlength(l)+1，線性表未滿。實(shí)現(xiàn)步驟：

(1)將線性表l中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。(2)將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。

(3)線性表長度加1。*/ status insert_sqlist(sqlist *l,int i,elemtype e){ int j;if((i<1)||(i>l->length+1))//位置錯(cuò)誤

return error;else

if(l->length>=max_size)//線性表上溢

//實(shí)際開發(fā)中達(dá)到空間上限時(shí)可用remalloc()函數(shù)重新分配空間，擴(kuò)大空間容量

return error;

else

{

//i-1位置以后的所有結(jié)點(diǎn)后移

for(j=l->length-1;j>=i-1;--j)

l->elem_array[j+1]=l->elem_array[j];

l->elem_array[i-1]=e;//在i-1位置插入結(jié)點(diǎn)

l->length++;//線性表長度增1

return ok;

} } /* 時(shí)間復(fù)雜度分析：

在線性表l中的第i個(gè)位置插入新結(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動操作上，因此，可用結(jié)點(diǎn)的移動來估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線性表l中的第i個(gè)位置插入結(jié)點(diǎn)的概率為pi，不失一般性，設(shè)各個(gè)位置插入是等概率，則pi=1/(n+1)，而插入時(shí)移動結(jié)點(diǎn)的次數(shù)為n-i+1。

總的平均移動次數(shù)：einsert=∑pi*(n-i+1)(1≤i≤n)計(jì)算得：einsert=n/2。

即在順序表上做插入運(yùn)算，平均要移動表上一半結(jié)點(diǎn)，當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為o(n)。

*/ /*

5、線性表元素位置查詢

返回元素e在l中的邏輯位置，不存在則返回0

云淡風(fēng)清 http:/// */ int locate_sqlist(sqlist *l,elemtype e){ int i,found=0;//found用于表示是否找到，0：未找到 1：找到

i=0;//從第一個(gè)開始查詢

while((i

length)&&(found==0))

found=1;

else

i++;if(found==1)

return i+1;//返回邏輯位置編號

else

return 0;//未找到，返回0 } /*

6、刪除指定位置元素 在線性表：

l=(a1，?ai-1，ai，ai+1，?，an)中刪除結(jié)點(diǎn)ai(1≦i≦n)，使其成為線性表： l=(a1，?ai-1，ai+1，?，an)要求1≤i≤listlength(l)，線性表未空。實(shí)現(xiàn)步驟：

(1)將線性表l中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移動一個(gè)位置。(2)線性表長度減1。*/ status delete_sqlist(sqlist *l,int i){ int k;if(l->length==0)//線性表空

{

printf(“線性表l為空!n”);

return error;} else

if(i<1||i>l->length)//指定位置不合適

{

printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n”);

return error;

}

else

{

//i位置以后的所有結(jié)點(diǎn)前移

for(k=i;k

length;k++)

云淡風(fēng)清 http:///

l->length--;//線性表長度減1

return(ok);

} } /* 時(shí)間復(fù)雜度分析：

刪除線性表l中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動操作上，因此，可用結(jié)點(diǎn)的移動來估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線性表l中刪除第i個(gè)元素的概率為pi，不失一般性，設(shè)刪除各個(gè)位置是等概率，則pi=1/n，而刪除時(shí)移動結(jié)點(diǎn)的次數(shù)為n-i。

則總的平均移動次數(shù)：edelete=∑pi*(n-i)

(1≤i≤n)計(jì)算得：edelete=(n-1)/2 即在順序表上做刪除運(yùn)算，平均要移動表上一半結(jié)點(diǎn)，當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)停虼怂惴ǖ钠骄鶗r(shí)間復(fù)雜度為o(n)。

*/ /*

7、清空 */ status clear_sqlist(sqlist *l){ l->length=0;return ok;} /*

8、遍歷 以輸出為例 */ status traverse_sqlist(sqlist *l){ int i;printf(“共有%d個(gè)元素，以下為具體內(nèi)容：n”,l->length);for(i=0;i

length;i++)

9、修改

將線性表l中第i個(gè)位置的值置為e。要求線性表l已存在且1≤i≤listlength(l)。*/ status update_sqlist(sqlist *l,int i,elemtype e){ if((i<1)||(i>l->length))//位置錯(cuò)誤

云淡風(fēng)清 http:///

return error;else {

l->elem_array[i-1]=e;//放置新數(shù)據(jù)

return ok;} } /*

10、排序

按要求對線性表中元素排序。*/ status sort_sqlist(sqlist *l){ int i,j;elemtype temp;for(i=1;i<=l->length-1;i++)

for(j=0;j<=l->length-i-1;j++)

{

if(l->elem_array[j]

elem_array[j+1])

temp=l->elem_array[j];

l->elem_array[j]=l->elem_array[j+1];

l->elem_array[j+1]=temp;

}

} return ok;} /* 主函數(shù) */ void main(){ int xz=1,i;sqlist l;elemtype e;while(xz!=0){

printf(“

1、初始化n

2、測長度n

3、取元素n

4、插入n

5、查詢n

6、刪除n

7、清空n

8、遍歷n

9、修改n10、排序n 0、結(jié)束n請選擇：”);

scanf(“%d”,&xz);

switch(xz)

{

case 1:

if(init_sqlist(&l)==ok)

云淡風(fēng)清 http:///

printf(“初始化成功！n”);else

printf(“初始化未成功！n”);break;case 2: printf(“線性表長度為：%dn”,length_sqlist(&l));break;case 3: printf(“請輸入要取元素的位置：”);scanf(“%d”,&i);if(get_sqlist(&l,i,&e)==ok)

printf(“指定位置上的元素為：%dn”,e);else

printf(“error！n”);break;case 4: printf(“請輸入要插入的位置：”);scanf(“%d”,&i);printf(“請輸入要插入的元素內(nèi)容：n”);scanf(“%d”,&e);if(insert_sqlist(&l,i,e)==ok)

printf(“插入成功n”);else

printf(“error！n”);break;case 5: printf(“請輸入要查詢的元素內(nèi)容：”);scanf(“%d”,&e);printf(“此元素邏輯位置為：%d(0表示未找到)。n”,locate_sqlist(&l,e));break;case 6: printf(“請輸入要?jiǎng)h除元素的位置：”);scanf(“%d”,&i);if(delete_sqlist(&l,i)==ok)

printf(“刪除成功n”);else

printf(“error！n”);break;case 7: clear_sqlist(&l);break;case 8: traverse_sqlist(&l);break;

云淡風(fēng)清 http:///

case 9:

printf(“請輸入要修改的元素位置：”);

scanf(“%d”,&i);

printf(“請輸入元素的新內(nèi)容：n”);

scanf(“%d”,&e);

if(update_sqlist(&l,i,e)==ok)

printf(“修改成功n”);

else

printf(“error！n”);

break;

case 10:

sort_sqlist(&l);

printf(“排序完成！n”);

break;

case 0:

printf(“謝謝使用，再見！n”);

break;

default:

printf(“輸入錯(cuò)誤！n”);

break;

} } } 需要說明的是，本例沒有實(shí)現(xiàn)空間的動態(tài)分配，若要實(shí)現(xiàn)動態(tài)分配，可參照第三章“棧的動態(tài)順序存儲結(jié)構(gòu)”的做法。

2.2.3順序存儲線性表的特點(diǎn)

優(yōu)點(diǎn)：表中任意一個(gè)結(jié)點(diǎn)的存取很方便，可以進(jìn)行隨機(jī)存取，處于不同位置上的結(jié)點(diǎn)的存取時(shí)間從理論上來說相同，也能進(jìn)行插入和刪除操作。

缺點(diǎn)：

(1)插入和刪除不方便。為保持連續(xù)存放，操作中需要移動大量元素。

(2)會造成空間的浪費(fèi)以及不易擴(kuò)充。所占空間通常情況下大小固定，處理長度變化較大的線性表時(shí)，分配空間大小不夠，會造成溢出；分配空間太大，會造成浪費(fèi)。

2.3線性表的鏈?zhǔn)酱鎯?2.3.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈?zhǔn)酱鎯Γ河靡唤M任意(即不必要連續(xù))的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。

鏈表中結(jié)點(diǎn)所占用的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的，鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。

為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲指示其直接后繼結(jié)點(diǎn)的

云淡風(fēng)清 http:/// 地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，如下圖所示。

data：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。

next：指針域，存放結(jié)點(diǎn)的直接后繼的地址。

鏈表通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起。每一個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的鏈表，稱為單鏈表。

為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭指針變量head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息(或存放鏈表長度等輔助信息)，此時(shí)通常稱為帶頭結(jié)點(diǎn)的單鏈表。當(dāng)然，也可以讓頭結(jié)點(diǎn)的數(shù)據(jù)域存放有效數(shù)據(jù)，此時(shí)稱為不帶頭結(jié)點(diǎn)的單鏈表。相對而言，帶頭結(jié)點(diǎn)的單鏈表浪費(fèi)了一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域，但會給編程帶來一定方便。

帶頭結(jié)點(diǎn)的單鏈表其基本結(jié)構(gòu)如下：

說明：

(1)整個(gè)鏈表由若干個(gè)結(jié)點(diǎn)組成，一個(gè)結(jié)點(diǎn)占用一個(gè)內(nèi)存塊，而每個(gè)結(jié)點(diǎn)又分為兩大部分：數(shù)據(jù)域和指針域，其中數(shù)據(jù)域存放用戶數(shù)據(jù)，指針域用于存放后一個(gè)結(jié)點(diǎn)的地址，通過指針域?qū)⑦壿嬌锨昂笙噜彽慕Y(jié)點(diǎn)連接起來，這樣，通過前一個(gè)結(jié)點(diǎn)指針域中存放的地址就可以找到后一個(gè)結(jié)點(diǎn)?？煽闯?，每個(gè)結(jié)點(diǎn)的指針域?qū)嶋H上充當(dāng)了指針變量的角色，只要結(jié)點(diǎn)數(shù)可變，則意味著指針變量數(shù)也可變，而事實(shí)上結(jié)點(diǎn)所對應(yīng)的這些內(nèi)存塊完全可以多次動態(tài)分配，這也就意味著指針域(相當(dāng)于指針變量)的個(gè)數(shù)可以根據(jù)需要?jiǎng)討B(tài)調(diào)整，這就解決了前述的“程序中變量個(gè)數(shù)固定，但問題本身所需變量個(gè)數(shù)不定”的矛盾。

(2)設(shè)置一個(gè)頭指針變量指向首結(jié)點(diǎn)，在帶頭結(jié)點(diǎn)的單鏈表中，此結(jié)點(diǎn)不存放有效數(shù)據(jù)。(3)末尾結(jié)點(diǎn)的指針域設(shè)置為空“null”表示鏈表的結(jié)束，相當(dāng)于字符串中的''。

(4)在沒有用戶數(shù)據(jù)的情況下，此鏈表只有一個(gè)結(jié)點(diǎn)，此結(jié)點(diǎn)既是首結(jié)點(diǎn)，又是末結(jié)點(diǎn)，結(jié)點(diǎn)的指針域?yàn)椤皀ull”，此時(shí)表示鏈表為邏輯“空”，也就是說，鏈表的初始狀態(tài)應(yīng)該如下圖所示。

單鏈表是由表頭唯一確定的，因此單鏈表可以用頭指針的名字來命名。例

1、線性表l=(bat，cat，eat，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲方式如下圖所示。

云淡風(fēng)清 http:///

1、結(jié)點(diǎn)的描述與實(shí)現(xiàn)

c語言中用帶指針的結(jié)構(gòu)體類型來描述 typedef int elemtype;typedef struct lnode { elemtype

data;//數(shù)據(jù)域，保存結(jié)點(diǎn)的值

struct

lnode *next;//指針域，保存后繼結(jié)點(diǎn)地址 }lnode;

//結(jié)點(diǎn)的類型

2、結(jié)點(diǎn)空間分配及回收的實(shí)現(xiàn)

結(jié)點(diǎn)存儲空間是通過動態(tài)內(nèi)存分配和釋放來實(shí)現(xiàn)的，即需要時(shí)分配，不需要時(shí)釋放。在c語言中可通過標(biāo)準(zhǔn)函數(shù)：malloc()，realloc()，sizeof()，free()等來實(shí)現(xiàn)分配。

動態(tài)分配：p=(lnode*)malloc(sizeof(lnode));函數(shù)malloc分配了一個(gè)類型為lnode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。動態(tài)釋放：free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。p必須是最近一次調(diào)用malloc()函數(shù)時(shí)的返回值。動態(tài)重新分配：p=(lnode*)realloc(p,newsize);先判斷當(dāng)前的指針是否有足夠的連續(xù)空間，如果有，擴(kuò)大p指向的地址，并且將p返回，如果空間不夠，先按照newsize指定的大小分配空間，將原有數(shù)據(jù)從頭到尾拷貝到新分配的內(nèi)存區(qū)域，而后釋放原來p所指內(nèi)存區(qū)域，同時(shí)返回新分配的內(nèi)存區(qū)域的首地址，即重新分配存儲器塊的地址。返回值：如果重新分配成功則返回指向被分配內(nèi)存的指針，否則返回空指針null。

3、最常用的基本操作 ⑴ 結(jié)點(diǎn)的賦值 lnode *p;p=(lnode*)malloc(sizeof(lnode));p->data=20;p->next=null;講課時(shí)板書教案上的幾種常見的指針操作。效果如下圖。

⑵常見的指針操作 ①q=p;

云淡風(fēng)清 http:/// ②q=p->next;

③p=p->next;

④q->next=p;

⑤q->next=p->next;

云淡風(fēng)清 http:///

2.3.2單鏈?zhǔn)降幕静僮?/p>

以帶頭結(jié)點(diǎn)的單鏈表為例。#define ok #define error

-1 typedef int status;//狀態(tài) #include “stdlib.h” #include “stdio.h” typedef int elemtype;typedef struct lnode { elemtype

data;//數(shù)據(jù)域，保存結(jié)點(diǎn)的值

struct

lnode *next;//指針域，保存后繼結(jié)點(diǎn)地址 }lnode;

//結(jié)點(diǎn)的類型

/*

1、鏈表初始化(建立空鏈表)*/ lnode * init_linklist(void){ lnode *l;l=(lnode *)malloc(sizeof(lnode));//給頭結(jié)點(diǎn)分配空間

if(l!=null)

l->next=null;//指針域置為空以作為結(jié)束標(biāo)記

return l;} /*

2、頭插入法建表

從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止，每次插入的結(jié)點(diǎn)都作為鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。

*/

云淡風(fēng)清 http:/// status create1_linklist(lnode *l){ elemtype data;char sfjx=1;//0：結(jié)束 1：繼續(xù)

lnode *p;while(sfjx!=0){

p=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間

if(p==null)

return error;//空間分配不成功

else

{

printf(“請輸入元素內(nèi)容：”);

scanf(“%d”,&data);//讀入值

p->data=data;//數(shù)據(jù)域賦值

//鉤鏈，新創(chuàng)建的結(jié)點(diǎn)總是作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

p->next=l->next;

l->next=p;

}

printf(“是否繼續(xù)(0：結(jié)束 1：繼續(xù))：”);

scanf(“%d”,&sfjx);} return ok;} /*

3、尾插入法建表

頭插入法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。

該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，使其成為當(dāng)前鏈表的尾結(jié)點(diǎn)。*/ status create2_linklist(lnode *l){ elemtype data;char sfjx=1;//0：結(jié)束 1：繼續(xù)

lnode *p,*q;//找到已有鏈表的末結(jié)點(diǎn)

q=l;while(q->next!=null)

q=q->next;while(sfjx!=0){

p=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間

if(p==null)

云淡風(fēng)清 http:///

return error;//空間分配不成功

else

{

printf(“請輸入元素內(nèi)容：”);

scanf(“%d”,&data);//讀入值

p->data=data;//數(shù)據(jù)域賦值

//鉤鏈，新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)

q->next=p;

q=p;//q重新指向末結(jié)點(diǎn)

}

printf(“是否繼續(xù)(0：結(jié)束 1：繼續(xù))：”);

scanf(“%d”,&sfjx);} q->next=null;//重設(shè)鏈表結(jié)束標(biāo)記

return(ok);} /*

4、按序號查找，取單鏈表中的第i個(gè)元素。

對于單鏈表，不能象順序表中那樣直接按序號i訪問結(jié)點(diǎn)，而只能從鏈表的頭結(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。

設(shè)單鏈表的長度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。*/ status get_linklist(lnode *l,int i,elemtype *e){

int j=1;lnode *p;p=l->next;//使p指向第一個(gè)結(jié)點(diǎn)

while((p!=null)&&(j

p=p->next;//移動指針p

j++;

//j計(jì)數(shù)

} if(p==null)//找不到

return(error);else {

*e=p->data;

return(ok);} } /*

云淡風(fēng)清 http:///

5、按值查找

按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)? 若有，則返回首次找到的值為key的結(jié)點(diǎn)的存儲位置；否則返回null。

*/ lnode *locate_linklist(lnode *l,elemtype key){ lnode *p;p=l->next;while((p!=null)&&(p->data!=key))

p=p->next;if(p!=null)//找到了

return p;else//找不到

return(null);} /*

6、單鏈表的插入，插入到指定位置

在以l為頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn)。

插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點(diǎn)p，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q，q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。

*/ status insert_linklist(lnode *l,int i,elemtype e){ int j=0;lnode *p,*q;p=l;//找待插入位置的前一個(gè)結(jié)點(diǎn)位置

while((p!=null)&&(j

p=p->next;

j++;} if((j!=i-1)||(p==null))//位置不合適

{

printf(“位置不合適，無法插入！n”);

return error;} else {

q=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間

if(q==null)

return error;

else

云淡風(fēng)清 http:///

{

//實(shí)現(xiàn)插入

q->data=e;

q->next=p->next;

p->next=q;

return ok;

} } } /*

7、按序號刪除

刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。

為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲地址。該存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1的存儲位置p，然后令p->next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲池”。設(shè)單鏈表長度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≤i≤n時(shí)是合法的。則當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，是終端結(jié)點(diǎn)。故判斷條件之一是p->next!=null。顯然此算法的時(shí)間復(fù)雜度也是o(n)。

*/ status delete1_linklist(lnode *l,int i){ int j=1;lnode *p,*q;p=l;q=l->next;//找待刪除位置的前一個(gè)結(jié)點(diǎn)位置

while(q!=null && j

p=q;

q=q->next;

j++;} if((q==null)||(i<=0)){

printf(“位置不合適，無法刪除！n ”);

return error;} else {

//實(shí)現(xiàn)刪除

p->next=q->next;

free(q);

return ok;} }

云淡風(fēng)清 http:/// /*

8、按值刪除

刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。

與按值查找相類似，首先要查找值為key的結(jié)點(diǎn)是否存在? 若存在，則刪除；否則返回null。*/ status delete2_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//找待刪除結(jié)點(diǎn)位置，q指向其位置，p指向其前驅(qū)結(jié)點(diǎn)

while(q!=null && q->data!=key){

p=q;

q=q->next;} if(q!=null)//找到了

{

//實(shí)現(xiàn)刪除

p->next=q->next;

free(q);

return ok;} else {

printf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在！n”);

return error;} } /*

9、刪除單鏈表中值為key的所有結(jié)點(diǎn)

與按值查找相類似，但比前面的算法更簡單。

基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始，對每個(gè)結(jié)點(diǎn)進(jìn)行檢查，若結(jié)點(diǎn)的值為key，則刪除之，然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。

*/ void delete3_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//p始終指向q的前驅(qū)，以方便刪除操作的實(shí)現(xiàn)

while(q!=null){

if(q->data==key)

{

p->next=q->next;

云淡風(fēng)清 http:///

free(q);

q=p->next;

}

else

{

p=q;

q=q->next;

} } } /*

10、刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)，使得所有結(jié)點(diǎn)的值都不相同 與按值查找相類似，但比前面的算法更復(fù)雜。

基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始，對每個(gè)結(jié)點(diǎn)進(jìn)行檢查：檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，只要有值和該結(jié)點(diǎn)的值相同，則刪除之；然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。

*/ void delete4_linklist(lnode *l){ lnode *p=l->next,*q,*ptr;while(p!=null)//檢查鏈表中所有結(jié)點(diǎn)

{

q=p;

ptr=p->next;

while(ptr!=null)//檢查結(jié)點(diǎn)p的所有后繼結(jié)點(diǎn)ptr

{

if(ptr->data==p->data)

{

q->next=ptr->next;

free(ptr);

ptr=q->next;

}

else

{

q=ptr;

ptr=ptr->next;

}

}

p=p->next;} } /*

云淡風(fēng)清 http:///

11、修改指定位置的數(shù)據(jù) */ status modify_linklist(lnode *l,int i,elemtype e){ int j=1;lnode *p;p=l->next;//找待修改結(jié)點(diǎn)位置

while(p!=null && j

p=p->next;

j++;} if((p==null)||(i<=0))//找不到

{

printf(“位置不合適，無法修改！n ”);

return error;} else {

p->data=e;

return ok;} } /*

12、單鏈表遍歷 以輸出為例 */ void traverse_linklist(lnode *l){ lnode *p;p=l->next;while(p!=null){

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

p=p->next;} printf(“n”);} /*

13、單鏈表的合并

設(shè)有兩個(gè)有序的單鏈表，它們的頭指針分別是la、lb，將它們合并為以lc為頭指針的有序鏈表。算法說明：算法中pa，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，pc是合并過程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。

云淡風(fēng)清 http:///

合并了值為-7，-2的結(jié)點(diǎn)后示意圖如下圖所示。

*/ lnode *merge_linklist(lnode *la,lnode *lb){ lnode *lc,*pa,*pb,*pc,*ptr;lc=la;pc=la;//指向新鏈表的末結(jié)點(diǎn)

pa=la->next;pb=lb->next;while(pa!=null && pb!=null){

if(pa->data

data)//將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else

if(pa->data>pb->data)//將pb所指的結(jié)點(diǎn)合并，pb指向下一個(gè)結(jié)點(diǎn)

{

pc->next=pb;

pc=pb;

pb=pb->next;

云淡風(fēng)清 http:///

}

else//將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除

{

pc->next=pa;

pc=pa;

pa=pa->next;

ptr=pb;

pb=pb->next;

free(ptr);

} } //將剩余的結(jié)點(diǎn)鏈上

if(pa!=null)

pc->next=pa;else

pc->next=pb;

free(lb);return(lc);} /*

14、單鏈表的排序

采用插入排序方法，以升序?yàn)槔?*/ void sort_linklist(lnode *l){ lnode *p,*q,*r,*s;p=l->next;l->next=null;while(p!=null){

q=l->next;

r=l;

while((q!=null)&&(p->data>q->data))

{

q=q->next;

r=r->next;

}

s=p->next;

r->next=p;

p->next=q;

p=s;} }

云淡風(fēng)清 http:/// /*

15、單鏈表的釋放 */ void release_linklist(lnode *l){ lnode *p,*q;p=l;//指向頭結(jié)點(diǎn)，從此結(jié)點(diǎn)開始釋放

while(p!=null){

q=p->next;

free(p);

p=q;} } void main(){ int xz=1,i;lnode *l,*l1,*l2;elemtype e;while(xz!=0){

printf(“

1、鏈表初始化n

2、頭插入法建表n

3、尾插入法建表n

4、按序號查找n

5、按值查找n

6、單鏈表的插入n”);

printf(“

7、按序號刪除n

8、按值刪除n

9、刪除單鏈表中指定值的所有結(jié)點(diǎn)n10、刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)n”);

printf(“

11、修改指定位置的數(shù)據(jù)n12、單鏈表遍歷n13、單鏈表的合并n14、單鏈表的排序n15、單鏈表的釋放n 0、結(jié)束n請選擇：”);

scanf(“%d”,&xz);

switch(xz)

{

case 1:

l=init_linklist();

if(l!=null)

printf(“初始化成功！n”);

break;

case 2:

if(create1_linklist(l)==ok)

printf(“建立成功！n”);

else

printf(“建立不成功！n”);

break;

case 3:

if(create2_linklist(l)==ok)

printf(“建立成功！n”);

云淡風(fēng)清 http:///

else

printf(“建立不成功！n”);break;case 4: printf(“請輸入要查找元素的序號：”);scanf(“%d”,&i);if(get_linklist(l,i,&e)==ok)

printf(“%dn”,e);else

printf(“找不到！n”);break;case 5: printf(“請輸入要查找元素的關(guān)鍵字：”);scanf(“%d”,&e);l1=locate_linklist(l,e);if(l1!=null)

printf(“%dn”,l1->data);else

printf(“找不到！n”);break;case 6: printf(“請輸入要插入元素的內(nèi)容：”);scanf(“%d”,&e);printf(“請輸入插入位置：”);scanf(“%d”,&i);if(insert_linklist(l,i,e)==ok)

printf(“插入成功！n”);else

printf(“插入不成功！n”);break;case 7: printf(“請輸入要?jiǎng)h除元素的位置：”);scanf(“%d”,&i);if(delete1_linklist(l,i)==ok)

printf(“成功刪除！n”);else

printf(“未成功刪除！n”);break;case 8: printf(“請輸入要元素的內(nèi)容：”);scanf(“%d”,&e);if(delete2_linklist(l,e)==ok)

printf(“成功刪除！n”);else

云淡風(fēng)清 http:///

printf(“未成功刪除！n”);break;case 9: printf(“請輸入要元素的內(nèi)容：”);scanf(“%d”,&e);delete3_linklist(l,e);printf(“成功刪除！n”);break;case 10: delete4_linklist(l);printf(“成功刪除！n”);

break;case 11: printf(“請輸入修改位置：”);scanf(“%d”,&i);printf(“請輸入元素的新內(nèi)容：”);scanf(“%d”,&e);if(modify_linklist(l,i,e)==ok)

printf(“修改成功！n”);else

printf(“修改不成功！n”);break;case 12: traverse_linklist(l);

break;case 13: l1=init_linklist();l2=init_linklist();if((l1==null)||(l2==null))

printf(“初始化不成功！n”);else {

printf(“請建立第一個(gè)鏈表：n”);

create2_linklist(l1);

printf(“請建立第二個(gè)鏈表：n”);

create2_linklist(l2);

sort_linklist(l1);

sort_linklist(l2);

l=merge_linklist(l1,l2);

printf(“合并后的結(jié)果如下：n”);

traverse_linklist(l);} break;case 14:

云淡風(fēng)清 http:///

}

} sort_linklist(l);break;case 15: release_linklist(l);

break;case 0: printf(“謝謝使用，再見！n”);break;default: printf(“輸入錯(cuò)誤！n”);break;} 2.4循環(huán)鏈表

循環(huán)鏈表(circular linked list)：是一種頭尾相接的鏈表，其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)，這樣，從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。

下圖是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖。

循環(huán)鏈表的操作：

對于帶頭結(jié)點(diǎn)的單循環(huán)鏈表，除鏈表的合并外，其它操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎(chǔ)上做以下簡單修改：

1、判斷是否是空鏈表 head->next==head;

2、判斷是否是表尾結(jié)點(diǎn) p->next==head;例：有m個(gè)人圍成一圈，順序排號。從第一個(gè)人開始報(bào)數(shù)，凡報(bào)到3的人退出圈子，問最后留下的那位是原來的第幾號？

根據(jù)問題描述可知，該問題中m個(gè)人圍坐在一起形成首尾相接的環(huán)，比較自然的一種思路是用循環(huán)鏈表模擬這個(gè)環(huán)。從第3個(gè)人開始出圈，相當(dāng)于從鏈表中刪除一個(gè)結(jié)點(diǎn)。該程序主要由三個(gè)模塊組成：

1、建立循環(huán)單鏈表存放初始各人編號；

2、報(bào)數(shù)并按順序輸出出圈人的編號；

3、輸出剩下的人的編號。具體步驟如下：

云淡風(fēng)清 http:/// 第一步：輸入人員總數(shù)；

第二步：創(chuàng)建循環(huán)鏈表并向單鏈表中填入人員編號； 第三步：找第一個(gè)開始報(bào)數(shù)的人；

第四步：數(shù)到3讓此人出圈(刪除對應(yīng)結(jié)點(diǎn))；

第五步：接著開始報(bào)數(shù)，重復(fù)第四步，直到圈中剩余一個(gè)為止； 第六步：輸出剩下結(jié)點(diǎn)中的編號，即為最終所要求的編號。程序源代碼： #include “stdio.h” #include “stdlib.h” #define maxn 100 //最大個(gè)數(shù) struct node { int data;struct node *next;};void main(){ struct node *head, *s, *q, *t;int n, m, count=0, i;do//輸入總個(gè)數(shù)

{ printf(“請輸入總個(gè)數(shù)(1－%d)：”,maxn);scanf(“%d”,&m);}while((m<1)||(m>maxn));do//輸入出圈時(shí)要數(shù)到的個(gè)數(shù)

{ printf(“要數(shù)到的個(gè)數(shù)(1--%d)：”,m);scanf(“%d”,&n);}while((n<1)||(n>m));for(i=0;i

{ s=(struct node *)malloc(sizeof(struct node));s->data=i+1;s->next=null;if(i==0){ head=s;q=head;} else

{ q->next=s;q=q->next;}

云淡風(fēng)清 http:/// } q->next=head;//形成圈

//以下代碼輸出原始狀態(tài)

printf(“原始狀態(tài)：n”);q=head;while(q->next!=head){ printf(“%4d”,q->data);q=q->next;} printf(“%4dn”,q->data);q=head;//以下代碼實(shí)現(xiàn)出圈

printf(“出圈順序：n”);do { count++;if(count==n-1){ t=q->next;q->next=t->next;count=0;printf(“%4d”,t->data);free(t);} q=q->next;}while(q->next!=q);printf(“n剩下的是%4dn”,q->data);} 注意：此程序采用的是不帶頭結(jié)點(diǎn)的單鏈表，以免在循環(huán)鏈表中由于不存放有效數(shù)據(jù)的頭結(jié)點(diǎn)的存在而影響計(jì)數(shù)。

2.5雙向鏈表

雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。單鏈表只

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

《數(shù)據(jù)結(jié)構(gòu)》教案

課程性質(zhì)和任務(wù)

本課程是計(jì)算機(jī)專業(yè)的主要專業(yè)基礎(chǔ)課程之一。本課程的參考教學(xué)時(shí)數(shù)為54學(xué)時(shí)，實(shí)際講課學(xué)時(shí)為35，實(shí)驗(yàn)學(xué)時(shí)為16。其主要內(nèi)容包括順序表、鏈表、棧、隊(duì)、串、樹和圖的結(jié)構(gòu)，以及查找和排序技術(shù)。通過本課程的教學(xué)，使學(xué)生理解計(jì)算機(jī)軟件系統(tǒng)所必須的數(shù)據(jù)結(jié)構(gòu)及算法的內(nèi)部邏輯，掌握在軟件工程中大量存在的查找和排序技術(shù)，并通過大量的上機(jī)實(shí)習(xí)，實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的算法，以便為后續(xù)課程的學(xué)習(xí)提供專業(yè)基礎(chǔ)知識，同時(shí)增強(qiáng)學(xué)生編制程序的能力。

課程教學(xué)目標(biāo)

通過本課程的學(xué)習(xí)，應(yīng)達(dá)到以下目標(biāo)：

? 深刻理解數(shù)據(jù)結(jié)構(gòu)中線性表、棧、隊(duì)和鏈的概念、算法及其基本應(yīng)用。

? 理解樹的基本概念，學(xué)會建立二叉樹，并在二叉樹上進(jìn)行查找、插入和刪除等各種運(yùn)算。

? 理解圖的基本結(jié)構(gòu)和算法，了解圖的路徑問題。

? 熟練掌握幾種重要的內(nèi)部排序和查找技術(shù)，了解外部排序的一般過程。

? 能熟練地運(yùn)用c語言，準(zhǔn)確、清晰地編制與本課程有關(guān)的算法，并能上機(jī)調(diào)試通過。

新疆農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)課程教案

第一講 緒論(對應(yīng)教材p1—p17)

一、教學(xué)目的和要求

要求掌握數(shù)據(jù)結(jié)構(gòu)中基本概念的定義，理解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容，了解抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)，理解算法評價(jià)的兩個(gè)指標(biāo)。

二、授課主要內(nèi)容

1.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 2.數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念

3.算法的概念、描述方法以及評價(jià)標(biāo)準(zhǔn)

三、教學(xué)重點(diǎn)難點(diǎn)

數(shù)據(jù)結(jié)構(gòu)中的基本概念、算法的概念、描述方法以及評價(jià)標(biāo)準(zhǔn)

四、授課內(nèi)容和方法

【口述】當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)：所處理的數(shù)據(jù)量大且具有一定的關(guān)系；對其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對其進(jìn)行組織、管理和檢索。

一、什么是數(shù)據(jù)結(jié)構(gòu)

我們大家知道許多非數(shù)值計(jì)算問題的數(shù)學(xué)模型常常是數(shù)學(xué)方程，如線性方程組、微分方程。所以這類非數(shù)值計(jì)算問題的解決就歸結(jié)于對數(shù)學(xué)模型設(shè)計(jì)算法、編寫程序。然而在現(xiàn)實(shí)社會中存在著許多非數(shù)值計(jì)算問題，其數(shù)學(xué)模型難以用數(shù)學(xué)方程描述。

1、舉例說明

? 圖書館的書目檢索自動化問題----計(jì)算機(jī)處理的對象之間存在著線性關(guān)系，稱為線性的數(shù)據(jù)結(jié)構(gòu)。

? 人機(jī)對奕問題----計(jì)算機(jī)處理的對象是一個(gè)個(gè)格局。所有可能出現(xiàn)的格局是一棵倒置的樹。

? 多岔路口交通燈的管理問題----數(shù)學(xué)模型是圖的數(shù)學(xué)結(jié)構(gòu)。

【由以上舉例引出下列結(jié)論：】

非數(shù)值計(jì)算問題的數(shù)學(xué)模型是表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。【總結(jié)出定義】 數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對象以及它們之間關(guān)系和操作的一門學(xué)科。（三個(gè)要素：對象、關(guān)系及操作（運(yùn)算））

2、《數(shù)據(jù)結(jié)構(gòu)》課程的介紹

1968年美國克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系： 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作。

數(shù)據(jù)結(jié)構(gòu)是一門綜合性的專業(yè)課程，是一門介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件之間的一門核心課程。是設(shè)計(jì)和實(shí)現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)。

二、基本概念和術(shù)語

1、數(shù)據(jù) 數(shù)據(jù)：是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。是計(jì)算機(jī)

加工的“原料”。

數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。

數(shù)據(jù)項(xiàng):有時(shí)，一個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。

2、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

data_structure=(d,s)其中，d 是數(shù)據(jù)元素的有限集，s 是d上關(guān)系的有限集。

例：復(fù)數(shù) complex=(c,r)例：課題小組 group=(p,r)p={t,g1,?,gn,s11,?,snm}1≤n≤3，1≤m≤2，r={r1,r2} r1={

|1≤i≤n, 1≤n≤3,} r2={

|1≤i≤n, 1≤j≤m,1≤m≤2,} 數(shù)據(jù)結(jié)構(gòu)一般包括三方面的內(nèi)容：

② 存儲結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器的表示。用于表示數(shù)據(jù)元素的位串稱之為元素或結(jié)點(diǎn)。用于表示數(shù)據(jù)項(xiàng)的位串稱之為數(shù)據(jù)域。

③ 數(shù)據(jù)的運(yùn)算：對數(shù)據(jù)施加的操作。

算法的設(shè)計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。

3、數(shù)據(jù)的兩種存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)：把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。通常順序存儲結(jié)構(gòu)是借助于語言的數(shù)組來描述的。

鏈?zhǔn)酱鎯Y(jié)構(gòu)：不要求邏輯上相鄰的結(jié)點(diǎn)物理上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的，通常要借助于語言的指針類型來描述。

*

4、數(shù)據(jù)類型、抽象數(shù)據(jù)類型

數(shù)據(jù)類型:是一個(gè)值的集合和定義在這個(gè)值集上的所有的操作。例如，整數(shù)類型。數(shù)據(jù)類型可分為：非結(jié)構(gòu)的原子類型和結(jié)構(gòu)類型。

原子類型的值是不可分解的，結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。

抽象數(shù)據(jù)類型:是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，它僅取決于數(shù)據(jù)類型的邏輯性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)是無關(guān)的。

抽象數(shù)據(jù)類型的定義由一個(gè)值域和定義在該值域上的一組操作組成。抽象數(shù)據(jù)類型按其值的不同特性，分為三種類型： ① 原子類型:變量的值是不可分解的。

② 固定聚合類型:變量的值由確定數(shù)目的成分按某種結(jié)構(gòu)組成。③ 可變聚合類型:其值的成分?jǐn)?shù)目不確定。

抽象數(shù)據(jù)類型的形式定義：我們用一個(gè)三元組來表示一個(gè)抽象數(shù)據(jù)類型。

（d，s，p）

d是數(shù)據(jù)對象，s是d上的關(guān)系集，p是對d的基本操作。

格式：

adt 抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作的定義〉 }adt 抽象數(shù)據(jù)類型名。

數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述。數(shù)據(jù)基本操作的定義格式：

基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉 例：

adt triplet{ 數(shù)據(jù)對象：d={e1，e2,e3 |e1,e2,e3∈elemset(定義了關(guān)系運(yùn)算的某個(gè)集合)} 數(shù)據(jù)關(guān)系：r1={〈e1,e2>,

〉 基本操作：

min(t,&e)

}adt triplet 多形數(shù)據(jù)類型:是其值的成分不確定的數(shù)據(jù)類型。

三、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。

1、類c語言

精選了c 的一個(gè)子集，擴(kuò)充修改，增強(qiáng)了語言的描述功能。? 預(yù)定義常量和類型

? 數(shù)據(jù)結(jié)構(gòu)的表示：存儲結(jié)構(gòu)用類型（typedef）定義來描述。

數(shù)據(jù)元素類型約定為elemtype.? 基本操作的算法用函數(shù)描述：

函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）{ //算法說明

語句序列

}//函數(shù)名

增加了引用調(diào)用的參數(shù)傳遞方式。

? 賦值語句、選擇語句、循環(huán)語句、結(jié)束語句、輸入輸出語句、注釋語句 ? 基本函數(shù) ? 邏輯運(yùn)算約定

例：triplet的表示和實(shí)現(xiàn)

//采用動態(tài)分配的順序存儲結(jié)構(gòu)

typedef elemtype * triplet://由inittriplet分配三個(gè)元素存儲空間 //基本操作的函數(shù)原型說明

status inittriplet(triplet &t,elemtype v1, elemtype v2, elemtype v3)status destroytriplet（&t）status get（t,i,&e）status put(&t,i,e)status isascending(t)status isdescending(t)status max(t,&e)status min(t,&e)//基本操作的實(shí)現(xiàn)

status inittriplet(triplet &t, elemtype v1, elemtype v2, elemtype v3){ //構(gòu)造三元組t，依次置t 的三個(gè)元素的處值為v1,v2和v3。

t=(elemtype)malloc(3*sizeof(elemtype));//分配三個(gè)元素的存儲空間

if(!t)exit(overflow);//分配存儲空間失敗 t[0]=v1;t[1]=v2;t[2]=v3;return ok;}//inittriplet status destroytriplet（triplet &t）{ //銷毀三元組t?！ぁぁぁぁぁ?/p>

}//min

四、算法和算法分析

1、算法（algorithm）

是對特定問題求解步驟的一種描述，它是指令的有限序列。算法具有五個(gè)重要特性：有窮性、確定性、可行性、輸入、輸出

2、算法設(shè)計(jì)的要求

正確性、可讀性、健壯性和效率與低存儲量要求

3、算法效率的度量

算法時(shí)間是由控制結(jié)構(gòu)和原操作的決定的。做法：選取一種是基本操作的原操作，以該基本操作重復(fù)的次數(shù)作為算法的時(shí)間量度。

時(shí)間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），t（n）=o（f（n））

它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長綠相同。

語句的頻度：是該語句重復(fù)執(zhí)行的次數(shù)。

例：求兩個(gè)n階方陣的乘積c=a×b，其算法如下： #define n 100 void matrixmultiply(int a[n][n],int b[n][n],int c[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1

for(j=1;j<=n;++j)n*(n+1)

c[i][j]=0;n2

for(k=1;k<=n,k++)n2(n+1)

3c[i][j]=c[i][j]+a[i][k]*b[k][j];n

} } t(n)=2n3+3n2+2n+1 3limt(n)/ n=2 t(n)=o(n3)例：

（a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的語句的頻度分別為1,n和n2 時(shí)間復(fù)雜度是o(1),o(n)和o(n2)。時(shí)間復(fù)雜度有時(shí)與輸入有關(guān)。

4、算法的存儲空間需求

空間復(fù)雜度：s（n）=o（f（n））

五、作業(yè)布置

復(fù)習(xí)回顧c語言中關(guān)于結(jié)構(gòu)體和指針部分的內(nèi)容，以便于后期學(xué)習(xí)。

六、教學(xué)后記

按2 學(xué)時(shí)講完。

以前教學(xué)中反映出學(xué)生對抽象數(shù)據(jù)類型掌握不好，結(jié)構(gòu)體知識基本不懂，所以要求學(xué)生課下自學(xué)，下次課抽1學(xué)時(shí)學(xué)習(xí)結(jié)構(gòu)體和指針。

學(xué)生讀程序能力差，循環(huán)嵌套分析不出執(zhí)行次數(shù)。考慮布置了一道題目練習(xí)。

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

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

一、選擇

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

a.棧 b.隊(duì)列 c.樹 d.圖 2.下面程序段的時(shí)間復(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.兩個(gè)字符串相等的條件是（）

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

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

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

-1 +1 d.n 11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(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．一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關(guān)于棧和隊(duì)列的說法中正確的是（）

a．棧和隊(duì)列都是線性結(jié)構(gòu) b.棧是線性結(jié)構(gòu)，隊(duì)列不是線性結(jié)構(gòu) c.棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu) d.棧和隊(duì)列都不是線性結(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．已知一個(gè)單鏈表中，指針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)個(gè)數(shù)是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時(shí)，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的線性表中刪除一個(gè)指針p所指結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個(gè)棧的輸入序列是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．空串是只含有零個(gè)字符的串 b.空串是只含有空格字符的串

c.空串是含有零個(gè)字符或含有空格字符的串

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

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

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)個(gè)數(shù)是（）

-1 c.n(m-1)d.m(n-1)27．在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，每個(gè)頂點(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.矩陣中的非零元素個(gè)數(shù)等于圖的邊數(shù)

d.第i行上非零元素個(gè)數(shù)和第i列上非零元素個(gè)數(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)個(gè)數(shù)是（）a.1 b.2 c.3 d.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個(gè)關(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ì)算機(jī)加工處理的對象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面()。

3.線性表是由n≥0個(gè)相同類型組成的有限序列（）。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í)，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。

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

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨(dú)立于計(jì)算機(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)行的線性表是隊(duì)列（）。

三、畫圖題

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．已知一個(gè)圖的頂點(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.一個(gè)線性表為b=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為ht[0..12]，散列函數(shù)為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。

平均查找長度：（寫出計(jì)算過程）

3．已知一個(gè)圖的頂點(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è)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。

五、編程題

1.請編寫一個(gè)算法，實(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.請編寫一個(gè)算法，實(shí)現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點(diǎn)）。linklist *invertlink(linklist *h){

數(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請輸入要?jiǎng)h除的數(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(“請輸入一個(gè)關(guān)鍵字(輸入0時(shí)結(jié)束輸入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“請輸入下一個(gè)關(guān)鍵字(輸入0時(shí)結(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ǎng)h除的結(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);}

}