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

數據結構演講篇一

【實驗目的】

學習掌握線性表的順序存儲結構、鏈式存儲結構的設計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法。

【實驗內容】

1.順序表的實踐

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

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

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

3.1)建立一個包括頭結點和4個結點的（5，4，2，1）的單鏈表，實現單鏈表建立的基本操作。

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

3)在已建好的單鏈表中的指定位置（i=3）插入一個結點3，實現單鏈表插入的基本操作。

4)在一個包括頭結點和5個結點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結點，實現單鏈表刪除的基本操作。5)實現單鏈表的求表長操作。

【實驗步驟】

1.打開vc++。

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

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

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

線性是我們學習數據結構中，碰到的第一個數據結構。學習線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結構和鏈式存儲結構。通過學習我知道了對線性表進行建立、插入、刪除，同時單鏈表也是進行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復雜度均為0（n）.通過這次的學習，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念?？傊@次實驗我找到了自己的不足之處，以后會努力的。

實驗二：棧的表示與實現及棧的應用

【實驗目的】

（1）掌握棧的順序存儲結構及其基本操作的實現。（2）掌握棧后進先出的特點，并利用其特性在解決實際問題中的應用。（3）掌握用遞歸算法來解決一些問題?！緦嶒瀮热荨?/p>

1.編寫程序，對于輸入的任意一個非負十進制整數，輸出與其等值的八進制數。

2.編寫遞歸程序，實現n！的求解。3.編寫遞歸程序，實現以下函數的求解。

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

4.編寫程序，實現hanoi塔問題。【實驗步驟】 1.打開vc++。

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

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

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

通過這次的學習我掌握了棧這種抽象數據類型的特點，并能在相應的應用任務中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應地，表頭端稱為棧底（botton）；棧又稱為后進先出（last in first out）的線性表,簡稱lifo結構，因為它的修改是按后進先出的原則進行的。

加上這個實驗，我已經學了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學習有很大的作用，可以說這是學習以后知識的總要基礎。

實驗三：二叉樹的建立及遍歷

【實驗目的】

（1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法?！緦嶒瀮热荨?/p>

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

并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實驗步驟】 1.打開vc++。

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

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

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

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

實驗四：查找與排序

【實驗目的】

（1）掌握折半查找算法的實現。（2）掌握冒泡排序算法的實現?！緦嶒瀮热荨?/p>

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

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

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

4．寫好代碼

5．編譯－＞鏈接－＞調試

（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(“輸入元素個數和各元素的值:”);

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

} 實驗結果如下所示：

（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(“輸入元素個數和各元素的值:”);

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);} 實驗結果如下所示：

【實驗心得】

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

數據結構演講篇二

云淡風清 http:///

第1章 數據結構概述

1.1概述

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

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

計算機進行此類信息的處理時，涉及到兩個問題：一是現實當中的信息在計算機中如何表示，二是如何對信息進行處理。

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

1.1.1編寫解決實際問題的程序的一般流程

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

1、由具體問題抽象出一個適當的數學模型；

2、分析問題所涉及的數據量大小及數據之間的關系；

3、確定如何在計算機中存儲數據及體現數據之間的關系？

4、確定處理問題時需要對數據作何種運算？

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

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

云淡風清 http:/// 上面所列舉的問題基本上由數據結構這門課程來回答。

《數據結構》是計算機科學中的一門綜合性專業(yè)基礎課，是介于數學、計算機硬件、計算機軟件三者之間的一門核心課程，不僅是一般程序設計的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序和大型應用程序的重要基礎。

1.1.2數據結構的例子

1、電話號碼查詢系統

設有一個電話號碼薄，它記錄了n個人的名字和其相應的電話號碼。要求設計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。

姓名

電話號碼

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

這是一種典型的線性結構。

2、磁盤目錄文件系統

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

。。

本問題中各目錄從上到小形成了一種一對多的關系，是一種典型的樹形結構。

云淡風清 http:///

3、交通網絡圖

下圖表明了若干個城市之間的聯系：

從圖中可看出，一個地方到另外一個地方可以有多條路徑，是一種典型的網狀結構，數據與數據成多對多的關系。

4、排序問題

對100000個整數進行降序排序。冒泡法程序： #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”);

云淡風清 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記錄比關鍵字小的元素的最右位置

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

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

{

temp=a[last];

a[last]=a[j];

a[j]=temp;

last++;

}

//對形成的新子集遞歸進行快速排序

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”);

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

