上一篇：程序员:数据结构复习指导

程序员数据结构笔记(一)

1.数据结构中对象的定义,存储的表示及操作的实现.
　　2.线性:线性表、栈、队列、数组、字符串（广义表不考）
　　　树：二叉树
　　　集合：查找，排序
　　　图(不考)
能力：
　　分析，解决问题的能力
过程：
　　● 确定问题的数据。
　　● 确定数据间的关系。
　　● 确定存储结构（顺序－数组、链表－指针）
　　● 确定算法
　　● 编程
　　● 算法评价（时间和空间复杂度，主要考时间复杂度）
一、数组
　　1、存放于一个连续的空间
　　2、一维～多维数组的地址计算方式
　　已知data[0][0]的内存地址，且已知一个元素所占内存空间s求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(位数)
　　b[]: 8　9 9 2 1 8 0 7 8 0 0 0 b[0]=8
　　c进位　0 1 1 0 0 1 1 1 1 0 0
　　c[]:11　7 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位数)由c[max_s 1]决定!
　　注意:在求C前应该将C(max_s 1)位赋0.否则为随机数; 较小的整数高位赋0.
　　算法:已知a,b两个长整数,结果:c=a b;
　　总共相加次数: max_s=max(a[],b[])
　　程序:
　　for(i=1;i<=max_s;i ) {
　　　k=a[i] b[i] c[i];
　　　c[i]=k;
　　　c[i 1]=k/10;
　　}
　　

下一篇：『软考』SQL的基本操作

↓相关文章：