顺序表的基本操作（c++实现）

1. 头文件LinearList#ifndef _LINEARLIST_H_#define _LINEARLIST_H_#include<iostream>using namespace std;template<class T>//T为数据类型class LinearList//模板名{private:int length;//当前数组元素个数int Maxsize;..

dingding_coding

843人浏览 · 2021-11-17 10:29:06

dingding_coding · 2021-11-17 10:29:06 发布

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;
}