【数据结构】CH2 线性表&顺序存储结构

发布于：2022-12-08 ⋅ 阅读:(1220) ⋅ 点赞:(0)

目录

一、线性表及其逻辑结构

1.线性表的定义

（1）定义

（2）表示

（3）特性

（4）注

2.线性表的抽象数据类型描述

3.例题

二、线性表的顺序存储结构

1.顺序表

2.顺序表基本运算的实现

（1）建立顺序表

（2）初始化线性表InitList(&L)

（3）销毁线性表DestroyList(&L)

（4）判断线性表是否为空表ListEmpty(L)

（5）求线性表的长度ListLength(L)

（6）输出线性表DispList(L)

（7）求线性表中的某个数据元素值GetElem(L,i,e)

（8）按元素值查找LocateElem(L,e)

（9）插入数据元素ListInsert(&L,i,e)

（10）删除数据元素ListDelete(&L,i,e)

3.例题

一、线性表及其逻辑结构

1.线性表的定义

（1）定义

线性表是指具有相同特性的数据元素的一个有限序列

（2）表示

线性表用二元组表示为L=\left ( D,R \right )，其中：

D={a_{i}|1\leqslant i\leq n,n\geqslant 0,a_{i}为Elem Type类型}        //Elem Type是自定义的类型标识符

R={r}

r={<a_{i},a_{i+1}>|1\leq i\leq n-1}     //a_{i}与a_{i+1}相邻（有序）   

（3）特性

  • 有穷性：一个线性表中的元素个数是有限的
  • 一致性：一个线性表中所有元素的性质相同。从现实的角度看，所有元素具有相同的数据类型
  • 序列性：一个线性表中所有元素之间的相对位置是线性的，即存在唯一的开始元素和终端元素，除此之外，每个元素只有唯一的前驱元素和后继元素。各元素在线性表中的位置只取决于他们的序号，所以在一个线性表中可以存在两个值相同的元素。

（4）注

  • 线性表中，每个数据元素由其逻辑序号唯一确定，设序列中的第i（i表示逻辑序号）个元素为a_{i}(1\leq i\leq n)，则线性表的一般表示为\left ( a_{1},a_{2},\cdots ,a_{i},\cdots ,a_{n} \right )，其中a_{1}又称作表头元素，a_{n}又称为表尾元素。
  • 线性表中的元素呈现线性关系。

2.线性表的抽象数据类型描述

ADT List

{  数据对象：

        D={a_{i}|1\leqslant i\leq n,n\geqslant 0,a_{i}为Elem Type类型}        //Elem Type是自定义的类型标识符     数据关系：

        R={<a_{i},a_{i+1}>|a_{i}、a_{i+1}\epsilon D,i=1,\cdots ,n-1}     //a_{i}与a_{i+1}相邻（有序）

   基本运算：

        InitList(&L)：初始化线性表，构造一个空的线性表L

        DestroyList(&L)：销毁线性表，释放线性表L占用的内存空间

        ListEmpty(L)：判断线性表是否为空表，若L为空表，则返回真，否则返回假

        ListLength(L)：求线性表的长度，返回L中元素的个数

        DispList(L)：输出线性表，当线性表L不为空时顺序显示L中各结点的值域

        GetElem(L,i,&e)：求线性表中某个数据元素值，用e返回L中第i(1\leqslant i\leq n)个元素的值

        LocateElem(L,e)：按元素值查找，返回L中第一个值域与e相等的元素的序号，若这样的元素不存在，则返回值为0

        ListInsert(&L,i,e)：插入数据元素，在L的第i\left ( 1\leqslant i\leq n+1 \right )个位置插入一个新的元素e，L的长度增1

        ListDelete(&L,i,&e)：删除数据元素，删除L的第i\left ( 1\leq i\leq n \right )个元素，并用e返回其值，L的长度减1

}

3.例题

假设有两个集合A和B，分别用两个线性表LA和LB表示，即线性表中的数据元素为集合中的元素怒。利用线性表的基本运算设计一个算法求一个新集合C=A\bigcup B，即将两个集合的并集放在线性表LC中。

