数据结构及算法之线性表_创建一个线性表,为什么需要判断有没有创建-CSDN博客

本文链接：https://blog.csdn.net/clky00/article/details/124751812

本文详细介绍了线性表的逻辑结构及其两种主要的存储方式——顺序存储和链式存储。顺序存储使用数组实现，操作包括初始化、销毁、清空、判断空表、获取长度、获取元素、定位元素、插入和删除。链式存储包括单链表、循环链表和双向链表，每种结构都有相应的插入和删除操作，其中双向链表支持双向遍历。此外，还讨论了不同存储结构之间的比较。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

线性表

一、线性结构的定义

有且仅有一个开始和一个终端节点，并且所有节点最多只有一个直接前驱和一个直接后继。

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

1.抽象数据类型

本文所有代码均为类C代码。

ADT List{
数据对象:D = { a_i | a_i ϵ ElemSet, i = 1, 2, …, n, n>= 0 }
数据关系:R1 = { < a_i-1,a_i > | a_i-1,a_i ϵ D,i =2,… n }
基本操作：
InitList( &L )
操作结果：构造一个新的线性表L。
DestroyList( &L )
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList( &L )
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListEmpty( &L )
初始条件: 线性表L已存在。
操作结果：若L为空表，则返回TRUE,否则返回FALSE。
ListLength( &L )
初始条件: 线性表L已存在。
操作结果：返回L中数据元素的个数。
GetElem( L, i，&e )
初始条件: 线性表L已存在，1<= i <= ListLength( L )。
操作结果：用e返回L中第i个数据元素的值。
LocateElem( L, e，compare() )
初始条件: 线性表L已存在,compare()是数据元素判定函数。
操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。若这样的元素不存在，则返回值为0。
PriorElem( L, cur_e, &pre_e )
初始条件: 线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem( L, cur_e, &next_e )
初始条件: 线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
ListInsert( &L, i, e )
初始条件: 线性表L已存在,1<= i <= ListLength( L )+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete( &L, i, &e )
初始条件: 线性表L已存在且非空,1<= i <= ListLength( L )。
操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1。
ListTraverse( L, visit() )
初始条件: 线性表L已存在。
操作结果: 依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT List

以上这些所提及的运算是逻辑结构上定义的运算，只要给出这些运算的功能是“做什么”，至于“如何做”等实现细节，只有待确定了存储结构之后才考虑。

2.线性表的顺序存储结构

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。由于，高级语言中的数组类型也有随机存取的特性，因此，通常用数组来描述数据结构中的顺序存储结构。

//函数结果状态代码
#define TRUE            1
#define FALSE           0
#define OK              1
#define ERROR           0
#define INFEASIBLE     -1
#define OVERFLOW       -2

//Status是函数的类型，其值是函数结果状态代码
typedef int  Status;
typedef char ElemType;

顺序线性表类型：

typedef struct {
	ElemType   *elem;
	int       length;
}SqList;

基本操作的实现算法：

Status
InitList( SqList &L ){                      //构造一个空的顺序表
	L.elem = new ElemType[ MAXSIZE ];       //为顺序表分配空间
	if( ! L.elem ) 
	exit( OVERFLOW );                       //存储分配失败
	L.length = 0;                           //空表长度为0
	return OK ;
}

void
DestroyList( &L ){
	if( L.elem )
	delete L.elem;                          //释放存储空间
}

void
ClearList( SqList &L ){
	if( L.elem )
	L.length = 0;                          //将线性表的长度置为0
}

Status
ListEmpty( SqList L ){
	if( L.elem )
	if( L.length == 0 )                  //如果为空表，返回TRUE
		return TRUE;                     
	else 
		return FALSE;	
}

Status
ListLength( SqList L ){
	if( L.elem )
	return L.length;                 //返回线性表L的长度
}

Status
GetElem( SqList L, int i，ElemType &e ){
	if( i < 1 || i > L.length )     //判断i的值是否合理，若不合理，返回ERROR
	return ERROR ;
	e = L.elem[ i - 1 ];             // 第i-1的单元存储着第i个数据
	return OK;
}

Status
LocateElem( SqList L, ElemType e){   //在线性表L中查找值为e的数据元素，返回其序号(第几个元素)
	for( i = 0; i < L.length; i++ )
		if( L.elem[ i ] == e )
		return i+1;                 //查找成功，返回序号
	return 0;                       //查找失败，返回0
}

Status
ListInsert( SqList &L, int i, ElemType e ){
	if( i < 1 || i > L.length + 1 )
	return ERROR;                           //i值不合法
	if( L.length == MAXSIZE )
	return ERROR;                           //当前存储空间已满
	for( j = L.length - 1 ;j >= i -1; j-- )
		L.elem[ j + 1 ] = L.elem[ j ];     //插入位置及之后的元素后移
	L.elem[ i - 1 ] = e;                   //将新元素e放入第i个位置
	L.length++;                            //表长增1
	return OK;
}

Status
ListDelete( SqList &L, int i){
	if( i < 1 || i > L.length )
	return ERROR;                          //i值不合法
	for( j = i; j <= L.length; j++)
		L.elem[ j - 1 ] = L.elem[ j ];     //被删除元素之后的元素后移
	L.length--;                            //表长减1
	return OK;
}

3.线性表的链式存储结构

(1)单链表

结点只有一个指针域的链表称为单链表，单链表是顺序存取的存储结构。

单链表类型：

typedef struct Lnode{             //声明结点的类型和指向结点的指针类型
	ElemType       data;          //结点的数据域
	struct Lnode  *next;          // 结点的指针域
}LNode,*LinkList;                 //LinkList为指向结构体Lnode的指针类型

头插法建立带头结点的单链表：
图片:
在这里插入图片描述

void
CreateList_H( LinkList &L, int n ){
	L = new LNode;
	L->next = NULL;               //建立一个带头结点的单链表
	for( i = n; i > 0; --i )
	{
		p = new LNode;           //生成新结点p=(LNode *)malloc(sizeof(LNode))
		cin >> p->data;          //输入元素值scanf(&p->data)
		p->next = L->next;       //插入到表头
		L->next = p;
    }
}

尾插法建立带头结点的单链表：

void
CreateList_R( LinkList &L, int n ){
	L = new LNode;
	L->next = NULL;               //建立一个带头结点的单链表
	r = L;                        //尾指针r指向头结点
	for( i = 0; i < n; ++i )
	{
		p = new LNode;           //生成新结点p=(LNode *)malloc(sizeof(LNode))
		cin >> p->data;          //输入元素值scanf(&p->data)
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

带头结点的单链表基本操作的实现算法：

Status
InitList_L( LinkList &L ){
	L = new LNode;
	L->next = NULL;               //建立一个带头结点的单链表
	return OK;
}

void
DestroyList_L( LinkList &L ){           //销毁单链表
	LinkList p;
	while( L ){
		p = L;
		L = L->next;
		delete p;
	}
	return OK;
}

void
ClearList_L( LinkList &L ){          //将L置为空表
	LinkList p,q;
	p = L->next;                    //p指向首元结点
	while( p ){                       //没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;                 //头指针指针域为空
	return OK;
}

Status
ListEmpty_L( LinkList L ){      //若L为空表，则返回1，否则返回0
	if( L->next )
		return 0;
	else
		return 1;
}

Status
ListLength_L( LinkList L ){      //返回L中数据元素个数
	LinkList p;
	p = L->next;                    //p指向首元结点
	i = 0;
	while( p ){
		i++;
		p = p->next;
	}
	return i;
}

Status
GetElem_L( LinkList L, int i，ElemType &e ){    //获取L中第i个元素的值，通过e返回
	p = L->next;                    //p指向首元结点
	j = 1;
	while( p && j < i ){            //向后扫描，指到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if( !p || j > i ){               //第i个元素不存在
		return ERROR;
	}else
	{
		e = p->data;                   //取第i个元素
		return OK;
	}
}

LinkList
LocateElem_L( LinkList L, ElemType e){
	//在线性表L中查找值为e的数据元素，找到，则返回值为e的数据元素地址，查找失败则返回NULL
	p = L->next;                    //p指向首元结点
	while( p && p->dtat != e ){
		p = p->next;
	}
	return p;
}

Status
LocateElem_L( LinkList L, ElemType e){
	//在线性表L中查找值为e的位置序号，找到，返回e的位置序号，否则，返回0
	p = L->next;                    //p指向首元结点
	j = 1;
	while( p && p->dtat != e ){
		p = p->next;
		j++；
	}
	if( p )
		return j;
	else
		return 0;
}

Status
ListInsert_L( LinkList &L, int i, ElemType e ){
	p = L;j = 0;            //p指向头结点
	while( p && j < i - 1 ){            //向后扫描，指到p指向第i-1个元素或p为空
		p = p->next;
		++j;
	}
	if( !p || j > i - 1 ){               //第i个元素不存在
		return ERROR;
	}else
	{
		s = new LNode;                  //生成新结点
		s->data = e;                    //将结点s的数据域置为e
		s->next = p->next;              //将结点s插入到L中
		p->next = s;
		return OK;
	}
}

Status
ListDelete_L( LinkList &L, int i, ElemType &e){
	//将L中第i个元素删除，并用e保存删除的元素
	p = L;j = 0;            //p指向头结点
	while( p->next && j < i - 1 ){            //向后扫描，指到p指向第i-1个元素或p为空
		p = p->next;
		++j;
	}	
	if( !p->next || j > i - 1 ){               //第i个元素不存在
		return ERROR;
	}else
	{
		q = p->next;                          //临时保存被删除结点的地址以便释放
		p->next = q->next;                    //改变删除结点前驱结点的指针域
		e = q->data;                          //保存删除结点的数据域
		delete q;                             //释放删除结点
		return OK;
	}
}

(2)循环链表

循环链表是另一种形势的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。
循环链表的操作和单链表基本一致，只不过：
循环条件：
p != NULL; p != L;
p->next != NULL; p->next != L;
单链表单循环链表

以下，是两个带尾指针的循环链表的合并：
在这里插入图片描述
如图，将Tb合并在Ta之后：

合并算法：

LinkList
Connect( LinkList Ta, LinkList Tb ){
	//假设Ta，Tb都是非空的单循环链表
	p = Ta->next;                     //p存表头结点
	Ta->next = Tb->next->next;        //Tb表头连接Ta表尾
	delete Tb->next;                  //释放Tb表头结点
	Tb->next = p;                     //修改指针
	return Tb;
}

(3)双向链表

以上，从某个结点出发只能顺指针往后巡查其他结点。若要寻查结点的直接前驱，则需要从表头指针出发。为了克服这种缺点，可利用双向链表( double linked list )。

双向链表的类型：

typedef struct DuLNode{
	ElemType          data;
	struct DuLNode   *prior;
	struct DuLNode   *next;
}DuLNode,*DuLinkList;

双向链表结构的对称性( 设指针p指向某一结点)：
p->prior->next = p = p->next->prior
在双向链表中，有些操作如：ListLength、GetElem和LocateElem等，因仅涉及一个方向的指针，故他们的算法与线性链表相同。但在插入、删除时，则需同时修改两个方向的指针。两者的操作的时间复杂度均为O(n)。

双向链表的插入：
在这里插入图片描述
如上图所示，把s结点插入到双向链表中。

Status
ListInsert_DuL( DuLinkList &L, int i, ElemType e ){
	//在带头结点的双向循环链表L中第i个位置之前插入元素e
	if( !( p = GetElemP_DuL( L, i )))         //在L中确定插入位置的指针
		return ERROR;
		s = new DuLNode;
		s->data = e;	
		s->prior = p->prior;                //  1
		p->prior->next = s;                 //  2
		s->next = p;                        //  3
		p->prior = s;                       //  4
		return OK;	
}

Status
ListDelete_DuL( DuLinkList &L, int i, ElemType &e){
	//删除带头结点的双向循环链表L中的第i个元素，并用e返回
		if( !( p = GetElemP_DuL( L, i )))         //在L中确定插入位置的指针
		return ERROR;
		e = p->data;
		p->prior->next = p->next;
		p->next->prior = p->prior;
		free(p);
		return OK;
}