printf(“%8d”,a[i]);printf(“n”);} 運行可知，兩者速度差異非常明顯，主要是排序所花的時間差別很大。可看出，同樣的問題，采用不同方法進行處理，有可能呈現出非常大的性能方面的差異。

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

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

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

1.2.2數據元素(data element)：

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

1.2.3數據對象(data object)：

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

1.2.4數據的邏輯結構：

指對數據元素之間邏輯關系的描述。

數據元素之間的關系可以是一種或多種。

數據元素之間的關系可以是元素之間代表某種含義的自然關系，也可以是為處理問題方便而人為定義的關系，這種自然或人為定義的“關系”稱為數據元素之間的邏輯關系，相應的結構稱為邏輯結構。其要點有兩個方面：一是元素本身，二是元素之間的關系。數據元素之間的邏輯結構有四種基本類型，如下：

云淡風清 http:///

①集合：結構中的數據元素除了“同屬于一個集合”外，沒有其它關系。②線性結構：結構中相鄰的數據元素之間存在一對一的關系。③樹型結構：結構中相鄰的數據元素之間存在一對多的關系。

④圖狀結構或網狀結構：結構中相鄰的數據元素之間存在多對多的關系。數據結構數學形式的定義是一個二元組： datastructure=(d，s)其中：d是數據元素的有限集，s是d上關系的有限集。例：設數據邏輯結構b=(k，r)，其中： k={k1, k2, …, k9}

r={

，

，

，

，

，

，

，

，

，

，

} 畫出這邏輯結構的圖示，并確定哪些是起點，哪些是終點。

又稱存儲結構，指數據結構在計算機內存中的存儲方式。

數據結構在計算機內存中的存儲包括數據元素的存儲和元素之間的關系的存儲。元素之間的關系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。

順序存儲結構：用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯結構(關系)。鏈式存儲結構：在每一個數據元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數據元素之間的邏輯結構(關系)。

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

鏈式結構：數據元素存放的地址是否連續(xù)沒有要求。

數據的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。

在c語言中，用一維數組表示順序存儲結構；通過結構體類型實現的鏈表來表示鏈式存儲結構。

1.2.6數據結構(data structure)：

按某種邏輯關系組織起來的一批數據，按一定的映象方式把它存放在計算機存貯器中，并在這些數據上定義了一個運算的集合，就叫做數據結構。

1.2.7數據結構的三個組成部分：

邏輯結構：數據元素之間邏輯關系的描述：d_s=(d，s)。

存儲結構：數據元素在計算機中的存儲及其邏輯關系的表現稱為數據的存儲結構或物理結構。數據操作：對數據要進行的運算。

本課程中將要討論的三種邏輯結構及其采用的存儲結構如下圖所示。

云淡風清 http:///

邏輯結構與所采用的存儲結構

數據邏輯結構層次關系圖

1.2.8數據類型(data type)：

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

數據類型是和數據結構密切相關的一個概念。在c語言中數據類型有：基本類型(如int，float，double，char等)和構造類型(如數組，結構體，共用體等)。

數據結構不同于數據類型，也不同于數據對象，它不僅要描述數據類型的數據對象，而且要描述數據對象各元素之間的相互關系。

1.3數據結構的運算

數據結構的主要運算包括： ⑴建立(create)一個數據結構； ⑵消除(destroy)一個數據結構；

⑶從一個數據結構中刪除(delete)一個數據元素； ⑷把一個數據元素插入(insert)到一個數據結構中； ⑸對一個數據結構進行訪問(access)；

⑹對一個數據結構(中的數據元素)進行修改(modify)； ⑺對一個數據結構進行排序(sort)； ⑻對一個數據結構進行查找(search)。

以上只列舉了一些常見運算，實際應用當中可能會遇到許多其它運算。

云淡風清 http:/// 1.4抽象數據類型(abstract data type)1.4.1抽象數據類型簡介：

簡稱adt，是指一個數學模型以及定義在該模型上的一組操作。adt的定義僅是一組邏輯特性描述，與其在計算機內的表示和實現無關。因此，不論adt的內部結構如何變化，只要其數學特性不變，都不影響其外部使用。

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

⑴adt和數據類型實質上是一個概念，其區(qū)別是：adt的范疇更廣,它不再局限于系統已定義并實現的數據類型，還包括用戶自己定義的數據類型。

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

adt不考慮物理結構以及算法的具體實現。

例：整數的數學概念和對整數所能進行的運算構成一個adt，c語言中的變量類型int就是對這個抽象數據類型的一種物理實現。

