数据结构——顺序表（超完整）

た入场券 2024-03-31 16:14 16阅读 0赞

**目录**

顺序表

静态顺序表

动态顺序表

顺序表定义

顺序表初始化

顺序表扩容

顺序标插入

顺序表删除

顺序表查找

顺序表修改

顺序表打印

顺序表销毁

--------------------

## 顺序表 ##

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

顺序表一般可以分为：  
**静态顺序表：**使用定长数组存储。

**动态顺序表：**使用动态开辟的数组存储。

### 静态顺序表 ###

由于静态顺序表不是特别重要，我在这里就不仔细展开。

// 顺序表的静态存储
    #define N 100
    typedef int SLDataType;
    typedef struct SeqList
    {
         SLDataType array[N]; // 定长数组
         size_t size;     // 有效数据的个数 
    }SeqList;
    typedef struct SeqList
    {
    	SQDataType a[MAX_SIZE];
    	int size;
    }SL;
    
    //接口函数定义
    void SeqListInit(SL* ps)
    {
    	memset(ps->a, 0, sizeof(SQDataType)*MAX_SIZE);//初始化函数
    	ps->size = 0;
    }
    
    // 头插 尾插 头删 尾删
    void SeqListPushBack(SL* ps, SQDataType x)
    {
    	if (ps->size >= MAX_SIZE)
    	{
    		printf("SeqList is Full\n");
    		return;
    	}
    
    	ps->a[ps->size] = x;
    	ps->size++;
    }
    //下面几种和尾插类似
    void SeqListPushFront(SL* ps, SQDataType x);
    void SeqListPopBack(SL* ps);
    void SeqListPopFront(SL* ps);

静态顺序表由于数组空间有限，导致储存较大的数据的时候会溢出，需要手动改写MAX\_SIZE值，所以我们就需要用扩容函数来实现动态顺序表的实现。

### 动态顺序表 ###

#### 顺序表定义 ####

首先由于是动态数据表，所以需要将静态数组改成动态数组。

typedef struct SeqList
    {
    	SQDataType* a;
    	int size;     // 有效数据的个数
    	int capacity; // 容量
    }SL;

#### 顺序表初始化 ####

void SeqListInit(SL* ps)
    {
    	ps->a = NULL;
    	ps->size = 0;
    	ps->capacity = 0;
    }

#### 顺序表扩容 ####

我们需要用realloc函数来扩容，malloc函数也是扩容函数但是realloc函数效率更高，所以这里我们使用realloc。

void SeqListCheckCapacity(SL* ps)
    {
    	// 满了就要扩容
    	if (ps->size == ps->capacity)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
    		if (tmp == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		else
    		{
    			ps->a = tmp;
    			ps->capacity = newcapacity;
    		}
    	}
    }

由于我们最初将capacity初始化为0，所以我们扩容函数最初需要判断capacity是不是0，是0我们就需要给一个初始空间4，经过下面扩容函数如果空间超出将空间扩大两倍！

#### 顺序标插入 ####

void SeqListInsert(SL* ps, int pos, SQDataType x)
    {
    	assert(pos <= ps->size);
    	SeqListCheckCapacity(ps);//检查是否超出容量
    
    	int end = ps->size - 1;
    	while (end >= pos)
    	{
    		ps->a[end + 1] = ps->a[end];
    		--end;
    	}
    
    	ps->a[pos] = x;
    	ps->size++;
    }

#### 顺序表删除 ####

void SeqListErase(SL* ps, int pos)
    {
    	assert(pos < ps->size);
    	int start = pos + 1;
    	while (start < ps->size)
    	{
    		ps->a[start-1] = ps->a[start];
    		++start;
    	}
    	ps->size--;
    }

#### 顺序表查找 ####

int SeqListFind(SL* ps, SQDataType x)
    {
    	for (int i = 0; i < ps->size; ++i)
    	{
    		if (ps->a[i] == x)
    		{
    			return i;
    		}
    	}
    	return -1;//未找到
    }

#### 顺序表修改 ####

void SeqListModity(SL* ps, int pos, SQDataType x)
    {
    	assert(pos < ps->size);
    	ps->a[pos] = x;
    }

#### 顺序表打印 ####

void SeqListPrint(SL* ps)
    {
    	for (int i = 0; i < ps->size; ++i)
    	{
    		printf("%d ", ps->a[i]);
    	}
    	printf("\n");
    }

#### 顺序表销毁 ####

void SeqListDestory(SL* ps)
    {
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = ps->size = 0;
    }

顺序表初始化的时候是用realloc函数向系统申请的空间，malloc函数申请的空间是在内存的堆区，堆区的空间不会被系统自动回收，需要用free函数释放空间。