《數據結構》課程簡介一、課程性質與教學目的二、基本要求三、教學內容四、學分及學時分配五、參考書目六、前期課程及后續課程第一章一、課程性質與教學目的用計算機解決任何問題都需要進行數據表示和數據處理，而數據表示和數據處理正是《數據結構》要研究的內容。《數據結構》是計算機科學中一門綜合性的專業基礎課。主要介紹如何合理地組織數據、有效地存儲和處理數據，正確地設計算法以及對算法的分析和評價。通過本課程的學習，使學生深刻地理解數據結構的邏輯結構和物理結構的基本概念以及有關算法，培養基本的、良好的程序設計技能，編制高效可靠的程序，為學習操作系統、編譯原理和數據庫等課程奠定基礎。二、基本要求1.了解數據結構及其分類、數據結構與算法的密切關系。2.熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。3.掌握設計算法的步驟和算法分析方法。4.掌握數據結構在排序和查找等常用算法中的應用。5.初步掌握文件組織方法和索引技術。三、教學內容見書目錄學時：課程講授學時６４四、學分及學時分配五、參考書目嚴蔚敏等著《數據結構》清華大學出版社1997范策等著《算法與數據結構》機械工業出版社2004李春保《數據結構與習題解析》清華大學出版社1997謝楚屏等編著《數據結構》人民郵電出版社六、前期課程及后續課程前期：C語言，計算機基礎，離散數學后續：操作系統，數據庫等C語言版軟件與理論教研室張澤寶哈爾濱工程大學計算機科學與技術學院第一章緒論目錄第一章緒論第二章線性表第三章棧和隊列第四章串第五章數組和廣義表第六章樹和二叉樹第七章圖第八章查找第九章內部排序第十章文件

本章說明1.1數據結構1.2基本概念和術語1.3抽象數據類型的表示和實現1.4算法和算法分析本章說明本章的主要內容基本概念和術語抽象數據類型的表示與實現算法和算法分析（掌握時間復雜度和空間復雜度）本章與后續各章的關系本章是后續各章的準備1.1數據結構1．什么是數據結構我們大家知道許多非數值計算問題的數學模型常常是數學方程，如線性方程組、微分方程。所以這類非數值計算問題的解決就歸結于對數學模型設計算法、編寫程序。然而在現實社會中存在著許多非數值計算問題，其數學模型難以用數學方程描述。例1-1書目檢索自動化問題登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表計算機處理的對象之間存在著線性關系，稱為線性的數據結構。例1-2人機對奕問題樹……..……..…...…...…...…...CEDABABACADBABCBDDADBDCEAEBECED圖例1-3多岔路口交通燈的管理問題1968年美國克努特教授開創了數據結構的最初體系：數據的邏輯結構和存儲結構及其操作。數據結構是一門綜合性的專業課程，是一門介于數學、計算機硬件、計算機軟件之間的一門核心課程。是設計和實現編譯系統、操作系統、數據庫系統及其他系統程序和大型應用程序的基礎。

2.《數據結構》課程數據結構定義數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科主要研究和討論以下三個方面的問題:(1)數據集合中各數據元素之間所固有的邏輯關系,即數據的邏輯結構.(2)在對數據進行處理時,各數據元素在計算機中的存儲關系,即數據的存儲結構.(3)對各種數據結構進行的運算.1.2基本概念和術語1．數據2．數據對象、數據結構3．數據的兩種存儲結構4.數據類型、抽象數據類型數據：是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。是計算機加工的“原料”。數據元素:是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理，也稱節點或記錄數據項:有時，一個數據元素可由多個數據項組成。數據項是數據的不可分割的最小單位。1.2基本概念和術語1.數據數據對象：是性質相同的數據元素的集合，是數據的一個子集。例：整數數據對象是集合N={0，±1，±2，……}字母字符數據對象是集合C={“A”，“B”，……“Z”}數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。2.數據對象、數據結構1.2基本概念和術語根據數據元素間關系的基本特性，有四種基本數據結構：集合——數據元素間除“同屬于一個集合”外，無其它關系線性結構——一個對一個，如線性表、棧、隊列樹形結構——一個對多個，如樹圖狀結構——多個對多個，如圖數據結構的形式定義：數據結構是一個二元組

