同济大学计算机专业数据结构笔记总结

Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 同济计算机专业数据结构笔记总结 -是前人根据辅导班笔记做的浓缩,很 有用的,配着教材可拿它做大纲使用了:)有些是我补充的 第一章绪论 1)数据结构是解决非数值计算的问题的。 2)数据的基本单位是数据元素;最小单位是数据项。数据对象是性质相同的数据元素的集 合,是数据的一个子集 3)数据结构的划分通常有四种基本结构: 按性质分为(逻辑,物理结构);按存储方式分为(顺序存储,非顺序存储结构)。 4)顺序存储方式不只用于存储线性结构,比如也可以存储树型结构 5)算法:是对特定问题的求解步骤的一种描述。他的5个特性:有穷性,确定性,可行性 输入,输出。 6)算法和数据结构的关系:算法的设计依靠的是数据逻辑结构,而算法的实现依靠的是数 据物理结构。 ⑦)算法的要求:正确性,可读性,健壮性,效率与低存储量需求。 8)算法原地工作:额外空间相对于输入数据量来说是常数,既不依赖于问题的规模。 9)时间复杂度:最坏的情况下估算算法的一个上界。O(n)在时间上总优于O(n^2) 附:历年基本上没有出现过时间复杂度的计算题目,本章都是些概念题,出现在填空或选择中,在数据结 构填空,判断复习题中都有体现 第二章线性表 在本节中主要研究两种形式的线性表:顺序表和链表。 1)顺序表是随机存储结构的线性表,而单链表是顺序存储结构的线性表 2)顺序表的基本操作(査找,插入,删除)要求会熟练操作,这部分十分简单。 3)单链表分为带头节点的,和不带头节点的链表。这两种链表的基本操作(建立,输出 合并,拆分,插入,删除,逆置)要熟练掌握!尤其是插入和删除时的操作顺序。 4)链表的插入(表头插入法,表尾添加法)要熟练掌握。 5)用链表的插入进行排序 6)链表的逆置 7)循环链表和双向链表也要掌握操作! 8)一般在考试中有一道大题。 第三章栈和队列 在本节中主要研究链栈和顺序栈。 1)链栈是不带头节点的单链表,头指针指向栈顶元素,操作的时候在此添加元素。 2)顺序栈的建立 Typedef struct

Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 同济计算机专业数据结构笔记总结 -----是前人根据辅导班笔记做的浓缩，很 有用的，配着教材可拿它做大纲使用了：）有些是我补充的。 第一章 绪论 1） 数据结构是解决非数值计算的问题的。 2） 数据的基本单位是数据元素；最小单位是数据项。数据对象是性质相同的数据元素的集 合，是数据的一个子集。 3） 数据结构的划分通常有四种基本结构： 按性质分为（逻辑，物理结构）；按存储方式分为（顺序存储，非顺序存储结构）。 4） 顺序存储方式不只用于存储线性结构，比如也可以存储树型结构。 5） 算法：是对特定问题的求解步骤的一种描述。他的 5 个特性：有穷性，确定性，可行性， 输入，输出。 6） 算法和数据结构的关系：算法的设计依靠的是数据逻辑结构，而算法的实现依靠的是数 据物理结构。 7） 算法的要求：正确性，可读性，健壮性，效率与低存储量需求。 8） 算法原地工作：额外空间相对于输入数据量来说是常数，既不依赖于问题的规模。 9） 时间复杂度：最坏的情况下估算算法的一个上界。O（n）在时间上总优于 O（n^2）. 附：历年基本上没有出现过时间复杂度的计算题目，本章都是些概念题，出现在填空或选择中，在数据结 构填空，判断复习题中都有体现。 第二章 线性表 在本节中主要研究两种形式的线性表：顺序表和链表。 1）顺序表是随机存储结构的线性表，而单链表是顺序存储结构的线性表。 2）顺序表的基本操作（查找，插入，删除）要求会熟练操作，这部分十分简单。 3）单链表分为带头节点的，和不带头节点的链表。这两种链表的基本操作（建立，输出， 合并，拆分，插入，删除，逆置）要熟练掌握！尤其是插入和删除时的操作顺序。 4）链表的插入（表头插入法，表尾添加法）要熟练掌握。 5）用链表的插入进行排序。 6）链表的逆置。 7）循环链表和双向链表也要掌握操作！ 8）一般在考试中有一道大题。 第三章 栈和队列 在本节中主要研究链栈和顺序栈。 1） 链栈是不带头节点的单链表，头指针指向栈顶元素，操作的时候在此添加元素。 2） 顺序栈的建立： Typedef struct{

Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia Int stacksize 顺序栈是用数组描述栈的一种形式 3)要会判断两种栈的空满。 4)要熟练掌握两种栈的操作(插入,删除)。 5)栈的内容十分重点,应该有一道大体,和若干小题! 在本节中主要研究链队列和循环队列。 )链队列是带头节点的单链表,要熟练掌握链队列的插入和删除元素的操作。 2)循环队列的判断空满是一个考点:在循环队列中,浪费一个元素空间,以尾指针加1 于头指针作为队列满的标志。 队列空: front=rare 队列满:(rare+1)%max=font max是整个循环队列的元素空间个数,包 括浪费的那个元素空间 第四章串 初步了解串的三种结构:顺序存储结构(静态存储结构),链式存储结构(块状存储结 构),堆结构。这章不是特别重点。 1)串的堆结构中,串名的存储映像:串名←(位置,长度) 2)串值存储密度:串值所占的存储位/实际分配存储位。密度越小,操作越方便,但存储占 用的空间大。 第五章数组和广义表 1)数组 矩阵的压缩存储: 1.特殊矩阵。 ①对称阵:n*n对称阵要用n*(n+1)2个存储单元。 存储下三角对称阵。索引位置k=i*(-1)2+j-1 减1是考虑到c语言的数组下表从0开始。i,j是元素的坐标 ②三角阵: 下三角阵:k=i*(-)2+1 上三角阵:k=(2ni)*(i-1)2+-1 ③三对角阵(如下图形式)

Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia Int top; Int stacksize; }sqStack; 顺序栈是用数组描述栈的一种形式。 3） 要会判断两种栈的空满。 4） 要熟练掌握两种栈的操作（插入，删除）。 5） 栈的内容十分重点，应该有一道大体，和若干小题！ 在本节中主要研究链队列和循环队列。 1） 链队列是带头节点的单链表，要熟练掌握链队列的插入和删除元素的操作。 2） 循环队列的判断空满是一个考点：在循环队列中，浪费一个元素空间，以尾指针加 1 等 于头指针作为队列满的标志。 队列空：front=rare 队列满：(rare+1)%max=front max 是整个循环队列的元素空间个数，包 括浪费的那个元素空间。 第四章 串 初步了解串的三种结构：顺序存储结构（静态存储结构），链式存储结构（块状存储结 构），堆结构。这章不是特别重点。 1） 串的堆结构中，串名的存储映像： 串名 ÍÎ(位置，长度)。 2） 串值存储密度：串值所占的存储位/实际分配存储位。密度越小，操作越方便，但存储占 用的空间大。 第五章 数组和广义表 1）数组 矩阵的压缩存储： 1． 特殊矩阵。 ○1 对称阵：n*n 对称阵要用 n*(n+1)/2 个存储单元。 存储下三角对称阵。索引位置 k= i*(i-1)/2+j-1 减 1 是考虑到 c 语言的数组下表从 0 开始。i，j 是元素的坐标。 ○2 三角阵： 下三角阵：k= i*(i-1)/2+j-1 上三角阵：k=(2n-i）*(i-1)/2+j-1 ○3 三对角阵 （如下图形式）

Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 0 0081 0 存储三对角阵。索引位置k=2*+-3 2.稀疏矩阵的存储方式。 ①三元组法 ②十字链表法 要了解这两种方法,以及基本应用(矩阵转制,矩阵乘法)。了解即可。 2)重点:广义表:是递归结构,不能分配固定大小 长度:元素或子表的个数。 深度:括号重数。 表头为单元素或子表,表尾必为子表,不是单元素! 这些容易出试题。 附:05年考试中,第四五章均出现在填空判断中,将复习题中的同类题目会做就应该可以了 第六章树和二叉树 1)了解树以及二叉树的相关定义 结点拥有的子树数称为结点的度 树的度是树内各结点的度的最大值。 树中结点的最大层次称为树的深度 2)5个性质(必考内容,容易出现在小题中) 1.在二叉树的第i层上至多有2~(i-1)个结点(p>=1) 2.深度为k的二叉树至多有2^k-1个结点,(k>=1) 3.对任何一棵二叉树T如果其终端结点数为nO,度为2的结点数为n,则n0=n2+1。 4.具有n个结点的完全二又树的深度为[ogn+1。(向下取整) 5.双亲,孩子判断法。 3)满二叉树的定义,完全二叉树的定义

Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 1 2 0 0 0 3 4 5 0 0 0 6 7 8 0 0 0 9 1 2 0 0 0 3 4 存储三对角阵。索引位置 k= 2*i+j-3 2． 稀疏矩阵的存储方式。 ○1 三元组法 ○2 十字链表法 要了解这两种方法，以及基本应用（矩阵转制，矩阵乘法）。了解即可。 2) 重点：广义表: 是递归结构，不能分配固定大小。 长度：元素或子表的个数。 深度：括号重数。 表头为单元素或子表，表尾必为子表，不是单元素！ 这些容易出试题。 附：05 年考试中，第四五章均出现在填空判断中，将复习题中的同类题目会做就应该可以了 第六章 树和二叉树 1）了解树以及二叉树的相关定义： 结点拥有的子树数称为结点的度。 树的度是树内各结点的度的最大值。 树中结点的最大层次称为树的深度。 2）5 个性质（必考内容，容易出现在小题中） 1．在二叉树的第 i 层上至多有 2^(i-1)个结点（i> =1）. 2．深度为 k 的二叉树至多有 2^k-1 个结点，（k>=1）. 3．对任何一棵二叉树 T，如果其终端结点数为 n0,度为 2 的结点数为 n2，则 n0=n2+1。 4．具有 n 个结点的完全二叉树的深度为[logn]+1。（向下取整） 5．双亲，孩子判断法。 3） 满二叉树的定义，完全二叉树的定义

Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大求使用,禁止任何单位和个人用作其它离业用途!--- Andy xia 4)完全二叉树的特点 叶子结点只可能在层次最大的两层上出现 2.对任何一结点,若其右分支下的子孙的最大层次为1,则其左分支下的子孙的最 大层次必为l或H+1。 3.完全二叉树不一定是满二叉树 5)存储结构 1.顺序存储,适用于完全二叉树。 2.链式存储,怎么建立,基本操作,重点 3.静态二叉链表,三叉链表,大致了解。 6)遍历二叉树 递归遍历二叉树。如下是先序遍历 Void Order(BiTree T) f if(D)i Order(T->Lchild) Order(T->Rchild) 先序遍历1,2,3 中序遍历2,1,3 后序遍历2,3,1 逆先序遍历1,3,2 逆中序遍历3,1,2 逆后序遍历3,2,1 非递归遍历二叉树。掌握先序和中序。 先序 while(p) stop++, P=P->Chil p=p->Rchild; While(s. toplIP)

Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 4） 完全二叉树的特点： 1．叶子结点只可能在层次最大的两层上出现； 2．对任何一结点，若其右分支下的子孙的最大层次为 l，则其左分支下的子孙的最 大层次必为 l 或 l+1。 3．完全二叉树不一定是满二叉树。 5）存储结构 1．顺序存储，适用于完全二叉树。 2．链式存储，怎么建立，基本操作，重点。 3．静态二叉链表，三叉链表，大致了解。 6）遍历二叉树 1．递归遍历二叉树。如下是先序遍历。 Void Xorder (BiTree T) { if (T) { Visit (T->data); ……………………….○1 Xorder(T->Lchild); ……………………….○2 Xorder(T->Rchild); ……………………….○3 }} 先序遍历 1，2，3 中序遍历 2，1，3 后序遍历 2，3，1 逆先序遍历 1，3，2 逆中序遍历 3，1，2 逆后序遍历 3，2，1 1． 非递归遍历二叉树。掌握先序和中序。 先序： P=root; do{ while(P) { visit(P); s.top++; s.base[s.top]=p; P=P->Lchild; } If (s.top) { p=s.base[s.top]; s.top--; p=p->Rchild; } While (s.top||P)

Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 中序 P=root while(p) s base[s. top]=p: P=P->Lchild p-s base(s top]: While(s top!IP) 7)找遍历的第一和最后一个结点 先序:第一个是根结点,最后一个要会编程寻找 If (P)i While(p->Lchild lp->Rchild) If(p->Rchild) p=p->Rchild Else p->Lchild 后序:第一个要会编程寻找,最后一个是根结点。 中序:第一个是最左边没有左子树的结点,最后一个是最右边无右子树的结点 8)线索二叉树(重点,必考) 要熟练掌握线索化的方法。 中序遍历线索二叉树寻找任一结点x的前驱和后继的方法。 寻找前驱 While(p->RTag==0) P=p->Rchild; Else p=x->Lchild

Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 中序： P=root; do{ while(P) { s.top++; s.base[s.top]=p; P=P->Lchild; } If (s.top) { p=s.base[s.top]; s.top--; visit(p); p=p->Rchild; } While (s.top||P) 7) 找遍历的第一和最后一个结点 先序：第一个是根结点，最后一个要会编程寻找。 P=root; If (P) { While (p->Lchild||p->Rchild) { If (p->Rchild) p= p->Rchild; Else p->Lchild; } } 后序：第一个要会编程寻找，最后一个是根结点。 中序：第一个是最左边没有左子树的结点，最后一个是最右边无右子树的结点。 8）线索二叉树（重点，必考） 要熟练掌握线索化的方法。 中序遍历线索二叉树寻找任一结点 x 的前驱和后继的方法。 寻找前驱： If (x->LTag==0) { p=x->Lchild; While (p->RTag==0) P=p->Rchild; } Else p=x->Lchild;