資料結構之單向連結清單的實作【C++】

大學沒有學習過資料結構，之前也隻是泛泛的看看連結清單的原理，并沒有實際編寫，昨天就系統的将連結清單的各項功能給實作了下，其中包括：移除，插入，更改，清空，列印，連結清單反轉等功能；其中，連結清單的反轉這在《劍指offer》以及其他面試中經常會被問到的問題；同時，對連結清單的熟悉可以為後期的隊列以及棧等的編寫提供基礎，是以還是很有必要從頭将連結清單進行弄明白。

1. 首先建立List.h檔案，為了和STL中的list進行區分，是以才用大寫表示：

#ifndef _LIST_H_
#define _LIST_H_

#include<iostream>
#include<string>

using namespace std;

struct Info
{
    string name;
    int id;
};

struct Node
{
    Info val;
    Node * next;
    Node(Info x):val(x),next(NULL){};
};

class List
{
public:
    List();
    ~List();

    void ListHead(Info val); //插傳入連結表頭

    void Insert(Info val,int pos); //在pos位置插入資訊val
    void Insert(Info val);//預設在連結清單的最後添加資料
    int Find(Info val);//查找val,并傳回val前一個節點的指針

    void Remove(Info val);//移除val

    void Update(Info val,Info val1);//更新val的值為val1

    void Print();//列印連結清單

    void erase();//清空連結清單

    void Reverse();//連結清單反轉


private:
    Node * head;//一個連結清單的頭指針
    int length;//連結清單的長度
};
#endif
           

2、然後建立List.cpp檔案

#include"List.h"

List::List()
{
    head = NULL;
    length = ;
}

List::~List()
{
    Node * temp = head;
    for(int i = ;i < length;i++)
    {
        delete temp;
        temp = temp->next;
    }
}
//建立一個連結清單頭

void List::ListHead(Info val)
{
    Insert(val,);
}

//在連結清單中pos的位置插入資料
void List::Insert(Info val,int pos)
{
    if(pos < )
        cout<<"Error:pos must be integer!";
    Node *temp = head;
    Node *node = new Node(val);

    int index = ;

    if(pos == )
    {
        node->next = temp;
        head = node;
        length++;
        return;
    }
    while(temp!=NULL && index < pos)
    {
        temp = temp->next;
        index++;
    }
    if(temp == NULL)
    {
        cout<<"Error:Insert failed!"<<endl;
        return;
    }
    node->next = temp->next;
    temp->next = node;
    length++;
}

//預設在連結清單的末尾添加資料

void List::Insert(Info val) 
{
    Node *temp = head;
    Node *p;
    Node* node = new Node(val);

    while(temp->next!=NULL)
    {
        temp = temp->next;
    }
    node->next = temp->next;
    temp->next = node;
    length++;
}
//在連結清單中查找val
int List::Find(Info val)
{
    Node* temp = head;
    int index = ;
    for(;temp;temp = temp->next)
    {
        if(temp->val.id == val.id && temp->val.name == val.name)
            return index;
        index++;
    }
    return -;
}
//删除val值
void List::Remove(Info val)
{
    int pos = Find(val);
    if(pos == -)
        cout<<"Error:Remove failed!"<<endl;
    if(pos == )
    {
        head = head->next;
        length--;
        return;
    }

    int index = ;
    Node* temp = head;
    while(index<pos)
    {
        temp = temp->next;
        index++;
    }
    temp->next = temp->next->next;
    length--;
}
//列印連結清單
void List::Print()
{
    Node* temp = head;
    if(temp == NULL)
    {
        cout<<"Error:print failed!"<<endl;
        return;
    }
    while(temp!=NULL)
    {
        cout<<temp->val.name<<"<***>"<<temp->val.id<<endl;
        temp = temp->next;
    }
}

//連結清單反轉
void List::Reverse()
{
    if(head==NULL)
        return;
    Node *curNode=head,*nextNode=head->next,*temp;
    while(nextNode!=NULL)
    {
        temp=nextNode->next;
        nextNode->next=curNode;
        curNode=nextNode;
        nextNode=temp;
    }
    head->next=NULL;
    head=curNode;
}
//清空連結清單

void List::erase()
{
    Node* temp = head;

    while(temp)
    {
        Node* p = temp->next;
        //temp = temp->next;
        delete temp;
        temp = p;
        head = temp;
        length--;
    }
}
           

3、最後就是進行test.cpp檔案的編寫進行測試程式！

#include"List.h"

int main(int argc,char** argv)
{
    system("color 3F");
    List temp;

    Info val1,val2,val3,val4,val5,val6;
    val1.id = ;val1.name = "Wang";val2.id = 2;val2.name = "Chao";val3.id = 3;val3.name = "long";
    val4.id = ;val4.name = "Kong";val5.id = 5;val5.name = "zhi";val6.id = 6;val6.name = "shi";
    cout<<"Listhead test"<<endl;
    temp.ListHead(val1);
    temp.Print();
    temp.Insert(val2,);
    temp.Print();
    temp.Insert(val2,);
    temp.Print();
    temp.Insert(val3,);
    temp.Print();
    cout<<"Remove test!"<<endl;
    temp.Remove(val2);
    temp.Print();

    cout<<"<**************************>"<<endl;
    temp.ListHead(val2);
    temp.Print();

    cout<<"*************************Last******************"<<endl;
    temp.Insert(val4);
    //temp.Print();
    temp.Insert(val5);
    temp.Insert(val6);
    temp.Print();
    cout<<"*************************Remove**********************"<<endl;
    temp.Remove(val5);
    temp.Print();
    cout<<"<************************Reverse*********************>"<<endl;
    temp.Reverse();
    temp.Print();

    cout<<"***********************erase******************"<<endl;
    temp.erase();
    temp.Print();
    system("pause");
    return ;
}
           

4、總結

之前都是覺得資料結構特别的難，這次為了提升自己的算法能力以及代碼的Coding能力，決定再花點時間将《資料結構和算法分析》好好學習一下，平時都是直接調用STL标準庫中現成的API函數，沒什麼感覺，通過對資料結構的學習，可以讓我們從底層的原理實作進行更深層次的了解！