数据结构是研究包括数据的逻辑结构、存储结构以及定义在它们之上的一组运算。
第一章、基础知识
1.数据结构的主要研究内容
（1）数据结构的逻辑结构。根据应用对象 设计有限元素集合中结点之间的逻辑关系，如线性表、树、图等
（2）逻辑结构在计算机中的物理实现。数据结构在计算机内存中的表示方法称为数据结构的物理结构，以区别前者的逻辑结构形式，
如顺序表（顺序存储结构）、链表（链式存储结构）、二叉树等
（3）数据结构中结点的操作运算。如插入、删除、检索等
2. 数据结构的线性和非线性
数据结构有线性和非线性之分。一个数据结构的关系里，除端点外，每个结点有一个且仅有一个前趋和后继时，
这个数据结构是线性的，如数组，链表。（成绩单，账目管理，书籍管理）
一个数据结构的关系里，其结点有一个以上的前趋或后继，则称之为非线性的数据结构，如树、图（比赛晋级）
3 . 数据结构内容的三要素
数据结构 = 数据逻辑结构 + 物理结构 + 数据运算
4. 数据结构常用术语
数据 Data：对事物的符号表示
数据元素 Data element：描述数据的基本单位
其中，数据项 Data item：数据元素中的项，是描述数据的最小单位
数据对象 Data Object ：是性质相同的一类数据元素的集合，是数据的子集
数据结构 Data structure
逻辑结构 Logical structure：集合、线性结构、树形结构、网状结构
数据类型 Data type：int、float、char等
抽象数据类型 Abstract DataType：是指一个数学模型以及定义在该模型上的一组操作。
5. 算法的时间复杂度
抛弃特定的软硬件配置有关的因素，而使用指令的执行次数作为算法的时间度量单位，这种情况下，算法的时间和问题的规模n有关系，当n趋向于无穷大的是时间量级就称为时间复杂性，记做T(n)=O(f(n)),即T(n)是f(n)的同阶无穷大
例如，折半查找算法O（log底数2 n），也就是他需要通过log底数2 n量级步骤去检索一个规模为n的数组，记法O(f(n))表示当n增大时，运行时间将以正比于f(n)的速度增长。
第二章、线性存储结构
一、线性表的定义及基本操作
1.线性表概念
线性表是最简单常用的一种数据结构。线性表是具有相同类型的n个数据元素的有限序列。
在线性表中，元素之间存在着线性逻辑关系，即表中只有一个开始结点和一个终端结点；除了开始结点，其他结点均只有一个前驱节点；除了终端结点，其他结点均只有一个后继节点；线性表可以表示成n个元素组成的序列
线性表是个十分灵活的数据结构，可以在他的任意位置上插入或者删除数据元素，对线性表的主要操作有创建线性表，插入元素，删除元素和查找元素等。
2.线性表的抽象数据类型
线性表的抽象数据类型的定义：
ADT List{ 数据对象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
基本操作：
InitList(&l) 操作结果：构造一个空的线性表L
DestroyList(&l) 初始条件：线性表已存在 ； 操作结果：销毁线性表L
ClearList(&l) 初始条件：线性表已存在； 操作结果：置线性表L为空表
ListEmpty(L) 初始条件：线性表已存在； 操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE
ListLenght(L) 初始条件：线性表已存在 ；操作结果：返回线性表L数据元素个数
GetElem(L,i,&e) 初始条件：线性表已存在（1≤i≤ListLenght(L)）；操作结果：用e返回线性表L中第i个数据元素的值
locatElem(L,e,comare()) 初始条件：线性表已存在,comare()是数据元素判定函数；
操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序
PriorElem(L,cur_e,&pre_e)；初始条件：线性表已存在；操作结果：若cur_e是线性表L的数据元素，且不是第一个，
则用pre_e返回它的前驱，否则操作失败，pre_e无定义
NextElem(L,cur_e,&) 初始条件：线性表已存在； 操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，
则用next_e返回它的后继，否则操作失败，next_e无定义
ListInsert(&L,i,e) 初始条件：线性表已存在（1≤i≤ListLenght(L)+1）； 操作结果：在线性表L中第i个数据元素
之前插入新元素e，L长度加1
ListDelete(&L,i,&e) 初始条件：线性表已存在（1≤i≤ListLenght(L)）； 操作结果：删除线性表L中第i个数据元素，
用e返回其值，L长度减1
ListTraverse(L,visit()) 初始条件：线性表已存在； 操作结果：依次对线性表L的每个数据元素调用visit()函数，
一旦visit()失败，则操作失败
}ADT List二、线性表之-顺序存储结构
1.顺序存储结构定义
把线性表存储在一串连续的内存地址的结构，叫做顺序存储结构。
顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间，缺点是由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。例如，一年四季的顺序存储结构如图：
假设每个元素占用的空间为L个字节，则第n个元素的位置是：
Loc（an）= Loc（a1）+ L（n-1）
由此可见，只要知道第一个元素的位置就可以很快的找到表中任何一个元素。
采用顺序存储结构的线性表叫做顺序表。
2.顺序表的基本操作和实现
（1）建立顺序表：
假设元素为整形，长度为len
void CreatList (int *list，int len)
{
int value;
cout<<"请输入数据元素值: ";
for(int i=0;i<len;i++) //注意：组的下标从0开始
{ cin>>value;
list[i]=value;
}
}（2）查询顺序表
在顺序表中查找值为x的元素，若找到，则返回它在数组中的下标
int FindElement (int *list，int len，int x)
{
int i=0;
while（list[i]!=x&&i<len）
{i++;}
if (i==len)
{return (-1);}
else
{return (i+1);} //返回数组中的相对位置
}（3）顺序表插入
在第i个位置插入新元素x，
首先确定数组空间是否足够大，然后找到第i个位置； 并从最后一个元素开始项前直到第i个元素，依次向后移动一位，最后将新元素存储到第i个位置上
int InsertElement (int *list，int *len，int x，int i)
{
int k;
if(*len>=MaxSize)
{cout<<"表已满,无法插入!"<<endl; return（-1）; }
else if(i<0||i>*len)
{cout<<"参数i不合理!"<<endl; return（-1）; }
else if(i==*len)
{list[i]=x; } //插入到最后一个元素之后
else {
for(k=*len;k>i;k--)
{ list[k]=list[k-1]; }
list[i]=list[i-1];
list[i-1]=x; //插入第i个位置
}
*len=*len+1；
return （1）;
}（4）顺序表删除
删除值为X的元素，假设表中只有一个。
查找位置，确保下标不会超出线性表的范围；找到后，从它之后的元素开始一次向前移，把数值写入前一个存储单元，直到最后一个元素，最后将长度减一。
int DeleteElement (int *list，int *len，int x)
{
int Loc，i=0;
while (list[i]!==x&&i<*len)
{
i ++;
}
if (i==*len)
{
return -1; //未找到
}
else
{
Loc=i;
for (i=Loc; i<*len; i++)
{
list[i]=list[i+1];
*len=*len-1;
}
}
return (Loc+1); //返回被删除结点在表中的相对位置
}删除值为X的元素，假设表中有多个
int DeleteFullElement (int *list，int *len，int x)
{
int Loc，i;
for(i=0;i< *len; i++) //从第一个开始查找x
{
if （list[i]==x） //找到一个x删除
{
for (Loc=i; Loc<*len;Loc++)
{
list[Loc]=list[Loc+1];
*len=*len-1;
i=i-1；
}
}
}
return;
}应用：将两个顺序表a和顺序表b组合成一个新顺序表c，其中，a和b都是生序排列的，要求c的元素也是升序排列。假设c足够长
思路：依次扫描顺序表a、b中相对位置上的元素，并比较大小，将小的直赋给c，重复这个步骤直到其中一个表的所有元素都扫描完，将另一个数组的剩余部分直接接到c的末尾
int MergeOrder(int *a,int *b,int *c,int lena,int lenb)
{
int i=0，j=0，k=0;
while (i<lena&&j<lenb) //同时扫描a，b比较大小
{ if(a[i]<b[i])
{ c[i]=a[i];i++;}
else
{ c[i]=b[j];j++;}
k++;
}
if(i==lena) //a先扫描完
{
for (j=lena; j<lenb ;j++) //将b的剩余元素接到c的末尾
{c[j]=b[j];}
return (lenb);
}
if(j==lenb) //b先扫描完
{
for (i=lenb; i<lena ;i++) //将a的剩余元素接到c的末尾
{c[i]=a[i];}
return (lena);
}
}三、线性表之-链式存储结构
链表将数据成串链接起来，以形成其他结构，例如堆栈，队列，树状结构，二叉树结构，图形结构等。
链表包括：单链表，双链表、循环链表三种基本模式
1、链式存储结构
链接存储结构是将结点所占的存储单元分为两部分，一部分存放结点本身的信息，即数据项。另一部分存放该结点的后续结点所对应的存储单元的地址，即为指针项。
优点是不会出现碎片现象，在链表中差入或者删除数据时，只需要修改指针即可，从而避免顺序存储中数据大量移动的问题；缺点是每个结点占用较多的存储空间，并且由于在物理位置上并不相邻，因此它不像顺序存储那样可以随机访问结点。例如，一年四季的链接存储结构如图:
即，每个数据元素除了存储自身的信息之外，还要存储指向直接后继元素或直接前驱元素位置的部分——指针域。这两部分信息组成了数据元素的存储映像称为结点。
用链式存储结构存储的线性表也成为“链表”。
逻辑上相邻的两个结点其存储的物理位置不要求相邻，可以随意的存放在内存中的任何空闲地方
链表是一种动态存储结构，在需要插入一个结点时，按结点的类型像系统申请一个结点的存储空间；当删除一个结点时，就将这个结点的存储空间释放，他比顺序表的静态存储方式更灵活高效。
2.单链表及基本操作
定义
单链表结点由两部分组成：一部分是该结点的数值，这个值可以是任意类型如int、float、double等；另一个是指向后继结点的指针。单链表结点只有一个数据域和指针域
#include <stdio.h>
typedef struct Node
{
ElemType data; //单链表中的数据域
struct Node *next; //单链表的指针域
}Node; 通常把链表画成用箭头相连的结点序列，结点之间的箭头表示指针。
访问单链表的任何节点必须由头指针出发（h=1），按照指针域依次向后访问节点并进行处理。单链表可以由头指针唯一确定，故单链表可以用头指针的名字来命名。
最后一个结点没有后继结点，因此它的指针域为空，记做null
单链表的基本操作：
（1）单链表的建立
生成一个带头结点的单链表（长度为len，数值类型为整形）
NODE *creatLink （int len） //建立链表返回链表头指针
{
NODE *h,*p,*s;
p=h=(NODE *)malloc(sizeof(NODE)); //建立头结点
h - >next=NULL; //空链表
for (int i=1;i<=len;i++)
{
s=（NODE *）malloc (sizeof(NODE));
scanf(“%d”，&s ->data);
s ->next=NULL;
p ->next=s;
p=s;
}
return h;
}（2）求表长
（3）取元素
（4）输出链表
（5）插入结点
（6）删除结点
（7）销毁链表
（8）逆置链表
楼楼有时间再总结这些代码……
3.循环链表及基本操作
定义
将链表最后的一个结点的指针域指向头结点，从而形成一个环状。由此，从表中任意一结点出发都可以访问到表中其他的结点。这种结构叫最循环链表。
#include <stdio.h>
typedef struct Node
{
ElemType data; //循环链表中的数据域
struct CNode *next; //循环链表的指针域
}CNODE; 循环列表需要将尾结点的指针域等于头指针；
在插入操作过程中如果在最后一个结点之后插入结点，则需要将头指针的值赋值给新结点的指针域；
在删除操作过程中如果在最后一个结点之后插入结点，则需要将头指针的值赋值给倒数第二个结点的指针域；
输出操作和计算链表长度操作都需要检查当前结点的指针域是否等于头指针，如果是说明循环结束；
循环链表的基本操作：
（1）循环链表的建立
生成一个带头结点的循环链表（长度为len，数值类型为整形）
CNODE *creatLink （int len） //建立链表返回链表头指针
{
CNODE *h,*p,*s;
p=h=(CNODE *)malloc(sizeof(CNODE)); //建立头结点
h - >next=NULL; //空链表
for (int i=1;i<=len;i++)
{
s=（CNODE *）malloc (sizeof(CNODE));
scanf(“%d”，&s ->data);
s ->next=NULL;
p ->next=s;
p=s;
}
P ->next=h; //尾指针指向头结点
return h;
}（2）取元素
（3）插入结点
（4）删除结点
（5）定位操作
（6）两个循环链表合并
楼楼有时间再总结这些代码……
循环列表不适用于需要经常访问前趋结点的情况，于是有了下面的双链表
4.双链表及基本操作
定义
每个结点包含两个指针域：一个指向前趋结点，另一个指向后继结点；这种结构可以方便的向前访问结点；
尤其在删除过程中，单链表需要两个指针，一个指向需要删除的结点。一个指向该结点的前驱节点，双链表只需要一个指针指向目标位置，利用结点自带的两个指针完成操作
#include <stdio.h>
typedef struct dNode
{
Datatype data; //双链表中的数据域
struct dNode *next; //双链表的后继指针域
struct dNode *prev; //双链表的前驱指针域
}DNODE; 双链表的基本操作：
（1）双链表的建立
生成一个带头结点的双链表（长度为len，数值类型为整形）
DNODE *creatLink （int len） //建立链表返回链表头指针
{
DNODE *h,*p,*s;
p=h=(DNODE *)malloc(sizeof(DNODE)); //建立头结点
h - >next=NULL; //空链表
h - >prev=NULL;
for (int i=1;i<=len;i++)
{
s=（DNODE *）malloc (sizeof(DNODE));
scanf(“%d”，&s ->data);
s ->next=NULL;
s ->prev=p;
p ->next=s;
p=s;
}
return h;
}（2）插入结点
（3）删除结点
楼楼有时间再总结这些代码……
5.循环双链表及基本操作
将尾结点的next指针指向头结点，将头结点的prev指针指向尾结点
题库：
- 线性表示具有有限个数据元素的序列。
- 顺序存储结构的优点：
可以通过数据元素的相对存储地址随机地读取元素，时间的复杂度为O（1）；
缺点：在删除和插入元素时，需要大量移动元素 - 顺序表中长度为n时插入或者删除一个数据元素所需要的时间复杂度为O(n)，需要移动的元素个数平均为n/2
- 在单链表中访问一个结点必须要从头结点逐个遍历，时间复杂度为O（n），因此链表不具备随机存储的功能，但是在插入和删除结点的时候不需要移动数据元素，只需要修改结点的NEXT 指针即可
- 判断循环列表是否遍历完全的条件是指针是否指向头结点
- 序列是线性表
- 输出某个位置的数据值在顺序表上比在链表上实现的效率高
- 设一个链表最常用的操作是在末尾插入结点和删除结点，则选用带尾指针的单循环链表和头结点带前指针的循环双链表最节省时间。
- 链表存储结构适用于需要频繁的插入和删除结点操作，并且存储空间大小不能预先确定
- 双向链表适用于频繁访问前驱和后继结点的时候 11.