第一篇：數(shù)據(jù)結(jié)構(gòu)講稿-第一次課-DS緒論
《數(shù)據(jù)結(jié)構(gòu)》教案
課程性質(zhì)和任務(wù)
本課程是計算機專業(yè)的主要專業(yè)基礎(chǔ)課程之一。本課程的參考教學時數(shù)為54學時，實際講課學時為35，實驗學時為16。其主要內(nèi)容包括順序表、鏈表、棧、隊、串、樹和圖的結(jié)構(gòu)，以及查找和排序技術(shù)。通過本課程的教學，使學生理解計算機軟件系統(tǒng)所必須的數(shù)據(jù)結(jié)構(gòu)及算法的內(nèi)部邏輯，掌握在軟件工程中大量存在的查找和排序技術(shù)，并通過大量的上機實習，實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的算法，以便為后續(xù)課程的學習提供專業(yè)基礎(chǔ)知識，同時增強學生編制程序的能力。
課程教學目標
通過本課程的學習，應(yīng)達到以下目標：
? 深刻理解數(shù)據(jù)結(jié)構(gòu)中線性表、棧、隊和鏈的概念、算法及其基本應(yīng)用。
? 理解樹的基本概念，學會建立二叉樹，并在二叉樹上進行查找、插入和刪除等各種運算。
? 理解圖的基本結(jié)構(gòu)和算法，了解圖的路徑問題。
? 熟練掌握幾種重要的內(nèi)部排序和查找技術(shù)，了解外部排序的一般過程。
? 能熟練地運用C語言，準確、清晰地編制與本課程有關(guān)的算法，并能上機調(diào)試通過。
新疆農(nóng)業(yè)大學數(shù)據(jù)結(jié)構(gòu)課程教案
第一講 緒論(對應(yīng)教材p1—p17)
一、教學目的和要求
要求掌握數(shù)據(jù)結(jié)構(gòu)中基本概念的定義，理解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容，了解抽象數(shù)據(jù)類型的表示和實現(xiàn)，理解算法評價的兩個指標。
二、授課主要內(nèi)容
1.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 2.數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念
3.算法的概念、描述方法以及評價標準
三、教學重點難點
數(shù)據(jù)結(jié)構(gòu)中的基本概念、算法的概念、描述方法以及評價標準
四、授課內(nèi)容和方法
【口述】當今計算機應(yīng)用的特點：所處理的數(shù)據(jù)量大且具有一定的關(guān)系；對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。
一、什么是數(shù)據(jù)結(jié)構(gòu)
我們大家知道許多非數(shù)值計算問題的數(shù)學模型常常是數(shù)學方程，如線性方程組、微分方程。所以這類非數(shù)值計算問題的解決就歸結(jié)于對數(shù)學模型設(shè)計算法、編寫程序。然而在現(xiàn)實社會中存在著許多非數(shù)值計算問題，其數(shù)學模型難以用數(shù)學方程描述。
1、舉例說明
? 圖書館的書目檢索自動化問題----計算機處理的對象之間存在著線性關(guān)系，稱為線性的數(shù)據(jù)結(jié)構(gòu)。
? 人機對奕問題----計算機處理的對象是一個個格局。所有可能出現(xiàn)的格局是一棵倒置的樹。
? 多岔路口交通燈的管理問題----數(shù)學模型是圖的數(shù)學結(jié)構(gòu)。
【由以上舉例引出下列結(jié)論：】
非數(shù)值計算問題的數(shù)學模型是表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)?！究偨Y(jié)出定義】 數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計算的程序設(shè)計問題中計算機操作對象以及它們之間關(guān)系和操作的一門學科。（三個要素：對象、關(guā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ù)學、計算機硬件、計算機軟件之間的一門核心課程。是設(shè)計和實現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)。
二、基本概念和術(shù)語
1、數(shù)據(jù) 數(shù)據(jù)：是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。是計算機
加工的“原料”。
數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數(shù)據(jù)項:有時，一個數(shù)據(jù)元素可由多個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。
2、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(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)是一個二元組
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={
① 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。
② 存儲結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)元素及其關(guān)系在計算機存儲器的表示。用于表示數(shù)據(jù)元素的位串稱之為元素或結(jié)點。用于表示數(shù)據(jù)項的位串稱之為數(shù)據(jù)域。
③ 數(shù)據(jù)的運算：對數(shù)據(jù)施加的操作。
算法的設(shè)計取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。
3、數(shù)據(jù)的兩種存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)：把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。通常順序存儲結(jié)構(gòu)是借助于語言的數(shù)組來描述的。
鏈式存儲結(jié)構(gòu)：不要求邏輯上相鄰的結(jié)點物理上也相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的，通常要借助于語言的指針類型來描述。
*
4、數(shù)據(jù)類型、抽象數(shù)據(jù)類型
數(shù)據(jù)類型:是一個值的集合和定義在這個值集上的所有的操作。例如，整數(shù)類型。數(shù)據(jù)類型可分為：非結(jié)構(gòu)的原子類型和結(jié)構(gòu)類型。
原子類型的值是不可分解的，結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。
抽象數(shù)據(jù)類型:是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念，它僅取決于數(shù)據(jù)類型的邏輯性，而與其在計算機內(nèi)部如何表示和實現(xiàn)是無關(guān)的。
抽象數(shù)據(jù)類型的定義由一個值域和定義在該值域上的一組操作組成。抽象數(shù)據(jù)類型按其值的不同特性，分為三種類型： ① 原子類型:變量的值是不可分解的。
② 固定聚合類型:變量的值由確定數(shù)目的成分按某種結(jié)構(gòu)組成。③ 可變聚合類型:其值的成分數(shù)目不確定。
抽象數(shù)據(jù)類型的形式定義：我們用一個三元組來表示一個抽象數(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)系運算的某個集合)} 數(shù)據(jù)關(guān)系：R1={〈e1,e2>,
InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）Get（T,i,&e）Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e)
Min(T,&e)
}ADT Triplet 多形數(shù)據(jù)類型:是其值的成分不確定的數(shù)據(jù)類型。
三、抽象數(shù)據(jù)類型的表示與實現(xiàn)
抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。
1、類C語言
精選了C 的一個子集，擴充修改，增強了語言的描述功能。? 預(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ù) ? 邏輯運算約定
例：Triplet的表示和實現(xiàn)
//采用動態(tài)分配的順序存儲結(jié)構(gòu)
Typedef ElemType * Triplet://由InitTriplet分配三個元素存儲空間 //基本操作的函數(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)//基本操作的實現(xiàn)
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //構(gòu)造三元組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、算法設(shè)計的要求
正確性、可讀性、健壯性和效率與低存儲量要求
3、算法效率的度量
算法時間是由控制結(jié)構(gòu)和原操作的決定的。做法：選取一種是基本操作的原操作，以該基本操作重復(fù)的次數(shù)作為算法的時間量度。
時間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f（n），T（n）=O（f（n））
它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長綠相同。
語句的頻度：是該語句重復(fù)執(zhí)行的次數(shù)。
例：求兩個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 時間復(fù)雜度是O(1),O(n)和O(n2)。時間復(fù)雜度有時與輸入有關(guān)。
4、算法的存儲空間需求
空間復(fù)雜度：S（n）=O（f（n））
五、作業(yè)布置
復(fù)習回顧c語言中關(guān)于結(jié)構(gòu)體和指針部分的內(nèi)容，以便于后期學習。
六、教學后記
按2 學時講完。
以前教學中反映出學生對抽象數(shù)據(jù)類型掌握不好，結(jié)構(gòu)體知識基本不懂，所以要求學生課下自學，下次課抽1學時學習結(jié)構(gòu)體和指針。
學生讀程序能力差，循環(huán)嵌套分析不出執(zhí)行次數(shù)?？紤]布置了一道題目練習。
第二篇：數(shù)據(jù)結(jié)構(gòu)DS復(fù)習_章節(jié)教案（模版）
《數(shù)據(jù)結(jié)構(gòu)》課程授課教案
課程名稱：數(shù)據(jù)結(jié)構(gòu) 英文名稱：Data Structure 學時數(shù)及學分：64＋32學時
4＋1學分 授課班級：2005級2班
教材名稱及作者、出版社、出版時間：
《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴蔚敏 吳偉民，北京：清華大學出版社，2004
一、課程的目的、要求和任務(wù)
《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)的一門必修的核心基礎(chǔ)課程。是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它對理論和實踐的要求都相當高，具有相當?shù)碾y度，且內(nèi)容較多。
本課程旨在討論現(xiàn)實世界中數(shù)據(jù)（即事物的抽象描述）的各種邏輯結(jié)構(gòu)在計算機中的存儲結(jié)構(gòu)，以及進行各種非數(shù)值運算的方法，讓學生學習、分析和研究計算機加工數(shù)據(jù)對象的特性，掌握數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，設(shè)計相應(yīng)的操作運算。在計算機應(yīng)用領(lǐng)域中，尤其是在系統(tǒng)軟件和應(yīng)用軟件的設(shè)計和應(yīng)用中都要用到各種數(shù)據(jù)結(jié)構(gòu)，這對提高軟件設(shè)計和程序編制水平都有很大的幫助。
二、課程主要教學內(nèi)容
本課程討論了軟件設(shè)計中經(jīng)常遇到的線性表、堆棧、隊列、串、數(shù)組、二叉樹、圖等典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法以及各種典型排序和查找算法的性能和設(shè)計方法，并介紹了各種典型數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。通過本課程的學習，學生對軟件設(shè)計的基本要素和軟件的基本結(jié)構(gòu)有了深入理解，并通過算法設(shè)計方法學習和上機編程實踐，編程能力有了進一步提高。
1.掌握主要內(nèi)容包括：線性表、堆棧、隊列、串、數(shù)組、樹、二叉樹、圖等典型數(shù)據(jù)結(jié)構(gòu)問題的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作的實現(xiàn)方法，各種典型的排序和查找算法，以及遞歸算法的設(shè)計方法；
2.掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點、機內(nèi)表示、處理數(shù)據(jù)的算法設(shè)計，以及算法分析、組織、處理數(shù)據(jù)的理論和方法，建立良好的編程風格；培養(yǎng)數(shù)據(jù)的抽象能力。
三、課程教學重點與難點
1.教學重點：線性表、棧、隊列、二叉樹、圖典型數(shù)據(jù)結(jié)構(gòu)問題的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作的實現(xiàn)方法，各種典型的排序和查找算法思想。2.教學難點：各種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用和進行操作實現(xiàn)。
四、參考書
1.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴蔚敏、吳偉民編著，清華大學出版社，2006年7月 2.《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》,王曉東,電子工業(yè)出版社,2002.3 3.《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習題與解析》,李春葆, 清華大學出版社 4.《數(shù)據(jù)結(jié)構(gòu)學習指導與典型題解》，朱占立等編著，西安交通大學出版社 5.《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》, 嚴蔚敏
吳偉民, 清華大學出版社 6.《數(shù)據(jù)結(jié)構(gòu)》 殷人昆 編著, 清華大學出版社
7.《數(shù)據(jù)結(jié)構(gòu)》 張選平雷永梅, 機械工業(yè)出版社，2002.1 第一章 緒論
1.教學內(nèi)容(1)(2)(3)(4)2.數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語； 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)； 抽象數(shù)據(jù)類型在軟件設(shè)計中的意義；
算法的概念和算法的時間和空間復(fù)雜度分析。
教學目的及要求(1)(2)(3)(4)掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，理解數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系； 抽象數(shù)據(jù)類型的表示和實現(xiàn)； 類C語言描述算法的機制； 掌握算法復(fù)雜性分析的方法和技巧。本課程的主要內(nèi)容；
數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，抽象數(shù)據(jù)類型，算法和算法的時間復(fù)雜度分析 抽象數(shù)據(jù)類型的表示和實現(xiàn) 算法的時間復(fù)雜度分析；
講授數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容以及在軟件分析和設(shè)計中意義； 講授抽象數(shù)據(jù)類型在軟件設(shè)計中的意義； 講授算法的概念和算法的時間復(fù)雜度分析方法； 例題講解算法的時間復(fù)雜度分析方法； 作業(yè)
對于重點和難點，通過例題討論講解。3.教學重點(1)(2)
4.教學難點(1)(2)
5.教學思路與教學方法(1)(2)(3)(4)(5)(6)
6.習題與思考題(1)填空題
a）數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個二元組B＝(D，S)來表示，其中D是_____，S是_____。b）存儲結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機器中的位置是否連續(xù)分為_____，_____。c）算法的基本要求有_____，_____，_____，_____，_____。d）度量算法效率可通過_____，_____兩方面進行。(2)簡述下列術(shù)語：
a）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu) b）數(shù)據(jù)的存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)； c）數(shù)據(jù)類型和抽象數(shù)據(jù)類型(3)(4)舉例說明一下數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系。
試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，并敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三方面的內(nèi)容。
例如：求下列算法的時間復(fù)雜度：
i=1;
while(i<=n)
i=i*3;答：O（logn）
第二章 線性表（8學時）
1.教學內(nèi)容(1)線性表的邏輯結(jié)構(gòu)特征；線性表上定義的基本運算，并利用基本運算構(gòu)造出較復(fù)雜的運算；(2)線性表的順序存儲結(jié)構(gòu)、a）特點；
b）基本操作的實現(xiàn)算法（初始化、插入、刪除、查找等）；(3)線性表的鏈式存儲結(jié)構(gòu)及基本操作的實現(xiàn)算法；
a）線性鏈表的特點、類型定義，以及基本操作（初始化、插入、刪除、查找等）的實現(xiàn)算法；
b）循環(huán)鏈表、雙向鏈表的定義、特點及操作的實現(xiàn)。
2.教學目的及要求(1)(2)(3)掌握線性表的邏輯特點；
掌握順序表的含義及特點，順序表上的插入、刪除操作是及其平均時間性能分析，解決簡單應(yīng)用問題。
掌握鏈表如何表示線性表中元素之間的邏輯關(guān)系；單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復(fù)雜度。(4)循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點。雙鏈表的定義和相關(guān)算法。利用鏈表設(shè)計算法解決簡單應(yīng)用問題。(5)3.領(lǐng)會順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能 教學重點(1)(2)(3)4.(1)(2)5.線性表的定義和抽象數(shù)據(jù)類型；順序和鏈式存儲結(jié)構(gòu)； 順序表的設(shè)計；
鏈表（單鏈表、循環(huán)鏈表、雙向鏈表）的設(shè)計。順序表操作的算法設(shè)計，以及單鏈表操作的算法設(shè)計； 完整應(yīng)用程序的結(jié)構(gòu) 教學難點
教學思路與教學方法(1)(2)講授本章節(jié)的基本概念，先邏輯結(jié)構(gòu)，后存儲結(jié)構(gòu)； 講授各存儲結(jié)構(gòu)下操作實現(xiàn)的主要思想；(3)(4)(5)6.在C++開發(fā)環(huán)境下，計算機演示完整應(yīng)用程序的結(jié)構(gòu)，以及編輯、編譯和運行的方法；
例題講解；對于重點和難點，通過程序演示，作業(yè)來突出。
輔助手段：多媒體演示＋板書
習題與思考題（見PPT課件，并完成實驗二的實驗題目）
教學內(nèi)容(1)(2)(3)(4)(5)棧的基本概念、特點，與一般線性表的區(qū)別；
棧順序表示和實現(xiàn)、鏈式表示和實現(xiàn)；
棧的典型應(yīng)用：數(shù)制轉(zhuǎn)換問題；括號匹配問題；棧與遞歸； 隊列的基本概念、特點，與一般線性表的區(qū)別；
順序隊列、順序循環(huán)隊列、鏈式隊列、隊列應(yīng)用；優(yōu)先級隊列。理解棧的概念；
掌握順序棧和鏈式棧的設(shè)計方法；
理解隊列的概念，掌握順序循環(huán)隊列和鏈式隊列的設(shè)計方法； 了解棧和隊列的應(yīng)用方法，掌握棧和隊列的基本應(yīng)用。第三章 棧和隊列（8學時）
1.2.教學目的及要求(1)(2)(3)(4)
3.教學重點(1)(2)順序棧和鏈棧的設(shè)計方法、典型應(yīng)用； 順序循環(huán)隊列和鏈式隊列的設(shè)計方法。棧和隊列的實現(xiàn)；
應(yīng)用棧實現(xiàn)表達式的求值；
順序隊列的假溢出現(xiàn)象，順序循環(huán)隊列的隊空和隊滿判斷方法。
課堂教學以課堂講授為主，采用多媒體教學方式以增大信息量，對重點和難點的算法的核心部分通過提問及增加板書進行詳細講解。(2)(3)(4)對算法的實現(xiàn)要求采用VC++ 開發(fā)環(huán)境，配合大屏幕投影演示，增強理論結(jié)合實際的效果和提高學生的學習興趣。
每次下課前布置若干思考題，待下次上新課前進行提問，或完成課堂練習，加強互動。
根據(jù)課程內(nèi)容，在講課中適當采取設(shè)立問題，請同學給出回答的方法加強師生互動，提高教學效果。4.教學難點(1)(2)(3)
5.教學思路與教學方法(1)
6.1.習題與思考題（見PPT課件，并完成實驗三的實驗題目）教學內(nèi)容 第四章 串（2學時）(1)(2)(3)2.(1)(2)(3)(4)3.(1)(2)4.5.串的基本概念、存儲結(jié)構(gòu)（順序存儲、鏈式存儲）、順序存儲結(jié)構(gòu)下基本操作的實現(xiàn)算法；
串的模式匹配：Brute-Force算法。
聯(lián)系C語言中串的存儲方法及串函數(shù)，并圍繞兩種基本存儲結(jié)構(gòu)進行分析。了解串類型的抽象數(shù)據(jù)類型定義； 熟悉串的有關(guān)概念，串和線性表的關(guān)系；
了解串的表示和實現(xiàn)（串的各種存儲結(jié)構(gòu)，比較它們的優(yōu)、缺點，從而學會在何時選用何種存儲結(jié)構(gòu)為宜）；
理解串的兩種模式匹配算法的思想、實現(xiàn)及時間復(fù)雜度的分析；
串的存儲結(jié)構(gòu)； 了解串的模式匹配。教學目的及要求
教學重點
教學難點
教學思路與教學方法(1)(2)(3)以課堂多媒體教學為主，輔助以黑板推導有關(guān)計算、繪圖分析；
課后做習題，并課外上機實驗，練習基本操作的實現(xiàn)及模式匹配的實例訓練，以鞏固課堂所學知識點。板書設(shè)計：
a）以文字描述為主，要點及關(guān)鍵詞用不同顏色標注； b）涉及有關(guān)存儲結(jié)構(gòu)、算法時，通過示意圖描述；(4)提問：
a）空串和空白串有無區(qū)別？
b）回顧：C語言中串的存儲方法及有關(guān)串函數(shù)。
6.習題與思考題（見PPT課件，并完成實驗四的實驗題目）
第五章 數(shù)組和廣義表（6學時）
1.教學內(nèi)容(1)(2)(3)(4)2.數(shù)組的定義及其實現(xiàn)機制；
特殊矩陣（包括n階對稱矩陣、n階三角矩陣）的壓縮存儲方法； 稀疏矩陣的壓縮存儲方法：三元組順序表、十字鏈表，以及稀疏矩陣實現(xiàn)轉(zhuǎn)置和相加運算；
廣義表的結(jié)構(gòu)特點、基本操作及其存儲表示方法
教學目的及要求(1)(2)理解了解數(shù)組的邏輯結(jié)構(gòu)和存儲表示；掌握數(shù)組在以行/列為主的存儲結(jié)構(gòu)中的地址計算方法；
掌握特殊矩陣的壓縮存儲方式及下標變換公式；(3)(4)了解稀疏矩陣壓縮存儲方法的特點和適用范圍，理解以三元組表示的稀疏矩陣進行矩陣運算采用的處理方法；
掌握廣義表的結(jié)構(gòu)特點極其存儲表示方法，以及對非空廣義表進行分解的兩種分析方法；
(5)3.(1)(2)(3)(4)4.5.(1)(1)(2)(3)(4)了解廣義表的遞歸算法設(shè)計。
稀疏矩陣的三元表存儲表示及稀疏矩陣轉(zhuǎn)置的兩種實現(xiàn)方法。多維數(shù)組的表示和實現(xiàn)； 特殊矩陣的壓縮存儲； 稀疏矩陣的壓縮存儲。
稀疏矩陣的十字鏈表的定義和建立算法。
從具體的矩陣實例出發(fā)，先分析其特點，然后圍繞以上知識點進行講述。以課堂多媒體教學為主，輔助以黑板推導有關(guān)計算、繪圖分析；
課后做習題，并上機實驗，練習特殊矩陣、稀疏矩陣的壓縮存儲方法，以鞏固課堂所學知識點。板書設(shè)計：
a）以文字描述為主，要點及關(guān)鍵詞用不同顏色標注； b）對壓縮存儲方法通過示意圖描述；
c）對于實例，通過鏈接到VC環(huán)境下實際運行。教學重點
教學難點
教學思路與教學方法
(5)(6)(7)重點突出：通過課堂強調(diào)與透徹分析，課后練習進行。
難點解決：通過實例講解，并在VC環(huán)境下實際運行實例，使學生真實體會算法設(shè)計全過程。師生互動設(shè)計：
a）提問：數(shù)組與線性表的區(qū)別與聯(lián)系？ b）回顧：線性表的兩種存儲結(jié)構(gòu)表示方法。
6.1.習題與思考題（見PPT課件，并完成實驗四的實驗題目）教學內(nèi)容(1)(2)(3)二叉樹的定義和性質(zhì)，性質(zhì)的應(yīng)用
二叉樹的存儲結(jié)構(gòu)（特別是二叉鏈表存儲結(jié)構(gòu)）
二叉樹的各種遍歷算法（先序、中序、后序、層次）及其應(yīng)用；能根據(jù)先序和中序，中序和后序確定一棵二叉樹。(4)(5)線索二叉樹的建立、遍歷的基本思想，能畫出按先序、中序、后序遍歷次序建立的線索二叉樹；
二叉樹的應(yīng)用—哈夫曼樹，哈夫曼編碼； 第六章 樹和二叉樹（10學時）(6)2.(1)(2)(3)3.(1)(2)(3)4.樹和二叉樹之間的轉(zhuǎn)換 樹與二叉樹的基本概念； 二叉樹的性質(zhì)與存儲結(jié)構(gòu)；
掌握二叉樹的遍歷算法和二叉樹問題的遍歷算法設(shè)計分析和實現(xiàn)。二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)；
二叉樹的遍歷算法和二叉樹遍歷算法的應(yīng)用； 哈夫曼樹在編碼方面的應(yīng)用方法。教學目的及要求
教學重點
教學難點(1)(2)二叉樹的性質(zhì)以及利用這些性質(zhì)分析問題的方法； 二叉樹問題的遍歷算法設(shè)計分析和實現(xiàn)。
講授本章節(jié)的基本概念，先邏輯結(jié)構(gòu)，后存儲結(jié)構(gòu)； 講授各存儲結(jié)構(gòu)下的實現(xiàn)的主要思想； 計算機演示存儲結(jié)構(gòu)下的實現(xiàn)； 例題講解； 作業(yè)
輔助手段：多媒體演示
對于重點和難點，通過程序演示，作業(yè)來突出。5.教學思路與教學方法(1)(2)(3)(4)(5)(6)(7)
6.習題與思考題（見PPT課件，并完成實驗五的實驗題目）
第七章 圖（10學時）
1.教學內(nèi)容(1)(2)2.(1)(2)(3)(4)(5)(6)(7)3.圖的基本概念、圖的存儲結(jié)構(gòu)；
圖的程序?qū)崿F(xiàn)、圖的遍歷、最小生成樹、最短路徑等。了解圖的定義和術(shù)語
掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)以及圖操作的實現(xiàn)方法； 理解圖的深度和廣度遍歷方法和算法設(shè)計方法； 了解圖的連通性問題極其判斷；
理解最小生成樹的概念、普里姆算法和克魯斯卡爾算法； 有向無環(huán)圖極其應(yīng)用（拓撲排序和關(guān)鍵路徑）；
了解最短路徑問題的基本概念和從一個結(jié)點到其余各結(jié)點最短路徑的算法。教學目的及要求
教學重點(1)(2)(3)圖的鄰接矩陣和圖的鄰接表存儲結(jié)構(gòu)； 圖的深度和廣度遍歷方法； 普里姆算法和克魯斯卡爾算法。4.5.教學難點(1)(1)(2)(3)(4)(5)(6)圖操作的實現(xiàn)方法。
課堂教學以課堂講授為主，采用多媒體教學方式以增大信息量；
圖中的概念很多，采取先講實例應(yīng)用，再總結(jié)概念定義的方法學習效果會好些；
對重點和難點算法的核心部分通過板書進行詳細講解。
對算法的實現(xiàn)要求采用VC++開發(fā)環(huán)境，配合大屏幕投影演示，增強理論結(jié)合實際的效果和提高學生的學習興趣。
每次下課前布置若干思考題，待下次上新課前進行提問。
根據(jù)課程內(nèi)容，在講課中適當采取設(shè)立問題，請同學給出回答的方法加強師生互動，提高教學效果。教學思路與教學方法
6.習題與思考題（見PPT課件，并完成實驗六的實驗題目）
第八章 查找（8學時）
1.教學內(nèi)容(1)(2)(3)(4)順序查找、二分查找、索引順序查找算法；
二叉排序樹的查找、插入與刪除算法；了解二叉平衡樹的基本概念 常用的哈希函數(shù)的設(shè)計方法：除留余數(shù)法、直接定址法、數(shù)字分析法；哈希沖突解決方法：開放地址法、鏈表法。
哈希表的完整設(shè)計過程，包括：哈希表的構(gòu)建、元素的插入與刪除、哈希表查找效率。
2.教學目的及要求(1)掌握靜態(tài)查找表的四種查找方法（順序查找、折半查找、靜態(tài)樹表、索引查找）的實現(xiàn)；(2)(3)3.掌握動態(tài)查找表（二叉排序樹、二叉平衡樹、B-和B+樹、鍵樹）的構(gòu)造和查找方法；
掌握哈希表構(gòu)造方法，哈希表的查找以及衡量查找效率的平均查找長度的討論。教學重點(1)(2)(3)4.5.二分查找；
二叉排序樹的查找； 哈希表查找。
教學難點(1)(1)哈希表中哈希函數(shù)的設(shè)計與哈希沖突解決方法。以課堂多媒體教學為主，輔助以黑板進行繪圖分析； 教學思路與教學方法(2)(3)課后完成上機實驗，練習二分查找、二叉排序樹查找及哈希表查找的算法設(shè)計，以鞏固課堂所學知識點。板書設(shè)計：
a）以文字描述為主，要點及關(guān)鍵詞用不同顏色標注； b）對查找、插入與刪除等算法通過示意圖描述； c）對于實例，通過鏈接到VC環(huán)境下實際運行。
(4)(5)(6)重點突出：通過課堂強調(diào)與透徹分析，課后練習進行。
難點解決：通過不同類型的實例講解，使學生理解并掌握常用的哈希函數(shù)設(shè)計方法以及哈希沖突的解決方法，并總結(jié)其優(yōu)、缺點。師生互動設(shè)計：
a）實例分析中引導學生參與算法設(shè)計；
b）提問：在每一種哈希函數(shù)的設(shè)計方法及哈希沖突的解決方法講解后，引導并提問學生此類方法的優(yōu)、缺點及解決途徑。
6.1.習題與思考題（見PPT課件，并完成實驗七的實驗題目）教學內(nèi)容(1)(2)排序算法的性能指標；
插入排序、選擇排序、交換排序、歸并排序、基數(shù)排序的算法設(shè)計與應(yīng)用。第九章 內(nèi)部排序（8學時）
2.教學目的及要求(1)(2)掌握排序的基本概念和排序算法的評判標準；
掌握如下排序的算法基本思想和設(shè)計方法，以及算法分析。a）直接插入排序 b）希爾排序 c）直接選擇排序 d）堆排序 e）快速排序 f）二路歸并排序 g）基數(shù)排序
3.4.5.教學重點(1)希爾排序、堆排序、快速排序、二路歸并排序和基數(shù)排序的算法思想； 教學難點(1)(1)(2)(3)(4)堆排序、快速排序、二路歸并排序和基數(shù)排序的算法設(shè)計方法。講授本章節(jié)的基本概念，先邏輯結(jié)構(gòu)，后存儲結(jié)構(gòu)； 講授各存儲結(jié)構(gòu)下的實現(xiàn)的主要思想； 計算機演示存儲結(jié)構(gòu)下的實現(xiàn)； 例題講解； 教學思路與教學方法(5)(6)(7)6.作業(yè)
輔助手段：多媒體演示
對于重點和難點，通過程序演示，作業(yè)來突出。
習題與思考題（見PPT課件，并完成實驗七的實驗題目）。
第三篇：湖州師范學院數(shù)據(jù)結(jié)構(gòu)DS大作業(yè)
求真學院
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大作業(yè)
20142832班
題
目： 專
業(yè)： 學生姓名： 學
號 指導教師 完成日期：
排序效率的比較 計算機科學與技術(shù)
邵
斌
湖州師院求真學院信息工程系
目錄一、二、三、四、五、六、七、實驗內(nèi)容概述...............................................................................................................................1 實驗?zāi)康母攀?..............................................................................................................................1 解題思路的描述...........................................................................................................................1 源程序清單...................................................................................................................................1 程序調(diào)試及測試結(jié)果...................................................................................................................8 結(jié)論...............................................................................................................................................9 參考文獻.....................................................................................................................................10
I
此處寫大作業(yè)題目（宋體三號，居中）
【內(nèi)容摘要】
200至300字左右，楷體BG2312五號
【關(guān)鍵字】XXXX，XXXXX，XXXXX，XXXXX(3到5個)數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素和集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率，處理各種問題。該程序是用C語言編寫的，它充分體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的理念與算法的魅力。該程序植入多種排序方法，這些排序方法的算法各具有特色，利用多種算法達到同一效果，正所謂“條條大路通羅馬”。并且，該程序還收集各算法的運行時間，通過對耗時的比較，為用戶挑選出兩種最優(yōu)化的排序方法。
關(guān)鍵字：排序 邏輯運算 數(shù)據(jù)結(jié)構(gòu) 時間復(fù)雜度
【Abstract】
中文摘要的翻譯，五號，Times New Roman
【Key words】XXXXX，XXXXX，XXXXX，XXXXX Data structure is the way of computer storage and organization data.A data structure is a data element and a set of data elements that have one or more specific relationships between each other.Typically, carefully selected data structures can be brought to a higher running or storage efficiency, processing a variety of problems.The program is written in C language, it fully reflects the concept of data structure and algorithm charm.The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achieve the same effect, is the so-called “all roads lead to Rome”.And, the program also collects the running time of each algorithm, through the time of the comparison, for the user to pick out two kinds of optimization of the sorting method.Keywords: sorting logic operation data structure time complexity
一、實驗內(nèi)容概述
對于直接插入排序、選擇排序、冒泡排序、Shell排序、快速排序和堆排序等幾種常見的排序算法進行練習，并且比較各算法在不同長度數(shù)據(jù)下的優(yōu)劣。
要求：（１）被排序的對象由計算機隨機生成，長度分別?。玻?，１００，５００三種。
（２）程序中要有對各種排序算法的比較，具體為比較次數(shù)和移動次數(shù)的統(tǒng)計。
（３）對課設(shè)的結(jié)果做比較分析
二、實驗?zāi)康母攀?/p>
1.鞏固和加深學生對數(shù)據(jù)結(jié)構(gòu)算法的理解，提高綜合運用所學課程知識的能力；
2.通過各個排序算法的實現(xiàn)，練習包括文件的讀寫、動態(tài)內(nèi)存的申請、函數(shù)的應(yīng)用、指針的應(yīng)用等多種最基本的C語言操作；
3.鍛煉學生的動手能力與培養(yǎng)其獨立思考的能力。
三、解題思路的描述
這是一個算法性能評價的程序，重點在于算法的性能評價上。實現(xiàn)排序功能可以有多種方法，判斷一個算法性能好壞的標準主要有時間復(fù)雜度和空間復(fù)雜度。在當今系統(tǒng)資源相對充足的計算機系統(tǒng)中，時間復(fù)雜度便成為最主要的評價標準。
對于每一個排序算法，都應(yīng)當有兩個返回值：比較次數(shù)和移動次數(shù)。這里采用指針傳遞地址的方式，通過修改形參的地址從而可以改變實參的值。每個排序算法中除了含被排序?qū)ο笾羔樛猓€有兩個整型變量指針，用于傳遞算法執(zhí)行過程中的比較次數(shù)和移動次數(shù)。
取定一種排序?qū)ο蟮拈L度，由計算機產(chǎn)生一定量的偽隨機數(shù)后，主函數(shù)調(diào)用各個排序子函數(shù)，但由于排序?qū)ο笠彩侵赶蛞痪S數(shù)組的指針，在調(diào)用一次一種排序算法后，通過形參對指針的改變，被排序?qū)ο笠呀?jīng)是有序的了。當再次調(diào)用其他函數(shù)時有可能使比較和移動次數(shù)達到最大或最小，就失去了比較的意義。因此，本程序中采用了子函數(shù)另開辟空間，參數(shù)只起到一個復(fù)制值的作用，在每個子函數(shù)結(jié)束前用delete()來釋放申請排序?qū)ο蟮闹羔?，避免程序出現(xiàn)內(nèi)存耗盡的情況。
四、源程序清單
主要包括： #include
void number(){ srand(time(0));int i,t;printf(“隨機數(shù)長度：n”);printf(“ 1.長度為20n”);printf(“ 2.長度為100n”);printf(“ 3.長度為500n”);printf(“輸入序號選擇長度:”);scanf(“%d”,&t);switch(t){ case 1: n=20;for(i=1;i<=n;i++){ a[i]=rand()%1000+1;//1-1000的隨機數(shù)
}break;case 2: n=100;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;case 3:n=500;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;} for(i=1;i<=len;i++)b[i]=a[i];printf(“隨機生成的%d個數(shù)如下：n”,len);for(i=1;i<=len;i++){ printf(“%d ”,a[i]);} printf(“n”);} typedef struct{ int key;//關(guān)鍵字
}RecordNode;//排序結(jié)點類型 typedef struct{ RecordNode *record;int n;//排序?qū)ο蟮拇笮?//srand函數(shù)是初始化隨機數(shù)的種子 }ElemType;//排序?qū)ο蟮念愋?直接排序
void InsertSort(ElemType A[], int n){ int i, j;ElemType x;for(i=1;i x = A[i];//準備插入第i個元素 for(j=i-1;j>=0;j--){ //從第i-1個開始往前找插入點 if(x.stn < A[j].stn)A[j+1]=A[j];else break;} A[j+1]=x;//插入 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比較次數(shù)：%d次n”,i);printf(“移動次數(shù)：%d次n”,j);} 直接選擇排序 void SelectSort(ElemType A[], int n){ int i, j, k;ElemType x;for(i=0;i<=n-2;i++){ //每一趟選擇最小元素并與A[i]交換 k=i;for(j=i+1;j<=n-1;j++)//查找最小元素的下標 if(A[j].stn void BubbleSort(ElemType A[], int n){ int i, j, flag;//flag為交換標記 ElemType x;for(i=1;i<=n-1;i++){ // 最多n-1趟排序flag=0;//假設(shè)本次沒有交換 for(j=n-1;j>=i;j--)//第i 趟 if(A[j].stn < A[j-1].stn){ flag=1;//出現(xiàn)交換 x=A[j];A[j]=A[j-1];A[j-1]=x;} if(flag==0)return;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比較次數(shù)：%d次n”,i);printf(“移動次數(shù)：%d次n”,j);} } Shell排序 void ShellSort(ElemType A[ ], int n,int dk) { int i,j,temp;ElemType x; for(i=dk;i 快速排序 void QuickSort(ElemType A[ ], int s, int t){ //遞歸算法，對區(qū)間 A[s] ～A[t] 進行快速排序 int i=s+1, j=t;ElemType temp, x = A[s];//第一個為基準元素 while(i<=j){ while(i<=j && A[i].stn <= x.stn)i++;//從左到右 while(i<=j && A[j].stn >= x.stn)j--;//從右到左 if(i < j){ temp=A[i];A[i]=A[j];A[j]=temp;i++;j--;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比較次數(shù)：%d次n”,i);printf(“移動次數(shù)：%d次n”,j);} } if(s!=j){ //交換基準元素 A[s]=A[j];A[j]=x;} if(s void CreatHeap(ElemType A[], int n){ int i;for(i =(n–2)/2;i >= 0;i--)Sift(A, n, i);//調(diào)整A[i..n-1]使之為一個堆 } void Sift(ElemType A[], int n, int i){ // 調(diào)整A[i..n-1]成為一個堆（它的左右子樹已是一個堆）ElemType x=A[i];int j = 2 * i + 1;// j為i的左孩子 while(j <= n-1){ // i有左子樹 if(j +1 < n && A[j].stn < A[j+1].stn)j++;// 使j指向左右孩子中排序碼大的孩子 if(x.stn < A[j].stn){ //使j指向左右孩子中排序碼大的孩子 A[i]=A[j];i=j;j=2*i+1;} else break;} A[i]=x;} void HeapSort(ElemType A[], int n){ //A為待排序表，n為表的長度 int i;ElemType x； CreatHeap(A, n);// 把A建成一個堆 for(i = n-1;i >= 1;i--){ x = A[0];//第0個元素與第i個元素交換 A[0] = A[i];A[i] = x;Sift(A, i, 0);//調(diào)整A[0..i-1]使之為一個堆 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比較次數(shù)：%d次n”,i);printf(“移動次數(shù)：%d次n”,j);} } Void main(){ int i,j,n,N=20;cout<<“ 各排序方法選擇結(jié)果：n”;ElemType A[20];for(j=0;j 算法的時間復(fù)雜度是什么？算法的空間復(fù)雜度是什么？為什么？ 插入排序：穩(wěn)定，時間復(fù)雜度 O(n^2)O(n2)選擇排序：不穩(wěn)定，時間復(fù)雜度 O(n^2)O(n2)冒泡排序：穩(wěn)定，時間復(fù)雜度 O(n^2)O(n2)希爾排序：不穩(wěn)定，時間復(fù)雜度平均時間 O(nlogn)最差時間O(n^s)1 程序調(diào)試及測試結(jié)果 主要包括： 選擇長度為20的隨機數(shù)，六種方法排序的結(jié)果。 從比較次數(shù)和移動次數(shù)可大致看出各排序方法的效率高低，后三種明顯優(yōu)于前三種 六、結(jié)論 主要包括： 隨機數(shù)產(chǎn)生方法：srand(time(0))就是給這個算法一個啟動種子，也就是算法的隨機種子數(shù)，有這個數(shù)以后才可以產(chǎn)生隨機數(shù),用1970.1.1至今的秒數(shù)，初始化隨機數(shù)種子。Srand是種下隨機種子數(shù)，你每回種下的種子不一樣，用Rand得到的隨機數(shù)就不一樣。為了每回種下一個不一樣的種子，所以就選用Time(0)，Time(0)是得到當前時時間值（因為每時每刻時間是不一樣的了）。 進行函數(shù)的參數(shù)傳遞時，如果傳入一個地址，比傳入一個struct效率要高，因為少了一個拷貝過程。待改進的地方：很多步驟有重復(fù)用到，如把數(shù)組b賦值給a，定義Ccnt，Rcnt等，可以做個初始化的函數(shù)調(diào)用，省去重復(fù)的代碼。可以增加其他排序方法進行效率比較。 七、參考文獻? [1] 唐國民, 王國鈞.數(shù)據(jù)結(jié)構(gòu) [M].北京:清華大學出版社, 2013: 213-238 [2] 張乃孝.算法與數(shù)據(jù)結(jié)構(gòu)——C語言描述[M].北京: 高等教育出版社, 2002 [3] 唐國民，王智群.C語言程序設(shè)計[M].北京:清華大學出版社, 2009:107-115 [4] 唐國民, 王國鈞.數(shù)據(jù)結(jié)構(gòu)實驗教程 [M].北京:清華大學出版社, 2013: 195-207 說明： 標為M的是書籍 標為D的為學位論文 標為J的為期刊 標為C的為會議論文 ?指導教師：邵 斌 日期：2016/6/5 實驗成績： 法律邏輯學教案 第一章 引 論 第一節(jié) 邏輯學的產(chǎn)生和發(fā)展 一、“邏輯”的含義 二、邏輯的產(chǎn)生 邏輯問題(亦即思維或論辯的正確性問題)成為人們的研究對象，幾乎同時起源于三個古老的國家，即古代的希臘、印度和中國。不過，真正形成較完整的學科體系并在世界各國流傳至今的，是古希臘的邏輯學，它作為一門獨立的學科出現(xiàn)，迄今已有2000多年。 在古希臘，當時雖然是奴隸主貴族政治時期，但生產(chǎn)力有了很大的發(fā)展。 一方面，社會政治生活中演講辯論的風氣盛行，不僅出現(xiàn)了一批專門以論辯為職業(yè)的人，而且還出現(xiàn)了一批專門培養(yǎng)所謂有智能、善辯論者的教師，即智者學派。 另一方面，古希臘的自然科學尤其是數(shù)學，特別是以歐幾里德為代表的“幾何學”有了很大發(fā)展。這不僅表現(xiàn)了人們已具有較高的抽象思維能力，而且，其證明本身就包含了邏輯知識。 古希臘邏輯科學的創(chuàng)始人是亞里士多德(公元前384年至公元前322年)。他的《工具論》一書奠定了邏輯科學的理論基礎(chǔ)，他被稱為“邏輯之父”。 《工具論》包括《范疇篇》 (即概念)，《解釋篇》(即命題與判斷)，《前分析篇》、《后分析篇》(即推理與證明)，《論辯篇》(即論辯常識)，《辯謬篇》 (即揭露詭辯的方法)，這本書對后世影響很大。 亞里士多德以后，直到中世紀，歐洲的邏輯學家在邏輯學的基本理論方面雖作了一些研究，但發(fā)展不大。 在我國，先秦時期的邏輯思想異?；钴S，社會上出現(xiàn)了“百家爭鳴”的文化局面。當時的諸子百家為使世人采納己見，便相互辯詰，其中有很多邏輯方面的知識?；菔⒐珜O龍、韓非和茍況等人，都提出了許多有價值的邏輯理論，特別是后期的墨家的邏輯理論就更加完整和系統(tǒng)。 《墨經(jīng)》是一部內(nèi)容非常豐富的邏輯專著，它包括《經(jīng)上》、《經(jīng)下》、《經(jīng)說上》、《經(jīng)說下》、《大取》、《小取》。在這部專著中，當今邏輯學所講的概念、判斷和推理等在《墨經(jīng)》中都已有論述。比如，《小取》篇中說： “以名舉實，以辭抒意，以說出故?！边@里的“名”相當于概念，“辭”相當于判斷，“說”相當于推理。它說明了概念是用來反映事物的，判斷是用來推導事物之間因果關(guān)系的。我國古代的邏輯學先后被稱做“名學”、“辯學”、“理則學”和“理論學”等。到了東漢時期，由于董仲舒倡導“罷黜百家，獨尊儒術(shù)”，此后的邏輯學說便趨于衰微了。 在古代印度，同樣是諸教紛紛興起，他們之間互相論爭，其中，勝論派和正理派開創(chuàng)了因明學?！耙颉敝竿评淼囊罁?jù)，“明”即通常所說的“學”，“因明”就是古代印度關(guān)于推理的學說。如陳那在《因明正理門論》中提出的“三支論式”認為，每一個推理形式都是由“宗”、“因”、“喻”三部分組成。這里所謂的“宗”相當于三段論中的結(jié)論，所謂“因”相當于三段論的小前提，所謂“喻”相當于三段論的大前提。 古希臘的邏輯學、印度的因明學和中國的名辯學，猶如三顆瑰麗的明珠，在世界古代邏輯史上交相輝映。 三、邏輯學的發(fā)展 16世紀以后，資產(chǎn)階級革命帶來了科學的革命，這一時期的自然科學發(fā)展迅速，使邏輯邏輯學得到了極大的豐富和發(fā)展，甚至可以說是經(jīng)歷了偉大的轉(zhuǎn)折。 例如，哥白尼的太陽中心說，笛卡爾的解析幾何，牛頓和萊布尼茨的微積分，伽利略的動力學，拉普拉斯的星云說，并且電磁波的發(fā)現(xiàn)，蒸汽機、渦輪機、電動機的發(fā)明都在這個時期。 英國唯物主義哲學家、被馬克思譽為 “整個近代實驗科學的真正始祖”的弗蘭西斯·培根，建立起歸納邏輯理論，主要著作《新工具》。 法國著名數(shù)學家笛卡爾則進一步完善了演繹法，并在歷史上第一次提出了關(guān)于推理過程中可以運用簡單的符號，建立“普遍數(shù)學’’的設(shè)想，給后繼者創(chuàng)立符號化的數(shù)理邏輯以啟迪。 17世紀法國波爾·羅亞爾修道院的阿爾諾和尼卡爾合寫并出版的邏輯著作，即被后人稱的“波爾·羅亞爾邏輯學”，更是大大地豐富和完善了原有邏輯學的內(nèi)容，成為近代邏輯學中最早的也最具代表 性的邏輯學教科書，流傳甚廣，影響深遠，可以說傳統(tǒng)邏輯學的主要內(nèi)容和體系，至此基本定型。 17世紀后半期，特別是18世紀以后，傳統(tǒng)邏輯在原有基礎(chǔ)上朝著兩個根本不同的方向發(fā)展。 一方面，人們基于傳統(tǒng)邏輯還不夠形式化而帶來的不精確、不系統(tǒng)的弊端，在傳統(tǒng)邏輯基礎(chǔ)上發(fā)展出了數(shù)理邏輯。 早在17世紀末期，德國數(shù)學家萊布尼茨在笛卡爾思想影響下就設(shè)想把數(shù)學方法應(yīng)用于邏輯，把邏輯推理變成純符號的邏輯演算，使邏輯成為一種證明藝術(shù)，并進行了開創(chuàng)性的研究工作。盡管他后來中斷了這一研究，設(shè)想未能實現(xiàn)，卻給邏輯的發(fā)展指出了新的方向，對后來數(shù)理邏輯的創(chuàng)建起到了重要作用，因而被公認為數(shù)理邏輯學奠基人。 此后，經(jīng)過19世紀末期英國數(shù)學家喬治·布爾、德·摩根，以及后來的德國數(shù)學家弗雷格和20世紀英國數(shù)學家羅素、懷特海等許多人的努力，前后經(jīng)歷了200年左右的時間，終于建立起了嚴密、完整、嶄新的邏輯體系——數(shù)理邏輯。 另一方面，在科學迅速發(fā)展的時代背景下，18世紀末期德國的一些哲學家卻從另一個角度批評了傳統(tǒng)邏輯的不足。他們基于傳統(tǒng)邏輯只研究思維的形式，沒有把思維的內(nèi)容和思維的形式統(tǒng)一起來；基于它只立足于思維的確定性而撇開了思維的變動性、辯證性，提出了研究辯證思維的問題，從而出現(xiàn)了辯證邏輯。 德國哲學家康德首先對傳統(tǒng)思維提出批評。他認為亞里士多德的 邏輯雖然完善，但它只研究思維的功能及其形式，不研究思維的內(nèi)容、來源，因此他把這樣的邏輯稱之為“形式邏輯”、“普通邏輯”，使傳統(tǒng)邏輯的這種稱謂流傳至今(不過，當代學術(shù)界更傾向于認為嚴格意義下的形式邏輯僅指數(shù)理邏輯，而把傳統(tǒng)邏輯稱為普通邏輯)。 繼康德之后，19世紀德國的辯證邏輯的創(chuàng)始人黑格爾在批評傳統(tǒng)邏輯的基礎(chǔ)上，努力用他的辯證法觀點來改造舊邏輯，建立新邏輯。他在《邏輯學》這一巨著中，系統(tǒng)地研究了思維的辯證或辯證思維的問題，勾畫出了一種新的——即辯證邏輯學科體系的輪廓。 自此也可以說又誕生了一種與傳統(tǒng)邏輯根本不同的、既是世界觀又是方法論的另一種意義上的邏輯——辨證邏輯。 第二節(jié) 法律邏輯學的性質(zhì)和研究對象 一、法律邏輯學的性質(zhì) 法律邏輯學是一門介于普通邏輯學和法律科學之間的交叉學科，是一門工具性質(zhì)學科。 二、法律邏輯學的研究對象 法律邏輯學的主要研究對象是法律思維形式及其規(guī)律。思維形式：是思維內(nèi)容與形式的統(tǒng)一，思維內(nèi)容是思維反映的特定對象及其本質(zhì)和規(guī)律；思維形式是思維賴以存在和表達的方式，即概念、判斷和推理。 思維的邏輯形式：是指思維形式的各部分之間的聯(lián)系方式。 例如： 所有金屬都是導電體。 所有出現(xiàn)尸斑的尸體都是死后２－４小時的尸體。所有哺乳動物都是用肺呼吸的動物。所有Ｓ都是Ｐ。又如： 如果死者背上有自己無法形成的致命傷，那么，死者是被人殺害的。 如果數(shù)Ｘ能被８整除，那么，數(shù)Ｘ能被４整除。如果p，那么q。 再如： 法律是有階級性的，刑法是法律，所以，刑法是有階級性的。 所有出現(xiàn)尸斑的尸體都是死亡后２－４小時的尸體，本案死者的尸體是出現(xiàn)尸斑的尸體，所以，死者的尸體是死亡后２－４小時的尸體。 Ｍ是Ｐ，Ｓ是Ｍ，所以，Ｓ是Ｐ。 邏輯形式是由邏輯常項和邏輯變項構(gòu)成。 邏輯常項：是思維形式中不變的部分。如：所有?都是? 如果?那么? 邏輯變項：是邏輯形式中可變的因素，即可以表示任何具體內(nèi)容的部分。 如：Ｓ、Ｐ、Ｍ、p、q Ｓ、Ｐ、Ｍ是詞項變項；p、q是命題變項。 法律邏輯學是我國高等院校法學專業(yè)的一門必修課。法律邏輯學具有很強的應(yīng)用性質(zhì),是結(jié)合案例分析而建立在普通邏輯原理基礎(chǔ)上的,是和語言邏輯學、教育邏輯學、醫(yī)療邏輯學等并列的形式邏輯的分支學科.由于高校的法律專業(yè)是為社會培養(yǎng)法律方面的人才,法律工作者必須掌握科學的思維素質(zhì)和嚴謹縝密的邏輯思維能力.作為訓練法學專業(yè)學生邏輯思維能力的學科,法律邏輯學成為法律專業(yè)一門重要的基礎(chǔ)課程。 云淡風清 http://gsqls.blog.163.com/ 第1章 數(shù)據(jù)結(jié)構(gòu)概述 1.1概述 以下為某市部分院校的交通地圖情況，要求找出從出發(fā)點到目的地之間的最短路徑及其長度。 對于此問題，如果手工去做，速度慢(特別地，現(xiàn)實中實際地圖信息要比此例復(fù)雜許多)，還容易出錯，此時可借助于計算機完成。 計算機進行此類信息的處理時，涉及到兩個問題：一是現(xiàn)實當中的信息在計算機中如何表示，二是如何對信息進行處理。 信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問題不斷復(fù)雜化，導致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復(fù)雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。 1.1.1編寫解決實際問題的程序的一般流程 如何通過編寫程序，以比手工更為高效精確的方式解決實際問題呢？一般流程如下： 1、由具體問題抽象出一個適當?shù)臄?shù)學模型； 2、分析問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系； 3、確定如何在計算機中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系？ 4、確定處理問題時需要對數(shù)據(jù)作何種運算？ 5、確定算法并編寫程序； 5、分析所編寫的程序的性能是否良好？若性能不夠好則重復(fù)以上步驟。 云淡風清 http://gsqls.blog.163.com/ 上面所列舉的問題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來回答。 《數(shù)據(jù)結(jié)構(gòu)》是計算機科學中的一門綜合性專業(yè)基礎(chǔ)課，是介于數(shù)學、計算機硬件、計算機軟件三者之間的一門核心課程，不僅是一般程序設(shè)計的基礎(chǔ)，而且是設(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è)有一個電話號碼薄，它記錄了N個人的名字和其相應(yīng)的電話號碼。要求設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。 姓名 電話號碼 陳偉海 *** 李四鋒 ***。。 這是一種典型的線性結(jié)構(gòu)。 2、磁盤目錄文件系統(tǒng) 磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推。 。。 本問題中各目錄從上到小形成了一種一對多的關(guān)系，是一種典型的樹形結(jié)構(gòu)。 云淡風清 http://gsqls.blog.163.com/ 3、交通網(wǎng)絡(luò)圖 下圖表明了若干個城市之間的聯(lián)系： 從圖中可看出，一個地方到另外一個地方可以有多條路徑，是一種典型的網(wǎng)狀結(jié)構(gòu)，數(shù)據(jù)與數(shù)據(jù)成多對多的關(guān)系。 4、排序問題 對100000個整數(shù)進行降序排序。冒泡法程序： #include a[i]=rand();printf(“n按原序輸出：n”);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://gsqls.blog.163.com/ for(i=1;i<=N;i++) printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include void quick_sort(int a[N+1],int left,int right){ int j,last,temp;if(left { //將劃分子集的元素(此處選中間元素)移動到最左邊 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++; } //對形成的新子集遞歸進行快速排序 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://gsqls.blog.163.com/ quick_sort(a,1,N);printf(“n按新次序輸出：n”);for(i=1;i<=N;i++) printf(“%8d”,a[i]);printf(“n”);} 運行可知，兩者速度差異非常明顯，主要是排序所花的時間差別很大?？煽闯?，同樣的問題，采用不同方法進行處理，有可能呈現(xiàn)出非常大的性能方面的差異。 還可以找到許多其它例子，如圖書館的書目檢索系統(tǒng)自動化問題，教師資料檔案管理系統(tǒng)，多叉路口交通燈的管理問題等。 1.2基本概念和術(shù)語 1.2.1數(shù)據(jù)(Data)： 是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。 1.2.2數(shù)據(jù)元素(Data Element)： 是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。 1.2.3數(shù)據(jù)對象(Data Object)： 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集，其中的數(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)。其要點有兩個方面：一是元素本身，二是元素之間的關(guān)系。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如下： 云淡風清 http://gsqls.blog.163.com/ ①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關(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ù)學形式的定義是一個二元組： DataStructure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B=(K，R)，其中： K={k1, k2, …, k9} R={ 1.2.5數(shù)據(jù)的物理結(jié)構(gòu)： 又稱存儲結(jié)構(gòu)，指數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲方式。 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關(guān)系的存儲。元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈式存儲結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(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ù)的； 鏈式結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面，一個算法的設(shè)計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。 在C語言中，用一維數(shù)組表示順序存儲結(jié)構(gòu)；通過結(jié)構(gòu)體類型實現(xiàn)的鏈表來表示鏈式存儲結(jié)構(gòu)。 1.2.6數(shù)據(jù)結(jié)構(gòu)(Data Structure)： 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計算機存貯器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。 1.2.7數(shù)據(jù)結(jié)構(gòu)的三個組成部分： 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述：D_S=(D，S)。 存儲結(jié)構(gòu)：數(shù)據(jù)元素在計算機中的存儲及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對數(shù)據(jù)要進行的運算。 本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲結(jié)構(gòu)如下圖所示。 云淡風清 http://gsqls.blog.163.com/ 邏輯結(jié)構(gòu)與所采用的存儲結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖 1.2.8數(shù)據(jù)類型(Data Type)： 指的是一個值的集合和定義在該值集上的一組操作的總稱。 數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。在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)的運算 數(shù)據(jù)結(jié)構(gòu)的主要運算包括： ⑴建立(Create)一個數(shù)據(jù)結(jié)構(gòu)； ⑵消除(Destroy)一個數(shù)據(jù)結(jié)構(gòu)； ⑶從一個數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個數(shù)據(jù)元素； ⑷把一個數(shù)據(jù)元素插入(Insert)到一個數(shù)據(jù)結(jié)構(gòu)中； ⑸對一個數(shù)據(jù)結(jié)構(gòu)進行訪問(Access)； ⑹對一個數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進行修改(Modify)； ⑺對一個數(shù)據(jù)結(jié)構(gòu)進行排序(Sort)； ⑻對一個數(shù)據(jù)結(jié)構(gòu)進行查找(Search)。 以上只列舉了一些常見運算，實際應(yīng)用當中可能會遇到許多其它運算。 云淡風清 http://gsqls.blog.163.com/ 1.4抽象數(shù)據(jù)類型(Abstract Data Type)1.4.1抽象數(shù)據(jù)類型簡介： 簡稱ADT，是指一個數(shù)學模型以及定義在該模型上的一組操作。ADT的定義僅是一組邏輯特性描述，與其在計算機內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學特性不變，都不影響其外部使用。 ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。說明： ⑴ADT和數(shù)據(jù)類型實質(zhì)上是一個概念，其區(qū)別是：ADT的范疇更廣,它不再局限于系統(tǒng)已定義并實現(xiàn)的數(shù)據(jù)類型，還包括用戶自己定義的數(shù)據(jù)類型。 ⑵ADT的定義是由一個值域和定義在該值域上的一組操作組成。包括定義，表示和實現(xiàn)三個部分。⑶ADT的最重要的特點是抽象和信息隱蔽。抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細節(jié)，使所設(shè)計的結(jié)構(gòu)更具有一般性，可以解決一類問題。信息隱蔽就是對用戶隱藏數(shù)據(jù)存儲和操作實現(xiàn)的細節(jié)，使用者了解抽象操作或界面服務(wù)，通過界面中的服務(wù)來訪問這些數(shù)據(jù)。 ADT不考慮物理結(jié)構(gòu)以及算法的具體實現(xiàn)。 例：整數(shù)的數(shù)學概念和對整數(shù)所能進行的運算構(gòu)成一個ADT，C語言中的變量類型int就是對這個抽象數(shù)據(jù)類型的一種物理實現(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)的出錯信息。 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。 1.5算法(Algorithm)1.5.1算法基本概念： 算法是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個或 云淡風清 http://gsqls.blog.163.com/ 多個操作。 1.5.2算法的基本特征： 算法具有以下五個特性 ①有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。 ②確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。 ③可行性：一個算法是能行的。即算法描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。 ④輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。 ⑤輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。 1.5.3算法的基本描述方法： 一個算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計算機程序設(shè)計語言描述等。 1.5.4算法與程序的異同比較： 算法和程序是兩個不同的概念。一個計算機程序是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn)。算法必須可終止意味著不是所有的計算機程序都是算法。 1.5.5評價算法好壞的幾個標準： 評價一個好的算法有以下幾個標準 ①正確性(Correctness)：算法應(yīng)滿足具體問題的需求。 ②可讀性(Readability)：算法應(yīng)易于供人閱讀和交流?？勺x性好的算法有助于對算法的理解和修改。 ③健壯性(Robustness)：算法應(yīng)具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法應(yīng)能適當?shù)刈龀龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。 ④通用性(Generality)：算法應(yīng)具有一般性，即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立。⑤效率與存儲容量需求：效率指的是算法執(zhí)行的時間；存儲容量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關(guān)。 1.6算法效率的度量 解決同一個問題的算法可能有多種，如何選擇一個效率高的算法呢？應(yīng)該來講，與算法效率相關(guān)的因素有很多，如下： 云淡風清 http://gsqls.blog.163.com/ 1、算法選用何種策略； 2、問題的規(guī)模； 3、程序設(shè)計的語言； 4、編譯程序所產(chǎn)生的機器代碼的質(zhì)量； 5、內(nèi)存的大??； 6、外存的大??； 7、機器執(zhí)行指令的速度； 8、其它。 而確定算法效率的方法通常有兩種： 1.6.1事后統(tǒng)計： 先實現(xiàn)算法，然后運行程序，測算其時間和空間的消耗。缺點： 1、必須先依據(jù)算法編制程序并運行程序，耗費人力物力； 2、依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣。由于算法的運行與計算機的軟硬件等環(huán)境因素有關(guān)，不容易發(fā)現(xiàn)算法本身的優(yōu)劣。同樣的算法用不同的編譯器編譯出的目標代碼數(shù)量不同，完成算法所需的時間也不同；若計算機的存儲空間較小，算法運行時間也就會延長； 3、沒有實際價值。測試花費不少時間但并沒有解決現(xiàn)實中的實際問題。 1.6.2事前分析： 僅僅通過比較算法本身的復(fù)雜性來評價算法的優(yōu)劣，不考慮其它的軟硬件因素，通常考查算法所用的時間和所需的存儲空間。 算法復(fù)雜性的度量可以分為時間復(fù)雜度和空間復(fù)雜度。 1.6.3算法的時間復(fù)雜度(Time complexity) 1、算法的時間復(fù)雜度 算法的時間復(fù)雜度用于度量一個算法所用的時間。 算法所用的時間主要包括程序編譯時間和運行時間。由于一個算法一旦編譯成功可以多次運行，因此可以忽略編譯時間，只討論算法的運行時間。 算法的運行時間依賴于加、減、乘、除、等基本的運算以及參加運算的數(shù)據(jù)量的大小，另外，與計算機硬件和操作環(huán)境等也有關(guān)系。要想準確地估算時間是不可行的，而影響算法時間最為主要的因素是問題的規(guī)模，即輸入量的多少。同等條件下，問題的規(guī)模越大，算法所花費的時間也就越長。例如，求1+2+3+?+n的算法，即n個整數(shù)的累加求和，這個問題的規(guī)模為n。因此，運行算法所需的時間T是問題規(guī)模n的函數(shù)，記作T(n)。 同等條件下，相同或類似的基本操作在真正程序運行過程中所花費的時間也差不多，這樣，如果兩個不同算法中一個所含基本操作多而另一個所含基本操作少，則包含基本操作少的算法其花費時間也就較少。因此，通常用算法中基本語句的執(zhí)行次數(shù)來作為度量算法速度快慢的依據(jù)，而這種度量時間復(fù)雜度的方法得出的不是時間量，而是一種增長趨勢的度量，即當問題規(guī)模n增大時，T(n)也隨之變大。換言之，當問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)為在漸進意義下的階，稱為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度，通常用大O記號表示。用數(shù)學語言通常描述為：若當且僅當存在正整數(shù)n和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱該算法的漸進時間復(fù)雜度為T(n)=O(f(n))。 一般地，常用最內(nèi)層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示時間復(fù)雜度。 2、時間復(fù)雜度分析舉例： 例：兩個n階方陣的乘法。 云淡風清 http://gsqls.blog.163.com/ 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，則總次數(shù)為： n×n×n=n3，時間復(fù)雜度為T(n)=O(n3)。 例： { ++x;s=0;} 分析：將x自增看成是基本操作，則語句頻度為1，即時間復(fù)雜度為O(1)。 如果將s=0也看成是基本操作，則語句頻度為2，其時間復(fù)雜度仍為O(1)，即常量階。只要T(n)不是問題規(guī)模n的函數(shù)，而是一個常數(shù)，它的時間復(fù)雜度則均為O(1)。例：以下程序段： for(i=1;i<=n;++i){ ++x;s+=x;} 分析：基本語句的語句頻度為：n，其時間復(fù)雜度為：O(n)，即為線性階。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){ ++x; s+=x;} 分析：基本語句的語句頻度為：n2，其時間復(fù)雜度為：O(n2)，即為平方階。 定理：若T(n)=amnm+am-1nm-1+?+a1n+a0是一個m次多項式，則T(n)=O(nm)，即復(fù)雜度表達式只取一個n趨向于無窮大時的同階無窮小表達式即可。 通過對算法復(fù)雜度的分析，總結(jié)出這樣一條結(jié)論，在計算任何算法的復(fù)雜度時，可以忽略所有低次冪和最高次冪的系數(shù)，這樣可以簡化算法分析，并使注意力集中在增長率上。 從本質(zhì)上來講，此種策略也就是只考慮對算法復(fù)雜度影響最大的因素而忽略次要因素。例：以下程序段： for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i,j]=x; } 云淡風清 http://gsqls.blog.163.com/ 分析：基本語句的語句頻度為： 1+2+3+?+n-2 =(1+n-2)×(n-2)/2 =(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，時間復(fù)雜度為O(n2)，即此算法的時間復(fù)雜度為平方階。 一個算法時間復(fù)雜度為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)(即零次多項式)來界定。而一個時間為O(n2)的算法則由一個二次多項式來界定。 3、常見表示時間復(fù)雜度的階： O(1)：常量時間階 O(n)：線性時間階 O(㏒n)：對數(shù)時間階 O(n㏒n)：線性對數(shù)時間階 O(nk)：k≥2，k次方時間階 4、常見時間復(fù)雜度大小關(guān)系分析： 以下六種計算算法時間復(fù)雜度的多項式是最常用的，其大小關(guān)系通常為： O(1) 當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨輸入數(shù)據(jù)集的不同而不同。例：素數(shù)的判斷算法。 void prime(int n)//n是一個正整數(shù) { int i=2;while((n%i)!=0 && i*1.0 i++;if(i*1.0>sqrt(n)) printf(“&d 是一個素數(shù)n”,n);else printf(“&d 不是一個素數(shù)n”,n);} 此例中執(zhí)行頻率最高的語句為i++;，此語句最少執(zhí)行0次，最多執(zhí)行sqrt(n)次，對于不同的n，執(zhí)行次數(shù)不確定。 對于此類算法，如果輸入數(shù)據(jù)不同，則算法運行時間也不同，因此要全面分析一個算法，需要考慮算法在最好、最壞、平均情況下的時間消耗。由于最好情況出現(xiàn)的概率太小，因此不具代表性，但是，當最好情況出現(xiàn)的概率大時，應(yīng)該分析最好情況；雖然最壞情況出現(xiàn)的概率也太小，不具代表性，但是分析最壞情況能夠讓人們知道算法的運行時間最壞能到什么程度，這一點在實時系統(tǒng)中很重要；分析平均情況是比較普遍的，特別是同一個算法要處理不同的輸入時，通常假定輸入的數(shù)據(jù)是等概率分布的。 例：冒泡排序法。 void bubble_sort(int a[],int n) 云淡風清 http://gsqls.blog.163.com/ { 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平均時間復(fù)雜度為：O(n2)1.6.4算法的空間復(fù)雜度(Space complexity) 1、算法的空間復(fù)雜度 算法的空間復(fù)雜度是指在算法的執(zhí)行過程中需要的輔助空間數(shù)量。輔助空間數(shù)量指的不是程序指令、常數(shù)、指針等所需要的存儲空間，也不是輸入數(shù)據(jù)所占用的存儲空間，輔助空間是除算法本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時開辟的存儲空間。算法的空間復(fù)雜度分析方法同算法的時間復(fù)雜度相似，設(shè)S(n)是算法的空間復(fù)雜度，通?？梢员硎緸椋?/p> S(n)=O(f(n))其中：n為問題的規(guī)模(或大小)。該存儲空間一般包括三個方面： 指令常數(shù)變量所占用的存儲空間； 輸入數(shù)據(jù)所占用的存儲空間； 輔助(存儲)空間。 一般地，算法的空間復(fù)雜度指的是輔助空間。如： 一維數(shù)組a[n]：空間復(fù)雜度O(n)二維數(shù)組a[n][m]：空間復(fù)雜度O(n*m)例：數(shù)組a中有10000個數(shù)，要求將所有數(shù)據(jù)逆置(即順序倒過來存放)。為達到逆置目的，有以下兩種方案： 方案一： 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://gsqls.blog.163.com/ { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明顯，方案二中的輔助空間數(shù)量為1，而方案一中的輔助空間數(shù)量為10000，方案二的空間復(fù)雜度優(yōu)于方案一。 在算法的時間復(fù)雜度和空間復(fù)雜度中，我們更注重算法的時間性能。因此，在對算法性能的分析當中，通常均主要針對算法時間性能進行分析。 1.6.5學習算法的原因 講述了這么多關(guān)于算法的基礎(chǔ)知識，究竟為什么要學習算法呢？ 首先，算法無處不在。算法不僅出現(xiàn)在數(shù)學和計算機程序中，更普遍地出現(xiàn)在我們的生活中，在生活中做什么事情都要有一定的順序，然而不同的順序帶來的效率和成果可能都會不同，只有學好了算法，才能讓生活更有趣、更有效率。 其次，算法是程序的靈魂。學習計算機編程，必須要掌握好其靈魂，否則，寫出來的程序就像是沒有靈魂的軀體。 再次，算法是一種思想。掌握了這種思想，能夠拓展思維，使思維變得清晰、更具邏輯性，在生活以及編程上的很多問題，也就更易解決。 最后，算法的樂趣。學習算法不僅僅是為了讓它幫助人們更有效地解決各種問題，算法本身的趣味性很強，當通過煩瑣的方法解決了一個問題后會感覺到有些疲憊，但是面對同一個問題，如若學會使用算法，更簡單有效地解決了這個問題，會發(fā)現(xiàn)很有成就感，算法的速度、思想會讓人覺得很奇妙。每一個奇妙的算法都是智慧的結(jié)晶。 學習算法的理由成千上萬，不同的人可能出于不同的目的去學習算法，希望大家能夠通過對課程的學習對算法有進一步的理解。 習題一 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)的主要運算包括哪些？ 4、算法分析的目的是什么？算法分析的主要方面是什么？ 云淡風清 http://gsqls.blog.163.com/ 第2章 線性表 下表為某電臺提供給聽眾的若干首英文歌曲名及相關(guān)點播情況統(tǒng)計信息： 由于實際的歌曲庫可能很大，手工管理效率低，不方便，現(xiàn)請設(shè)計一個軟件系統(tǒng)實現(xiàn)對此類歌曲庫的管理。 分析： 此例中相鄰的兩首歌之間是一種一對一的關(guān)系，屬于典型的線性結(jié)構(gòu)，可按線性結(jié)構(gòu)進行組織及管理。 2.1線性結(jié)構(gòu)與線性表 2.1.1線性結(jié)構(gòu) 如果一個數(shù)據(jù)元素序列滿足： ⑴除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個直接前驅(qū)數(shù)據(jù)元素和一個直接后繼數(shù)據(jù)元素； ⑵第一個數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素； ⑶最后一個數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。則稱這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。 線性表、棧、隊列、串和數(shù)組都屬于線性結(jié)構(gòu)。如下圖： 云淡風清 http://gsqls.blog.163.com/ 2.1.2線性表 線性表(Linear List)是一種最簡單、最常用的線性結(jié)構(gòu)，是一種可以在任意位置進行插入和刪除數(shù)據(jù)元素操作的、由n(n≥0)個相同類型數(shù)據(jù)元素a1，a2，?，an組成的線性結(jié)構(gòu)。在這種結(jié)構(gòu)中： ⑴存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素； ⑵存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素； ⑶除第一個元素外，每個元素均有唯一一個直接前驅(qū)； ⑷除最后一個元素外，每個元素均有唯一一個直接后繼。線性表中的數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時，稱為空表?？站€性表用符號()表示。 當n>0時，將非空的線性表記作：(a1，a2，?an)，其中符號ai(1≤i≤n)表示第i個抽象數(shù)據(jù)元素。 a1稱為線性表的第一個(頭)結(jié)點，an稱為線性表的最后一個(尾)結(jié)點。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)，其基本特點是可以在任意位置進行插入和刪除等操作，且數(shù)據(jù)元素是有限的。 線性表可以用順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)實現(xiàn)。用順序存儲結(jié)構(gòu)實現(xiàn)的線性表稱為順序表，用鏈式存儲結(jié)構(gòu)實現(xiàn)的線性表稱為鏈表。鏈表主要有單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表三種。順序表和鏈表各有優(yōu)缺點，并且優(yōu)缺點剛好相反，在實際應(yīng)用中要根據(jù)情況選擇對操作及性能有利的存儲結(jié)構(gòu)。 線性表中的數(shù)據(jù)元素ai所代表的具體含義隨實際應(yīng)用領(lǐng)域的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號。 ◆線性表中的結(jié)點可以是單值元素(每個元素只有一個數(shù)據(jù)項)。例1：26個英文字母組成的字母表：(A，B，C、?、Z)例2：某校從1978年到1983年各種型號的計算機擁有量的變化情況：(6，17，28，50，92，188)例3：一副撲克的點數(shù)：(2，3，4，?，J，Q，K，A)◆線性表中的結(jié)點可以是記錄型元素，每個元素含有多個數(shù)據(jù)項，每個項稱為結(jié)點的一個域。每個元素有一個可以唯一標識每個結(jié)點的數(shù)據(jù)項組，稱為關(guān)鍵字。 例4：某校2001級同學的基本情況：{(‘2001414101’，‘張里戶’，‘男’，06/24/1983)，(‘2001414102’，‘張化司’，‘男’，08/12/1984)?，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} ◆若線性表中的結(jié)點是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。◆線性表是一種相當靈活的數(shù)據(jù)結(jié)構(gòu)，其長度可根據(jù)需要增長或縮短。 ◆對線性表的基本操作如下(實際應(yīng)用中要根據(jù)需要選擇相應(yīng)操作或者添加未列出的操作)： ⑴建立空表L ⑵返回表L的長度，即表中元素個數(shù) ⑶取線性表L中位置i處的元素(1≤i≤n)⑷取i的直接前驅(qū)元素 ⑸取i的直接后繼元素 ⑹查詢元素x在L中的邏輯位置 ⑺在線性表L的位置i處插入元素x，原位置元素后移一個位置 ⑻從線性表L中刪除位置i處的元素 ⑼判斷線性表是否為空 ⑽清空已存在的線性表 ⑾遍歷所有元素 云淡風清 http://gsqls.blog.163.com/ ⑿根據(jù)所給關(guān)鍵字查詢元素并返回其詳細信息 ⒀修改表中元素 ⒁對所有元素按條件排序 2.1.3線性表的抽象數(shù)據(jù)類型定義 ADT List { 數(shù)據(jù)對象：D = { ai | ai∈ElemSet, i=1,2,?,n, n≥0 } 數(shù)據(jù)關(guān)系：R = { 操作結(jié)果：構(gòu)造一個空的線性表L； ListLength(L)初始條件：線性表L已存在； 操作結(jié)果：返回線性表中的元素個數(shù)； GetElem(L,i,e)初始條件：線性表L已存在，1≤i≤ListLength(L)； 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值； ListInsert(L,i,e)初始條件：線性表L已存在，1≤i≤ListLength(L)+1，線性表未滿； 操作結(jié)果：在線性表L中的第i個位置插入元素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個位置的值置為e； ListSort(L)初始條件：線性表L已存在； 操作結(jié)果：按一定條件對所有元素重新排序； ListDestroy(L)初始條件：線性表L已存在； 操作結(jié)果：釋放線性表空間； … 云淡風清 http://gsqls.blog.163.com/ } ADT List 2.2線性表的順序存儲 2.2.1線性表的順序存儲結(jié)構(gòu) 順序存儲：把線性表的結(jié)點按邏輯順序依次存入地址連續(xù)的一組存儲單元里。用這種方法存儲的線性表簡稱順序表。 順序存儲的線性表的特點： ◆線性表的邏輯順序與物理順序一致； ◆數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)的。設(shè)有非空的線性表：(a1，a2，?an)。順序存儲如下圖所示。 在具體的機器環(huán)境下，設(shè)線性表的每個元素需占用len個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置，則線性表中第i+1個數(shù)據(jù)元素的存儲位置Loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置Loc(ai)之間滿足下列關(guān)系： Loc(ai+1)=Loc(ai)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： Loc(ai)=Loc(a1)+(i-1)*len 高級語言中同一個數(shù)組的各個元素占用連續(xù)存儲單元，具有隨機存取(指存取同一數(shù)組各元素的時間開銷相同，不受所處位置的限制)的特性，故而在高級語言中通常用數(shù)組來存儲順序表。除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該表示線性表的長度屬性以方便某些操作，所以用結(jié)構(gòu)體類型來定義順序表類型。 #include -1 #define MAX_SIZE 100 //最大長度 typedef int Status;//狀態(tài) typedef int ElemType;//元素類型，可根據(jù)實際需要更改 typedef struct Sqlist { ElemType *Elem_Array;//線性表存儲空間地址 int Length;//線性表長度 } SqList;注意：C語言中數(shù)組的下標值是從0開始，第i個元素的下標值是i-1。 2.2.2順序表的基本操作 順序存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。 以下將對幾種主要的操作進行討論。#include 云淡風清 http://gsqls.blog.163.com/ #include -1 #define MAX_SIZE 100 //最大長度 typedef int Status;//狀態(tài) typedef int ElemType;//元素類型，可根據(jù)實際需要更改 typedef struct Sqlist { ElemType Elem_Array[MAX_SIZE];//線性表存儲空間地址 int Length;//線性表長度 } SqList;/* 1、初始化 構(gòu)造一個空的線性表 */ Status Init_SqList(SqList *L){ L->Length=0;return OK;} /* 2、測長度 返回線性表中的元素個數(shù) */ int Length_SqList(SqList *L){ return L->Length;} /* 3、取元素 用e返回L中第i個數(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)的元素下標為i-1 return OK;} else return ERROR;} 云淡風清 http://gsqls.blog.163.com/ /* 4、順序線性表的插入 在線性表L中的第i個位置插入元素e，原來位置及以后的元素都后移。要求1≤i≤ListLength(L)+1，線性表未滿。實現(xiàn)步驟： (1)將線性表L中的第i個至第n個結(jié)點后移一個位置。(2)將結(jié)點e插入到結(jié)點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()函數(shù)重新分配空間，擴大空間容量 return ERROR; else { //i-1位置以后的所有結(jié)點后移 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é)點 L->Length++;//線性表長度增1 return OK; } } /* 時間復(fù)雜度分析： 在線性表L中的第i個位置插入新結(jié)點，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復(fù)雜度。 設(shè)在線性表L中的第i個位置插入結(jié)點的概率為Pi，不失一般性，設(shè)各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動結(jié)點的次數(shù)為n-i+1。 總的平均移動次數(shù)：Einsert=∑pi*(n-i+1)(1≤i≤n)計算得：Einsert=n/2。 即在順序表上做插入運算，平均要移動表上一半結(jié)點，當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復(fù)雜度為O(n)。 */ /* 5、線性表元素位置查詢 返回元素e在L中的邏輯位置，不存在則返回0 云淡風清 http://gsqls.blog.163.com/ */ int Locate_SqList(Sqlist *L,ElemType e){ int i,found=0;//found用于表示是否找到，0：未找到 1：找到 i=0;//從第一個開始查詢 while((i if(L->Elem_Array[i]==e) found=1; else i++;if(found==1) return i+1;//返回邏輯位置編號 else return 0;//未找到，返回0 } /* 6、刪除指定位置元素 在線性表： L=(a1，?ai-1，ai，ai+1，?，an)中刪除結(jié)點ai(1≦i≦n)，使其成為線性表： L=(a1，?ai-1，ai+1，?，an)要求1≤i≤ListLength(L)，線性表未空。實現(xiàn)步驟： (1)將線性表L中的第i+1個至第n個結(jié)點依此向前移動一個位置。(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(“要刪除的數(shù)據(jù)元素不存在!n”); return ERROR; } else { //i位置以后的所有結(jié)點前移 for(k=i;k L->Elem_Array[k-1]=L->Elem_Array[k]; 云淡風清 http://gsqls.blog.163.com/ L->Length--;//線性表長度減1 return(OK); } } /* 時間復(fù)雜度分析： 刪除線性表L中的第i個元素，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復(fù)雜度。 設(shè)在線性表L中刪除第i個元素的概率為Pi，不失一般性，設(shè)刪除各個位置是等概率，則Pi=1/n，而刪除時移動結(jié)點的次數(shù)為n-i。 則總的平均移動次數(shù)：Edelete=∑Pi*(n-i) (1≤i≤n)計算得：Edelete=(n-1)/2 即在順序表上做刪除運算，平均要移動表上一半結(jié)點，當表長n較大時，算法的效率相當?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個元素，以下為具體內(nèi)容：n”,L->Length);for(i=0;i printf(“%8d”,L->Elem_Array[i]);printf(“n------------------END------------------n”);return OK;} /* 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://gsqls.blog.163.com/ 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] { 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) 云淡風清 http://gsqls.blog.163.com/ 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(“請輸入要刪除元素的位置：”);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://gsqls.blog.163.com/ 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(“輸入錯誤！n”); break; } } } 需要說明的是，本例沒有實現(xiàn)空間的動態(tài)分配，若要實現(xiàn)動態(tài)分配，可參照第三章“棧的動態(tài)順序存儲結(jié)構(gòu)”的做法。 2.2.3順序存儲線性表的特點 優(yōu)點：表中任意一個結(jié)點的存取很方便，可以進行隨機存取，處于不同位置上的結(jié)點的存取時間從理論上來說相同，也能進行插入和刪除操作。 缺點： (1)插入和刪除不方便。為保持連續(xù)存放，操作中需要移動大量元素。 (2)會造成空間的浪費以及不易擴充。所占空間通常情況下大小固定，處理長度變化較大的線性表時，分配空間大小不夠，會造成溢出；分配空間太大，會造成浪費。 2.3線性表的鏈式存儲 2.3.1線性表的鏈式存儲結(jié)構(gòu) 鏈式存儲：用一組任意(即不必要連續(xù))的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。 鏈表中結(jié)點所占用的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的，鏈表中結(jié)點的邏輯順序和物理順序不一定相同。 為了正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其直接后繼結(jié)點的 云淡風清 http://gsqls.blog.163.com/ 地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)，如下圖所示。 data：數(shù)據(jù)域，存放結(jié)點的值。 next：指針域，存放結(jié)點的直接后繼的地址。 鏈表通過每個結(jié)點的指針域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起。每一個結(jié)點只包含一個指針域的鏈表，稱為單鏈表。 為操作方便，總是在鏈表的第一個結(jié)點之前附設(shè)一個頭指針變量head指向第一個結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息(或存放鏈表長度等輔助信息)，此時通常稱為帶頭結(jié)點的單鏈表。當然，也可以讓頭結(jié)點的數(shù)據(jù)域存放有效數(shù)據(jù)，此時稱為不帶頭結(jié)點的單鏈表。相對而言，帶頭結(jié)點的單鏈表浪費了一個結(jié)點的數(shù)據(jù)域，但會給編程帶來一定方便。 帶頭結(jié)點的單鏈表其基本結(jié)構(gòu)如下： 說明： (1)整個鏈表由若干個結(jié)點組成，一個結(jié)點占用一個內(nèi)存塊，而每個結(jié)點又分為兩大部分：數(shù)據(jù)域和指針域，其中數(shù)據(jù)域存放用戶數(shù)據(jù)，指針域用于存放后一個結(jié)點的地址，通過指針域?qū)⑦壿嬌锨昂笙噜彽慕Y(jié)點連接起來，這樣，通過前一個結(jié)點指針域中存放的地址就可以找到后一個結(jié)點?？煽闯觯總€結(jié)點的指針域?qū)嶋H上充當了指針變量的角色，只要結(jié)點數(shù)可變，則意味著指針變量數(shù)也可變，而事實上結(jié)點所對應(yīng)的這些內(nèi)存塊完全可以多次動態(tài)分配，這也就意味著指針域(相當于指針變量)的個數(shù)可以根據(jù)需要動態(tài)調(diào)整，這就解決了前述的“程序中變量個數(shù)固定，但問題本身所需變量個數(shù)不定”的矛盾。 (2)設(shè)置一個頭指針變量指向首結(jié)點，在帶頭結(jié)點的單鏈表中，此結(jié)點不存放有效數(shù)據(jù)。(3)末尾結(jié)點的指針域設(shè)置為空“NULL”表示鏈表的結(jié)束，相當于字符串中的'
第四篇：緒論講稿
第五篇：數(shù)據(jù)結(jié)構(gòu)講稿