2.1《線性表結(jié)構(gòu)及其實現(xiàn)》

1.3認(rèn)識數(shù)據(jù)抽象高中信息技術(shù)/教科版/選擇性必修1目錄1問題導(dǎo)入2.新課講授3.實踐操作4.課堂小結(jié)1.問題導(dǎo)入同學(xué)們，數(shù)據(jù)結(jié)構(gòu)有幾種類型？你認(rèn)為哪一種最簡單？你能舉一些線性結(jié)構(gòu)的例子嗎？數(shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種結(jié)構(gòu)類型。我覺得線性結(jié)構(gòu)最簡單，它是最常見的數(shù)據(jù)組織結(jié)構(gòu)。排列好的圖書、餐廳刷卡就餐都是線性結(jié)構(gòu)。那線性結(jié)構(gòu)有什么特點呢？我們一起來回顧一下吧！知識回顧——線性結(jié)構(gòu)數(shù)據(jù)元素之間的排列次序存在一種明確的先后關(guān)系，這樣的數(shù)據(jù)組織方式稱為線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，除了最后一個元素，每個元素都有一個唯一的后繼元素，所有元素都排成一個線性序列。這種圖書排列方式是線性的嗎？不是。因為它的排列是無序的。不符合線性排列的有序特征。2.新課講授線性表的概念線性表(linearlist)按線性結(jié)構(gòu)組織數(shù)據(jù)元素。在線性表中，數(shù)據(jù)元素之間存在前后的順序關(guān)系。每個數(shù)據(jù)元素都有一個順序號，順序號是連續(xù)的整數(shù)。通過順序號可以訪問數(shù)據(jù)元素。線性表中的數(shù)據(jù)元素可以是一個數(shù)或一個字符，也可以是一個對象。線性表中的順序號從0開始，而日常生活中說第幾個元素，一般是從1開始，比如第12個元素的順序號為11，請注意區(qū)分。

任務(wù)一

手工整理圖書

活動1認(rèn)識線性排列填一填（1）從左數(shù)第1本書的書名是,緊挨著它的后一本是

。（2）第3本書的書名是

，緊挨著它的后一本是

，緊挨著它的前一本是。（3）第8本書的書名是

，緊挨著它的前一本是

?！稊?shù)據(jù)與計算》《信息系統(tǒng)與社會》《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》《人工智能初步》《信息系統(tǒng)與社會》《算法初步》《開源硬件項目合計》

任務(wù)一

手工整理圖書

活動2整理圖書填一填（1）添加圖書。圖書館新采購了圖書《移動應(yīng)用設(shè)計》，放在書架最右邊，請在圖左圖中相應(yīng)的書脊上寫上書名。（2）借閱圖書。有同學(xué)借閱了圖書《人工智能初步》，請在右圖中相應(yīng)的書脊上寫上書名。移動應(yīng)用設(shè)計三維設(shè)計與創(chuàng)意開源硬件項目設(shè)計算法初步設(shè)計

任務(wù)一

手工整理圖書

活動2整理圖書填一填（3）歸還圖書。有同學(xué)歸還了圖書《網(wǎng)絡(luò)基礎(chǔ)》，需將該書放置在圖書《數(shù)據(jù)管理與分析》左面，請在圖中相應(yīng)的書脊上寫上書名。（4）查詢圖書。經(jīng)過以上操作后，圖書列表中共有本圖書，第8本書的書名是

。

網(wǎng)絡(luò)基礎(chǔ)

三維設(shè)計與創(chuàng)意開源硬件項目設(shè)計9算法初步線性表的特征在線性表中插入或刪除數(shù)據(jù)元素，該元素之后的數(shù)據(jù)元素順序號都將改變。線性表中的順序號從0開始，而日常生活中說第幾個元素，一般是從1開始，比如第12個元素的順序號為11，請注意區(qū)分。從以上活動可以看出，線性表的基本操作主要包括追加、刪除、插入、查詢等操作。為了便于在程序中使用線性表解決問題，需要定義線性表抽象數(shù)據(jù)類型(ADTLinearList)，接口如下：線性表抽象數(shù)據(jù)類型ADTLinearList:LinearList():創(chuàng)建空線性表。appendItem(item):將數(shù)據(jù)元素item追加到線性表removeItem(pos):從線性表中刪除pos位置的數(shù)據(jù)元素getItem(pos):取得pos位置的數(shù)據(jù)元素。setItem(pos,item):設(shè)置線性表pos位置的數(shù)據(jù)為item。size():獲得線性表中數(shù)據(jù)元素的個數(shù)。isEmpt():判斷線性表是否為空insertItem(item,pos):將item插入表中pos位置。

