第二次作業(yè)簡報

1、第二次作業(yè)簡報駱雄武 2008.3.11題目要求o 寫出循環(huán)鏈表的ADT定義。鏈表元素定為整數(shù)類型。o 實現(xiàn)鏈表的創(chuàng)建，元素插入函數(shù)。o 創(chuàng)建兩個鏈表，然后分別在兩個鏈表中插入元素序列：12，5，-9，3，6，5 和7，45，0，5o 要求插入后的鏈表內(nèi)元素的值從頭到尾按升序排列。o 完成兩個鏈表的合并函數(shù)（不必寫在ADT內(nèi) ）o 合并后的內(nèi)容在第一個鏈表中，并且也要保持所有節(jié)點的值按升序排列。循環(huán)鏈表ADT具體實現(xiàn)兩個關(guān)鍵函數(shù)o 插入函數(shù)n create函數(shù)一開始只創(chuàng)建一個空的鏈表o 帶頭節(jié)點的鏈表（本示例采用的結(jié)構(gòu)）o 不帶頭結(jié)點的鏈表n 在后面添加元素時，是通過插入函數(shù)不斷添加進去的n

2、在插入時，同時結(jié)合插入排序方法，這樣在所有元素都插入后，鏈表已經(jīng)是排好序的了headhead30具體實現(xiàn)兩個關(guān)鍵函數(shù)o 合并函數(shù)n大家通常的做法是：遍歷第二個鏈表中的每個元素，每取一個元素，就調(diào)用上面的插入函數(shù)，插入到第一個鏈表中o 假設(shè)兩個鏈表元素個數(shù)分別為m和n，則最壞情況下時間復(fù)雜度O(mn)n更效率的一種算法是：對兩個鏈表同時遍歷，各用一個指針p1,p2o 若p2-value value,則將p2插到p1前，同時p2前進o 若p2-value p1-value,則p2不動，p1前進，直到滿足上面條件n這種算法時間復(fù)雜度O(m+n)具體實現(xiàn)- create函數(shù)具體實現(xiàn)- insert函數(shù)

3、（接上頁）具體實現(xiàn)- sUnion函數(shù)具體實現(xiàn)- sUnion函數(shù)（cont.）批改作業(yè)時發(fā)現(xiàn)的個別問題o 先對數(shù)組進行冒泡排序，然后將數(shù)組放到鏈表里面去 ；或者先合并，再進行冒泡排序n這個既麻煩，又效率低下n同時失去了使用鏈表的意義o 邊界問題：循環(huán)時沒有判斷好鏈表尾，結(jié)果指針越界 o 指針問題：n沒有對指針進行檢查是否為空，就引用指針指向的結(jié)構(gòu)n沒有對指針就行空間分配，就對指針指向的結(jié)構(gòu)進行賦值o “=”和”=”nif(P=NULL)和if(p=NULL)程序風(fēng)范問題o 注釋o 條理、結(jié)構(gòu)o 代碼書寫n ListNode* p = s1-head;s1-head = s2-head;free(p);return s1;n nListNode* p = s1-head;ns1-head =