文章来源: http://thunderfyc.wordpress.com.cn
算法 数据结构 问题 程序的关系
问题由模型作为内核，用替换方式将抽象概念具体化，形成描述来包装内核
模型由数据和解决方法构成，每个问题不同情况的表现组成成数据，通过统一的解决方法得到解决
算法是解决问题的一般化方法
数据结构是数据的组织形式
程序是用计算机语言，在数据结构上操作算法，利用计算机解决问题
数据结构
数据结构是独立于数据而存在，具有一定逻辑结构，支持在上面进行被允许的操作，如插入、删除、查找等
主要有 单元节点、散列、线性表、树、图
单元节点/元素
最基本元素，储存数据的直接单位
散列
元素相互独立，没有直接关系的结构 集合
唯一关系 元素在集合内
操作 插入 删除 查找某元素
集合的实现 数组 BST
Hash表
考虑集合的数组表示a[x]为x是否在集合中，这是一一对应的关系
Hash表将x用特征值t来表示 对于不同的x可能对应同一个t（即冲突），根据t来查找x
f(x) = t 的函数是hash函数， t为x的hash值
因为可能存在冲突 有不同的处理方法 通常用链表来存储不同的x
操作 插入 删除 查找
先计算f(x) 在对应的链表中操作， 好的hash函数可以让链表尽可能短， 达到理想效果
典型应用：记录庞大数字、字符串等，字典的实现
线性表
线性表中，元素线性排列，相邻元素有前驱后继的关系
操作 插入 删除 查找某元素 遍历 查找第k小
线性表实现 数组 链表
有序表
元素顺序排列，可以用二分查找某个元素，可以直接获取第k小，插入删除困难，适用于排序之后的静态操作
栈
先进后出，用于人工模拟递归操作，表达式处理，递归过程中获取解答和模拟类题目
队列
先进先出，用于宽度优先搜索
映射
在线性表上加以集合构造 a[]是一个数组,已经具备某种逻辑关系A。
b[i]表示b[]第i个元素在a中的位置，初始b[i]=i，通过对a[b[i]]的排序得到对应数组a’[]具有逻辑关系B，a[]中元素位置未改变过
指针操作
对于一个序列，在上面进行简单的指针移动，获得完全遍历求最优解
字符串
匹配
RK 将模式串用数字表示(hash)，然后通过移动将当前匹配单位的hash值计算出来，相等的时候，逐个判断
KMP P为模式串 S为正文，用R[p]表示最大的k 使得P[1..k] = P[m-k+1..m]，这样如果在p+1处匹配失败，可以直接移动k个单位，匹配的过程实际为O(n+m)
获得R[]的过程，对于R[p]，k = R[p-1]+1 如果P[k]不等于P[p]，k移动到R[k-1]上，继续匹配，否则R[p]=k，k右移
文章来源: http://thunderfyc.wordpress.com.cn
==================================================================================
1 对0..65535范围内的数字进行O(N)复杂度的排序
用t[i]表示等于i的元素有多少个 从0开始往后数即可
2 有一串数，找到两个的商最接近t的
将数排序之后 用两个指针l, r 如果a[l]/a[r] < t， 那么a[l+1]/a[r]可能更接近t， 至少比a[l]/a[r+1]接近；
反之亦然。最后l和r从1遍历到n之后，中途遇到的最优解即可
3 表达式处理
表达式 = 表达式 符号 表达式。只有当表达式为优先级最高的时候，才能把它转化为数字，替换，这个就是典型递归过程，
但是串的处理是顺序的，所以用栈操作，每次判断新压入栈的符号是否更高级，如果更高级 将前面的基础表达式计算。
==================================================================================
Hash
f_hash(x: dataType): int;
find(x: dataType): node;
{
t = f_hash(x);
s = hash[t];
while (s.data <> x)
{
s = s.next;
if (s = nil)
return nil;
}
return s;
}
ins(x: dataType);
{
t = f_hash(x);
s = hash[t];
if (s = nil)
{
new(hash[t]);
hash[t].data = x;
hash[t].next = nil;
return;
}
while (s.next <> nil)
s = s.next;
new(s.next);
s = s.next;
s.next = nil;
s.data = x;
}
del(x: dataType);
{
if (find(x) = nil)
return;
t = f_hash(x);
s = hash[t];
if (s.data = x)
{
hash[t] = s.next;
return;
}
p = s;
s = s.next;
while (s.data <> x)
{
p = s;
s = s.next;
}
p.next = s.next;
delete(s);
}
RK
RK(p:string, s:string): int;
{
pt = 0;
m[0] = 1;
for i <- 1 to p.len do
{
pt = (pt*26+p[i]) mod 29999;
m[i] = m[i-1]*26;
}
st = 0;
for i <- 1 to p.len do
{
st = (st*26+s[i]) mod 29999;
}
for i <- p.len+1 to s.len do
{
st = ((st - m[p.len]*s[i-p.len])*26+s[i]) mod 29999;
if (st = pt)
{
check one by one;
if ok
return i;
}
}
return -1;
}
KMP
pre(p: string);
{
j = 1; k = 0; next[1] = 0;
while (j < p.len)
{
if (k = 0 or p[j] = p[k])
{
j+1; k+1;
if (p[j] <> p[k])
next[j] = k
else
next[j] = next[k];
}
else
k = next[k];
}
}
KMP(p: string, s: string);
{
i = 1; j = 1;
while (j <= p.len and i <= s.len)
{
if (j = 0 or s[i] = p[j])
{
i+1; j+1;
}
else
j = next[j];
}
if (j > t.len)
return i;
else
return -1;
}
文章来源: http://thunderfyc.wordpress.com.cn
