熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構各章要點

2013-11-15 15:48:47  來源: 數據結構 
第一章 概 論
************************************************************************
數據就是指能夠被計算機識別存儲和加工處理的信息的載體
數據元素是數據的基本單位可以由若干個數據項組成數據項是具有獨立含義的最小標識單位
************************************************************************
數據結構的定義·邏輯結構從邏輯結構上描述數據獨立於計算機·線性結構一對一關系
·線性結構多對多關系
·存儲結構是邏輯結構用計算機語言的實現·順序存儲結構如數組
  ·鏈式存儲結構如鏈表
        ·索引存儲結構·稠密索引每個結點都有索引項
         ·稀疏索引每組結點都有索引項
        ·散列存儲結構如散列表
·數據運算·對數據的操作定義在邏輯結構上每種邏輯結構都有一個運算集合
·常用的有檢索插入刪除更新排序
************************************************************************
數據類型是一個值的集合以及在這些值上定義的一組操作的總稱·原子類型由語言提供
             ·結構類型由用戶借助於描述機制定義是導出類型
抽象數據類型ADT·是抽象數據的組織和與之的操作相當於在概念層上描述問題
 ·優點是將數據和操作封裝在一起實現了信息隱藏
************************************************************************
程序設計的實質是對實際問題選擇一種好的數據結構設計一個好的算法算法取決於數據結構
************************************************************************
算法是一個良定義的計算過程以一個或多個值輸入並以一個或多個值輸出
評價算法的好壞的因素·算法是正確的
·執行算法的時間
·執行算法的存儲空間(主要是輔助存儲空間)
·算法易於理解編碼調試
************************************************************************
時間復雜度是某個算法的時間耗費它是該算法所求解問題規模n的函數
漸近時間復雜度是指當問題規模趨向無窮大時該算法時間復雜度的數量級
評價一個算法的時間性能時主要標准就是算法的漸近時間復雜度
算法中語句的頻度不僅與問題規模有關還與輸入實例中各元素的取值相關
時間復雜度按數量級遞增排列依次為常數階O()對數階O(logn)線性階O(n)線性對數階O(nlogn)平方階O(n^)立方階O

(n^)……k次方階O(n^k)指數階O(^n)
空間復雜度是某個算法的空間耗費它是該算法所求解問題規模n的函數
算法的時間復雜度和空間復雜度合稱算法復雜度


第二章 線性表

************************************************************************
線性表是由n≥個數據元素組成的有限序列n=是空表非空表只能有一個開始結點有且只能有一個終端結點
************************************************************************
線性表上定義的基本運算·構造空表Initlist(L)
·求表長Listlength(L)
·取結點GetNode(Li)
·查找LocateNode(Lx)
·插入InsertList(Lxi)
·刪除Delete(Li)
************************************************************************
順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關

