数组：一种线性表数据结构

 线性表是指：每个数据只有前后两个方向的关联，常见的有数组，栈，链表，队列

与之相对应的非线性表有树，堆，图

关于删除和查找：在数组中删除或添加一个元素，为了内存的连续性，需要变动此增加元素索引之后的所有元素，在链表中则只需要断开和连接



数组扩容：数组在定义时需要分配连续的内存空间，扩容时的操作是将整个数组复制一份并重新分配新的内存空间，所以如果在定义数组是能确定数据的长度，尽量直接定义固定长度的数组，这样可以省掉很多次内存申请和数据搬移的操作，减少代码执行时需要消耗的时间

此等观众，才有幸见证我的来临

数组索引为什么从0开始：首先，数组内存的寻址公式如下：


a[i]_address = base_address + i * data_type_size


data_type_size是数组元素的大小，比如int型就是4个字节，那么从这个公式看来，我们通常所说的下标更准确的说法应该是offset，“偏移”，从0开始的话正好数组第一个元素的地址就是起始地址，从1开始的话会多一层减法运算

二维数组：二维数组在内存中的本质其实也是一维数组，只不过数组的每个元素又是一个数组，比如arr[3][3]就可以看出一个length=3的一维数组，一个m*n的二维数组，其寻址公式为：


a[i][j]_address = base_address + (i *n+j)* data_type_size


 

数据结构八大类型的总结及应用
数据结构八大类型的总结及应用（上）
数组
概念及优缺点
数组的应用
栈
概念
应用
队列
概念
链表
概念及优缺点
链表的应用及适用范围

数据结构八大类型的总结及应用（上）
本篇博客只总结了一半的内容，后一半的链接给各位送上：

https://blog.csdn.net/weixin_44593531/article/details/107453932
数组
概念及优缺点
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问。
优点十分明显，根据数组的索引可以快速的查找元素和遍历数组。
缺点表现在以下三个方面：

数组的大小一般在创建的时候就已经定义好了。
数组的添加某个元素，和删除某个元素的操作比较复杂，需要修改该位置后面的所有元素。
数组只能存放一种类型的数据。


数组的应用
我们通过一个C语言程序来总结数组结构的适用范围
对一个数组进行冒泡排序和选择排序
int main()
{
	int a[] = {2,5,8,0,9,6};
	int n= sizeof(a)/sizeof(a[0]); 
	//冒泡排序从大到小 
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++){
			if(a[j]<a[j+1]){
				int x = a[j];
				a[j] = a[j+1];
				a[j+1] = x;
			}
		}
	}
	//选择排序从小到大 
	int tmp = 0;
    for (int i=1;i<n;i++) {
        int j = i - 1;
        if (a[i] < a[j]) {
            tmp = a[i];
            a[i] = a[j];
            while (tmp < a[j-1]) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = tmp;
        }
    }
	return 0;
} 


我们可以看到，如果在实现需要频繁的迅速的遍历或者查找元素功能，且很少增加和删除的情况下，数组是非常有效的。但是通过对概念的了解，数组存放在一片连续的地址空间上，因而一般用来处理数量相对较小的数据，也就是对内存空间要求不大时，我们使用数组来操作。
栈
概念
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。


应用
用C语言链表来实现栈操作
typedef struct Link{
	int elem;
	struct Link *next;
}link;//结构体创建 

link * initStack(){
	link * stack = (link*)malloc(sizeof(link));
	return stack;
}//新建一个栈 ，令其指针永远指向栈顶元素，元素的指针指向下一元素 

void inStack(int elem, link *stack) {
	link *temp = stack;
	if(temp->next == NULL){//如果栈内没有元素就直接添加到栈顶 
		link * d = (link*)malloc(sizeof(link));
		d = temp->next;
		d->elem = elem;
		d->next = NULL;
	}else{//否则添加到栈顶，并将新元素指向之前的栈顶 
		link * s = (link*)malloc(sizeof(link));
		s->next = temp->next
		temp->next = s;
		s->elem = elem;
	}
}//入栈 

void outStack(link *stack){
	link *temp = stack;
	if(temp->next == NULL){
		printf("The stack is empty!");
	}else{
		printf("%d",temp->next);
	}
}//输出栈顶元素 

void deleteStackElem(link *stack){
	link *temp = stack;
	if(temp->next == NULL){
		printf("The stack is empty!");
	}else{
		link *s = temp->next;
		temp->next = s->next;
		s->next = NULL;
		free(s);
	}
}//删除栈顶元素 

队列
概念
队列与栈一样，也是一种线性表，不同的是，队列可以在头一端添加元素，在尾一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。


typedef struct Link{
	int elem;
	struct Link *next;
}link;//结构体创建 

link * initQueue{
	link *front = (link*)malloc(sizeof(link));
	link *rear = (link*)malloc(sizeof(link));
} //初始化两个指针分别指向入队口和出队口 

void addElem(int elem,link *front,link *rear){
	link *add = (link*)malloc(sizeof(link));
	link *temp = rear;
	if(temp->next == NULL){
		temp->next = add;
		add->next = elem;
		front->next = add;
	} else{
		temp->next->next = add;
		add->elem = elem;
		temp->next = add;
	}
}//入队 

