数据结构---链表ADT C++实现
2024-08-30 21:53:40
最近在学习数据结构，刚开始一直在看书，但是总是感觉似懂非懂，心想还不如自己操练一波，势必有所收获。现将实现代码发表此地，以备日后复习，若有错误或者建议，欢迎告知本人！
1. 节点类
class Node {
public:
int data;
Node *next;
Node(int da):
data(da), next(NULL){}
};
这里节点类的定义采用多数OJ的模版（当然，也可以使用 struct ）
2. 链表类ADT
class List{
private:
Node *head;
public:
List(): head(NULL){}
~List(){
delete head;
cout<<"The list is deleted."<<endl;
};
int size(); // 链表长度
bool isEmpty(); // 是否为空
void printList(); // 打印链表
void insert(int position, int value); // 指定位置插入
void insertHead(int value); // 插入到最前
void insertTail(int value); // 插入到最后
int getValue(int position); // 查找指定位置的值
int search(int value); // 查找指定元素的位置
void update(int position, int value); // 更新指定位置的值
int erase(int position); // 删除指定位置的节点
void reverse(); // 反转链表
//void clearList() // 清空链表
};
3. 完整代码
#include<iostream>
using namespace std; class Node {
public:
int data;
Node *next;
Node(int da):
data(da), next(NULL){}
}; class List{
private:
Node *head;
public:
List(): head(NULL){}
~List(){
delete head;
cout<<"The list is deleted."<<endl;
};
int size(); // 链表长度
bool isEmpty(); // 是否为空
void printList(); // 打印链表
void insert(int position, int value); // 指定位置插入
void insertHead(int value); // 插入到最前
void insertTail(int value); // 插入到最后
int getValue(int position); // 查找指定位置的值
int search(int value); // 查找指定元素的位置
void update(int position, int value); // 更新指定位置的值
int erase(int position); // 删除指定位置的节点
void reverse(); // 反转链表
//void clearList() // 清空链表
}; // 返回链表大小
int List::size(){
Node *p = head;
int index = ;
while(p != NULL){
index++;
p = p->next;
}
return index;
} // 判断链表是否为空
bool List::isEmpty(){
if(List::size() == )
return true;
else
return false;
} // 打印链表
void List::printList(){
Node *p = head;
while(p != NULL){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
cout<<endl;
} // 在position位置插入value
void List::insert(int position, int value){
if(position< || position>List::size()){
cout<<"position error, please check."<<endl;
return ;
}
Node *s = new Node(value); // new node
Node *p = head;
if(head == NULL){ // isEmpty = true
head = s;
}
else{ // isEmpty = false
if(position == ){
s->next = p;
head = s;
}
else{
int index = ;
while(index != position-){
p = p->next;
index++;
}
s->next = p->next;
p->next = s;
}
}
if (position == )
cout<<"insert "<<value<<" at the first."<<endl;
else if (position == List::size())
cout<<"insert "<<value<<" at the tail."<<endl;
else
cout<<"insert "<<value<<" at position "<<position<<endl;
} // 头部插入
void List::insertHead(int value){
List::insert(, value);
} // 尾部插入
void List::insertTail(int value){
List::insert(List::size(), value);
} // 搜索数据value，并返回位置
int List::search(int value){
Node *p = head;
int index = ;
while(p != NULL && p->data != value){
index++;
p = p->next;
}
if(p == NULL){
cout<<"the value is not in the list, please check."<<endl;
return -;
}
else{
cout<<value<<" at position "<<index<<endl;
return index;
}
} // 将position位置的数据更新为value
void List::update(int position, int value){
if(position< || position>(List::size()-)){
cout<<"position error, please check."<<endl;
return ;
}
Node *p = head;
int index = ;
while(index != position){
p = p->next;
index++;
}
p->data = value;
cout<<"update "<<value<<" at position "<<position<<endl;
} // 删除position位置的数据，并返回
int List::erase(int position){
if(position< || position>(List::size()-)){
cout<<"position error, please check."<<endl;
return -;
}
int res = List::getValue(position);
Node *p = head;
int index = ;
cout<<"erase data at position "<<position<<endl;
if(position == ){
head = p->next;
return res;
}
else{
while(index != position-){
p = p->next;
index++;
}
Node *temp = p->next;
p->next = temp->next;
return res;
}
} // 反转链表
void List::reverse(){
if (head == NULL || head->next == NULL)
return ;
Node *prev = head;
Node *cur = head->next;
Node *temp = head->next->next;
while(cur){
temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
head->next = NULL; // 更新末尾元素的指针
head = prev; // 更新头结点
cout<<"reverse the list."<<endl;
} // 返回position位置的数据
int List::getValue(int position){
if(position< || position>(List::size()-)){
cout<<"position error, please check."<<endl;
return -;
}
Node *p = head;
int index = ;
while(index != position){
p = p->next;
index++;
}
cout<<"position "<<position<<" is "<<p->data<<endl;
return p->data;
}
/*
void List::clearList(){
Node *p = head;
while(p){
Node *temp = p->next;
delete p;
p = temp;
}
}
*/
int main() {
List l1;
l1.insertTail();l1.printList();
l1.insertHead();l1.printList();
l1.insert(, );l1.printList();
l1.insert(, );l1.printList();
l1.insert(, );l1.printList();
l1.insert(, );l1.printList();
l1.insert(, );l1.printList();
l1.search();
l1.getValue();
l1.update(, );l1.printList();
l1.erase();l1.printList();
l1.reverse(); l1.printList();
cout<<"The size of the list: "<<l1.size()<<endl;
return ;
}
4. 运行结果
insert at the first. insert at the first. insert at position insert at the first. insert at position insert at the first. insert at position at position
position is
update at position position is
erase data at position reverse the list. The size of the list:
The list is deleted.
[Finished in .0s]
关于每一部分的详解会继续补充。
最新文章
- 冲刺一 （Day 3）
- nagios二次开发（二）---nagios和nagiosql合并与取舍
- [题解]poj 1274 The Prefect Stall
- BZOJ1008 ／乘法原理＋快速幂 解题报告
- Maven 插件开发（一）
- 前端开发者使用JS框架的三个等级
- 第二章——Serializable的使用(跨进程使用和Intent的传递对象)
- java 调用jdbc 实现excel和csv的导入和导出
- BZOJ 3230: 相似子串( RMQ + 后缀数组 + 二分 )
- iOS 纯代码适配iPhone6，6+
- elasticsearch系列（三）分表分库
- (转)微信开发连接SAE数据库
- .NET Core微服务之基于Consul实现服务治理
- 深度原理与框架-图像超分辨重构-tensorlayer
- Java常用工具方法
- python requests库与json数据处理详解
- vue国际化插件
- Mybatis类型转换介绍
- 【JAVA与C#比较】其它
- 【onethink搬家】win环境移植linux环境，注意事项
热门文章
- 【Silverlight】Bing Maps学习系列（一）：开发前的准备工作
- CSU 1806 Toll 自适应simpson积分+最短路
- 继续不温不火Windows Phone
- Oracle 10g 10.2.0.4的group by BUG |ORA-00979 not a GROUP BY expression|
- java运行代码连接mysql时提示：找不到类错误
- HTML5移动Web开发
- bzoj 1705: [Usaco2007 Nov]Telephone Wire 架设电话线【dp】
- [Swift通天遁地]一、超级工具-(9)在地图视图MKMapView中添加支持交互动作的标注图标
- vbnet 进程监控，监控Acad开启的数量，并且添加到开机启动
- Odoo免费开源企业信息化平台助力企业成功