前序

---

数据结构：包括数据的逻辑结构、存储结构和数据的运算

• 逻辑结构：线性、树形、图与集合
• 存储结构：顺序存储和链式存储结构
• 运算分类：更新、删除、插入和查询 抽象数据类型：Abstract Data Type

ADT 抽象数据类型名{
数据：
	数据元素以及之间关系定义
运算：
	运算1(参数表)：运算实现
	...
	运算n(参数表)：运算实现
}

算法与算法分析：

• 正确性
• 可读性
• 健壮性
• 高效性 时间复杂度分析：
• 核心：程序从开始到结束运行需要的时间
• 解决：事后分析+问题规模
• 最好最坏平均时间复杂度 空间复杂度分析:
• 固定部分：比如代码所占的空间
• 可变部分：代码中比如数组长度、堆栈 C/C++语言语法复习：
• 结构体

结构体知识：
	struct 与 class很相似 但是struct默认访问权限是public
	创建结构体：
	typedef strcut student{
		char namep[20];
		int age;
		float score;
	}Student;
	
	格式：typedef struct name{数据内容}bie_name;
	
	创建结构体元素：bie_name var;
	
	定义与初始化：
		1.直接给出初始化：Student S = {30,40};
		2.带初始化数值：Student S{30,40};
		3.构造：Student(int x_val,int y_val):x(x_val),y(y_val){}结构体内部
			然后调用：Student S(30,40);
		4.依次给出初始化：Stduent S;S.x = 30;S.score=40;
	结构体数组：
		与平时使用的数组几乎一致：
		Student students[3] ={
		{"张三",18,99},
		{"李四",19,99},
		{"你好",20,10}
		};
		调用：直接students[]	
		
	结构体指针：指向结构体元素
	
	结构体嵌套:
		example：
		typedef struct date{
			int year;
			int month;
			int day;
		}Date;
		typedef struct person{
			Date birthday;
			int age;
			char name[20];
		}Man;	
		
		一个结构体里面可以嵌套其他结构体，增加代码复用率
		
	结构体与函数：
		可以直接作为参数传入函数内部
		1.直接传入
		2.传入引用
		3.指针传递
		
		
		
	c++结构体的高级特性：
		1.结构体内部可以添加成员函数
		2.构造函数与解析函数
		3.几乎等同于类的性质 但是最大的区别就是类可以确定成员的私密属性
		4.但是struct只能是共有

• 指针知识

指针：是一种特殊变量，拥有类型，但是指向地址
	简单定义与使用：
		int *ptr = &var;
		或者
		char *ch;
		...
		也可以是结构体指针...
		
	数组与指针：
		数组首地址就是一个指针：int *ptr = arr;
		后面可以直接调用：*(ptr+1)
		表示arr[1]

• 类

---

线性表

---

线性表：是零个或者若干个数据元素构成的线性序列,元素个数称作n

• 直接前驱、直接后继
• 线性表很灵活、可在任意位置插入、删除元素的运算

ADT List{
Data:
	数据类型
Function:
	运算类型
}

1. 线性表的顺序存储与实现

//线性表的顺序表示定义如下
typedef struct seqList{
	int n;//线性表的当前长度
	int maxLength;//最大长度
	ElemType *element;//线性表元素数组
}SeqList;

//拟定线性表的数据元素ElemType如下：
typedef float ElemType;//浮点类型

那么定义一个线性表就是直接：SeqList L;

• 线性表的基本运算的实现：

/*
1.初始化
2.调用元素
3.插入元素
4.删除元素
5.遍历元素
6.撤销线性表
*/

//初始化
int Init(int maxsize,SeqList *L){
	L->n = 0;
	L->maxLength = maxsize;
	L->element = (ElemType*)malloc(sizeof(ElemType)*maxsize)
	if(L->element == NULL) return 0;
	return 1;
}

//查找元素
int Use(SeqList L,int i,ElemType *x){
	if(i<0 || i > L.n-1) return 0;
	*x = L.element[i];
	return 1;
}//找到返回1，越界直接返回0(不需要判断表是否为空，该情形直接包含在i>n-1内部)

//插入元素(插入位置为i意味着在下标为i+1的位置插入元素)
int Insert(int i,SeqList *L,ElemType x){
	if(i<-1 || L->n = L->maxLength || i>L->n-1) return 0;
	for(int j=L->n-1;j>i;j--){
		L->element[j+1] = L->element[j];
	}
	L->element[i+1] = x;
	L->n++;
	return 1;
}

