《數據結構》1

教材數據結構（C語言版）嚴蔚敏吳偉民清華大學出版社參考教材數據結構題集（C語言版）

嚴蔚敏吳偉民清華大學出版社2對于一個課題，在計算機領域，一般遵循下面的解決原則：需求分析總體設計模塊分割建立數學模型解數學模型的算法程序編制調試結果數據結構涉及到：數學模型的建立和對該模型具體實現的對應的算法。數據結構的地位：數學、硬件、軟件之間。核心專業基礎課.引論3數據結構課程解決的問題1、采用什么樣的存儲方式才能正確的表達數據對象中數據元素的類型與關系。2、采用什么樣的方式才能正確訪問已經存儲的數據對象中的數據元素。5教學內容

第一章緒論

第二章線性表

第三章棧和隊列

第四章串

第五章數組和廣義表

第六章樹

第七章圖

第八章查找

第九章排序6第一章緒論7第一章緒論

1.1

本課程研究的問題

1.2數據結構的有關基本概念

1.3數據結構（邏輯結構）的分類及表示

1.4數據的存儲結構

1.5算法及算法分析（算法評價）

1.6C語言中的結構體類型

8

數值問題與非數值問題1）數值問題例1已知：游泳池的長len和寬wide，求面積area?！粼O計求解問題的方法◆編程main(){ intlen,wide,area;

scanf(“%d%d\n”,&len,&wide);

area=len*wide;

printf(“area=%d”,area);}1.1本課程研究的問題◆建模型

問題涉及的對象：游泳池的長len，寬wide，面積area；

對象之間的關系：area=lenwide101.1本課程研究的問題例3迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。計算機處理的這類對象之間通常不存在線性關系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹”。121.1本課程研究的問題數據結構：數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。141．2數據結構的有關概念

數據：客觀事物的符號表示。即一切能夠被計算機接受并進行處理的信息對象。例如：學號，姓名，班名都是數據。

數據元素：數據的基本單位。相當于“記錄”,在計算機程序中通常作為一個整體進行考慮和處理。數據項:相當于記錄的“域”,是數據的不可分割的最小單位,如學號。數據對象：性質相同的數據元素的集合。

數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。

1.2數據結構的有關概念15姓名性別出生日期班級張紅女1982-01-010201王林男1983-02-030230趙麗女1981-09-140229數據數據元素數據對象1．2數據結構的有關概念舉例：16對每種數據結構，主要討論如下兩方面的問題：1）數據的邏輯結構(logicalstructrue)數據元素之間客觀存在的真實的關系。

2）數據的存儲結構（physicalstructure）我們研究結點間的邏輯結構是為了加工和存儲管理的需要，因此，在確定數據的邏輯結構后，就要把結點及其關系存儲到計算機中去。數據的邏輯結構是獨立于計算機的，而數據的存儲結構是依賴于計算機的，它是邏輯結構在計算機中的實現。1．2數據結構的有關概念1718家族的族譜：

假設某家族有10個成員A，B，C，D，E，F，G，H，I，J，他們之間的血緣關系可以用如下圖表示。JIACBDHGFE1．3數據結構的分類及表示例20二、數據結構的表示

1、圖示表示

圖示表示是由頂點和邊構成的圖，其中頂點表示數據，邊表示數據之間的結構關系。

001003002004006005008007學生基本情況表的圖示表示JIACBDHGFE家族樹的圖示表示1．3數據結構的分類及表示21三、有關術語結點：在研究數據的邏輯結構時，為了便于討論，我們通常把在問題中作為整體進行考慮和處理的數據單位，稱為“結點”。前驅和后繼：如果B=(A,R)是一個數據結構，設rR，A中的二結點a，b有<a,b>r，則稱結點a為結點b的前驅，反之，結點b為結點a的后繼。起始結點：若A中不存在結點d，使<d,a>r，則稱結點a是關系r中的一個起始結點，它是r中的無前驅結點。終止結點：若A中不存在結點c，使<b,c>r，則稱結點b是關系r中的一個終止結點，它是r中的無后繼結點。23四、分類按邏輯關系的不同分為線性結構和非線性結構，其中非線性結構又可分為樹結構和圖結構。集合：結構中的數據元素之間除了“同屬于一個集合”的關系外，別無其他關系。線性結構：結構中數據元素之間存在一個對一個的關系，即結構中除起始結點和終止結點外，每個結點都有一個唯一的前驅和后繼。樹狀結構：結構中數據元素之間存在一個對多個的關系。在樹狀結構中，只有唯一的一個結點沒有前驅，稱為“樹根”，其余結點都有且僅有一個前驅。圖狀結構：結構中數據元素之間存在多個對多個的關系。在圖狀結構中，結點的前驅和后繼的個數不受限制。241、順序存儲結構262、鏈式存儲結構第1個職工信息第2個職工信息第4個職工信息第3個職工信息200302408302408200NULL10027

順序存儲結構和鏈式存儲結構的對比--1順序存儲結構的優點：

結構中的數據元素是依次存放，所以數據元素存取操作簡單、速度較快。順序存儲結構的缺點：

插入、刪除數據元素時，由于需要保持數據元素之間的邏輯關系，必須移動大量元素，因此實現起來較慢。

281．4算法與算法分析1.5算法與算法分析一、算法的概念

算法是求解問題的操作序列。算法的基本特征：

1）輸入：0個或多個輸入；

2）輸出：1個或多個輸出；

3）有窮性：算法必須在有限步內結束；

4）確定性：組成算法的操作必須清晰無二義性。

5）可行性：組成算法的操作必須能夠在計算機上實現。求兩個正整數m，n中的最大數MAX的算法。（1）若m>n則max=m

