数据结构——线性表（顺序实现）

　　　　好好学习基础知识，出人头地就靠它了，内外兼修。(好吧，我现在内外都不行)写这篇文章的目的就是为了，巩固刚学完的线性表，个人能力有限，若有不当之处，望指出。

线性表

　　好了，扯完了，说正事：

　　1、定义

　　　　线性表是一种及其常用的并且最简单的一种数据结构。简单来说，线性表就是集合里的元素的有限排列。(在这里我把集合定义为具有相同属性的元素，会有些狭义)

　　在线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)^{[百度百科]}

　　怎么说呢，毕竟数据结构毕竟是逻辑结构，逻辑上符合线性结构的特征即可，存储结构能实现就行。线性表的很重要！很重要！很重要！后面的栈，队列，串等都是基于线性表的基础上实现的，所以说一定要学好线性表

　　2、线性表的特点：

　　　　对于任意的的非空线性表或者线性结构有：

　　　　　　1、存在唯一一个被称为 ”第一个“的元素

　　　　　　2、存在唯一一个被称为 ”最后一个“的元素

　　　　　　3、出第一个元素之外，每一个元素都存在一个后继

　　　　　　4、除最后一个元素之外，每一个元素都存在一个前驱

　　3、基本操作

　　　　1、Create(*L)创建空表

　　　　2、InitEmpty(*L)初始化

　　　　3、getLength(*L)获取长度

　　　　4、Insert(*L)插入元素

　　　　5、Remove(*L)移除元素

　　　　6、IsEmpty(*L)空表检测

　　　　7、IsFulled(*L)表满检测(顺序表常用，链式表基本不用)

　　　　8、Delete(*L)删除表

　　　　9、getElemt(*L)获取元素

　　　 10、Traverse(*L)遍历输出所有元素

　　　 11、Clear(*L)清除所有元素

 　　4 、实现

　　　　好了最麻烦的事情开始了，数据结构在计算机上的的映射。众所周知，线性表有两种实现方法，一种是顺序表，另一种是链式表，这两种结构实现最大的不同在于前者逻辑关系无需存储空间，而后者则需要用额外的空间(顺便记录一下，指针大小只由环境有关(严格意义上说和CPU的位数有关)本篇只实现顺序结构)。

　　　　1、顺序表：

　　　　　　先说一下概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

　　　　很明显对于顺序表来说：逻辑上相邻的数据元素，物理次序也是相邻的。 

　　　　　　特点：

　　　　　　　　对表中任意元素访问时间复杂度都为常数级。

　　　　　　　　尾部插入元素时间复杂度也为常量级。

　　下面是重点！！！

　　　　说明一下，讲解的时候实现语言为C，后续会贴上C++和Python

　　　　　　实现：

　　　敲~~~键盘，敲~~键盘！敲~~~键盘，敲~~键盘！

　　结构定义：　　

 1 #define YWZLIST_INIT_SIZE 8
 2 #define INC_SIZE 3 //空间增量的大小
 3 
 4 typedef int ElemType;
 5 typedef struct listnode
 6 {
 7     ElemType *base;
 8     int capacity; //顺序表容量
 9     int size;     //表的大小
10 } YWZlist;

　　函数声明：

 1 bool IsEmpty(YWZlist *list);                         //空表检测
 2 bool IsFull(YWZlist *list);                          //表满检测
 3 bool Inc(YWZlist *list);                             //增加顺序表的容量
 4 void InitSeqlist(YWZlist *list);                     //初始化顺序表
 5 void Push_back(YWZlist *list, ElemType x);           //在顺序表的末尾插入元素
 6 void Push_front(YWZlist *list, ElemType x);          //在顺序表的头部插入元素
 7 void Show_list(YWZlist *list);                       //显示顺序表中的元素
 8 void Pop_back(YWZlist *list);                        //删除顺序表最后一个元素
 9 void Pop_front(YWZlist *list);                       //删除顺序表第一个元素
10 void Insert_pos(YWZlist *list, int pos, ElemType x); //在顺序表的选定位置上插入数据
11 int Find(YWZlist *list, ElemType key);               //在顺序表中查找元素key的下标
12 int Length(YWZlist *list);                           //求顺序表的长度
13 void Delete_pos(YWZlist *list, int pos);             //删除顺序表中特定位置的数据元素
14 void Delete_val(YWZlist *list, int key);             //删除顺序表中值为key的数据元素
15 void Sort(YWZlist *list);                            //冒泡排序
16 void Reverse(YWZlist *list);                         //逆置顺序列表
17 void Clear(YWZlist *list);                           //清除顺序表中的所有元素
18 void Destroy(YWZlist *list);                         //摧毁顺序表
19 void Merge(YWZlist *lt, YWZlist *la, YWZlist *lb);   //合并两个顺序列表