任務(wù)一

手工整理圖書

活動3用線性表實現(xiàn)圖書整理填一填借助抽象數(shù)據(jù)類型LinearList，可以方便地用線性表實現(xiàn)任務(wù)。請補全下面的代碼或注釋。01.books=LinearList(

)

#創(chuàng)建一個空線性表02.books.appendItem("數(shù)據(jù)與計算")

#追加“數(shù)據(jù)與計算”03.books.appendItem("信息系統(tǒng)與社會”)

#追加“信息系統(tǒng)與社會“04.books.appendItem("數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)”)

#

05.books.appendItem("數(shù)據(jù)管理與分析”)#

06.books.appendItem("人工智能初步")

#

07.books.appendItem("三維設(shè)計與創(chuàng)意”)#

08.books.appendItem("開源硬件項目設(shè)計”)#

追加“數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)“追加“數(shù)據(jù)管理分析“追加“人工智能初步“追加“三維設(shè)計與創(chuàng)意“追加“開源硬件項目設(shè)計“

#追加“算法初步”

#追加“移動應(yīng)用設(shè)計”11.books.removeItem(4)

#在位置4刪除圖書12.books.insertItem("網(wǎng)絡(luò)基礎(chǔ)”,3)

#在位置3插人“網(wǎng)絡(luò)基礎(chǔ)”13.print(books.getItem(7))

#顯示位置7的圖書名稱14.print(books.size())

#顯示圖書數(shù)量books.appendItem("算法初步”)books.appendItem("移動應(yīng)用設(shè)計”)

任務(wù)一

手工整理圖書

活動3用線性表實現(xiàn)圖書整理

任務(wù)二

編程整理圖書

活動1用順序存儲實現(xiàn)線性表Python的列表采用了順序存儲的方式，可以保存多個數(shù)據(jù)，并提供了一些好用的方法。利用列表可以方便地實現(xiàn)線性表。列表的第一個存儲位置的順序號為0。以下用列表items來保存線性表中的數(shù)據(jù)元素(1)創(chuàng)建空列表由構(gòu)造方法__init__（）完成，它的功能是生成一個空的列表items。01.classLinearList:02.def__init__(self):03.self.items=[]

#空列表

任務(wù)二

編程整理圖書

活動1用順序存儲實現(xiàn)線性表(2)追加數(shù)據(jù)元素在列表最后添加數(shù)據(jù)元素，可以使用列表的方法append。04.defappendItem(self,item):05.self.items.append(item)

#在列表最后增加一個元素(3)刪除數(shù)據(jù)元素刪除線性表指定位置的數(shù)據(jù)元素，可以使用列表的pop方法。06.defremoveItem(self,pos):07.self.items.pop(pos)

#刪除表中pos位置的元素

任務(wù)二

編程整理圖書

活動1用順序存儲實現(xiàn)線性表(4)插入數(shù)據(jù)元素在線性表中把一個元素插入到指定位置，這個位置及之后的數(shù)據(jù)元素會向后移動，順序號發(fā)生變化。08.definsertItem(self,item,pos):

#把item插人表中pos位置09.self.items.insert(pos,item)

任務(wù)二

編程整理圖書

活動1用順序存儲實現(xiàn)線性表(5)其他操作defgetItem(self,pos):

#獲得位置pos的數(shù)據(jù)元素returnself.items[pos]

defsetItem(self,pos,item):

#設(shè)置位置pos的值為itemself.items[pos]=itemdefsize(self):

#獲取線性表的數(shù)據(jù)元素個數(shù)returnlen(self.items)defisEmpty(self):

#判斷線性表是否為空returnself.size()==0

任務(wù)二

編程整理圖書

活動1用順序存儲實現(xiàn)線性表順序表和數(shù)組線性表的順序存儲用一組連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。利用這種存儲方式實現(xiàn)的線性表叫作順序表。如果順序表中各數(shù)據(jù)元素占用的存儲空間大小相同(比如是同一種類型的數(shù)據(jù))，這樣的順序表叫數(shù)組。各個數(shù)據(jù)元素叫數(shù)組元素，數(shù)據(jù)元素的序號叫數(shù)組下標(biāo)。如果知道數(shù)組的起始存儲位置及單個數(shù)組元素占用空間大小，各個數(shù)組元素的存儲位置可以通過計算得到，因而數(shù)組具有隨機訪問的特點，存取數(shù)組元素的效率很高。

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表用鏈?zhǔn)酱鎯崿F(xiàn)的線性表是一個節(jié)點序列。節(jié)點中不僅保存數(shù)據(jù)，還保存下一個節(jié)點的存儲位置。用鏈?zhǔn)酱鎯崿F(xiàn)的線性表也叫作鏈表。首先定義鏈?zhǔn)酱鎯λ枰墓?jié)點類。01.classNode:02.def__init__(self,item):self.data=item

