1、 数据结构的逻辑结构的种类:线性结构(线性表、栈、队列、串、数组和广义表)、非线性结构(多维数组、广义表、树、图等。树(层次结构) 、图(网状结构))。
2、 存储结构有:顺序存储结构、链式存储结构、索引存储结构、散列存储结构四种: 索引存储结构:
在存储结点信息的同时,还建立附加的索引表,由此得到的存储表示称为索引存储结构。。散列存储结构:根据结点关键字值直接计算出该结点的存储地址,由此得到的存储结构称为散列存储结构(亦称为哈希存储结构)
3、(例1)
4、(例2)
1).无循环的频度都为1;
2)题 t(n)=o(n的2次方);
5、顺序存储结构的表:线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素,这种机内存储表示称为线性表的顺序存储结构。采用顺序存储结构存储的线性表称为顺序表。
6、(2.3.1)结点程序会写:线性表的单链表存储结构 (重点:单链表)
typedef struct lnode
l->next=null;
*两个域:数据域、指针域。
*线性表的单链表存储结构程序:
*插入、删除—>改变结点指向的指针:怎么改结点的指针?
7、栈:栈(stack):仅在表的一端进行插入(进栈)或删除(出栈)的线性表称为栈。
能进行插入或删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何元素的栈称为空栈。特点:先进后出。
8、栈有2种存储结构:顺序存储结构(栈主要用)、链式存储结构(队列主要用)。存储想不相邻是错误的,前提是看哪种存储结构。
9、队列:队列是一种先进先出(first in first out, 缩写为fifo)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。
删除只能在队头删除(出栈),队尾进(入栈)。
10、删除链队列中的一个元素是不可以的。
11、第k层有多少个结点?
12、串和栈连接:入栈出栈操作题集,出栈赋给哪个?
13、串:由零个或多个字符组成的有限序列,一般记为: s=‘a1a2…an’;
14、什么是空串?空格串?空格串有字符。
15、串和栈结合起来(push、pop。。问什么样的串)
16、二叉树的定义:二叉树或为空树;或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
17、性质:性质1、在二叉树的第i层上至多有2i-1个结点(i≥1)。
性质2、深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3、对任何一棵二叉树t,如果其终端结点数为n0,度为2的结点数为n2,则:n0=n2+1
性质5、如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层序编号(从上到下且每层从左至右),则对任一结点i(1≤i≤n),有:
1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲parent(i)是结点i/2。
2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子lchild(i)是结点2i。
3)若2i+1>n,则结点i无右孩子;否则其右孩子rchild(i)是结点2i+1。
18、完全二叉树的概念:若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且,最下一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。例
19、二叉树的存储结构:(顺序存储结构、链式存储结构)二叉链表树结点结构(图)
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数,因为它的值不含有子结构。aggregate type,复杂类型,一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构,存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个,每题2分,共40分 简答题 6个,每题5分,共30分 和算法设计题 2个,每题15分,共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d,r 要求给定一个形式化表示,能够画出...