快捷導(dǎo)航

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

更新時間：2017年04月11日 10:19:57 投稿：jingxian

下面小編就為大家?guī)硪黄肅++類實現(xiàn)單向鏈表的增刪查和反轉(zhuǎn)操作方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

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

找網(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ù)
}

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

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

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

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

二、單結(jié)點

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é)點刪除

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é)點

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)上好多代碼都是新建一個鏈表，或者用到尾指針雙向鏈表之類，我覺得不會這么麻煩于是就想了這么個算法

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

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

六、結(jié)語

寫到這里，終于明白為什么網(wǎng)上包括書上很多代碼都是看懂容易寫起來難，因為書或者博客作者就不會把他犯過的錯誤貼出來，一些簡單的代碼也沒有很多注釋，自己寫的時候也理解他們了，想詳細寫出每一步的理由還是太難了，無法表達的東西太多，所以想掌握一個東西還是親手實踐，多犯錯誤才能進步，因為書上或網(wǎng)上很難找到細節(jié)之處易犯的錯誤，以為自己會了的時候就用紙寫出來，到頭來會發(fā)現(xiàn)還是不會……循環(huán)幾次，就差不多了。

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