1.4.2adt的一般定義形式：

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

初始條件：描述操作執(zhí)行之前數據結構和參數應滿足的條件；若不滿足，則操作失敗，返回相應的出錯信息。

操作結果：描述操作正常完成之后，數據結構的變化狀況和應返回的結果。

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

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

云淡風清 http:/// 多個操作。

1.5.2算法的基本特征：

算法具有以下五個特性

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

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

③可行性：一個算法是能行的。即算法描述的操作都可以通過已經實現的基本運算執(zhí)行有限次來實現。

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

⑤輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。

1.5.3算法的基本描述方法：

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

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

算法和程序是兩個不同的概念。一個計算機程序是對一個算法使用某種程序設計語言的具體實現。算法必須可終止意味著不是所有的計算機程序都是算法。

1.5.5評價算法好壞的幾個標準：

評價一個好的算法有以下幾個標準

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

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

③健壯性(robustness)：算法應具有容錯處理。當輸入非法或錯誤數據時，算法應能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。

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

1.6算法效率的度量

解決同一個問題的算法可能有多種，如何選擇一個效率高的算法呢？應該來講，與算法效率相關的因素有很多，如下：

云淡風清 http:///

1、算法選用何種策略；

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

3、程序設計的語言；

4、編譯程序所產生的機器代碼的質量；

5、內存的大??；

6、外存的大??；

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

8、其它。

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

1.6.1事后統計：

先實現算法，然后運行程序，測算其時間和空間的消耗。缺點：

1、必須先依據算法編制程序并運行程序，耗費人力物力；

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

3、沒有實際價值。測試花費不少時間但并沒有解決現實中的實際問題。

1.6.2事前分析：

僅僅通過比較算法本身的復雜性來評價算法的優(yōu)劣，不考慮其它的軟硬件因素，通?？疾樗惴ㄋ玫臅r間和所需的存儲空間。

算法復雜性的度量可以分為時間復雜度和空間復雜度。

1.6.3算法的時間復雜度(time complexity)

1、算法的時間復雜度

算法的時間復雜度用于度量一個算法所用的時間。

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

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

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

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

2、時間復雜度分析舉例： 例：兩個n階方陣的乘法。

云淡風清 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];} 分析：由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數為： n×n×n=n3，時間復雜度為t(n)=o(n3)。

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

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

++x;

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

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

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

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

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

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

{

++x;

a[i,j]=x;

}

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

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

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

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

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

4、常見時間復雜度大小關系分析：

以下六種計算算法時間復雜度的多項式是最常用的，其大小關系通常為： o(1)

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

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

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

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

printf(“&d 是一個素數n”,n);else

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

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

例：冒泡排序法。

void bubble_sort(int a[],int n)

云淡風清 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平均時間復雜度為：o(n2)1.6.4算法的空間復雜度(space complexity)

1、算法的空間復雜度

算法的空間復雜度是指在算法的執(zhí)行過程中需要的輔助空間數量。輔助空間數量指的不是程序指令、常數、指針等所需要的存儲空間，也不是輸入數據所占用的存儲空間，輔助空間是除算法本身和輸入輸出數據所占據的空間外，算法臨時開辟的存儲空間。算法的空間復雜度分析方法同算法的時間復雜度相似，設s(n)是算法的空間復雜度，通?？梢员硎緸椋?/p>

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

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

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

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++)

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

在算法的時間復雜度和空間復雜度中，我們更注重算法的時間性能。因此，在對算法性能的分析當中，通常均主要針對算法時間性能進行分析。

1.6.5學習算法的原因

講述了這么多關于算法的基礎知識，究竟為什么要學習算法呢？

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

其次，算法是程序的靈魂。學習計算機編程，必須要掌握好其靈魂，否則，寫出來的程序就像是沒有靈魂的軀體。

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

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

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

習題一

1、簡要回答術語：數據，數據元素，數據結構，數據類型。

2、數據的邏輯結構？數據的物理結構？邏輯結構與物理結構的區(qū)別和聯系是什么？

3、數據結構的主要運算包括哪些？

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

云淡風清 http:///

第2章 線性表

下表為某電臺提供給聽眾的若干首英文歌曲名及相關點播情況統計信息：

由于實際的歌曲庫可能很大，手工管理效率低，不方便，現請設計一個軟件系統實現對此類歌曲庫的管理。

分析：

此例中相鄰的兩首歌之間是一種一對一的關系，屬于典型的線性結構，可按線性結構進行組織及管理。

