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位置空出来

2. //在顺序表末尾添加一个元素：在size下标位置添加一个元素
3. void add(Array * a,int k)
4. {
5.         //先判断是否超出最大容量值
6.         if(a->size < a->length)
7.         {
8.                 a->data[a->size]=k;
9.                 a->size++;
10.          }
11.          else{
12.                  printf("顺序表已满，不能放入数据\n");
13.          }
14. }
16. //在下标i位置 插入一个数据k
17. void insert(Array *a,int i,int k)
18. {
19.         //先判断是否超出最大容量值 先判满
20.         if(a->size < a->length)
21.         {
22.                 //移动位置，把data[i]空出来
23.                 for(int j=a->size-1;j>=i;j--)
24.                 {
25.                         a->data[j+1]=a->data[j];
26.                 }
27.                 a->data[i]=k;
28.                 a->size++;
29.          }
30.          else{
31.                  printf("顺序表已满，不能放入数据\n");
32.          }
33. }

复制代码

2.查找：查找到给定命据的下标（位置），假如该数据不存在 返回-1

2. //查 : 一一比对  找到后直接把这个值返回
3. int find(Array a,int k)
4. {
5.         for(int i=0;i<a.size;i++)//i只能小于a.size  因为size那个位置没数据（它是实际数据之后的位置） ，因为数组中有0，所以size多占了一个位置
6.         {
7.                 if(k==a.data[i])
8.                 {
9.                         return i;
10.                         //如果没有找到，则不会返回任何值退出循环
11.                 }
12.         }
13.         return -1;//最后返回-1
14. }

复制代码

3.删除：删除给定的数据k

查找k的下标，往前调用 覆盖

2. void del(Array *a,int k)
3. {
4.         //返回删除元素的下标 利用查找函数
5.         int i =find(a,k);//或者直接加（*a） 即int i = find((*a),k);
6.         if(i==-1)
7.         {
8.                 printf("被删除的数据不存在\n");
9.         }
10.         else{
11.                 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
12.                 {
13.                         a->data[j]=a->data[j+1];
14.                 }
15.                 a->size--;
16.         }
17. }

复制代码

4.改：把数据i-->k

找i的下标b，然后a->data=k;

2. void change(Array *a,int i,int k)
3. {
4.         //找到数据为i的下标
5.         int b =find(a,i);
6.         if(b==-1)
7.         {
8.                 printf("被修改的数据不存在\n");
9.         }
10.         else{
11.                 a->data[b]=k;
12.         }
13.        
14. }

复制代码

次序表的优缺点(说白了就是数组)：

长处：(方便)随机访问 data 可以根据下标直接访问
缺点：使用繁琐：插入和删除使用都须要移动大量的数据,不敷机动
应用场景：以随机访问为主的需求中---》需求很少

5.源码

1. #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的地方         }
2. //在顺序表末尾添加一个元素：在size下标位置添加一个元素
3. void add(Array * a,int k)
4. {
5.         //先判断是否超出最大容量值
6.         if(a->size < a->length)
7.         {
8.                 a->data[a->size]=k;
9.                 a->size++;
10.          }
11.          else{
12.                  printf("顺序表已满，不能放入数据\n");
13.          }
14. }
16. //在下标i位置 插入一个数据k
17. void insert(Array *a,int i,int k)
18. {
19.         //先判断是否超出最大容量值 先判满
20.         if(a->size < a->length)
21.         {
22.                 //移动位置，把data[i]空出来
23.                 for(int j=a->size-1;j>=i;j--)
24.                 {
25.                         a->data[j+1]=a->data[j];
26.                 }
27.                 a->data[i]=k;
28.                 a->size++;
29.          }
30.          else{
31.                  printf("顺序表已满，不能放入数据\n");
32.          }
33. }//查 : 逐一比对  找到后直接把这个值返回 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 }
34. void del(Array *a,int k)
35. {
36.         //返回删除元素的下标 利用查找函数
37.         int i =find(a,k);//或者直接加（*a） 即int i = find((*a),k);
38.         if(i==-1)
39.         {
40.                 printf("被删除的数据不存在\n");
41.         }
42.         else{
43.                 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
44.                 {
45.                         a->data[j]=a->data[j+1];
46.                 }
47.                 a->size--;
48.         }
49. }  
50. void change(Array *a,int i,int k)
51. {
52.         //找到数据为i的下标
53.         int b =find(a,i);
54.         if(b==-1)
55.         {
56.                 printf("被修改的数据不存在\n");
57.         }
58.         else{
59.                 a->data[b]=k;
60.         }
61.        
62. }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;}

复制代码