資源簡介

(共43張PPT)
信息技術
2
第二章
數組與鏈表
計算機中數據的存儲模式分為順序存儲和非順序存儲，所有數據結構的存儲也可以分為這兩類，而作為常用數據結構中的數組與鏈表，就是這兩種存儲模式的典型代表,其他的數據結構都是在這兩種數據結構的基礎上構建的。
順序存儲結構和非順序存儲結構
計算機中數據的存儲結構主要分為順序存儲結構和非順序存儲結構。其中順序存儲結構是將邏輯上相鄰的數據節點存儲在物理位置相鄰的存儲單元中，典型代表為數組;而非順序存儲結構的形式就是鏈式存儲結構，在鏈式存儲結構中可以將邏輯上相鄰的數據節點在內存中分開存儲，節點之間的前后關系由每個節點中的指針確定,典型代表為鏈表。
第二章 數組與鏈表
數組與鏈表
數組
鏈表
鏈表的概念
鏈表的特性
鏈表的基本操作
數組的概念
數組的特性
數組的基本操作
內容總覽
數組是由相同類型的變量構成的一個序列。
由數組名和下標組成數組的各個變量稱為數組的分量，也稱為下標變量或數組元素。
b[0] b[1] b[2] b[3] b[4]
20 15 14 10 4
b [3]
數組分量/下標變量/數組元素
b
[3]
數組名
下標
每個數組元素的類型相同，所需的存儲空間一致，因此在明確第一個數組元素的存儲位置后，可以利用下標計算出其他數組元素的存儲位置，從而達到快速訪問的目的。
2.1 數組
一維數組：只有一個下標的數組稱為一維數組，一維數組適合用來表示具有一維空間的線性特征的數據序列。
數組元素：d[0],d[1],d[2],d[3],d[4]….
二維數組（形象、方便）：
二維空間內既有縱向聯系又有橫向聯系的一批數據。
由于二維數組中的數據元素有行、列兩個維度位置信息，因此需要兩個下標。
數組下標表示方法
不同程序語言中的數組，特別是多維數組的下標表示各有不同。有的語言中使用多個方括號分別表示其中一個下標，如: a[1][3]，典型代表有C、C++、Python等;有的語言中則是使用一個方括號包含所有下標，每個下標之間用逗號隔開，如: a[1,3]，典型代表有Pascal;有的則使用一個圓括號包含所有下標，每個下標之間用逗號隔開，如: a(1,3)，典型代表有VB。
0 1 0 0
1 2 2 0
0 2 0 1
0 2 0 0
數組名：qp 列位置下標：
0 1 2 3
行位置下標：0
1
2
3
數組元素：qp[0][0], qp[0][1],……, qp[3][3],
行、列下標均從0開始
0：無子
1：黑子
2：白子
qp[0][0]=0
qp[0][1]=1
qp[0][2]=0
qp[0][3]=0
存儲方式可分為：行優先和列優先兩種。
二維數組：順序存儲
數組名qp
下標
[0][0]
[0][1]
[0][2]
[0][3]
[1][0]
[1][1]
[1][2]
……
0
1
0
0
1
2
2
…
數組名：qp 列位置下標：
0 1 2 3
行位置下標：0
1
2
3
數組元素：qp[0][0], qp[0][1],……, qp[3][3],
0 1 0 0
1 2 2 0
0 2 0 1
0 2 0 0
數組快速訪問：先指向第一個第一行數組元素存儲的位置，其他元素根據下標快速得到存儲位置。
2.數組的特性
（1）數組元素（下標變量）的數據類型相同
（2）通過下標變量對數組元素的值進行訪問
（3）存儲空間固定不變
除非特殊說明，數組指向的往往是靜態數組
開辟一批地址連續，且空間固定的存儲空間。
快速訪問一維數組a[9]:第10個元素的位置
靜態數組特點：
規模可預估，處理過程穩定
動態數組
沒有確定數據規模的數組，可以在任何時候改變數據規模。可在運行時具體改變數組大小的，從而引入動態數組。
2.1.2 數組基本操作
列表包含類型可不同。《必修1 》P72
列表=數組（列表中每個數據元素所含數據項的數量和數據類型都相同）
列表的存儲
列表的存儲雖然可以使用列表來模擬數組,但是列表的存儲方式與數組是截然不同的,列表中索引是連續的,但其數據元素在內存中存儲時一般不是連續存儲的,這是由Python中變量存儲模式決定的，如定義1000個初始化為0的列表,這1000個數值為0的列表元素均指向同一個地址,可以使用id()函數進行驗證。
1.數組的創建
例1 統計分數
學校元旦文藝匯演比賽時，現場有9位評委給各班節目打分，統計系統需要根據9位評委的原始分計算平均分作為各班表演節目的最終得分。
分析：該問題中9位評委給出的分數屬于同一類型的數據，可以創建一個包含9個下標變量的數值型數組來存儲評委的原始分。
創建保存評委原始分的一維數組s的程序如下：
qp=[[0]*4]*4
規模較小
規模較大
二維數組的創建
Python中二維數組的創建
Python中創建二維數組的方式比較特殊,不能使用如同一維數組的方式創建,若使用語句qp=[[0]*4]*4來創建,則在修改某行元素時,4行中同一列的數據會同時被修改。這是因為其實質是創建了一行數據的4個引用,因此修改某一行中的數據相當于修改了所有行中的數據。這種情況在Python中稱為淺拷貝。
0 0 0 0
qp=[[0]*4]*4
二維數組：3行4列？
1.8作業：
創新設計-《教學案》 p8-p9
2.數組的訪問
由于數組元素可以通過數組名和下標快速確定數據元素的內存地址，因此可通過下標變量直接進行訪問。例如，print(s[5])表示將一維數組s中第6個元素的值進行輸出（第1個元素為s[0]）。
第一章1.2節將“數據合并”問題簡化成合并兩個有序數據序列的問題，對如何使用數組解決數據合并問題進行了分析并設計了算法。下面將對算法進行修改和優化，避免插入數據時其他數據元素的移動，并編程實現該功能。
例2 基于數組實現數據合并的功能
①初始化3個數組a，b，c，元素個數分別為n，m和n+m。數組a和數組b用來存儲已有的兩個有序數據（降序），數據使用隨機函數randint(start,end)產生；數組c用于保存合并后的所有數據（降序），所有數組元素的值初始化為0。
②使用變量i指向數組a當前未處理數據中要處理的數據元素的位置，初始化為0；變量j指向數組b當前未處理數據中要處理的數據元素的位置，初始化為0；變量k指向數組c中可加入元素的位置，初始化為0。
③重復以下操作，直至數組a或數組b中的數據元素全部合并入數組c中：比較a[i]和b[j]的大小，若a[i]≥b[j]，則將a[i]放入數組c中，并將i和k的值增加1；否則，將b[j]放入數組c中，并將j和k的值增加1。
④如果數組a或數組b中尚有未處理的數據元素，那么將剩余數據元素按原有順序依次存入數組c中，合并完成，輸出數組c。
1.如何保證降序？
2.如何合并數據？
3.如何做到空間適時靈活分配？
4.若數組a、b元素相等，哪個放前？
5.若數組a、b元素個數不等，其中一個數組元素排完后，另一個數組剩下元素怎么辦？
程序 測試結果
from random import randint a=[0]*20 #創建數組 b=[0]*15 c=[0]*35
a[0]=randint(95,100) for i in range(1,20): # 隨機產生降序數據序列一 a[i]=a[i-1]-randint(1,5) 生成a數組序列：
[99, 97, 95, 94, 90, 87, 83,79, 78, 73, 71, 69, 67, 66, 61,60, 56, 55, 52, 51]
b[0]=randint(95,100) for i in range(1,15): # 隨機產生降序數據序列二 b[i]=b[i-1]-randint(1,5) 生成b數組序列：
[99, 96, 94, 91, 90, 88, 87,
82, 80, 79, 75, 73, 70, 66, 62]
print(" 原始數據序列一為： ") print(a) print(" 原始數據序列二為： ") print(b)
程序 測試結果
i=0 j=0 k=0 while(i<20 and j>15): # 合并數據直至某個數組數據合并完成 if a[i] >=b[j]: c[k]=a[i] i=i+1 k=k+1 else: c[k]=b[j] j=j+1 k=k+1 C數組序列
[99, 99, 97, 96, 95, 94, 94,
91, 90, 90, 88, 87, 87, 83, 82,
80, 79, 79, 78, 75, 73, 73, 71,
70, 69, 67, 66, 66, 62,0,0,0,0,0,0]
j=15
i=14
程序 測試結果
while i < 20: #當數據序列一中還有數據時的處理 c[k]=a[i] i=i+1 k=k+1 C數組序列
[99, 99, 97, 96, 95, 94, 94,
91, 90, 90, 88, 87, 87, 83, 82,
80, 79, 79, 78, 75, 73, 73, 71,
70, 69, 67, 66, 66, 62, 61, 60,
56, 55, 52, 51]
j=15
i=20
while j ＜ 15: #當數據序列二中還有數據時的處理 c[k]=b[j] j=j+1 k=k+1
print(" 合并后的數據序列為： ") print(c) 輸出合并后的C數組序列
3.數組的插入與刪除
當需要在數組中某個位置插入一個新的數據時，必須先將該位置及其后的所有數據向后移動一個位置，在保證順序不變的前提下保存這些數據，最后再修改該位置上的數據為新數據。
在數組d中第3個位置( d[2])插入新數據：
將該位置及其后所有數據依次向后移動一個位置;
第二步，修改d[2]的值為新的數據。
靜態數組插入元素，移動位置：a[i+1]=a[i]；
效率較低，可能會超出數組元素數量而導致數據丟失；
思考
？
靜態數組刪除元素：將被刪除元素位置后的所有元素前移一個位置：a[i]=a[i+1]；
效率較低，且刪除元素后，會留有空位，造成存儲空間浪費；
在使用數組組織、存儲數據時應避免數組元素的增刪操作！
例3 基于數組的車牌搖號系統功能實現
汽車數量的急劇增加，導致城市交通的壓力越來越大，許多大城市采取通過搖號方式來發放汽車車牌。在申請人通過資格審核后，車牌搖號系統反饋回一個唯一的編號。每次搖號前，車牌搖號系統需要收集所有本次申請人的編號，再在所有編號中隨機抽取不重復的若干個編號來發放車牌。
（1）抽象與建模
用n表示有資格參加搖號的申請人總數，用序列luck存儲編號，luck 0 ，luck 1 ，…，luck n–1 依次表示n個編號，其中的下標表示每個編號的位置，luck i 的初值為第i+1位申請人的編號。使用變量m表示最終的車牌發放數量，計數器c表示已抽中人數，每當隨機抽出一個有效的下標位置（如k）時，計數器c加1，輸出申請人的編號后將該下標位置（如luck k ）的值設為空串（表示該編號已被抽取），用來判斷其后抽取的編號是否重復。重復該過程直至計數器c的值變為m，搖號結束。
例3 基于數組的車牌搖號系統功能實現
（2）設計算法
由于該問題中數據規模可以預估，在處理過程中其數據規模保持不變，并需要根據隨機產生的編號讀取和修改對應的值，所以用數組來存儲所有申請人的編號，下標表示該編號的位置。算法分為兩個步驟：
①根據申請人總數n，初始化數組luck，其數組下標代表位置，數組元素值為申請者編號（類型為字符串），并使用計數器c表示已抽中人數，初始化值為0。
②使用隨機整數函數randint(a,b)隨機產生一個位置k，若其作為數組下標對應的數組數據元素值為空串，則表示該編號已被抽取，該編號為重復號碼，需要重新生成；否則，表示該編號為有效編號，計數器c加1，輸出對應的數組元素并修改數組元素值為空串，表示該編號已被抽取。
③重復執行步驟②，直至計數器c變為m，程序結束。
函數和方法 功能 實例
len(list) 統計列表list中元素個數 list=[]
print(len(list))
輸出為：0
list.append(x) 在列表中list末尾添加元素x list=[22,33,44]
list.append(55)
print(list)
輸出為：[22,33,44,55]
list.insert(i,x) 在列表list中下標為i處插入元素x list=[“A”, ”B”, ”D”]
list.insert(2,”C”)
print(list)
輸出為：[“A”, ”B”, ”C”，”D”]
list.pop(i） 將列表list中下標為i的元素刪除，若i不指定，默認為-1，即最后一個 list=[“A”, ”B”, ”C”，”D”]
list.pop(2)
print(list)
輸出為：[“A”, ”B”, ”D”]
函數和方法 功能 實例
len(list) 統計列表list中元素個數 list=[]
print(len(list))
輸出為：0
list.append(x) 在列表中list末尾添加元素x list=[22,33,44]
list.append(55)
print(list)
輸出為：[22,33,44,55]
list.insert(i,x) 在列表list中下標為i處插入元素x list=[“A”, ”B”, ”D”]
list.insert(2,”C”)
print(list)
輸出為：[“A”, ”B”, ”C”，”D”]
list.pop(i） 將列表list中下標為i的元素刪除，若i不指定，默認為-1，即最后一個 list=[“A”, ”B”, ”C”，”D”]
list.pop(2)
print(list)
輸出為：[“A”, ”B”, ”D”]
使用以上列表的函數和方法后，可以將由列表模擬實現的數組視為動態數組，其中的增加、刪除數組元素的操作由相應的函數實現。
from random import randint
luck=[] # 新建列表
csv_file=open("bh.csv", "r", encoding='utf-8') # 打開存有編號的文件 bh.csv
flines=csv_file.readlines() # 將文件中所有編號按行讀入 flines 中
csv_file.close # 關閉文件
n=0
for one_line in flines:
tmp=one_line.strip("\n") # 將一個編號去除換行后賦給 tmp
luck.append(tmp) #填加列表元素
n+=1
m=int(input(" 請輸入發放數： "))
for i in range(m):
k=randint(0,n-1)
print(luck[k])
luck.pop(k) #編號抽取后刪除
n-=1 #元素數組減少1個
思考與練習
？
1.參考二維數組的行優先存儲方式，畫圖模擬二維數組的列優先存儲方式。觀察并比較行優先存儲與列優先存儲中相同元素的存儲位置的改變，如qp[1][2]在行優先存儲方式下在序列的第7個位置，則其在列優先存儲方式下在序列的第幾個位置
2.參考搖號系統的功能實現，將自己班級所有同學的名字以一個名字一行的形式存入文件name.csv，并使用文件讀入的方式，使用數組實現隨機抽獎程序。
課堂小結：
2.1.2 數組基本操作
列表包含類型可不同。《必修1 》P72
列表=數組（列表中每個數據元素所含數據項的數量和數據類型都相同）
列表的存儲
列表的存儲雖然可以使用列表來模擬數組,但是列表的存儲方式與數組是截然不同的,列表中索引是連續的,但其數據元素在內存中存儲時一般不是連續存儲的,這是由Python中變量存儲模式決定的，如定義1000個初始化為0的列表,這1000個數值為0的列表元素均指向同一個地址,可以使用id()函數進行驗證。
下列python語句的輸出結果是：
s1=[4,5,6]
s2=s1
s[1]=0
print(s2)
A.[4,5,6] B.[0,5,6]
C.[4,0,6] D.[1,0,0]
答案：C
s1和s2指向同一對象（同一個列表）
淺拷貝vs深拷貝
在淺拷貝時，拷貝出來的新對象的地址和原對象的地址是不一樣的，但是新對象的可變元素和原對象的可變元素的地址是一樣的。也就是說，淺拷貝它拷貝的是淺層次的數據結構元素（不可變元素），對象的可變元素作為深層次的數據結構并沒有被拷貝到新地址里面去，而是和原對象的可變地址指向同一個地址，所以在新對象和原對象里對這個可變元素做修改時，兩者對象同時改變。
不可變元素
可變元素
淺拷貝
拷貝前后對象地址應當不同
可變元素
不可變元素
python格式化輸出（使用占位符）：【選修1作業本】P13
%s表示字符串輸出，%d表示整數輸出，%f表示浮點數輸出
示例：
>>> name="Lucy"
>>> age=19
>>> print('%s的年齡是%d'%(name,age))
Lucy的年齡是19
示例：
>>> money=12345.123456789
>>> name="174"
>>> print('%s的工資是%f'%(name,money))
174的工資是12345.123457 默認保留6位小數
示例：
>>> scale=0.13526
>>> print('數據的比例是%.2f%%'%scale)
數據的比例是0.14%
python格式化輸出：
情況一：
>>> rate=0.91826
>>> print("rate的終值為:%0.2f分"%rate)
rate的終值為:0.92分
情況二：
>>> rate=0.91826
>>> print("rate的終值為:%.2f分"%rate)
rate的終值為:0.92分
情況三：
>>> rate=0.91826
>>> print("rate的終值為:%0.3f分"%rate)
rate的終值為:0.918分
作業本 （雙色版）
11.9作業：
《2.1 數據的概念及其操作》1-7題
錯題本：整理《上機實驗練習紙》，例如：升序段個數+其他任意兩題
格式：選擇題（可以剪程序，自己寫解析思路）
編程題：重在一題多解（例如：list.append()或者list=list+[]）
楊輝三角：
1
1 1
1 2 1
1 3 3 1
1 2 6 4 1
1 5 8 10 5 1
………………
數組名：pas 列下標元素
0 1 2 3 4
0 1
行 下 標 位 值 1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
（1）為了在計算機中存儲和處理所指元素，已知數字“6”存儲在數組元素pas[4][2]中,其值由數組元素________和數組元素_________相加得到。
（2）在程序設計時，先將數組pas中的數據元素均賦初值為1，然后從數組元素_____開始進行計算（數字“1”無須再次計算）。
（3）實現輸出該圖形的代碼如下，在程序劃線處填入適當的語句表達式，將程序補充完整。
n=int（input(“請輸入行數n=”)） #輸出n行的楊輝三角
pas=[[1 for in range(n)]for j in range(n)]
for i in range(2,n):
for j in range(1,i):
pas[i][j]=pas[i-1][j-1]+___________
for i in range(n):
s=[] #定義列表s用于輸出每一行所需數據
for j in range(_______):
s.append(pas[i][j])
print(s)
pas[i-1][j]
i+1
數組名：pas 列下標元素
0 1 2 3 4
0 1
行 下 標 位 值 1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
作業本 （雙色版）
11.9作業：
《2.1 數據的概念及其操作》1-7題
下節課復習帶知識清單2張（學考+選考）、《必修1 數據與數據計算》教材

展開更多......

收起↑