第1章緒論第1章緒論1.1數(shù)據結構概述1.2數(shù)據的邏輯結構

1.3數(shù)據的存儲結構1.4算法和算法的效率1.5實驗預備知識 2重難點數(shù)據結構中的常用基本概念和術語

四種邏輯結構及其描述四種存儲結構，及其與算法的關系算法的描述和復雜度分析算法時間和空間復雜度的計算方法C++中的引用變量和引用參數(shù)C語言復習：指針、結構體、文件、數(shù)字菜單31.1數(shù)據結構概述1.1.1數(shù)據結構研究的內容什么是數(shù)據結構？數(shù)據

——特指數(shù)據元素，現(xiàn)實世界中存在的一個獨立個體的相關信息(結構體變量、對象、記錄)，也稱之為結點。結構

——數(shù)據元素之間存在的關系。邏輯結構：指數(shù)據元素之間的邏輯關系。存儲結構：也稱物理結構，指數(shù)據的邏輯結構在計算機中的實現(xiàn)。算法

——解決問題方法(步驟)的描述。4數(shù)據結構＝數(shù)據＋(邏輯、存儲)結構＋少量算法1.1.1數(shù)據結構研究的內容所謂數(shù)據元素，就是C語言中的結構體變量例如：書籍元素——Book結構體類型可以根據需要，在Book結構體中增加出版社、出版年份、版本號和印數(shù)等成員。5typedef

struct{

charisbn[16];

chartitle[32];

charauthor[16];

intpages;

doubleprice;}Book;數(shù)據項1.1.1數(shù)據結構研究的內容所謂數(shù)據元素，就是C語言中的結構體變量例如：學生元素——Student結構體類型可以根據需要，將成員score定義為數(shù)組，以便存儲多門課程的成績；還可以將成員age改名為birthday，將其定義為日期類型等。6typedef

struct{

charstuId[16];

charname[16];

chargender;

intage;

doublescore;}Student;數(shù)據項1.1.2典型數(shù)據結構舉例用計算機解決具體實際問題的步驟：(1)從問題抽象出適當?shù)臄?shù)學模型(對象、關系)；(2)分析邏輯結構(提取數(shù)據元素、建立邏輯關系)(3)根據邏輯結構的主要操作，確定存儲結構(4)基于選定的存儲結構，設計求解數(shù)學模型的算法(解決問題的方法)；(5)編寫程序、運行并調試，直到解決問題。71.1.2典型數(shù)據結構舉例數(shù)據存儲結構的選擇，依賴于邏輯結構；算法的設計，必須基于數(shù)據的存儲結構；例如：81.1.2典型數(shù)據結構舉例——線性結構【例1-1】學生入學情況登記表91.1.2典型數(shù)據結構舉例——樹形結構【例1-2】井字棋對弈問題10七橋問題1.1.2典型數(shù)據結構舉例——圖形結構【例1-3】七橋問題11歐拉回路1.2數(shù)據的邏輯結構——四種集合結構樹形結構(一對多)12線性結構(一對一)圖形結構(多對多)ABCDEF沒有前驅，有且僅有一個后繼。沒有后繼，有且僅有一個前驅。ABECDFGRABCDEGHFIJK一個雙親，多個孩子。邊為鄰接關系1.2數(shù)據的邏輯結構——四種(1)集合結構數(shù)據元素之間，除了“同屬于一個集合”的關系外，別無其它關系。(2)線性結構(線性表、棧、隊列、串)數(shù)據元素之間，存在著“一對一”的關系。(3)樹形結構(樹、二叉樹)數(shù)據元素之間，存在著“一對多”的關系。(4)圖形結構(圖、網)數(shù)據元素之間，存在著“多對多”的關系。131.2.1基本概念數(shù)據(Data)數(shù)據是信息的載體，是對客觀事物的符號表示。通俗的說，凡是能被計算機識別、存取和處理的符號、圖形、圖像、聲音、視頻信號等都可以稱之為數(shù)據。數(shù)據元素(DataElement)數(shù)據元素是對現(xiàn)實世界中，某個獨立個體的數(shù)據描述，是數(shù)據的基本單位。數(shù)據元素俗稱為結點(Node)，也稱其為記錄(record)，在計算機中常作為一個整體來處理。141.2.1基本概念數(shù)據項(DataItem)數(shù)據項是不可分割的、具有獨立意義的最小數(shù)據單位，是對數(shù)據元素屬性的描述。數(shù)據項也稱為域，或字段(Field)。數(shù)據對象(DataObject)

