数据结构Ⅱ线性表

发表于 | 分类于
字数统计: 2.8k

一.线性表

1.定义

线性表（List）：零个或有限个数据类型相同的数据元素的有限序列。

性质：

  • 线性表中的数据元素之间是有顺序的。
  • 线性表中的数据元素个数是有限的。
  • 线性表中的数据元素的类型必须相同。

</br>

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2, ......, an}，每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，
    除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。
Operation
/*该方法用于创建并且返回一个空的线性表*/
List* List_Create();

/*该方法用于销毁一个线性表list*/
void List_Destroy(List* list);

/*该方法用于将一个线性表list中的所有元素清空,使得线性表回到创建时的初始状态*/
void List_Clear(List* list);

/*该方法用于返回一个线性表list中的所有元素个数
*/
int List_Length(List* list);

/*该方法用于向一个线性表list的pos位置处插入新元素node,返回值为1表示插入成功，0表示插入失败*/
int List_Insert(List* list, ListNode* node, int pos);

/*该方法用于获取一个线性表list的pos位置处的元素,返回值为pos位置处的元素，NULL表示获取失败*/
ListNode* List_Get(List* list, int pos);

/*该方法用于删除一个线性表list的pos位置处的元素,返回值为被删除的元素，NULL表示删除失败*/
ListNode* List_Delete(List* list, int pos);

</br>

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

(1).结构分析

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表（a1,a2,……,an）的顺序存储示意图如下：

.

在C中用一维数组来实现顺序存储结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
存储空间的起始位置:数组node
线性表的最大容量:数组长度MAXSIZE
线性表的当前长度:length
*/

/* 存储空间初始分配量 */
#define MAXSIZE 20             
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;          
typedef struct
{
    /* 数组存储数据元素，最大值为MAXSIZE */
    ElemType data[MAXSIZE];    
    /* 线性表当前长度 */
    int length;                
} SeqList;

</br>

(2).重点操作

创建线性表

操作步骤：

  • 创建
  • 分配内存
  • 检验分配情况并把新建完的链表的指针指向结构体地址后的node处
  • 返回表的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//1.创建
TSeqList* ret = NULL;

if(capacity >= 0)
{
    //2.分配内存（结构体+数据表）
    ret = (TSeqList*) malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
}

//3.检验分配是否成功
if(ret != NULL)
{
    ret->capacity = capacity;
    ret->length = 0;
    //新建完的链表的指针指向结构图后的node处
    ret->node = (TSeqListNode*)(ret + sizeof(TSeqList));
}

//返回新建成功的链表
return ret;

</br>

获取元素

操作步骤：

  • 判断线性表是否合法
  • 判断位置是否合法
  • 直接通过数组下标的方式获取元素
1
2
3
4
5
6
7
//1.判断线性表是否合法
//2.判断位置是否合法
if( (List != NULL) && (0 <= pos) && (pos < List->length) )
{
   //3.获取元素
   ret = List->node[pos];
}

</br>

插入元素操作

操作步骤：

  • 判断线性表是否合法
  • 判断插入位置是否合法
  • 把最后一个元素到插入位置的元素后移一个位置
  • 将新元素插入
  • 线性表长度加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//1.判断线性表是否合法
int ret = (List != NULL);
int i = 0;

//2.判断插入位置是否合法
ret = ret && (List->length + 1 <= List->capacity);
ret = ret && (0 <= pos);

if( ret )
{
if( pos >= List->length )
{
		pos = List->length;
}
//3.把最后一个元素到插入位置的元素后移一个位置
for(i=List->length; i>pos; i--)
{
		List->node[i] = List->node[i-1];
}
//4.将新元素插入
List->node[i] = (int)node;
//5.线性表长度加1
List->length++;
}

</br>

删除元素操作

操作步骤：

  • 判断线性表是否合法
  • 判断删除位置是否合法
  • 将元素取出
  • 将删除位置后的元素分别向前移动一个位置
  • 线性表长度减1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char ret = -1;
int i = 0;

//1.判断线性表是否合法
//2.判断删除位置是否合法
if((list != NULL) && (0 <= pos) && (pos<= list->length))
{
		//3.将元素取出
		ret = list->node[pos];
      
		//4.将删除位置后的元素分别向前移动一个位置
		for(int i = pos+1; i < list->length; i++)
		{
				list->node[i-1] = list->node[i];
		}
		
  	//5.线性表长度减1
		list->length--;
}

</br>

(3).顺序存储的优缺点

</br>

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

(1).结构分析

链式存储定义：为了表示每个数据元素与其直接后继的元素之间的逻辑关系，每个元素除了存储本身的信息之外，还需要存储指示其直接后继的消息。

链式存储逻辑结构：n个结点链接成一个链式线性表的结构叫做链表，当每个结点中只包含一个指针域时，叫做单链表。