系是一致的地址計算LOCa(i)=LOCa()+(i)*d(首地址為
在順序表中實現的基本運算 ·插入平均移動結點次數為n/平均時間復雜度均為O(n)
·刪除平均移動結點次數為(n)/平均時間復雜度均為O(n)
************************************************************************
線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同為了能正確表示結點間的邏輯關系在存儲每個結點值的同時還存儲

了其後繼結點的地址信息(即指針或鏈)這兩部分信息組成鏈表中的結點結構 一個單鏈表由頭指針的名字來命名
************************************************************************
單鏈表運算·建立單鏈表·頭插法s>next=headhead=s生成的順序與輸入順序相反平均時間復雜度均為O(n)
·尾插法head=rear=nullif(head=null) head=s;else r>next=s;r=s; 平均時間復雜度均為O(n)
·加頭結點的算法對開始結點的操作無需特殊處理統一了空表和非空表
·查找·按序號與查找位置有關平均時間復雜度均為O(n)
·按值與輸入實例有關平均時間復雜度均為O(n)
·插入運算p=GetNode(Li)s>next=p>nextp>next=s平均時間復雜度均為O(n)
·刪除運算p=GetNode(Li)r=p>nextp>next=r>nextfree(r)平均時間復雜度均為O(n)
************************************************************************
單循環鏈表是一種首尾相接的單鏈表終端結點的指針域指向開始結點或頭結點鏈表終止條件是以指針等於頭指針或尾指針
采用單循環鏈表在實用中多采用尾指針表示單循環鏈表優點是查找頭指針和尾指針的時間都是O()不用遍歷整個鏈表
************************************************************************
雙鏈表就是雙向鏈表就是在單鏈表的每個結點裡再增加一個指向其直接前趨的指針域prior形成兩條不同方向的鏈由頭指針head惟一

確定
雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表
雙鏈表上的插入和刪除時間復雜度均為O ()
************************************************************************
順序表和鏈表的比較·基於空間 ·順序表的存儲空間是靜態分配存儲密度為適於線性表事先確定其大小時采用
·鏈表的存儲空間是動態分配存儲密度<適於線性表長度變化大時采用
  ·基於時間 ·順序表是隨機存儲結構當線性表的操作主要是查找時宜采用
·以插入和刪除操作為主的線性表宜采用鏈表做存儲結構
·若插入和刪除主要發生在表的首尾兩端則宜采用尾指針表示的單循環鏈表

第三章 棧和隊列
************************************************************************
棧(Stack)是僅限制在表的一端進行插入和刪除運算的線性表稱插入刪除這一端為棧頂另一端稱為棧底表中無元素時為空棧

的修改是按後進先出的原則進行的我們又稱棧為LIFO表(Last In First Out)通常棧有順序棧和鏈棧兩種存儲結構
************************************************************************
棧的基本運算有六種 ·構造空棧InitStack(S)
·判棧空: StackEmpty(S)
·判棧滿 StackFull(S)
·進棧 Push(Sx)
·退棧 Pop(S)
·取棧頂元素StackTop(S)
************************************************************************
在順序棧中有上溢下溢的現象 ·上溢是棧頂指針指出棧的外面是出錯狀態
·下溢可以表示棧為空棧因此用來作為控制轉移的條件
順序棧中的基本操作有六種·構造空棧·判棧空·判棧滿·進棧·退棧·取棧頂元素

************************************************************************
鏈棧則沒有上溢的限制因此進棧不要判棧滿鏈棧不需要在頭部附加頭結點只要有鏈表的頭指針就可以了
鏈棧中的基本操作有五種·構造空棧·判棧空·進棧·退棧·取棧頂元素
************************************************************************
隊列(Queue)是一種運算受限的線性表插入在表的一端進行而刪除在表的另一端進行允許刪除的一端稱為隊頭(front)允許插入的

一端稱為隊尾(rear) 隊列的操作原則是先進先出的又稱作FIFO表(First In First Out) 隊列也有順序存儲和鏈式存儲兩種存儲結


************************************************************************
隊列的基本運算有六種 ·置空隊InitQueue(Q)
·判隊空QueueEmpty(Q)
·判隊滿QueueFull(Q)
·入隊EnQueue(Qx)
·出隊DeQueue(Q)
·取隊頭元素QueueFront(Q)
************************************************************************
順序隊列的假上溢現象由於頭尾指針不斷前移超出向量空間這時整個向量空間及隊列是空的卻產生了上溢現象
為了克服假上溢現象引入循環向量的概念是把向量空間形成一個頭尾相接的環形這時隊列稱循環隊列
判定循環隊列是空還是滿方法有三種 ·一種是另設一個布爾變量來判斷
·第二種是少用一個元素空間入隊時先測試((rear+)%m = front)? 滿 
·第三種就是用一個計數器記錄隊列中的元素的總數
********************
From:http://tw.wingwit.com/Article/program/sjjg/201311/24001.html

  • 上一篇文章:

  • 下一篇文章: 没有了
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.