数据结构——顺序表【C】

avatar
作者
筋斗云
阅读量:0

顺序表

1. 顺序表的概念以及结构

1.1概念

顺序表就是用一段物理地址连续空间储存元素的线性结构,在正常情况下采用数组存储,在数组上完成增删查改等操作。

1.2静态顺序表和动态顺序表

  1. 静态顺序表: 使用长数组存储数据(数组的长度是固定的)
  2. 动态顺序表: 动态开辟数组存储(根据需求来设定数组长度)

2. 顺序表接口模拟实现

接口总览

typedef int SLDatatype; typedef struct SeqList { 	SLDatatype* a; //指向动态开辟的数组 	int size;//数组中有效数据的个数 	int capacity;//容器空间大小 }SL;  void SLInit(SL* psl); //顺序表初始化  void SLDestory(SL* psl);//顺序表的销毁  void SLPrint(SL* psl);//打印顺序表中的元素  void SLPushBack(SL* psl, SLDatatype num);//尾插  void SLPushFront(SL* psl, SLDatatype num);//头插  void SLPopBack(SL* psl);//尾删  void SLPopFront(SL* psl);//头删  void SLInsert(SL* psl, int pos, SLDatatype num);//从任意位置插入数据  int SLFind(SL* psl, SLDatatype num);//查找顺序表中的元素  void SLErase(SL* psl, int pos);//删除任意位置的元素 

2.1 初始化数据和销毁容器

初始化数据:
设置指向数组的指针为空,有效数据个数和容器空间大小设置为0。

void SLInit(SL* psl) { 	assert(psl); 	psl->a = NULL; 	psl->size = psl->capacity = 0; } 

销毁容器:
所释放动态开辟数组的空间,并设置指向的指针为空指针,有效数据个数和容器空间大小设置为0。

void SLDestory(SL* psl) { 	assert(psl); //判断psl是否为空  	free(psl->a); 	psl->a = NULL; 	psl->size = psl->capacity = 0;  } 

2.2 顺序表的尾插和尾删

在尾插只前我们还要考虑容器是否有足够的空间,若是足够直接插入数据,若是不够则需要动态开辟数组。
注意我们这里默认开辟两倍的空间,在实际中要需要根据需求来开辟容器空间。

void SLCheckCapacity(SL* psl) { 	assert(psl); 	if (psl->size == psl->capacity)//若是容器中的有效元素等于容器间就要扩容 	{ 		int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; 		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * newcapacity); 		if (tmp == NULL) 		{ 			perror("realloc"); 			return; 		} 		psl->a = tmp; 		psl->capacity = newcapacity; 	} } 

尾插:
首先我们要判断容器空间大小,不足则扩容,足够则插入数据。尾插十分容易直接在数组末尾插入数据即可,有效数据加一。
在这里插入图片描述

void SLPushBack(SL* psl, SLDatatype num) { 	assert(psl);  	SLCheckCapacity(psl);  	psl->a[psl->size++] = num; } 

尾删:
同样的尾删也很容易,只需要将有效数据size-1即可。在这里插入图片描述

void SLPopBack(SL* psl) { 	assert(psl); 	assert(psl->size > 0);  	psl->size--; } 

2.3 头插和头删

头插:
首先还是容器大小的老问题,不足则扩容,足够则插入数据。头插与尾插不同的是,需要挪动数据将数组中的每一个元素向后移动一位,然后我们在空出的头位置插入数据。
在这里插入图片描述

void SLPushFront(SL* psl, SLDatatype num) { 	assert(psl); 	  	SLCheckCapacity(psl);  	int end = psl->size - 1; 	while (end >= 0) 	{ 		psl->a[end + 1] = psl->a[end]; 		end--; 	}  	psl->a[0] = num; 	psl->size++; } 

头删:
头删也是同样的,让开始位置的后一个数据向前覆盖,将有效数据size-1即可。
在这里插入图片描述

void SLPopFront(SL* psl) { 	assert(psl);  	int begin = 1; 	while (begin < psl->size) 	{ 		psl->a[begin - 1] = psl->a[begin]; 		begin++; 	}  	psl->size--; } 

2.4 任意位置插入和删除数据

任意位置插入数据:
这里任意位置的数据就是容器中任意元素下标位置,同样的插入数据还使用挪动数据,将末尾到pos位置的数据向后挪动一位,在空出的pos位置插入数据。

void SLInsert(SL* psl,int pos, SLDatatype num) { 	assert(psl);  	SLCheckCapacity(psl);  	int end = psl->size;  	while (end >= pos) 	{ 		psl->a[end] = psl->a[end - 1]; 		end--; 	}  	psl->a[pos] = num; 	psl->size++;   } 

任意位置删除数据:
删除pos位置的数据,还是一样挪动覆盖。

void SLErase(SL* psl,int pos) { 	assert(psl);  	int end = pos; 	while (end <= psl->size - 1) 	{ 		psl->a[end] = psl->a[end + 1]; 		end++; 	} 	psl->size--; } 

2.5 查找数据

通过遍历容器中的元素,若是查到则返回元素下标,若是没有找到则返回-1。

int SLFind(SL* psl,SLDatatype num) { 	assert(psl); 	 	for (int i = 0; i < psl->size; i++) 	{ 		if (psl->a[i] == num) 		{ 			return i; 		} 	} 	return -1; } 

3. 顺序表的问题 :

  1. 尾部插入的效率还行,头部或者中间插入删除(时间复杂度尾O(N))、需要挪动数据、效率低下。
  2. 满了以后只能扩容。扩容式有一定的消耗的,扩容一般是存在一定的空间浪费。
    (假设空间是100满了,扩容到200,但是只需要插入120个数据,因此有80个空间就浪费掉了,一次扩的越多,可能浪费的越多,一次扩少了,那么有可能就会频繁的扩容)

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!