C++链表实现

list和vector都是Sequence类型，不同的是vector的每个元素在内存中的地址位置是挨个连续的，list则不必需要连续的空间。它之所以是sequence是通过串联一个个结点实现的，每个结点包含用户存储进的元素与指向下一个元素的指针。如果是双向链表，还包括指向前一个结点的指针。本节实现的是单向list，具体实现是两个结构体和维护这两个结
构体的函数。

serverExe : try_List_main.o try_List.o g++ -o Exe try_List_main.o
try_List.o main.o : try_List_main.cpp try_List.h g++ -g -c
try_List_main.cpp solution.o : try_List.h try_List.cpp g++ -g -c
ry_List.cpp clean : rm try_List_main.o try_Vector.o Exe

#include 
#include 
using namespace std;

class try_List
{
public:
    try_List();
    ~try_List();
    //增加
    void insert(int pos, int value);
    //尾插
    void push_back(int value);
    //删最后一个
    void pop();
    //指定位置删除
    void delete_by_pos(int pos);
    //指定值删除 TODO:暂未实现
    // void delete_by_value(int value);
    //指定位置查找
    int find_by_pos(int pos);
    //指定值查找
    int find_by_value(int value);
    //返回链表的长度
    int size();
    //打印链表中各值
    int print_list();


typedef struct Node
{
    struct Node* next_ptr;
    int value;
}NODE;

typedef struct Data
{
    NODE* head;
    int size;
}DATA;
DATA* data; //head节点
};

#include "try_List.h"

try_List::try_List()
{
    //为结构体分配区间
    this->data = (DATA *)malloc(sizeof(DATA));
    this->data->size = 0;
    //初始化head节点 head节点不保存数据
    this->data->head = (NODE *)malloc(sizeof(NODE));
    this->data->head->next_ptr = NULL;
    this->data->head->value = 0;
}

try_List::~try_List()
{
}

//增加
void try_List::insert(int pos, int value)
{

    NODE *for_ptr = NULL;
    for_ptr = this->data->head;
    for (int i = 0; i < pos; i++) //遍历到要插入位置的前一个节点
    {
        for_ptr = for_ptr->next_ptr;
    }
    //分配一个空间节点,用于存储插入的value值
    NODE *temp_ptr = (NODE *)malloc(sizeof(NODE));
    temp_ptr->value = value;
    temp_ptr->next_ptr = NULL;

    //保存原pos位置上的节点
    NODE *pos_ptr = (NODE *)malloc(sizeof(NODE));
    pos_ptr = for_ptr->next_ptr;
    //将新节点挂在pos前的一个节点上
    for_ptr->next_ptr = temp_ptr;
    //将原pos位置的值挂在pos节点上
    temp_ptr->next_ptr = pos_ptr;
    this->data->size++;
}

//尾插
void try_List::push_back(int value)
{

    //找到最后一个节点
    NODE *for_ptr = NULL;
    for_ptr = this->data->head; //从头结点开始遍历
    while (true)
    {
        if (for_ptr->next_ptr == NULL)
        {
            break;
        }
        for_ptr = for_ptr->next_ptr;
    }

    //分配一个NODE空间,插在尾部
    NODE *temp_ptr = (NODE *)malloc(sizeof(NODE));
    temp_ptr->value = value;
    temp_ptr->next_ptr = NULL;

    for_ptr->next_ptr = temp_ptr;
    this->data->size++;
}

//删最后一个
void try_List::pop()
{
    if (this->data->size == 0)
    {
        cout << "@@@没有元素@@@" << endl;
        return;
    }
    NODE *for_ptr = NULL;
    for_ptr = this->data->head; //将0节点赋值过去
    for (int i = -1; i < data->size; i++)
    {
        if (for_ptr->next_ptr->next_ptr == NULL) //检验i节点是否是倒数第二个节点
        {
            break;
        }
        for_ptr = for_ptr->next_ptr;
    }
    for_ptr->next_ptr = NULL; //将最后一个元素舍弃
    this->data->size--;
}
//指定位置删除
void try_List::delete_by_pos(int pos)
{
    if (this->data->size == 0)
    {
        cout << "@@@没有元素@@@" << endl;
        return;
    }
    if(this->data->size < pos + 1)
    {
        cout << "@@@删除超界@@@" << endl;
    }
    NODE *for_ptr = NULL;
    for_ptr = this->data->head; //将0节点赋值过去
    for (int i = -1; i < pos; i++) //找到pos的前一个节点
    {
        for_ptr = for_ptr->next_ptr;
    }
    if(this->data->size == pos + 1)
    {
        for_ptr->next_ptr = NULL;
    }
    else
    {
        for_ptr->next_ptr = for_ptr->next_ptr->next_ptr;
    }
    
    this->data->size--;
}

//指定位置查找
int try_List::find_by_pos(int pos)
{
    if (this->data->size == 0)
    {
        cout << "@@@没有元素@@@" << endl;
        return false;
    }
    NODE *for_ptr = NULL;
    for_ptr = this->data->head; //将0节点赋值过去
    for (int i = -1; i < pos; i++)
    {
        for_ptr = for_ptr->next_ptr;
    }
    return for_ptr->value;
}

//指定值查找
int try_List::find_by_value(int value)
{
    if (this->data->size == 0)
    {
        cout << "@@@没有元素@@@" << endl;
        return false;
    }
    NODE *for_ptr = NULL;
    for_ptr = this->data->head; //将0节点赋值过去
    for (int i = -1; i < this->data->size; i++)
    {
        for_ptr = for_ptr->next_ptr;
        if (for_ptr->value == value)
        {
            return i + 1;
        }
    }
    cout << "@@@没有此值@@@" << endl;
    return false;
}
//返回链表的长度
int try_List::size()
{
    return this->data->size;
}


//打印链表中各值
int try_List::print_list()
{
    if (this->data->size == 0)
    {
        cout << "@@@没有元素@@@" << endl;
        return false;
    }
    NODE* for_ptr = NULL;
    for_ptr = this->data->head->next_ptr; //将0节点赋值过去
    for (int i = 0; i < this->data->size; i++)
    {
        cout << i  << " : " << for_ptr->value << endl; //从0节点开始打印
        for_ptr = for_ptr->next_ptr;
    }
}

#include "try_List.h"
#include 
#include 
using namespace std;

int main(void)
{
    try_List try_list;
    try_list.push_back(0);
    try_list.push_back(1);
    try_list.push_back(2);
    try_list.insert(3, 3);
    try_list.push_back(4);
    try_list.push_back(5);
    try_list.insert(6, 6);
    cout << "size : " << try_list.size() << endl;
    // try_list.pop();
    // try_list.delete_by_pos(6);
    // cout << "find_by_pos_6 : " << try_list.find_by_pos(6) << endl;
    // cout << "find_by_value_6 : " << try_list.find_by_value(6) << endl;
    cout << "capacity : " << try_list.capacity() << endl;

    cout << "size : " << try_list.size() << endl;
    try_list.print_list();
    return 0;
}