1. 头文件LinearList
#ifndef _LINEARLIST_H_
#define _LINEARLIST_H_
#include<iostream>
using namespace std;
template<class T> ? ? ? ? ?//T为数据类型
class LinearList ? ? ? ? ? //模板名
{
private:
?? ?int length; ? ? ? ? ? ?//当前数组元素个数
?? ?int Maxsize; ? ? ? ? ? //线性表中最大元素个数
?? ?T*element; ? ? ? ? ? ? //一维动态数组
public:
?? ?LinearList(int LLMaxsize); ? ? ? ? ?//构造函数，创建空表
?? ?~LinearList(); ? ? ? ? ? ? ? ? ? ? ?//析构函数，删除表
?? ?LinearList<T>&InSert(int k, const T & x); ?//在第K个位置插入元素x，返回插入后的线性表
?? ?bool IsEmpty()const; ?//判断表是否为空，表空返回true，非空返回false
?? ?int GetLength()const; ?//返回表中数据元素个数
?? ?bool GetData(int k, T & x); ?//将表中第k个元素返回到x中，不存在返回false
?? ?bool ModifyData(int k, const T & x); ?//将表中第k个元素修改为x，不存在返回false
?? ?int Find(const T &x); ?//返回x在表中的位置，不存在返回0
?? ?LinearList<T>&DeleteByIndex(int k, T & x); ?//删除表中第k个元素，并把它保存在x中，返回修改后的线性表
?? ?LinearList<T>&DeleteByKey(const T & x, T & y); ?//删除表中关键字为x元素，返回删除后的线性表
?? ?void OutPut(ostream&out)const; ? //输出线性表的每个元素
?? ?
};
template <class T>? ? ? ? ? ? ? ? ? ? ? //实现构造函数
LinearList<T>::LinearList(int LLMaxsize)
{
?? ?Maxsize = LLMaxsize;
?? ?element = new T[LLMaxsize];
?? ?length = 0;
}
template <class T>? ? ? ? ? ? ? ? ? ? ?//实现析构函数
LinearList<T>::~LinearList()
{
?? ?delete[] element;
}
template <class T>? ? ? ? ? ? ? ? ? ? ?//实现插入新数据元素
LinearList<T> & LinearList<T>::InSert(int k, const T & x)
{
?? ?if (k<1 || k>length + 1)
?? ??? ?cout << "元素下标越界，添加元素失败" << endl;
?? ?else
?? ??? ?if (length == Maxsize)
?? ??? ??? ?cout << "此表已满，无法添加新元素" << endl;
?? ??? ?else
?? ??? ?{
?? ??? ??? ?for (int i = length; i > k - 1; i--)
?? ??? ??? ??? ?element[i] = element[i - 1];
?? ??? ??? ?element[k - 1] = x;
?? ??? ??? ?length++;
?? ??? ?}
?? ?return *this;
}
template <class T>? ? ? ? ? ? ? ? ? ?//实现判断是否为空表
bool LinearList<T>::IsEmpty() const
{
?? ?return length == 0;
}
template <class T>? ? ? ? ? ? ? ? ? ?//求当前表的长度
int LinearList<T>::GetLength() const
{
?? ?return length ;
}
template <class T>? ? ? ? ? ? ? ? //实现按位置取元素
bool LinearList<T>::GetData(int k,T&x)?
{
?? ?if (k<1 || k>length)
?? ??? ?return false;
?? ?else
?? ?{
?? ??? ?x = element[k - 1];
?? ??? ?return true;
?? ?}
}
template <class T>? ? ? ? ? ? ? ? ? ? //实现按位置修改元素
bool LinearList<T>::ModifyData(int k, const T&x)
{
?? ?if (k<1 || k>length)
?? ??? ?return false;
?? ?else
?? ?{
?? ??? ?element[k - 1] = x;
?? ??? ?return true;
?? ?}
}
template <class T>? ? ? ? ? ? ? ? ? ? ? ?//实现按关键字查找
int LinearList<T>::Find(const T&x)
{
?? ?for (int i = 0; i < length; i++)
?? ??? ?if (element[i] == x)
?? ??? ??? ?return i + 1;
?? ?return 0;
}
template <class T>? ? ? ? ? ? ? ? ? ? ? ? ?//实现按位置删除
LinearList<T> & LinearList<T>::DeleteByIndex(int k, T & x)
{
?? ?if (GetData(k, x))
?? ?{
?? ??? ?for (int i = k - 1; i < length - 1; i++)
?? ??? ??? ?element[i] = element[i + 1];
?? ??? ?length--;
?? ?}
?? ?else
?? ??? ?cout << "元素下标越界，删除失败" << endl;
?? ?return *this;
}
template <class T>? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//实现按关键字删除
LinearList<T> & LinearList<T>::DeleteByKey(const T & x, T&y)
{
?? ?int index = Find(x);
?? ?if (index != 0)
?? ??? ?return DeleteByIndex(index, y);
?? ?else
?? ?{
?? ??? ?cout << "没有此元素，删除失败" << endl;
?? ?}
?? ?return *this;
}
template <class T>? ? ? ? ? ? ? ? ? ? ? ? ? ?//实现数据元素的输出
void LinearList<T>::OutPut(ostream & out) const
{
?? ?for (int i = 0; i < length; i++)
?? ??? ?out << element[i] << endl;
}
//全局函数，实现重载运算符<<
template<class T> ? ??
ostream& operator<<(ostream &out, const LinearList<T> & x)
{
?? ?x.OutPut(out);
?? ?return out;
}
#endif?
2.?主函数
#include<iostream>
using namespace std;
#include "LinearList.h"
int x,getnum;
int main()
{
?? ?LinearList<int> InregerList(10);//创建链表
?? ?InregerList.InSert(1, 10);//插入元素
?? ?InregerList.InSert(1, 20);
?? ?InregerList.InSert(1, 30);
?? ?InregerList.InSert(1, 40);
?? ?InregerList.InSert(1, 50);
?? ?cout << InregerList << endl;//输出链表
?? ?cout << "-------------------" << endl;
?? ?getnum=InregerList.Find(40);//获取数据为40的元素下标
?? ?cout << getnum << endl;
?? ?cout << "-------------------" << endl;
?? ?getnum=InregerList.GetData(1,x);//获取下标为1的数据元素值
?? ?if (getnum == 1)
?? ??? ?cout << x << endl;
?? ?cout << "-------------------" << endl;
?? ?InregerList.DeleteByIndex(3, x);//删除第3个元素
?? ?cout << InregerList << endl;//输出链表
?? ?cout << "-------------------" << endl;
?? ?getnum = InregerList.GetLength();
?? ?cout << getnum << endl;//求当前链表长度
?? ?cout << "-------------------" << endl;
}
图片如图
?