第一章 概 论************************************************************************
数据就是指能够被计算机识别存储和加工处理的信息的载体
数据元素是数据的基本单位可以由若干个数据项组成数据项是具有独立含义的最小标识单位
************************************************************************
数据结构的定义·逻辑结构从逻辑结构上描述数据独立于计算机·线性结构一对一关系
·线性结构多对多关系
·存储结构是逻辑结构用计算机语言的实现·顺序存储结构如数组
·链式存储结构如链表
·索引存储结构·稠密索引每个结点都有索引项
·稀疏索引每组结点都有索引项
·散列存储结构如散列表
·数据运算·对数据的操作定义在逻辑结构上每种逻辑结构都有一个运算集合
·常用的有检索插入删除更新排序
************************************************************************
数据类型是一个值的集合以及在这些值上定义的一组操作的总称·原子类型由语言提供
·结构类型由用户借助于描述机制定义是导出类型
抽象数据类型ADT·是抽象数据的组织和与之的操作相当于在概念层上描述问题
·优点是将数据和操作封装在一起实现了信息隐藏
************************************************************************
程序设计的实质是对实际问题选择一种好的数据结构设计一个好的算法算法取决于数据结构
************************************************************************
算法是一个良定义的计算过程以一个或多个值输入并以一个或多个值输出
评价算法的好坏的因素·算法是正确的
·执行算法的时间
·执行算法的存储空间（主要是辅助存储空间）
·算法易于理解编码调试
************************************************************************
时间复杂度是某个算法的时间耗费它是该算法所求解问题规模n的函数
渐近时间复杂度是指当问题规模趋向无穷大时该算法时间复杂度的数量级
评价一个算法的时间性能时主要标准就是算法的渐近时间复杂度
算法中语句的频度不仅与问题规模有关还与输入实例中各元素的取值相关
时间复杂度按数量级递增排列依次为常数阶O()对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n^)立方阶O
(n^)……k次方阶O(n^k)指数阶O(^n)
空间复杂度是某个算法的空间耗费它是该算法所求解问题规模n的函数
算法的时间复杂度和空间复杂度合称算法复杂度
第二章 线性表
************************************************************************
线性表是由n≥个数据元素组成的有限序列n=是空表非空表只能有一个开始结点有且只能有一个终端结点
************************************************************************
线性表上定义的基本运算·构造空表Initlist(L)
·求表长Listlength(L)
·取结点GetNode(Li)
·查找LocateNode(Lx)
·插入InsertList(Lxi)
·删除Delete(Li)
************************************************************************
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关
系是一致的地址计算LOCa(i)=LOCa()+(i)*d（首地址为）
在顺序表中实现的基本运算 ·插入平均移动结点次数为n/平均时间复杂度均为O(n)
·删除平均移动结点次数为（n）/平均时间复杂度均为O(n)
************************************************************************
线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同为了能正确表示结点间的逻辑关系在存储每个结点值的同时还存储
了其后继结点的地址信息(即指针或链)这两部分信息组成链表中的结点结构 一个单链表由头指针的名字来命名
************************************************************************
单链表运算·建立单链表·头插法s>next=headhead=s生成的顺序与输入顺序相反平均时间复杂度均为O(n)
·尾插法head=rear=nullif(head=null) head=s;else r>next=s;r=s; 平均时间复杂度均为O(n)
·加头结点的算法对开始结点的操作无需特殊处理统一了空表和非空表
·查找·按序号与查找位置有关平均时间复杂度均为O(n)
·按值与输入实例有关平均时间复杂度均为O(n)
·插入运算p=GetNode(Li)s>next=p>nextp>next=s平均时间复杂度均为O(n)
·删除运算p=GetNode(Li)r=p>nextp>next=r>nextfree(r)平均时间复杂度均为O(n)
************************************************************************
单循环链表是一种首尾相接的单链表终端结点的指针域指向开始结点或头结点链表终止条件是以指针等于头指针或尾指针
采用单循环链表在实用中多采用尾指针表示单循环链表优点是查找头指针和尾指针的时间都是O()不用遍历整个链表
************************************************************************
双链表就是双向链表就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior形成两条不同方向的链由头指针head惟一
确定
双链表也可以头尾相链接构成双(向)循环链表
双链表上的插入和删除时间复杂度均为O ()
************************************************************************
顺序表和链表的比较·基于空间 ·顺序表的存储空间是静态分配存储密度为适于线性表事先确定其大小时采用
·链表的存储空间是动态分配存储密度＜适于线性表长度变化大时采用
·基于时间 ·顺序表是随机存储结构当线性表的操作主要是查找时宜采用
·以插入和删除操作为主的线性表宜采用链表做存储结构
·若插入和删除主要发生在表的首尾两端则宜采用尾指针表示的单循环链表
第三章 栈和队列
************************************************************************
栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表称插入删除这一端为栈顶另一端称为栈底表中无元素时为空栈栈
的修改是按后进先出的原则进行的我们又称栈为LIFO表(Last In First Out)通常栈有顺序栈和链栈两种存储结构
************************************************************************
栈的基本运算有六种 ·构造空栈InitStack(S)
·判栈空: StackEmpty(S)
·判栈满 StackFull(S)
·进栈 Push(Sx)
·退栈 Pop(S)
·取栈顶元素StackTop(S)
************************************************************************
在顺序栈中有上溢和下溢的现象 ·上溢是栈顶指针指出栈的外面是出错状态
·下溢可以表示栈为空栈因此用来作为控制转移的条件
顺序栈中的基本操作有六种·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素
************************************************************************
链栈则没有上溢的限制因此进栈不要判栈满链栈不需要在头部附加头结点只要有链表的头指针就可以了
链栈中的基本操作有五种·构造空栈·判栈空·进栈·退栈·取栈顶元素
************************************************************************
队列(Queue)是一种运算受限的线性表插入在表的一端进行而删除在表的另一端进行允许删除的一端称为队头(front)允许插入的
一端称为队尾(rear) 队列的操作原则是先进先出的又称作FIFO表(First In First Out) 队列也有顺序存储和链式存储两种存储结
构
************************************************************************
队列的基本运算有六种 ·置空队InitQueue(Q)
·判队空QueueEmpty(Q)
·判队满QueueFull(Q)
·入队EnQueue(Qx)
·出队DeQueue(Q)
·取队头元素QueueFront(Q)
************************************************************************
顺序队列的假上溢现象由于头尾指针不断前移超出向量空间这时整个向量空间及队列是空的却产生了上溢现象
为了克服假上溢现象引入循环向量的概念是把向量空间形成一个头尾相接的环形这时队列称循环队列
判定循环队列是空还是满方法有三种 ·一种是另设一个布尔变量来判断
·第二种是少用一个元素空间入队时先测试（(rear+)%m = front）? 满空
·第三种就是用一个计数器记录队列中的元素的总数
********************
