《数据结构》概述：
数据结构：数据元素之间的关系（逻辑关系）
数据类型：高地电平 表示 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;//还没放元素，则实际值为0return 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;
}
