數(shù)據(jù)結(jié)構(gòu)課件-第三講(線性表)

算法和數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)

大話《數(shù)據(jù)結(jié)構(gòu)》崔基哲2012年算法和數(shù)據(jù)結(jié)構(gòu)2第一章緒論第二章算法第三章線性表第四章棧和隊列第五章串第六章樹

第七章圖第八章查找第九章排序算法和數(shù)據(jù)結(jié)構(gòu)3線性表的定義線性表的定義排隊、點名冊、公司的組織架構(gòu)（?），朋友關(guān)系(?)第三章：線性表123n……算法和數(shù)據(jù)結(jié)構(gòu)4算法和數(shù)據(jù)結(jié)構(gòu)5算法和數(shù)據(jù)結(jié)構(gòu)6線性表的類型定義定義：一個線性表是n個數(shù)據(jù)元素的有限序列,,,a,()niaaa…………21如例英文字母表（A,B,C,…..Z)是一個線性表例數(shù)據(jù)元素特征：元素個數(shù)n—表長度，n=0空表1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項算法和數(shù)據(jù)結(jié)構(gòu)7線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼算法和數(shù)據(jù)結(jié)構(gòu)8相關(guān)概念和例子數(shù)據(jù)項紀(jì)錄文件例子字母表數(shù)據(jù)庫表第二章：線性表算法和數(shù)據(jù)結(jié)構(gòu)9線性表操作（一）初始化：Initiate求長度：Length得到第I個元素：Get設(shè)置第I個元素：Set求前驅(qū)：Prior求后繼：Next定位：Locate插入：Insert第二章：線性表算法和數(shù)據(jù)結(jié)構(gòu)10線性表操作（二）刪除操作：Delete判斷表是否為空：Empty置空表操作：Clear第二章：線性表算法和數(shù)據(jù)結(jié)構(gòu)11線性表的存儲結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯Φ诙拢壕€性表NULL……算法和數(shù)據(jù)結(jié)構(gòu)12兩種存儲方式的比較順序存儲優(yōu)點：元素訪問方便缺點：內(nèi)存使用；插入刪除不方便鏈?zhǔn)酱鎯?yōu)點：內(nèi)存利用好，插入刪除方便缺點：元素訪問不方便第二章：線性表算法和數(shù)據(jù)結(jié)構(gòu)13線性表的順序存儲結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)14線性表的順序存儲結(jié)構(gòu)的地址計算注意：C語言中的數(shù)組是從0開始第一個下表算法和數(shù)據(jù)結(jié)構(gòu)15算法和數(shù)據(jù)結(jié)構(gòu)16算法和數(shù)據(jù)結(jié)構(gòu)17算法和數(shù)據(jù)結(jié)構(gòu)18算法和數(shù)據(jù)結(jié)構(gòu)19算法和數(shù)據(jù)結(jié)構(gòu)20順序存儲優(yōu)點1：無須為表示表中元素之間的邏輯關(guān)系而增加額外空間優(yōu)點2：可以快速地存取表中任意位置的元素缺點1：插入和刪除操作需要移動大量的元素缺點2：當(dāng)線性表長度變化較大時，難以確定其空間的容量缺點3：造成存儲空間的“碎片”線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)21算法和數(shù)據(jù)結(jié)構(gòu)22算法和數(shù)據(jù)結(jié)構(gòu)23算法和數(shù)據(jù)結(jié)構(gòu)24算法和數(shù)據(jù)結(jié)構(gòu)25算法和數(shù)據(jù)結(jié)構(gòu)26算法和數(shù)據(jù)結(jié)構(gòu)27算法和數(shù)據(jù)結(jié)構(gòu)28算法和數(shù)據(jù)結(jié)構(gòu)29算法和數(shù)據(jù)結(jié)構(gòu)30算法和數(shù)據(jù)結(jié)構(gòu)31算法和數(shù)據(jù)結(jié)構(gòu)32算法和數(shù)據(jù)結(jié)