数据结构总复习

《数据结构总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》总复习主讲教师：翁梅第一章绪论1．1基本概念1．数据数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2．数据元素数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。3．数据对象数据对象是性质相同的数据元素的集合。4．数据结构数据的逻辑结构是相互之间存在一种或多种特定关系的数据元素的集合，形式定义为一个二元组：Data_Structure=(D，S)其中，D是数据元素的有限集；S是D上关系的有限集。(1)集合：数据元素之间除了“同属于一个集合”的关系外，别无其他关系。(2)线性结构：数据元素之间存在一个一对一的关系，有且

2、仅有一个开始结点和终端结点，除开始结点外，每个结点有且仅有一个前趋结点，除终端结点外，每个结点有且仅有一个后继结点。(3)树型结构：数据元素之间存在一个对多个的关系，有一个开始结点和多个终端结点，除开始结点外，每个结点有且仅有一个前趋结点，除终端结点外，每个结点可能有多个后继结点。(4)网状结构或图状结构：数据元素之间存在多个对多个的关系，每个结点可能有多个前趋结点和多个后继结点。树型结构和网状结构又称为非线性结构。顺序存储、链接存储、索引存储、散列存储。1.2算法及其分析算法是是指令的有限运算序列。算法具有以下5个重要特性：1.有穷性；2.确定性；3.可行性；4.输入；5.输出1.3算

3、法的性能分析与度量1.算法的性能标准(1)正确性；(2)可读性；(3)健壮性；(4)高效率与低存储量2.算法效率的度量时间复杂度T(n)=O(f(n))空间复杂度S(n)=O(f(n))算法+数据结构=程序1第二章线性表2．1线性表的顺序存储1．线性表的顺序存储特点逻辑上相邻的元素，物理位置也相邻。静态有序表。线性表的顺序存储结构是一种随机存取的存储结构。表2-1插入、删除、查找、合并算法的时间复杂度操作元素移动元素移动元素移动(或比较)最少(或比较)最多(或比较)平均插入0nn/2删除0n-1(n-1)/2查找1n(n+1)/2有序表的合并n1+n2n1+n2n1+n22．2线性表的动

4、态链式存储特点：逻辑上相邻的元素，物理位置可以不相邻，表中元素只能顺序访问，插入、删除等操作只需修改指针而不需移动元素。线性表的链式存储结构是一种顺序存取的存储结构。2．3线性表的静态链式存储特点：用一维数组描述线性链表。2．4其他形式的链表1．循环线性链表特点：最后一个结点的指针域指向头结点，从任意结点出发都可以找到表中的其他结点。2．双向链表特点:双向链表克服了在单链表中求前趋需要遍历链表而导致效率较低的缺点。从任意结点出发都可以找到表中的其他结点。2第3章栈和队列栈和队列是操作受限制的线性表。3．1栈及其应用栈(stack)是限定只在表尾（栈顶）进行插入或删除操作的线性表，是后进先

5、出(LIFO)的线性表。栈结构通常采用的两种存储结构是顺序存储结构和链表存储结构。图3．1栈结构的示意图(A，B，C，D)(C，A，B，D)3．2队列及其应用队列(Queue)是限定只能在表的一端（队尾）进行插入，而在表的另一端（队头）进行删除操作的线性表。和栈相反，队列是一种先进先出(FIFO)的线性表。图3．2队列的示意图链队列：队列的链式存储结构循环队列：队列的顺序存储结构1，2，3，4线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。3第4章串4．1有关概念串(或字符串)，是由零个或多个

6、字符组成的有序序列。s='a1a2…an'(n≥0)串中字符的数目称为串的长度。零个字符的串称为空串，它的长度为零。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串是所有字符串的子串，任何字符串是自身的子串。4．2串的存储表示1．串的定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，每个串变量分配一个固定长度的存储区。2．串的变长顺序存储(堆分配存储)表示用一组地址连续的存储单元存储串值的字符序列，它们的存储空间是在程序执行过程中动态分配而得，对字串进行操作时不存在溢出问题。3．串的块链存储表示适用于不改变数据结点的操作,如查找(或模式匹配)。4

7、．3串的常用运算串赋值StrAssign、串的比较StrCompare、求串长StrLength、串连接Strcat以及求子串SubString构成串类型的最小操作子集。如果s='IAMASTUDENT'，t='GOOD'，则LENGTH(s)的结果是14，CONCAT(SUBSTR(s,6,2),CONCAT(t,SUBSTR(s,7,8)))AGOODSTUDENTA='BEI'B='JING'C=''D='BEIJING'St