数据结构：是一种或多种特定关系的数据元素的集合（结构是关系）

数据结构：分为逻辑结构(集合结构、树形结构、线性结构、图形结构)物理结构(计算机中数据逻辑结构的存储形式，又称存储结构)

存储结构：顺序存储和链式存储。

数据类型：集合一组具有相同性质的值并定义该值

数据类型的作用：

• 1.约束变量的内存空间

• 2.限制变量或常量的值范围

• 3.约束变量或常量的操作

抽象数据类型：抽象现有数据结构（包装和包装基本数据类型）

抽象数据类型的概念与面向对象的概念是一致的。

程序=数据结构 算法

算法：算法是解决特定问题解决步骤的描述，是计算机中指令的有限序列，每个指令表示一个或多个操作

时间复杂：T(n)=O(f(n))

省略常系数，只保留最高项

常见时间复杂度比较：O(1)2)n)

空间复杂：S(n)=O(f(n))

算法所需的存储空间存储空间实现算法的空间复杂性，所需的存储空间是指算法在运行过程中临时占用存储空间

数据结构可以进一步分为线性结构和图形结构（树是一种特殊的图）

（1）定义：线性表就是n个数据元素(类型相同)的有限序列

（2）特点：存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素

​ 除第一个之外的数据元素均只有一个前驱 除最后一个之外的数据元素均只有一个后继

​ 存在首尾，除首尾都有前驱和后继

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素 ，这种方法存储的线性表称作顺序表。

描述顺序存储结构需要三个属性：

（1）存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

（2）线性表的最大存储容量：数组长度MaxSize。

（3）线性表的当前长度：length。

顺序表存入或者取出数据时间复杂度为O（1）（通过公式直接计算），这种存储结构称为随机存取结构

优缺点

优点：（1）无需为表中元素之间的逻辑关系增加额外的空间 （2）快速查找

缺点：（1）插入删除移动大量元素 （2）存储空间固定

//顺序存储结构线性表

include<stdio.h>
include<stdlib.h>
define MAXSIZE 20

typedef struct{ 
        
	int data[MAXSIZE];
	int length;
}Sqlist;

/* typedef struct{ int*data; int MAXSIZE; int length; }Sqlist; */

//线性表的初始化
void Initlist(Sqlist* p) { 
        
	p->length = 0;
}

/* void Initlist(Sqlist* p){ p->data = (int*)malloc(sizeof(int)); if(p->data==NULL) { printf("动态内存分配失败"); exit(-1); } p->length = 0; } */

//线性表的创建
void CreateList(Sqlist* p,int n) { 
        
	int i,m;
	for (i = 0; i < n; i++)
	{ 
        
		scanf("%d", &m);
		p->data[i] = m;
		p->length++;
	}
}

//获取元素操作
int GetElem(Sqlist* p, int e) { 
        
	int i; //第几个元素
	scanf("%d", &i);
	if (i > p->length)
	{ 
        
		exit(0);
	}
	e = p->data[i - 1];
	return e;
}
顺序存储结构线性表中
插入一个元素，平均需要移动 n/2个元素
删除一个元素，平均需要移动 n-1/2个元素
//插入元素

算法思路：
如果插入位置不合理，抛出异常；
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处，表长加1。

Sqlist* ListInsert(Sqlist* p) { 
        
	int k,i,a;
	scanf("%d", &i);
	scanf("%d", &a);
	if (p->length == MAXSIZE)
	{ 
        
		printf("线性表已满");
		exit(0);
	}
	if (i<1 || i>p->length + 1)
	{ 
        
		printf("插入位置不在范围内 ");
		exit("error");
	}
	if (i <= p->length)
	{ 
        
		//将要插入位置后数据元素向后移动一位
		for (k = p->length - 1; k >= i - 1; k--)
		{ 
        
			p->data[k + 1] = p->data[k];
		}
		p->data[i - 1] = a;
		p->length++;
		return p;
	}
}

//删除元素

如果删除位置不合理，抛出异常；
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
表长减1。

Sqlist* ListDelete(Sqlist* p) { 
        
	int k, i;
	scanf("%d", &i);
	if (p->length == 0) //线性表为空
	{ 
        
		exit(0);
	}
	if (i<1 || i>p->length + 1)
	{ 
        
		printf("删除位置不在范围内 ");
		exit(0);
	}
	if (i < p->length)
	{ 
        
		for (k = i; k < p->length; k++)
		{ 
        
			p->data[k - 1] = p->data[k];
		}
	}
	p->length--;
	return p;
}
//插入和删除的平均时间复杂度均为O（n）
int main(void)
{ 
        
	int n,j,e = 0;//初始化e
	Sqlist* p = (Sqlist*)malloc(sizeof(Sqlist)); //初始化p
	Initlist(p);
	scanf("%d", &n);
	CreateList(p, n);
	//e = GetElem(p, e);
	//p = ListInsert(p);
	//p = ListDelete(p);
	for (j = 0; j < p->length; j++)
	{ 
        
		printf("%d ", p->data[j]);
	}
	return 0;
}

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

头结点与头指针

头指针是指向链表第一个结点的指针，如果有头结点就是指向头结点的指针，具有标识作用，常被冠以链表名字

头指针是必须有的，头结点不是必须有的

头结点是为了统一第一个元素与其他元素插入删除操作的统一

由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是**“工作指针后移”**