您当前的位置: 首页 » ASP/ASP.NET编程 » 链表的顺序表示和实现（C++模板类实现）
链表的顺序表示和实现（C++模板类实现）
论坛链接
/*List.h*/
#ifndef _LIST_H
#define _LIST_H
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
template <class T>
class List
{
public:
List(); //构造函数：构造一个空的线性表
//~List(); //析构函数
void DestroyList(); //销毁线性表
void ClearList(); //将表重置为空表
bool ListEmpty(); //若为空表存在返回True
int ListLength(); //返回表中数据元素个数
T GetElem(int i,T &e); //用e返回表中第i个元素的值
int LocateElem(T e); //返回表中第一个e元素的位置
T PriorElem(T cur_e,T &pre_e); //返回前驱
T NextElem(T cur_e,T &next_e); //返回后继
void ListInsert(int i,T e); //在第i个元素插入值e
T ListDelete(int i,T &e); //删除第i个元素的值并返回
void ListTraverse(void visit()); //对每个元素进行visit()
private:
T *elem;
int length;
int listsize;
};
//构造一个空的线性表
template <class T>
List<T>::List()
{
elem=(T *)malloc(LIST_INIT_SIZE*sizeof(T)); /*分配空间*/
if(!elem)
throw "Allocation failed";
else
{
length=0;
listsize=LIST_INIT_SIZE;
}
}
//销毁线性表
template <class T>
void List<T>::DestroyList()
{
free(elem);
}
//将表重置为空表
template <class T>
void List<T>::ClearList()
{
length=0;
}
//若为空表存在返回True
template <class T>
bool List<T>::ListEmpty()
{
return length ? true :false;
}
//返回表中数据元素个数
template <class T>
int List<T>::ListLength()
{
return length;
}
//用e返回表中第i个元素的值
template <class T>
T List<T>::GetElem(int i,T &e)
{
if(i<1||i>length)
throw "Index out of bounds";
else
e=elem[i-1];
return e;
}
//返回表中第一个e元素的位置
template <class T>
int List<T>:: LocateElem(T e)
{
for(int i=0;i<length;i++)
{
if(elem==e)
return i+1;
}
cout<<"表中不存在值为"<<e<<"的元素!"<<endl;
return 0;
}
//返回前驱
template <class T>
T List<T>::PriorElem(T cur_e,T &pre_e)
{
int i=LocateElem(cur_e);
if(i>1)
{
pre_e=elem[i-2];
return pre_e;
}
else
return NULL;
}
//返回后继
template <class T>
T List<T>::NextElem(T cur_e,T &next_e)
{
int i=LocateElem(cur_e);
if(i>0&&i<length)
{
next_e=elem;
return next_e;
}
else
return NULL;
}
//在第i个元素插入值e
template <class T>
void List<T>::ListInsert(int i,T e)
{
if(i<0||i>length+1) cout<<"error!";
else if(i==length)
{
elem = (T *)realloc(elem,(length+LISTINCREMENT)*sizeof(T));
}
for(int j=length;j>=i;j--) elem[length]=elem[length-1];
elem[i-1]=e;
length++;
}
//删除第i个元素的值并返回
template <class T>
T List<T>::ListDelete(int i,T &e)
{
if(length==0) return NULL;
if(i<0||i>length) return NULL;
e=elem[i-1];
for(int j=i;j<length;j++) elem[j-1]=elem[j];
length--;
return e;
}
//对每个元素进行visit()
template <class T>
void List<T>::ListTraverse(void visit())
{
for(i=0;i<length;i++) visit(elem);
}
#endif
//程序测试文件，http://blog.ourys.com/原创，做人好厚道，转载请表明出去
#include<iostream>
#include "List.h"
using namespace std;
int main()
{
List<int> list;
for(int i=0;i<10;i++) list.ListInsert(i+1,i*(1+i));
int a[10],b[10];
for(int i=0;i<list.ListLength();i++) cout<<list.GetElem(1+i,a)<<endl;
cout<<list.ListLength()<<endl;
cout<<list.LocateElem(90)<<endl;
list.NextElem(0,b[0]);
cout<<b[0]<<endl;
cout<<list.ListDelete(4,b[1])<<endl;
for(int i=0;i<list.ListLength();i++) cout<<list.GetElem(1+i,a)<<endl;
return 0;
}
#ifndef _LIST_H
#define _LIST_H
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
template <class T>
class List
{
public:
List(); //构造函数：构造一个空的线性表
//~List(); //析构函数
void DestroyList(); //销毁线性表
void ClearList(); //将表重置为空表
bool ListEmpty(); //若为空表存在返回True
int ListLength(); //返回表中数据元素个数
T GetElem(int i,T &e); //用e返回表中第i个元素的值
int LocateElem(T e); //返回表中第一个e元素的位置
T PriorElem(T cur_e,T &pre_e); //返回前驱
T NextElem(T cur_e,T &next_e); //返回后继
void ListInsert(int i,T e); //在第i个元素插入值e
T ListDelete(int i,T &e); //删除第i个元素的值并返回
void ListTraverse(void visit()); //对每个元素进行visit()
private:
T *elem;
int length;
int listsize;
};
//构造一个空的线性表
template <class T>
List<T>::List()
{
elem=(T *)malloc(LIST_INIT_SIZE*sizeof(T)); /*分配空间*/
if(!elem)
throw "Allocation failed";
else
{
length=0;
listsize=LIST_INIT_SIZE;
}
}
//销毁线性表
template <class T>
void List<T>::DestroyList()
{
free(elem);
}
//将表重置为空表
template <class T>
void List<T>::ClearList()
{
length=0;
}
//若为空表存在返回True
template <class T>
bool List<T>::ListEmpty()
{
return length ? true :false;
}
//返回表中数据元素个数
template <class T>
int List<T>::ListLength()
{
return length;
}
//用e返回表中第i个元素的值
template <class T>
T List<T>::GetElem(int i,T &e)
{
if(i<1||i>length)
throw "Index out of bounds";
else
e=elem[i-1];
return e;
}
//返回表中第一个e元素的位置
template <class T>
int List<T>:: LocateElem(T e)
{
for(int i=0;i<length;i++)
{
if(elem==e)
return i+1;
}
cout<<"表中不存在值为"<<e<<"的元素!"<<endl;
return 0;
}
//返回前驱
template <class T>
T List<T>::PriorElem(T cur_e,T &pre_e)
{
int i=LocateElem(cur_e);
if(i>1)
{
pre_e=elem[i-2];
return pre_e;
}
else
return NULL;
}
//返回后继
template <class T>
T List<T>::NextElem(T cur_e,T &next_e)
{
int i=LocateElem(cur_e);
if(i>0&&i<length)
{
next_e=elem;
return next_e;
}
else
return NULL;
}
//在第i个元素插入值e
template <class T>
void List<T>::ListInsert(int i,T e)
{
if(i<0||i>length+1) cout<<"error!";
else if(i==length)
{
elem = (T *)realloc(elem,(length+LISTINCREMENT)*sizeof(T));
}
for(int j=length;j>=i;j--) elem[length]=elem[length-1];
elem[i-1]=e;
length++;
}
//删除第i个元素的值并返回
template <class T>
T List<T>::ListDelete(int i,T &e)
{
if(length==0) return NULL;
if(i<0||i>length) return NULL;
e=elem[i-1];
for(int j=i;j<length;j++) elem[j-1]=elem[j];
length--;
return e;
}
//对每个元素进行visit()
template <class T>
void List<T>::ListTraverse(void visit())
{
for(i=0;i<length;i++) visit(elem);
}
#endif
//程序测试文件，http://blog.ourys.com/原创，做人好厚道，转载请表明出去
#include<iostream>
#include "List.h"
using namespace std;
int main()
{
List<int> list;
for(int i=0;i<10;i++) list.ListInsert(i+1,i*(1+i));
int a[10],b[10];
for(int i=0;i<list.ListLength();i++) cout<<list.GetElem(1+i,a)<<endl;
cout<<list.ListLength()<<endl;
cout<<list.LocateElem(90)<<endl;
list.NextElem(0,b[0]);
cout<<b[0]<<endl;
cout<<list.ListDelete(4,b[1])<<endl;
for(int i=0;i<list.ListLength();i++) cout<<list.GetElem(1+i,a)<<endl;
return 0;
}