holyya.com
2025-09-04 16:42:36 Thursday
登录
文章检索 我的文章 写文章
C++链表类模板的实现
2023-06-30 21:34:11 深夜i     --     --
C++ 链表 类模板 实现

在C++编程中，链表类是一种非常有用的数据结构，它能够存储和管理大量的数据。其中链表类模板的实现更加普遍和灵活，能够适用于不同类型的数据，包括整数、浮点数、字符等。下面将介绍如何实现一个基本的链表类模板。

首先，我们需要定义一个节点类来存储链表的每个元素。节点类通常包含两个成员变量：一个是数据的值，另一个是一个指向下一个节点的指针。这个指针是存储链表中每个元素的关键部分。

template

class Node{

public:

  T data;

  Node * next;

}

接下来，我们需要定义链表类，它是一个由节点组成的集合。链表类模板应该有一个指向链表头部的指针。每个节点的指针next指向链表下一个节点，最后一个节点的指针指向NULL。

template

class LinkedList{

public:

  LinkedList();

  void push_front(T value); //在链表前插入元素

  void push_back(T value);  //在链表后插入元素

  void remove_front();    //删除第一个元素

  void remove_back();    //删除最后一个元素

  void insert(T value, int pos); //在链表中插入元素

  void remove(int pos);   //删除指定位置的元素

  int size();        //获取链表大小

  void print();       //打印链表内容

private:

  Node * head;       //链表头部指针

  int count;         //链表大小

};

链表类模板中需要定义一些公共方法。例如，push_front和push_back方法用于在链表前或后插入元素。remove_front和remove_back方法删除链表中第一个或最后一个元素。insert和remove方法用于在链表中插入或删除元素。size方法用于获得链表的大小。print方法用于打印链表中的所有元素。

下面是一些公共方法的示例：

template

LinkedList ::LinkedList()

  head = NULL;

  count = 0;

template

void LinkedList ::push_front(T value){

  Node * newNode = new Node ;

  newNode->data = value;

  newNode->next = head;

  head = newNode;

  count++;

}

template

void LinkedList ::push_back(T value){

  Node * newNode = new Node ;

  newNode->data = value;

  newNode->next = NULL;

  if(head==NULL)

    head = newNode;

  else{

    Node * temp = head;

    while(temp->next!=NULL)

      temp = temp->next;

    temp->next = newNode;

  }

  count++;

}

template

void LinkedList ::remove_front(){

  if(head==NULL)

    cout << "List is empty" << endl;

  else{

    Node * temp = head;

    head = head->next;

    delete temp;

    count--;

  }

}

template

void LinkedList ::remove_back(){

  if(head==NULL)

    cout << "List is empty" << endl;

  else if(head->next==NULL)

    delete head;

    head = NULL;

    count--;

  else{

    Node * temp = head;

    while(temp->next->next!=NULL)

      temp = temp->next;

    delete temp->next;

    temp->next = NULL;

    count--;

  }

}

template

void LinkedList ::insert(T value, int pos){

  if(pos<0 || pos>count)

    cout << "Invalid position" << endl;

  else if(pos==0){

    push_front(value);

  }else if(pos==count){

    push_back(value);

  }else{

    Node * temp = head;

    Node * newNode = new Node ;

    newNode->data = value;

    for(int i=0; i

      temp = temp->next;

    newNode->next = temp->next;

    temp->next = newNode;

    count++;

  }

}

template

void LinkedList ::remove(int pos){

  if(pos<0 || pos>=count)

    cout << "Invalid position" << endl;

  else if(pos==0){

    remove_front();

  }else if(pos==count-1){

    remove_back();

  }else{

    Node * temp = head;

    Node * toDelete;

    for(int i=0; i

      temp = temp->next;

    toDelete = temp->next;

    temp->next = temp->next->next;

    delete toDelete;

    count--;

  }

}

template

int LinkedList ::size()

  return count;

template

void LinkedList ::print(){

  if(head==NULL)

    cout << "List is empty" << endl;

  else{

    Node * temp = head;

    while(temp!=NULL)

      cout << temp->data << " ";

      temp = temp->next;

    cout << endl;

  }

}

以上是链表类模板的一些基本方法和实现，可以用于存储和管理大量的数据。应用链表类模板，我们可以将不同类型、不同长度、不同功能的数据进行统一的处理和操作。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复