數據結構這東西,理解起來不算難,但是實現難度就不小了,雖然思路很清晰,但不知道從何下手還有語言的細節問題一直是阻礙初學者的主要障礙(比如我)。今天用了一下午時間終於獨立完成了鏈表操作。
找網上的代碼,大多用了結構體,還有些並不適合剛學C++或者數據結構的人看,於是我是用類寫的,代碼比較符合學生的習慣和水平。
先看類定義
class node
{
public:
int data;
node *next;
};
class linklist
{
node *h;
……//一些函數
}
兩個類,node用來表示結點,node *next,表示next是指向node型的指針(一些同學看不懂這句,會和構造函數弄混),linklist類是存放頭指針和定義操作函數用的。
一、整表的創建
整表創建有兩種方法,頭插(倒敘)和尾插(順序),這裡只說頭插。
void head(linklist &l,int n)
{
node *p;
p=new node;
l.h=p;//定義頭結點和投指針
p->data=n;//頭指針的數據域是結點個數
p->next=NULL;//最末結點的後繼必須為空
for(int i=0;i<n;i++)//創建n個新結點
{
node *q=new node;
cin>>q->data;
q->next=p->next;
p->next=q;//每個新結點都放在頭結點後面
}
}
二、單結點插入
void insert(linklist &l,int n,int num)
{
node *p=l.h;
for(int i=0;i<n;i++)
{
p=p->next;
}//找到插入的位置
node *q=new node;
q->next=p->next;
p->next=q;
q->data=num;
}
三、單結點刪除
void del(linklist &l,int n)
{
node *p=l.h;
for(int i=0;i<n-1;i++)
{
p=p->next;
}//找到刪除的位置
node *q=p;
q=q->next;
p->next=q->next;
delete q;//釋放空間
}
四、查找結點
void search(linklist &l,int n)
{
node *p=l.h;
for(int i=0;i<n;i++)
{
p=p->next;
}
cout<<p->data<<endl;
}
五、倒置
由於頭插是倒敘輸出,就想倒置,網上好多代碼都是新建一個鏈表,或者用到尾指針雙向鏈表之類,我覺得不會這麼麻煩於是就想了這麼個算法
void reverse(linklist l)
{
node *p=l.h;
node *q;
p=p->next;
while(p->next)
{
q=p->next;
p->next=q->next;
// q->next=p; //如果把下面兩句換成這句,就會悲劇。
q->next=l.h->next;
l.h->next=q;
}
}
一下午時間主要就耽誤在這裡了,我一開始寫的就是注釋那句話,後來總是輸出頭結點的數據,仔細觀察發現原來是頭指針跟著頭結點換到了最後面,然後這個問題通過下面兩句解決,保證頭指針永遠在表頭。
六、結語
寫到這裡,終於明白為什麼網上包括書上很多代碼都是看懂容易寫起來難,因為書或者博客作者就不會把他犯過的錯誤貼出來,一些簡單的代碼也沒有很多注釋,自己寫的時候也理解他們了,想詳細寫出每一步的理由還是太難了,無法表達的東西太多,所以想掌握一個東西還是親手實踐,多犯錯誤才能進步,因為書上或網上很難找到細節之處易犯的錯誤,以為自己會了的時候就用紙寫出來,到頭來會發現還是不會……循環幾次,就差不多了。