西电计算机系

《西电计算机系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、·西电计算机系2008专业课笔记¬------数据结构前言:用书<数据结构>清华大学出版社严蔚敏 范围章八不考双星号(4.3除外)不考章一章十一章十二只考概念 算法题语法不限 参考书近年真题(选择填空少了题目趋于简单习题集要做重在线性表查找排序二叉树)第一部分:基本概念一. D.S的概念1. 定义:关系2. 三要素:a逻辑结构(关系)b物理存储结构(元素,关系)c基本算法(定义在逻辑关系上,实现在物理结构上)3. 分类:线数图集合(以直接前驱,直接后继的关系来区分)4. 存储结构:a顺序(用一组地址连续空间…能随即访问)如cd机b链式(关系是显性表示顺序访问)如磁带c索

2、引d散列(hash)二. 算法概念1. 定义:解决问题方法的描述.2. 描述:可以是自然语言,也可以是高级语言3. 性质:有穷性确定性可行性输入输出4. 分析:时间空间(事后统计事前估计:基本语句执行次数的数量级)例:1.x=n;y=0 Whilex>0(y+1)+(y+1); y++; 问:时间复杂度O()  2.viodmain() { int y=0;intx=5/y Printf(x,y); } 分母为0违反了可行性不是算法O()不仅与数据规模有关,还与除态有关.如数据开始就是顺序排列的那么查找的时候的算法就可以比随即排列是快 3.判断正误  算法最终要用计算机

3、实现F  可行性:是指算法不能有二异性F(是说确定性)  同意算法实现语言越高效率越低T  原地工作:指不需要任何额外辅助空间F(需要但一定)第二部分:线性数据结构一. 线性表基础内容1. 逻辑关系定义:存在第一和最后元素,除第一个均有后继,除最后一个都有前驱2. 存储结构:顺序(关系不占空间)链式(占) 单链表:一指针表一关系 双链表:一指针表两个关系 循环链表:最后最前 头节点:在某些运算下使空表和非空表的操作一样3. 基本操作:插入,删除 顺序存储:时间花在移动中 链式存储:时间花在定位中(插入时改2条指针,删除时改1条)*在确定修改次序时可以采用画图时多引入指针

4、的方法 4.应用:(知道)一元多项式表示及加法 总结:书中的算法掌握基本算法二. 栈与队列1. 栈a. 定义:操作受限制的线性表(先进后出)b. 顺序栈及运算(入栈,出栈)Top:只是当前栈顶元素的下一位置   判断栈空:top==0   判断栈满:top==StackSize   判断栈厂:top   入栈:Sdata[Stop++]=x   出栈:Sdata[Stop--]=x   栈溢出问题:上溢出是错误数据会丢失应避免      下溢出不是错误   链栈:头指针和top指针为一个经常无头结点c. 应用:(知道)不同进制转换括号匹配回溯算法(迷宫)表达式求值递归2

5、. 队列’a. 定义:操作受限的线性表(先进先出)b. 顺序队列的基本操作Front:指示当前队列首元素所在位置Rear:指示当前队列尾元素的下一位置判断空:rear=front判断满:rear-front=QueueSize入队:Qdata[Qrear++]=x出队:Qdata[Qfront++]=x队列溢出问题:上溢出(真:队列中所有元素都有值假:队列因删除数据使f值变化,导致队列前面的地址不能储存数据.这样就浪费了地址空间)c. 循环队列(重点)为了解决假上溢的问题i牺牲一个存储空间rear==front队空(rear+1)%MaxSize==front队满ii计

6、数器count count==0空count==MaxSize满iii标志位tag  tag==0空tag==1满d. 链队列e. 特殊的线性表输入首先的双端队列表输入首先的双端队列表f. 应用不考:….这个就不用解释了吧…