西电计算机系2008专业课笔记¬------数据结构

前言:
用书 <数据结构> 清华大学出版社 严蔚敏
 范围 章八 不考 双星号(4.3除外) 不考 章一章十一章十二 只考概念
 算法题 语法不限
 参考书 近年真题(选择填空少了 题目趋于简单 习题集要做 重在线性表 查找排序 二叉树)

第一部分: 基本概念

一. D.S的概念
1. 定义: 关系
2. 三要素: a 逻辑结构(关系) b 物理存储结构(元素,关系) c 基本算法(定义在逻辑关系上,实现在物理结构上)
3. 分类: 线 数 图 集合 (以直接前驱,直接后继的关系来区分)
4. 存储结构: a 顺序(用一组地址连续空间…能随即访问) 如cd机 b 链式 (关系是显性表示 顺序访问) 如磁带 c 索引 d 散列(hash)
二. 算法概念
1. 定义: 解决问题方法的描述.
2. 描述: 可以是自然语言,也可以是高级语言
3. 性质: 有穷性 确定性 可行性 输入 输出
4. 分析: 时间 空间(事后统计 事前估计:基本语句执行次数的数量级)

例: 1. x=n;y=0
  While x>0(y+1)+(y+1);
  y++;
 问:时间复杂度 O( )
 
 2. viod main()
 {
 int  y=0;
int x=5/y
  Printf(x,y);
 }
 分母为0 违反了可行性 不是算法

O()不仅与数据规模有关,还与除态有关.如 数据开始就是顺序排列的 那么查找的时候的算法 就可以比随即排列是快

 3.判断正误
  算法最终要用计算机实现 F
  可行性:是指算法不能有二异性 F(是说确定性)
  同意算法实现语言越高效率越低 T
  原地工作:指不需要任何额外辅助空间 F(需要但一定)
第二部分: 线性数据结构

一. 线性表基础内容
1. 逻辑关系定义:存在第一和最后元素,除第一个均有后继,除最后一个都有前驱
2. 存储结构: 顺序(关系不占空间) 链式(占)
 单链表:一指针表一关系
 双链表:一指针表两个关系
 循环链表:最后 最前
 头节点:在某些运算下使空表和非空表的操作一样
3. 基本操作: 插入,删除
 顺序存储: 时间花在移动中
 链式存储: 时间花在定位中(插入时改2条指针,删除时改1条)
*在确定修改次序时 可以采用画图时多引入指针的方法
 4. 应用: (知道)一元多项式表示及加法
 总结: 书中的算法掌握基本算法
二. 栈与队列
1. 栈
a. 定义: 操作受限制的线性表(先进后出)
b. 顺序栈及运算(入栈,出栈)
Top:只是当前栈顶元素的下一位置
   判断栈空:top==0
   判断栈满:top==StackSize
   判断栈厂:top
   入栈: S data[S top++] = x
   出栈: S data[S top--] = x
   栈溢出问题: 上溢出 是错误 数据会丢失 应避免
      下溢出 不是错误
   链栈: 头指针和top指针为一个 经常无头结点
c. 应用: (知道)不同进制转换 括号匹配 回溯算法(迷宫) 表达式求值 递归
2. 队列’
a. 定义: 操作受限的线性表(先进先出)
b. 顺序队列的基本操作
Front: 指示当前队列首元素所在位置
Rear: 指示当前队列尾元素的下一位置
判断空: rear=front
判断满: rear-front=QueueSize
入队: Q data[Q rear++]=x
出队: Q data[Q front++]=x
队列溢出问题: 上溢出(真:队列中所有元素都有值 假: 队列因删除数据使f值变化,导致队列前面的地址不能储存数据.这样就浪费了地址空间)
c. 循环队列(重点)
为了解决假上溢的问题
i牺牲一个存储空间 rear==front 队空 (rear+1)%MaxSize==front 队满
ii 计数器 count count==0 空 count==MaxSize 满
iii 标志位 tag  tag==0 空 tag==1 满
d. 链队列
e. 特殊的线性表
输入首先的双端队列表
输入首先的双端队列表
f. 应用
不考:….这个就不用解释了吧…