欢迎来到天天文库
浏览记录
ID:56767358
大小:82.50 KB
页数:24页
时间:2020-07-08
《软考程序员数据结构笔记.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]=
此文档下载收益归作者所有