顺序表：线性表

客官°小女子只卖身不卖艺 2022-11-25 10:11 173阅读 0赞

### 线性表 ###

由n（n>=0)个数据元素（也称节点或表元素）组成的有限序列k0,k1,…,kn-1,  
其中，k0为开始结点，无前驱，仅有一个后继；  
kn-1为终端结点，无后继，只有一个前驱；  
其他结点ki(0<i<n-1)有且仅有一个前驱ki-1和一个后继ki+1;n为线性表的长度，n=0时为空表。  
**线性表中的各个数据元素并不要求是同一种数据类型。数据元素相同的线性表又称数组或向量。数据元素不同类型的线性表可通过建立索引表后，转化为数据元素相同的线性表处理。**

#### 线性表的类表示 ####

enum boolean{ FALSE,TRUE}；
    template <class T>
    class LinearList
    { 
    	private:
    		T * data;					//线性表以数组形式存放
    		int Maxsize;					//表空间最大范围
    		int Last;					//表当前结点个数（表长）
    	public:
    		LinearList(int MaxSize=defaultSize);		//构造函数
    		~LinearList(void);				//析构函数
    		boolean ListEmpty(void);			//判断表是否为空
    		boolean ilstFull(void);				//判断表是否已满
    		int Listlength (void)const;			//求表长
    		T GetElem(int i);				//求第i个结点的值
    		int LocateElem(T&x,int i);			//查找表中值为x的结点
    		boolean InsertElem(T&x,int i);			//在表中第i个位置插入新结点
    		boolean DeleteElem(int i);			//删除表中第i个结点
    }；

##### 构造函数LinearList（int sz) #####

template<class T>
    LinearList <T>::LinearList(sz)
    { 
    	//按sz的大小申请一个表空间，生成一个空表，及表的初始化
    	if(sz>0)
    	{ 
    		MaxSize=sz;
    		Last=0;
    		//创建表空间
    		data=new T[MaxSize];
    	}
    }

##### 析构函数~LinearList（） #####

template<class T>
    LinearList <T>::~LinearList(void)
    { 
    	//清除表，释放表空间，即撤销一个表
    	delete []data;
    }

##### 判断线性表是否为空 #####

template<class T>
    boolean LinearList <T>::ListEmpty(void)
    { 
    	//判断表是否为空:空则返回TRUE；否则返回FALSE
    	return (Last<=0)?TRUE:FALSE;

##### 判断线性表是否已满 #####

template<class T>
    boolean LinearList <T>::ListFull(void)
    { 
     	//判断表是否已满:满则返回TRUE；否则返回FALSE
     	return (Last>=MaxSize)?TRUE:FALSE; 
    }

##### 求线性表的长度 #####

template<class T>
    int LinearList <T>::ListLength(void)const
    { 
     	//求表中结点个数，即求表长
     	return Last;
     }

##### 求线性表中第i个结点的值 #####

template<class T>
    int LinearList <T>::GetElem(int i)
    { 
      	//求线性表中第i个结点的值
      	//若第i个节点存在，则返回该节点的值，否则返回NULL
      	return (i<0||i>=Last)?NULL:data[i];
     }

##### 查找线性表中值为x的结点 #####

template<class T>
    int LinearList <T>::LocateElem(T&x)const
    { 
      	//查找表中值为x的结点：若查找成功，则返回该结点的序号；否则返回-1
      	//若表中值为x的结点有多个，找到的是最前面的一个
      	for(int i=0;i<Last;i++)
      	{ 
      		if(data[i]==x)
      		{ 
      			return i;	//查找成功
      		}
      		return -1;		//查找失败
      	}
     }

##### 在线性表中第i个位置插入值为x的结点 #####

template<class T>
    boolean LinearList<T>::InsertElem(T&x,int i)
    { 
    	//在表中第i个位置插入值为x的结点
      	//若插入成功，则返回TRUE,否则返回FALSE
      	//插入位置不合理，插入失败
      	if(i<0||i>Last||Last==MaxSize)
      	{ 
      		return FALSE;
      	}
      	else
      	{ 
      		//后移
      		for(int j=Last;j>i;j--)
      		{ 
      			data[j]=data[j-1];
      		}
      		//插入
      		data[i]=x;
      		//表增长1
      		Last++；
      		return TRUE;
      	}
      }

##### 删除线性表的第i个结点 #####

template<class T>
    boolean LinearList<T>::DeleteElem(int i)
    { 
       //删除表中第i个结点：若删除成功，则返回TRUE,否则返回FALSE
       //第i个结点不存在，删除失败
       if(i<0||i>Last||Last==0)
       { 
           return FALSE;
       }
       else
       { 
           //前移
           for(int j=i;j<Last-1;j++)
           { 
         	   data[j]=data[j+1];
           }
           //表长减1
        	Last--；
           return TRUE;
       }
    }