2.1線性結構與線性表 2.1.1線性結構

如果一個數據元素序列滿足：

⑴除第一個和最后一個數據元素外，每個數據元素只有一個直接前驅數據元素和一個直接后繼數據元素；

⑵第一個數據元素沒有前驅數據元素； ⑶最后一個數據元素沒有后繼數據元素。則稱這樣的數據結構為線性結構。

線性表、棧、隊列、串和數組都屬于線性結構。如下圖：

云淡風清 http:/// 2.1.2線性表

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

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

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

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

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

線性結構是最常用、最簡單的數據結構，而線性表是一種典型的線性結構，其基本特點是可以在任意位置進行插入和刪除等操作，且數據元素是有限的。

線性表可以用順序存儲結構或鏈式存儲結構實現。用順序存儲結構實現的線性表稱為順序表，用鏈式存儲結構實現的線性表稱為鏈表。鏈表主要有單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表三種。順序表和鏈表各有優(yōu)缺點，并且優(yōu)缺點剛好相反，在實際應用中要根據情況選擇對操作及性能有利的存儲結構。

線性表中的數據元素ai所代表的具體含義隨實際應用領域的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號。

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

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

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

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

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

云淡風清 http:/// ⑿根據所給關鍵字查詢元素并返回其詳細信息 ⒀修改表中元素

⒁對所有元素按條件排序

2.1.3線性表的抽象數據類型定義

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

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

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

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

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

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

云淡風清 http:/// } adt list 2.2線性表的順序存儲 2.2.1線性表的順序存儲結構

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

順序存儲的線性表的特點：

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

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

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

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

#include

#include

#define ok #define error

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

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

2.2.2順序表的基本操作

順序存儲結構中，很容易實現線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。

以下將對幾種主要的操作進行討論。#include

#define ok #define error

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

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

1、初始化

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

2、測長度

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

3、取元素

用e返回l中第i個數據元素的值，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位置對應的元素下標為i-1

return ok;} else

return error;}

云淡風清 http:/// /*

4、順序線性表的插入

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

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

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

return error;else

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

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

return error;

else

{

//i-1位置以后的所有結點后移

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位置插入結點

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

return ok;

} } /* 時間復雜度分析：

在線性表l中的第i個位置插入新結點，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。

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

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

即在順序表上做插入運算，平均要移動表上一半結點，當表長n較大時，算法的效率相當低。因此算法的平均時間復雜度為o(n)。

*/ /*

5、線性表元素位置查詢

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

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

i=0;//從第一個開始查詢

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)中刪除結點ai(1≦i≦n)，使其成為線性表： l=(a1，?ai-1，ai+1，?，an)要求1≤i≤listlength(l)，線性表未空。實現步驟：

(1)將線性表l中的第i+1個至第n個結點依此向前移動一個位置。(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(“要刪除的數據元素不存在!n”);

return error;

}

else

{

//i位置以后的所有結點前移

for(k=i;k

length;k++)

云淡風清 http:///

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

return(ok);

} } /* 時間復雜度分析：

刪除線性表l中的第i個元素，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。

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

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

(1≤i≤n)計算得：edelete=(n-1)/2 即在順序表上做刪除運算，平均要移動表上一半結點，當表長n較大時，算法的效率相當低，因此算法的平均時間復雜度為o(n)。

*/ /*

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

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

length;i++)

9、修改

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

云淡風清 http:///

return error;else {

l->elem_array[i-1]=e;//放置新數據

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;} /* 主函數 */ 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、結束n請選擇：”);

scanf(“%d”,&xz);

switch(xz)

{

case 1:

if(init_sqlist(&l)==ok)

云淡風清 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”);scanf(“%d”,&e);if(insert_sqlist(&l,i,e)==ok)

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

printf(“error！n”);break;case 5: printf(“請輸入要查詢的元素內容：”);scanf(“%d”,&e);printf(“此元素邏輯位置為：%d(0表示未找到)。n”,locate_sqlist(&l,e));break;case 6: printf(“請輸入要刪除元素的位置：”);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;

云淡風清 http:///

case 9:

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

scanf(“%d”,&i);

