简易有序链表

链表是一种在内存中非连续、非顺序的存储结构,链表的数据元素的逻辑顺序是通过链表中的指针链接次序实现的,就是说通过一个指针指向下一个元素,而下一个元素的指针再指向再下一个。链表是由一系列结点(链表中的每一个元素称为结点)组成的,结点可以在程序运行时动态生成,所以不用固定链表的长度,从而可以大大的节省内存空间。

我写的这个简易链表主要实现了“增删改查”的功能,其中每个结点包括三个部分:第一个是链表元素的索引值(可用于操作元素),第二个是用于存放内容的字符串空间,第三个就是存放指向下一个元素的指针。

详细实现的代码:

List.h 链表的头文件

class List{
public:
    List():head(nullptr){};
    ~List(){};

    struct Node;

    void Insert(int index, std::string values);
    void Show(int index = NULL);
    void Delete(int index);
    void Update(int index, std::string values);

private:
    Node *head;
};

List.cpp 链表的源文件

#include <iostream>
#include <string>
#include "List.h"

struct List::Node{
    int index;
    std::string values;
    Node *next;
};

void List::Insert(int index, std::string values){
    Node *node = new Node, *p = head;

    node->index = index;
    node->values = values;
    node->next = nullptr;

    if(head == nullptr){
        head = node;
    }else{
        if(p->index > node->index){
            node->next = head;
            head = node;
        }else{
            while(p){
                if(p->next != nullptr){
                    if(p->next->index > node->index){
                        node->next = p->next;
                        p->next = node;
                        break;
                    }

                }else{
                    p->next = node;
                    break;
                }

                p = p->next;
            }
        }

    }
}

void List::Delete(int index){
    Node *p = head, *tmp = nullptr;
    if(p->index == index){
        tmp = p->next;
        head = tmp;
    }else{
        while(p){
            if(p->next->index == index){
                tmp = p->next->next;
                delete p->next;
                p->next = tmp;

                break;
            }

            p = p->next;
        }
    }

}

void List::Show(int index){
    Node *p = head;

    while(p){

        if(index != NULL && p->index == index){
            std::cout << p->index << "\t" << p->values << std::endl;
            break;
        }
        
        if(index == NULL){
            std::cout << p << "\t" << p->index << "\t" << p->values << "\t" << p->next << std::endl;
        }

        p = p->next;
    }

    std::cout << std::endl;
}

void List::Update(int index, std::string values){
    Node *p = head;

    while(p){
        if(p->index == index){
            p->values = values;
            break;
        }

        p = p->next;
    }
}

[Insert函数详细说明]

这个函数只要分为4个部分,第一部分是建立一个新的结点。第二部分是初始化链表,若已初始化则跳过该部分。第三部分是判断新的结点的元素是否小于已存在的元素,若小于则把新元素插入在链表的最前。第四部分就是把元素插入对应的地方,这个插入行为是按索引值来排列的。

Main.cpp 程序的主文件

#include <iostream>
#include <string>
#include "List.h"

using namespace std;

int main(){
    List _list;

    //通过循环插入元素
    for(int i = 0; i < 8; i++){
        char tmp[10];
        sprintf_s(tmp, "test%d", i);
        _list.Insert(i, tmp);
    }
    _list.Show();

    //删除元素2
    _list.Delete(2);
    _list.Show();

    //显示元素3
    _list.Show(3);

    //修改元素5
    _list.Update(5, "test");
    _list.Show();

    //释放内存
    _list.~List();

    system("pause");
    return 0;
}

这就是简易链表的实现方式,虽然效率不是最高的写法,但是看起来非常的清晰。

标签:计算机, 程序, 设计, 常用, 算法, 简易, 链表

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:http://blog.fdawn.com/CPP/19.html

添加新评论