指針典型數(shù)據(jù)結(jié)構(gòu)簡介

第2-6講指針2——

典型數(shù)據(jù)結(jié)構(gòu)簡介線性表棧隊列動態(tài)內(nèi)存分配鏈表二叉樹16.1線性表簡介一、線性表的基本概念線性表（linearlist）是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成一個n維向量英文字母表矩陣學(xué)生信息……2線性表是一種線性結(jié)構(gòu)，對于一個非空的線性表，有如下結(jié)構(gòu)特征：有且只有一個頭（根）結(jié)點，無前繼；有且只有一個尾（終端）結(jié)點，無后續(xù)；其它結(jié)點有且只有一個前繼，一個后續(xù)。線性表中結(jié)點的個數(shù)n稱為線性表的長度。當(dāng)n=0時，稱為空表。線性表的存儲結(jié)構(gòu)順序存儲（數(shù)組）表中所有元素所占的空間是連續(xù)的表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表，結(jié)點）每個結(jié)點由兩部分組成：數(shù)據(jù)域和指針域存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致數(shù)據(jù)元素之間的邏輯關(guān)系由指針域來完成3二、線性表的基本運算表的建立線性表的插入順序存儲下的操作注意表的溢出線性表的刪除刪除操作注意空線性表的查找查找操作注意未找到線性表的排序線性表的分解線性表的合并線性表的復(fù)制線性表的逆轉(zhuǎn)4三、棧棧（stack）是一種特殊的線性表，限定在一端進(jìn)行插入與刪除操作。在棧中允許插入、刪除的一端稱為棧頂(top)，不允許插入、刪除的一端稱為棧底(bottom)。棧是按照“先進(jìn)后出”(FILO:firstinlastout)或“后進(jìn)先出”(LIFO:lastinfirstout)原則組織數(shù)據(jù)的。a1a2┋an入棧出棧topbottom5棧的基本運算入棧出棧，讀棧頂元素1.建立一個棧的存儲空間獲取棧的容量，maxStack設(shè)棧頂top=062.入棧運算是指在棧頂位置插入一個新元素基本操作：棧頂top（指針）加1新元素插入到棧頂指針指向的位置異常操作：棧滿溢出73.出棧，棧頂數(shù)據(jù)的彈出讀出棧頂元素值，將其賦給一個指定的變量。棧頂指針top減1異常：?？?top<0)8四、隊列隊列(equeue)也是一種特殊的線性表，它允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除。隊列中允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。在隊列中，最先插入的元素將最先被刪除，最后插入的元素最后才能被刪除。因此隊列又稱為“先進(jìn)先出”(FIFO:firstinfirstout)或“后進(jìn)后出”(LILO:lastinlastout)FEDCBA出隊入隊frontrear9隊列運算入隊列出隊列，讀出隊列數(shù)據(jù)FEDCBA出隊入隊frontrearrearAEDCB出隊入隊frontrearAfront10順序存儲1.建立隊列2.入隊列在隊尾加入一個新元素隊尾指針rear加1異常：隊列滿，溢出113.出隊列讀出隊頭元素值，將其賦給一個指定的變量。隊頭指針front加1異常：隊空(front==rear)12136.2動態(tài)內(nèi)存分配與鏈表一、動態(tài)內(nèi)存分配動態(tài)數(shù)據(jù)結(jié)構(gòu)可以在運行時靈活地添加、刪除或重排數(shù)據(jù)項。動態(tài)內(nèi)存管理則允許在運行時分配更多的內(nèi)存空間或釋放掉不再需要的空間，因而可以優(yōu)化存儲空間的使用。在運行時分配內(nèi)存空間的過程就稱為動態(tài)內(nèi)存分配。

程序內(nèi)存空間

