正文內容

自考02142數據結構導論串講筆記(編輯修改稿)

2026-07-20 06:12 本頁面

　

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

點擊復制文檔內容

環評公示相關推薦

自考02142數據結構導論串講筆記(編輯修改稿)

數據結構講義-資料下載頁

自考筆記管理學原理自考管理學原理筆記自考串講講義資料-資料下載頁

嚴蔚敏數據結構為主的筆記-吐血推薦-資料下載頁

數據結構實踐-資料下載頁

自考財務報表分析串講筆記-資料下載頁

數據結構(10800)-資料下載頁

數據結構(7128)-資料下載頁

自考企業管理咨詢筆記小抄串講-資料下載頁

數據結構(4772)-資料下載頁

全國自學考試數據結構導論試題及答案(4套)-資料下載頁

自考筆記自考小抄自考串講㊣01848公務員制度--考試必用-資料下載頁

[工學]2001年到2006年自考數據結構試題和答案-資料下載頁

10月--20071月自考2331數據結構歷試題和答案-資料下載頁

java基礎復習筆記09數據結構哈夫曼樹-資料下載頁

公文寫作與處理自考重點筆記串講內容-資料下載頁

自考02142數據結構導論串講筆記(更新版)

自考02142數據結構導論串講筆記(專業版)

自考02142數據結構導論串講筆記(留存版)

自考02142數據結構導論串講筆記-文庫吧