0-軟件技術基礎-數據結構(L1-3)-sxdai

1數據結構成都理工高校工程技術學院計科系代世雄2010年３月８日數據結構與算法的基本概念的基本概念什么是數據？

數據就是是信息的載體,它可以用計算機表示并加工?？梢钥闯?，數據這個概念本身是隨著計算機的發(fā)展而不斷擴展的概念。在計算機發(fā)展的初期，由于計算機主要用于數值計算，數據指的就是數值。計算機硬件和軟件技術的不斷發(fā)展，擴大了計算機的應用領域，諸如字符、文字、表格、圖形、圖像、聲音等也屬于數據的范疇2數據結構與算法的基本概念的基本概念什么是數據元素？數據元素是數據集合中的一個個體，它是數據的基本單位。例如：全部學生的學籍登記卡組成學生的學籍數據，每個學生的學籍登記卡就是學籍數據的一個數據元素。數據元素可以是一個數或字符串，也可以由若干數據項組成(數據的最小單位)。在這種狀況下，通常把數據元素稱為記錄。34表2-1學生學籍登記表學號姓名性別民族籍貫專業(yè)1王安男漢北京計算機通信2李華男回河北軟件3張莉女漢山西計算機應用4張平女漢廣東軟件數據結構與算法的基本概念的基本概念什么是數據結構？（１）數據結構就是探討數據及數據元素之間關系的一門學科。（２）數據結構的基本單位是數據元素，它可以是基本類型，也可以是結構類型。數據結構的三個方面：數據的邏輯結構。數據的存儲結構。數據的操作集合。561.數據的邏輯結構2.數據的存儲結構3.數據的運算：檢索、排序、插入、刪除、修改等。A.線性結構B.非線性結構A.依次存儲B.鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面反映數據元素之間的邏輯關系數據元素在計算機內部的組織方式C.散列結構（散列表）D.索引結構（索引表）數據的邏輯結構數據的邏輯結構就是它是描述數據間的依次（邏輯）關系，只是抽象地反映數據元素的結構，而不管它們在計算機中如何存放。一般用下列二元組來描述：DS=（D，R）其中：D：是數據元素的有限集合；R：是數據元素之間關系的集合。數據的邏輯結構與數據在計算機中的存放的物理位置無關7數據的存儲結構數據的存儲結構又稱物理結構，是指數據結構在計算機中的表示(又稱映象)，即數據在計算機中的存放。常用的存儲結構包括依次結構和鏈式結構。邏輯結構和存儲結構的關系１、數據的邏輯結構是從邏輯關系（某種依次）上視察數據，它是獨立于計算機的；可以在理論上、形式上進行探討、推理、運算等各種操作。２、數據的存儲結構是邏輯結構在計算機中的實現(xiàn)，是依靠于計算機的；離開了機器，則無法進行任何操作。３、任何一個算法的設計取決于選定的邏輯結構；而算法的最終實現(xiàn)依靠于接受的存儲結構。8數據的操作集合數據的操作集合：是指對存放在物理結構上的數據，按定義的邏輯結構進行的各種操作。常見操作有：輸入、檢索、插入、刪除、修改、排序等。9數據結構與算法算法：為解決一個問題而實行的方法和步驟，就稱為算法。算法的基本特性：１、有窮性：一個算法必需總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。２、確定性：每一步的依次與內容必需是唯一確定的。３、可行性：可以通過基本運算執(zhí)行有限次來實現(xiàn)。４、數據輸入：可以有０個或多個輸入５、數據輸出：必需至少有１個輸出10算法和程序的區(qū)分算法是解決問題的一種方法或過程，考慮的是如何將輸入轉換為輸出。一個問題可以有多種算法。程序是某種程序設計語言對算法的具體實現(xiàn)。算法和程序的主要區(qū)分在于：有窮性，正確性，和描述方法。１、程序可以是無窮的，如OS，算法是有窮的。２、程序可以是錯誤的，算法必需是正確的。３、程序是用程序設計語言描述，可在計算機上執(zhí)行；算法還可以用框圖、自然語言等形式來描述。11算法優(yōu)劣的評價標準評價算法優(yōu)劣的標準：時間困難度和空間困難度頻度：是指該語句重復執(zhí)行的次數。算法的時間困難度：指在計算機上運行該算法所花費的時間。用“O（數量級）”來表示，稱為“階”。常見的時間困難度有：O(1)O(logn)O(n)O(n2)空間困難度：指算法在計算機上運行所占用的存儲空間。度量同時間困難度。時間與空間是一對沖突，要節(jié)約空間往往要消耗較多的時間，反之亦然。目前，內存空間足夠，應重點考慮時間。12數據結構與算法－課堂練習131.數據在計算機內存中的表示是指數據的存儲結構。 (Ｙ/N)3.以下（14）不是數據結構探討的主要問題。(A)數據元素之間的邏輯關系 (B)數據元素之間的存儲結構(C)軟件開發(fā)方法 (D)實現(xiàn)操作的算法4.數據的基本單位是數據元素。5.數據類型是具有共同屬性的一類變量的抽象。6.在數據結構中，一個存儲結點存放一個（）。(A)數據項(B)數據元素(C)數據結構(D)數據類型7.數據類型是某種程序設計語言中已實現(xiàn)的數據結構。8.數據在計算機內在中的表示是指數據的存儲結構。9.以下特征中哪個不是算法的特征 ()。(A)可行性 (B)確定性(C)有窮性(D)唯一性10.算法指的是（15）。（A）計算機程序（B）解決問題的有限運算序列（C）排序算法（D）解決問題的計算方法11.數據元素是數據的基本單位，數據項是數據的最小單位。線性結構線性結構：是最常用的數據結構。線性結構的基本特點：數據元素是有序且有限的。線性結構的邏輯特征：在線性結構中１、有且僅有一個無干脆前趨而僅有一個干脆后繼的起始元素２、有且僅有一個無干脆后繼而僅有一個干脆前趨的終點元素３、其余元素均為內部元素常用的線性結構包括：線性表、堆棧、隊列、數組、串。14線性表線性表是由ｎ個(n>=0)相同類型元素構成的集合。15線性表的邏輯結構線性表是由n個數據元素組成的有限序列。記作：L=(a1，a2，…an)數據元素之間的關系ai-1領先于ai，ai領先于ai+1ai-1是ai的干脆前驅元素，ai＋1是ai的干脆后繼元素除a1外，每個元素有且只有一個干脆前驅元素。除an外，每個元素有且只有一個干脆后繼元素。線性表中數據元素的個數n(n>＝0)稱為表的長度。n=0時稱為空表16線性表的基本運算17Setnull（L）置空表Length（L）求表長度；求表中元素個數Get（L，i）取表中第i個元素（1≤i≤n）Prior（L，i）取i的前趨元素Next（L，i）取i的后繼元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）刪除元素Empty（L）判別表是否為空線性表的依次存儲結構線性表的依次存儲結構將表中元素一個接一個的存入一組連續(xù)的存儲單元中，這種存儲結構是依次結構。接受依次存儲結構的線性表簡稱為“依次表”。依次表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L1≤i≤n其中，L是元素占用存儲單元的長度。18線性表元素存儲示意圖19線性表依次存儲結構的特點線性表依次存儲結構的特點：(1)占用連續(xù)的內存；(2)數據元素的邏輯結構和物理結構保持一樣；(3)只要確定存儲依次表的起始位置，表中隨意元素可隨機存??；故該結構亦稱隨機存儲結構。線性表依次存儲結構的缺點：(1)在插入或刪除操作時，需移動大量的元素；(2)在給長度變更較大的線性表支配空間時，必需按最大空間支配；使存儲空間不能得到充分利用；(3)表的容量難以擴容。20依次存儲結構的插入運算21依次存儲結構的插入運算22當在依次存儲結構的線性表中某個位置上插入或刪除一個數據元素時，其時間主要耗費在移動元素上，而移動元素的個數取決于插入或刪除元素的位置。假設在第i個元素之前插入一個新元素的概率為1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，則插入操作中元素的平均移動次數(事實上就是時間困難度)為： T=依次存儲結構的特點小結依次存儲結構的特點數據連續(xù)存放、隨機存取邏輯上相鄰，物理上也相鄰存儲結構簡潔、易實現(xiàn)插入、刪除操作不便存儲密度大，空間利用率高結論：依次存儲結構適合于表中元素變動較少的狀況。23線性鏈表(LinkedList)線性表的依次存儲結構簡潔實現(xiàn)，可以隨機存取表中的隨意元素。依次表缺點是：–難于插入、刪除操作；–須要預先支配空間，不管這些空間能否最大限度地利用。鏈表存儲結構在這兩個方面恰好是優(yōu)點：–簡潔插入、刪除操作–不須要預分空間。24線性鏈表(LinkedList)鏈表：是指用一組隨意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內存中的隨意位置上的。結點：數據元素ai的存儲映象，它包括兩個域：數據域：存儲每個結點值；指針域：存儲指示其后繼結點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結點結構：25線性鏈表(LinkedList)結點（NODE）表中元素的存儲單元。鏈表存儲結構形式為：數據域指針域鏈表結構的C語言描述為：structnode{intdata;structnode*next;};typedefstructnodeNODE；26線性鏈表(LinkedList)基本概念鏈表（Link）:由結點組成的表。頭指針（head）:指向鏈表中第1個結點的指針。頭結點:為便利操作，在頭指針和首元結點之間設置的結點。首元結點:第一個結點（a1）。27線性鏈表(LinkedList)可以認為利用小的零散空間“串”起來，表示線性表，即把線性表的元素分散插入到系統(tǒng)所限制的零散空間中，然后用“指針”串起來，組成一個有序的線性表，用指針表示數據元素的邏輯關系。元素的存儲，可以是連續(xù)的，也可以不是連續(xù)的。結點至少包括數據元素和指針兩個區(qū)域。28a[0]a[2]a[3]a[1]300020001000單鏈表結構圖示單鏈表的頭指針為H：29160H160110a5200…

