线性表

线性表（linear list）是 $n$ 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

一、顺序表

1.1 概念及结构

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储。
   • 难以确定适合的空间大小

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

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

// 顺序表的动态存储
typedef struct SeqList
{
     SLDataType* array;  // 指向动态开辟的数组
     size_t size ;       // 有效数据个数
     size_t capicity ;   // 容量空间的大小
}SeqList;

返回顶部

1.2 接口定义

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致$N$定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

SqList_dynamic.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;  // 自定义数组的类型 -> 实现类型一次性修改
// 静态顺序表
typedef struct SeqList {
	SLDataType* array ; // 指针指向开辟的空间
	int size;			// 有效数据的个数
	int capacity;       // 数组实际存储容量空间大小
}SL;

//基本增删查改接口
// 顺序表初始化
void SeqListInit(SL* psl);
// 顺序表销毁
void SeqListDestory(SL* psl);
// 顺序表打印
void SeqListPrint(SL* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SL* psl);
// 顺序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* psl, size_t pos);

返回顶部

1.3 初始化顺序表

// 顺序表初始化
void SeqListInit(SL* psl){
	assert(psl); // 判断
	psl->array = NULL;
	psl->size = psl->capacity = 0;
}

返回顶部

1.4 销毁顺序表

// 顺序表销毁
void SeqListDestory(SL* psl) {
	free(psl->array);  // 释放指针指向的空间
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}

返回顶部

1.5 打印顺序表

// 顺序表输出
void SeqListPrint(SL* psl){
    // 循环遍历
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->array[i]);
	}
	printf("\n");
}

正常的循环遍历顺序表，进行元素的输出！

返回顶部

1.4 尾部插入新元素

开始之前我们需要考虑以上的三种情况！

SqList.c

// 顺序表尾插
void SeqListPushBack(SL* psl, SLDataType x) {
    
	// 当数据个数等于空间容量大小时
	if (psl->size == psl->capacity) {
		// 1、均为0，没有空间
		// 2、空间已满 (扩容 2倍 适中)
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->array, newcapacity * sizeof(SLDataType));
        
		if (tmp == NULL) {
			// 增容失败，退出
			printf("realloc fail\n");
			exit(-1);
		}
        
		// 增容成功，重新赋值
		psl->array = tmp;
		psl->capacity = newcapacity;
	}
    
	// 空间容量足够，直接添加 => size即表示数据的个数也表示下一位的索引
	psl->array[psl->size] = x;
	psl->size++;
    
}

Test.c

#include "SqList_dynamic.h"
void TestInit() {
	SL s1;
	SeqListInit(&s1);  // 初始化，传递地址
	SeqListPushBack(&s1, 1); // 尾插5个数据
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(&s1); // 输出创建的顺序表
    // 销毁顺序表
    SeqListDestory(&s1);
}

int main() {
	TestInit();
	return 0;
}

返回顶部

1.5 尾部删除元素

// 顺序表尾删
void SeqListPopBack(SL* psl) {
	// 只写 psl->size--; 会出现数组越界
	
	//处理方式一：判断size的值
	//if (psl->size > 0) {
	//	psl->size--;  // 顺序表的数据个数由size控制
	//}
	
	// 处理方式二：断言
	assert(psl->size> 0);
	psl->size--;  // 顺序表的数据个数由size控制
}

• 只写 psl->size–; 会出现数组越界，如下图：

使用断言处理之后，当顺序表的元素个数小于0时就会报错，停止程序：

返回顶部

1.6 头部插入元素

头插元素，相当于将原顺序表从头部开始的元素依次往后移动1个位置。这里需要注意的是要从最后一个位置开始，如果从第一个左边开始往后移动，会发生覆盖，需要创建中间变量存储，不如从右边往后移动方便。移动完成后，将第一个位置赋值即可。

// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x) {
    
	int end = psl->size - 1;  // 定义游标end指向顺序表最后一位
	// 从后往前依次移动后移顺序表的元素 -> 直到移动完第一个元素为止
	while (end>=0){
		// 元素后移一位
		psl->array[end + 1] = psl->array[end];
		// 游标前移
		--end;
	}
	// 全部移动完成后，头部元素空出来为所要插入的元素
	psl->array[0] = x;
	// 同时元素个数加一
	psl->size++;

}

测试的时候会发生报错：显然数组越界了！

解决方案：扩容

// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x) {
    
	// 当数据个数等于空间容量大小时
	if (psl->size == psl->capacity) {
		// 1、均为0，没有空间
		// 2、空间已满 (扩容 2倍 适中)
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->array, newcapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			// 增容失败，退出
			printf("realloc fail\n");
			exit(-1);
		}
		// 增容成功，重新赋值
		psl->array = tmp;
		psl->capacity = newcapacity;
	}
	
	int end = psl->size - 1;  // 定义游标end指向顺序表最后一位
	// 从后往前依次移动后移顺序表的元素 -> 直到移动完第一个元素为止
    .............
    
}

到这里为止，我们可以发现扩容的操作是一样的，所以我们可以将其提取出来，单独设置一个函数，后面使用直接调用就可以了。

