資源簡介

(共22張PPT)
第14課線性表
第15課數據結構與算法
數據結構：數據之間的相互關系及數據的組織方式。
復習鞏固
先進后出
先進先出
隊列
數組
棧
線性結構
特殊的線性表
復習鞏固
打印機打印文件
瀏覽網頁
線性結構是最基本、最簡單，也是最常用的一種數據結構。（一對一）
線性表是一種最基礎的線性結構，是由n個相同類型元素組成的有限序列。
（n=0時為空表）
1 線性表的概念
線性表有且僅有一個開始結點和一個終端結點。
線性表所有結點都最多只有一個前驅節點和一個后繼節點。
a0 a1 …… ai-1 ai ai+1 …… an-1
A B C D E F …… Z
首節點
尾節點
無前驅節點
無后繼節點
學號 姓名 語文 數學 英語
1 小明 95 100 98
2 小張 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小趙 89 85 95
……
是線性表嗎？
春 夏 秋 冬
數據的存儲方式(物理結構）
數據自身的邏輯關系(結構）
線性表的存儲方式一般有順序存儲結構和鏈式存儲結構兩種。
鏈式存儲方式
順序表
順序存儲結構
鏈表
A B C D E F G
A
B
C
D
E
F
G
二、線性表的存儲結構
順序表
順序存儲結構
小明 小張 小林 小王 小趙
二、線性表的存儲結構
學號 姓名 語文 數學 英語
1 小明 95 100 98
2 小張 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小趙 89 85 95
……
邏輯上相鄰的兩個數據在物理上也相鄰
鏈表
鏈式存儲方式
二、線性表的存儲結構
學號 姓名 語文 數學 英語
1 小明 95 100 98
2 小張 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小趙 89 85 95
……
數據分散地存儲在物理空間中
小明
小張
小林
小王
小趙
需要存儲兩個部分：
數據信息和后繼元素的位置信息（指針）
三、數據組織與算法
線性表的常用操作：
學號 姓名 語文 數學 英語
1 小明 95 100 98
2 小張 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小趙 89 85 95
……
訪問元素
插入元素
刪除元素
查找學生
增加學生
刪除學生
訪問元素
a0 … a45 a46 a47 a48 … a900
小明 ….. 小林 小王 小趙 小軍 ….. 小劉
順序表常用數組的方法來實現
數據元素
數組下標
小明
…
…
小張
小林8
小王
小趙
1154
a0
a45
a46
a47
a48
a900
a47
小明
…..
小林
小王
小趙
小劉
小軍
a0 … a45 a46 a47 a48 … a900
數據組織與算法在數組或鏈表中插入某個元素，分別采用怎樣的算法？小明小張小林小王小趙head小明小張小林小王小趙null將元素“小海”插入到元素“小王”的前面小海小海小海設計兩個不同的算法，在數組或鏈表中刪除某個元素，比較兩種算法的效率。小明小張小林小王小趙head小明小張小林小王小軍null刪除數組或鏈表中的元素“小張”小軍小趙（ ）
方法一：……
方法二：……
方法三：……
算法效率
時間效率
儲存量需求
空間效率
算法的執行時間
算法在執行過程中
需要的最大存儲空間
四、算法效率
隊列
數組
棧
線性表
線性結構
（一對一）
非線性結構
圖（多對多）
樹（一對多）
數據結構
邏輯結構
存儲結構（物理結構）
鏈式存儲方式
順序存儲結構
1.線性表是一個__________。
A. 有限序列，可以為空
B. 有限序列，不能為空
C. 無限序列，可以為空
D. 無限序列，不能為空
A
2.下面關于線性表的敘述中，錯誤的是 _________。
A. 線性表采用順序存儲，必須占用一片連續的存儲單元
B. 線性表采用順序存儲，便于進行插入和刪除操作
C. 線性表采用鏈接存儲，不必占用一片連續的存儲單元
D. 線性表采用鏈接存儲，便于進行插入和刪除操作
B
3.用鏈式存儲方式來存儲線性表的優點是______。
（A）便于隨機讀取
（B）花費的存儲空間較順序存儲少
（C）便于插入和刪除
（D）數據元素的物理順序與邏輯順序相同
C
21
24
36
57
77
87
99
14
a
4.若長度為8的一維數組，第一個元素為a[0],刪除第3個數據元素后，需要向前移動________個數據元素，刪除后數組元素a[5]的值是___________；然后在將66插入到數組中，使數組仍然按照從小到大排列，請問需要______移動步驟？
課堂練習
5
87
3
5.在長度為n的順序表的第i(1≤i≤n+1)個位置上插入一個元素，元素的移動次數為( )
A. n-i+1 B. n-i
C. i D. i-1
A
6.若長度為n的順序存儲結構線性表， 在第i個位置刪除一個元素，需要依次向后移動 _____個元素。
A. n-i+1 B. n-i
C. i D. i-1
B
7.一個順序表所占存儲空間的大小與______無關。
A．順序表長度 B．結點類型
C．結點中各數據域的類型 D．結點的存放次序
D
8.以順序存儲結構實現的線性表簡稱為 __________，它要求存儲空間必須是_________，并以下標來體現元素之間的關系，在順序表中訪問第i個元素的時間復雜度為 O（1） ，因此，順序表也稱為隨機存取的數據結構。 以鏈式存儲結構實現的線性表稱為_________。其存儲空間可以是_____________，以指針來體現元素之間的關系。在鏈表中訪問第i個元素的時間復雜度為 O（n），因此，鏈表也稱為順序訪問的數據結構。
順序表
連續的
不連續的
鏈表

展開更多......

收起↑