void unionList(List LA,List LB,List &LC)
{
	int lena,i;
	ElemType e;
	InitList(LC)	//初始化LC
	for(i=1;i<=ListLength(LA),i++)    //将LA中的所有元素复制到LC中
	{
		GetElem(LA,i,e);    //取LA中的第i个元素赋给e
		ListInsert(LC,i,e);    //将元素e插入到LC中
	}
	lena=ListLength(LA);    //求线性表LA的长度
	for(i=1;i<=ListLength(LB);i++)    //循环处理LB中每一个元素
	{
		GetElem(LB,i,e);    //取LB中的第i个元素赋给e
		if(!LocateElem(LA,e))    //判断e是否在LA中
			ListInsert(LC,++lena,e)    //若e不在LA中，则将其插入到LC中
	}
}

二、线性表的顺序存储结构

1.顺序表

（1）定义

        线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。由于线性表中逻辑上相邻的两个元素在对应的顺序表中他们的存储位置也相邻，所以这种映射成为直接映射。线性表的顺序存储结构简称为顺序表。

 【注】

  • 假设线性表的元素类型为ElemType，则每个元素所占用存储空间的大小（即字节数）为sizeof(ElemType)，整个线性表所占用存储空间的大小为n*sizeof(ElemType)，其中n表示线性表的长度。
  • 在C/C++语言中，借助数组类型来实现顺序表，即数组存放线性表的元素及其逻辑关系，数组的基本类型就是线性表中元素的类型，数组大小（即数组上界-下届+1）要大于等于线性表的长度，否则该数组不能存放对应线性表的所有元素。

  • 数组大小MaxSize一般定义为一个整型变量。如果估计一个线性表不会超过50个元素，则可以把MaxSize定义为50：
#define MaxSize 50
  • 在声明线性表的顺序存储类型时，定义一个data数组来存储线性表中的所有元素，还定义一个整型变量length来存储线性表的实际长度，并采用结构体类型SqList表示如下：
typedef struct
{
	ElemType data[MaxSize];	//存放线性表中的元素
	int length;	//存放线性表的长度
}SqList;	//顺序表类型

2.顺序表基本运算的实现

        为了简单，假设ElemType为int类型，使用以下自定义类型语句：

typedef int ElemType;

【注】顺序表指针L和顺序表Q都可以提供一个顺序表，但前者是通过指针L间接地提供顺序表，其定义方式为SqList *L，后者是直接地提供顺序表，其定义方式为SqList Q。前者引用length域的方式为L->length，后者引用length域的方式为Q.length。之所以采用顺序表指针，主要是为了方便顺序表的释放算法设计，并且在函数之间传递顺序表指针时会节省形参分配的空间。

（1）建立顺序表

这里介绍整体创建顺序表，即由数组元素a[0..n-1]创建顺序表L。其方法是将数组a中的每个元素依次放入到顺序表中，并将n赋给顺序表的长度域。算法如下：

void CreatList(SqList *&L,ElemType a[],int n)	//由a中的n个元素建立顺序表
{
	int i=0,k=0;	//k表示L中元素个数，初始值为0
	L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
	while(i>n)	//i扫描数组a
	{
		L->data[i]=a[i];	//将元素a[i]存放到L中
		k++;j++;
	}
	L->length=k;	//设置L的长度为k
}

（2）初始化线性表InitList(&L)

        构造一个空的线性表，实际上只需要分配线性表的存储空间并将length域设置为0即可。（此算法时间复杂度为O(1)）

void InitList(SqList *&L)
{
	L=(SqList *)malloc(sizeof(SqList))	//分配存放线性表的空间
	L->length=0;	//置空线性表的长度为0
}

（3）销毁线性表DestroyList(&L)

        该运算的功能是释放线性表L占用的内存空间。(O(1))

void DestroyList(SqList *&L)
{
	free(L);	//释放L所指的顺序表空间
}

（4）判断线性表是否为空表ListEmpty(L)

        该运算返回一个布尔值表示L是否为空表。若L为空表，则返回true，否则返回false。(O(1))

bool ListEmpty(SqList *L)
{
	return(L->length==0);
}

