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