链表的基本概念:

  • 表头结点：链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息。(本身不是数据元素)
  • 数据结点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息。
  • 尾结点：链表中的最后一个数据结点，其下一元素指针为空，表示无后继。

C语言用结构体来定义链表中的结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef _tag_LinkListNode LinkListNode;

//结点指针域定义
struct _tag_LinkListNode
{
  LinkListNode* next;
};

//头结点定义
typedef struct _tag_LinkList
{
  LinkListNode header;
  int length;
}TLinkList;

//数据元素定义示例
struct Value
{
  LinkListNode header;
  int value;
};

</br>

(2).重点操作

获取第pos个元素操作

操作步骤：

  • 判断线性表是否合法
  • 判断位置是否合法
  • 由表头开始通过next指针移动pos次后，当前元素的next指针即指向要获取的元素
1
2
3
4
5
6
7
8
9
10
11
12
//1.判断线性表是否合法
//2.判断位置是否合法
if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
{
    LinkListNode* current = (LinkListNode*)sList;
    //由表头开始通过next指针移动pos次后，当前元素的next指针即指向要获取的元素
    for(int i=0; i<pos; i++)
    {
        current = current->next;
    }
    ret = current->next;
}

</br>

插入元素操作

操作步骤：

  • 判断线性表是否合法
  • 判断插入位置是否合法
  • 由表头开始通过next指针移动pos次后，当前元素的next指针即指向要插入的位置
  • 将新元素插入
  • 线性表长度加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//1.判断线性表是否合法
//2.判断插入位置是否合法
int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
if( ret )
{
    LinkListNode* current = (LinkListNode*)sList;
    //3.由表头开始通过next指针移动pos次后，当前元素的next指针即指向要插入的位置
    for(int i=0; (i<pos) && (current->next != NULL); i++)
    {
        current = current->next;
    }
    //4.将新元素插入
    node->next = current->next;
    current->next = node;
    //5.线性表长度加1
    sList->length++;
}

</br>

删除元素操作

操作步骤：

  • 判断线性表是否合法

  • 判断插入位置是否合法

  • 获取第pos个元素
  • 将第pos个元素从链表中删除
  • 线性表长度减1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkListNode* ret = NULL;
int i = 0;
//1.判断线性表是否合法
//2.判断插入位置是否合法
if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
{
		LinkListNode* current = (LinkListNode*)sList;
		//3.获取第pos个元素
		for(i=0; i<pos; i++)
		{
				current = current->next;
		}
		//4.将第pos个元素从链表中删除
		ret = current->next;
		current->next = ret->next;
		//5.线性表长度减1
		sList->length--;
}
return ret;

</br>

(3).单链表结构与顺序存储结构优缺点

</br>

5.静态链表

(1).结构分析

静态链表：让数组的元素都是由两个数据域组成，data和next。也就是说，数组的每个下标都对应一个data和一个next。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而next相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把next叫做游标。

  • 顺序表数组中的元素由两个数据域组成:data和next
  • data域用于存储数据
  • next域用于存储下一个元素在数组中的下标

表头结点中，data = 3 表示链表长度为3，next = 1 表示下一个结点的位置是1。

**静态链表是在顺序表的基础 静态链表是在顺序表的基础上利用数组实现的单链表。**

在C中用一维数组来实现顺序存储结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//节点结构体定义
typedef struct _tag_StaticListNode
{
  unsigned int date;
  int next;
}TStaticListNode;

//静态链表结构体定义
typedef struct _tag_StaticList
{
  int capacity;
  TStaticListNode header;
  TStaticListNode node[];
}TStaticList;

</br>

(2).重点操作

获取第pos个元素操作

操作步骤：

  • 判断线性表是否合法
  • 判断位置是否合法
  • 由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标
1
2
3
4
5
6
7
8
9
10
11
12
//1.判断线性表是否合法
//2.判断位置是否合法
if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
{
	sList->node[0] = sList->header;
  //由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标
  for(int i = 0; i < pos; i++)
  {
    current = sList->node[current].next;
  }
  object = sList->node[current].next;
}

</br>

插入元素到位置pos的算法

操作步骤：

  • 判断线性表是否合法
  • 判断插入位置是否合法
  • 在数组中查找空闲位置index
  • 由表头开始通过next域移动pos次后，当前元素的next域为要插入的位置
  • 将新元素插入
  • 线性表长度加1
1
2


</br>

删除第pos个元素的算法

操作步骤：

  • 判断线性表是否合法
  • 判断插入位置是否合法
  • 获取第pos个元素
  • 将第pos个元素从链表中删除
  • 线性表长度减1
1
2


</br>

(3).静态链表优缺点

</br>

6.循环链表

(1).结构分析

循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素.

</br>

(2).重点操作

循环链表拥有单链表的所有操作。

  • 创建链表
  • 销毁链表
  • 获取链表长度
  • 清空链表
  • 获取第pos个元素操作
  • 插入元素到位置pos
  • 删除位置pos处的元素

</br>

7.双向链表

0%