线性表

线性表(inear list)是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

首先线性表是一个序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
其次，线性表强调是有限的，其中的元素是有限的。

比如，要实现两个线性表集合A和B的并集操作。即要使的集合A=A并集B。也就是将存在于B中，不存在于A中的元素插入进集合A中。
我们假设La表示集合A，Lb表示集合B，则实现的代码如下：

/*将所有的在线性表Lb中但不存在La中的数据元素插入到La中*/
void unionL(Sqlist *La, Sqlist Lb)
{
	int La_len, Lb_len;
	ElemType e;                    /* 声明与La和Lb相同的数据元素e */
	La_len = Listlength(*La);      /* 求线性表的长度 */
	Lb_len = Listlength(Lb);
	for (int i = 1; i <= Lb_len; i++)
	{
		GetElem(Lb,i,&e);				/* 取Lb中第i个数据元素赋给e */
		if (!LocateElem(*La, e))		/* La中不存在和e相同数据元素 */
			ListInsert(La,++La_len,e);  /* 插入 */
	}
}

顺序表

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

顺序表一般可以分为：

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

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

看代码一，我们可以发现描述顺序存储结构需要三个属性:

1.存储空间的起始位置:数组array它的存储位置就是存储空间的存储位置;
2.线性表的最大存储容量:数组长度N;
3.线性表的当前长度: size。

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

代码二，原理与代码一无太大差别，只是数组的空间大小由静态变为动态的了。在数组每次满载时，进行判断进行增容capicity的大小。

（一）数据长度与线性表长度的区别

我们需要了解的是数组是我们创建出用来存放元素的存储空间，它的大小是固定的或是动态的。
而结构体中的size所表示的是我们创建线性表中的元素的个数，随着线性表插入和删除操作的进行，这个值是发生改变的。
在任意时刻，线性表的长度都应该小于等于数组的长度（否则出现访问越界的情况）。
我们明白选择数组的特点之一就是我们可以通过下标访问到我们想要的元素，在数组中我们排序也是从0开始的（须注意就是数组的下标），所以将线性表的元素存储在数组中，线性表中的第 i 个元素就是在数组下标为 i-1 的位置，即数据元素的序号和存放它的数组下标之间存在对应关系。

存储器中的每个存储单元都有自己的编号，这个编号成为地址。

假设占用的是 c 个存储单元，那么线性表中第 i+1（下标） 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

LOC(ai+1) = LOC(ai)+c;

所以对于第 i 个数据元素ai的存储位置可以有a1推算得出：

*LOC(ai) = LOC(a1) + (i-1)c;

通过此公式，可以随时算出线性表中任意位置的地址。对于计算机来说，对每个线性表位置的存入或者取出数据，都花费相同的时间，也就是一个常数，因此它的时间复杂度就是O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

（二）动态顺序表的实现

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

1.为了方便管理和提高代码的可读性，创建不同的文件来放置代码。

list.h用于放置所需头文件和宏，以及函数的声明
list. c用于放置函数的定义，通常于设置头文件的名字一致，便于与test. c分辨
test. c中放置主函数，作为一个菜单操作界面，使用所设计的函数。

2.我们可以联系之间学习的通讯录的原理参考使用

但是基于我们现在的目的是学习动态顺序表，所以我们尽量保持测试数据的便于调试(保证遇到问题时，可以快速找到问题)。
要求对线性表中的元素进行增删查改。
须注意，我们在学习C语言时就了解到使用动态内存的操作:
申请动态内存后，要确保使用的是成功申请了内存的空间，其次是使用结束后要释放空间，并将指向该空间的指针置为NULL。

3.创建结构体

结构体为了更好观察与全局的使用，我们将其建立在list头文件中。

//"list.h"
#include <stdio.h>
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array; // 指向动态开辟的数组
	size_t size; // 有效数据个数
	size_t capicity; // 容量空间的大小
}SL;

4.test.c

基于顺序表的功能前，我们需要最基本的两步，初始化和销毁。
并且在程序功能完善之前，我们先对每一步功能直接在程序中输入，不考虑程序使用时的菜单，选项等步骤。这便于我们在写单独某一项功能的代码时，出现错误便于调试查找错误。

//"test.c"