//删除元素 输入下标i 删除i的位置的元素 并且将后续元素和迁移一个
int Delete(int i,SeqList *L){
	if(i<0 || i>L->n-1 || L->n==0) return 0;
	//错误原因：下标越界或者没有元素可以删除
	for(int j=i;j<L->n-1;j++){
		L->element[j] = L->element[j+1];
	}
	//直接将下标为i的元素覆盖 达到删除的效果
	return 1;
}

//遍历顺序表
void Traverse(SeqList L){
	if(L.n == 0) return 0;
	for(int i =0;i<L.n-1;i++){
		printf("%d ",L->element[i]);
	}
}

//撤销顺序表
void Destroy(SeqList *L){
	L->n = 0;
	L->maxLength = 0;
	free(L->element)//直接free顺序表首地址
}


//调用：
SeqList list;
Init(&list,100);//初始化list最大长度为100
循环插入填充元素
Delete(&list,8);
...
//有些地方是传入list的地址：当需要改变的时候
//当不需要改变的时候：直接传入list即可

2. 线性表的链式存储结构与实现 采用这种存储结构的线性表也称作：链表 分为：单链表、多链表、双向链表等多种类型

1.单链表的定义与表示
> 节点结构
element + link
typedef struct node{
	int data;
	struct node *link;
}Node;//结构体指针 指向的内容也是该结构体类型

typedef struct singleList{
	int n;
	Node *first;//头指针
}SingleList;

2.基本运算的实现:初始化、查找、插入、删除、输出与撤销

//初始化
int Init(int maxsize,SingleList *L){
	L->n = 0;
	L->first = NULL;
	return 1;
}

//调取元素(不改变单链表 只需要传入表名)
int Use(int i,SingleList L,int *x){
	if(i>L.n-1 || i<0) return 0;
	Node *t = L->first;
	for(int j=0;j<i;j++) t=t->link;
	*x = t->data;
	return 1;
}

//插入元素 插入在i之后 当i=-1时 插入在头节点
//i可以等于L->n-1但是不能大于等于L->n 越界
int Insert(int i,SingleList *L,int x){
	if(i<-1 || i>L->n-1) return 0;
	Node *temp = L->first;
	//找到插入前一个位置 头节点+i次1 (这里的i就是数组内部的索引，不过在链表内)
	for(int j=0;j<i;j++) temp = temp->link;
	//找到之后 执行插入操作
	Node *n = (Node*)malloc(sizeof(Node));
	n->element = x;//赋值给新创建的节点
	if(i<0){
		n->link = L->first;//n节点指向原来的头节点
		L->first = n;//头节点变成n
	}
	else{
		n->link = temp->link;
		temp->link = n;
	}
}

//删除链表元素 先找到位置 做好善后工作之后 删除节点
//传入下标为i 删除i的位置
int Delete(int i,SingleList *L){
	//先判断能不能删除
	if(i < 0 || i > L->n-1 || n == 0 ) return 0;//越界没有元素可以删除
	
	//然后需要找到删除元素前面的节点 与后面的节点
	Node *p = L->first,*q = p;
	for(int j=0;j<i-1;j++){
		q = q->link;//这里的temp就是i前面的节点
	}
	if(i=0){
		L->first = L->first->link;
	}
	else{
		p = q->link;
		q->link = p->link;
	}
	free(p);
	L->n--;
	return 1;
}//程序的健壮性

//输出链表
void OutPut(SingleList L){
	Node *work = L.first;
	if(!L.first) return 0;
	while(work){
		printf("%d ",work.element);
		work = work->link;//传递到下一个节点
	}
	return 1;
}

//删除创建好的链表
//删除链表 就是一个一个free 兄弟
int Destroy(SingleList *L){
	Node *work = L->first;
	while(work){
		L->first = work->link;
		free(work);
		work = L->first;
	}
}//销毁原理 先保存work为头节点 然后当当前要删除的节点不是null时
//将头节点设置为 该节点之后的节点 然后删除当前work节点 再重新定义work节点

代表头节点的单链表： 由于单链表插入删除的时候 需要将头节点作为特殊的位置进行处理，所以引入表头，只包含link信息 不含有数据域的节点，专门记录链表的位置

typedef struct headerList{

}