c++数据结构之实现链表操作-创新互联

实现链表，首先要实现节点，然后由节点串成链表，一般来说会有打印节点、插入、删除、返回长度、空不空判断等操作。其中最重要的就是插入和删除操作。我觉得在实现上，主要还是要理解节点在链表中是怎么表示的，在对节点操作时是以什么形式进行操作的。

#include//#include//#include//#includeusing namespace std;

struct ListNode
{double value;
	ListNode* next; // 指向相同类型节点的指针
};

// 链表类
class LinkList
{private:
	ListNode* head;
public:
	LinkList():head(nullptr){}
	~LinkList() {cout<< "析构链表"<< endl; }
	void insert(int i, double value);
	bool isempty();
	void shownodes();
	int length();
	void erase(int i);
};

void LinkList::erase(int i)
{// 删除第i个节点,检查合法性
	if (i<0 || i>this->length()) {cout<< "i = "<< i<< ", 输入不合法!"<< endl;
		return;
	}
	if (i == 1) {// 如果删除头节点
		ListNode* temp_head = head; // 保存目前的头结点
		head = head->next; // 将head後的节点置为头节点
		delete temp_head; // 删除之前的头结点
	}
	else {// 否则就是删除其他节点
		// 首先找到这个节点和这个节点的前一个节点
		ListNode* node_del = head->next;
		ListNode* node_pre = head;
		while (i>2) {	node_del = node_del->next;
			node_pre = node_pre->next;
			i--;
		}
		node_pre->next = node_del->next;
		delete node_del;
	}
}

int LinkList::length()
{if (isempty()) return 0;
	int l = 0;
	ListNode* node = head;
	while (node) {l += 1;
		node = node->next;
	}
	return l;
}


void LinkList::shownodes()
{ListNode* begin = this->head;
	while (begin) {cout<< begin->value<< "\t";
		begin = begin->next;
	}
	cout<< endl;
}

bool LinkList::isempty()
{if (this->head == nullptr) return true;
	else return false;
}

void LinkList::insert(int i, double value) {if (this->isempty()) {// 如果是空表,就只能接在头上
		cout<< "空表,将接在头上"<< endl;
		head = new ListNode; // 申请空间
		head->value = value;
		head->next = nullptr;
		return;
	}
	// 检查i的合法性
	if (i >this->length()) {cout<< "i = "<< i<< "的值大于链表长度,异常输入!"<< endl;
		return;
	}
	
	// 否则插入节点
	ListNode* s = new ListNode; // 新建节点
	s->value = value;
	if (i == 1) {// 如果是头节点
		// 插入表头
		s->next = head;
		head = s; // 修改头节点的值
		return;
	}

	// 找到第i个节点
	ListNode* node = head;
	while (i >2) {node = node->next;
		i--;			
	}
	if (node != nullptr)
	{// 现在node是插入位置的前一个节点
		s->next = node->next;
		node->next = s;
	}	
}


int main()
{LinkList alinklist;
	alinklist.insert(2, 2.3); // 插入节点，作为第2个节点(由于此时是空表，所有会被当成插入头节点)
	alinklist.insert(1, 4.4);
	alinklist.insert(1, 3.3);
	alinklist.insert(8, 8.5); // 插入节点，作为第8个节点
	alinklist.insert(2, 2.5); // 插入节点，作为第2个节点
	alinklist.insert(3, 3.5); // 插入节点，作为第2个节点


	alinklist.shownodes(); // 打印节点内容

	alinklist.erase(5); // 删除第5个节点
	alinklist.erase(5); // 删除第5个节点
	alinklist.erase(3); // 删除第3个节点
	alinklist.shownodes(); // 打印节点内容

	cout<< "这里程序结束"<< endl;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