数据结构C++ 实现单链表

68 阅读 0 评论 45 点赞

我是靠谱客的博主不安自行车，最近开发中收集的这篇文章主要介绍数据结构C++ 实现单链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

link.h

#ifndef LINK_H
#define LINK_H
#pragma once
#include <iostream>
#define OK 1
#define fail 0
using namespace std;
template <class T>
class Node
{
public:
Node<T> *next;
T *data;
};
template <class T>
class Link
{
private:
Node<T> *head;
int length;
public:
// 构造函数，初始化链表
Link();
// 拷贝构造
Link(const Link<T> &ln);
// 析构
~Link();
// 指定位置添加节点
int link_insert(int pos, T *value);
// 遍历链表
void link_foreach(void(print)(T *));
// 删除尾结点
T *link_pop();
// 添加尾节点
int link_push(T *value);
// 删除头结点
T *link_shift();
// 添加头结点
int link_unshift(T *value);
// 输出指定位置节点
T * link_index(int index);
// 查找节点
T * link_find(bool(print)(T *));
// 翻转链表
int link_reverse();
// 获取链表长度
int link_length();
// 清空链表
int link_clear();
// 销毁链表
int link_destory();
// 连接链表
Link<T>& operator+(const Link<T> &plink);
};
#endif //TEST1_LIST_H

link.cpp

#include "link.h"
// 初始化链表
template<typename T>
Link<T>::Link(){
this->head=new Node<T>;
this->head->next=NULL;
this->head->data=NULL;
this->length=0;
}
// 拷贝构造
template<typename T>
Link<T>::Link(const Link<T> &ln){
this->length=ln.length;
this->head=new Node<T>;
this->head->next=NULL;
Node<T> *p=this->head;
Node<T> *move=ln.head->next;
for(int i=0;i<this->length;++i){
Node<T> *newNode=new Node<T>;
newNode->data=move->data;
newNode->next=NULL;
p->next=newNode;
p=newNode;
move=move->next;
}
}
// 析构
template<typename T>
Link<T>::~Link(){
this->link_destory();
}
// 指定位置添加节点
template<typename T>
int Link<T>::link_insert(int pos,T *value){
if(!value){
return fail;
}
if(pos<0||pos>this->length){
pos=this->length;
}
Node<T> *pCur=this->head;
for(int i=0;i<pos;++i){
pCur=pCur->next;
}
Node<T> *newNode=new Node<T>;
newNode->next=pCur->next;
newNode->data=value;
pCur->next=newNode;
this->length++;
return OK;
}
// 遍历链表
template<typename T>
void Link<T>::link_foreach(void(print)(T *)){
if(!print){
return ;
}
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
print(pCur->data);
}
}
// 删除尾结点
template<typename T>
T* Link<T>::link_pop(){
if(this->length==0)
return NULL;
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
}
Node<T> *deleteNode=pCur;
T *value=deleteNode->data;
delete deleteNode;
pCur=pCur->next;
this->length--;
return value;
}
// 插入尾结点
template<typename T>
int Link<T>::link_push(T *value){
if(!value)
return fail;
Node<T> *pCur=this->head;
for(int i=0;i<this->length;i++){
pCur=pCur->next;
}
Node<T> *newNode=new Node<T>;
newNode->data=value;
newNode->next=NULL;
pCur->next=newNode;
this->length++;
return OK;
}
// 删除头结点
template<typename T>
T * Link<T>::link_shift(){
if(this->length==0)
return NULL;
Node<T> *pCur=this->head;
T *value=pCur->next->data;
Node<T> *deleteNode=pCur->next;
pCur->next=deleteNode->next;
delete deleteNode;
this->length--;
return value;
}
// 查找指定位置节点
template<typename T>
T * Link<T>::link_index(int index){
if(index>this->length||index<0)
return NULL;
Node<T> *pCur=this->head->next;
for(int i=0;i<index;++i){
pCur=pCur->next;
}
return pCur->data;
}
// 添加头结点
template<typename T>
int Link<T>::link_unshift(T *value){
if(!value)
return fail;
Node<T> *pCur=this->head;
Node<T> *newNode=new Node<T>;
newNode->data=value;
newNode->next=pCur->next;
pCur->next=newNode;
this->length++;
return OK;
}
// 查找节点
template<typename T>
T * Link<T>::link_find(bool(print)(T *)){
if(this->length==0||!print)
return NULL;
Node<T> *pCur=this->head->next;
for(int i=0;i<this->length;i++){
if(print(pCur->data)){
return pCur->data;
}
}
return NULL;
}
// 翻转链表
template<typename T>
int Link<T>::link_reverse(){
if(this->length==0)
return fail;
Node<T> *pHead=this->head;
Node<T> *pFont=NULL;
Node<T> *pNext=NULL;
while(pHead->next!=NULL){
pFont=pHead->next;
pHead->next=pFont->next;
pFont->next=pNext;
pNext=pFont;
}
this->head->next=pFont;
return OK;
}
// 获取链表长度
template<typename T>
int Link<T>::link_length(){
return this->length;
}
// 清空链表
template<typename T>
int Link<T>::link_clear(){
if(this->length==0)
return OK;
Node<T> *pCur=this->head->next;
for(int i=0;i<this->length;i++){
Node<T> *t=pCur->next;
if(!pCur)
break;
delete pCur;
pCur=t;
}
this->length=0;
return OK;
}
// 销毁链表
template<typename T>
int Link<T>::link_destory(){
this->link_clear();
if(this->head){
delete this->head;
}
return OK;
}
// 连接链表
template<typename T>
Link<T>& Link<T>::operator+(const Link<T> &plink){
Node<T> *pCur=this->head;
for(int i=0;i<this->length;++i){
pCur=pCur->next;
}
// pCur->next=plink.head->next;
Node<T> *move=plink.head->next;
Node<T> *newHead=new Node<T>;
newHead->next=NULL;
Node<T> *p=newHead;
for(int i=0;i<plink.length;++i){
Node<T> *newNode=new Node<T>;
newNode->data=move->data;
newNode->next=NULL;
p->next=newNode;
p=newNode;
move=move->next;
}
pCur->next=newHead->next;
this->length+=plink.length;
delete newHead;
return *this;
}