數(shù)據對象是相同數(shù)據元素的集合；例如：在“學生入學情況登記表”中，數(shù)據對象是全體學生記錄(數(shù)據元素)的集合。數(shù)據的邏輯結構(DataStructure)相互之間存在特定關系的數(shù)據元素的集合。151.2.1基本概念直接前驅每個數(shù)據元素的前面，緊挨著它的那個元素，稱為它的直接前驅，可簡稱為前驅(precursor)。直接后繼每個數(shù)據元素的后面，緊挨著它的那個元素，稱為它的直接后繼，可簡稱為后繼(next)。線性結構中，第一條記錄沒有直接前驅，稱為開始結點；最后一條記錄沒有直接后繼，稱為終端結點。16ABCDEF開始結點終端結點1.2.2邏輯結構的描述數(shù)據元素之間的邏輯關系，稱為邏輯結構。邏輯結構可以用二元組來表示G=(D,R)其中：D是數(shù)據元素的集合；R是D上所有數(shù)據元素之間關系的集合。一種數(shù)據結構Line=(D,R)其中:D={01,02,03,04,05,06,07,08,09,10}R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>, <07,04>,<04,06>,<06,09>,<09,10>}17050103080207040609101.2.2邏輯結構的描述一種數(shù)據結構Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>, <02,07>,<03,08>,<03,09>,<04,10>}18010208030706050409101.2.2邏輯結構的描述一種數(shù)據結構Graph=(D,R)，其中：D={a,b,c,d,e}R={(a,b),(a,d),(b,d),(b,c),(b,e),(c,d),(d,e)}圓括號表示無向邊(雙向)，尖括號表示有向邊。19badce1.3數(shù)據的存儲結構——四種數(shù)據元素及它們之間的關系，在計算機存儲器中的表示，稱為數(shù)據的存儲結構。常用的存儲結構有四種:(1)順序存儲順序存儲結構的特點，是借助元素在存儲器中的相對位置，來表示數(shù)據元素之間的邏輯關系。(2)鏈式存儲借助指示元素存儲地址的指針(Pointer)，來表示數(shù)據元素之間的邏輯關系。201.3數(shù)據的存儲結構——四種(3)索引存儲索引存儲是在原有存儲結構的基礎上，建立一個索引表，索引表中的每一項都由關鍵字和地址組成。索引表的主要作用是為了提高數(shù)據的檢索速度。漢語字典的組織方式，就是典型的索引存儲。(4)散列存儲(哈希存儲)通過構造散列(Hash，哈希)函數(shù)的方式，由數(shù)據元素的關鍵字計算確定其存儲或查找地址的方式，稱為散列存儲。211.3數(shù)據的存儲結構——四種(1)順序存儲——數(shù)組優(yōu)點：可以隨機訪問(或存取)指定元素；缺點：插入或刪除需移動大批元素，效率很低。(2)鏈式存儲——鏈表優(yōu)點：插入或刪除非常方便；缺點：所有元素只能順序訪問。(3)索引存儲——類似漢語字典的組織方式查找效率高，但是需要構造并維護索引表。(4)散列/哈希存儲——哈希表效率取決于哈希函數(shù)，數(shù)據元素可能發(fā)生碰撞。221.4算法和算法的效率算法(Algorithm)算法就是方法(method)，是對特定問題求解步驟的描述，是指令的有限序列。其中每一條指令(或語句)，表示一個或多個操作。算法的特性有窮性：有限步數(shù)，且每步在有限時間內完成確定性：每條指令必須有確切的定義，無二義性可行性：可以通過有限次運算實現(xiàn)，得到正確結果輸入：有0個或多個輸入輸出：有1個或多個輸出231.4算法和算法的效率程序、算法與數(shù)據結構的關系一個算法必須在有窮步之后結束；一個程序不一定滿足有窮性(例如：死循環(huán))。程序中的指令必須是機器可執(zhí)行的，而算法中的指令無此限制。算法代表了對問題的求解過程，而程序則是算法在計算機上的實現(xiàn)；算法用特定的程序設計語言來描述，就成了程序。算法與數(shù)據結構是相輔相承的。241.4算法和算法的效率一個好算法應達到的目標正確性：算法應能滿足設定的功能和要求。可讀性：思路清晰、層次分明、易讀易懂。健壯性：輸入非法數(shù)據時，算法應能有適當?shù)姆磻吞幚?。健壯性也稱為魯棒性(robust)。高效性：解決同一問題時，所花的時間越短，算法的效率就越高。低存儲量：完成同一功能，算法占用的存儲空間應盡可能少。好算法的首要目標——高效性251.4算法和算法的效率算法效率的兩種度量方法事后統(tǒng)計法必須先運行按照算法編寫的程序。運行時間的統(tǒng)計依賴于計算機硬件和軟件的環(huán)境，容易掩蓋算法本身的優(yōu)劣。事先估算法使用何種程序設計語言；采取怎樣的算法策略；算法涉及的問題規(guī)模；編譯程序產生的目標代碼的質量；機器執(zhí)行指令的速度。算法效率的評價——通常只考慮算法策略261.4算法和算法的效率算法效率的評價指標時間復雜度——隨問題規(guī)模的增大，算法所需運行時間增長的函數(shù)；空間復雜度——隨問題規(guī)模的增大，算法運行時所占存儲空間增長的函數(shù)；重點是時間復雜度，因此有時會用空間換時間。271.4算法和算法的效率時間復雜度(TimeComplexity)把算法中所需執(zhí)行的簡單操作的次數(shù)T(n)

