|
程序员数据结构笔记
第一天
真想不到,第一次上课竟然会是"9.11"事件纪念日.美国竟然还是不改老毛病,伊拉克战争死了多少平民百姓啊?!!!在此请先为死难者默哀3分钟,老美如果再这样多管闲事下去,上帝会二度
惩罚美国人的啊！
能听到周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、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）
算法
● 数组中元素的原地逆置； 对换
● 在顺序表中搜索值为X的元素；
● 在有序表中搜索值为X的元素；（折半查找）
● 在顺序表中的第i个位置插入元素X；
● 在顺序表中的第i个位置删除元素X；
● 两个有序表的合并；算法？
线性表数据结构定义：
Typedef struct {
int data[max_size];
int len;
}linear_list;
● 模式匹配
● 字符串相加
● 求子串
● （i,j）<=>K 注意：不同矩阵所用的公式不同；
● 稀疏矩阵的转置（两种方式，后种为妙）
● 和数组有关的算法
例程：求两个长整数之和。
a=13056952168
b=87081299
数组:
a[]:1 3 0 5 6 9 5 2 1 6 8
b[]:8 7 0 8 1 2 9 9
由于以上的结构不够直观(一般越是直观越容易解决) 将其改为:
a[]:11 8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位数)
|
| |
