有一個線性表，采用帶頭結點的單連結清單L來存儲，設計一個算法将其逆置，且不能建立新節點，隻能通過表中已有的節點的重新組合來完成。

分析:線性表中關于逆序的問題,就是用建立連結清單的頭插法.而本題要求不能建立新結點,也就不能把元素重新弄到一個表中.可以将L中的元素作為逆轉後的L的元素來源,将L->next設定為空.然後将頭結點後的一串結點用頭插法逐個插入L中.

僞代碼:

void reversel(LNode *L)
{
    LNode *p=L->next, *q;
    L->next=NULL;            //置為空
    while(p!=NULL)
    {
        q=p->next;           //q記錄p的直接後繼結點的位置
        p->next=L->next;
        L->next=p;
        p=q;
    }
}
           

cue:

1.

LNode *p, *q;

并不是建立新結點,它們隻是存儲位址的變量.(我第一次遇到這個問題時沒弄懂,以為這兩是定義了新的結點.其實不是.)

2

LNode *A=(LNode*)malloc(sizeof(LNode));

才是使用者配置設定了一片LNode型空間,也就是構造了一個LNode型結點.這時候定義了名為A的指針來指向這個結點,同時我們也把A也當做這個結點的名字.這裡A命名了兩個東西,一個是結點,一個是指向這個結點的指針.

指針變量自身的存儲空間是系統配置設定的,不需要使用者調用函數free()釋放,隻有使用者配置設定的存儲空間才需要使用者自己來釋放.