（2）若m<=n則max=n例30二、描述算法的書寫規則所有算法均以函數形式給出,算法的輸入數據來自參數表。參數表的參數在算法之前均進行類型說明。有關結點結構的類型定義，以及全局變量的說明等均在算法之前進行說明。31三、算法與數據結構的關系計算機科學家沃斯（N.Wirth）提出的：“算法+數據結構=程序”揭示了程序設計的本質：對實際問題選擇一種好的數據結構，加上設計一個好的算法，而好的算法很大程度上取決于描述實際問題的數據結構。算法與數據結構是互相依賴、互相聯系的。一個算法總是建立在一定數據結構上的；反之，算法不確定，就無法決定如何構造數據。32四、評價算法標準

算法的正確性、可讀性、健壯性（容錯性）、效率與低存儲量需求。1、算法時間復雜度T（n）

本課程采用以求解問題的基本操作（原操作）的執行次數作為算法時間的度量。

1．4算法與算法分析O(n3）

稱為矩陣相乘算法時間復雜度；O(n3）表示矩陣相乘算法執行時間與n3成正比,即O(n3）與n3同一數量級；n階矩陣相乘的算法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]；}

乘法加法執行次數均為n3

例

矩陣相乘的基本運算：乘法加法；33有些算法，基本操作執行次數與問題的輸入數據有關，這時可考慮

（1）算法平均時間復雜度

（2）算法在最壞情況下的時間復雜度算法的時間復雜度

一般來說，設算法中基本操作重復執行的次數是問題規模n的某個函數f(n)，算法的時間復雜度記作：

T(n)=O(f(n))

它表示隨問題規模n的增大，算法執行時間的增長率與f(n)的增長率相同。

1．4算法與算法分析34算法的時間復雜度為T(N)=O(N3)

1．4算法與算法分析

100元買100支筆,其中鋼筆3元/支,圓珠筆2元/支,鉛筆0.5元/支。寫算法輸出各種組合方案。解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%”,i,j,k);

}

}例35解法2#defineN100voidscheme(){inti,j;for(i=0;i<=N/3;i++)for(j=0;j<=(N-3*i)/2;j++){if(3*i+2*j+0.5*(N-i-j)==N)printf(“%d,%d,%d\n%”,i,j,N-i-j);}}時間復雜度為T(N)=O(N2)

36表：時間復雜度和算法運行時間的關系T(n)nO(logn)O(n)O(nlogn)O(n2)O(n3)O(n5)O(2n)O(n!))204.3us20us86.4us400us8ms3.2s1.05s771世紀405.340213160064ms1.7min12.7天2.59*1032世紀605.9603543600216ms13min366世紀2.64*1066世紀37結論（1）當f(n)為對數函數、冪函數、或它們的乘積時，算法的運行時間是可以接受的，稱這些算法是有效算法；當f(n)為指數函數或階乘函數時，算法的運行時間是不可接受的，稱這些算法是無效的算法。（2）隨著n值的增大，增長速度各不相同，n足夠大時，存在下列關系：對數函數<冪函數<指數函數38

1．4算法與算法分析例2、算法空間復雜度

本課程中，用執行算法所需輔助空間的大小作為算法所需空間的度量。

設執行算法所需的輔助空間是問題規模n的某個函數g(n),則算法空間復雜度記作：S（n）=O(g(n))表示算法輔助空間的增長率與g(n)的增長率相同計算解法1先計算x的冪,存于power[]中,再分別乘以相應的系數coef[]#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];

for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}問題規模為n,算法時間復雜度:O(n)空間復雜度：O(N)39解法2#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}時間復雜度為O(n),空間復雜度為O(1)。40練習分析以下程序段的時間復雜度。1、for(i=1;i<n;i++){y=y+1;for(j=0;j<=2*n;j++)x++;}2、i=1; while(i<=n) i=i*2;41要統計某公司職員的基本情況，包括每個職員的編號、姓名、年齡、性別、工資例如：編號：姓名：年齡：性別：工資：intnum;charname[20];intage;charsex;floatpay;1．4算法與算法分析1.6C語言中的結構體類型

42定義結構體類型的一般形式為：struct

employee{

intnum;charname[20];intage;charsex;floatpay;}；struct

結構體名{類型說明成員1;類型說明成員2;類型說明成員3;……}；43（1）定義了結構體類型之后，再定義該類型的變量。定義格式為：1.6.1結構體變量的定義結構體類型標識符

結構體變量名structemployeezhang，wang;structemployee{intnum;charname[20];intage;charsex;floatpay;};結構體類型標識符結構體變量44引用結構體變量中成員的一般格式為：（2）結構體變量中結構體成員的引用結構體變量名.成員名

struct

employee{

intnum;charname[20];intage;charsex;floatpay;};structemployee

zhang，wang;小張各個信息：zhang.num;;zhang.age;zhang.sex;zhang.pay;小王各個信息：wang.num;;wang.age;wang.sex;wang.pay;45numnameagesexpay101lilin25m985.5102zhangming26f800103liuxin27f10001.6.2結構體數組

46例如：structemployee{ intnum; charname[20]; intage; charsex; floatpay;};structemployeeemp[3];

結構體數組的引用emp[0].name為"lilin"emp[2].pay為1000471.6.3指向結構體變量的指針變量structstudent_info{ intnumber; charname[20]; charsex; floatscore;};48structstudent_infostu1;2000stu1101李明M89.0stu1.number=101;=”李明”;stu1.sex=‘M’;stu1.score=89.0;&stu1

printf(“%d”,&stu1);200049structstudent_info*P;P20