void delElem(link *front,link *rear){
	link *temp = front;
	if(temp->next == NULL){
		printf("The queue is empty!");
	}else{
		link *elem = temp->next
		temp->next = elem->next;
		free(elem);
	}
}//出队 

链表
概念及优缺点
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
单链表：

每一个结点被分成两个部分，第一个部分是用来存放数据的，称为数据域，第二个部分是用来存放指针的，称为指针域，该位置所存放的指针指向的是下一个结点的地址。
一般链表中都存在一个头结点，该结点是不存放数据的，也就是说该结点的数据域为NULL，另外还存在一个尾结点，这个结点的指针域为空，也就是不指向下一个结点，因为它不存在下一个。首元结点指的是第一个存放数据的结点，头指针指向的是头结点。


双向链表：

在传统链表中我们寻找下一个结点是否方便，但是如果要追溯前面的结点是比较困难的。因此双向链表提供了反向遍历的能力。其秘密在于每个结点有两个指向其他结点的引用，一个指向前继结点，一个指向后继结点。下图显示了双向链表：

每个结点包括前指针、数据、后指针三部分。前指针指向前一个结点，后指针指向后一个结点，对于头结点，前指针为NULL，对于尾结点来时后指针为NULL。
循环链表：

循环链表就是在单链表的基础上，尾结点指向头结点，如下图所示：


链表的优点：

方便添加和删除元素

链表的缺点

查找相对困难

链表的应用及适用范围
C语言对单链表进行增删改查操作：
typedef struct Link{
	int elem;
	struct Link *next;
}link;//创建结构体

link * initLink(int n){
	int x;
    link * p=(link*)malloc(sizeof(link));
    link * temp=p;
    for (int i=0; i<n; i++) {
        link *a=(link*)malloc(sizeof(link));
        scanf("%d",&x);
        a->elem=x;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
} //新建

void addElem(int elem, int index,link *p) {
	link *temp = p;
	link *a=(link*)malloc(sizeof(link));
	for(int i=0;i<index;i++){
		temp = temp->next;
	}
	a->elem = elem;
	a->next = temp->next;
	temp->next = a;
}//增加 

link * delElem(link * p,int add){
    link * temp=p;
    for (int i=0; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;
    temp->next=temp->next->next;
    free(del);
    return p;
}//删除 

void modifyElem(link *p,int index,int elem){
	link *temp = p;
	for(int i = 0;i<index;i++){
		temp = temp->next;
	}
	temp->elem = elem;
} 

void getElem(link *p, int index){
	link *temp = p;
	for(int i = 0;i<index;i++){
		temp = temp->next;
	}
	printf("%d\n",temp->elem);
} //查找 

void display(link *p){
	link *temp=p;
	while(temp){
		printf("%d",temp->next->elem);
		temp=temp->next;
	}
	printf("\n");
}//遍历 

我们可以看到，在链表的初始化中不需要确定容量，所以后面可以进行元素的增加和删除，而且删除和增加操作都非常方便只需要改变指针所指向的值就好，但是，链表的查找却不是很简单，因为他需要从头结点开始遍历一直到找到该数据，相比数组而言，无法通过索引进行寻找，因此，我们一般在需要频繁的增加和删除的情况下使用链表。

数组：
定义：存储同一种类型多个元素的容器
特点：查找快，增删慢
查找：直接根据索引值即可
增加元素(假设在x元素元素后加入y元素):

A：新建一个数组，长度比原数组大1

B:遍历原数组，找到x元素位置

C:将原数组里x元素及x元素前面的元素都赋给新数组

D:再将y元素及x元素后的所有元素赋值给新数组

删除元素（同上）
链表：
定义：用一个链子将多个结点连起来的数据
特点：查找慢，增删快
查找：不管找哪个，都要从头开始
增加元素（在x元素后增加y元素):

A:新建一个临时变量temp

B:将x元素地址位置的值赋值给temp

C:将y元素的地址值赋值给x元素地址位置值

D:将temp值赋值给y元素的地址位置值

删除元素(删除x元素）：

将x元素地址位置值给x前一个元素地址位置值即可

当使用for循环顺序删除数组或者我之前遇到的问题使用Python操作Excel中需
要循环删除空列，会导致一次性删除不完。
原因是当我用for循环时候是用的索引循环。当我删除一个循环中的值时，索引
长度会变短，会往前递进。导致无法一次性循环删除。

      
如上图当一个循环的数组中包含 1 2 3 4 5需要删除 当循环删除2后绿色的框，数组长
度	就变成4个，所有2后面的都会依次往前顶上去。导致下一次循环到3时，他删除的
就是	紫色的框的值就会跳过蓝色的框，这样依次下去就会导致不会一次性删除索要删
除的数	据。 解决这个办法可以投机取巧，不要从第一位开始循环，可以从最后一位，
倒着循	环删除，就可以解决问题了。Python中倒着循环代码如下：

 for i in range(10,0,-1): #0<i<=10 步长-1 
 print(i)