2015年初级软考辅导:程序员数据结构笔记（一）
发布时间：2010/3/13 14:15:31 来源：城市学习网 编辑：MOON
能听到周SIR讲课真的挺开心的，我觉得他讲课比某些高程还深动，为了考中程，上学期的<算法分析>选修课我也去揍了揍热闹.可惜由于SARS的关系，课只上了将近一半就停了.可以说我报程序员的原因就是因为有周SIR开导我们，听他的课真的是一种享受，不像大学里的某些人，水平不怎么高还在这里作威作福.
好了，发了这么多劳骚，开始转入正题了.
读这文章的人想必都是想报考或者将考程序员的同志们吧!首先一点必须问问自己，我考程序员的目的到底是为了什么?如果你的答案是:"只是为了拿一本证书".那我劝你早点GIVEUP吧!那样学起来会很累，因为没有兴趣.如果你想加入程序员的行列，为将来开发打下坚实的基础，那就试着看完这一小篇读书笔记吧!或许会对你有所帮助.
有句话必须记住:程序员考试仅仅是为了检验自己学到的而已，仅此而已!我想这便是程序员考试的最终意义所在吧!有些事情更注重过程!
数据结构
知识:
1.数据结构中对象的定义，存储的表示及操作的实现.
2.线性:线性表、栈、队列、数组、字符串（广义表不考）
树：二叉树
集合：查找，排序
图
能力：
分析，解决问题的能力
过程：
确定问题的数据。
确定数据间的关系。
确定存储结构（顺序－数组、链表－指针）
确定算法
编程
算法评价（时间和空间复杂度，主要考时间复杂度）
一、数组
1、存放于一个连续的空间
2、一维～多维数组的地址计算方式
已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。
公式：（add+S)
注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3]和情况；
3、顺序表的定义
存储表示及相关操作
4、顺序表操作中时间复杂度估计
5、字符串的定义（字符串就是线性表），存储表示
模式匹配算法（简单和KMP（不考））
6、特殊矩阵：存储方法（压缩存储（按行，按列））
三对角：存储于一维数组
三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。
7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）
算法
数组中元素的原地逆置；对换
在顺序表中搜索值为X的元素；
在有序表中搜索值为X的元素；（折半查找）
在顺序表中的第i个位置插入元素X；
在顺序表中的第i个位置删除元素X；
两个有序表的合并；算法？
线性表数据结构定义：
Typedefstructlinear_list;
模式匹配
字符串相加
求子串
（i，j）<=>K注意：不同矩阵所用的公式不同；
稀疏矩阵的转置（两种方式，后种为妙）
和数组有关的算法
例程：求两个长整数之和。
a=13056952168
b=87081299
数组:
a:13056952168
b:87081299
由于以上的结构不够直观将其改为:
a:1186125965031a[0]=11
b:899218078000b[0]=8
c进位01100111100
c:1176433044231c[0]的值由c[max_s+1]决定!
注意:在求C前应该将C位赋0.否则为随机数;较小的整数高位赋0.
算法:已知a，b两个长整数，结果:c=a+b;
总共相加次数:max_s=max
程序:
for
求c位数:
if
c[0]=max_s;
else
c[0]=max_s+1;
以下代码是我编的:
/两长整数相加/
#include<stdio.h>
#include<string.h>
#definePRINprintf;
intflag=0;/a[0]>b[0]?1:0/
/max/
change
else
}
add
if
c[0]=a[0];
else
c[0]=a[0]+1;
}
else
if
c[0]=b[0];
else
c[0]=b[0]+1;
}
}
voidprint
main;
chardb=;
a[0]=strlen;
b[0]=strlen;
printf;
printf;PRIN
change;
printf;PRIN
printf;
if
else
add;
printf;
print;
}
时间复杂度计算:
确定基本操作
计算基本操作次数
选择T
lim/T)=c
0)为时间复杂度
上例子的时间复杂度为O;
二:链表
1、知识点
逻辑次序与物理次序不一致存储方法；
单链表的定义：术语（头结点、头指针等）
注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带头结点，因为稍难理解）
插入、删除、遍历（p==NULL表明操作完成）等操作
循环链表：定义，存储表示，操作；
双向链表：定义，存储方法，操作；
单链表和循环链表区别在最后一个指针域值不同。
2、操作
单链表：插入X，删除X，查找X，计算结点个数
单链表的逆置（中程曾考）
head->NULL/p->a1/p->a2/p->a3/p……an/NULL注：p代表指针;NULL/p代表头结点
＝》head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL
循环链表的操作：插入X，删除X，查找X，计算结点个数；
用p=head->next来判断一次计算结点个数完成；
程序段如下：
k=0;
dowhile;
双向链表
多项式相加
有序链表合并
例程：已知两个字符串S，T，求S和T的最长公子串；
1、逻辑结构：字符串
2、存储结构：数组
3、算法：精化（精细化工）老顽童注：此处“精细化工”说明好像不对！
s="abaabcacb"
t="abdcabcaabcda"
当循环到s.len-1时，有两种情况：s="abaabcacb"、s="abaabcacb"
s.len-2时，有三种情况：s="abaabcacb"、s="abaabcacb"、s="abaabcacb"
.
.
.
1s.len种情况
程序思路：
tag=0//没有找到
for
长度为l的s的子串在s中有（s.len-l+1）个。
子串0:0～l-1
1:1～l
2:2～l+1
3:3～l+2
……
……
s.len-l:s.len-l～s.len-1
由上面可得：第j个子串为j～l+j-1。
判断长度为l的s中的子串是否为t的子串:
for
模式结构：
tag=0;
for
}
