ch021線性表1-定義與順序表.ppt

第2章 線性表,數(shù)據(jù)結(jié)構(gòu)講義,- 定義與順序表示,信息工程學(xué)院 王晟 Email:,2019/7/11,24,2,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 線性表的邏輯結(jié)構(gòu),1. 線性表的定義：是n個數(shù)據(jù)元素的有限序列,n=0時稱為,數(shù)據(jù)元素,線性起點,ai的直接前趨,ai的直接后繼,下標(biāo)，是元素的序號，表示元素在表中的位置,n為元素總個數(shù)，即表長,空表,線性終點,2019/7/11,24,3,例1 分析26 個英文字母組成的英文表,（ A, B, C, D, , Z）,例2 分析學(xué)生情況登記表,數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性,數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性,同一線性表中的元素必定具有相同特性,2019/7/11,24,4,線性表的抽象數(shù)據(jù)類型的定義： ADT List 數(shù)據(jù)對象：D=ai|aiElemset,i=1,2,n,n0 數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n 基本操作： InitList(&l) 操作結(jié)果：構(gòu)造一個空的線性表L DestroyList(&l) 初始條件：線性表已存在 操作結(jié)果：銷毀線性表L,2019/7/11,24,5,自定義 釋放線性表內(nèi)存,Void DestroyList(SqList *L) Free(L-elem); L-length=0; L-listsize=0; ,2019/7/11,24,6,自定義 釋放鏈表內(nèi)存,全部元素都要釋放，可以寫為遞歸程序: typedef struct List ListType data; struct List* next; List,*PList; 可以寫為： void Destroy_List(PList list) if(list) Destroy_List(list-next); free(list); list=NULL; list=NULL;是必須要加的，否則后果自負(fù)。 如不加上list=NULL;該指針還是指向原來的空間,會發(fā)生意外,2019/7/11,24,7,自定義 鏈表內(nèi)存釋放,如果從一個程序完美的角度來說，還是要釋放所有結(jié)點的內(nèi)存為好， 參考代碼： template void LinkedList:makeEmpty() LinkedNode* ptr=head;/游標(biāo)指針 LinkedNode* pre; /指向ptr前個結(jié)點的指針 while(ptr!=NULL) pre=ptr; /保存前個結(jié)點指針 ptr=ptr-link; delete pre; 一般在析構(gòu)函數(shù)里調(diào)用它.,2019/7/11,24,8,自定義 C語言，free函數(shù),遇這種情況會怎么樣?,我現(xiàn)在知道了:用malloc申請了空間并使用之后，要用free函數(shù)釋放內(nèi)存空間,如果不釋放的話，那塊內(nèi)存區(qū)等于被一直占據(jù)著,而無法被其他函數(shù)使用, 但是問題來了. 如:我用malloc申請5個連續(xù)空間: p=(int *)malloc(5*sizeof(int); . 在使用之后,我要釋放它: for(i=1;i=5;i+) free(p+); 這樣就可以釋放了, 但是如果我把循環(huán)該成 for(i=1;i10;i+) free(p+); 這樣:本來我申請了5個，但是我釋放的時候，循環(huán)了10次，也就是說釋放了,后面5個空間了，這樣會造成什么后果呢?,2019/7/11,24,9,自定義,1. 分配內(nèi)存空間函數(shù)malloc 調(diào)用形式： (類型說明符*)malloc(size) 功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為“size“字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。 “類型說明符”表示把該區(qū)域用于何種數(shù)據(jù)類型。 (類型說明符*)表示把返回值強(qiáng)制轉(zhuǎn)換為該類型指針。 “size”是一個無符號數(shù)。 例如： pc=(char *)malloc(100); 表示分配100個字節(jié)的內(nèi)存空間，并強(qiáng)制轉(zhuǎn)換為字符數(shù)組類型，函數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針變量pc。 2. 分配內(nèi)存空間函數(shù) calloc calloc 也用于分配內(nèi)存空間。 調(diào)用形式： (類型說明符*)calloc(n,size) 功能：在內(nèi)存動態(tài)存儲區(qū)中分配n塊長度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。 (類型說明符*)用于強(qiáng)制類型轉(zhuǎn)換。 calloc函數(shù)與malloc 函數(shù)的區(qū)別僅在于一次可以分配n塊區(qū)域。 例如： ps=(struet stu*)calloc(2,sizeof(struct stu); 其中的sizeof(struct stu)是求stu的結(jié)構(gòu)長度。因此該語句的意思是：按stu的長度分配2塊連續(xù)區(qū)域，強(qiáng)制轉(zhuǎn)換為stu類型，并把其首地址賦予指針變量ps。,2019/7/11,24,10,自定義,2. 釋放內(nèi)存空間函數(shù)free 調(diào)用形式： free(void*ptr); 功能：釋放ptr所指向的一塊內(nèi)存空間，ptr是一個任意類型的指針變量，它指向被釋放區(qū)域的首地址。被釋放區(qū)應(yīng)是由malloc或calloc函數(shù)所分配的區(qū)域。 【例】分配一塊區(qū)域，輸入一個學(xué)生數(shù)據(jù)。 main() struct stu int num; char *name; char sex; float score; *ps; ps=(struct stu*)malloc(sizeof(struct stu); ps-num=102; ps-name=“Zhang ping“; ps-sex=M; ps-score=62.5; printf(“Number=%dnName=%sn“,ps-num,ps-name); printf(“Sex=%cnScore=%fn“,ps-sex,ps-score); free(ps); ,2019/7/11,24,11,自定義,本例中，定義了結(jié)構(gòu)stu，定義了stu類型指針變量ps。然后分配一塊stu大內(nèi)存區(qū)，并把首地址賦予ps，使ps指向該區(qū)域。再以ps為指向結(jié)構(gòu)的指針變量對各成員賦值，并用printf輸出各成員值。最后用free函數(shù)釋放ps指向的內(nèi)存空間。整個程序包含了申請內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個步驟，實現(xiàn)存儲空間的動態(tài)分配。 一般我們常說的內(nèi)存泄漏是指堆內(nèi)存的泄漏。堆內(nèi)存是指程序從堆中分配的，大小任意的（內(nèi)存塊的大小可以在程序運(yùn)行期決定），使用完后必須顯示釋放的內(nèi)存。應(yīng)用程序一般使用malloc，realloc，new等函數(shù)從堆中分配到一塊內(nèi)存，使用完后，程序必須負(fù)責(zé)相應(yīng)的調(diào)用free或delete釋放該內(nèi)存塊，否則，這塊內(nèi)存就不能被再次使用，我們就說這塊內(nèi)存泄漏了。,2019/7/11,24,12,ClearList(&l) 初始條件：線性表已存在 操作結(jié)果：置線性表L為空表 ListEmpty(L) 初始條件：線性表已存在 操作結(jié)果：若線性表L為空表，則返回TRUE，否則返回FALSE ListLenght(L) 初始條件：線性表已存在 操作結(jié)果：返回線性表L數(shù)據(jù)元素個數(shù) GetElem(L,i,&e) 初始條件：線性表已存在（1iListLenght(L)） 操作結(jié)果：用e返回線性表L中第i個數(shù)據(jù)元素的值,2019/7/11,24,13,locatElem(L,e,compare() 初始條件：線性表已存在,compare()是數(shù)據(jù)元素判定函數(shù) 操作結(jié)果：返回線性表L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序 PriorElem(L,cur_e,&pre_e) 初始條件：線性表已存在 操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義 NextElem(L,cur_e,&) 初始條件：線性表已存在 操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義,2019/7/11,24,14,ListInsert(&L,i,e) 初始條件：線性表已存在（1iListLenght(L)+1） 操作結(jié)果：在線性表L中第i個數(shù)據(jù)元素之前插入新元素e，L長度加1 ListDelete(&L,i,&e) 初始條件：線性表已存在（1iListLenght(L)） 操作結(jié)果：刪除線性表L中第i個數(shù)據(jù)元素，用e返回其值，L長度減1 ListTraverse(L,visit() 初始條件：線性表已存在 操作結(jié)果：依次對線性表L的每個數(shù)據(jù)元素調(diào)用visit()函數(shù)，一旦visit()失敗，則操作失敗 ADT List,2019/7/11,24,15,上述是線性表抽象數(shù)據(jù)類型的定義，其中只是一些基本操作，另外可以更復(fù)雜。如：將兩個線性表合并等。復(fù)雜的操作可用基本操作實現(xiàn)。 例2-2 void MergeList(List la,List lb,list ,2019/7/11,24,16, while(i=la_len) GetElem(la,i+,ai);ListInsert(lc,k+,ai); while(j=lb_len) GetElem(lb,j+,bj); ListInsert(lc,k+,bj); ,2019/7/11,24,17,線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。,順序存儲定義： 把邏輯上相鄰的數(shù)據(jù)元素存儲在 物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。,2.2.1 順序表的表示,2.2 線性表的順序表示和實現(xiàn),2019/7/11,24,18,線性表順序存儲特點：,1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2. 若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計算方法是： 設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L,2019/7/11,24,19,線性表的順序存儲結(jié)構(gòu)示意圖,地址 內(nèi)容 元素在表中的位序,1,i,2,n,空閑區(qū),i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,2019/7/11,24,20,一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素的第一個字節(jié)的地址是，則的第一個字節(jié)的地址是,113,例1,因此：LOC( M3 ) = 98 + 5 (3-0) =113,解：地址計算通式為：,LOC(ai) = LOC(a1) + L *（i-1）,2019/7/11,24,21,線性表的順序存儲結(jié)構(gòu)定義（靜態(tài)）,#define MAXSIZE 100 typedef struct ElemType elemMAXSIZE; int length; SqList;,2019/7/11,24,22,2.2.2 順序表的實現(xiàn)（或操作）,數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有： 初始化、插入、刪除、查找、排序、修改,1）初始化： Status InitList_Sq(SqList ,2019/7/11,24,23,自定義,將L.elem這個指針指向一塊通過malloc函數(shù)分配的內(nèi)存的地址 這個內(nèi)存的大小為Elemtype這個結(jié)構(gòu)體的size*LIST_INIT_SIZE的乘積這么大 malloc 是用于分配指定size的內(nèi)存的庫函數(shù) 原型：extern void *malloc(unsigned int num_bytes); 用法：#include 或#include 功能：分配長度為num_bytes字節(jié)的內(nèi)存塊 說明：如果分配成功則返回指向被分配內(nèi)存的指針，否則返回空指針NULL。 當(dāng)內(nèi)存不再使用時，應(yīng)使用free()函數(shù)將內(nèi)存塊釋放。 malloc的語法是：指針名=（數(shù)據(jù)類型*）malloc（長度）,（數(shù)據(jù)類型*）表示指針.,2019/7/11,24,24,自定義 C語言函數(shù)realloc,函數(shù)簡介 原型：extern void *realloc(void *mem_address, unsigned int newsize); 語法：指針名=（數(shù)據(jù)類型*）realloc（newsize）,（數(shù)據(jù)類型*）表示指針。 頭文件：#include 有些編譯器需要#include ，在TC2.0中可以使用alloc.h頭文件 功能：先釋放原來mem_address所指內(nèi)存區(qū)域，并按照newsize指定的大小重新分配空間，同時將原有數(shù)據(jù)從頭到尾拷貝到新分配的內(nèi)存區(qū)域，并返回該內(nèi)存區(qū)域的首地址。即重新分配存儲器塊。 返回值：如果重新分配成功則返回指向被分配內(nèi)存的指針，否則返回空指針NULL。 注意：這里原始內(nèi)存中的數(shù)據(jù)還是保持不變的。當(dāng)內(nèi)存不再使用時，應(yīng)使用free()函數(shù)將內(nèi)存塊釋放。,2019/7/11,24,25,2)插入 在線性表的第i個位置前插入一個元素,實現(xiàn)步驟： 將第n至第i 位的元素向后移動一個位置； 將要插入的元素寫到第i個位置； 表長加1。 注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿?,長度為n的線性表變?yōu)殚L度為n+1的線性表 （a1,a2,ai-1,ai,an）,（a1,a2,ai-1,x,ai,an）,2019/7/11,24,26,程序： Status ListInsert_sq(SqList ,順序表插入的演示,2019/7/11,24,27,實現(xiàn)步驟： 將第i +1至第n 位的元素向前移動一個位置； 表長減1。 注意：事先需要判斷，刪除位置i 是否合法?,3)刪除 刪除線性表的第i個位置上的元素,使：長度為n的線性表變?yōu)殚L度為n-1的線性表。（a1,a2,ai-1,ai,ai+1,an）,（a1,a2,ai-1,ai+1,an）,2019/7/11,24,28,Status ListDelete_sq(Sqlist ,順序表刪除的演示,刪除順序表中某個指定的元素的代碼和示意圖如下：,2019/7/11,24,29,4) 順序表的合并,參見例【2-2】,2019/7/11,24,30,2.2.3 順序表的運(yùn)算效率分析,時間效率分析: 插入算法花費(fèi)的時間，主要在于循環(huán)中元素的后移。但是，插入的位置是不固定的，當(dāng)插入位置i=1時，全部元素都得移