线性结构和顺序表
简单介绍一下什么是线性表。
先学习一下顺序表。
什么是线性表
线性表，全名线性存储结构，简单的可以理解为，把所有的数据用一根线串起来，再存储到物理空间中。
当然按照数据结构的存储方式，我们可以将线性存储结构分为两类，一种是将所有数据按照顺序串起来直接放进物理空间中，另一种则是利用空闲的物理空间来存放一串数据。
图3a)是多数人能想到的存储方式，而图3b)却很少有人能想到，我们知道，数据存储的成功与否，取决于是否能将数据完整的复原成它本来的样子，如果把线头扯起，就会发现数据的顺序没有发生任何改变，因此这两种存储方式都没问题。
将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）
使用线性表存储数据，和数组一样，数据类型必须是一样的。
线性存储结构分为顺序存储结构和链式存储结构
前驱和后继
在数据结构中，一组数据的每个个体被称为“数据元素”(简称“元素”)。
顺序表
顺序表也称顺序存储结构，属于线性表中的一种。
不仅如此，顺序表在存储数据的时候，会提前申请一块足够大小的物理空间，然后将数据依次存进去，存储的时候数据与数据之间没有任何空隙。
顺序表的初始化
使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用数据，顺序表还需要实时记录两项数据：
- 顺序表申请的存储容量；
- 顺序表的长度，也就是表中存储数据元素的个数； 因此，我们需要自定义顺序表：
typedef struct Table{
int * head; //声明了一个名为head的长度不确定的数组，也叫“动态数组”
int length; //记录当前顺序表的长度
int size; //记录顺序表分配的存储容量
}table;
head是我们声明的一个未初始化的动态数组，不要将其当作一个普通的指针。
我们接下来要给顺序表初始化，也就是初步建立一个顺序表：
- 给head动态数据申请足够大小的物理空间；
- 给size和length赋初值；
#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小
table initTable(){
table t;
t.head=(int *)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
if(!t.head){//如果申请失败，做出提示，并直接退出程序
printf("初始化失败");
exit(0);
}
t.length=0;//空表的长度初始化为0
t.size=Size;//空表的初始存储空间为Size
return t;
}
我们将这段程序写完整并在顺序表中输入数据：
#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct Table{
int *head;
int length;
int size;
}table;
table initTable(){
table t;
t.head=(int*)malloc(Size*sizeof(int));
if(!t.head){
printf("初始化失败");
exit(0);
}
t.length=0;
t.size=Size;
return t;
}
void displayTable(table t){//这段函数表示输出顺序表t中的元素
for(int i=0;i<t.length;i++){
printf("%d",t.head[i])
}
printf("\n");
}
int main(){
table t = initTable();
for(int i=1;i<=Size;i++){
t.head[i-1]=i;
t.length++;
}
printf("顺序表中的元素分别是：");
displayTable(t);
return 0;
}
程序运行结果：
12345
顺序表插入元素
向顺序表中插入元素分为三种情况：
- 向顺序表的表头位置插入元素
- 向顺序表的中间位置插入元素
- 在顺序表的最后插入元素
虽然插入元素的位置不一样，但是插入的方法是一样的，都是用同一种方式去解决问题，即:通过遍历，找到数据元素要插入的位置然后：
- 将要插入位置的元素以及后续的所有元素都往后移动一个位置；
- 然后将你要输入的元素放进去
//插入函数，其中，elem为插入元素，add为插入到顺序表中的位置。
table addTable(table t,int elem,int add){
//判断插入本身是否存在问题(如果插入元素位置比整张表的长度+1还大(如果相等是尾随的情况)，或者插入的位置本身不存在，程序作为提示并自动退出)
if(add>t.length+1||add<1){
printf("插入位置有问题\n");
return t;
}
//做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请。
if(t.length==t.size){
t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
if(!t.head){
printf("存储分配失败\n");
return t;
}
t.size+=1;
}
//插入操作，需要将从插入位置开始的后续元素，逐个后移
for(int i=t.length-1;i>=add-1;i--){
t.head[i+1]=t.head[i];
}
//后移完成后将所需插入元素，添加到顺序表的相应位置
t.head[add-1]=elem;
//由于添加了元素，所以长度+1
t.length++;
return 0;
}
我们在初始申请空间的时候使用的是malloc函数，但在后续申请更大的物理空间的时候使用realloc函数，并且，在实现后续元素整体后移的过程，目标位置其实是有数据的，只是下一步将新的数据插入进去就会把旧元素覆盖
顺序表删除元素
从顺序表中删除指定元素，实现起来其实很简单，就是找到你要删除的元素，然后将其后一个元素前移一个位置，将后一个位置上的元素前移就相当于覆盖了前一个元素，就可以间接实现删除元素的目的。
table delTable(table t,int add){
if(add>t.length||add<1){
printf("被删除元素位置有误。");
return t;
}
//删除操作
for(int i=add;i<t.length;i++){
t.head[i-1]=t.head[i];
}
t.length--;
return t;
}
顺序表查找元素
顺序表中查找目标元素，可以使用多种查找算法实现，这里我们使用顺序查找算法：
int selectTable (table t,int elem){
for(int i=0;i<t.length;i++){
if(t.head==elem){
return i+1;
}
}
return -1;
}
顺序表更改元素
顺序表更改元素的顺序：
- 找元素
- 改元素
//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
table amendTable(table t,int elem,int newElem){
int add=selectTable(t,elem);
t.head[add-1]=newElem;
return t;
}
实现顺序表的基本操作，我给出完整的代码:
#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct Table{
int * head;
int length;
int size;
}table;
table initTable(){
table t;
t.head=(int*)malloc(Size*sizeof(int));
if(!t.head){
printf("初始化失败\n");
exit(0);
}
t.length=0;
t.size=Size;
return t;
}
table addTable(table t,int elem,int add){
if(add>t.length+1||add<1){
printf("插入位置错误\n");
return t;
}
if(t.length>=t.size){
t.head=(int*)realloc(t.head,(t.size+1)*sizeof(int));
if(!t.head){
printf("存储分配失败\n");
return t;
}
t.size+=1;
}
for(int i=t.length-1;i>=add-1;i--){
t.head[i+1]=t.head[i];
}
t.head[add-1]=elem;
t.length++;
return t;
}
table delTable(table t,int add){
if(add>t.length||add<1){
printf("被删除位置有误\n");
return t;
}
for(int i=add;i<t.length;i++){
t.head[i-1]=t.head[i];
}
t.length--;
return t;
}
int selectTable(table t,int elem){
for(int i=0;i<t.length;i++){
if(t.head[i]==elem){
return i+1;
}
}
return -1;
}
table amendTable(table t, int elem,int newElem){
int add = selectTable(t,elem);
t.head[add-1]=newElem;
return t;
}
void displayTable(table t){
for(int i=0;i<t.length;i++){
printf("%d",t.head[i]);
}
printf("\n");
}
int main(){
table t1 = initTable();
for(int i=1;i<Size;i++){
t1.head[i-1]=i;
t1.length++;
}
printf("原顺序表:\n");
displayTable(t1);
printf("删除元素后的顺序表：\n");
t1=delTable(t1,1);
displayTable(t1);
printf("在第二个元素的位置插入5：\n");
t1=addTable(t1,5,2);
displayTable(t1);
printf("查找元素3的位置：\n");
int add=selectTable(t1,3);
printf("%d\n",add);
printf("将元素3改为7:\n");
t1=amendTable(t1,3,7);
displayTable(t1);
return 0;
}