数据结构中的链表
链表与线性表相对,链表数据在内存中的存储空间是不连续的,链表每个节点包含数据域和指针域。
代码
下述代码实现了链表及其接口
包括增、删、查、改以及其他一些简单的功能
#include <iostream>
using namespace std;
#define eleType int
struct ListNode{//表示链表的一个节点
eleType data;
ListNode *next;
ListNode(eleType x) : data(x),next(NULL){}//构造函数
};
class LinkedList{//链表类
private:
ListNode *head;
int size;
public:
LinkedList() : head(NULL), size(0){}//链表的构造函数
~LinkedList();//析构函数
void insert(int i, eleType value);//增
void remove(int i);//删
ListNode* find(eleType value);//查
ListNode* get(int i);//查
void update(int i, eleType value);//改
void print();
};//模板//1分号
LinkedList::~LinkedList(){
ListNode *curr = head;
while(curr != NULL){
ListNode *tmp = curr;
curr = curr->next;
delete tmp;
}
}
void LinkedList::insert(int i, eleType value){
if(i < 0 || i > size){//2是>不是>=
throw std::out_of_range("Invalid position");
}
ListNode *newNode = new ListNode(value);
if(i == 0){
newNode->next = head;
head = newNode;
}
else{
ListNode *curr = head;
for(int j = 0; j < i-1; j++){
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
size++;
}
void LinkedList::remove(int i){
if(i < 0 || i >= size){
throw std::out_of_range("Invalid position");
}
if(i == 0){
ListNode *tmp = head;
head = head->next;
delete tmp;
}
else{
ListNode *curr = head;
for(int j = 0 ;j < i-1; j++){
curr = curr->next;
}
ListNode *tmp = curr->next;
curr->next = tmp->next;
delete tmp;
}
}
ListNode* LinkedList::find(eleType value){
ListNode *curr = head;
while(curr != NULL && curr->data != value){
curr = curr->next;
}
return curr;
}
ListNode* LinkedList::get(int i){
if(i < 0 || i >= size){
throw std::out_of_range("Invalid position");
}
ListNode *curr = head;
for(int j = 0 ;j < i; j++){
curr = curr->next;
}
return curr;
}
void LinkedList::update(int i, eleType value){
get(i)->data = value;
}
void LinkedList::print(){
ListNode *curr = head;
while(curr){
cout << curr->data << " " ;
curr = curr->next;
}
cout << endl;
}
int main()
{
LinkedList list;
list.insert(0,10);
list.insert(1,100);
list.insert(2,1000);
list.insert(3,10000);
list.insert(4,100000);
list.insert(5,1);
list.print();//对应运行结果第一行
list.remove(1);
list.print();//对应运行结果第二行
cout << list.find(10000)->data << endl;//对应运行结果第三行
cout << list.get(4)->data << endl;//对应运行结果第四行
list.update(1,1234);
list.print();//对应运行结果第五行
return 0;
}
运行结果:
于 2024-01-23 第一次整理编写文章来源:https://www.toymoban.com/news/detail-819854.html
学习时整理,不当之处烦请指正
码字不易,留个赞再走吧文章来源地址https://www.toymoban.com/news/detail-819854.html
到了这里,关于【c++学习】数据结构中的链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!