Skip to main content

第3章 线性表

Archived University Note

This content is from my university archives and may not be reliable or up-to-date.

3.1 线性表的类型定义​

3.1.1 线性表的逻辑定义​

由n个数据元素（结点）组成的有限序列，数据元素可以由若干个数据项组成

从线性表的定义可以看出他的逻辑特征，即对于一个非空的线性表有如下特征：

  1. 有且仅有一个称为开始元素的a1，他没有直接前驱元素，仅有一个直接后继元素a2
  2. 有且仅有一个终端元素an，他没有后继元素
  3. 其余元素ai([2,n-1])称为内部元素，他们都有且仅有一个直接前驱和一个直接后继

线性表中元素之间的逻辑关系就是上述的相邻关系，又称为线性关系，因此线性表是一种典型的线性结构

3.1.2 线性表的抽象数据类型​

可以用一个抽象数据类型(Abstract Data Type, ADT)来描述线性表。

ADT LinearList{
    数据对象及关系
    0个或多个元素的有序集合
    基本运算
    CreateList(),创建一个空的线性表；
    Destory(),删除表；
    ListEmpty(),如果表为空则返回true，否则返回false；
    ListLength(),返回线性表中元素个数,表长；
    GetElem(i,x),取表中第i个元素，若 1<=i<=Listlength(),则将第i个元素值存入x中，否则返回false；
    LocateElem(x),在表中查找第一个值为x的元素，若存在，则返回其在表中的位置，否则返回0；
    InsertElem(i,x),在表L的第i个结点之前插入一个值为x的新元素，表长加1，返回修改后的线性表；
    DeleteElem(i,x),删除表中第i个元素，并将其保存到x中，表长减1，返回修改后的线性表。
} //ADT LinearList

3.2 线性表的顺序存储及基本运算​

3.2.1 线性表的顺序存储​

  • 将线性表的数据元素按照其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表简称为顺序表
  • 线性表第i个元素存储位置：LOC(ai)=LOC(a1)+(i-1)×d （基地址）
  • 线性表的机内表示称为线性表的顺序存储结构，只要确定了线性表的起始位置，线性表中任意一个结点都可随机存取，顺序表是一种随机存取结构

顺序表C++类定义：

//list.h
template<class T>
class SeqList{
    public:
		friend void Converts(SeqList<T> &L);    //线性表逆置友元函数
		SeqList(int MaxListSize=100);			//构造函数，默认表长为100
		~SeqList(){delete[] data;}				//析构函数
		bool ListEmpty(){return length == 0;}
		int ListLength(){return length;}
		bool GetElem(int i,T x);				//第i个元素存入x中
		int LocateElem(T x);					//返回x所在的位置
		void InsertElem(int i,T x);				//在第i个元素之前插入x
		void DeleteElem(int i,T &x);			//删除第i个元素，将值存到x
		void PrintList();					   //输出表的内容

	private:
		int length;
		int MaxSize;
		T *data;

};

3.2.2 顺序表上基本运算的实现​

1. 构造函数的定义

template<class T>
SeqList<T>::SeqList(int MaxListSize)
{
	MaxSize=MaxListSize;
	data=new T[MaxSize]; 	//申请一块动态连续的内存区
	length=0;
}

2. 取表中第i个元素 O(1)

template<class T>
bool SeqList<T>::GetElem(int i,T &x)
{	//取表中第i个元素值存入x中
	if(i<1||i>length)
		return false;
	x=data[i-1];
	return true;
}

3. 查找值为x的元素 O(length)

template <class T>
int SeqList<T>::LocateElem(T x)
{	//返回x在表中的位置，如果x不在表中，则返回0
	for(int i=0;i<length;i++)
		if(data[i]==x)
			return ++i;
	return 0;
}

4. 插入运算

template<class T>
void SeqList<T>::InsertElem(int i,T x)
{	//在表第i个元素之前插入x
	if(i<1||i>length+1){
		cout<<"position error"<<endl;
		return;				//给定位置不合理，退出程序
	}
	for (int j=length - 1 ; j>=i-1;j--)
		data[j+1]=data[j]; // 从最后一个元素开始逐一后移
	data[i-1]=x;	//插入新元素x
	length++;	//实际表加长1
}

5. 删除运算 O(n)

template <class T>
void SeqList<T>::DeleteElem(int i,T &x)
{	//在顺序表中删除第i个元素，并返回被删除元素
	if(i<1||i>length){
		cout<<"position error"<<endl;
		return;	 	//给定位置不合理，退出程序
	}
	x=data[i-1];   //返回被删除的元素
	for(int j=1;j<length;j++)
		data[j-1]=data[j];
	length--;		//实际表长减1

}

6. 顺序表的输出

template<class T>
void SeqList<T>::PrintList()
{
	for(int i=0;i<length;i++)
		cout<<data[i]<<" ";
	cout<<endl;
}

7. 顺序表的逆置 O(n)

template<class T>
void Converts(SeqList<T> &L)
{
	int x;
	int i,k;
	k=length/2;
	for(i=0;i<k;i++){
		x=L.data[i];
		L.data[i]=L.data[L.length-i-1];
		L.data[L.length-i-1] = x;
	}
}