程序员数据结构笔记（一）

能听到周 SIR讲课真的挺开心的,我觉得他讲课比某些高程(高级工程师)还深动(当然,他的数据结构水平应该不亚于高程),为了考中程,上学期的<算法分析 >选修课我也去揍了揍热闹.可惜由于SARS的关系,课只上了将近一半就停了.可以说我报程序员的原因就是因为有周SIR开导我们,听他的课真的是一种享受,不像大学里的某些人,水平不怎么高还在这里作威作福.
　　好了,发了这么多劳骚,开始转入正题了.
　　读这文章的人想必都是想报考或者将考程序员的同志们吧!首先一点必须问问自己,我考程序员的目的到底是为了什么?如果你的答案是:"只是为了拿一本证书".那我劝你早点GIVE UP吧!那样学起来会很累,因为没有兴趣.如果你想加入程序员的行列,为将来开发打下坚实的基础,那就试着看完这一小篇读书笔记吧!或许会对你有所帮助.
　　有句话必须记住:程序员考试仅仅是为了检验自己学到的而已,而已!我想这便是程序员考试的最终意义所在吧!有些事情更注重过程!

数据结构

知识:
　　1.数据结构中对象的定义,存储的表示及操作的实现.
　　2.线性:线性表、栈、队列、数组、字符串（广义表不考）
　　　树：二叉树
　　　集合：查找，排序
　　　图(不考)
能力：
　　分析，解决问题的能力
过程：
　　● 确定问题的数据。
　　● 确定数据间的关系。
　　● 确定存储结构（顺序－数组、链表－指针）
　　● 确定算法
　　● 编程
　　● 算法评价（时间和空间复杂度，主要考时间复杂度）

一、数组
　　1、存放于一个连续的空间
　　2、一维～多维数组的地址计算方式
　　　已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。
　　　公式：（add+(i*12+j)*S)(假设此数组为data[10][12])
　　注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况；
　　3、顺序表的定义
　　　存储表示及相关操作
　　4、顺序表操作中时间复杂度估计
　　5、字符串的定义（字符串就是线性表），存储表示
　　　模式匹配算法（简单和KMP（不考））
　　6、特殊矩阵：存储方法（压缩存储（按行，按列））
　　　三对角：存储于一维数组
　　　三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。
　　7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）