計(jì)算機(jī)等級考試二級C語言入門教程：堆和鏈表

　　2.鏈數(shù)據(jù)的插入和刪除

　　對于一個已排序好的鏈表(假設(shè)是生序)，現(xiàn)在想插入一個數(shù)據(jù)進(jìn)去，可能有三種情況：

　　(1).比首項(xiàng)數(shù)據(jù)還小，即插入的數(shù)據(jù)作為首項(xiàng)出現(xiàn)：

　　這種情況我們的處理方法是：把該數(shù)據(jù)作為第一項(xiàng)，指針指向原先的首項(xiàng)即可。設(shè)原先首項(xiàng)為top，待插入的數(shù)據(jù)為in，則：

　　in->next=top;

　　即可讓該數(shù)據(jù)作為鏈表的頭。

　　(2).比最后一項(xiàng)大，即插入的數(shù)據(jù)作為最后一項(xiàng)出現(xiàn)：

　　這也很好辦，設(shè)原先最后一項(xiàng)為old，則：

　　old->next=in;

　　in->next=NULL;

　　(3).作為中間某一項(xiàng)出現(xiàn)：前面是old,后面是top,則：

　　old->next=in;

　　in->next=top;

　　如果想刪除一個數(shù)據(jù)，也可能是出現(xiàn)在開頭，中間和結(jié)尾。

　　例如想刪除in這個數(shù)據(jù)，它原先的前面是old,后面是top,即原先的鏈表是這樣：

　　old->next=in;

　　in->next=top;

　　現(xiàn)在刪除in，只需把old指向top即可:

　　old->next=top->next;

　　/*刪除節(jié)點(diǎn)函數(shù)*/

　　void delete(struct address *info,struct address *old)

　　{

　　if(info)

　　{

　　if(info==start) start=info->next; /*刪除的是第一個節(jié)點(diǎn)*/

　　else

　　{

　　old->next=info->next; /*被刪除節(jié)點(diǎn)前的指針指向下一個節(jié)點(diǎn)*/

　　last=old; /*若節(jié)點(diǎn)是鏈表尾，則該節(jié)點(diǎn)前的節(jié)點(diǎn)指針指向NULL*/

　　}

　　free(info); /*釋放刪除節(jié)點(diǎn)占用空間*/

　　}

　　}

　　/*查找鏈表中是否有該數(shù)據(jù)*/

　　struct address *search(struct address *top,char *n)

　　{

　　while(top)

　　{

　　if(!strcmp(n,top->name)) return top; /*找到要刪除的節(jié)點(diǎn)指針*/

　　top=top->next; /*繼續(xù)找*/

　　}

　　return NULL; /*沒有找到*/

　　}

　　/*鏈表的輸出*/

　　void display(struct address *top)

　　{

　　while(top)

　　{

　　printf(top->name);

　　top=top->next;

　　}

　　}

　　鏈表問題比較復(fù)雜，但又是很重要的概念。上面說的輸入，查找，刪除，插入等功能一定要理解，可以參考別的一些資料看看。

　　上面說的單鏈表，但是單鏈表有一個缺點(diǎn)，就是無法反向操作，當(dāng)某一個鏈因破壞而斷裂，則整個鏈就被破壞而無法恢復(fù)。雙鏈表可以彌補(bǔ)這個缺點(diǎn)，所謂雙鏈表是指每個節(jié)點(diǎn)有兩個指針項(xiàng)，一個指針指向其前面的節(jié)點(diǎn)，而另一個指針指向后面的節(jié)點(diǎn)。關(guān)于雙鏈表的使用相對要復(fù)雜一些，這里就不介紹了，可以找其他一些資料看看。

　　　　　　　計(jì)算機(jī)等級考試二級C語言常見知識點(diǎn)總結(jié)

　　　　　　　計(jì)算機(jī)等考二級C50套上機(jī)程序填空題匯總

　　　　　　　計(jì)算機(jī)等級考試二級C語言三套全真預(yù)測試題