本章的 重點 是掌握 順序表 和 單鏈表 上實現的各種基本算法及相關的時間性能分析 難點 是使用本章所學的基本知識 設計有效算法 解決與線性表相關的應用問題
要求達到< 識記 >層次的內容有:線性表的邏輯結構特征;線性表上定義的基本運算並利用基本運算構造出較復雜的運算
要求達到< 綜合應用 >層次的內容有順序表的含義及特點順序表上的插入刪除操作及其平均時間性能分析解決簡單應用問題
鏈表如何表示線性表中元素之間的邏輯關系;單鏈表雙鏈表循環鏈表鏈接方式上的區別; 單鏈表上實現的建表查找插入和刪除等基本算法及其時間復雜度 循環鏈表上尾指針取代頭指針的作用以及單循環鏈表上的算法與單鏈表上相應算法的異同點雙鏈表的定義和相關算法利用鏈表設計算法解決簡單應用問題
要求達到< 領會 >層次的內容就是順序表和鏈表的比較以及如何選擇其一作為其存儲結構才能取得較優的時空性能
線性表 的 邏輯結構特征 是很容易理解的如其名它的邏輯結構特征就好象是一條線上面打了一個個結很形象的如果這條線上面有結那麼它就是非空表只能有一個 開始結點 有且只能有一個 終端結點 其它的結前後所相鄰的也只能是一個結點( 直接前趨 和 直接後繼 )
關於線性表上定義的基本運算主要有構造空表求表長取結點查找插入刪除等
線性表 的 邏輯結構 和 存儲結構 之間的關系在計算機中如何把線性表的結點存放到存儲單元中就有許多方法最簡單的方法就是 按順序存儲 就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中 在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的
在順序表中實現的基本運算主要討論了 插入 和 刪除 兩種運算相關的算法我們通過練習掌握對於順序表的插入和刪除運算其平均時間復雜度均為 O(n)
線性表的 鏈式存儲結構 它與順序表不同 鏈表 是用一組 任意的存儲單元 來存放線性表的結點這組存儲單元可以分布在內存中任何位置上因此 鏈表中結點的邏輯次序和物理次序不一定相同 所以為了能正確表示結點間的邏輯關系在存儲每個結點值的同時還存儲了其後繼結點的地址信息(即指針或鏈)這 兩部分信息組成鏈表中的結點結構
一個單鏈表由頭指針的名字來命名
對於單鏈表其操作運算主要有 建立單鏈表 (頭插法尾插法和 在鏈表開始結點前附加一個 頭結點 的算法) 查找 (按序號和按值) 插入 運算 刪除 運算等以上各運算的平均時間復雜度均為 O(n) 其主要時間是耗費在查找操作上
循環鏈表 是一種首尾相接的鏈表也就是終端結點的指針域不是指向NULL空而是指向開始結點(也可設置一個頭結點)形成一個環采用循環鏈表在實用中多采用尾指針表示單循環鏈表這樣做的好處是查找頭指針和尾指針的時間都是O()不用遍歷整個鏈表了
判別鏈表終止的條件也不同於單鏈表它是以指針是否等於某一指定指針如頭指針或尾指針來確定
雙鏈表 就是雙向鏈表就是在單鏈表的每個結點裡再增加一個指向其直接前趨的指針域prior這樣形成的鏈表就有 兩條不同方向的鏈 使得從已知結點查找其 直接前趨 結點可以和查找其 直接後繼 結點的時間一樣縮短為 O()
雙鏈表 一般也由頭指針head惟一確定雙鏈表也可以頭尾相鏈接構成 雙(向)循環鏈表
關於順序表和鏈表的比較請看下表
具體要求 順序表 鏈表
基於空間 適於線性表長度變化不大易於事先確定其大小時采用 適於當線性表長度變化大難以估計其存儲規模時采用
基於時間 由於順序表是一種隨機存儲結構當線性表的操作主要是查找時宜采用 鏈表中對任何位置進行插入和刪除都只需修改指針所以這類操作為主的線性表宜采用鏈表做存儲結構若插入和刪除主要發生在表的首尾兩端則宜采用尾指針表示的單循環鏈表
第二章 線性表 復習要點
本章復習要點是
線性表的邏輯結構特征常見的線性表的六種基本運算並可以根據這些基本運算組合得到更復雜的運算
順序表的特征順序表中結點地址的計算
順序表上實現的基本運算(算法)主要是插入和刪除的算法順序表的算法應該掌握算法時間復雜度要記住
單鏈表的特征圖形表示法
單鏈表的各種算法實現並能運用這些算法解決一些簡單問題;
循環鏈表的特征雙鏈表的特征以及它們的主要算法實現
可能出的題型有填空題簡答題應用題和算法題
如
在雙鏈表中插入運算的時間復雜度為()
AO() BO(n) CO(lgn) DO(nlgn)
請問頭指針開始結點和頭結點的區別與聯系
關於單鏈表上進行排序的算法設計
等等
From:http://tw.wingwit.com/Article/program/sjjg/201311/23679.html
