考试网 >> IT认证 >> 水平 >> 程序员 >> 软考指南：程序员数据结构笔记1

发布时间：2006-06-28 01:51     点击：

   　1.数据结构中对象的定义,存储的表示及操作的实现.

　　2.线性:线性表、栈、队列、数组、字符串（广义表不考）

　　　树：二叉树

　　　集合：查找，排序

　　　图(不考)

能力：

　　分析，解决问题的能力

过程：

　　● 确定问题的数据。

　　● 确定数据间的关系。

　　● 确定存储结构（顺序－数组、链表－指针）

　　● 确定算法

　　● 编程

　　● 算法评价（时间和空间复杂度，主要考时间复杂度）

一、数组

　　1、存放于一个连续的空间

　　2、一维～多维数组的地址计算方式

　　已知data[0][0]的内存地址，且已知一个元素所占内存空间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求Aij。

　　7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考） 

　　算法

　　● 数组中元素的原地逆置； 对换

　　● 在顺序表中搜索值为X的元素；

　　● 在有序表中搜索值为X的元素；（折半查找）

　　● 在顺序表中的第i个位置插入元素X；

　　● 在顺序表中的第i个位置删除元素X；

　　● 两个有序表的合并；算法？

　　线性表数据结构定义：

　　　Typedef struct {

　　　　int data[max_size];

　　　　int len;

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。