总言

  数据结构基础：顺序表模拟实现。
  

文章目录

• 总言
• 1、顺序表各接口功能实现描述
• • 1.1、如何创建一个顺序表？
  • 1.2、如何初始化顺序表：SLInit
  • 1.3、顺序表的尾插、头插
  • • 1.3.1、顺序表尾插1.0：SLPushBack
    • 1.3.2、顺序表头插1.0：SLPushFront
    • 1.3.3、辅助扩容函数：SLCheckCapacity
    • • 1.3.3.1、基本说明
      • 1.3.3.2、基于辅助扩容函数的头插尾插2.0
  • 1.4、顺序表的尾删、头删
  • • 1.4.1、顺序表尾删：SLPopBack
    • 1.4.2、顺序表头删：SLPopFront
    • 1.4.3、关于结构体指针的检查说明
  • 1.5、顺序表打印、顺序表销毁
  • • 1.5.1、顺序表打印：SLPrint
    • 1.5.2、顺序表销毁：SLDestroy
  • 1.6、顺序表在pos位置插入、删除
  • • 1.6.1、顺序表在pos位置插入：SLInsert
    • 1.6.2、顺序表头插、尾插实现3.0
    • 1.6.3、顺序表在pos位置删除：SLErase
    • 1.6.4、顺序表头删、尾删实现3.0
  • 1.7、顺序表查找、修改
  • • 1.7.1、顺序表查找：SLFind
    • 1.7.2、顺序表修改：SLModify

1、顺序表各接口功能实现描述

1.1、如何创建一个顺序表？

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

struct SeqList
{int data[100];//数组，顺序表一部分，用于存储数据int size;//大小，用于统计顺序表中元素个数
};

  上述只是一个基本雏形，因为还需要完善和修改。
  问题一：int data[100];顺序表存储的数据类型、数据大小被固定。
  
  1）、两种顺序表结构

  静态顺序表：使用定长数组存储元素。

#define N 100
typedef int SLDataType;
typedef struct SeqList
{SLDataType data[N];size_t size;
}SL;

  缺点：定长数组长度固定，若N太小，可能不满足实际存储所需大小，若N太大，当实际存储数目相对很小时，会造成空间浪费。即这种以定长数组来实现的静态顺序表，一定程度上不能满足实际使用中运用自如的多种场景。
  
  
  动态顺序表：使用动态开辟的数组存储。

typedef int SLDataType;
typedef struct SeqList
{SLDataType* data;//用于存储数据的数组,指向动态开辟空间的指针size_t size;//顺序表中实际数据个数size_t capacity;//顺序表容量空间大小
}SL;//为了便于书写而重命名

  其它说明:
  typedef int SLDataType;：使用typedef重定义数组类型，其目的是方便后续更换类型，此方法需要学习。
  
  

1.2、如何初始化顺序表：SLInit

  写法一：在初始化时置空，后续需要存储数据时再动态申请内存空间。

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

  其它说明：
  SL* ps：此处使用指针，是因为自定义函数中要改变实参数据，则需要址传递。
  
  
  

1.3、顺序表的尾插、头插

1.3.1、顺序表尾插1.0：SLPushBack

  1）、实现说明
  简介：顺序表尾插，即在顺序表末尾（数组末）插入一个新的数据。但需要注意容量空间问题：一初始插入未扩容时、其二为容量空间已满时。

void SLPushBack(SL* ps, SLDataType val)
{//检查	if (ps->capacity == ps->size){size_t newcapacity = (ps->capacity == 0) ? (4) : (ps->capacity * 2);SLDataType* tmpdata = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));if (tmpdata == NULL)//检查{perror("realloc");return 1;}ps->capacity = newcapacity;ps->data = tmpdata;}//尾插ps->data[ps->size] = val;ps->size++;
}

  if (ps->capacity == ps->size)：这里一次检查了两种情况：即初始化为NULL时，容量空间已满时；
  
  
  2）、测试检查

void test1()
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPrint(&s1);
}int main(void)
{test1();return 0;
}

1.3.2、顺序表头插1.0：SLPushFront

  1）、实现说明

  简介：顺序表头插，即在顺序表头部插入一个新的数据。由于此处顺序表是由数组实现的，数组在内存空间中连续存储，因此要头插一个新的数据，即意味着在数组空间足够的情况下，将原先数据都往后挪动一个位置。
  
  需要注意的细节：
  1、保证顺序表空间足够（数组空间），则需要在每次使用头插函数时，都进行扩容检查。
  2、如何挪动数组数据？为了保证数组元素不被覆盖，在内存空间充裕的情况下，从后往前（先挪动后面的数据，再挪动前面的数据）。
  3、头插函数实际可通过pos位置插入函数实现(后续内容)。

