数据结构----顺序表

简介

线性表是一种最基本、最简单的数据结构，数据元素之间仅具有单一的前驱和后继关系。线性表是线性结构的典型代表。
线性表的两种存储方式：

顺序存储
链接存储

下面我们将分别对这两种方式进行学习并用代码实现。

顺序表

顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中，在计算机中一般采用数组进行存储(因为数组元素存放在一组地址连续的存储单元中)

代码实现：

#include <iostream>
#define MAX_SIZE 100

using namespace std;

/*
* @Author: zbl
* @Date: 2019-10-31 11:29:23
* @Last Modified by: zbl
* @Last Modified time: 2019-10-31 11:33:51
*/


template <class T>
class SeqList
{
   public:
       SeqList(T a[],int n);
       SeqList();
       virtual ~SeqList();
       int getLength();
       T get(int i);
       int find(T x);
       void insert(int i,T x);
       T remove(int i);
       bool isEmpty();
       void dispaly();

   private:
       T data[MAX_SIZE];
       int length;
};

//构造函数
template <class T>
SeqList<T>::SeqList(T a[], int n)
{
   cout<<MAX_SIZE<<endl;
   if(n > MAX_SIZE)
       throw "参数非法!";

   //初始化
   for (int i = 0; i < n; ++i)
   {
       data[i] = a[i];
   }
   length = n;
}

//无参构造函数
template <class T>
SeqList<T>::SeqList(){
   length = 0;
   //初始化
   memset(data, 1, sizeof(data));
}


//析构函数
template <class T>
SeqList<T>::~SeqList()
{
   //dtor
}

//获取长度
template <class T>
int SeqList<T>::getLength(){
   return length;
}

//获取i位置的元素
template <class T>
T SeqList<T>::get(int i){
   if(i < 0)
       throw "下溢";
   else if(i > length - 1)
       throw "上溢";
   else
       return data[i];
}

//查找x元素的位置
template <class T>
int SeqList<T>::find(T x){
   for (int i = 0; i < length; ++i)
   {
       if(x == data[i])
           return i;
   }
   //未找到
   return -1;
}

//在i位置插入元素x
template <class T>
void SeqList<T>::insert(int i ,T x){
   if(length == MAX_SIZE)
       throw "线性表已满!";

   if(i<0||i>length)
       throw "参数非法!";

   //头插
   if(i==0){
       for (int j = length; j > 0; --j)
       {
           data[j] = data[j-1];
       }
       data[i] = x;
   }

   //尾插
   else if(i==length){
       data[i] = x;
   }

   //中间
   else
   {
       for (int j = length; j > i; --j)
       {
           data[j] = data[j - 1];
       }
       data[i] = x;
   }
   length++;

}

//删除位置为i的元素
template <class T>
T SeqList<T>::remove(int i){
   if(i<0||i>length-1)
       throw "参数非法!";
   T x = data[i];
   for (int j = i; i < length; ++i)
   {
       data[j] = data[j + 1];
   }
   length--;
   return x;
}

//判断顺序表是否为空
template <class T>
bool SeqList<T>::isEmpty()
{
   return length==0?true:false;
}

//打印顺序表
template <class T>
void SeqList<T>::dispaly(){
   for (int i = 0; i < length; ++i)
   {
       cout<<data[i]<<" ";
   }
   cout<<endl;

}


int main()
{
   int a[5] = {2,1,22,33,12};
   //创建线性表
   SeqList<int> seqlist(a,5);
   cout<<"第一次输出线性表："<<endl;
   seqlist.dispaly();

   cout<<"查找元素22的位置："<<seqlist.find(22)<<endl;

   cout<<"插入元素5，头插"<<endl;
   seqlist.insert(0,5);
   seqlist.dispaly();

   cout<<"插入元素25，尾插"<<endl;
   seqlist.insert(6,25);
   seqlist.dispaly();

   cout<<"插入元素100"<<endl;
   seqlist.insert(3,100);
   seqlist.dispaly();

   cout<<"删除位置为3的元素"<<seqlist.remove(3)<<endl;
   cout<<"线性表长度："<<seqlist.getLength()<<endl;

   return 0;
}

运行结果：

由于开始我是将SeqList类的定义和实现分开在2个文件中写的，导致在编译时main函数报错，原因在于在使用模板类时不能将类的定义与实现分开写，这样在使用时编译器找不到类中函数的实现，报错信息如下：

undefined reference to `SeqList<int>::SeqList(int*, int)'
undefined reference to `SeqList<int>::xxx
undefined reference to `SeqList<int>::xxx
undefined reference to `SeqList<int>::xxx
undefined reference to `SeqList<int>::xxx
undefined reference to `SeqList<int>::xxx