数据结构
知识:
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(位数) b[]: 8 9 9 2 1 8 0 7 8 0 0 0 b[0]=8
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.否则为随机数; 较小的整数高位赋算法:已知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; }
求c位数:
if(c[max_s+1]==0) c[0]=max_s; else
c[0]=max_s+1;
以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!): /*两长整数相加*/ #include
#define PRIN printf(\int flag=0; /*a[0]>b[0]?1:0*/
c进位 0 1 1 0 0 1 1 1 1 0 0 0.
/* max(a[],b[]) {}*/
change(char da[],char db[],int a[],int b[],int c[]) { int i;
if(a[0]>b[0]) {
for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); /*a[0]-'0' so good!*/
for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=b[0]+1;i<=a[0];b[i]=0,i++); for(i=1;i<=a[0]+1;c[i]=0,i++); flag=1; }
else {
for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); for(i=a[0]+1;i<=b[0];a[i]=0,i++); for(i=1;i<=b[0]+1;c[i]=0,i++); } }
add(int a[],int b[],int c[]) { int i,sum; if(flag==1) {
for(i=1;i<=a[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum; }
if(c[a[0]+1]==0) c[0]=a[0]; else
c[0]=a[0]+1; }
else {
for(i=1;i<=b[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum; }
if(c[b[0]+1]==0) c[0]=b[0]; else
c[0]=b[0]+1; }
}
void print(int m[]) { int i;
for(i=m[0];i>=1;i--)
printf(\ }
main(){ int s;
int a[20],b[20],c[20]; char da[]={\ char db[]={\ a[0]=strlen(da); b[0]=strlen(db);
printf(\ printf(\ change(da,db,a,b,c);
printf(\ printf(\ if(flag==1) { print(a); PRIN s=abs(a[0]-b[0]); printf(\
for(s=s*2-1;s>0;s--) printf(\ print(b); PRIN }
else {
s=abs(a[0]-b[0]); printf(\
for(s=s*2-1;s>0;s--) printf(\ print(a); PRIN print(b); PRIN }
add(a,b,c);
printf(\ print(c); }
时间复杂度计算: ● 确定基本操作 ● 计算基本操作次数
● 选择T(n)
● lim(F(n)/T(n))=c ● 0(T(n))为时间复杂度
上例子的时间复杂度为O(max_s);
二:链表
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; do{ k++;
p=p->next;
}while(p!=head->next); ● 双向链表 ●多项式相加
● 有序链表合并
例程：已知两个字符串S，T，求S和T的最长公子串； 1、逻辑结构：字符串 2、存储结构：数组
3、算法： 精化（精细化工）**老顽童注：此处“精细化工”说明好像不对！
s=\ t=\
当循环到s.len-1时，有两种情况：s=\、s=\ s.len-2时，有三种情况：s=\、s=\、s=\ .