用C++類實(shí)現(xiàn)單向鏈表的增刪查和反轉(zhuǎn)操作方法

數(shù)據(jù)結(jié)構(gòu)這東西，理解起來不算難，但是實(shí)現(xiàn)難度就不小了，雖然思路很清晰，但不知道從何下手還有語言的細(xì)節(jié)問題一直是阻礙初學(xué)者的主要障礙（比如我）。今天用了一下午時(shí)間終于獨(dú)立完成了鏈表操作。

找網(wǎng)上的代碼，大多用了結(jié)構(gòu)體，還有些并不適合剛學(xué)c++或者數(shù)據(jù)結(jié)構(gòu)的人看，于是我是用類寫的，代碼比較符合學(xué)生的習(xí)慣和水平。

先看類定義

class node
{
public:
  int data;
  node *next;
};
class linklist
{
  node *h;
  ……//一些函數(shù)
}

兩個(gè)類，node用來表示結(jié)點(diǎn)，node *next，表示next是指向node型的指針（一些同學(xué)看不懂這句，會(huì)和構(gòu)造函數(shù)弄混），linklist類是存放頭指針和定義操作函數(shù)用的。

一、整表的創(chuàng)建

整表創(chuàng)建有兩種方法，頭插（倒敘）和尾插（順序），這里只說頭插。

void head(linklist &l,int n)
  {
    node *p;
    p=new node;
    l.h=p;//定義頭結(jié)點(diǎn)和投指針
    p->data=n;//頭指針的數(shù)據(jù)域是結(jié)點(diǎn)個(gè)數(shù)
    p->next=NULL;//最末結(jié)點(diǎn)的后繼必須為空
    for(int i=0;i<n;i++)//創(chuàng)建n個(gè)新結(jié)點(diǎn)
    {
      node *q=new node;
      cin>>q->data;
      q->next=p->next;
      p->next=q;//每個(gè)新結(jié)點(diǎn)都放在頭結(jié)點(diǎn)后面
    }
  }

二、單結(jié)點(diǎn)插入

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;
  }

三、單結(jié)點(diǎn)刪除

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;//釋放空間
  }

四、查找結(jié)點(diǎn)

void search(linklist &l,int n)
  {
    node *p=l.h;
    for(int i=0;i<n;i++)
    {
      p=p->next;
    }
    cout<<p->data<<endl;
  }

五、倒置

由于頭插是倒敘輸出，就想倒置，網(wǎng)上好多代碼都是新建一個(gè)鏈表，或者用到尾指針雙向鏈表之類，我覺得不會(huì)這么麻煩于是就想了這么個(gè)算法

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;  //如果把下面兩句換成這句，就會(huì)悲劇。
     q->next=l.h->next;
     l.h->next=q;
    }
  }

一下午時(shí)間主要就耽誤在這里了，我一開始寫的就是注釋那句話，后來總是輸出頭結(jié)點(diǎn)的數(shù)據(jù)，仔細(xì)觀察發(fā)現(xiàn)原來是頭指針跟著頭結(jié)點(diǎn)換到了最后面，然后這個(gè)問題通過下面兩句解決,保證頭指針永遠(yuǎn)在表頭。

六、結(jié)語

寫到這里，終于明白為什么網(wǎng)上包括書上很多代碼都是看懂容易寫起來難，因?yàn)闀蛘卟┛妥髡呔筒粫?huì)把他犯過的錯(cuò)誤貼出來，一些簡單的代碼也沒有很多注釋，自己寫的時(shí)候也理解他們了，想詳細(xì)寫出每一步的理由還是太難了，無法表達(dá)的東西太多，所以想掌握一個(gè)東西還是親手實(shí)踐，多犯錯(cuò)誤才能進(jìn)步，因?yàn)闀匣蚓W(wǎng)上很難找到細(xì)節(jié)之處易犯的錯(cuò)誤，以為自己會(huì)了的時(shí)候就用紙寫出來，到頭來會(huì)發(fā)現(xiàn)還是不會(huì)……循環(huán)幾次，就差不多了。

以上這篇用C++類實(shí)現(xiàn)單向鏈表的增刪查和反轉(zhuǎn)操作方法就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持億速云。