软考程序员数据结构笔记.doc

《软考程序员数据结构笔记.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软考指南：程序员数据结构笔记1.数据结构中对象的定义,存储的表示及操作的实现.　　2.线性:线性表、栈、队列、数组、字符串（广义表不考）　　　树：二叉树　　　集合：查找，排序　　　图(不考)能力：　　分析，解决问题的能力过程：　　● 确定问题的数据。　　● 确定数据间的关系。　　● 确定存储结构（顺序－数组、链表－指针）　　● 确定算法　　● 编程　　● 算法评价（时间和空间复杂度，主要考时间复杂度）一、数组　　1、存放于一个连续的空间　　2、一维～多维数组的地址计算方式　　已知data[0][0]的内存地址，且已知一个元素所占内存空

2、间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求A

3、ij。　　7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考） 　　算法　　● 数组中元素的原地逆置； 对换　　● 在顺序表中搜索值为X的元素；　　● 在有序表中搜索值为X的元素；（折半查找）　　● 在顺序表中的第i个位置插入元素X；　　● 在顺序表中的第i个位置删除元素X；　　● 两个有序表的合并；算法？　　线性表数据结构定义：　　　Typedef struct {　　　　int data[max_size];　　　　int len;　　　}linear_list;　　● 模式匹配　　● 字符串相加　　● 求子串　　

4、● （i,j）<=>K 注意：不同矩阵所用的公式不同；　　● 稀疏矩阵的转置（两种方式，后种为妙）　　● 和数组有关的算法 --------------------------------------------------------------------------------　　例程：求两个长整数之和。　　a=　　b=　　数组:　　a[]:1 3 0 5 6 9 5 2 1 6 8　　b[]:8 7 0 8 1 2 9 9 　　由于以上的结构不够直观(一般越是直观越容易解决)将其改为:　　a[]:11　86125965031a

5、[0]=11(位数)　　b[]:8　99218078000b[0]=8　　c进位　01100111100　　c[]:11　76433044231c[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%10;　　　c[i+1]=k/10;　

6、　}　　求c位数:　　if(c[max_s+1]==0)　　　c[0]=max_s;　　else　　　c[0]=max_s+1;　　以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!):　　/*两长整数相加*/　　#include　　#include　　#definePRINprintf("");　　intflag=0;/*a[0]>b[0]?1:0*/　　/*max(a[],b[]){}*/　　change(charda[],chardb[],inta[],intb[],intc[]){　　

7、　inti;　　　if(a[0]>b[0]){　　　　for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++);/*a[0]-'0'sogood!*/　　　　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++)

8、;　　　　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]=