简易有序链表
链表是一种在内存中非连续、非顺序的存储结构，链表的数据元素的逻辑顺序是通过链表中的指针链接次序实现的，就是说通过一个指针指向下一个元素，而下一个元素的指针再指向再下一个。链表是由一系列结点（链表中的每一个元素称为结点）组成的，结点可以在程序运行时动态生成，所以不用固定链表的长度，从而可以大大的节省内存空间。
我写的这个简易链表主要实现了“增删改查”的功能，其中每个结点包括三个部分：第一个是链表元素的索引值（可用于操作元素），第二个是用于存放内容的字符串空间，第三个就是存放指向下一个元素的指针。
详细实现的代码：
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;
}
这就是简易链表的实现方式，虽然效率不是最高的写法，但是看起来非常的清晰。