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

link.h

#ifndef link_H
#define link_H
#pragma once
#include 
#define OK 1
#define fail 0
using namespace std;

template 
class Node
{
public:
  Node *next;
  T *data;
};

template 
class link
{
private:
  Node *head;
  int length;

public:
  // 构造函数，初始化链表
  link();
  // 拷贝构造
  link(const link &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& operator+(const link &plink);
};

#endif //TEST1_LIST_H

link.cpp

#include "link.h"

// 初始化链表
template
link::link(){
  this->head=new Node;
  this->head->next=NULL;
  this->head->data=NULL;
  this->length=0;
}

// 拷贝构造
template
link::link(const link &ln){
  this->length=ln.length;
  this->head=new Node;
  this->head->next=NULL;
  Node *p=this->head;
  Node *move=ln.head->next;
  for(int i=0;ilength;++i){
    Node *newNode=new Node;
    newNode->data=move->data;
    newNode->next=NULL;
    p->next=newNode;
    p=newNode;
    move=move->next;
  }
}

// 析构
template
link::~link(){
  this->link_destory();
}

// 指定位置添加节点
template
int link::link_insert(int pos,T *value){
  if(!value){
    return fail;
  }
  if(pos<0||pos>this->length){
    pos=this->length;
  }
  Node *pCur=this->head;
  for(int i=0;inext;
  }
  Node *newNode=new Node;
  newNode->next=pCur->next;
  newNode->data=value;
  pCur->next=newNode;
  this->length++;
  return OK;
}

// 遍历链表
template
void link::link_foreach(void(print)(T *)){
  if(!print){
    return ;
  }
  Node *pCur=this->head;
  for(int i=0;ilength;++i){
    pCur=pCur->next;
    print(pCur->data);
  }  
}

// 删除尾结点
template
T* link::link_pop(){
  if(this->length==0)
    return NULL;
  Node *pCur=this->head;
  for(int i=0;ilength;++i){
    pCur=pCur->next;
  }
  Node *deleteNode=pCur;
  T *value=deleteNode->data;
  delete deleteNode;
  pCur=pCur->next;
  this->length--;
  return value;
}

// 插入尾结点
template
int link::link_push(T *value){
  if(!value)
    return fail;
  Node *pCur=this->head;
  for(int i=0;ilength;i++){
    pCur=pCur->next;
  }
  Node *newNode=new Node;
  newNode->data=value;
  newNode->next=NULL;
  pCur->next=newNode;
  this->length++;
  return OK;
}

// 删除头结点
template
T * link::link_shift(){
  if(this->length==0)
    return NULL;
  Node *pCur=this->head;
  T *value=pCur->next->data;
  Node *deleteNode=pCur->next;
  pCur->next=deleteNode->next;
  delete deleteNode;
  this->length--;
  return value;
}

// 查找指定位置节点
template
T * link::link_index(int index){
  if(index>this->length||index<0)
    return NULL;
  Node *pCur=this->head->next;
  for(int i=0;inext;
  }
  return pCur->data;
}

// 添加头结点
template
int link::link_unshift(T *value){
  if(!value)
    return fail;
  Node *pCur=this->head;
  Node *newNode=new Node;
  newNode->data=value;
  newNode->next=pCur->next;
  pCur->next=newNode;
  this->length++;
  return OK;
}

// 查找节点 
template
T * link::link_find(bool(print)(T *)){
  if(this->length==0||!print)
    return NULL;
  Node *pCur=this->head->next;
  for(int i=0;ilength;i++){
    if(print(pCur->data)){
      return pCur->data;
    }
  }
  return NULL;
}

// 翻转链表
template
int link::link_reverse(){
  if(this->length==0)
    return fail;
  Node *pHead=this->head;
  Node *pFont=NULL;
  Node *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
int link::link_length(){
  return this->length;
}

// 清空链表
template
int link::link_clear(){
  if(this->length==0)
    return OK;
  Node *pCur=this->head->next;
  for(int i=0;ilength;i++){
    Node *t=pCur->next;
    if(!pCur)
      break;
    delete pCur;
    pCur=t;
  }
  this->length=0;
  return OK;
}

// 销毁链表
template
int link::link_destory(){
  this->link_clear();
  if(this->head){
    delete this->head;
  }
  return OK;
}

// 连接链表
template
link& link::operator+(const link &plink){
  Node *pCur=this->head;
  for(int i=0;ilength;++i){
    pCur=pCur->next;
  }
  // pCur->next=plink.head->next;
  Node *move=plink.head->next;
  Node *newHead=new Node;
  newHead->next=NULL;
  Node *p=newHead;
  for(int i=0;i *newNode=new Node;
    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 
#include 
using namespace std;

struct person{
  int id;
  string name;
  int age;
};

int maxValue=-99;
int minValue=99;
struct person *pMax;
struct person *pMin;
template
void myPrint(T *value){
  struct person *p=(struct person *)value;
  if(maxValueage){
    maxValue=p->age;
    pMax=p;
  }
  if(minValue>p->age){
    minValue=p->age;
    pMin=p;
  }
  cout<<"id:"<id<<" name:"<name<<" age:"<age<
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 *k1=new link();
  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:"<id<<" name:"<name<<" age:"<age<link_foreach(myPrint);
  cout<<"max value. id:"<id<<" name:"<name<<" age:"<age<id<<" name:"<name<<" age:"<age<link_find(findPrint);
  if(p)
  cout<<"find id:"<id<<" name:"<name<<" age:"<age<link_reverse()<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<link_length()< *k2=new link(*k1);
  k2->link_insert(0,&p1);
  k2->link_foreach(myPrint);
  cout<<"-------------------------------------"<link_foreach(myPrint);

  *k1=*k1+*k2;
  cout<<"-------------------------------------"<link_foreach(myPrint);
  k1->link_destory();
  cout<<"-------------------------------------"<link_foreach(myPrint);
  p=(struct person *)k2->link_index(0);
  cout<<"index id:"<id<<" name:"<name<<" age:"<age<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
请按任意键继续. . .