可以看到，当我们使用扩容之后在进行程序的调试，再进行添加元素的时候，就会重新申请内存空间进行扩容操作：

最终的结果也不会报错了：

返回顶部

1.7 头部删除元素

顺序表的头删，与头插相反，这里只要从左往后依次向前移动一位就可以了，直接2覆盖1、3覆盖2….若从右边开始往左移，则会出现5覆盖4，4就随即消失了，需要创建中间变量进行存储，很不方便。

// 顺序表头删
void SeqListPopFront(SL* psl) {
	// 断言：判断size是否大于0
	assert(psl->size > 0);
	// 定义起点游标begin，从前往后移
	int begin = 1;
	// 当游标移动到最后一个元素结束
	while (begin<psl->size){
		// 每一次使用当前元素覆盖前面一个元素
		psl->array[begin - 1] = psl->array[begin];
		// 游标后移一位
		++begin;
	}
	// 全部移动完成后，代表头元素被删除，所以顺序表的元素个数减一
	psl->size--;

}

返回顶部

1.8 查找指定值的下标

查找指定数值的下标位置相对来说比较简单，直接通过遍历查找进行匹配就可以了：

// 顺序表查找x值位置的下标
int SeqListFind(SL* psl, SLDataType x) {
	// 循环遍历顺序表元素
	for (int i = 0; i < psl->size; i++) {
		// 一一比较
		if (psl->array[i] == x) {
			// 找到返回下标
			return i;
		}
	}
	// 未找到，返回-1
	return -1;
}

返回顶部

1.9 指定位置插入新元素

首先，我们需要考虑一下插入数据位置的选择，如上图所示，当我们在红色区域时，范围均超出了并且不合理。当在绿色区域时，分别对应头插与尾插，上面已经分析过了，所以我们只要考虑中间插入的情况。

如果A区域的位置不存在，此时插入还需要考虑扩容的问题！

// 顺序表在postion位置插入x
void SeqListInsert(SL* psl, size_t pos, SLDataType x) {
	// 处理方式一：判断结束
	/*if (pos<0 || pos>psl->size) {
		printf("位置不合理！");
		return;
	}*/
	// 处理方式二：断言
	assert(pos >= 0 && pos< psl->size);
    
	// 检查空间，如果满了，进行增容
	CheckCapacity(psl);
    
	// 定义end游标指向顺序表最后一位
	int end = psl->size-1;
	// 循环直到end游标移到指定位置pos时结束
	while (end>=pos) {
		// 将pos后的元素依次后移一位
		psl->array[end + 1] = psl->array[end];
		// 游标前移一位
		--end;
	}
	// 将指定元素添加到指定的位置
	psl->array[pos] = x;
	// 顺序表元素个数加一
	psl->size++;

}

返回顶部

1.10 删除指定位置的元素

删除之前需要判断指定删除的位置必须存在assert(pos >= 0 && pos < psl->size);，与头删的理念一样，这里从指定位置的后一位开始依次向前移动元素，最终删除元素后，要将顺序表的元素个数减一。

// 顺序表删除postion位置的值
void SeqListErase(SL* psl, size_t pos) {
	// 断言：删除的位置必须存在
	assert(pos >= 0 && pos < psl->size);
	// 定义指定位置后一位处为开始游标
	int begin = pos + 1;
	// 循环遍历，从游标位置开始每个元素前移一位
	while (begin<psl->size){
		// 元素前移
		psl->array[begin - 1] = psl->array[begin]; 
		// 游标后移一位
		++begin;
	}
	// 删除元素后，元素个数减一
	psl->size--;
}

返回顶部

1.11 合并两个顺序表

// 合并两个顺序表
void SqListMerge(SL* L1, SL* L2, SL* L3) {
	SLDataType* p1 = L1->array;
	SLDataType* p2 = L2->array;
	L3->capacity = L3->size = L1->size + L2->size;
	SLDataType* p3 = L3->array = (int*)malloc(L3->capacity * sizeof(SLDataType));
	if (!L3->array) exit(-1);			//存储分配失败
	SLDataType* p1Last = L1->array + L1->size - 1;
	SLDataType* p2Last = L2->array + L2->size - 1;
	while (p1 <= p1Last && p2 <= p2Last) {	//合并
		if (*p1 < *p2)  *p3++ = *p1++;
		else if (*p1 == *p2) {				//如果碰到相同的元素可以去掉其中一个
			*p3++ = *p1++;					//然后表长-1，两个指针都指向下一个
			p2++;
			L3->size--;
		}
		else *p3++ = *p2++;
	}
	while (p1 <= p1Last) *p3++ = *p1++;		//插入L1的剩余元素
	while (p2 <= p2Last) *p3++ = *p2++;		//插入L2的剩余元素
}

补充：

• 这里还有一种思路，就是中间利用已经编写好的尾插进行顺序表的合并操作！

返回顶部

1.12 过程剖析

（1）函数的参数问题

• 在函数中有参数需要进行传递的时候，形参相当于函数的一个局部变量；形参是将实参进行拷贝然后放入函数进行运行，所以并不会对原来的实参数据有任何影响

• 若需要改变实参数据，需要传递地址参数

返回顶部