第一章 数据结构与算法
一.算法的基本概念
计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。
1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。
2.算法的基本要素:算法中对数据的运算和操作、算法的控制结构。
3.算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。
4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求
二.算法的复杂度
1.算法的时间复杂度:指执行算法所需要的计算工作量
2.算法的空间复杂度:执行这个算法所需要的内存空间
三.数据结构的定义
1.数据的逻辑结构:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括
集合、线形结构、树形结构和图形结构四种。
2.数据的存储结构:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。
常用的存储结构有顺序、链接、索引等存储结构。
四.数据结构的图形表示:
在数据结构中,没有前件的结点称为根结点;没有后件的结点成为终端结点。插入和删除是
对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。
五.线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线
性结构和非线性结构。
线性结构:非空数据结构满足:有且只有一个根结点;每个结点最多有一个前件,最多只有
一个后件。非线性结构:如果一个数据结构不是线性结构,称之为非线性结构。
常见的线性结构:线性表、栈、队列
六.线性表的定义
线 性表是n 个元素构成的有限序列(A1,A2,A3 )。表中的每一个数据元素,除了第
一个以外,有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表 是一个空
表,或可以表示为(a1,a2, an), 其中ai(I=1,2, n)是属于数据对象的元素,通常也称
其为线性表中的一个结点。
非空线性表有如下一些特征:
(1)有且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线
性表中结点的个数n称为线性表的长度。当n=0时称为空表。
七.线性表的顺序存储结构
线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储结构具备如下两个基本特征:
1.线性表中的所有元素所占的存储空间是连续的;
2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
即线性表逻辑上相邻、物理也相邻,则已知第一个元素首地址和每个元素所占字节数,则可
求出任一个元素首地址。
假设线性表的每个元素需占用K个存储单元,并以所占的第一个单元的存储地址作为数据
元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的
存储位置LOC(ai)之间满足下列关系:
Data Structures, Algorithms, and Applications in C++ 数据结构算法与应用——C++语言描述 (英文版) Sartaj Sahni McGraw-Hill & 机械工业出版社 ? 数据结构课程...
数据结构与算法 Data Structures and Algorithms_其它考试_资格考试/认证_教育专区。数据结构基础 Fundamentals of Data Structures 主讲教师: 何钦铭 Instructor: He...
The library includes some generic data structures and generic algorithms, and the two parts are ass...更多>>Here, we report a template library used for...
Data Structures and Algo... 80页 免费 Algorithms and Data Stru... 179页 1财富值 Data Structures and Algo... 52页 免费 Data Structures & Algori.....
25 pages. Page D-1 Data Structures and Algorithms: Shifting the Focus to Components and Reasoning [Clifton 02] Clifton, C. and Leavens, G. T., “...
? ? 常用的资料表现方式 (Static vs. Dynamic, Dense vs. Sparse) 选取合适的资料结构+适当的演算法 (Programming= Data Structures + Algorithms) 评估所采用的...
Data Structures and Algorithms_互联网_IT/计算机_专业资料。Data Structures and Algorithms Rationale Computer science is a field of study that deals with ...
Data Structures and Algo... 80页 免费 Algorithms and Data Stru... 179页 1财富值 Data Structures and Algo... 52页 免费 Data Structures & Algori.....
Information Retrieval Data Structures and Algorithms (William B. Frakes, Ricardo Baeza-Yates)_工学_高等教育_教育专区。Information Retrieval Data Structures ...
Data Structures and Algo... 52页 免费 L2-Algorithms and Data S... 85页 2财富值 Data Structures and Algo... 暂无评价 28页 免费 Chapter 1-Data ...
热门文档