void SLPushFront(SL* ps, SLDataType val)
{//容量检查if (ps->capacity == ps->size){size_t newcapacity = (ps->capacity == 0) ? (4) : (ps->capacity * 2);SLDataType* tmpdata = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));if (tmpdata == NULL)//动态申请检查{perror("realloc");return 1;}ps->capacity = newcapacity;ps->data = tmpdata;}//数据挪动int end = ps->size;while (end >= 1){ps->data[end] = ps->data[end - 1];end--;}//头插ps->data[0] = val;ps->size++;
}

  需要注意：挪动数据中的写法不唯一，只要保证先挪动后面的数据，再挪动前面的数据即可。
  
  
  2）、测试检查

void test2()
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPrint(&s1);
}int main(void)
{test2();return 0;
}

1.3.3、辅助扩容函数：SLCheckCapacity

1.3.3.1、基本说明

  1）、问题引入
  在1.3.1和1.3.2中，进行数据插入时我们都进行了容量检查，因此，可以考虑将此部分内容单独拎出，写成一个独立的函数。
  
  2）、相关实现
  1、扩容检查分为两种情况，其一为首次使用顺序表（capacity=0），其二为顺序表容量空间满时（capacity≠0, but capacity=size）。
  2、使用realloc函数而未用malloc函数，是根据realloc函数的特性：第一形参为空指针NULL时，功能等同于malloc；第二形参为0，等同于free将释放内存块。

void SLCheckCapacity(SL* ps)
{//容量检查if (ps->capacity == ps->size){size_t newcapacity = (ps->capacity == 0) ? (4) : (ps->capacity * 2);SLDataType* tmpdata = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));if (tmpdata == NULL)//动态申请检查{perror("realloc");return 1;}ps->capacity = newcapacity;ps->data = tmpdata;}}

1.3.3.2、基于辅助扩容函数的头插尾插2.0

  1）、尾插实现2.0

void SLPushBack(SL* ps, SLDataType val)
{SLCheckCapacity(ps);ps->data[ps->size] = val;ps->size++;
}

  
  
  2）、头插实现2.0

void SLPushFront(SL* ps, SLDataType val)
{//容量检查SLCheckCapacity(ps);//数据挪动int end = ps->size;while (end >= 1){ps->data[end] = ps->data[end - 1];end--;}//头插ps->data[0] = val;ps->size++;
}

1.4、顺序表的尾删、头删

1.4.1、顺序表尾删：SLPopBack

  1）、实现说明
  简介：顺序表尾删，即删除顺序表最末尾的数据

void SLPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}

  注意事项:
  1、关于是否要对被删除数据做处理？
  实际上没有必要，例如，将被删除数据赋值为-1以此来表示该数据不存在，但也会有-1本身就是顺序表中一个数据的情况，即没有多余数值可提供该需求。
  因此实际操作中只需要将size数据实际个数做出更改即可。以此达到访问不到顺序表最末尾数据的效果。

  2、对size变量的细节处理？
  size在顺序表中表示实际数据个数，通常实际使用中有范围下限（最小值），因此使用尾删操作时，不能无限删下去，这样会造成size变为负值，而以负值访问数组是一种越界情况。
  因此尾删时需要对数据个数做检查。

  ps:此处关于越界不报错的原因：
  大概几率下，malloc等出错，在free处才显示报错。此外，关于越界是否报错，取决于编译器，系统对越界的检查，属于设岗抽查，类似于交警拦违规驾驶。
  
  
  2）、测试检查

void test3()//验证尾删
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);}

1.4.2、顺序表头删：SLPopFront

  1）、实现说明
  顺序表头删和尾删需要注意的细节点大致相同，只是头删需要涉及数据挪动问题。

void SLPopFront(SL* ps)
{assert(ps->size > 0);//挪动数据int begin = 1;while(begin < ps->size){ps->data[begin-1] = ps->data[begin];begin++;}//数值矫正ps->size--;
}

  
  
  2）、测试检查

void test4()
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);
}int main(void)
{test4();return 0;
}

1.4.3、关于结构体指针的检查说明

  根据上述内容，此处来思考一个问题，如下代码：

