数据结构（二）———线性表和线性表的顺序存储结构

发表于 | 分类于

数据结构分为物理结构和逻辑结构，逻辑结构分为线性结构、集合结构、树形结构和图形结构。线性表就属于线性结构，线性表是最基本、最简单、也是最常用的一种数据结构。

最后更新时间：2018/11/16 17:05

线性表

线性表的性质

线性表 就是具有像线一样的性质的表。它是由零个或多个数据元素组成的有限序列。当线性表的长度为0时，称为空表。

在稍复杂的线性表中，一个数据元素可由多个数据项组成，此种情况下常把数据元素称为记录，含有大量记录的线性表又称为文件。

1
2
3
4
5
graph LR
数据元素1-.-数据元素2
数据元素2-.-数据元素3
数据元素3-.-...
数据元素n-.-...

线性表中数据元素之间的关系是一对一的关系，
数据元素1是线性表的第一个元素，只有一个直接后继。
数据元素n是线性表的最后一个元素，只有一个直接前驱。
除数据元素1和数据元素n的其他数据元素，既有直接前驱，也有直接后继，并且有且只有一个。

线性表的特点

  • 线性表存储的数据是同类型的
  • 线性表中各数据元素之间的相对位置是固定的

线性表的分类

逻辑结构上相邻的数据在实际的物理存储中有两中形式：分散存储和集中存储。

跟据这两种形式线性表可分为两种：

  • 数据元素在内存中集中存储，采用顺序存储结构，简称“顺序存储”，也称顺序表
  • 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”，也称链表

线性表的顺序存储结构

线性表的顺序存储结构是用一段地址连续的存储单元依次存储线性表的数据元素。

a1 a2 … ai-1 ai ai+1 … an

顺序表一般使用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中，数组大小有两种方式指定，一是静态分配，二是动态扩展。

注：数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变得。线性表的长度是线性表中数据元素的个数，随着线性表的插入和删除操作的进行，这个量是变化的。线性表的长度应该小于等于数组的长度。

顺序表的顺序存储表示

1
2
3
4
5
6
7
8
//----- 顺序表的顺序存储表示 -----
typedef  int  ElemType;
typedef struct {
	ElemType	*elem;	// 存储空间的基址
    int length; // 表长
    int size;// 存储容量
	int increment; // 扩容时，增加的存储容量
} SqList;  //顺序表

使用顺序存储结构需要四个属性：

  • 存储空间的起始位置：指针elem,它存储的位置就是存储空间的存储位置
  • 顺序存储表的最大存储容量：size
  • 顺序存储表的当前长度：length
  • 顺序存储表扩容时增加的容量：increment

顺序表的创建

1
2
3
4
5
6
7
8
Status InitSqlist(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem) exit (OVERFLOW);         //返回空指针则退出程序
	L.length = 0;                       // 空表长度为0
	L.size = LIST_INIT_SIZE;             // 初始存储容量
	L.increment = LISTINCREMENT;
	return OK;
}

void malloc(unsigned int num_bytes)：动态内存分配，用于申请一块连续的指定大小的内存块区域，void 表示未确定类型的指针，void * 可以指向任何类型的数据，更明确的说是指申请内存空间时还不知道用这段空间来存储什么类型的数据。如果分配内存成功则函数返回被分配内存的指针，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。

顺序表的的初始化操作就是为了顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。

顺序表的插入

插入算法的思路：

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

示例

当前有一个长度为7的顺序表

1 2 3 4 5 6 7 空闲

在顺序表第三的位置上插入一个元素“8”，因此当前顺序表的第三个元素及其以后的所有元素要向后移动一位，从顺序表的表尾开始

1
2
graph LR
8
1 2 3 4 5 6 7

当移动完成后，元素“8”插入顺序表的第三个位置上。顺序表的长度增加1。

1 2 8 3 4 5 6 7 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//顺序表插入函数
Status ListInsert_Sq(SqList &L, int i ,ElemType e){
	int j;  
   	if(i<1 || i>L.length+1) {      //对i的合法性判断
		printf("\n插入位置不合法！，i值必须大于等于1，小于等于%d\n",L.length+1);
		return ERROR;
	}      
   
   	if(L.length>=L.size) {        //对顺序表是否满判断 
   	    //当前存储空间已满，增加分配
   	   	L.elem = (ElemType *)realloc(L.elem, (L.size + LISTINCREMENT)*sizeof(ElemType));
		if(NULL == L.elem)       //分配内存失败，退出程序
		    return  OVERFLOW;
		L.size += LISTINCREMENT;     //增加存储容量
   	}
  
   	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;
}

void realloc(void ptr, size_t new_Size ) 用于对动态内存进行扩容（及已申请的动态空间不够使用，需要进行空间扩容操作），ptr为指向原来空间基址的指针，new_size为接下来需要扩充容量的大小。

执行realloc函数的几种情况

  • 如果当前内存段后面有需要的内存空间，则直接扩展这段内存空间，realloc()将返回指向原地址的指针。
  • 如果当前内存段后面的空闲字节不够，那么就是用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块位置。
  • 如果申请失败，将返回NULL，此时，原来的指针仍然有效。
注：如果调用成功，不管当前内存段后面的空闲空间是否满足要求，都会释放掉原来的指针

顺序表插入操作的时间复杂度为O(n)。

顺序表的按位获取元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ElemType ListQuery_Sq(SqList L,int i){
	ElemType e;
	if(i<1 || i>L.length+1) {    //对i的合法性判断
		printf("\n查询位置不合法！，i值必须大于等于1，小于等于%d\n",L.length+1);
		return ERROR;
	}      
	if (L.length!=0) {  //判断顺序表是否为空表
		e=L.elem[i-1];
		return e;
	}else {
		printf("\n这是个空表\n");
		return ERROR;
	}
}

顺序表本质是一个数组，利用数组的下标，可以获取到顺序表的元素。数组下标从0开始，顺序表位置从1开始，所以在获取顺序表中的元素，需要（i-1）才是数组的下标。

顺序表按位查找操作的时间复杂度为O(1)。

顺序表的删除

删除算法的思路：

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

示例

1 2 8 3 4 5 6 7

当前是一个长度为8的顺序表，我们要删除第三个位置上的元素。我们只需要将第四个位置上的元素覆盖掉第三个位置上的元素，第五个位置上的元素覆盖掉第四个位置上的元素，依此类推，直到执行至表尾。

1 2 3 4 5 6 7 空闲

执行完删除操作后，顺序表的长度减1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//顺序表删除元素函数
Status ListDelete_Sq(SqList &L, int i, ElemType  &e){
   //请在此填写代码，将该算法补充完整
   int j;
   if((i<1)||(i>L.length)) {
   		printf("\n删除位置不合法！，i值必须大于等于1，小于等于%d\n",L.length);
   		return ERROR;	 //i值不合法
   }
   e = L.elem [ i -1];
   for (j=i;  j<=L.length-1;  j++)                   
   		L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移   
   --L.length;               	      //表长减1
  return OK;
}

一般情况下，删除第i个元素时需要将从第i+1至第n个元素依次向前移动一个位置。

顺序表删除操作的时间复杂度为O(n)。

线性表顺序存储结构的优缺点

优点：

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任一位置的元素

缺点

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间容量
  • 造成存储空间的“碎片”