1、线性表的本质和操作

线性表的表现形式主要有以下几个方面

• 零个或多个数据元素组成的集合
• 数据元素在位置上是有序排列的
• 数据元素的个数是有限的
• 数据元素的类型必须相同

线性表的抽象定义是具有相同的n(n>=0)个数据元素的优先序列(a0,a1…an)

2、线性表的性质

a0为线性表的i的一个元素，只有一个后继

an-1为线性表的最后一个元素，只有一个前驱

除去这两个元素外的其他元素ai既有前前驱，又有后继

直接支持逐项访问和顺序存取

本文福利，莬费领取Qt开发学习资料包、技术视频，内容包括（C++语言基础，Qt编程入门，QT信号与槽机制，QT界面开发-图像绘制，QT网络，QT数据库编程，QT项目实战，QSS，OpenCV，Quick模块，面试题等等）↓↓↓↓↓↓见下面↓↓文章底部点击莬费领取↓↓

3、线性表的一些常用操作

1. 将元素插入线性表
2. 将元素从线性表中删除
3. 获取目标位置处元素的值
4. 设置目标位置处元素的值
5. 获取线性表的长度
6. 清空线性表

template <typename T>
class List :public Object
{//Object为顶层父类
  protected:
     List(const List&);
     List& operator=(const List&);//避免赋值操作
	public:
		List(){};
		virtual bool insert(int i,const T&e)=0;//插入
		virtual bool remove(int i)=0;//删除
		virtual bool set(int i,const T&e)=0//设置值;
		virtual bool get(int i,const T&e)=0;//获取值
		virtual int length()const=0;//获取长度
		virtual void clear()=0;//清空操作
}

4、线性表的顺序存储结构的实现

思路：可以用一维数组来实现顺序存储结构

存储空间 T array*

当前的长度 int length

a.顺序存储结构的元素插入操作

• 判断目位置是否合法
• 将目标位置之后的所有元素后移一个位置
• 将新元素插入目标位置
• 线性表的长度+1

简单的图示

代码的实现部分

inset (int i,const T&e)
{
	bool ret=((0<=i)&&(i<length));
	ret=ret&&((length+1)<=capacity());//对位置进行判断是否合法
	
	if(ret)
	{
		for(int p=length-1;p>i;p--)
		{
			array[p+1]=arrray[p];//将目标位置后的元素后移一位
		}
		array[i]=e;//将元素插入
		length++;//线性表长度加1
	}
	return ret;
}

b.顺序存储结构的元素删除操作

• 对位置进行判断是否合法
• 将目标位置后的所有元素前移一个位置
• 线性表的长度减1

实现代码如下

简单的图示

remove(int i,const T&e)
{
	bool ret=((o<=i)&&(i<=length));
	ret=ret&&((length+1)<=capacity());//对位置进行判断是否合法
	
	if(ret)
	{
		for(int p=i;p<length-1;p++)//在删除处进行遍历
		{
			array[p]=array[p+1];//将元素前移一个位置
		}
		length--;//线性表的长度减1
    }
		return ret;
}

c.元素的设置以及获取

• 判断目标位置是否合法
• 将目标位置作为数组下标对元素进行操作

实现代码如下

set(int i,const T&e)
{
	bool ret=((0<=i)&&(i<=length))
	
	if(ret)
	{
		array[i]=e;
	}
	return ret;
}

get(int  i,T&e)const
{
	bool ret=((0<=i)&&(i<=length))
	
	if(ret)
	{
		e=array[i];
	}
	return ret;
}

d.其他的操作(清除及获取长度)

实现代码如下

        int length()const
        {
            return length;
        }

        void clear()
        {
            length=0;
        }

完整的代码如下

include "List"
include "Object"

namespace MyLib
{
	template<typename T>
	class SeqList :public List<T>
	{
		protected:
			T* array;
			int length;
		public:
			bool insert(int i,const T&e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            ret=ret&&(m_length<capacity());
            if(ret)
            {
                for(int p=m_length-1;p>=i;p--)
                {
                    m_array[p+1]=m_array[p];
                }
                m_array[i]=e;
                m_length++;
            }

            return ret;
        }

        bool insert(const T&e)//在尾部插入数据
        {
            return insert(m_length,e);
        }

        /*删除操作
         1.判断目标是否合法
         2.将目标位置后的所有元素前移一个位置
         3.线性表长度减1
        */
        bool remove(int i)
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                for(int p=i;p<m_length;p++)
                {
                    m_array[p]=m_array[p+1];
                }
                m_length--;
            }
            return ret;
        }

        bool set(int i,const T&e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                m_array[i]=e;
            }
            return ret;
        }

        bool get(int i,T&e) const
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                e=m_array[i];
            }
            return ret;
        }

        int find(const T&e)const
        {
            int ret=-1;

            for(int i=0;i<m_length;i++)
            {
                if(m_array[i]=e)
                {
                    ret=i;
                    break;
                }
            }

            return ret;
        }

        int length()const
        {
            return m_length;
        }

        void clear()
        {
            m_length=0;
        }

        //数组的访问
        T& operator[](int i)//数组操作符的重载
        {
           if((0<=i)&&(i<=m_length))
           {
               return m_array[i];
           }
           else
           {
               THROW_EXCEPTION(indexOutOfBoundsException,"Parameter i is invaild...");//i不合法，越界操作异常
           }
        }

        T operator [](int i)const
        {
            //去除当前对象的const属性
            return (const_cast<SeqList<T>&>(*this))[i];
        }

        virtual int capacity()const=0;//纯虚h函数，由子类重写
	};
}

本文福利，莬费领取Qt开发学习资料包、技术视频，内容包括（C++语言基础，Qt编程入门，QT信号与槽机制，QT界面开发-图像绘制，QT网络，QT数据库编程，QT项目实战，QSS，OpenCV，Quick模块，面试题等等）↓↓↓↓↓↓见下面↓↓文章底部点击莬费领取↓↓