没有合适的资源?快使用搜索试试~ 我知道了~
引入头结点后的优点:(1)由于开始结点的位置被放置在头结点的指针域中,所以在链表的第一个位置上的操作和在表的其它位置上的操作一致,无需特殊处理。(2)无论链表是
资源详情
资源评论
资源推荐
第1章:绪论
1.2 算法和算法平均
1.2.2 算法效率的度量
1. 时间复杂度
选择:2011-1,2012-1,2013-1,2014-1,2017-1
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为 ,
它是该算法问题规模的 的函数,时间复杂度主要分析 的数量级。算法中基本运算(最深层循环内的
语句)的频度与 同数量级,因此通常采用算法中基本运算频度 来分析算法的时间复杂度。因
此,算法的时间复杂度记为
式中,O的含义是 的数量级,其严格的数学定义是:若 和 是定义在整数集合上的两个函
数,则存在正常数 和 ,使得当 时,都满足 。
算法的时间复杂度不仅依赖于问题的规模 ,还取决于待输入的数据的性质(如输入数据元素的初始
状态)。
三种时间复杂度
(1)最坏时间复杂度:指在最坏的情况下,算法的时间复杂度
(2)平均时间复杂度:指所有可能输入实例在等概率出现的情况下,算法的期望运行时间
(3)最好时间复杂度:指在最好的情况下,算法的时间复杂度
加法规则与乘法法则
常见的时间复杂度
2. 空间复杂度
算法的空间复杂度 定义为该算法所耗费的存储空间,它是问题规模 的函数。渐进空间复杂度
也简称为空间复杂度,记为 。
一个上机程序除需要存储空间来存放本身所需要的指令、常数、变量和输入数据外,还需要一些对
数据进行操作的工作单元和存储为实现计算所需的一些信息的辅助空间,若输入的数据所占空间只取决
于问题本身而与算法无关,则只需分析除输入和程序外的额外空间。
【注】:算法原地工作是指算法所需的辅助空间为常量,即 。
第2章:线性表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义
线性表示具有相同数据类型的 个数据元素的有限序列,其中 为表长,当 时线性表
是一个空表。若用 命名线性表,则其一般表示为
是“第一个”数据元素,又称为表头元素, 是”最后一个“元素,又称为表尾元素。除第一个元素外,
每个元素有且仅有一个直接前驱。除最后一个元素以外,每个元素都有且仅有一个直接后继。以上都是
线性表的逻辑特性。
线性表的特点
(1)表中元素有限
(2)表中元素具有逻辑上的顺序性,在序列中各个元素排序有其先后次序
(3)表中元素都是数据元素,每个元素都是单个元素
(4)表中元素的数据类型都相同,这意味着每个元素占有相同的大小的存储空间
(5)表中元素具有抽象性,即仅讨论元素之间的逻辑关系,而不讨论元素究竟表示什么内容
2.1.2 线性表的基本操作
InitList(&L):初始化表。返回一个空的线性表。
Length(L):求表长。返回线性表L的长度,即L中元素的个数。
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i):按位查找操作。获取表L中的第i个位置的元素。
ListInsert(&L,i,e):插入操作。在表L中的第i个位置插入指定元素e。
ListDelect(&L,i,&e):删除操作。删除表L中的第i个位置的元素,并用e返回删除元素的值。
PrintList(L):输出操作。按前后的输出顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表,则返回ture,否则返回false。
DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占用的内存空间。
2.2 线性表的顺序表示
2.2.1 顺序表的定义
线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据单元,
从而使得逻辑上相邻的两个元素在物理位置上也相邻。
假定线性表中的元素类型为ElemType,则线性表的顺序存储类型描述为
动态数组分配
C的初始动态分配语句
C++初始动态分配语句
2.3 线性表的链式表示
顺序表的插入、删除操作需要移动大量的元素,影响了运行效率,由此引入了线性表的链式存储。
链式存储不要求连续的存储单元,即它不要求逻辑上相邻的两个元素物理上也相邻。对线性表的插入、
删除不需要移动元素,只需修改指针即可。
2.3.1 单链表的定义
线性表的链式存储又称为单链表,它是通过任意一组存储单元来存储线性表中的数据元素。
单链表结点类型的描述
#define MaxSize 50 //定义线性表的最大长度
typedef struct{
ElemType data[MaxSize]; //顺序表的元素
int length; //顺序表当前长度
}SqList; //顺序表的类型定义
#define InitSize 100 //表长度的初始定义
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length //数组的最大容量和当前个数
}SqList; //顺序表的类型定义
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)
L.data = new ElemType(InitSize);
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
通常用一个头指针来标识一个链表,如单链表 ,头指针为NULL时表示一个空表,为了方便,在单
链表第一个结点前附加一个结点,称为头结点。头结点的数据域不含有任何信息,指针域指向线性表的
第一个元素结点。
头指针和头结点的区分
不管带不带头结点,头指针始终指向链表的第一个结点,而头结点是带头结点的链表中的第一个结
点,结点内不存储信息。
引入头结点后的优点:
(1)由于开始结点的位置被放置在头结点的指针域中,所以在链表的第一个位置上的操作和在表的其
它位置上的操作一致,无需特殊处理。
(2)无论链表是否为空,其头指针都指向头结点而非空指针,因此空表和非空表的处理也得到了统
一。
2.3.3 双链表
选择:2016-2
单链表结点中只有一个指向其后继的指针,使得单链表只能从结点依次顺序地向后遍历。要访问某
个结点的前驱结点(插入、删除操作时),只能从头结点开始遍历,访问后继结点的时间复杂度为 ,
访问前驱结点的复杂度为 。
为了克服单链表的上述缺点,引入了双链表,双链表结点中有两个指针prior和next,分别指向其
前驱结点和后继结点,如图:
双链表结点类型的描述如下:
双链表的插入、删除结点的算法复杂度均为 。
2.3.5 静态链表
选择:2016-1
静态链表借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与前面所讲
的链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称游标。
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;
和顺序表一样,静态链表也要预先分配一块连续的内存空间。
静态链表结构类型的描述如下:
第3章:栈和队列
3.1 栈(Stack)
3.1.1 栈的基本概念
选择:2009-2,2010-1,2011-2,2013-2,2015-1,2017-2
1. 栈的定义
栈只允许在一端进行插入或删除的线性表。栈的操作特性可归纳为后进先出(Last In First Out,
LIFO)。
2. 栈常见的基本操作
InitQueue(&S):初始化一个空栈S。
StackEmpty(S):判断栈空,若栈S为空返回true,否则返回false。
Push(&S,x):进栈,若栈S未满,将x加入,使之成为新的栈顶。
Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。
GetTop(S,&x):读栈顶元素,若栈S非空,则用x返回栈顶元素。
ClearStack(&S):销毁栈,并释放栈S占用的存储空间
3.1.2 栈的顺序存储结构
3. 共享栈
选择:2016-3
利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置
在共享空间的两端,两个栈顶向共享空间的中间延伸,如图所示:
#define MaxSize 50 //静态链表的最大长度
typedef struct{ //静态链表结构数据类型定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
剩余55页未读,继续阅读
7323
- 粉丝: 22
- 资源: 327
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0