Data_Structure=(D,S)其中，D是數據元素的有限集,S是D上關系的有限集例1-4復數Complex=(C,R)例1-5課題小組Group=(P,R)P={T,G1,…,Gn,S11,…,Snm}1≤n≤3，1≤m≤2，R={R1,R2}R1={<T,Gi>|1≤i≤n,1≤n≤3,}R2={<Gi,Sij>|1≤i≤n,1≤j≤m,1≤m≤2,}1.2基本概念和術語位：在計算機中表示信息的最小單位，二進制數的一位位串：由若干個位組合，表示一個數據元素。（以后稱“元素”或“結點”）例：整數用一個字長（16位）表示，字符用8位表示子位串：表示一個數據項。（以后稱“數據域”）數據的邏輯結構—只抽象反映數據元素的邏輯關系數據的存儲（物理）結構—數據的邏輯結構在計算機存儲器中的實現1.2基本概念和術語數據的邏輯結構與存儲結構密切相關算法設計 取決于選定的邏輯結構算法實現 依賴于采用的存儲結構 存儲結構分為：順序存儲結構——借助元素在存儲器中的相對位置來表示數據元素間的邏輯關系鏈式存儲結構——借助指示元素存儲地址的指針表示數據元素間的邏輯關系3．數據的兩種存儲結構1.2基本概念和術語元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內容Loc(元素i)=Loc+（i-1)*m順序存儲1536元素21400元素11346元素3∧元素41345h存儲地址

存儲內容

指針

1345元素11400

1346

元素4

∧

…….

……..

…….1400元素21536

…….

……..

…….

1536

元素3

1346

鏈式存儲

h數據的邏輯結構數據的存儲結構數據的運算：檢索、排序、插入、刪除、修改等線性結構非線性結構順序存儲鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面：數據類型：是一個值的集合和定義在這個值集上的所有的操作。如，整型。數據類型可分為：非結構的原子類型和結構類型。原子類型的值是不可分解的結構類型的值是由若干成分按某種結構組成的。4.數據類型抽象數據類型數據類型在高級語言中指數據的取值范圍及其上可進行的操作的總稱例C語言中，提供int,char,float,double等基本數據類型，數組、結構體、共用體、枚舉等構造數據類型，還有指針、空(void)類型等。用戶也可用typedef

自己定義數據類型typedef

struct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;數據類型可以看成是已經實現了的數據結構。

抽象數據類型：

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

