自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講筆記(編輯修改稿)
2025-07-20 06:12 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 or(‘不存在第i個(gè)結(jié)點(diǎn)’) } free是庫(kù)函數(shù)，結(jié)果是釋放q所指結(jié)點(diǎn)占用的內(nèi)存空間，同時(shí)q的值變成無(wú)定義。6 插入 Void insert_lklist( lklist head,datatyped x ,int i) { P=find_lklist (head, i1)。If ( p==NULL)Error (‘不存在第i個(gè)位置’) Else { s= malloc (size)。 sdata= x。 snext=pnext。 pnext =s。 } 其他鏈表 循環(huán)鏈表尾結(jié)點(diǎn)的鏈域值不是NULL,而是指向頭結(jié)點(diǎn)的指針。優(yōu)點(diǎn)是從任一結(jié)點(diǎn)出發(fā)都能通過(guò)后移操作而掃描整個(gè)循環(huán)鏈表。但為找到尾結(jié)點(diǎn)，必須從頭指針出發(fā)掃描表中所有結(jié)點(diǎn)。改進(jìn)的方法是不設(shè)頭指針而改設(shè)尾指針。這樣，頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的位置為：rearnextnext 和rear.雙鏈表：在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針域，所含指針指向前趨結(jié)點(diǎn)。 雙鏈表的摘除*P的操作：ppriornext=pnext。 pnextprior=pprior。 鏈入操作：P后面鏈入*q: qprior=p。 qnext=pnext。 pnextprior=q。 pnext =q。 空間性能的比較：存儲(chǔ)結(jié)點(diǎn)中數(shù)據(jù)域占用的存儲(chǔ)量與整個(gè)存儲(chǔ)結(jié)點(diǎn)占用存儲(chǔ)量之比稱為存儲(chǔ)密度。順序表=1，鏈表1，所有順序表空間利用率高。但順序表要事先估計(jì)容量，有時(shí)造成浪費(fèi)。 時(shí)間性能的比較： 一種實(shí)現(xiàn)的時(shí)間性能是指該實(shí)現(xiàn)中包含的算法的時(shí)間復(fù)雜性。定位： 順序表和鏈表都是O（n）讀表元：順序表O（1），鏈表O（n），故當(dāng)需要隨機(jī)存取時(shí)，不宜采用鏈表。摘除，鏈入：順序表O（n），鏈表O（1），經(jīng)常需要插入刪除時(shí)不宜采用順序表。 串是由零個(gè)或多個(gè)字符組成的又窮序列。含零個(gè)字符的串稱為空串。串中所含字符的個(gè)數(shù)稱為該串的長(zhǎng)度。 兩個(gè)串完全一樣時(shí)稱為相等的。 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子竄，該竄稱為主竄。 字符串常量按字符數(shù)組處理，它的值在執(zhí)行過(guò)程中不能改變。串變量與其他變量不一樣，不能由賦值語(yǔ)句賦值。 串的基本運(yùn)算：1． 賦值：ASSIGN(S,T):加工型運(yùn)算。將串變量或串常量的值傳給串變量。2． 判等：EQUAL(S,T)：引用型運(yùn)算，若相等返回1，否則返回0。3． 求長(zhǎng)：LENGTH(S)：引用型運(yùn)算4． 聯(lián)接：CONCAT(S,T)：引用型運(yùn)算。運(yùn)算結(jié)果是聯(lián)接在一起形成的新串。5． 求子串：SUBSTR(S,I,j)：引用型運(yùn)算：結(jié)果是串S中從第i個(gè)字符開(kāi)始，由連續(xù)j個(gè)字符組成的子串。當(dāng)I,j參數(shù)超過(guò)范圍時(shí)，運(yùn)算不能執(zhí)行，也沒(méi)有結(jié)果。6． 插入：INSERT(S1,I,S2)：加工型運(yùn)算。將串2整個(gè)插到S1的第i個(gè)字符之后從而產(chǎn)生一個(gè)新串。7． 刪除DELETE(S,I,J)加工型運(yùn)算。從串S中刪去第I個(gè)字符開(kāi)始的長(zhǎng)度為J的子串。8． 定位：INDEX(S,T)：引用型運(yùn)算。若串S中存在一個(gè)與T相等的子串。則結(jié)果為S中第一個(gè)這樣的子串的第一個(gè)字符在S中的位置，否則，結(jié)果為0。（要求T不是空串）9． 替換：REPLACE(S,T,R)加工型運(yùn)算。在S中處處同時(shí)以串R置換T的所有出現(xiàn)所得的新串。 串的存儲(chǔ)：1． 串的順序存儲(chǔ)：緊縮格式，非緊縮格式2． 串的鏈接存儲(chǔ)：將串中每個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)的字符個(gè)數(shù)稱為結(jié)點(diǎn)大小。結(jié)點(diǎn)為1時(shí)存儲(chǔ)密度低但操作方便，大于1時(shí)存儲(chǔ)密度高但操作不方便。第三章 棧，隊(duì)列和數(shù)組 棧 棧是一種特殊的線性表，棧上的插入刪除操作限定在表的某一端進(jìn)行，稱為棧頂。另一端稱為棧底。不含任何元素的棧稱為空棧。 棧又稱為先進(jìn)后出線性表。在棧頂進(jìn)行插入運(yùn)算，被稱為進(jìn)棧，刪除被稱為出棧。 棧的基本運(yùn)算：1． 初始化：InitStack(S):加工型運(yùn)算，設(shè)置一個(gè)空棧S.2． 進(jìn)棧：push（S,X）加工型運(yùn)算，將元素X插入S中，使X稱為棧頂元素。3． 退棧：pop（S）加工型運(yùn)算，當(dāng)棧不空時(shí)，從棧中刪除當(dāng)前棧頂。4． 讀棧頂：top（S）：引用型運(yùn)算，若S不空，由X返回棧頂元素，S為空時(shí)，結(jié)果為一特殊標(biāo)志。5． 判棧空empty（S）：引用型運(yùn)算，若S為空棧，結(jié)果為1，否則為0 棧的順序?qū)崿F(xiàn) 順序棧由一個(gè)一維數(shù)組和一個(gè)記錄棧頂位置的變量組成。 空棧中進(jìn)行出棧操作，發(fā)生下溢，滿棧中進(jìn)行入棧操作，發(fā)生上溢。 類C語(yǔ)言定義： define sqstack_maxsize 6 /*6是棧的容量*/Typedef struct sqstack { DataType dada[sqstack_maxsize]。 Int top。 }SqStackTP。 棧的基本運(yùn)算的實(shí)現(xiàn)：1． 初始化Int InitStack(InitStackTp *sq){sqtop=0。 Return(1)。 } 2. 進(jìn)棧 Int push(sqstackTp *sq, datatype x){ if (stop == sqstack_maxsize1) {error(“棧滿”)。return 0。}Else{sqtop++。 Sqdata[sqtop]=x。 Return(1)。 } 3 退棧Int pop(sqstackTp *sq,datatype *x) {if (sqtop==0) {error(“下溢”)。return(0)。}Else {*x=sqdata[sqtop]。Sqtop。Return(1)。 }4 判?？?Int emptystack(stackTp *sq){if sqtop==0} Return(1)。Else return(0)。 }5 取棧頂元素Int gettop( sqstackTp *sq, datatype *x){if(sqtop=0) return(0)。Else{*x =sqdata[sqtop]。Return(1)。 } 鏈棧由棧頂指針ls唯一確定。棧中其他結(jié)點(diǎn)通過(guò)他們的next域鏈接起來(lái)。棧底結(jié)點(diǎn)的next域?yàn)镹ULL。因?yàn)殒湕１旧頉](méi)有容量限制，所以不會(huì)出現(xiàn)棧滿情況。 3． 棧的簡(jiǎn)單應(yīng)用和遞歸棧與函數(shù)調(diào)用: 函數(shù)調(diào)用時(shí)，先保存的位置后返回，后保存的位置先返回。所以每遇到一個(gè)函數(shù)調(diào)用便立刻將相應(yīng)的返回位置進(jìn)棧，調(diào)用結(jié)束時(shí)，棧頂元素正好是此函數(shù)的返回位置。遞歸與棧： 滿足遞歸的條件：1． 被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。2． 被定義項(xiàng)在最小尺度上的定義不是遞歸的。 隊(duì)列 隊(duì)列也可以看成一種受限的線性表，插入限定在表的某一端進(jìn)行（隊(duì)尾），刪除限定在另一端進(jìn)行（隊(duì)頭） 隊(duì)列又稱先進(jìn)先出線性表。 隊(duì)列的基本運(yùn)算：1． 隊(duì)列初始化initQueue(Q) 加工型運(yùn)算，設(shè)置一個(gè)空隊(duì)列Q2． 入隊(duì)列enQueue(Q,X
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1