（5）求线性表的长度ListLength(L)

int ListLength(SqList *L)
{
	return(L->length);
}

（6）输出线性表DispList(L)

        该运算依次显示L中各元素的值。(O(n))

void DispList(SqList *L)
{
	for(int i=0;i<L->length;i++)
		print("%d",L->data[i]);
		printf("\n");
}

（7）求线性表中的某个数据元素值GetElem(L,i,e)

bool GetElem(SqList *L,ElemType &e)
{
	if(i<1||i>L->length)
		return false;
	e=L->data[i-1];
	return true;
}

（8）按元素值查找LocateElem(L,e)

int LocateElem(SqList *L,ElemType e)
{
	int i=0;
	while(i<L->length&&L->data[i]!=e)
		i++;
	if(i>=L->length)	//未找到时返回0
		return 0;
	else
	return i+1;	//返回其逻辑序号
}

（9）插入数据元素ListInsert(&L,i,e)

bool ListInsert(SqList *&L,int i,ElemType e)
{
	int j;
	if(i<1||i>L->length+1)	//i>=1&&i<=n+1时符合条件
		return false;
	i--;
	for(j=L->length;j>i;i--)
		L->data[j]=L->data[j-1];
	L-<data[i]=e;
	L->length++;
	return true;
}

（10）删除数据元素ListDelete(&L,i,e)

bool ListDelete(SqList *&L,int i,ElemType &e)
{
	int j;
	if(i<1||i>L->length)
		return false;
	i--;
	for(j=i;i<L->length-1;j++)
		L->data[j]=L->data[j+1];
	L->length--;
	return true;
}

3.例题

  • 假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x的元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
//算法一
void delnode1(SqList *&L,ElemType x)
{
	int k=0,i;
	for(i=0;i<L->length;i++)
		if(L->data[i]!=x)
		{
			L->data[k]=L->data[i];
			k++;
		}
	L->length=k;
}

//算法二
void delnode2(SqList *&L,ElemType x)
{
	int k=0,i=0;
	while(i<L->length)
	{
		if(L->data[i]!=x)
			k++;
		else
			L->data[i-k]=L->data[i];
		i++;
	}
	L->length-=k
}
  • 有一个顺序表L，假设元素类型ElemType为整型，设计一个尽可能高效的算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该基准的前面，将所有大于它的元素移到该基准的后面。
//算法一
int partition1(SqList *&L)
{
	int i=0,j=L->length-1;
	ElemType pivot=L->data[0];
	while(i<j)
	{
		while(i<j&&L->data[j]>pivot)
			j--;
		while(i<j&&L->data[i]<=pivot)
			i++;
		if(i<j)
			swap(L->data[i],L->data[j]);
	}
	swap(L->data[0],L->data[i]);
}

//算法二
void partition2(SqList *&L)
{
	int i=0,j=L->length-1;
	ElemType pivot=L->data[0];
	while(i<j)
	{
		while(j>i&&L->data[j]>pivot)
			j--;
		L->data[i]=L->data[j];
		while(i<j&&L->data[j]<=pivot)
			i++;
		L->data[j]=L=data[i];
	}
	L->data[i]=pivot;
}
  • 有一个顺序表L，假设元素类型ElemType为整型，设计一个尽可能高效的算法，将所有奇数移动到偶数的前面。
//算法一
void move1(SqList *&L)
{
	int i=0,j=L->length-1;
	while(i<j)
	{
		while(i<j&&L->data[j]%2==0)	//从右向左扫描，找一个奇数元素
			j--;
		while(i<j&&L->data[i]%2==1)	//从左向右扫描，找一个偶数元素
			i++;
		if(i<j)	
			swap(L->data[i],L->data[j]);
	}
}

//算法二
void move2(SqList *&L)
{
	int i=-1,j;
	for(j=0;j<=L->length-1;j++)
	{
		if(L->data[j]%2==1)	//j指向奇数时
		{
			i++;	//奇数区间个数增1
			if(i!=j)	//若i不为j，将L->data[i]和L->data[j]交换
				swap(L->data[i],L->data[j]);
		}
	}
}

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布