1、数据结构概述及顺序表（附：可以直接打印显示的源码）
《数据结构》概述：
数据结构：数据元素之间的关系（逻辑关系）
数据类型：高地电平 表示 1/0
要做大量的运算：诞生了基本数据类型：int double .....--》反应了数据的取值范围
（int字节：占4B--->-2^31~~~(2^31)-1
1bit: 0~1
2bit: 0~(2^2)-1 个数:2^2
个数怎么算的 ：00 01 10 11 四个
为什么要减一： 因为除二后0没有对称，先拿出一个数跟0对称，然后再要减一
32bit 表示多少个数：2^32
-2^31 ~~2^31-1）
要做什么系统之类的更复杂的东西：诞生了抽象数据类型：抽象
（人：信息（数据）+行为--->函数/方法--->数据+函数=抽象数据类型
使用抽象数据类型 定义一个数据结构--->数据集合+操作集合）
分析问题：逻辑结构--->逻辑上分析 事物之间的关系
解决问题：存储结构（物理结构/映像）--->在计算机中实现逻辑关系
存储结构就是用计算机语言实现的逻辑结构：密不可分
逻辑结构：线性逻辑结构：数据之间的关系是一对一的：线性表、栈、队列
非线性逻辑结构：数据之间的关系是一对多/多对多：树、图。。。
数据存储在存储器中
存储结构：1.顺序存储结构：逻辑上是连续的数据，存储时，在物理上也连续
2.链式存储结构：逻辑上是连续的数据，存储时，在物理上不连续，但是要实现逻辑上的连续：用指针把数据连起来，实现了逻辑上的连续
3.索引存储结构+4.散列存储结构（哈希）
数据结构：学一个一个的逻辑结构，选择合适的存储结构把它实现
线性逻辑结构：
线性表：n个数据元素的有限序列，按照线性结构排列
操作：增删改查
存储结构实现线性表：
顺序存储结构实现的线性表：
顺序表（在内存中画出以同一种数据类型存储的空间-->即数组）：以一维数组的形式保存的线性表
操作：增删改查
1.增：在顺序表中添加一个元素
（1）在末尾添加一个元素
（2）在末尾元素之前的某个i位置指定添加元素
倒着循环 把i及i位置后面的数据 往后移动一个位置，把i位置空出来
//在顺序表末尾添加一个元素：在size下标位置添加一个元素
void add(Array * a,int k)
{
//先判断是否超出最大容量值
if(a->size < a->length)
{
a->data[a->size]=k;
a->size++;
}
else{
printf("顺序表已满，不能放入数据\n");
}
}
//在下标i位置 插入一个数据k
void insert(Array *a,int i,int k)
{
//先判断是否超出最大容量值 先判满
if(a->size < a->length)
{
//移动位置，把data[i]空出来
for(int j=a->size-1;j>=i;j--)
{
a->data[j+1]=a->data[j];
}
a->data[i]=k;
a->size++;
}
else{
printf("顺序表已满，不能放入数据\n");
}
}2.查找：查找到给定数据的下标（位置），如果该数据不存在 返回-1
//查 : 一一比对 找到后直接把这个值返回
int find(Array a,int k)
{
for(int i=0;i<a.size;i++)//i只能小于a.size 因为size那个位置没数据（它是实际数据之后的位置） ，因为数组中有0，所以size多占了一个位置
{
if(k==a.data[i])
{
return i;
//如果没有找到，则不会返回任何值退出循环
}
}
return -1;//最后返回-1
}3.删除：删除给定的数据k
查找k的下标，往前调用 覆盖
void del(Array *a,int k)
{
//返回删除元素的下标 利用查找函数
int i =find(a,k);//或者直接加（*a） 即int i = find((*a),k);
if(i==-1)
{
printf("被删除的数据不存在\n");
}
else{
for(int j=i;j<a->size-1;j++)//j<a->size 或者j<a->size-1 不过没影响 正常是j<a->size-1 data[size+1]不会越界 因为size<length,但是数组满的时候会越界所以保险起见还是用j<a->size-1
{
a->data[j]=a->data[j+1];
}
a->size--;
}
}4.改：把数据i-->k
找i的下标b，然后a->data[b]=k;
void change(Array *a,int i,int k)
{
//找到数据为i的下标
int b =find(a,i);
if(b==-1)
{
printf("被修改的数据不存在\n");
}
else{
a->data[b]=k;
}
}顺序表的优缺点(说白了就是数组)：
优点：(方便)随机访问 data[i] 可以根据下标直接访问
缺点：操作繁琐：插入和删除操作都需要移动大量的数据,不够灵活
应用场景：以随机访问为主的需求中---》需求很少
5.源码
#include<stdio.h>
#include<stdlib.h>
//实现一个存放int类型的顺序表
//分析： 需要知道数据-->要一个数组 ,同时得知道这个数据的理论容量最大值跟实际值 三个方面来描述,放在一个里面-->声明结构体来实现
typedef struct ArrayList{
// int data[105];//静态开数组
int *data;//指针模拟开数组
int length;//声明理论容量的最大值
int size;//声明实际个数
}Array;
//初始化顺序表
Array initArray(int n)
{
Array ar;
ar.data=(int *)malloc(sizeof(int)*n);//开辟顺序表的空间 :分配成功-->data是一个实际的内存地址;分配不成功则会返回NULL（malloc的语法）
if(ar.data==NULL)
{
printf("空间分配失败");
}
//申请下来后就可以赋值了
ar.length=n;
ar.size=0;//还没放元素，则实际值为0
return ar;//返回到下面代码a的地方
}
//在顺序表末尾添加一个元素：在size下标位置添加一个元素
void add(Array * a,int k)
{
//先判断是否超出最大容量值
if(a->size < a->length)
{
a->data[a->size]=k;
a->size++;
}
else{
printf("顺序表已满，不能放入数据\n");
}
}
//在下标i位置 插入一个数据k
void insert(Array *a,int i,int k)
{
//先判断是否超出最大容量值 先判满
if(a->size < a->length)
{
//移动位置，把data[i]空出来
for(int j=a->size-1;j>=i;j--)
{
a->data[j+1]=a->data[j];
}
a->data[i]=k;
a->size++;
}
else{
printf("顺序表已满，不能放入数据\n");
}
}
//查 : 一一比对 找到后直接把这个值返回
int find(Array *a,int k)
{
for(int i=0;i<a->size;i++)//i只能小于a.size 因为size那个位置没数据（它是实际数据之后的位置） ，因为数组中有0，所以size多占了一个位置
{
if(k==a->data[i])
{
return i;
//如果没有找到，则不会返回任何值退出循环
}
}
return -1;//最后返回-1
}
void del(Array *a,int k)
{
//返回删除元素的下标 利用查找函数
int i =find(a,k);//或者直接加（*a） 即int i = find((*a),k);
if(i==-1)
{
printf("被删除的数据不存在\n");
}
else{
for(int j=i;j<a->size-1;j++)//j<a->size 或者j<a->size-1 不过没影响 正常是j<a->size-1 data[size+1]不会越界 因为size<length,但是数组满的时候会越界所以保险起见还是用j<a->size-1
{
a->data[j]=a->data[j+1];
}
a->size--;
}
}
void change(Array *a,int i,int k)
{
//找到数据为i的下标
int b =find(a,i);
if(b==-1)
{
printf("被修改的数据不存在\n");
}
else{
a->data[b]=k;
}
}
void show(Array a)
{
for(int i=0;i<a.size;i++)
{
printf("%d ",a.data[i]);
}
printf("\n");
}
int main()
{
Array a;//顺序表
//初始化：
int n; //假设理论容量的最大值
printf("请输入顺序表的理论最大容量：\n");
scanf("%d",&n);
a=initArray(n);//把n传入进去 写一个带返回值的函数 ，把线性表初始化好后再返回回来
//操作：增 利用add函数 因为增加后顺序表（函数）发生变化，则利用地址传参
add(&a,6);
// a=add(a,6) 也可以这样写
add(&a,7);
add(&a,8);
add(&a,9);
add(&a,1);
add(&a,5);
show(a);
insert(&a,3,7);
show(a);
//查
//顺序表没有变，所以用值传递
printf("%d",find(&a,9));
printf("\n");
//删
del(&a,6);//顺序表发生变化 因为del函数中要调用查找函数 所以把查找函数中的值传递a变成&a地址传递方便之后调用不会报错
//或者直接加（*a）
show(a);
//改
change(&a,1,10);//把数据1改成10
show(a);
return 0;
}