c++編程指針典型數(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)存分配鏈表二叉樹1第2-6講指針2——

典型數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介線性表16.1線性表簡(jiǎn)介一、線性表的基本概念線性表（linearlist）是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成一個(gè)n維向量英文字母表矩陣學(xué)生信息……26.1線性表簡(jiǎn)介一、線性表的基本概念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線性表是一種線性結(jié)構(gòu)，對(duì)于一個(gè)非空的線性表，有如下結(jié)構(gòu)特征：c++編程指針典型數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介課件c++編程指針典型數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介課件棧的基本運(yùn)算入棧出棧，讀棧頂元素1.建立一個(gè)棧的存儲(chǔ)空間獲取棧的容量，maxStack設(shè)棧頂top=06棧的基本運(yùn)算62.入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素基本操作：棧頂top（指針）加1新元素插入到棧頂指針指向的位置異常操作：棧滿溢出72.入棧運(yùn)算73.出棧，棧頂數(shù)據(jù)的彈出讀出棧頂元素值，將其賦給一個(gè)指定的變量。棧頂指針top減1異常：棧空(top<0)83.出棧，棧頂數(shù)據(jù)的彈出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ì)列FEDCBA出隊(duì)入隊(duì)frontrear9隊(duì)列運(yùn)算入隊(duì)列出隊(duì)列，讀出隊(duì)列數(shù)據(jù)FEDCBA出隊(duì)入隊(duì)frontrearrearAEDCB出隊(duì)入隊(duì)frontrearAfront10隊(duì)列運(yùn)算FEDCBA出隊(duì)入隊(duì)frontrearrearAED順序存儲(chǔ)1.建立隊(duì)列2.入隊(duì)列在隊(duì)尾加入一個(gè)新元素隊(duì)尾指針rear加1異常：隊(duì)列滿，溢出11順序存儲(chǔ)113.出隊(duì)列讀出隊(duì)頭元素值，將其賦給一個(gè)指定的變量。隊(duì)頭指針front加1異常：隊(duì)空(front==rear)123.出隊(duì)列1213136.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ù)146.2動(dòng)態(tài)內(nèi)存分配與鏈表一、動(dòng)態(tài)內(nèi)存分配C語言提供了4個(gè)“內(nèi)存管理函數(shù)”，以用來在程序運(yùn)行時(shí)分配和釋放內(nèi)存函數(shù)任務(wù)malloc分配所需的字節(jié)大小，并返回指向所分配空間的第一個(gè)字節(jié)的指針calloc為元素?cái)?shù)組分配空間，并初始化為零，然后返回指向該內(nèi)存的指針free釋放前面已分配的空間realloc修改前面已分配空間的大小15C語言提供了4個(gè)“內(nèi)存管理函數(shù)”，以用來在程序運(yùn)行時(shí)分配和釋用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用malloc函數(shù)分配一塊內(nèi)存16例6-1，請(qǐng)編寫一個(gè)程序，使用一個(gè)整數(shù)表，其大小在運(yùn)行時(shí)交互地指定。17例6-1，請(qǐng)編寫一個(gè)程序，使用一個(gè)整數(shù)表，其大小在運(yùn)行時(shí)交互用calloc函數(shù)分配多個(gè)內(nèi)存塊分配多個(gè)存儲(chǔ)塊，每個(gè)塊大小相等，并把所有字節(jié)都初始化為零。ptr=(cast-type*)calloc(n，elem-size);18用calloc函數(shù)分配多個(gè)內(nèi)存塊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用free函數(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ǔ)更大的字符串。20用realloc函數(shù)改變內(nèi)存塊的大小202121二、鏈表的概念鏈表是一種常見的重要的數(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二、鏈表的概念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鏈表的一般形式node1node1.datano鏈表是由指向下一個(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鏈表是由指向下一個(gè)結(jié)點(diǎn)的指針(next)鏈接而成的。nex鏈表提供的靈活性允許高效地重排數(shù)據(jù)項(xiàng)。通過重排鏈接，就可以很容易地插入或刪除數(shù)據(jù)項(xiàng)。item1item2item3x要插入的項(xiàng)item1item2item3要?jiǎng)h除的項(xiàng)25鏈表提供的靈活性允許高效地重排數(shù)據(jù)項(xiàng)。通過重排鏈接，就可以很鏈表的種類線性鏈表環(huán)形鏈表雙向鏈表雙向環(huán)形鏈表item1item20item3item1item2item3item10item20item3item1item2item326鏈表的種類item1item20item3item1三、創(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三、創(chuàng)建鏈表27鏈表的建立（初始化）鏈表的建立就是要建立結(jié)點(diǎn)間的鏈接關(guān)系方法就是將每一結(jié)點(diǎn)中的next指針分別賦以它要指向（鏈接）的結(jié)點(diǎn)的地址28鏈表的建立（初始化）28例6-3，建立一個(gè)由三個(gè)學(xué)生數(shù)據(jù)結(jié)點(diǎn)組成的簡(jiǎn)單鏈表，并輸出各結(jié)點(diǎn)數(shù)據(jù)29例6-3，建立一個(gè)由三個(gè)學(xué)生數(shù)據(jù)結(jié)點(diǎn)組成的簡(jiǎn)單鏈表，并輸出各例6-4，建立一個(gè)單向動(dòng)態(tài)鏈表30例6-4，建立一個(gè)單向動(dòng)態(tài)鏈表303131鏈表的結(jié)點(diǎn)的插入、刪除操作插入結(jié)點(diǎn)原來鏈表為空表原來鏈表不為空在頭結(jié)點(diǎn)前插入在當(dāng)前結(jié)點(diǎn)后插入在鏈表尾插入32鏈表的結(jié)點(diǎn)的插入、刪除操作323333刪除結(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)34刪除結(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í)常用遞歸算法356.3二叉樹二叉樹的基本概念356LR4LR8LR3LR5LR7LR9LRrootcode1code2code3code4code5code6code7366LR4LR8LR3LR5LR7LR9LRrootcode1二叉樹的建立樹中的每個(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)小，則將其插至左子樹，否則插入右子樹。37二叉樹的建立3784122720

insertTree(pRoot,temp)

根結(jié)點(diǎn)為空root==NULL新結(jié)點(diǎn)作為根結(jié)點(diǎn)，return(newNode);根結(jié)點(diǎn)不為空樹已存在