西安电子科技大学2007年数据结构辅导笔记
数据结构部分:王卫东主讲（我去年十一上西电上的辅导班笔记，希望对大家有帮助）
第一章 绪论
一，数据结构:数据元素之间的关系（集合）
三要素:逻辑结构，物理结构，运算（定义在逻辑，实现在物理）
二，算法
1，定义:解决某个问题的描述
2，性质:确定性，可行性，有穷性，输入，输出
3，时间复杂度
n->无穷 算法中基本操作的执行次数最高数量级
第二章 线性表
一，定义
二，存储结构 {1，顺序:随机访问 2，链式，顺序访问}
三，运算 插入，删除，查找 等
第三章 栈和队列
栈
存储:顺序栈（注意溢出问题） 链栈（下溢出）
队列
存储:循环队列 front = (front+1)%maxsize
解决空与满 1，空 rear = front
2，满 front = (rear+1)%maxsize
第四章 串
主要是顺序存储
KMP算法
0 当 j = 1
max{k|p1...pk-1 = pj-k+1...pj-1 pj !=pk
改进KMP算法 =>netval {nexval[k] 当p1...pk-1 = pj-k+1...pj-1,pj=pk
1 其他情况但 pj != p1时
0 其他情况但pj = p1时
上边的式子希望大家能看懂！
第五章 数组和广义表
一，同构
计算地址 aij-->A[k]
ij-->k的对应
广义表要求:长度，深度 运算:取头，取尾
题:
1，求 a,b,c,a,a,b,b,c,a,b,c,a,a,b,d,a,b 的next和nextval的值
next 0,1,1,1,2,2,3,1,1,2,3,4,5,6,7,1,2
nexval0,1,1,0,2,1,3,1,0,1,1,0,2,1,7,0,1
2,A[0...5,0...6]中每个元素占15个字节，按列优先
A[5，5]地址___起始地址为1000
3，广义表 L = ((x,y,z),a,(u,t,w))
从中取出u
第六章 树和二叉树
注:**为重点
一，二叉树
1，树的定义，递归，一对多
2，二叉树的定义
3，性质
1）2的i-1次幂个结点，证明时用归纳
2）最多2的k-1个结点
**3）n0 = n2+1
例:N个结点K条边（N>K)____棵树
完全二叉树
4）h 的式子，不好往上打，书上有
4，存储
1）顺序存储
2）链式存储
5，基本操作:遍历
6，应用
1）线索二叉树:是一种存储结构，应用:找某个结点直接前驱
若p-->ltag = 1 则 p-->lchild为前驱
否则 其左子树的最右结点既是
后序线索书找*P的后继，parent指示*P的双亲，parent指针随P的移动而移动
1）若*P是根，则无后继
2）若*P是其parent的右孩子，其后继是其双亲
3）若*P是parent的左孩子且无右兄弟，则parent为后继
4）若*P是parent的左孩子且有右兄弟，其双亲右子树最左下的叶子结点即是
例题:
1，一个完全二叉树有768个结点，则叶子结点的个数是多少？
2，一个有124个叶子结点的完全二叉树，最多有多少个结点
3，二叉树有50个叶子结点，这二叉树结点总数最少是多少？
4，编号为i,j的完全二叉树上处在同一层的条件
5，在任何一个二叉树中，叶子结点在前，中，后的遍历序列中相对顺序是否发生改变？答:相对次序不会改变
今天就先打到这，有时间我在补充，后边相对多一些，也比较难打！
欢迎来到免费考研网www.freekaoyan.com |
[复制链接]
