数据结构之单向链表的实现【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函数，没什么感觉，通过对数据结构的学习，可以让我们从底层的原理实现进行更深层次的了解！