　　　　上面一共19个函数，空表和表满函数就不写了

　　1、初始化：

　　　　思路很明确，先开辟一个最小的数组空间，给capacity赋值

void InitYWZlist(YWZlist *list) //初始化顺序表
{
    //开辟初始空间，开辟失败返回空
    list->base = (ElemType *)malloc(sizeof(ElemType) * YWZLIST_INIT_SIZE);

    if (list->base == NULL)
    {
        printf("内存不足！\n");
        return;
    }

    list->capacity = YWZLIST_INIT_SIZE - 1;
    list->size = -1;
}

　　2、扩容：

　　　　顺序表扩容不比链表，顺序表需要重新开劈空间需要用到realloc函数，来看一下函数原型

　　　　_CRTIMP void* __cdecl __MINGW_NOTHROW	realloc	(void*, size_t);　　//传进去的是要改变大小的指针

　　　　嗯，两个参数，一个指针，一个大小，由于要新开辟一块空间，所以我们不能用原指针来指向新开辟的空间，我i们需要一个新的之指针，下一步当然是计算需要多少空间，这就和malloc函数一样了，自己琢磨琢磨，记得改变capacity的值，贴代码：

bool Inc(YWZlist *list)
{
    //重新分配内存空间
    ElemType *newspace = (ElemType *)realloc(list, sizeof(ElemType) * (list->capacity + INC_SIZE));
    if (newspace == NULL)
    {
        printf("内存空间已满，无法再分配内存空间！\n");
        return false;
    }

    list->base = newspace;
    list->capacity += INC_SIZE;

    return true;
}

　　　3、尾部插入：

　　　　　顺序表的尾部插入无比的简单，因为物理上相邻，所以访问最后一个元素的时间复杂度为常量级。插入元素我们不仅需要考虑表是否表满，同时我们还需要检测是否可以开辟新的空间。只有当表满且内存不足才能返回异常。

void Push_back(YWZlist *list, ElemType x)
{
    //当表满且无法扩容
    if (IsFull(list) && !Inc(list))
    {
        printf("顺序表容量已满，无法再在表尾继续插入新元素！\n");
        return;
    }

    list->base[list->size] = x;
    list->size++;
}

　　4、头部插入

　　　　　这个就麻烦了，因为物理相邻，所以我们得把所有元素都向后移。(这也是链式表出现的原因之一)当然啦，打印错误的条件和尾部插入相同。

void Push_front(YWZlist *list, ElemType x)
{
  if (IsFull(list) && !Inc(list))
  {
    printf("顺序表容量已满，无法再在表尾继续插入新元素！\n");
    return;
  }

  for (int i = list->size; i > 0; i--)
  {
    list->base[i] = list->base[i - 1];
  }
  list->base[0] = x;
  list->size++;
}

　　5、第i个索引插入

　　　　说完尾部和头部，我们来类推一下第i个元素删除的。

　　　　第一步，都不用想肯定是先找到第i个元素，

　　　　第二步，将n-i+1个元素个元素向后移动，

　　　　第三步，插入元素

　　　　第四步，size++

　　按着这个思路贴上代码

void Insert_pos(YWZlist *list, int pos, ElemType x) 
{
  if (pos < 0 || pos > list->size)
  {
    printf("插入位置不合法，无法插入元素！\n");
    return;
  }
  if (list->size >= list->capacity && !Inc(list))
  {
    printf("顺序表容量已满，无法在插入新的元素！\n");
    return;
  }
  for (int i = list->size; i > pos; i--)
  {
    list->base[i] = list->base[i - 1];
  }
  list->base[pos] = x;
  list->size++;
}

　　6、遍历

　　　　这个直接贴代码，太简单了，不做作说明

void Show_list(YWZlist *list)
{
  for (int i = 0; i < list->size; i++)
  {
    printf("%d ", list->base[i]);
  }
  printf("\n");
}

　　7、尾部删除

　　　　删除其实没有想象中的那么难，就是把size--，因为你下次插入就是直接覆盖了，和原先的值没有任何关系。当然你得先判断一下表是否为空

void Pop_back(YWZlist *list) 
{
  if (list->size == 0)
  {
    printf("顺序表已空，无法再在表尾删除元素！\n");
    return;
  }
  list->size--;
}

　　8、头部删除

　　　　个人觉得无论是链表还是顺序表，只要会了插入，删除类推一下就会了。打个比方顺序表的头部插入是，一个个往后推，那么删除就是一个个往前移。当然一个是判断表满一个是判断表空