，稱作算法的時間復雜度。沒有必要精確計算算法的執(zhí)行時間(即語句條數(shù))，只要大致算出T(n)的數(shù)量級(Order)即可。若函數(shù)f(n)和T(n)同階，則將算法時間多項式T(n)的數(shù)量級記為O(f(n))，通?？捎涀鳎篢(n)=O(f(n))它表示隨著問題規(guī)模n的增長，執(zhí)行時間T(n)的增長率和函數(shù)f(n)的增長率相同，稱作算法的漸近時間復雜度，簡稱時間復雜度。281.4算法和算法的效率

291.4算法和算法的效率【例1-8】交換變量a和b的值的另一種方法。方法②：a=a+b;b=a-b;a=a-b;方法②的策略，從細節(jié)上看，是典型的用時間換空間，通過多做加減運算的耗時，少用了臨時變量t。30時間空間時間復雜度和空間復雜度，往往無法同時達到最優(yōu)，更多的時候需要去權衡，去找到一個平衡！1.4算法和算法的效率

31T(n)的同階無窮小只要為常數(shù)即可1.4算法和算法的效率對于足夠大的n，常用的時間復雜度關系如下:32O(1)<O(lgn)<O(n)<O(nlgn)<O(n2)<(n3)<……<O(2n)對數(shù)階線性階線性對數(shù)階冪次階指數(shù)階常量階(平行于橫軸)問題規(guī)模需要執(zhí)行的語句條數(shù)1.4算法和算法的效率空間復雜度(SpaceComplexity)，是指程序從開始運行，到運行結束，所需存儲空間的大小。類似于時間復雜度，算法所需存儲空間的量，通常記作：S(n)=O(f(n))其中n為問題規(guī)模；如果所需的輔助空間與問題規(guī)模無關，則空間復雜度記為O(1)。程序執(zhí)行時，除了需要存儲空間來存放本身所用的指令、常數(shù)、變量和輸入數(shù)據以外，進行操作時，可能還需要一些必要的輔助空間。進行空間復雜度分析時，若所需空間的大小依賴于特定的輸入，一般都按最壞的情況(峰值)來分析。331.5實驗預備知識C++中的引用變量34#include<stdio.h>intmain(){

inta=3,b=5;

intm=a,&n=b;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);a=33,b=55;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);m=333,n=555;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);

return

0;}運行結果如下：a=3,m=3,b=5,n=5a=33,m=3,b=55,n=55a=33,m=333,b=555,n=555a和m的值不會同步變化；b和n的值會同步變化。1.5實驗預備知識C++中的引用參數(shù)35voidswapByValue(inta,intb){

inttmp=a;a=b;b=tmp;}voidswapByPoint(int

*a,int

*b){

inttmp=*a;*a=*b;*b=tmp;}voidswapByRef(int

&a,int

&b){

inttmp=a;a=b;b=tmp;}intmain(){

intx=6,y=8;printf("x=%d,y=%d\n",x,y);swapByPoint(&x,&y);printf("x=%d,y=%d\n",x,y);swapByRef(x,y);printf("x=%d,y=%d\n",x,y);swapByValue(x,y);printf("x=%d,y=%d\n",x,y);

return

0;}運行結果如下：x=6,y=8x=8,y=6x=6,y=8x=6,y=81.5實驗預備知識使用引用變量的時候，需要注意如下幾點：C++中不存在空引用。引用變量在聲明的時候，就必須初始化，不能先聲明再賦值。也就是說，引用變量在聲明時就必須指定，它引用的是哪個變量。引用變量一旦被初始化，就不能再引用其他變量。給引用變量無論是賦值還是傳參，都不能用常量，也就是說引用變量只能引用其他變量的內存空間。使用引用變量后源文件的后綴名必須用.cpp(CPlusPlus的簡稱，C++源文件的后綴名)，不要用.c，否則編譯器將無法識別。361.5實驗預備知識中文亂碼的問題中文字符的常用編碼GB（GuoBiao的拼音，國標碼）系列編碼Unicode系列編碼（統(tǒng)一字符編碼）中文字符可能出現(xiàn)的位置源代碼文件（后綴為.c或.cpp）讀寫的數(shù)據文件（文本文件、二進制文件中的字符串）輸入輸出控制臺亂碼產生的原因不同位置的中文字符，采用了不一致的編碼；不同的文本文件，有些可能有BOM（ByteOrderMark）頭，部分系統(tǒng)或函數(shù)無法自動識別該文件頭。371.5實驗預備知識中文亂碼的解決方案所有字符均采用UTF-8編碼，并且文本文件的格式統(tǒng)一采用無BOM