printf(“請輸入元素的新內容：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(“輸入錯誤！n”);

break;

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

2.2.3順序存儲線性表的特點

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

缺點：

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

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

2.3線性表的鏈式存儲 2.3.1線性表的鏈式存儲結構

鏈式存儲：用一組任意(即不必要連續(xù))的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表簡稱線性鏈表。

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

為了正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其直接后繼結點的

云淡風清 http:/// 地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結點結構，如下圖所示。

data：數據域，存放結點的值。

next：指針域，存放結點的直接后繼的地址。

鏈表通過每個結點的指針域將線性表的n個結點按其邏輯次序鏈接在一起。每一個結點只包含一個指針域的鏈表，稱為單鏈表。

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

帶頭結點的單鏈表其基本結構如下：

說明：

(1)整個鏈表由若干個結點組成，一個結點占用一個內存塊，而每個結點又分為兩大部分：數據域和指針域，其中數據域存放用戶數據，指針域用于存放后一個結點的地址，通過指針域將邏輯上前后相鄰的結點連接起來，這樣，通過前一個結點指針域中存放的地址就可以找到后一個結點?？煽闯?，每個結點的指針域實際上充當了指針變量的角色，只要結點數可變，則意味著指針變量數也可變，而事實上結點所對應的這些內存塊完全可以多次動態(tài)分配，這也就意味著指針域(相當于指針變量)的個數可以根據需要動態(tài)調整，這就解決了前述的“程序中變量個數固定，但問題本身所需變量個數不定”的矛盾。

(2)設置一個頭指針變量指向首結點，在帶頭結點的單鏈表中，此結點不存放有效數據。(3)末尾結點的指針域設置為空“null”表示鏈表的結束，相當于字符串中的''。

(4)在沒有用戶數據的情況下，此鏈表只有一個結點，此結點既是首結點，又是末結點，結點的指針域為“null”，此時表示鏈表為邏輯“空”，也就是說，鏈表的初始狀態(tài)應該如下圖所示。

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

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

云淡風清 http:///

1、結點的描述與實現

c語言中用帶指針的結構體類型來描述 typedef int elemtype;typedef struct lnode { elemtype

data;//數據域，保存結點的值

struct

lnode *next;//指針域，保存后繼結點地址 }lnode;

//結點的類型

2、結點空間分配及回收的實現

結點存儲空間是通過動態(tài)內存分配和釋放來實現的，即需要時分配，不需要時釋放。在c語言中可通過標準函數：malloc()，realloc()，sizeof()，free()等來實現分配。

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

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

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

云淡風清 http:/// ②q=p->next;

③p=p->next;

④q->next=p;

⑤q->next=p->next;

云淡風清 http:///

2.3.2單鏈式的基本操作

以帶頭結點的單鏈表為例。#define ok #define error

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

data;//數據域，保存結點的值

struct

lnode *next;//指針域，保存后繼結點地址 }lnode;

//結點的類型

/*

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

if(l!=null)

l->next=null;//指針域置為空以作為結束標記

return l;} /*

2、頭插入法建表

從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止，每次插入的結點都作為鏈表的第一個數據結點。

*/

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

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

p=(lnode *)malloc(sizeof(lnode));//給新結點分配空間

if(p==null)

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

else

{

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

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

p->data=data;//數據域賦值

//鉤鏈，新創(chuàng)建的結點總是作為第一個數據結點

p->next=l->next;

l->next=p;

}

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

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

3、尾插入法建表

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

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

lnode *p,*q;//找到已有鏈表的末結點

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

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

p=(lnode *)malloc(sizeof(lnode));//給新結點分配空間

if(p==null)

云淡風清 http:///

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

else

{

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

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

p->data=data;//數據域賦值

//鉤鏈，新創(chuàng)建的結點總是作為最后一個結點

q->next=p;

q=p;//q重新指向末結點

}

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

scanf(“%d”,&sfjx);} q->next=null;//重設鏈表結束標記

return(ok);} /*

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

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

設單鏈表的長度為n，要查找表中第i個結點，僅當1≦i≦n時，i的值是合法的。*/ status get_linklist(lnode *l,int i,elemtype *e){

int j=1;lnode *p;p=l->next;//使p指向第一個結點

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

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

j++;

//j計數

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

return(error);else {

*e=p->data;

return(ok);} } /*

云淡風清 http:///

5、按值查找

按值查找是在鏈表中，查找是否有結點值等于給定值key的結點? 若有，則返回首次找到的值為key的結點的存儲位置；否則返回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為頭結點的單鏈表的第i個位置插入值為e的結點。

插入運算是將值為e的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結點p，然后生成一個數據域為e的新結點q，q結點作為p的直接后繼結點。

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

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

p=p->next;

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

{

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

return error;} else {

q=(lnode *)malloc(sizeof(lnode));//給新結點分配空間

if(q==null)

return error;

else

云淡風清 http:///

{

//實現插入

q->data=e;

q->next=p->next;

p->next=q;

return ok;

} } } /*

7、按序號刪除

刪除單鏈表中的第i個結點。

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

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

while(q!=null && j

p=q;

q=q->next;

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

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

return error;} else {

//實現刪除

p->next=q->next;

free(q);

return ok;} }

云淡風清 http:/// /*

8、按值刪除

刪除單鏈表中值為key的第一個結點。

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

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

p=q;

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

{

//實現刪除

p->next=q->next;

free(q);

return ok;} else {

printf(“所要刪除的結點不存在！n”);

return error;} } /*

9、刪除單鏈表中值為key的所有結點

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

基本思想：從單鏈表的第一個結點開始，對每個結點進行檢查，若結點的值為key，則刪除之，然后檢查下一個結點，直到所有的結點都檢查。

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

while(q!=null){

if(q->data==key)

{

p->next=q->next;

云淡風清 http:///

free(q);

q=p->next;

}

else

{

p=q;

q=q->next;

} } } /*

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

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

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

{

q=p;

ptr=p->next;

while(ptr!=null)//檢查結點p的所有后繼結點ptr

{

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

{

q->next=ptr->next;

free(ptr);

ptr=q->next;

}

else

{

q=ptr;

ptr=ptr->next;

}

}

p=p->next;} } /*

云淡風清 http:///

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

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、單鏈表的合并

設有兩個有序的單鏈表，它們的頭指針分別是la、lb，將它們合并為以lc為頭指針的有序鏈表。算法說明：算法中pa，pb分別是待考察的兩個鏈表的當前結點，pc是合并過程中合并的鏈表的最后一個結點。

云淡風清 http:///

合并了值為-7，-2的結點后示意圖如下圖所示。

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

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

if(pa->data

data)//將pa所指的結點合并，pa指向下一個結點

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else

if(pa->data>pb->data)//將pb所指的結點合并，pb指向下一個結點

{

pc->next=pb;

pc=pb;

pb=pb->next;

云淡風清 http:///

}

else//將pa所指的結點合并，pb所指結點刪除

{

pc->next=pa;

pc=pa;

pa=pa->next;

ptr=pb;

pb=pb->next;

free(ptr);

} } //將剩余的結點鏈上

if(pa!=null)

pc->next=pa;else

pc->next=pb;

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

14、單鏈表的排序

采用插入排序方法，以升序為例 */ 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;} }