void Pop_front(YWZlist *list) 
{
  if (list->size == 0)
  {
    printf("顺序表已空，无法再在表头删除元素！\n");
    return;
  }
  for (int i = 0; i < list->size - 1; i++)
  {
    list->base[i] = list->base[i + 1];
  }
  list->size--;
}

　　9、指定位置删除

　　　　类推吧，

　　　　第一步，找到第i个元素

　　　　第二部，将从第i+1到第n个元素向前移动1

　　　　第三步，size--；

　　　是不是和插入很像，所以有些代码是很像的

void Delete_pos(YWZlist *list, int pos) 
{
  if (pos < 0 || pos >= list->size)
  {
    printf("删除位置不合法，无法删除元素！\n");
    return;
  }
  for (int i = pos; i < list->size - 1; i++)
  {
    list->base[i] = list->base[i + 1];
  }
  list->size--;
}

　　10、按元素删除

　　　　这个是我觉得，一般人找东西，都只记得叫什么名字而不是第几个，所以写了一个按元素删除的。其实思路和指定位置删除一样找到最前端的一样的元素后插入即可(有bug，当表中存在重复元素的时候，只会添加到最前面那个)

void Delete_val(YWZlist *list, int key) //删除顺序表中值为key的数据元素
{
  int pos = Find(list, key);
  if (pos == -1)
  {
    printf("顺序表中没有这个元素！\n");
    return;
  }
  Delete_pos(list, pos);
}

　　11、元素查找

　　　　不打算说，贴代码

int Find(YWZlist *list, ElemType key) //在顺序表中查找元素key的下标
{
  for (int i = 0; i < list->size; i++)
  {
    if (list->base[i] == key)
      return i;
  }
  return -1;
}

　　12、返回长度

　　　　size中记录了表长，直接return就好了

int Length(YWZlist *list) 
{
  return list->size;
}

　　13、排序

　　　　冒泡，不在这里做说明，自己去看。其实可以直接调用qsort函数的写一个compare函数就行了

void Sort(YWZlist *list) 
{
  for (int i = 0; i < list->size - 1; i++)
  { //排序的趟数(例如5个数据需要比较4趟)
    for (int j = 0; j < list->size - 1 - i; j++)
    { //每一趟比较中的比较次数(例如5个数据在第0趟需要比较4次)
      if (list->base[j] > list->base[j + 1])
      {
        ElemType temp = list->base[j];
        list->base[j] = list->base[j + 1];
        list->base[j + 1] = temp;
      }
    }
  }
}

　　14、顺序表逆序

　　要么写个for二分表只执行到n/2，要么写个while，大小指针(不是真正意义上的指针)小指针大于大指针的时候停止

void Reverse(YWZlist *list) //逆置顺序列表
{
  if (list->size == 0 || list->size == 1)
  {
    return;
  }
  int low = 0, high = list->size - 1;
  while (low < high)
  {
    ElemType temp = list->base[low];
    list->base[low] = list->base[high];
    list->base[high] = temp;
    low++;
    high--;
  }
}

　　15、清空表

　　无比简单，就一句size = -1；

void Clear(YWZlist *list) 
{
  list->size = 0;
}

　　16、删除表

　　free完毕之后，将所有成员重置

void Destroy(YWZlist *list) 
{
  free(list->base);
  list->base = NULL;
  list->capacity = 0;
  list->size = 0;
}

　　17、合并两个顺序表

　　这个就比较麻烦了

　　第一步：开辟足够的空间

　　第二步：让La与Lb比较，谁大/小存谁，直到一个表结束

　　第三步：将余下的元素都，存入表Lc中。

　　第四步：计算表长。

void Merge(YWZlist *lt, YWZlist *la, YWZlist *lb) 
{
  lt->capacity = la->size + lb->size;
  lt->base = (ElemType *)malloc(sizeof(ElemType) * lt->capacity);
  //assert(lt->base != NULL);
  int ia = 0, ib = 0, ic = 0;
  while (ia < la->size && ib < lb->size)
  {
    if (la->base[ia] < lb->base[ib])
    {
      lt->base[ic++] = la->base[ia++];
    }
    else
    {
      lt->base[ic++] = lb->base[ib++];
    }
  }
  while (ia < la->size)
  {
    lt->base[ic++] = la->base[ia++];
  }
  while (ib < lb->size)
  {
    lt->base[ic++] = lb->base[ib++];
  }
  lt->size = la->size + lb->size;
  Show_list(lt);
}

　　本篇只实现顺序表