代碼區(qū)(codearea)全局?jǐn)?shù)據(jù)區(qū)(dataarea)堆區(qū)(heaparea)棧區(qū)(stackarea)存放程序的代碼全局?jǐn)?shù)據(jù)和靜態(tài)數(shù)據(jù)程序的動態(tài)數(shù)據(jù)程序的局部數(shù)據(jù)14C語言提供了4個“內(nèi)存管理函數(shù)”，以用來在程序運行時分配和釋放內(nèi)存函數(shù)任務(wù)malloc分配所需的字節(jié)大小，并返回指向所分配空間的第一個字節(jié)的指針calloc為元素數(shù)組分配空間，并初始化為零，然后返回指向該內(nèi)存的指針free釋放前面已分配的空間realloc修改前面已分配空間的大小15用malloc函數(shù)分配一塊內(nèi)存malloc函數(shù)將保留指定大小的內(nèi)存塊，并返回void類型的指針。

ptr=(cast-type*)malloc(byte-size);ptr為cast-type類型的指針。malloc函數(shù)返回一個指向大小為byte-size的內(nèi)存區(qū)的指針（其類型為cast-type）。malloc函數(shù)分配的是連續(xù)的字節(jié)塊。如果堆的空間不能滿足要求，則分配失敗。如果失敗，將返回NULL。例如：x=(intx)malloc(100*sizeof(int));分配一個大小為100倍的int類型的內(nèi)存空間，該內(nèi)存的第一個字節(jié)的地址賦值給類型為int的指針xcptr=(char*)malloc(10);給char類型的指針分配10個字節(jié)的空間st_var=(structstudent*)malloc(sizeof(structsdudent));動態(tài)分配的存儲空間沒有名稱，因此只能通過指針來訪問其內(nèi)容。

16例6-1，請編寫一個程序，使用一個整數(shù)表，其大小在運行時交互地指定。17用calloc函數(shù)分配多個內(nèi)存塊分配多個存儲塊，每個塊大小相等，并把所有字節(jié)都初始化為零。ptr=(cast-type*)calloc(n，elem-size);18用free函數(shù)釋放已用的空間變量的編譯時存儲空間是由系統(tǒng)及其存儲類來分配和釋放的。對于運行時的內(nèi)存分配，當(dāng)不再需要時，由程序員來負(fù)責(zé)釋放。當(dāng)不再需要保存在內(nèi)存塊中的數(shù)據(jù)時，且不打算用它來存儲任何其他信息時，可用free函數(shù)來釋放掉內(nèi)存塊。free函數(shù)形式為：

free(ptr);釋放由ptr指向的內(nèi)存區(qū)，該內(nèi)存塊由malloc或calloc創(chuàng)建的，是最近一次調(diào)用的返回的值。在該函數(shù)調(diào)用中，使用非法的指針可能產(chǎn)生問題或引起系統(tǒng)崩潰。注意：所釋放的不是指針本身，而是它所指向的內(nèi)容。要釋放由calloc分配的內(nèi)存數(shù)組，只需要釋放該指針一次即可。19用realloc函數(shù)改變內(nèi)存塊的大小改變已分配內(nèi)存塊的大小的過程——內(nèi)存重分配(reallocation)。已分配內(nèi)存不夠；已分配內(nèi)存太大。realloc函數(shù)的形式ptr=realloc(ptr,newsize);該函數(shù)把大小為newsize的新內(nèi)存空間分配給指針變量ptr，并返回一個指向新內(nèi)存塊的第一個字節(jié)的指針。新內(nèi)存塊的開始位置可以與舊的相同，也可以不同。該函數(shù)保證九數(shù)據(jù)的完整性。即：舊內(nèi)存塊中的內(nèi)容將移到新塊中。如果函數(shù)沒有成功分配更多的空間，將返回一個空指針，就塊被丟失。例6-2，請編寫一個程序，把一個字符串保存在由malloc創(chuàng)建的內(nèi)存塊中，然后修改它以存儲更大的字符串。2021二、鏈表的概念鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。其大小可以在程序運行時增大或縮小，可按需決定。它是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)。鏈表是用指針表示兩個元素之間的先后順序關(guān)系，在邏輯上不要求兩個鏈表元素在物理上一定相鄰，且鏈表元素可根據(jù)需要開辟內(nèi)存單元。鏈表中的每一個元素稱為“結(jié)點”，每個結(jié)點都應(yīng)包含兩部分：用戶需要用的實際數(shù)據(jù)指向下一個結(jié)點的指針nodeitemnext22鏈表的一般形式例如：structlink_list{floatdata;

structlink_list*next;}；structlist_linknode1,node2;node1.next=&node2;node1.data=35.6;node2.data=45.5;node2.next=0;node1node1.datanode1.nextnode2node2.datanode2.nextXXXX35.645.5023鏈表是由指向下一個結(jié)點的指針(next)鏈接而成的。next指針具有與結(jié)點相同的類型。該指針由一個特殊的標(biāo)志(head)開始，由另一個特殊的標(biāo)志(NULL)結(jié)束。學(xué)生結(jié)點的定義&stu295.5Zhang10010&stu388.5Wang10011NULL88.5Wang10020&stu1head24鏈表提供的靈活性允許高效地重排數(shù)據(jù)項。通過重排鏈接，就可以很容易地插入或刪除數(shù)據(jù)項。item1

