线性表

第一节 线性表定义

文字语言描述线性表：
像排队一样，具有线一样性质的结构
线性表（List）：由多个数据元素组成的有限序列
数学语言描述线性表：
若将线性表记为(a1,…,ai-1,ai,ai+1,…an) ，则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。

图形语言描述

线性表特点：

• 是一个序列，先来后到；
• 元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素有且仅有一个前驱和后继；
• 线性表强调有限；
• 当元素个数n（n>=0）定义为线性表长度，当n=0时，称为空表；

第二节 抽象数据类型

介绍抽象数据类型之前先介绍数据类型的定义
数据类型：指一组性质相同的值得集合及定义在此集合上的一些操作的总称；
在c中数据类型分为两类：

• 原子类型：不可再分的数据类型，比如 整型，字符型。
• 结构类型：由若干个类型组合而成，是可以再分。比如 整形数组是由若干个整型数据组合而成。

抽象：抽取出事物具有的普遍性的本质。
对已有的数据类型进行抽象就有了抽象数据类型

抽象数据类型（Abstract Data Type , ADT）：是指一个数学模型及定义在该模型上的一组操作

描述抽象数据类型的标准格式

ADT （抽象数据类型名）
Data （数据元素之间逻辑关系的定义）
Operation （操作）
endADT

线性表的抽象数据类型定义

ADT 线性表（List）
Data
** 线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。其中，出第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。**
Operation
InitList（*L）：初始化操作，建立一个空的线性表L。
ListEmpty（L）：判断线性表是否为空表，若线性表为空，返回true，否则返回false。
CleratList（*L）：将线性表清空。
GetElem（L，i，*e）：将线性表L中的第i个位置元素值返回给e。
LocateElem（L，e）：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在在表中序号表示成功；否则返回0表示失败；
ListInsert（*L，i，e）：在线性表L在线性表L中第i个位置插入新元素e。
ListDelete（*L，i，*e）：删除线性表L中第i个元素位置，并用e返回其值。
ListLength(L)：返回线性表L的元素个数。
endADT

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂的操作，完全可以用这些基本操作的组合来实现。

小例子：实现 集合A∪集合B

思路：

循环遍历集合B中每个元素，判断当前元素是否存在A中，若不存在则插入A即可。

综上分析，我们需要用到的操作有：

• ListLength(L)
• GetElem（L，i，*e）
• LocateElem（L，e）
• ListInsert（*L，i，e）

// La代表集合A  Lb代表集合B
void unionL(List *La,lisr Lb)
{
	//因为要返回集合A所以传入指针类型
	int La_len,Lb_len,i;
	Elempty e;
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);
	for(i=1 ; i <= Lb_len; i++)
	{
		GetElem(Lb,i,&e);
		if( !LocateElem(*La,e) )
		{
			ListInsert(La, ++La_len, e);
		}	
	}
}

线性表的插入

插入思路

• 如果插入位置不合理抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加数组长度；
• 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；
• 将要插入的元素填入位置i处；
• 线性表长+1；

实现代码 ListInsert.c

// 初始条件：顺序线性表L已存在；
// 操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1；
Status ListInsert(SqList *L,int i, ElemType e)
{
	int k;
	if( L->length == MAXSIZE) //判断顺序表是否满了
	{
		return ERROR;
	}
	if( i<1 || i>L->length+1) //判断i是否越界
	{
		return ERROR;
	}
	if( i <= L->length)
	{
		//将i之后的数据位置往后挪一位
		for( k=L->length-1; k>=i-1;k--)
		{
			L->data[k+1] = L->data[k];
		}
	}
	L->data[i-1] = e; //新元素插入
	L->length++;
	
	return OK;
}

 

线性表的删除

线性表删除思路

• 如果删除位置不合理，抛出异常;
• 取出删除元素;
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置;
• 表长-1；

实现代码 ListDelete.c

// 初始条件： 顺序线性表L已存在
// 操作结果： 删除L的第i个数据元素，并用e返回其值，L的长度-1
Status ListDelete (SqList *L , int i,Elempty *e)
{
	int k;
	
	if(L->length == 0) //判断表是否为空表
	{
		return ERROR;
	}
	if(i < 1 || i > L->length )
	{
		return ERROR;
	}
	*e = L->data[i-1];
	if( i < L->length )
	{
		for( k=1 ; k<L->length;k++)
		{
			L->data[k-1] = l->data[k];
		}
	}
	L->length--;

	return OK;
}

最后

以上就是缓慢早晨为你收集整理的线性表 （一） 线性表定义与线性表插入与删除线性表线性表的插入线性表的删除的全部内容，希望文章能够帮你解决线性表 （一） 线性表定义与线性表插入与删除线性表线性表的插入线性表的删除所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。