数据结构复习总结.doc
50墨值下载
数据结构复习总结
第壱章绪论
1
、 数据：是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理
的符合的总成。
2、 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3
、 数据项：是数据的不可分割的最小单位。（一个数据元素可由若干个数据项组成）
4、 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
5
、 数据的逻辑结构（即数据之间的相互关系）：线性结构、树形结构、图状结构、集合。（
4
种）
6、 数据的存储结构（物理结构）：顺序存储结构、链式存储结构。（2 种）
7
、 数据的四种基本的存储方法：顺序存储方法、链式存储方法、索引存储方法、散列存储方法。
8、 数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻
辑）结构，而算法的实现依赖于采用的存储结构。
9
、 存取结构：与存储结构是两个不同的概念。存取结构是在一个数据结构上对查找操作的时间性能的
一种描述，通常有两种存取结构：随机存取结构（例如顺序表）和顺序存取结构（例如单链表）
10、 算法的特征：有穷性、确定性、可行性、输入和输出。
11
、 算法的时间复杂度（计算）
第弐章线性表
1、 线性结构（这里指线性表的逻辑结构）的特点：在数据元素的非空有限集中，（1）存在唯一的“第
一元素”（2）存在唯一的“最后元素”（3）除“第一元素”外，集合中的每个元素均只有一个前驱（4）
除“最后元素”外，集合中的每个元素均只有一个后继
2
、 线性表：是具有相同数据类型的
n(n>=0)
个数据元素的有限序列，是最简单、最基本、也是最常用
的一种线性结构。
（1）表中元素具有逻辑上的顺序性；
（
2
）表中元素个数有限；
（3）表中元素都是数据元素；
（
4
）表中元素的数据类型都相同；
（5）表中元素具有抽象性。
3
、 线性表的长度：线性表中元素的个数
n(n>=0)
定义为线性表的长度，
n=0
时成为空表。
4、 线性表的存储结构（物理结构）有
顺序存储结构：顺序表（具有按数据元素的序号随机存取的特点，时间复杂度为
O(1)
）
链式存储结构：单链表（数据的存取方式为顺序存取）
其它存储结构：循环链表、双向链表、静态链表
5、 顺序表（线性表的顺序存储表示）的形式描述：
静态分配：
#define LISTSIZE 100 //
线性表存储空间的初始分配量
Typedef struct{
ElemType elem[LISTSIZE];
int length;
}Sqlist;
动态分配： #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //
线性表存储空间的分配增量
Typedef struct{
ElemType *elem; //
存储空间基址，指示线性表的基地址
int length; //当前长度，实际已存元素个数
int listsize; //
当前分配的存储容量
,
以
sizeof(ElemType)
为单位
} Sqlist;
6、 构造一个空的顺序表
Status InitList Sq(SqList &L){
L.elem=(ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!L.elem) exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
7、 在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0
int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){
i=1;
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e)) ++i;
if(i<=Length) return I;
else return 0;
}
算法的时间复杂度为 O( ListLength(L) )
8
、 顺序表中插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
//
在顺序表
L
的第
i
个元素之前插入新的元素
e,
of 31
50墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论