…150a2190160a1150…

…190a3210200a6260210a4110…

….240a8NULL

…

...

260a7240線性鏈表可以看出，用線性鏈表表示線性表時，數據元素之間的邏輯關系是由結點中的指針指示的，邏輯上相鄰的兩個數據元素其存儲的物理位置不要求相鄰，因此，這種存儲結構為非依次映像或鏈式映像。在運用中，我們只關切數據元素的邏輯次序而不必關切它的真正存儲地址。通常，我們在單鏈表第一個元素所在的結點之前附設一個結點——頭結點（增加的目的是統(tǒng)一空表與非空表的處理）。頭結點的指針域存儲第一個元素所在結點的存儲位置；頭結點的數據域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息。若線性表為空表，則頭結點的指針域為“空”。30帶頭結點的單鏈表通常狀況下，為了運算的統(tǒng)一，常在第一個結點前附設一個結點，稱為“頭結點”，頭指針具有標識作用，因而，常用作鏈表的名字31LNode*p;p=（LNode*）malloc(sizeof(LNode))；則完成了申請一塊LNode類型的存儲單元的操作，并將其地址賦值給指針變量p?！腍空表a1a2an∧H

非空表…Pp->datap->next帶頭結點單鏈表的插入操作32線性鏈表操作：插入元素3333p指向當前結點，pre表示前一個結點(的指針)。在*p前(*pre后)插入元素s的語句序列：