按抽象數據類型值的不同特性，分為三種類型：①原子類型:變量的值是不可分解的。②固定聚合類型:變量的值由確定數目的成分按某種結構組成。③可變聚合類型:其值的成分數目不確定。抽象數據類型的形式定義我們用一個三元組來表示一個抽象數據類型：（D，S，P） D是數據對象，S是D上的關系集，P是對D的基本操作。ADT抽象數據類型名{數據對象：〈數據對象的定義〉數據關系：〈數據關系的定義〉基本操作：〈基本操作的定義〉}ADT抽象數據類型名。數據對象和數據關系的定義用偽碼描述。數據基本操作的定義格式： 基本操作名（參數表） 初始條件：〈初始條件描述〉 操作結果：〈操作結果描述〉抽象數據類型格式：P8-9例1-6抽象數據類型三元組的定義：ADTTriplet{數據對象：D={e1，e2,e3|e1,e2,e3∈Elemset(定義了關系運算的某個集合)}數據關系：R1={〈e1,e2>,<e2,e3>〉基本操作：InitTriplet(&T,v1,v2,v3)//構造三元組T，e1,e2,e3分別被賦以參數v1,v2,v3的值DestroyTriplet（&T）//撤消三元組TGet（T,i,&e）//三元組T已存在，1=<i<=3

用e返回第i元的值Put(&T,i,e)//三元組T已存在，1=<i<=3

將T的第i元值變為e

IsAscending(T)//三元組T已存在，1=<i<=3

三元素若升序排列返回1，否則返回0

IsDescending(T)Max(T,&e)Min(T,&e)}ADTTriplet多形數據類型：是其值的成分不確定的數據類型。如例1-6中定義的抽象數據類型Triplet，其元素e1,e2,e3可以是整數或字符串，也可以是由多種成分構成。1.3抽象數據類型的表示與實現

抽象數據類型可通過固有數據類型來表示和實現，即利用處理器中已存在的數據類型來說明新的結構，用已經實現的操作來組合新的操作。精選了C的一個子集，擴充修改，增強了語言的描述功能。預定義常量和類型數據結構的表示：存儲結構用類型（typedef）定義來描述。數據元素類型約定為ElemType.基本操作的算法用函數描述：1．類C語言P10-11函數類型函數名（函數參數表）{//算法說明語句序列 }//函數名增加了引用調用的參數傳遞方式。賦值語句、選擇語句(ifelse,switch)、循環語句(for,while,dowhile)、結束語句、輸入輸出語句(scanf,printf)、注釋語句基本函數邏輯運算約定:&&||例1-7Triplet的表示和實現//--采用動態分配的順序存儲結構Typedef

ElemType*Triplet;//由InitTriplet分配三個元素存儲空間//--基本操作的函數原型說明StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3)StatusDestroyTriplet（&T）StatusGet（T,i,&e）

StatusPut(&T,i,e)StatusIsAscending(T)StatusIsDescending(T)StatusMax(T,&e)StatusMin(T,&e)//--基本操作的實現

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//構造三元組T，依次置T的三個元素的處值為v1,v2和v3。T=(ElemType*)malloc(3*sizeof(ElemType));//分配三個元素的存儲空間If(!T)exit(OVERFLOW);//分配存儲空間失敗T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}//InitTripletStatusDestroyTriplet（Triplet&T）{//銷毀Tfree(T);T=NULL;returnOK;}//DestroyTripletStatusGet（TripletT,int

i,ElemType&e）{//1=<i=<3,用e返回T的第i元的值if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}//GetStatusPut（TripletT,int

i,ElemType&e）{//1=<i=<3,用e返回T的第i元的值if(i<1||i>3)returnERROR;T[i-1]=e;returnOK;}//PutStatusMax（TripletT,ElemType&e）{//用e返回指向T的最大元素值e=(T[0]>=T[1])?((T[0]<=T[2])?T[0]:T[2])

:((T[1]>=T[2])?T[1]:T[2]);returnOK;}//Max1.4算法和算法分析1．算法（Algorithm）

是對特定問題求解步驟的一種描述，它是指令的有限序列。算法的重要特性：有窮性——算法必須在執行有限步驟后結束確定性——算法的每一步必須是確切定義的，不能產生二義性可行性——算法是能實現的輸入——一個算法有零個或多個輸入輸出——一個算法有一個或多個輸出1.4算法和算法分析2．算法設計的要求——衡量算法優劣的標準

正確性可讀性健壯性效率與低存儲量要求3．算法效率的度量算法效率——用依據該算法編制的程序在計算機上執行所消耗的時間來度量。（算法時間是由控制結構和原操作的決定的）記號——引用了“O”。“O”表示一個數量級的概念。本書中根據算法中語句執行的最大次數（頻度）來估算一個算法執行時間的數量級。時間復雜度：算法中基本操作重復執行的次數是問題規模n的某個函數f（n），T（n）=O（f（n））它表示隨問題規模n的增大，算法執行時間的增長率和f（n）的增長率相同。語句的頻度：是該語句重復執行的次數。1.4算法和算法分析#definen100voidMatrixMultiply(int

A[n][n],int

B[n][n],intC[n][n]){ inti,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) C[i][j]=C[i][j]+a[i][k]*b[k][j];//n3}}T(n)=n+1+n*(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1量級：T(n)=O(n3)例：求兩個n階方陣的乘積C=A×B例：（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)。時間復雜度有時與輸入有關。亦可如上作類似分析。空間復雜度：S（n）=O（f（n））（略）4．算法的存儲空間需求主要介紹了數據結構的基本概念，分類，算法分析評價。

小結1.簡述下列術語：數據、數據元素、數據對象、數據結構、存儲結構、數據類型和抽象數據類型。

2.在程序設計中，常用下列三種不同的出錯處理方式：

(1)用exit語句終止執行并報告錯誤；

(2)以函數的返回值區別正確返回或錯誤返回；

(3)設置一個整型變量的函數參數以區別正確返回或某種錯誤返回。

試討論這三種方法各自的優缺點，并編寫算法，計算i!×2i的值并存入數組a[0..arrsize-1]的第i-1個分量中(i=1,2,…,n)。假設計算機中允許的整數最大值為maxint，則當n>arrsize

或對某個k(1≤k≤n)使k!×2k>maxint

時，應按出錯處理。注意選擇你認為較好的出錯處理方法。

課后習題3.在程序設計中，可采用下列三種方法實現輸出和輸入：

(1)通過scanf

和printf

語句；

(2)通過函數的參數顯式傳遞；

(3)通過全局變量隱式傳遞。

試討論這三種方法的優缺點，并編寫算法求一元多項式的值，并確定算法中