第二次作業(yè)簡(jiǎn)報(bào)

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

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

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