//我们在这里先将需要的功能函数写上，再在"list.c"中逐渐完善，
//最后再对这些代码进行“排版”

将每一项功能放在一个test();中，一一测试，节省时间，也更快捷。
设计函数中的参数时，注意：0传值传址的区别，以及其他参数的设计。
比如：增的设计中，&s是将地址传给形参，可修改其中的元素；i是第几位元素；num是要添加上的数字。
假如i为4，num为9. 数组中的元素是{ 1, 1,4,5,6, 7,8,9 };，那么这段增的函数运行后的数组变为{ 1,1,4,5,9,6,7,8,9 };那么当i=0时，就是头插，当i等于sz时，就是尾插。
其他的函数可以同理。
还需注意：num的类型可以用宏定义，以便选择使用不同的数据类型。
因此 #define int SLDataType

#include "list.h"

int main()
{
	SL s;
	int i = 0;
	SLDataType num = 0;
	//初始化顺序表
	SLInit(&s);		//了解传值和传址的区别
  
  //	//函数中中的pos，和num是方便理解，
  //	// 大家可以根据自己需求来修改
  //	//比如使用函数时直接（&s,0,3）这样
  //	//或者在函数中scanf等语句来修改pos和num的值
  
	//增-插入-头查-尾插-随机插入（查到才能插入）
	SLInsert(&s, i, num);

	//删-头删-尾删-随机删除（查到就能删除）
	SLErase(&s, i);

	//查
	SLFind(&s,i);

	//改-查到再改
	SLModify(&s, i, num);

	//销毁顺序表
	SLDestroy(&s);

	return 0;
}

5.lish.h

#pragma once

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

typedef int SLDataType;//num的数据类型

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

//初始化顺序表
void SLInit(SL* p);

//销毁顺序表
void SLDestroy(SL* p);

//增-插入-头查-尾插-随机插入
void SLInsert(SL* p,int pos, SLDataType num);

//删-头删-尾删-随机删除
void SLErase(SL* p, int pos);

//查
int SLFind(SL* p, SLDataType num);

//改-查到再改
void SLModify(SL* p, int pos, SLDataType num);


//打印-可供查看信息
void SLPrint(SL* p);

6.lish.c

#include "list.h"

//初始化顺序表
void SLInit(SL* p) {
	p->array = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (p->array == NULL)
	{
		perror("malloc fail");
		return;
	}
	p->size = 0;
	p->capacity = 4;
}

//增容
void SLCheckcapacity(SL* p)
{
	if ( p ->size == p->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(p->array,sizeof(SLDataType) * p->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		p->array = tmp;
		p->capacity *= 2;
	}
}

//增-插入-头查-尾插-随机插入
void SLInsert(SL* p, int pos, SLDataType num)
{
	assert(p);
	assert(0 <= pos && pos <= p->size);

	//先写一个插入后,后续元素要往后移动的程序
	//注意不要越界，因此要判断一个容量够不够存储
	SLCheckcapacity(p);
	for (int i = 0; i < p->size - pos; i++)
	{
		p->array[p->size - i] = p->array[p->size - 1 - i];
	}
	p->array[pos] = num;
	p->size++;
}

//删-头删-尾删-随机删除
void SLErase(SL* p, int pos)
{
	assert(p);
	assert(0 < pos && pos <= p->size);

	for (int i = pos; i < p->size-1; i++)
	{
		p->array[i] = p->array[i+1];
	}
	if(p->size > 0)
		p->size--;
}

//查
int SLFind(SL* p, SLDataType num)
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		if (num == p->array[i])
			return i+1;
	}
	return -1;
}

//改
void SLModify(SL* p, int pos, SLDataType num)
{
	assert(p);
	assert(0 < pos && pos <= p->size);
	p->array[pos] = num;
}

//打印-可供查看信息
void SLPrint(SL* p) 
{
	assert(p);

	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", p->array[i]);
	}
	printf("\n");
}

//销毁顺序表
void SLDestroy(SL* p)
{
	assert(p);
	free(p->array);
	p->array = NULL;
	p->size = 0;
	p->capacity = 0;
}

(三)完善代码

加上菜单等，循环等，让程序更完善。
略

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

优点：

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

缺点：

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