【数据结构】

【数据结构】_顺序表

1. 概念与结构

1.1 静态顺序表

1.2 动态顺序表

2. 动态顺序表实现

2.1 SeqList.h

2.2 SeqList.c

2.3 Test_SeqList.c

3. 顺序表性能分析

线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表有：顺序表、链表、栈、队列、字符串等；

线性表在逻辑上是连续的线性结构，在物理结构上并不一定是连续的。

线性表在物理上存储时，通常以数组和链式结构的形式存储，分别称之为顺序表和链表。

本文介绍顺序表。

1. 概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构，一般情况下采取数组存储，在数组上完成数据的增删查改；

要求数据必须从第一个位置开始连续存放；

顺序表在逻辑上是连续的，在物理上也是连续的；

1.1 静态顺序表

#define N 100
typedef int SLDataType;
// 静态顺序表
typedef struct SeqList{
	SLDataType arr[N]; // 定长数组
	size_t size;  // 有效数据个数
}SeqList;

在定义时使用定长数组，会造成数组大小若太小则导致不够用，数组若太大则导致空间浪费；

1.2 动态顺序表

#define N 100
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList {
	SLDataType* arr;
	size_t size;    // 有效数据个数
	size_t capacity;  // 空间大小
}SeqList;

在定义时仅给定数组首元素地址，并且基于size和capacity实现动态增容，相较而言更灵活。

注：1、通常会将顺序表的结构体命名为struct SeqList，即Sequence List；

2、建议目录结构：（注意自定义头文件的包含）

.h头文件：顺序表结构、声明顺序表的方法；

.c/.cpp源文件：实现顺序表的方法+测试；

3、为便于修改程序，通常会将顺序表结构体中的数据类型进行重命名，可命名为SLDataType；

为便于编写程序，通常也会对顺序表结构体进行重命名，可重命名为SeqList或SL；

2. 动态顺序表实现

2.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* arr;
	int size;   // 有效数据个数
	int capacity;  // 空间大小
}SL;
// 空间检查
void SLCheckCapacity(SL* psl);
// 打印
void SLPrint(SL* psl);
// 初始化
void SLInit(SL* psl);
// 销毁
void SLDestory(SL* psl);
// 尾插
void SLPushBack(SL* psl, SLDataType x);
// 头插
void SLPushFront(SL* psl, SLDataType x);
// 尾删
void SLPopBack(SL* psl);
// 头删
void SLPopFront(SL* psl);
// 指定位置插入
void SLInsert(SL* psl,int pos, SLDataType x);
// 指定位置删除
void SLErase(SL* psl,int pos);
// 查找
int SLFind(SL* psl, SLDataType x);
// 修改
void SLModify(SL* psl, int pos, SLDataType x);

2.2 SeqList.c

#include "SeqList.h"
// 初始化
void SLInit(SL* psl) {
	psl->arr = NULL;
	psl->size = psl->capacity = 0;
}
// 销毁
void SLDestory(SL* psl) {
	if (psl->arr) {
		free(psl->arr);
	}
	psl->arr = NULL;
	psl->size = psl->capacity = 0;
}
// 打印
void SLPrint(SL* psl) {
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->arr[i]);
	}
	printf("\n");
}
// 空间检查
void SLCheckCapacity(SL* psl) {
	if (psl->capacity == psl->size) {
		// 常以2倍增容
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->arr, newCapacity*sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc fail\n");
			exit(1);
		}
		psl->arr = tmp;
		psl->capacity = newCapacity;
	}
}
// 尾插
void SLPushBack(SL* psl, SLDataType x) {
	assert(psl);
	SLCheckCapacity(psl);
	// 写法1
	/*psl->arr[psl->size] = x;
	psl->size++;*/
	// 写法2
	psl->arr[psl->size++] = x;
}
// 头插
void SLPushFront(SL* psl, SLDataType x) {
	assert(psl);
	SLCheckCapacity(psl);
	int count = psl->size;
	// 写法一
	while (count) {
		psl->arr[count] = psl->arr[count-1];
		count--;
	}
	// 写法二
	//for (int i = psl->size; i > 0; i--) {
	//	psl->arr[i] = psl->arr[i - 1];
	//}
	psl->arr[0] = x;
	psl->size++;
}
// 尾删
void SLPopBack(SL* psl) {
	assert(psl);
	assert(psl->size);
	psl->size--;
}
// 头删
void SLPopFront(SL* psl) {
	assert(psl);
	assert(psl->size);
	for (int i = 0; i < psl->size - 1; i++) {
		psl->arr[i] = psl->arr[i+1];
	}
	psl->size--;
}
// 指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x) {
	assert(psl);
	assert(pos>=0 && pos<psl->size);
	SLCheckCapacity(psl);
	for (int i = psl->size; i >psl->size - pos;i--) {
		psl->arr[i] = psl->arr[i-1];
	}
	psl->arr[pos] = x;
	psl->size++;
}
// 指定位置删除
void SLErase(SL* psl, int pos) {
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	for (int i = pos; i < psl->size - 1; i++) {
		psl->arr[i] = psl->arr[i + 1];
	}
	psl->size--;
}
// 查找
int SLFind(SL* psl, SLDataType x) {
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->arr[i] == x)
			return i;
	}
	return -1;
}
// 修改
void SLModify(SL* psl, int pos, SLDataType x) {
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	psl->arr[pos] = x;
}

2.3 Test_SeqList.c

#include"SeqList.h"
int main() {
	SL sl1;
	SLInit(&sl1);
	printf("Test SLPushBack:PushBack5~10：\n");
	SLPushBack(&sl1, 5);
	SLPushBack(&sl1, 6);
	SLPushBack(&sl1, 7);
	SLPushBack(&sl1, 8);
	SLPushBack(&sl1, 9);
	SLPushBack(&sl1, 10);
	SLPrint(&sl1);

	printf("TestPushFront:PushFront 4~2：\n");
	SLPushFront(&sl1, 4);
	SLPushFront(&sl1, 3);
	SLPushFront(&sl1, 2);
	SLPrint(&sl1);

	printf("TestPopBack:PopBack 10：\n");
	SLPopBack(&sl1);
	SLPrint(&sl1);

	printf("TestPopFront:PopFront 2：\n");
	SLPopFront(&sl1);
	SLPrint(&sl1);

	printf("TestInsert:Insert arr[4]=99：\n");
	SLInsert(&sl1, 4, 99);
	SLPrint(&sl1);

	printf("TestErase:Erase arr[3]：\n");
	SLErase(&sl1, 3);
	SLPrint(&sl1);

	printf("TestFind: Find 99：\n");
	int retIndex = SLFind(&sl1, 99);
	printf("The index of 99 is: %d\n", retIndex);

	printf("TestModify:Modify 99 to 100：\n");
	SLModify(&sl1, 3, 100);
	SLPrint(&sl1);

	SLDestory(&sl1);
}

测试用例运行结果：