简易有序链表

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

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

详细实现的代码:

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 原创并发布在 被遗忘的曙光 技术博客

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

添加新评论