#數(shù)據(jù)區(qū)04.#鏈接區(qū)，指向下一個節(jié)點，初始化時為空05.self.next=None

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(1)創(chuàng)建空線性表創(chuàng)建空線性表由構(gòu)造方法__init__（）完成。鏈表需要有一個頭節(jié)點引用變量head指向第一個節(jié)點。新創(chuàng)建的鏈表還沒有節(jié)點，所以將head指向空。06.#鏈?zhǔn)酱鎯崿F(xiàn)的線性表07.classLinearList:08.def__init__(self):09.self.head=

#讓頭節(jié)點引用指向空None

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(2)追加數(shù)據(jù)元素在鏈表的末端添加節(jié)點，首先生成新節(jié)點，再找到鏈表尾節(jié)點，最后讓尾節(jié)點指向新節(jié)點。10.#在鏈表末端添加數(shù)據(jù)元素11.defappendItem(self,item):12.temp=Node(item)

#用item生成節(jié)點類對象temp#如果鏈表為空13.ifself.head==None:14.self.head=temp15.return

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(2)追加數(shù)據(jù)元素16.tail=

#tai1先指向頭節(jié)點17.whiletail.next!=None:

#tail還沒有指向最后節(jié)點18.tail=tail.next

#向后移動19.tail.next=

#鏈接新節(jié)點self.headtemp

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(3)刪除數(shù)據(jù)元素刪除鏈表中的數(shù)據(jù)元素，需要先從第一個節(jié)點開始向后移，直到指定位置。假設(shè)要刪除的節(jié)點的下一個節(jié)點為p。先移動到要刪除位置前面的節(jié)點previous，再讓previous指向節(jié)點p。20.#刪除表中pos位置的節(jié)點28.21.defremoveItem(self，pos):22.previous=self.head

#要刪除位置的前一個位置

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(3)刪除數(shù)據(jù)元素23.ifpos==0:

#如果要刪除的是鏈表頭節(jié)點24.25.return26.n=927.whilen<pos-1:

#找到要刪除的前一個節(jié)點28.previous=previous.next29.n=n+130.previous.next=

#刪除節(jié)點previous.next.next

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(4)獲取數(shù)據(jù)元素獲得鏈表指定位置的數(shù)據(jù)元素，需要先從頭節(jié)點移動到指定位置，再返回該位置的數(shù)據(jù)元素。請補全下面的代碼。31.#得到pos位置的數(shù)據(jù)元素32.defgetItem(self,pos):33.current=self.head#沒到指定位置34.count=035.whilecount<pos:

36.current=

#指向下一個節(jié)點37.count=count+1#數(shù)加138.returncurrent.data#返回數(shù)據(jù)元素current.next

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(5)獲取數(shù)據(jù)元素個數(shù)從頭節(jié)點遍歷整個鏈表，并計算數(shù)據(jù)元素節(jié)點的個數(shù)。39.#統(tǒng)計鏈表的節(jié)點數(shù)40.defsize(self):41.current=self.head#指向頭節(jié)點42.count=043.whilecurrent!=None:#不是鏈表的結(jié)尾#節(jié)點數(shù)增加144.count=count+1#節(jié)點數(shù)加145.current=#指向下一個節(jié)點46.returncount#返回節(jié)點數(shù)current.next

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表(6)判斷線性表是否為空判斷線性表是否為空,可以通過判斷頭節(jié)點引用是否為None實現(xiàn)。47.defisEmpty(self):#判斷鏈表是否為空48.returnself.head==None(7)插入數(shù)據(jù)元素插入節(jié)點需要先產(chǎn)生一個新節(jié)點，放置要插入的數(shù)據(jù)元素;然后從頭節(jié)點移動到插入位置前面的節(jié)點previous;最后讓新節(jié)點指向previous的后一個節(jié)點，讓previous指向新節(jié)點。請補全下面的代碼。

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表49.#將item插入表中pos位50.definsertItem(self,item,pos):51.temp=Node(item)#生成新節(jié)點52.ifpos==0:#如果在頭節(jié)點前插人53.temp.next=self.head#新節(jié)點指向頭節(jié)點54..self.head=temp#頭節(jié)點指向新節(jié)點55..return(7)插入數(shù)據(jù)元素

任務(wù)二

編程整理圖書

活動2用鏈?zhǔn)酱鎯崿F(xiàn)線性表56.previous=self.head#指向插入位置前一節(jié)點57.n=0#計數(shù)變量置058.whilen<pos-1: