第2章線性表5

1、第第2章章 線性表線性表2.1 線性表的定義線性表的定義2.2 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)2.3 2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 2.4 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加數(shù)據(jù)結(jié)構(gòu)三個(gè)方面的問(wèn)題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間 在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，可以根據(jù)所做的運(yùn)算不同，將數(shù)據(jù)組織成不同的形式，以便于做該種運(yùn)算，從而提高數(shù)據(jù)處理的效率。 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。例如：向量、矩陣 圖書館卡片目錄 數(shù)據(jù)結(jié)構(gòu)的基本概念現(xiàn)

2、實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。描述一年四季的季節(jié)名 春，夏，秋，冬 可以作為季節(jié)的數(shù)據(jù)元素；表示數(shù)值的各個(gè)數(shù) 18，11，35，23，16， 可以作為數(shù)值的數(shù)據(jù)元素；表示家庭成員的各成員名 父親，兒子，女兒 可以作為家庭成員的數(shù)據(jù)元素。 前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對(duì)象的不同而不同。 一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。1.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合D；反映D中各

3、數(shù)據(jù)元素之間的前后件關(guān)系R。 數(shù)據(jù)結(jié)構(gòu)可以表示成 B（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)。線性關(guān)系為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組 （a，b） 表示a是b的前件，b是a的后件。例如 B（D，R） D春，夏，秋，冬 R(春，夏)，(夏，秋)，(秋，冬)春夏秋冬樹(shù)家庭成員數(shù)據(jù)結(jié)構(gòu) B（D，R） D父親，兒子，女兒 R(父親，兒子），(父親，女兒）n維向量 X（x1，x2，xn） 也是一種數(shù)據(jù)結(jié)構(gòu)。即 X（D，R） Dx1，x2，xn R(x1，x2)，(x2，x3)，(xn1，xn)父親兒子女兒mn的矩陣是一個(gè)數(shù)據(jù)結(jié)構(gòu)。即 A（D，R） DA1

4、，A2，AmR(A1，A2)，(A2，A3)，(Ai，Ai1)，(Am1，Am)其中Ai=（ai1，ai2，ain），i1，2，m Ai（Di，Ri） Diai1，ai2，ain Ri(ai1，ai2)，(ai2，ai3)，(aij，ai，j1)，(ai，n1，ain)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)） 數(shù)據(jù)的物理物理結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。 常用的存儲(chǔ)結(jié)構(gòu)有： 順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。 采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。 數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示（數(shù)據(jù)結(jié)點(diǎn)，結(jié)點(diǎn)）用一

5、條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。 一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示 家庭成員間輩份關(guān)系數(shù)據(jù)結(jié)的圖形表示數(shù)據(jù)結(jié)構(gòu)的形式：（1）線性結(jié)構(gòu)：線性表、棧、隊(duì)列、數(shù)組（2）樹(shù)形（層次）結(jié)構(gòu)：樹(shù)（3）網(wǎng)狀結(jié)構(gòu)：圖線性結(jié)構(gòu)： （1）有且只有一個(gè)根結(jié)點(diǎn)； （2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件， 也最多有一個(gè)后件。1.什么是線性表什么是線性表(Linear List)向量(x1，x2，xn)是一個(gè)長(zhǎng)度為n的線性表英文小寫字母表(a，b，c，z)是一個(gè)長(zhǎng)度為26的線性表一年中的四個(gè)季節(jié)(春，夏，秋，冬)是一個(gè)長(zhǎng)度為4的線性表矩陣是一個(gè)比較復(fù)雜的線性表2.1 線性表的概念線性表的概念學(xué)生情況登記表是一個(gè)復(fù)雜的線性表 由若干數(shù)

6、據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record) 由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)列： 屬性 特征 字段 線性表是由n(n0)個(gè)數(shù)據(jù)元素a1，a2，an組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表或是一個(gè)空表，或可以表示為 (a1，a2，ai，an) 其中ai(i1，2，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。L =（a1, a2, ai-1，ai, ai1 ，, an）n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素第一個(gè)元素第一個(gè)元素ai的直接前趨的直接前趨ai的直接后繼的直接后繼i是元素是元素ai的的位序位

7、序 ，表示表示ai在表中的位在表中的位置置n為元素總個(gè)數(shù)，為元素總個(gè)數(shù)，即即表長(zhǎng)表長(zhǎng)空表空表最后一個(gè)元素最后一個(gè)元素定義：線性表是定義：線性表是n(n0)個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列, ,記為：記為： (1) 初始化初始化操作操作 initlist(L) 建立一個(gè)空表，即建立一個(gè)空表，即n=0(2) 求表長(zhǎng)求表長(zhǎng)操作操作 getlen(L) 返回線性表返回線性表L的長(zhǎng)度的長(zhǎng)度(3) 元素定位元素定位操作操作 locate(L,x) 返回元素返回元素x在線性表在線性表L中中第一次出現(xiàn)第一次出現(xiàn)的位置。若存在，返的位置。若存在，返回其位序，否則，返回回其位序，否則，返回0(4) 取元素

8、取元素操作操作 getelem(L,i,e) 返回線性表返回線性表L的第的第i個(gè)元素的值，用個(gè)元素的值，用e帶回帶回(5) 插入插入操作操作 insert(L,i,x) 在線性表在線性表L 的第的第i個(gè)位置上插入一個(gè)值為個(gè)位置上插入一個(gè)值為x的元素的元素 i的合法取值范圍是：的合法取值范圍是：1in1(6) 刪除刪除操作操作 delete(L,i) 刪除線性表刪除線性表L的第的第i個(gè)元素，個(gè)元素，i的合法到值范圍是：的合法到值范圍是： 1in輸出輸出操作操作 list(L) 按先后順序輸出線性表按先后順序輸出線性表L的所有元素值的所有元素值線性表的基本操作線性表的基本操作2.2 線性表的順序表

9、示和實(shí)現(xiàn)定義：定義：線性表的順序表示是指線性表的順序表示是指用一組地址連續(xù)的存儲(chǔ)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。元素元素地址地址計(jì)算方法：計(jì)算方法：LOC(ai)=LOC(a1)+(i-1)*l (1in) 內(nèi)存空間a1a2aianLoc(a1)+l邏輯地址12in空閑Loc(a1)Loc(a1)+(i-1)lLoc(a1)+(n-1)l其中：其中： l 一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù)一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù) LOC(ai) 順序表順序表第第i個(gè)元素的地址個(gè)元素的地址 LOC(a1) 順序表的基址（首地址）順序表的基址（首地址）L =（a1, a2

10、, ai-1，ai, ai1 ，, an）實(shí)現(xiàn)元素的實(shí)現(xiàn)元素的隨機(jī)存取隨機(jī)存取順序表（線性表的順序表示）順序表（線性表的順序表示）特點(diǎn)：特點(diǎn)：邏輯上相鄰的元素，它們物理地址相鄰，邏輯上相鄰的元素，它們物理地址相鄰，可實(shí)現(xiàn)元素的可實(shí)現(xiàn)元素的隨機(jī)存取隨機(jī)存取。 靜態(tài)順序表靜態(tài)順序表-靜態(tài)數(shù)組靜態(tài)數(shù)組動(dòng)態(tài)順序表動(dòng)態(tài)順序表-動(dòng)態(tài)分配存儲(chǔ)空間動(dòng)態(tài)分配存儲(chǔ)空間 整型一維數(shù)組存放長(zhǎng)度為8的線性表(29,18,56,63,35,24,31,47)順序表的實(shí)現(xiàn)：順序表的實(shí)現(xiàn)：線性表：線性表：L=(aL=(a1 1,a,a2 2, ,a,an n) )順序表：在物理存儲(chǔ)上如何描述一個(gè)順序存儲(chǔ)的線性順序表：在物理存

11、儲(chǔ)上如何描述一個(gè)順序存儲(chǔ)的線性表呢？表呢？順序表特點(diǎn)：占用一段連續(xù)存儲(chǔ)空間。順序表特點(diǎn)：占用一段連續(xù)存儲(chǔ)空間。問(wèn)題：?jiǎn)栴}：如何申請(qǐng)？初始存儲(chǔ)空間到底多大合適？如何申請(qǐng)？初始存儲(chǔ)空間到底多大合適？方法一：靜態(tài)方法一：靜態(tài)一維數(shù)組。一維數(shù)組。例如：例如：int a100;int a100;方法二：方法二：動(dòng)態(tài)動(dòng)態(tài)一維數(shù)組。一維數(shù)組。newnew，mallockmallock順序表所占用的存儲(chǔ)空間的順序表所占用的存儲(chǔ)空間的當(dāng)前容量當(dāng)前容量可能隨時(shí)變化。可能隨時(shí)變化。存儲(chǔ)空間基地址（首地址）。存儲(chǔ)空間基地址（首地址）。順序表長(zhǎng)度，即當(dāng)前順序表中的元素個(gè)數(shù)。順序表長(zhǎng)度，即當(dāng)前順序表中的元素個(gè)數(shù)。動(dòng)態(tài)動(dòng)態(tài)

12、分配一維數(shù)組分配一維數(shù)組：在在初始化時(shí)初始化時(shí)先用函數(shù)先用函數(shù)malloc()為順序表分配一個(gè)基本為順序表分配一個(gè)基本容量；在容量；在操作過(guò)程中操作過(guò)程中，若順序表的空間不足，再用，若順序表的空間不足，再用函數(shù)函數(shù)realloc()增加空間。動(dòng)態(tài)分配的內(nèi)存增加空間。動(dòng)態(tài)分配的內(nèi)存不用時(shí)不用時(shí)必須必須用用free()釋放。釋放。 頭文件：頭文件：stdlib.h 或或 malloc.h1)分配內(nèi)存函數(shù)分配內(nèi)存函數(shù)void*malloc(size);作用：作用：分配分配size字節(jié)大小的內(nèi)存區(qū)域，成功返回該內(nèi)存區(qū)域的字節(jié)大小的內(nèi)存區(qū)域，成功返回該內(nèi)存區(qū)域的首地址首地址，失敗返回，失敗返回NULL(

13、空指針空指針)。2)重新分配內(nèi)存重新分配內(nèi)存void*realloc(void *block, size_t size);參數(shù)參數(shù)block指定指定原內(nèi)存區(qū)域原內(nèi)存區(qū)域的首地址的首地址, size指定指定新內(nèi)存新內(nèi)存的大小。的大小。作用：作用：重新分配重新分配size字節(jié)大小的內(nèi)存區(qū)域。字節(jié)大小的內(nèi)存區(qū)域。 操作過(guò)程：操作過(guò)程：先分配一新的先分配一新的size字節(jié)的內(nèi)存，然后將字節(jié)的內(nèi)存，然后將block處處(原原內(nèi)存區(qū)域處內(nèi)存區(qū)域處)的數(shù)據(jù)全部的數(shù)據(jù)全部依次拷貝依次拷貝到新的內(nèi)存區(qū)域中，成功返到新的內(nèi)存區(qū)域中，成功返回新內(nèi)存區(qū)域的首地址，失敗返回回新內(nèi)存區(qū)域的首地址，失敗返回NULL。3)釋

14、放內(nèi)存釋放內(nèi)存void free(void *block); 作用：作用：釋放釋放block指定的內(nèi)存空間。指定的內(nèi)存空間。C+ 動(dòng)態(tài)存儲(chǔ)分配new / delete 運(yùn)算符(單目)1.new 申請(qǐng)動(dòng)態(tài)存儲(chǔ)申請(qǐng)動(dòng)態(tài)存儲(chǔ)(內(nèi)存內(nèi)存)空間空間 =new ； =new ； 為數(shù)組分配內(nèi)存為數(shù)組分配內(nèi)存2.delete 釋放已申請(qǐng)但不用的存儲(chǔ)（內(nèi)存）空釋放已申請(qǐng)但不用的存儲(chǔ)（內(nèi)存）空間間 delete ；C+ 輸入輸出語(yǔ)句輸入數(shù)據(jù) cin變量名; /從鍵盤為變量賦值輸出數(shù)據(jù) cout變量名; /輸出變量值 cout=0;i-) L.elemi+1=L.elemi; /下標(biāo)下標(biāo)0,length-1的元素

15、逐個(gè)后移的元素逐個(gè)后移 L.elem0=x; L.length+; return 1; int Ins_SList2(StaticList &L, int i, int x) /在表中下標(biāo)為在表中下標(biāo)為i的位置插入數(shù)據(jù)的位置插入數(shù)據(jù)xif(L.length=L.listsize) printf(“The list is overflow!n”); return -1; /順序表已滿順序表已滿(沒(méi)有多余空間沒(méi)有多余空間),返回返回-1，表示插入失敗，表示插入失敗 else for(int j=L.length-1;j=i;j-) L.elemj+1=L.elemj; /下標(biāo)下標(biāo)i,len

16、gth-1的元素逐個(gè)后移的元素逐個(gè)后移 L.elemi=x; L.length+; return 1;void print(StaticList &L) /遍歷線性表元素遍歷線性表元素 for(int i=0;i=L.length-1;i+) coutL.elemi ; /輸出元素輸出元素 coutendl; /輸出回車換行符輸出回車換行符刪除操作1.表尾,不產(chǎn)生數(shù)據(jù)元素的移動(dòng).2.表頭,產(chǎn)生數(shù)據(jù)元素的移動(dòng).3.表中第i個(gè)位置,產(chǎn)生數(shù)據(jù)元素的移動(dòng).刪除過(guò)程在順序表中刪除元素2001234567891214202122232425靜態(tài)順序表的刪除操作在順序表中刪除元素2001234567

17、8912142122232425靜態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425靜態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425靜態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425靜態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425靜態(tài)順序表的刪除操作刪除成功刪除成功線性表在順序存儲(chǔ)下的刪除運(yùn)算線性表在順序存儲(chǔ)下的刪除運(yùn)算 若要?jiǎng)h除第若要?jiǎng)h除第i（1in）個(gè)元素時(shí)，需從第）個(gè)元素時(shí)，需從第i+1個(gè)元素開(kāi)始，直至第個(gè)元素開(kāi)始，直至第n個(gè)元

18、素（共個(gè)元素（共n-i個(gè)元素）依次個(gè)元素）依次前移前移一個(gè)位置；一個(gè)位置； 線性表長(zhǎng)度減小線性表長(zhǎng)度減小1. n-i= n-(i+1)+1int Del_SList2(StaticList &L) /刪除表尾元素刪除表尾元素if(L.length=0) printf(“The list is empty!n”); return -1; /順序表為空順序表為空(沒(méi)有元素可刪沒(méi)有元素可刪),返回返回-1,刪除失敗刪除失敗elseL.length-;return 1;int Del_SList1(StaticList &L) /刪除表頭元素，第刪除表頭元素，第1個(gè)元素，下標(biāo)為個(gè)元素，

19、下標(biāo)為0if(L.length=0) printf(“The list is empty!n”); return -1; /順序表為空順序表為空(沒(méi)有元素可刪沒(méi)有元素可刪),返回返回-1,刪除失敗刪除失敗elsefor(int i=1;i=L.length-1;i+) /數(shù)據(jù)由后往前移到數(shù)據(jù)由后往前移到L.elemi-1=L.elemi;L.length-;return 1;int Del_SList(StaticList &L, int i) /刪除表中數(shù)組下標(biāo)為刪除表中數(shù)組下標(biāo)為i處的元素，第處的元素，第i+1個(gè)元素個(gè)元素if(L.length=0) printf(“The lis

20、t is empty!n”); return -1; /順序表為空順序表為空(沒(méi)有元素可刪沒(méi)有元素可刪),返回返回-1,刪除失敗刪除失敗 else if (iL.length-1) printf(“The i is error!n”); return 0; else / i=0 & i=L.length-1for(int j=i+1;j=L.length-1;j+) /下標(biāo)下標(biāo)i+1,length-1的元素逐個(gè)前移的元素逐個(gè)前移L.elemj-1=L.elemj;L.length-;return 1;int Del_SList(StaticList &L, int i) /刪除

21、表中第刪除表中第i個(gè)元素個(gè)元素,下標(biāo)是下標(biāo)是i-1if(L.length=0) printf(“The list is empty!n”); return -1; /順序表為空順序表為空(沒(méi)有元素可刪沒(méi)有元素可刪),返回返回-1,刪除失敗刪除失敗 else if (i-1L.length-1) printf(“The i is error!n”); return 0; else / i-1=0 & i-1=L.length-1for(int j=i;j=L.length-1;j+) /下標(biāo)下標(biāo)i+1,length-1的元素逐個(gè)前移的元素逐個(gè)前移L.elemj-1=L.elemj;L.l

22、ength-;return 1;遍歷操作(輸出)void print(StaticList &L)/輸出線性表各元素輸出線性表各元素 for(int i=0;i=L.length-1;i+) coutL.elemi ; /輸出輸出coutendl;#include stdafx.h#includeusing namespace std;#define LIST_INIT_SIZE 100 struct StaticListint elemLIST_INIT_SIZE;int length;int listsize;void InitList_StaticList(StaticList

23、&L) L.length=0; L.listsize=LIST_INIT_SIZE; int Ins_SList(StaticList &L, int x)if(L.length=L.listsize) return -1;else L.elemL.length=x; L.length+; return 1;void print(StaticList &L)for(int i=0;i=L.length-1;i+) coutL.elemi ; /輸出輸出coutendl;int main(int argc, char* argv)StaticList SL;InitLis

24、t_StaticList(SL); coutenter numbers:x; /輸入輸入if(x=9999) break;else Ins_SList(SL,x); coutThe array elems:endl; print(SL); return 0;#include stdafx.h#includeusing namespace std;#define LIST_INIT_SIZE 100 struct StaticList/初始化線性表初始化線性表int elemLIST_INIT_SIZE;int length;int listsize;void InitList_StaticLi

25、st(StaticList &L) /初始化線性表初始化線性表 L.length=0; L.listsize=LIST_INIT_SIZE; int Ins_SList(StaticList &L, int x) /在表尾插入新元素在表尾插入新元素xif(L.length=L.listsize) return -1;else L.elemL.length=x; L.length+; return 1;void print(StaticList &L) /輸出線性表元素輸出線性表元素 for(int i=0;i=L.length-1;i+) coutL.elemi ; c

26、outendl;int main(int argc, char* argv)StaticList SL;InitList_StaticList(SL); coutenter numbers:x; /輸入輸入if(x=9999) break;else Ins_SList(SL,x); coutThe array elems:endl; print(SL); return 0;int main(int argc, char* argv)StaticList SL;InitList_StaticList(SL);coutenter numbers:x; /輸入輸入if(x=9999) break;e

27、lse Ins_SList(SL,x); coutThe array elems:endl; print(SL); Del_SList(SL,5);coutThe new array elems:endl;print(SL);return 0;動(dòng)態(tài)動(dòng)態(tài)分配一維數(shù)組分配一維數(shù)組：在在初始化時(shí)初始化時(shí)先用函數(shù)先用函數(shù)malloc()為順序表分配一個(gè)基本為順序表分配一個(gè)基本容量；在容量；在操作過(guò)程中操作過(guò)程中，若順序表的空間不足，再用，若順序表的空間不足，再用函數(shù)函數(shù)realloc()增加空間。動(dòng)態(tài)分配的內(nèi)存增加空間。動(dòng)態(tài)分配的內(nèi)存不用時(shí)不用時(shí)必須必須用用free()釋放。釋放。 頭文件：頭文件：s

28、tdlib.h 或或 malloc.h順序存儲(chǔ)：數(shù)據(jù)元素的邏輯順序與物理順序一致靜態(tài)順序線性表-一維數(shù)組實(shí)現(xiàn)動(dòng)態(tài)順序線性表-指針+數(shù)組（動(dòng)態(tài)內(nèi)存分配）1)分配內(nèi)存函數(shù)分配內(nèi)存函數(shù)void*malloc(size);作用：作用：分配分配size字節(jié)大小的內(nèi)存區(qū)域，成功返回該內(nèi)存區(qū)域的字節(jié)大小的內(nèi)存區(qū)域，成功返回該內(nèi)存區(qū)域的首地址首地址，失敗返回，失敗返回NULL(空指針空指針)。2)重新分配內(nèi)存重新分配內(nèi)存void*realloc(void *block, size_t size);參數(shù)參數(shù)block指定指定原內(nèi)存區(qū)域原內(nèi)存區(qū)域的首地址的首地址, size指定指定新內(nèi)存新內(nèi)存的大小。的大小。作用

29、：作用：重新分配重新分配size字節(jié)大小的內(nèi)存區(qū)域。字節(jié)大小的內(nèi)存區(qū)域。 操作過(guò)程：操作過(guò)程：先分配一新的先分配一新的size字節(jié)的內(nèi)存，然后將字節(jié)的內(nèi)存，然后將block處處(原原內(nèi)存區(qū)域處內(nèi)存區(qū)域處)的數(shù)據(jù)全部的數(shù)據(jù)全部依次拷貝依次拷貝到新的內(nèi)存區(qū)域中，成功返到新的內(nèi)存區(qū)域中，成功返回新內(nèi)存區(qū)域的首地址，失敗返回回新內(nèi)存區(qū)域的首地址，失敗返回NULL。3)釋放內(nèi)存釋放內(nèi)存void free(void *block); 作用：作用：釋放釋放block指定的內(nèi)存空間。指定的內(nèi)存空間。C+:new / delete 運(yùn)算符(單目)動(dòng)態(tài)存儲(chǔ)分配1.new 申請(qǐng)動(dòng)態(tài)存儲(chǔ)申請(qǐng)動(dòng)態(tài)存儲(chǔ)(內(nèi)存內(nèi)存)空間空

30、間 =new ；1個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) =new ； n個(gè)數(shù)據(jù)，為數(shù)組分配內(nèi)存?zhèn)€數(shù)據(jù)，為數(shù)組分配內(nèi)存2.delete 釋放已申請(qǐng)但不用的存儲(chǔ)（內(nèi)存）空釋放已申請(qǐng)但不用的存儲(chǔ)（內(nèi)存）空間間 delete ；typedef int ElemType;/*在實(shí)際問(wèn)題中，根據(jù)需要定義所需的數(shù)據(jù)元素類型在實(shí)際問(wèn)題中，根據(jù)需要定義所需的數(shù)據(jù)元素類型*/#define LIST_INIT_SIZE 100 /*順序表存儲(chǔ)空間的初始分配量順序表存儲(chǔ)空間的初始分配量*/typedef struct /動(dòng)態(tài)順序表（指針）動(dòng)態(tài)順序表（指針） int length; /*順序表當(dāng)前長(zhǎng)度，即已存入的元素個(gè)數(shù)順序表當(dāng)前長(zhǎng)度，即已

31、存入的元素個(gè)數(shù)*/ int listsize; /*當(dāng)前存儲(chǔ)空間容量當(dāng)前存儲(chǔ)空間容量*/SqList; /* 順序表類型名順序表類型名*/線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：動(dòng)態(tài)順序表的類型定義動(dòng)態(tài)順序表的類型定義 ：ElemType *elem; /*存儲(chǔ)空間基址存儲(chǔ)空間基址*/struct StaticList /靜態(tài)順序表（數(shù)組）靜態(tài)順序表（數(shù)組）/初始化線性表初始化線性表int elemLIST_INIT_SIZE;int length;int listsize; L.elemL.lengthL.listsize0LIST_INIT_SIZELIST_INIT_

32、SIZE長(zhǎng)長(zhǎng)初始狀態(tài)：初始狀態(tài)：s為一個(gè)空的順序表為一個(gè)空的順序表SqList L; typedef int ElemType; #define LIST_INIT_SIZE 100 typedef struct ElemType *elem; int length; int listsize; SqList; 動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);free(elem); 元素存放在元素存放在elem0到到elemlength-1中，中，注意：注意：C語(yǔ)言的數(shù)組下標(biāo)從語(yǔ)言的數(shù)組下標(biāo)

33、從0開(kāi)始。開(kāi)始。初始化操作：初始化操作：創(chuàng)建一個(gè)空的順序表創(chuàng)建一個(gè)空的順序表L L void InitList_Sq( SqList &L ) /* 構(gòu)造一個(gè)空的順序表構(gòu)造一個(gè)空的順序表L*/L-elem = (ElemType *)malloc(INITSIZE *sizeof(ElemType);if (!L-elem) /*容錯(cuò)處理容錯(cuò)處理*/printf(“malloc failure! n ”); exit(1); /* 存儲(chǔ)分配失敗存儲(chǔ)分配失敗*/L-length = 0; /* 長(zhǎng)度為長(zhǎng)度為0*/L-listsize =LIST_INIT_SIZE; /* 當(dāng)前容量為初始

34、存儲(chǔ)容量當(dāng)前容量為初始存儲(chǔ)容量*/算法性能分析：時(shí)間性能算法性能分析：時(shí)間性能 O O(1)(1) 空間性能空間性能 O O(1) (1) int InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表L.elem=new ElemTypeLIST_INIT_SIZE;/申請(qǐng)空間申請(qǐng)空間if(L.elem=0) printf(“failure! n”); return 0; else L.length=0; L.listsize=LIST_INIT_SIZE; return 1; 動(dòng)態(tài)順序表的初始化操作01234567891214202122232425在

35、順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)

36、態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作01234567891214202122232425在順序表中第2個(gè)位置插入元素13X=13動(dòng)態(tài)順序表的插入操作插入成功（1）在表尾插入數(shù)據(jù)元素）在表尾插入數(shù)據(jù)元素int ListEndInsert_Sq(SqList &L,ElemType e)if(L.length=L.listsize)printf(“overflow!n”); return 0;/在表尾插入數(shù)據(jù)在表尾插入數(shù)據(jù)L.elemL.length=e;L.length+;return 1; 1

37、：x=10，L.length=0， L.elem0=10， L.length=12：x=20，L.length=1， L.elem1=20， L.length=23：x=30，L.length=2， L.elem2=30， L.length=311：x=9999 break，結(jié)束循環(huán)書面作業(yè)一、第3周上機(jī)題二、簡(jiǎn)答題1.簡(jiǎn)述數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象的概念；2.簡(jiǎn)述算法的概念及特征；3.簡(jiǎn)述算法的復(fù)雜度分析；4.簡(jiǎn)述線性表的概念及特點(diǎn)；5.簡(jiǎn)述順序存儲(chǔ)線性表（順序表）的特點(diǎn)。（2）在表頭插入數(shù)據(jù)元素）在表頭插入數(shù)據(jù)元素int ListInsert_Sq1(SqList &L,El

38、emType e) if(L.length=L.listsize) printf(“overflow!n”); return 0;for(int i=L.length-1;i=0;i-)L.elemi+1=L.elemi;L.elem0=e; /在表頭插入數(shù)據(jù)在表頭插入數(shù)據(jù)L.length+;return 1; (3) 在順序表在順序表L的的第第i個(gè)位置個(gè)位置插入元素插入元素e，下標(biāo)，下標(biāo)i-1int ListInsert_Sq(SqList &L,int i,ElemType e) n個(gè)元素，個(gè)元素，i【1 . n+1】 ElemType *p,*q; 【1 . length+1】i

39、f (iL.length+1) printf(“error!n”); /插入位置不合法插入位置不合法 return 0; if(L.length=L.listsize) /空間不足空間不足printf(“overflow!n”); return -1; q=&(L.elemi-1); /第第i個(gè)元素的地址個(gè)元素的地址for(p=&(L.elemL.length-1);p=q;- -p)*(p+1)=*p;*q=e;L.length+;return 1;void printSq(SqList &L) ElemType *p; for(p=&(L.elem0);p=

40、&(L.elemL.length-1);p+) cout*p ; coutendl;void print(SqList &L)for(int i=0;i=L.length-1;i+) coutL.elemi ; coutendl;int main(int argc, char* argv)SqList SSL;int i,x;InitList_Sq(SSL);coutenter numbers:x;if(x=9999) break;else ListEndInsert_Sq(SSL,x); coutThe array elems:endl; printSq(SSL); cout

41、enter the position i:i;coutenter the insert number x:x;ListInsert_Sq(SSL,i,x);coutThe new array elems:endl;printSq(SSL);return 0;在長(zhǎng)度為n的線性表中插入一個(gè)元素e，平均需要移動(dòng)幾次： 1234n12142021100在第n+1處插入，需要移動(dòng)0次在第n處插入，需要移動(dòng)1次在第n-1處插入，需要移動(dòng)2次在第1處插入，需要移動(dòng)n次所以，1n+1個(gè)位置，共有n+1次，平均移動(dòng)次數(shù)為：21.3210nnn即平均移動(dòng)表長(zhǎng)的一半。 1234n12142021100在順序表中刪除

42、元素2001234567891214202122232425動(dòng)態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425動(dòng)態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425動(dòng)態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425動(dòng)態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425動(dòng)態(tài)順序表的刪除操作在順序表中刪除元素20012345678912142122232425動(dòng)態(tài)順序表的刪除操作刪除成功刪除成功動(dòng)態(tài)順序表的刪除操作（1）刪除表尾數(shù)據(jù)元素）刪除表尾數(shù)

43、據(jù)元素int DelEndList_Sq(SqList &L)if(L.length=0) printf(“UNDERFLOW!n”); return -1;elseL.length-;return 1;動(dòng)態(tài)順序表的刪除操作（2）刪除表頭數(shù)據(jù)元素）刪除表頭數(shù)據(jù)元素int DelHeadList_Sq(SqList &L) ElemType *p;if (L.length=0)printf(“UNDERFLOW!n”); return -1; elsefor (p=&(L.elem1);p=&(L.elemL.length-1);p+) *(p-1)=*p; L.

44、length-;return 1; 動(dòng)態(tài)順序表的刪除操作（3）刪除）刪除第第i個(gè)個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素,下標(biāo)下標(biāo)i-1，第，第i+1n個(gè)元素前移個(gè)元素前移int DelList_Sq(SqList &L,int i)ElemType *p;if (iL.length) printf(“error!n”); /刪除位置不合法 return 0; if (L.length=0) printf(“UNDERFLOW!n”);/溢出 return -1; else for (p=&(L.elemi);p=&(L.elemL.length-1);p+) *(p-1)=*p; L.le

45、ngth-; return 1;int main(int argc, char* argv)SqList SSL; /定義構(gòu)造型變量SSLint i,x;InitList_Sq(SSL); /初始化線性表coutenter numbers:x;if(x=9999) break;else ListEndInsert_Sq(SSL,x); /構(gòu)造一個(gè)線性表 coutThe array elems:endl; printSq(SSL); coutenter the position i:i;coutenter the insert number x:x;ListInsert_Sq(SSL,i,x);

46、 /將新元素插入到第i個(gè)位置coutThe new array elems:endl;printSq(SSL);coutenter the deleted position i:i;DelList_Sq(SSL,i); /刪除第刪除第i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素coutThe new deleted array elems:x;if(x=9999) break;else ListEndInsert_Sq(SSL,x); for (i=0;i=10;i+) SSL.elemi=rand(); /rand()隨機(jī)函數(shù)隨機(jī)函數(shù)0,32767 SSL.length+;推廣一下：在長(zhǎng)度為n的線性表中刪除一個(gè)元

47、素e，平均需要移動(dòng)幾次： 1234n12142021100刪除第1個(gè)元素，需要移動(dòng)n-1次刪除第2個(gè)元素，需要移動(dòng)n-2次刪除第3個(gè)元素，需要移動(dòng)n-3次刪除第n個(gè)元素，需要移動(dòng)0次所以，從第1個(gè)元素到第n個(gè)元素，共n個(gè)位置，平均需要移動(dòng)：1234n1214202110021)1(.321nnn動(dòng)態(tài)順序表的查找操作動(dòng)態(tài)順序表的查找操作從前到后順序查找某個(gè)元素是否在順序表中存在：從前到后順序查找某個(gè)元素是否在順序表中存在：int FindList_Sq1(SqList &L,ElemType e) /在順序表在順序表L中查找元素中查找元素e是否存在，是否存在，/如果存在返回對(duì)應(yīng)的下標(biāo)如果

48、存在返回對(duì)應(yīng)的下標(biāo)i+1/否則返回否則返回0 for(int i=0;i=L.length-1;i+)if(L.elemi=e) return (i+1);return 0; 動(dòng)態(tài)順序表的查找操作動(dòng)態(tài)順序表的查找操作從前到后順序查找某個(gè)元素是否在順序表中存在：從前到后順序查找某個(gè)元素是否在順序表中存在：int FindList_Sq(SqList &L,ElemType e) /在順序表在順序表L中查找元素中查找元素e是否存在，是否存在，/如果存在返回對(duì)應(yīng)的下標(biāo)如果存在返回對(duì)應(yīng)的下標(biāo)i+1/否則返回否則返回0 int i=0; ElemType *p; for (p=&(L.e

49、lem0);p=&(L.elemL.length-1);p+) if(*p=e) return (i+1); i+; return 0; e是第一個(gè)元素，循環(huán)是第一個(gè)元素，循環(huán)1次，返回次，返回1e是第是第2個(gè)元素，循環(huán)個(gè)元素，循環(huán)2次，返回次，返回2 e是第一個(gè)元素，循環(huán)是第一個(gè)元素，循環(huán)1次，返回次，返回1int main(int argc, char* argv)SqList SSL;int i,x,fx,flag;InitList_Sq(SSL);coutenter numbers:endl; for (i=0;i=10;i+)SSL.elemi=rand();SSL.leng

50、th+; coutThe array elems:endl; printSq(SSL); coutenter the position i:i;coutenter the insert number x:x;ListInsert_Sq(SSL,i,x);coutThe new array elems:endl;printSq(SSL);coutenter the deleted position i:i;DelList_Sq(SSL,i);coutThe new deleted array elems:endl;printSq(SSL); coutenter the found number

51、fx:fx;flag=FindList_Sq(SSL,fx);if (flag!=0)printf(found %dn,flag);elseprintf(no-found!n);return 0;推廣一下：推廣一下：在長(zhǎng)度為在長(zhǎng)度為n的順序表中按從前到后的方式查找某個(gè)元素平均的順序表中按從前到后的方式查找某個(gè)元素平均需要比較幾次。需要比較幾次。1234n12142021100若查找第1個(gè)，需要1次若查找第2個(gè)，需要2次.若查找第n個(gè)，需要n次故平均需要比較：21.321nnn次。有序順序表的合并有序順序表的合并已知順序表已知順序表LA、LB中的數(shù)據(jù)元素按值非遞中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)

52、要求將減有序排列，現(xiàn)要求將LA和和LB歸并為一個(gè)歸并為一個(gè)新的順序表新的順序表LC，且，且LC中的數(shù)據(jù)元素仍按值中的數(shù)據(jù)元素仍按值非遞減有序排列。非遞減有序排列。1、算法動(dòng)態(tài)演示、算法動(dòng)態(tài)演示358112689111520LA：LB：LC：2358112689111520LA：LB：LC：2358112689111520LA：LB：LC：23358112689111520LA：LB：LC：23358112689111520LA：LB：LC：235358112689111520LA：LB：LC：235358112689111520LA：LB：LC：2356358112689111520LA：LB

53、：LC：2356358112689111520LA：LB：LC：23568358112689111520LA：LB：LC：23568358112689111520LA：LB：LC：235688358112689111520LA：LB：LC：235688358112689111520LA：LB：LC：2356889358112689111520LA：LB：LC：2356889358112689111520LA：LB：LC：235688911358112689111520LA：LB：LC：235688911358112689111520LA：LB：LC：2356889111135811268911

54、1520LA：LB：LC：23568891111358112689111520LA：LB：LC：2356889111115358112689111520LA：LB：LC：2356889111115358112689111520LA：LB：LC：235688911111520358112689111520LA：LB：LC：235688911111520358112689111520LA：LB：LC：2、順序表合并算法的具體實(shí)現(xiàn)void MergeList_Sq(SqList LA,SqList LB,SqList &LC)/LA、LB中元素原來(lái)按非遞減順序存儲(chǔ)中元素原來(lái)按非遞減順序存儲(chǔ)/

55、要求合并后的要求合并后的LC也按照非遞減序存儲(chǔ)也按照非遞減序存儲(chǔ)下標(biāo)下標(biāo)i用來(lái)指示當(dāng)前處理到表用來(lái)指示當(dāng)前處理到表LA的第的第i個(gè)元素，初值為個(gè)元素，初值為0下標(biāo)下標(biāo)j用來(lái)指示當(dāng)前處理到表用來(lái)指示當(dāng)前處理到表LB的第的第j個(gè)元素，初值為個(gè)元素，初值為0While(i不到不到LA的末尾的末尾&j不到不到LB的末尾的末尾)pa用于存儲(chǔ)用于存儲(chǔ)LA的第的第i個(gè)元素個(gè)元素 pb用于存儲(chǔ)用于存儲(chǔ)LB的第的第j個(gè)元素個(gè)元素if(Pa所指元素的值所指元素的值=Pb所指元素的值所指元素的值) 將將Pa所指元素插入所指元素插入LC中；中；i+ k+ else 將將Pb所指元素插入所指元素插入LC中；中；

56、j+ k+If(i沒(méi)有到達(dá)沒(méi)有到達(dá)LA的末尾的末尾) 將將LA中中Pa后面的元素全部插入后面的元素全部插入LC中；中；If(j沒(méi)有到達(dá)沒(méi)有到達(dá)LB的末尾的末尾) 將將LB中中Pb后面的元素全部插入后面的元素全部插入LC中；中；自然語(yǔ)言描述#include stdafx.h#includeusing namespace std;typedef int ElemType;struct SqListElemType *elem; int listsize;int length;void InputData(SqList &LA);void MergeList_Sq(SqList LA,SqL

57、ist LB,SqList &LC);void print(SqList LC);void main()SqList LA,LB,LC;LA.elem=new ElemType100;LA.length=0;LA.listsize=100;LB.elem=new ElemType100;LB.length=0;LB.listsize=100;InputData(LA);InputData(LB);MergeList_Sq(LA,LB,LC);print(LC);void InputData(SqList &LA)couttemp; if(temp!=-9999) LA.elem

58、i=temp;LA.length+; else break;void print(SqList LC)for(int i=0;iLC.length;i+)coutLC.elemi ;coutendl;void InputData(SqList &LA)int temp; couttemp; if(temp!=-9999) LA.elemi=temp; LA.length+; else break;void MergeList_Sq(SqList LA,SqList LB,SqList &LC)/LA、LB中元素原來(lái)按非遞減順序存儲(chǔ)/要求合并后的LC也按照非遞減序存儲(chǔ)int i,

59、j,k;i=j=k=0;/下面生成線性表LCLC.length=LA.length+LB.length;LC.listsize=LA.listsize+LB.listsize;LC.elem=new ElemTypeLC.listsize;while(i=LA.length-1 & j=LB.length-1)/當(dāng)LA、LB同時(shí)不為空時(shí)，進(jìn)行下面操作ElemType pa=LA.elemi;/取LA的第i個(gè)元素ElemType pb=LB.elemj;/取LB的第j個(gè)元素if(pa=pb) /如果pa=pbLC.elemk=pa;/pa插入LC尾部k+;i+;/LC、LA下標(biāo)后移els

60、eLC.elemk=pb;k+;j+;while(i=LA.length-1)/如果LA中還有元素，則所有元素全部插入LC尾部ElemType pa=LA.elemi;LC.elemk=pa;k+;i+;while(jnext=p-next; p-next=s;插入操作插入操作abpcq (1) q=p-next; (2) p-next=q-next;(1)(2)刪除操作刪除操作生成一個(gè)鏈表頭結(jié)點(diǎn)struct LinkNodeint data;struct LinkNode *next;int main(int argc, char* argv )LinkNode *H;/定義鏈表指針定義鏈表指針H=new LinkNode;/申請(qǐng)空間申請(qǐng)空間 H-data=-1;/為成員變量數(shù)據(jù)賦值為成員變量數(shù)據(jù)賦值H-next=0;/為成員變量指針賦值為成員變量指針賦值輸出單鏈表元素輸出單鏈表元素void print(LinkNode *L)/將鏈表將鏈表L中的數(shù)據(jù)輸出到屏幕上，其中中的數(shù)據(jù)輸出到屏幕上，其中L指向頭結(jié)點(diǎn)指