云淡風清 http:/// /*

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

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、刪除單鏈表中指定值的所有結點n10、刪除單鏈表中所有值重復的結點n”);

printf(“

11、修改指定位置的數據n12、單鏈表遍歷n13、單鏈表的合并n14、單鏈表的排序n15、單鏈表的釋放n 0、結束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”);

云淡風清 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(“請輸入要查找元素的關鍵字：”);scanf(“%d”,&e);l1=locate_linklist(l,e);if(l1!=null)

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

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

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

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

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

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

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

云淡風清 http:///

printf(“未成功刪除！n”);break;case 9: printf(“請輸入要元素的內容：”);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(“請輸入元素的新內容：”);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(“請建立第一個鏈表：n”);

create2_linklist(l1);

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

create2_linklist(l2);

sort_linklist(l1);

sort_linklist(l2);

l=merge_linklist(l1,l2);

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

traverse_linklist(l);} break;case 14:

云淡風清 http:///

}

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

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

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

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

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

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

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

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

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

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

2、報數并按順序輸出出圈人的編號；

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

云淡風清 http:/// 第一步：輸入人員總數；

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

第四步：數到3讓此人出圈(刪除對應結點)；

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

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

{ printf(“要數到的個數(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;}

云淡風清 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;//以下代碼實現出圈

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);} 注意：此程序采用的是不帶頭結點的單鏈表，以免在循環(huán)鏈表中由于不存放有效數據的頭結點的存在而影響計數。

2.5雙向鏈表

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

數據結構演講篇三

《數據結構》教案

課程性質和任務

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

課程教學目標

通過本課程的學習，應達到以下目標：

? 深刻理解數據結構中線性表、棧、隊和鏈的概念、算法及其基本應用。

? 理解樹的基本概念，學會建立二叉樹，并在二叉樹上進行查找、插入和刪除等各種運算。

? 理解圖的基本結構和算法，了解圖的路徑問題。

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

? 能熟練地運用c語言，準確、清晰地編制與本課程有關的算法，并能上機調試通過。

新疆農業(yè)大學數據結構課程教案

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