item2

item3

x

要插入的項item1

item2

item3

要刪除的項25鏈表的種類線性鏈表環(huán)形鏈表雙向鏈表雙向環(huán)形鏈表

item1

item20item3

item1

item2

item3

item10

item2

0item3

item1

item2

item3

26三、創(chuàng)建鏈表把鏈表看作是一種抽象數(shù)據(jù)類型，并可以執(zhí)行以下基本操作：創(chuàng)建鏈表遍歷鏈表計算鏈表中的數(shù)據(jù)項數(shù)目顯示鏈表查找某數(shù)據(jù)項，用于編輯或顯示插入一個數(shù)據(jù)項刪除一個數(shù)據(jù)項連接兩個鏈表27鏈表的建立（初始化）鏈表的建立就是要建立結(jié)點間的鏈接關(guān)系方法就是將每一結(jié)點中的next指針分別賦以它要指向（鏈接）的結(jié)點的地址28例6-3，建立一個由三個學(xué)生數(shù)據(jù)結(jié)點組成的簡單鏈表，并輸出各結(jié)點數(shù)據(jù)29例6-4，建立一個單向動態(tài)鏈表3031鏈表的結(jié)點的插入、刪除操作插入結(jié)點原來鏈表為空表原來鏈表不為空在頭結(jié)點前插入在當(dāng)前結(jié)點后插入在鏈表尾插入3233刪除結(jié)點要刪的是第一個結(jié)點要刪的結(jié)點不存在要刪的結(jié)點存在，且不是頭結(jié)點346.3二叉樹二叉樹的基本概念是一種非線性的結(jié)構(gòu)樹結(jié)構(gòu)中最簡單的一種外形像一棵倒立的樹；最上層有一個“根結(jié)點”；每個結(jié)點都是一個結(jié)構(gòu)，一個成員存放元素的值，另兩個成員是指針，分為左指針L和右指針R；根結(jié)點的左指針指向左子樹，右指針指向右子樹；左子樹或右子樹本身又是一棵二叉樹，又有它們自己的左子樹和右子樹……二叉樹是遞歸定義的，處理時常用遞歸算法356LR4LR8LR3LR5LR7LR9LRrootcode1code2code3code4code5code6code736二叉樹的建立樹中的每個結(jié)點有一個整數(shù)，數(shù)據(jù)名為data；有兩個指針（左指針Left，右指針Right），分別指向這個結(jié)點的左子樹和右子樹。structTreeNode{ intdata; structTreeNode*Left,*Right;};二叉樹的建立規(guī)則：第一個數(shù)據(jù)是這棵樹的根數(shù)據(jù)；之后再輸入的數(shù)據(jù)，每一個都要與根中的數(shù)據(jù)比較，以便確定其插入的位置；假定，待插入的數(shù)據(jù)如果比根結(jié)點小，則將其插至左子樹，否則插入右子樹。3784122720

insertTree(pRoot,temp)

根結(jié)點為空root==NULL新結(jié)點作為根結(jié)點