s->next=pre->next; pre->next=s;aknextai-1nextainextpre帶頭結點單鏈表的刪除操作34圖2-8帶頭結點的單鏈表圖2-9在單鏈表中刪除一個結點線性鏈表操作：刪除元素35ai-1nextainextai+1next*p表示當前結點,*pre表示*p的前驅結點刪除*p結點的語句序列為：

pre->next=p->next;free(p); 循環(huán)鏈表假如鏈表最終一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)，這樣的鏈表稱為循環(huán)鏈表。這樣，從表中任一結點動身均可找到表中其它結點，其邏輯狀態(tài)圖如圖2-1036圖2-10循環(huán)單鏈表循環(huán)鏈表循環(huán)鏈表一般設表頭結點，這樣鏈表將永不為空，這將使空表和非空表的邏輯狀態(tài)及運算統(tǒng)一起來。循環(huán)鏈表的操作和線性鏈表基本一樣，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。與單鏈表比較，循環(huán)鏈表有以下特點：(1)在循環(huán)單鏈表中，從表中任何一個結點動身都能訪問到其它全部的結點；而單鏈表一般把頭指針作為入口點，從某一結點動身，只能訪問到其全部后繼結點。(2)循環(huán)單鏈表的空表判定條件是：head->next=head。37雙向鏈表前面探討的鏈式存儲結構中只有一個指示干脆后繼的指針域，所以從某結點動身只能順指針往后查找其它結點。若要查找結點的干脆前趨，則應從頭指針動身(或在循環(huán)單鏈表中從p結點動身)始終往后找，直到結點q滿足q->next=p，那么q是p的前趨結點。為克服鏈表這種單向性的缺點，為有更大的靈敏性來操作線性鏈表，可接受雙向鏈表存儲結構。38雙向鏈表在每個結點上增加另一個指向線性表中每個元素的前趨結點的指針域prior，就得到雙向鏈表。其結點的結構如下圖所示。其中，prior是指向前趨結點的指針域；data是數據域；next是指向后繼結點的指針域。39雙向鏈表結點結構雙向鏈表將雙向鏈表的頭結點和尾結點鏈接起來組成雙向循環(huán)鏈表。雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13，圖2-14和圖2-15所示。40圖2-12帶頭結點的空雙向鏈表圖2-13帶頭結點的非空雙向鏈表雙向循環(huán)鏈表41圖2-14空的雙向循環(huán)鏈表

圖2-15非空雙向循環(huán)鏈表雙向鏈表在非空雙向循環(huán)鏈表中，設p是指向鏈表中任一結點的指針，則有：p->next->prior=p->prior->next=p這個等式反映了這種鏈表的本質，在此鏈表上進行插入或刪除操作是特殊便利的。雙向鏈表雖然多花了存儲空間，但卻換得了操作上的更大靈敏性。雙向鏈表的運算如LENGTH(Head)，GET(Head,i)，LOCATE(Head,x)等操作，僅涉及一個方向的指針，操作類似單鏈表。但插入INSERT、刪除DELETE時要同時修改兩個方向的指針。42雙向鏈表的插入操作43圖2-16在雙向鏈表中插入結點插入時相關操作序列為：①s->prior=p->prior;②(p->prior)->next=s;③s->next=p;④p->prior=s。雙向鏈表的刪除操作44圖2-17在雙向鏈表中刪除結點刪除時相關操作序列為：①(p->prior)->next=p->next;②(p->next)->prior=p->prior;

線性表－課堂練習451.數據的邏輯結構是從邏輯關系上描述數據，它與數據的存儲結構無關，是獨立于計算機的。(Ｙ/N)2.在線性表中，數據的存儲方式有依次和鏈接兩種。3.線性鏈表的地址()。(A)必需連續(xù) (B)部分地址必需連續(xù)(C)確定不連續(xù) (D)連續(xù)與否均可以4.線性表接受鏈式存儲時，結點的存儲地址必需是連續(xù)的5.依次表和線性鏈表的物理存貯形式都是依次存貯6.數組也是一種數據結構，一維數組就是一種依次表結構。7.線性表不具有的特點是（11）。(A)隨機訪問 (B)無須事先估計所需存儲空間大小(C)插入時不必移動元素(D)所需空間與純屬表長度成正比8.數據在計算機內存中的表示是指數據的存儲結構。9.鏈表可以隨機訪問隨意一個結點，而依次表則不能。線性表－課堂練習46下述哪一條是依次存儲結構的優(yōu)點？（）A．插入運算便利B．可便利地用于各種邏輯結構的存儲表示C．存儲密度大D．刪除運算便利下面關于線性表的敘述中，錯誤的是哪一個？（）A．線性表接受依次存儲，必需占用一片連續(xù)的存儲單元B．線性表接受依次存儲，便于進行插入和刪除操作C．線性表接受鏈接存儲，不必占用一片連續(xù)的存儲單元D．線性表接受鏈接存儲，便于插入和刪除操作。若某線性表最常用的操作是存取任一指定序號的元素和在最終進行插入和刪除運算，則利用（）存儲方式最節(jié)約時間。A．依次表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表線性表－課堂練習47鏈表不具有的特點是（）A．插入、刪除不須要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比棧和隊列棧(stack)和隊列(queue)是常常遇到的兩種數據結構，它們都是特殊狀況下的線性表。前面介紹的線性表的向量及鏈表存儲，進行插入、刪除時是比較麻煩的。向量導致數據元素的大量移動，而鏈表中則要順鏈找尋指定位置。假如能夠把插入、刪除操作都限制在線性表的端部進行，則運算效率可以大大提高。本節(jié)要探討的就是這種限制存取位置的線性表——棧和隊列。48棧棧（也稱堆棧）1．棧的定義棧（stack）是限定只能在表的同一端進行插入和刪除操作的線性表。其中允許進行插入和刪除操作的一端稱為棧頂(top)，而表中固定的一端稱為棧底(bottom)。棧中元素個數為零時稱為空棧。由于棧中元素的插入和刪除只能在棧頂進行，所以總是后進棧的元素先出來，即棧具有后進先出(LastInFirstOut，縮寫為LIFO)的特性，故棧又稱為“后進先出表”(LIFO表)。49棧在日常生活中，有不少類似棧的例子。例如食堂中盤子的疊放，假如限定一次疊放一只，那么每次都是疊放到原來一疊盤子的頂上，這相當于入棧操作；而當取用一只盤子時，也是從這一疊盤子的頂上取用，這相當于出棧操作。50棧棧的五種基本運算：(1)Inistack(S)。初始化棧S為空棧。(2)Empty(S)。判定S是否為空棧。若S是空棧則返回值為真(Ture)，否則返回值為假(False)。(3)Push(S，x)。進棧操作。在棧S的棧頂插入數據元素x。(4)Pop(S)。出棧操作。若棧S不是空棧，則刪除棧頂元素。(5)Gettop(S)。取棧頂元素。它只讀取棧頂元素，不變更棧中的內容。51棧52例2-9

有三個元素的進棧序列是1，2，3，舉出此三個元素可能的出棧序列，并寫出相應的進棧和出棧操作序列如圖2-18所示(假設以I和O表示進棧和出棧操作)。圖2-18三個元素可能的出棧序列棧的表示和實現(xiàn)因為棧是線性表的一種特例，所以線性表的存儲結構對它都適用。一般稱接受依次存儲結構的棧為依次棧；接受鏈式存儲結構的棧為鏈棧。1)棧的依次存儲結構——依次棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂的數據元素，同時設指針top指示棧頂元素的當前位置?？諚５臈ｍ斨羔樦禐?1。設用數組Stack[MAXSIZE]表示棧，則對非空棧，Stack[0]為最早進入棧的元素，Stack[top]為最遲進入棧的元素，即棧頂元素。當top=MAXSIZE-1時意為棧滿，此時若有元素入棧則將產生“數組越界”的錯誤，稱為棧的“上溢”(overflow)；反之，top=-1意為?？?，若此時再作退棧操作，則發(fā)生“下溢”(underflow)。圖2-19展示了依次棧中數據元素和棧頂指針之間的對應關系，設MAXSIZE=m。53棧的表示和實現(xiàn)54圖2-19棧頂指針和棧中元素之間的關系

55棧的鏈式存儲結構—鏈棧棧的運用特殊廣泛，常常會出現(xiàn)在一個程序中須要同時運用多個棧的情形，為了不因棧上溢而產生錯誤中斷，必需給每個棧預分一個較大的空間，但這并不簡潔做到，因為各個棧實際所用空間很難估計。考慮到在實際進程中，當一個棧發(fā)生上溢時，其它?？赡苓€留有很多空間，所以可設法動態(tài)地加以調整，以達到多個棧共享內存時，只要有一個棧未滿，其它任何棧的入棧操作均不會發(fā)生上溢。2)棧的鏈式存儲結構——鏈棧接受依次存儲結構，對于一個棧、兩個?？梢郧逦匀坏乇磉_，但當遇到多個棧共享空間的問題或棧的最大容量事先不能估計時，接受鏈式存儲結構是有效的方法。56鏈棧存儲結構的C語言描述structsnode{intdata;structsnode*link;};typedefstructsnodeSNODE;SNODE*top；鏈棧為空的條件：top=NULL鏈棧為滿的條件：t=NULLt為申請的結點，為NULL表示失敗。57棧的鏈式存儲結構58圖2-21鏈棧示意圖棧的鏈式存儲結構稱為鏈棧，它是運算是受限的單鏈表。棧的鏈式存儲結構對于鏈棧，不會產生單個棧滿而其余?？盏那樾危挥挟斦麄€可用空間都被占滿，malloc函數無法實現(xiàn)時才會發(fā)生上溢。因此多個鏈棧共享空間也就是