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

第2-6講指針2——

典型數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介線性表?xiàng)ｊ?duì)列動(dòng)態(tài)內(nèi)存分配鏈表二叉樹16.1線性表簡(jiǎn)介一、線性表的基本概念線性表（linearlist）是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成一個(gè)n維向量英文字母表矩陣學(xué)生信息……2線性表是一種線性結(jié)構(gòu)，對(duì)于一個(gè)非空的線性表，有如下結(jié)構(gòu)特征：有且只有一個(gè)頭（根）結(jié)點(diǎn)，無前繼；有且只有一個(gè)尾（終端）結(jié)點(diǎn)，無后續(xù)；其它結(jié)點(diǎn)有且只有一個(gè)前繼，一個(gè)后續(xù)。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱為空表。線性表的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)（數(shù)組）表中所有元素所占的空間是連續(xù)的表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表，結(jié)點(diǎn)）每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致數(shù)據(jù)元素之間的邏輯關(guān)系由指針域來完成3二、線性表的基本運(yùn)算表的建立線性表的插入順序存儲(chǔ)下的操作注意表的溢出線性表的刪除刪除操作注意空線性表的查找查找操作注意未找到線性表的排序線性表的分解線性表的合并線性表的復(fù)制線性表的逆轉(zhuǎn)4三、棧棧（stack）是一種特殊的線性表，限定在一端進(jìn)行插入與刪除操作。在棧中允許插入、刪除的一端稱為棧頂(top)，不允許插入、刪除的一端稱為棧底(bottom)。棧是按照“先進(jìn)后出”(FILO:firstinlastout)或“后進(jìn)先出”(LIFO:lastinfirstout)原則組織數(shù)據(jù)的。a1a2┋an入棧出棧topbottom5棧的基本運(yùn)算入棧出棧，讀棧頂元素1.建立一個(gè)棧的存儲(chǔ)空間獲取棧的容量，maxStack設(shè)棧頂top=062.入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素基本操作：棧頂top（指針）加1新元素插入到棧頂指針指向的位置異常操作：棧滿溢出73.出棧，棧頂數(shù)據(jù)的彈出讀出棧頂元素值，將其賦給一個(gè)指定的變量。棧頂指針top減1異常：?？?top<0)8四、隊(duì)列隊(duì)列(equeue)也是一種特殊的線性表，它允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除。隊(duì)列中允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭(front)。在隊(duì)列中，最先插入的元素將最先被刪除，最后插入的元素最后才能被刪除。因此隊(duì)列又稱為“先進(jìn)先出”(FIFO:firstinfirstout)或“后進(jìn)后出”(LILO:lastinlastout)FEDCBA出隊(duì)入隊(duì)frontrear9隊(duì)列運(yùn)算入隊(duì)列出隊(duì)列，讀出隊(duì)列數(shù)據(jù)FEDCBA出隊(duì)入隊(duì)frontrearrearAEDCB出隊(duì)入隊(duì)frontrearAfront10順序存儲(chǔ)1.建立隊(duì)列2.入隊(duì)列在隊(duì)尾加入一個(gè)新元素隊(duì)尾指針rear加1異常：隊(duì)列滿，溢出113.出隊(duì)列讀出隊(duì)頭元素值，將其賦給一個(gè)指定的變量。隊(duì)頭指針front加1異常：隊(duì)空(front==rear)12136.2動(dòng)態(tài)內(nèi)存分配與鏈表一、動(dòng)態(tài)內(nèi)存分配動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)可以在運(yùn)行時(shí)靈活地添加、刪除或重排數(shù)據(jù)項(xiàng)。動(dòng)態(tài)內(nèi)存管理則允許在運(yùn)行時(shí)分配更多的內(nèi)存空間或釋放掉不再需要的空間，因而可以優(yōu)化存儲(chǔ)空間的使用。在運(yùn)行時(shí)分配內(nèi)存空間的過程就稱為動(dòng)態(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ù)程序的動(dòng)態(tài)數(shù)據(jù)程序的局部數(shù)據(jù)14C語言提供了4個(gè)“內(nèi)存管理函數(shù)”，以用來在程序運(yùn)行時(shí)分配和釋放內(nèi)存函數(shù)任務(wù)malloc分配所需的字節(jié)大小，并返回指向所分配空間的第一個(gè)字節(jié)的指針calloc為元素?cái)?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ù)返回一個(gè)指向大小為byte-size的內(nèi)存區(qū)的指針（其類型為cast-type）。malloc函數(shù)分配的是連續(xù)的字節(jié)塊。如果堆的空間不能滿足要求，則分配失敗。如果失敗，將返回NULL。例如：x=(intx)malloc(100*sizeof(int));分配一個(gè)大小為100倍的int類型的內(nèi)存空間，該內(nèi)存的第一個(gè)字節(jié)的地址賦值給類型為int的指針xcptr=(char*)malloc(10);給char類型的指針分配10個(gè)字節(jié)的空間st_var=(structstudent*)malloc(sizeof(structsdudent));動(dòng)態(tài)分配的存儲(chǔ)空間沒有名稱，因此只能通過指針來訪問其內(nèi)容。

