文档介绍：第一章数据结构
数据结构是计算机存储、组织数据的方式。数据结构是抽象数据类型的物理实现。
:
数据元素之间的逻辑关系,即数据的逻辑结构。
数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。
施加在该数据上的操作,即数据的运算。
集合结构。交通工具的集合,动物的集合
线性结构。一对一,综合素质测评产生的学生排名
树形结构。一对多,单位的组织结构图,族谱
图形结构。多对多,生产流程、施工计划、网络建设图等
顺序存储方法。数组
链式存储方法。链表
索引存储方法
散列存储方法
通常把具体存储结构上的操作实现步骤或过程称为算法。
语言里通常表现为解决问题的步骤
程序 = 算法(加工数据) + 数据结构(数据的存储和组织)
有穷性:在有穷步之后结束。
确定性:无二义性。
可行性:可通过基本运算有限次执行来实现。
有输入:可有零个或多个。
有输出:至少有一个输出。
(1)时间复杂度:(算法的工作量大小)通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。
算法中基本运算次数 T(n)是问题规模 n 的某个函数 f(n),记作:
T(n)=O(f(n))
空间复杂度:
实现算法所需的存储单元多少
第二章线性表
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用 n 表示,n ≥0。
:
(1) 集合中必存在唯一的一个“第一元素” ;
(2) 集合中必存在唯一的一个“最后元素” ;
除最后一个元素之外,均有唯一的后继(后件);
除第一个元素之外,均有唯一的前驱(前件)。
线性表逻辑结构
顺序表存储结构
typedefstruct
{
ElemType data[MAXCOUNT]; 序表上的运算及其实现
(1). 建立顺序表 CreateList
创建一个空的顺序表,要完成线性表所需空间的分配和其他初始化设置。
求线性表的长度 ListLength
输出线性表 DispList
在线性表中的指定位置插入一个元素InsertElem
根据键值查找指定元素 FindElemByNum
获取指定位置的元素信息 GetElem
删除指定位置的元素 DelElem
释放线性表 DestroyList
——单链表(
data 域和指针域 next )
由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素
,即数据元素之间是一对一
的逻辑关系,所以当进行链式存储时
,一种最简单也最常用的方法是
:
在每个结点中除包含有数据域外
,只设置一个指针域,用以指向其后继结点
,这样构成的
链接表称为线性单向链接表
,简称单链表;
头结点
开始结点
终端结点
head
a1
a2
an ∧
LinkList 类型的定义如下 :
typedefstructLNode /* 定义单链表结点类型 */
{
ElemType data;
structLNode *next; /* 指向后继结点 */
}LinkList;
1、创建单链表 LinkList *CreateList();
2、初始化单链表 void InitList(LinkList *list);
3
、释放单链表 void DestroyList(LinkList *list);
4
、获取单链表中元素的数量
intListLength(LinkList *list);
5
、输出单链表中的所有数据
void DispList(LinkList *list);
6、获取单链表中指定位置的元素 intGetElem(LinkList *list, intloc, ElemType *pElem);
7、根据键值查找指定元素 intFindElemByNum(LinkList *list, char *keyCh, ElemType *pElem);
8、采用头插法向单链表中插入一个元素
intInsertElem_Head(LinkList *list, ElemTypemyElem);
9、采用尾插法向单链表中插入一个元素
intInsertElem_Foot(LinkList *list, ElemTypemyElem);
10、向单链