一、教學目的和要求

要求掌握數據結構中基本概念的定義，理解數據結構研究的主要內容，了解抽象數據類型的表示和實現，理解算法評價的兩個指標。

二、授課主要內容

1.數據結構研究的主要內容 2.數據結構中涉及的基本概念

3.算法的概念、描述方法以及評價標準

三、教學重點難點

數據結構中的基本概念、算法的概念、描述方法以及評價標準

四、授課內容和方法

【口述】當今計算機應用的特點：所處理的數據量大且具有一定的關系；對其操作不再是單純的數值計算，而更多地是需要對其進行組織、管理和檢索。

一、什么是數據結構

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

1、舉例說明

? 圖書館的書目檢索自動化問題----計算機處理的對象之間存在著線性關系，稱為線性的數據結構。

? 人機對奕問題----計算機處理的對象是一個個格局。所有可能出現的格局是一棵倒置的樹。

? 多岔路口交通燈的管理問題----數學模型是圖的數學結構。

【由以上舉例引出下列結論：】

非數值計算問題的數學模型是表、樹和圖之類的數據結構?！究偨Y出定義】 數據結構：是一門研究非數值計算的程序設計問題中計算機操作對象以及它們之間關系和操作的一門學科。（三個要素：對象、關系及操作（運算））

2、《數據結構》課程的介紹

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

數據結構是一門綜合性的專業(yè)課程，是一門介于數學、計算機硬件、計算機軟件之間的一門核心課程。是設計和實現編譯系統、操作系統、數據庫系統及其他系統程序和大型應用程序的基礎。

二、基本概念和術語

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

加工的“原料”。

數據元素:是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

數據項:有時，一個數據元素可由多個數據項組成。數據項是數據的不可分割的最小單位。

2、數據對象、數據結構

數據對象：是性質相同的數據元素的集合，是數據的一個子集。數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。四類基本結構：集合、線性結構、樹形結構、圖形結構或網狀結構。數據結構的形式定義：數據結構是一個二元組

data_structure=(d,s)其中，d 是數據元素的有限集，s 是d上關系的有限集。

例：復數 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,} 數據結構一般包括三方面的內容：

② 存儲結構(物理結構)：數據元素及其關系在計算機存儲器的表示。用于表示數據元素的位串稱之為元素或結點。用于表示數據項的位串稱之為數據域。

③ 數據的運算：對數據施加的操作。

算法的設計取決于選定的數據邏輯結構，而算法的實現依賴于采用的存儲結構。

3、數據的兩種存儲結構： 順序存儲結構：把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。通常順序存儲結構是借助于語言的數組來描述的。

鏈式存儲結構：不要求邏輯上相鄰的結點物理上也相鄰，結點間的邏輯關系是由附加的指針字段表示的，通常要借助于語言的指針類型來描述。

*

4、數據類型、抽象數據類型

數據類型:是一個值的集合和定義在這個值集上的所有的操作。例如，整數類型。數據類型可分為：非結構的原子類型和結構類型。

原子類型的值是不可分解的，結構類型的值是由若干成分按某種結構組成的。

抽象數據類型:是指一個數學模型以及定義在該模型上的一組操作。抽象數據類型和數據類型實質上是一個概念，它僅取決于數據類型的邏輯性，而與其在計算機內部如何表示和實現是無關的。

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

② 固定聚合類型:變量的值由確定數目的成分按某種結構組成。③ 可變聚合類型:其值的成分數目不確定。

抽象數據類型的形式定義：我們用一個三元組來表示一個抽象數據類型。

（d，s，p）

d是數據對象，s是d上的關系集，p是對d的基本操作。

格式：

adt 抽象數據類型名{ 數據對象：〈數據對象的定義〉 數據關系：〈數據關系的定義〉 基本操作：〈基本操作的定義〉 }adt 抽象數據類型名。

數據對象和數據關系的定義用偽碼描述。數據基本操作的定義格式：

基本操作名（參數表）

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

操作結果：〈操作結果描述〉 例：

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

〉 基本操作：

min(t,&e)

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

三、抽象數據類型的表示與實現

抽象數據類型可通過固有數據類型來表示和實現，即利用處理器中已存在的數據類型來說明新的結構，用已經實現的操作來組合新的操作。

1、類c語言

精選了c 的一個子集，擴充修改，增強了語言的描述功能。? 預定義常量和類型

? 數據結構的表示：存儲結構用類型（typedef）定義來描述。

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