void test()
{SL s1=NULL;SLInit(&s1);SLPushBack(&s1, 1);SLPrint(&s1);SLPopBack(&s1);SLPrint(&s1);
}

  假设我们将顺序表对应的结构体指针赋值为空，则后续就会出现空指针解引用的操作，是非法的行为。从这我们可以得出，在实现上述接口时，也需要对传入的结构体指针进行检查：

	assert(ps);

	assert(ps!=NULL);

1.5、顺序表打印、顺序表销毁

1.5.1、顺序表打印：SLPrint

  1）、实现说明

void SLPrint(SL* ps)
{assert(ps);//结构体指针检查for (int i = 0; i < ps->size; ++i){printf("%d ", ps->data[i]);}printf("\n");
}

1.5.2、顺序表销毁：SLDestroy

  1）、实现说明

void SLDestory(SL* ps)
{assert(ps);//结构体指针检查if (ps->data){free(ps->data);ps->x = NULL;ps->size = ps->capacity = 0;}
}

1.6、顺序表在pos位置插入、删除

1.6.1、顺序表在pos位置插入：SLInsert

  1）、实现说明
  简介：在pos处插入新数据，即在数组中间位置插入数据，所用方法和头插相似，例如，输入pos=2，则在ps->x[pos]的位置需要插入新输入的数据。

  注意事项：
  1、仍旧需要做扩容检查，此外，还需对输入的pos位置进行检查，即pos需要在数组内部[0,size]，pos=0即头插，pos=size即尾插。
  2、在pos位置处插入数据，需要从后往前挪动数据。

void SLInsert(SL* ps, int pos, SLDataType val)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//容量检查SLCheckCapacity(ps);//数据挪动：从后往前挪int end = ps->size;while (end > pos)//end-1>=pos 等价于end>=pos+1 可得end>pos{ps->data[end] = ps->data[end - 1];end--;}//插入数据ps->data[pos] = val;ps->size++;
}

  
  2）、测试检查

void test5()
{SL s1;SLInit(&s1);SLInsert(&s1, 0, 1);//效果等同头插SLPrint(&s1);SLInsert(&s1, 1, 2);//效果等同尾插SLPrint(&s1);SLInsert(&s1, 1, 3);SLPrint(&s1);SLInsert(&s1, 1, 4);SLPrint(&s1);SLInsert(&s1, 1, 5);SLPrint(&s1);SLDestroy(&s1);
}int main(void)
{test5();return 0;
}

1.6.2、顺序表头插、尾插实现3.0

  根据上述实现的SLInsert，我们就可以把之前写的头插、尾插简化：

void SLPushBack(SL* ps, SLDataType val)
{SLInsert(ps, ps->size, val);
}

void SLPushFront(SL* ps, SLDataType val)
{SLInsert(ps, 0, val);
}

1.6.3、顺序表在pos位置删除：SLErase

  1）、实现说明
   简介：删除pos处的数据，和头删一样使用覆盖法，其余注意事项相同(size下限值，pos范围：[0,size),此时尾部size不能包含进来)。

void SLErase(SL* ps, int pos)
{assert(ps);assert(ps->size);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->data[begin - 1] = ps->data[begin];begin++;}ps->size--;
}

  
  2）、测试检查

void test6()
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPrint(&s1);SLErase(&s1, 0);//效果等同于头删SLPrint(&s1);SLErase(&s1, s1.size-1);//效果等同于尾删SLPrint(&s1);SLErase(&s1, 1);SLPrint(&s1);SLErase(&s1, 1);SLPrint(&s1);SLDestroy(&s1);
}int main(void)
{test6();return 0;
}

1.6.4、顺序表头删、尾删实现3.0

  同理，可使用SLErase对尾删、头删做修改简化：

void SLPopBack(SL* ps)
{SLErase(ps, ps->size-1);
}void SLPopFront(SL* ps)
{SLErase(ps, 0);
}

1.7、顺序表查找、修改

1.7.1、顺序表查找：SLFind

  1）、实现说明
  给定一个值，查找顺序表中是否有该值，若有，则返回对应下标，若无，则返回-1(此处返回的含义是数组下标，数组下标从0开始，故返回-1可表示数组中无该元素)

int SLFind(SL* ps, SLDataType val)
{assert(ps);for (int i = 0; i < ps->size; ++i){if (ps->data[i] == val)return i;}return -1;
}

1.7.2、顺序表修改：SLModify

  1）、实现说明
  顺序表修改：给定顺序表中需要修改元素的下标以及修改值。可结合顺序表查找使用，如此就不用特意写该函数：单链表中有演示。

void SLModify(SL* ps, int pos, SLDataType val)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->data[pos] = val;
}