文档介绍：前言:用书<数据结构>清华大学出版社严蔚敏 范围章八不考双星号()不考章一章十一章十二只考概念 算法题语法不限 参考书近年真题(选择填空少了题目趋于简单****题集要做重在线性表查找排序二叉树)第一部分:基本概念一. . 定义:关系2. 三要素:a逻辑结构(关系)b物理存储结构(元素,关系)c基本算法(定义在逻辑关系上,实现在物理结构上)3. 分类:线数图集合(以直接前驱,直接后继的关系来区分)4. 存储结构:a顺序(用一组地址连续空间…能随即访问)如cd机b链式(关系是显性表示顺序访问)如磁带c索引d散列(hash)二. 算法概念1. 定义:. 描述:可以是自然语言,也可以是高级语言3. 性质:有穷性确定性可行性输入输出4. 分析:时间空间(事后统计事前估计:基本语句执行次数的数量级)例:=n;y=0 Whilex>0(y+1)+(y+1); y++; 问:时间复杂度O()  () { int y=0;intx=5/y Printf(x,y); } 分母为0违反了可行性不是算法O()不仅与数据规模有关,   算法最终要用计算机实现F  可行性:是指算法不能有二异性F(是说确定性)  同意算法实现语言越高效率越低T  原地工作:指不需要任何额外辅助空间F(需要但一定)第二部分:线性数据结构一. 线性表基础内容1. 逻辑关系定义:存在第一和最后元素,除第一个均有后继,除最后一个都有前驱2. 存储结构:顺序(关系不占空间)链式(占) 单链表:一指针表一关系 双链表:一指针表两个关系 循环链表:最后最前 头节点:在某些运算下使空表和非空表的操作一样3. 基本操作:插入,删除 顺序存储:时间花在移动中 链式存储:时间花在定位中(插入时改2条指针,删除时改1条)*在确定修改次序时可以采用画图时多引入指针的方法 :(知道)一元多项式表示及加法 总结:书中的算法掌握基本算法二. 栈与队列1. 栈a. 定义:操作受限制的线性表(先进后出)b. 顺序栈及运算(入栈,出栈)Top:只是当前栈顶元素的下一位置   判断栈空:top==0   判断栈满:top==StackSize   判断栈厂:top   入栈:Sdata[Stop++]=x   出栈:Sdata[Stop--]=x   栈溢出问题:上溢出是错误数据会丢失应避免      下溢出不是错误