简单数据结构之线性表之顺序表

数据结构之线性表之顺序表"/>

简单数据结构之线性表之顺序表

顺序表的实现

相信很多小伙伴们都觉的，数据结构在刚接触计算机时，都是比较让大家都疼的吧~

不论是对于现在还处在水生火热的大一、大二的同学，还是对计算机方向比较感兴趣的同学，对于数据结构还是比较费劲的，窝瓜也不敢说自己学的有多好，但是，在这里，还是和大家分享一下自己在学习数据结构的过程中，产生的一些小想法！

数据结构是什么？

对于计算机来说，最重要的是什么？

在窝瓜看来，是数据！

从第一台计算机ENIAC的出现开始，计算机最为主要的目的，就是为了计算，也就是对于数据的处理！

而所谓处理数据，无非就是三个过程：

1. 数据的存储
2. 数据的读取
3. 数据的计算

很多同学到这要问了，说了半天，你还是没有告诉我们，到底什么是数据结构啊~

别着急，干货这就到了~

在我看来，所谓的数据结构，就是上面我说的三个过程中的前两个：数据的存储、数据的读取！

为什么呢？

在数据结构刚刚出现的时候，总是有一个词和它深深的纠缠，那就是——算法！

相信大家一定都听说过“数据结构与算法”这个词吧，没错，这就是我为什么说数据结构和那两个过程有关了。

数据结构——数据的储存

数据的读取——算法

数据如何在计算机中合理、高效的储存呢？这就要利用我们数据结构对其进行管理了，所以，说白了，究竟什么是数据结构？

相互之间存在一种或多种关系的数据元素的集合和操作！

这就是数据结构，同学们可能会问了，这集合理解了，可是这操作是什么呢？

别忘了，我上面还提到过的算法！

对于一批数据，首先设计合理的数据结构来储存它，在掌握其逻辑结构之后，对其设计算法，最后在通过它的物理结构来实现它，这就是现在我们所说的，数据结构！

所以，学习数据结构，分为下面这几个步骤：

1. 清楚物理结构
2. 熟记逻辑结构
3. 掌握基本算法

如果按照上面的步骤来学习数据结构，我相信，一定会有着不小的收获！

在接下来的一段时间中，窝瓜会陆续为大家介绍一些数据结构，希望大家能拿下数据结构这块硬骨头！

话不多说，我们正式开始！

顺序表

什么是顺序表，顾名思义，这是一种顺序存储的数据结构。在数据结构中，我们大概的将其分为四种，分别是：集合、线性结构、树结构、图结构！

而这个顺序表，就是属于线性结构中的一种，其实，学过JAVA的小伙伴一定听说过ArrayList这个词，没错！这所谓的顺序表，就是JAVA中的ArrayList，有兴趣的小伙伴不妨到自己的编译器中看看，ArrayList的底层，究竟是什么样的！

所谓的顺序表，就是用内存中连续的空间，将数据保存在这片空间中，这其实和数组的概念有些类似，这也就造就了线性表的特点：
通过索引查找，时间复杂度低，效率高！

事物都是有两面性的，有好处，当然也就有着坏处，线性表和数组一样，查找容易，但是，对于元素的删除或者插入操作，就会比较麻烦，毕竟，涉及到了将整个结构向前或者向后移动的操作！

在清楚了线性表的逻辑结构之后，就让我们一起来看看，它到底是如何实现的：

---

定义顺序表的管理结构：

//定义顺序表的管理结构
typedef struct {int size;int capacity;int * array;
}SqList;

初始化操作：

SqList * init_sq(SqList * p, int c){p->size = 0;//初始大小设置为0p->capacity = c?c:8;//如果传入参数，capacity的大小就用传入的参数，如果没有传入，默认大小为8p->array = (int *)malloc(sizeof(int) * p->capacity);//手动在堆区为array创建一片空间return p;
}//初始化操作

清空操作：

SqList * clear_sq(SqList * p){free(p->array);//手动释放堆区内存空间
}//清空操作

销毁操作：

void * destory_sq(SqList * p){free(p->array);//由于此函数没有返回值，所以在手动释放空间后，就相当于彻底销毁顺序表（没有返回值，无法通过指针找到顺序表）
}//销毁操作

读取指定位置元素：

SqList * geti_sq(SqList * p, int i , int * data){if(i >= p->size){return (void *)0;}* data =  p->array[i];return p;
}//读取指定位置元素

修改指定位置元素：

SqList * updatai_sq(SqList * p , int i, int data){if(i >= p->size){return (void *)0;}p->array[i] = data;return p;
}//修改指定位置元素

空间拓展操作：

SqList * extend_sq(SqList * p){int * new_sq = (int *)malloc(sizeof(int) * p->capacity * 2);memcpy(new_sq, p->array, sizeof(int) * p->size);free(p->array);p->array = new_sq;p->capacity *= 2;return p;
}//扩展空间

尾部插入元素：

SqList * push_back_sq(SqList * p, int data){if(p->capacity == p->size){extend_sq(p);}p->array[p->size++] = data;return p;
}//尾部插入元素

尾部删除元素：

SqList * pop_back_sq(SqList * p){if(p->size == 0){return (void *)0;}p->size--;return p;
}//尾部删除元素

指定位置插入元素：

SqList * insert_sq(SqList * p ,int index, int data){if(index > p->size){return (void *)0;}if(p->size == p->capacity){extend_sq(p);}int i;for(i = p->size - 1; i >= index; i--){p->array[i + 1] = p->array[i];}//这个for循环可以用memove函数代替p->array[index] = data;p->size++;return p;
}//在指定位置插入元素

删除指定位置元素：

SqList * erase_sq(SqList * p, int index){if(index > p->size){return (void *)0;}int i;for(i = index; i < p->size; i++){p->array[i] = p->array[i + 1];}//这个for循环可以用memove函数代替p->size--;return p;
}//删除指定位置元素

删除指定元素：

SqList * remove_sq(SqList * p, int data){int i;int w = 0;int count = 0;for(i = 0; i < p->size; i++){if(p->array[i] == data){count++;}else{p->array[w++] = p->array[i];}}//i和w分别追踪读和写的位置，当读到的元素不等于data，就会发生写操作，遇到相等的，就跳过，直到全部遍历完成位置p->size -= count;return p;
}//删除指定元素

打印顺序表：

void print(SqList * p){int i;printf("size = %d\tcapacity = %d\telenents:",p->size,p->capacity);for(i = 0; i < p->size; i++){int x;geti_sq(p, i, &x);printf("%d、",x);}printf("\n");
}//打印顺序表

main方法测试数据：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
int main()
{SqList sq;init_sq(&sq,4);int i;for(i = 0; i < 10; i++){push_back_sq(&sq, i);print(&sq);}printf("初始化10个元素完成!\n");for(i = 0; i < 6; i++){pop_back_sq(&sq);print(&sq);}printf("尾删6个元素完成！\n");updatai_sq(&sq, 1, 100);print(&sq);printf("修改指定位置元素完成！\n");insert_sq(&sq, 1, 200);print(&sq);printf("指定位置插入元素完成！\n");erase_sq(&sq,2);print(&sq);printf("指定位置删除元素完成！\n");remove_sq(&sq, 200);print(&sq);printf("删除指定元素完成！\n");clear_sq(&sq);print(&sq);printf("清空顺序表完成！\n");destory_sq(&sq);return 0;
}

结果展示：

下次窝瓜将会给大家带来链表的实现，希望大家喜欢！！