函數類型 函數名（函數參數表）{ //算法說明

語句序列

}//函數名

增加了引用調用的參數傳遞方式。

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

例：triplet的表示和實現

//采用動態(tài)分配的順序存儲結構

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

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)//基本操作的實現

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

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

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）

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

2、算法設計的要求

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

3、算法效率的度量

算法時間是由控制結構和原操作的決定的。做法：選取一種是基本操作的原操作，以該基本操作重復的次數作為算法的時間量度。

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

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

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

例：求兩個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 時間復雜度是o(1),o(n)和o(n2)。時間復雜度有時與輸入有關。

4、算法的存儲空間需求

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

五、作業(yè)布置

復習回顧c語言中關于結構體和指針部分的內容，以便于后期學習。

六、教學后記

按2 學時講完。

以前教學中反映出學生對抽象數據類型掌握不好，結構體知識基本不懂，所以要求學生課下自學，下次課抽1學時學習結構體和指針。

學生讀程序能力差，循環(huán)嵌套分析不出執(zhí)行次數?？紤]布置了一道題目練習。

數據結構演講篇四

數據結構參考題目

一、選擇

1.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（）

a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復雜度為（）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.串的長度相等且對應的字符相同 5．若以s和x分別表示進棧和退棧操作，則對初始狀態(tài)為空的棧可以進行的棧操作系列是（）

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

（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]，散列函數h（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關鍵字：t[5]=39，t[6]=57和t[7]=7，則下一個關鍵字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的運算求取矩陣中的每一個元素，則求得a21的運算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為dout，則所有頂點的入度之和為（）

-1 +1 d.n 11．從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（）a線性結構 b.樹形結構 c.線性結構和樹型結構 d.線性結構和圖狀結構

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

a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）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．關于棧和隊列的說法中正確的是（）

a．棧和隊列都是線性結構 b.棧是線性結構，隊列不是線性結構 c.棧不是線性結構，隊列是線性結構 d.棧和隊列都不是線性結構 16．關于存儲相同數據元素的說法中正確的是（）a．順序存儲比鏈式存儲少占空間 b.順序存儲比鏈式存儲多占空間

c.順序存儲和鏈式存儲都要求占用整塊存儲空間 d.鏈式存儲比順序存儲難于擴充空間

17．已知一個單鏈表中，指針q指向指針p的前趨結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執(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．設一組記錄的關鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結點個數是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時，s語句被執(zhí)行的次數為：（）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所指結點的時間復雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（）

a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．關于串的敘述中，正確的是（）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．設有二維數組

?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的完全二叉樹中，結點數最多為（）

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

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

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

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

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

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.數據是計算機加工處理的對象（）。2.數據結構的概念包括數據的邏輯結構、數據在計算機中的存儲方式和數據的運算三個方面()。

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

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

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

10.單鏈表結點的指針域是用來存放其直接后繼結點的首地址的（）

11.數據的存儲結構是數據的邏輯結構的存儲映象（）。

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

13.在非線性結構中，至少存在一個元素不止一個直接前驅或不止一個直接后驅（）。14.樹的最大特點是一對多的層次結構（）。15.隊列的特點是先進先出（）。

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數據的存儲結構獨立于計算機（）。18.線性表簡稱為”順序表”。（）

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

27.數據的邏輯結構可以看作是從具體問題抽象出來的數學模型（）。

28.線性表的順序存儲方式是按邏輯次序將元素存放在一片地址連續(xù)的空間中（）。29.棧是一種先進后出的線性表（）。

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

三、畫圖題

1.請根據下列二元組畫出相應的數據結構

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據下列二元組畫出相應的數據結構

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

,

,

,

,

,

,

} 3．請根據下列二元組畫出相應的數據結構 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.請根據下列二元組畫出相應的數據結構

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）}

四、運算題

1．已知一個圖的頂點集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），設散列表為ht[0..12]，散列函數為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。

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

3．已知一個圖的頂點集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出發(fā)）

____

__，___

_，___

___，__

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

前序： 中序： 后序：

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

五、編程題

1.請編寫一個算法，實現十進制整數與二進制數的轉換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：

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

數據結構演講篇五

數據結構】二叉排序樹的建立，查找，插入和刪除實踐題 /*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請輸入要查找的數據：”);

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

searchbst(t,key);

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

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

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

insertbst(&t,key);

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

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

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(“請輸入一個關鍵字(輸入0時結束輸入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“請輸入下一個關鍵字(輸入0時結束輸入)：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(“沒有找到要刪除的結點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);}

}