test.cpp

#include "link/link.cpp"
#include <iostream>
#include <string>
using namespace std;
struct person{
int id;
string name;
int age;
};
int maxValue=-99;
int minValue=99;
struct person *pMax;
struct person *pMin;
template<typename T>
void myPrint(T *value){
struct person *p=(struct person *)value;
if(maxValue<p->age){
maxValue=p->age;
pMax=p;
}
if(minValue>p->age){
minValue=p->age;
pMin=p;
}
cout<<"id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
}
template<typename T>
bool findPrint(T *value){
struct person *p1=(struct person *)value;
if(p1->age==20&&p1->id==3&&p1->name=="Sam"){
return true;
}else{
return false;
}
}
void test(){
struct person p1={1,"Andy",18};
struct person p2={2,"Tom",19};
struct person p3={3,"Sam",20};
struct person p4={4,"Tim",21};
struct person p5={5,"Jack",22};
Link<person> *k1=new Link<person>();
k1->link_insert(0,&p1);
k1->link_insert(0,&p2);
k1->link_insert(0,&p3);
k1->link_insert(0,&p4);
k1->link_insert(0,&p5);
k1->link_push(&p5);
k1->link_unshift(&p3);
// struct person *p=(struct person *)k1->link_shift();
// cout<<"111id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
k1->link_foreach(myPrint);
cout<<"max value. id:"<<pMax->id<<" name:"<<pMax->name<<" age:"<<pMax->age<<endl;
cout<<"min value. id:"<<pMin->id<<" name:"<<pMin->name<<" age:"<<pMin->age<<endl;
struct person *p=(struct person *)k1->link_find(findPrint);
if(p)
cout<<"find id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
cout<<k1->link_reverse()<<endl;
cout<<"------------------"<<endl;
k1->link_foreach(myPrint);
k1->link_clear();
k1->link_insert(0,&p1);
k1->link_insert(0,&p2);
k1->link_insert(0,&p3);
k1->link_insert(0,&p4);
k1->link_insert(0,&p5);
k1->link_foreach(myPrint);
cout<<k1->link_length()<<endl;
cout<<"-------------------------------------"<<endl;
Link<person> *k2=new Link<person>(*k1);
k2->link_insert(0,&p1);
k2->link_foreach(myPrint);
cout<<"-------------------------------------"<<endl;
k1->link_foreach(myPrint);
*k1=*k1+*k2;
cout<<"-------------------------------------"<<endl;
k1->link_foreach(myPrint);
k1->link_destory();
cout<<"-------------------------------------"<<endl;
cout<<"find id:"<<p5.id<<" name:"<<p5.name<<" age:"<<p5.age<<endl;
// k2->link_foreach(myPrint);
p=(struct person *)k2->link_index(0);
cout<<"index id:"<<p->id<<" name:"<<p->name<<" age:"<<p->age<<endl;
k2->link_destory();
}
int main(){
test();
system("pause");
return EXIT_SUCCESS;
}

运行结果

id:3 name:Sam age:20
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
id:5 name:Jack age:22
max value. id:5 name:Jack age:22
min value. id:1 name:Andy age:18
find id:3 name:Sam age:20
1
------------------
id:5 name:Jack age:22
id:1 name:Andy age:18
id:2 name:Tom age:19
id:3 name:Sam age:20
id:4 name:Tim age:21
id:5 name:Jack age:22
id:3 name:Sam age:20
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
5
-------------------------------------
id:1 name:Andy age:18
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
id:1 name:Andy age:18
id:5 name:Jack age:22
id:4 name:Tim age:21
id:3 name:Sam age:20
id:2 name:Tom age:19
id:1 name:Andy age:18
-------------------------------------
find id:5 name:Jack age:22
index id:1 name:Andy age:18
请按任意键继续. . .