c语言用两个栈构造队列伪码,数据结构习题线性表栈队列.doc
數據結構習題線性表棧隊列
線性表(58)
1. 在單鏈表、雙鏈表和單循環鏈表中,若僅知道指針p指向某結點,不知道頭指針,能否將結點*p從相應的鏈表中刪去?若可以,其時間復雜度各為多少?
2.設線性表的n個結點定義為(a0,a1,...an-1),重寫順序表上實現的插入和刪除算法:InsertList 和DeleteList。
3.試分別用順序表和單鏈表作為存儲結構,實現將線性表(a0,a1,...an-1)就地逆置的操作,所謂"就地"指輔助空間應為O(1)。
4.設順序表L是一個遞增有序表,試寫一算法,將x插入L中,并使L仍是一個有序表。
5.設順序表L是一個遞減有序表,試寫一算法,將x插入其后仍保持L的有序性。
解答:與上題相類似,只要從終端結點開始往前找到第一個比x大(或相等)的結點數據,在這個位置插入就可以了。(邊尋找,邊移動)
6.寫一算法在單鏈表上實現線性表的ListLength(L)運算。
7.已知L1和L2分別指向兩個單鏈表的頭結點,且已知其長度分別為m和n。試寫一算法將這兩個鏈表連接在一起。請分析你的算法的時間復雜度。
8.設 A和B是兩個單鏈表,其表中元素遞增有序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C,并要求輔助空間為O(1),請分析算法的時間復雜度。
9.已知單鏈表L是一個遞增有序表,試寫一高效算法,刪除表中值大于min 且小于max的結點(若表中有這樣的結點),同時釋放被刪結點的空間,這里min 和 max是兩個給定的參數。請分析你的算法的時間復雜度。
10.寫一算法將單鏈表中值重復的結點刪除,使所得的結果表中各結點值均不相同。
11.假設在長度大于1的單循環鏈表中,既無頭結點也無頭指針。s為指向鏈表中某個結點的指針,試編寫算法刪除結點*s的直接前趨結點。
12. 試編寫一個算法,在帶表頭結點的單鏈表中尋找第i個結點。若找到,則函數返回第i個結點的地址;若找不到,則函數返回0。
13. 設ha和hb分別是兩個帶表頭結點的非遞減有序單鏈表的表頭指針, 試設計一個算法, 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數據。
14. 設有一個表頭指針為h的單鏈表。試設計一個算法,通過遍歷一趟鏈表,將鏈表中所有結點的鏈接方向逆轉,如下圖所示。要求逆轉結果鏈表的表頭指針h指向原鏈表的最后一個結點。
15. 從左到右及從右到左遍歷一個單鏈表是可能的,其方法是在從左向右遍歷的過程中將連接方向逆轉,如右圖所示。在圖中的指針p指向當前正在訪問的結點,指針pr指向指針p所指結點的左側的結點。此時,指針p所指結點左側的所有結點的鏈接方向都已逆轉。
(1) 編寫一個算法,從任一給定的位置(pr, p)開始,將指針p右移k個結點。如果p移出鏈表,則將p置為0,并讓pr停留在鏈表最右邊的結點上。
(2) 編寫一個算法,從任一給定的位置(pr, p)開始,將指針p左移k個結點。如果p移出鏈表,則將p置為0,并讓pr停留在鏈表最左邊的結點上。
16. 試寫出用單鏈表表示的字符串類及字符串結點類的定義,并依次實現它的構造函數、以及計算串長度、串賦值、判斷兩串相等、求子串、兩串連接、求子串在串中位置等7個成員函數。要求每個字符串結點中只存放一個字符。。
17. 試設計一個實現下述要求的Locate運算的函數。設有一個帶表頭結點的雙向鏈表L,每個結點有4個數據成員:指向前驅結點的指針prior、指向后繼結點的指針next、存放數據的成員data和訪問頻度freq。所有結點的freq初始時都為0。每當在鏈表上進行一次Locate (L, x)操作時,令元素值為x的結點的訪問頻度freq加1,并將該結點前移,鏈接到與它的訪問頻度相等的結點后面,使得鏈表中所有結點保持按訪問頻度遞減的順序排列,以使頻繁訪問的結點總是靠近表頭。
18.不帶頭結點的單鏈表進行就地逆置的算法,該算法用 L 返回逆置后的鏈表的
頭指針,
19.對單鏈表中元素按插入方法排序,其中L為鏈表頭結點指針。請完成其功能。
20.下面是一個求兩個集合 A 和B之差 C=A-B的程序,即當且僅當 e是 A 的一個元素,但不是 B 中的一個元素時,e 才是 C 中的一個元素。集合用有序鏈表實現,初始時,A,B集合中的元素按遞增排列,C 為空;操作完成后 A,B 保持不變,C 中元素按遞增排列。下面的函數 append(last,e)是把值為 e 的新結點鏈接在由指針 last 指向的結點的后面,并返回新結點的地址;函數 difference(A,B)實現集合運算 A-B,并返回表示結果集合 C 的鏈表的首結點的地址。在執行 A-B 運算之前,用于表示結果集合的
總結
以上是生活随笔為你收集整理的c语言用两个栈构造队列伪码,数据结构习题线性表栈队列.doc的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: c语言编程用得上i7,为什么我的C应用程
- 下一篇: 学生兴趣爱好管理系统 c语言,《学生兴趣