c++链表如何使用
问一下如何使用c++链表,最好能举个例子
你可以用STL中的vector,它就相当于一个单链表。而STL中的list更像一个双向循环链表,因为它可以在两端插入、弹出数据。我也写过一个链表类
//-----------------ListNode.h-----------------------
#ifndef LISTNODE_H
#define LISTNODE_H
#include <iostream>
using namespace std;
template <class Type> class List;
template <class Type>
class ListNode
{
friend class List<Type>;
private:
Type data;
ListNode<Type>* link;
public:
ListNode ();
ListNode (const Type& item);
};
#endif
template <class Type>
ListNode<Type>::ListNode() : link(NULL)
{}
template <class Type>
ListNode<Type>::ListNode(const Type &item) : data(item), link(NULL)
{}
//---------------------List.h------------------------
#ifndef LIST_H
#define LIST_H
#include "ListNode.h"
template <class Type>
class List
{
private:
ListNode<Type> *first;
ListNode<Type> *last;
public:
List(const Type &value = NULL);
~List();
void MakeEmpty();
int Length() const;
ListNode<Type> *Find(Type value);
ListNode<Type> *Find(int index);
bool Insert(Type value, int index);
bool Remove(int index);
Type Get(int index);
};
#endif
// 构造函数
template <class Type>
List<Type>::List(const Type &value)
{
first = last = new ListNode<Type>(value);
}
// 析构函数
template <class Type>
List<Type>::~List()
{
MakeEmpty();
delete first;
}
// 链表清空
template <class Type>
void List<Type>::MakeEmpty()
{
ListNode<Type> *p;
while (first->link != NULL)
{
p = first->link;
first->link = p->link;
delete p;
}
last = first;
}
// 计算链表长度
template <class Type>
int List<Type>::Length() const
{
ListNode<Type> *p = first->link;
int count = 0;
while (p != NULL)
{
p = p->link;
count++;
}
return count;
}
// 按链表中所存储的信息查找
template <class Type>
ListNode<Type> * List<Type>::Find(Type value)
{
ListNode<Type> *p = first->link;
while (p != NULL && p->data != value)
{
p = p->link;
}
return p;
}
// 按下标查找
template <class Type>
ListNode<Type> * List<Type>::Find(int index)
{
if (index < -1)
return NULL;
if (index == -1)
return first;
ListNode<Type> *p = first->link;
int i = 0;
while (p != NULL && i < index)
{
p = p->link;
i++;
}
return p;
}
// 在指定位置插入数据
template <class Type>
bool List<Type>::Insert(Type value, int index)
{
ListNode<Type> *p = Find(index - 1);
if (p == NULL)
{
return false;
}
ListNode<Type> *newnode = new ListNode<Type>(value);
newnode->link = p->link;
if (p->link == NULL)
last = newnode;
p->link = newnode;
return true;
}
// 从链表中删除一个元素,删除index后边的节点
template <class Type>
bool List<Type>::Remove(int index)
{
ListNode<Type> *p = Find(index-1);
ListNode<Type> *q;
// 如果p为空,或者p的下一个节点为空,没有办法删除
if (p == NULL || p->link == NULL)
return false;
q = p;
p = p->link;
q->link = p->link;
delete p;
if (q->link == NULL)
last = q;
return true;
}
// 得到指定位置的节点data信息
template <class Type>
Type List<Type>::Get(int index)
{
ListNode<Type> *p = Find(index);
if (p == NULL || p == first)
return NULL;
else
return p->data;
}