16例6-1，請(qǐng)編寫一個(gè)程序，使用一個(gè)整數(shù)表，其大小在運(yùn)行時(shí)交互地指定。17用calloc函數(shù)分配多個(gè)內(nèi)存塊分配多個(gè)存儲(chǔ)塊，每個(gè)塊大小相等，并把所有字節(jié)都初始化為零。ptr=(cast-type*)calloc(n，elem-size);18用free函數(shù)釋放已用的空間變量的編譯時(shí)存儲(chǔ)空間是由系統(tǒng)及其存儲(chǔ)類來分配和釋放的。對(duì)于運(yùn)行時(shí)的內(nèi)存分配，當(dāng)不再需要時(shí)，由程序員來負(fù)責(zé)釋放。當(dāng)不再需要保存在內(nèi)存塊中的數(shù)據(jù)時(shí)，且不打算用它來存儲(chǔ)任何其他信息時(shí)，可用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，并返回一個(gè)指向新內(nèi)存塊的第一個(gè)字節(jié)的指針。新內(nèi)存塊的開始位置可以與舊的相同，也可以不同。該函數(shù)保證九數(shù)據(jù)的完整性。即：舊內(nèi)存塊中的內(nèi)容將移到新塊中。如果函數(shù)沒有成功分配更多的空間，將返回一個(gè)空指針，就塊被丟失。例6-2，請(qǐng)編寫一個(gè)程序，把一個(gè)字符串保存在由malloc創(chuàng)建的內(nèi)存塊中，然后修改它以存儲(chǔ)更大的字符串。2021二、鏈表的概念鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。其大小可以在程序運(yùn)行時(shí)增大或縮小，可按需決定。它是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。鏈表是用指針表示兩個(gè)元素之間的先后順序關(guān)系，在邏輯上不要求兩個(gè)鏈表元素在物理上一定相鄰，且鏈表元素可根據(jù)需要開辟內(nèi)存單元。鏈表中的每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包含兩部分：用戶需要用的實(shí)際數(shù)據(jù)指向下一個(gè)結(jié)點(diǎn)的指針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鏈表是由指向下一個(gè)結(jié)點(diǎn)的指針(next)鏈接而成的。next指針具有與結(jié)點(diǎn)相同的類型。該指針由一個(gè)特殊的標(biāo)志(head)開始，由另一個(gè)特殊的標(biāo)志(NULL)結(jié)束。學(xué)生結(jié)點(diǎn)的定義&stu295.5Zhang10010&stu388.5Wang10011NULL88.5Wang10020&stu1head24鏈表提供的靈活性允許高效地重排數(shù)據(jù)項(xiàng)。通過重排鏈接，就可以很容易地插入或刪除數(shù)據(jù)項(xiàng)。item1

item2

item3

x

要插入的項(xiàng)item1

item2

item3

要?jiǎng)h除的項(xiàng)25鏈表的種類線性鏈表環(huán)形鏈表雙向鏈表雙向環(huán)形鏈表

item1

item20item3

item1

item2

item3

item10

item2

0item3

item1

item2

item3

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

insertTree(pRoot,temp)

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