数据结构课程的主要内容.doc

数据结构课程的主要内容 数据结构的基本概念 基本概念和术语 算法和算法分析（典型算法） 线性表 线性表的概念定义和特点 线性表的实现顺序表示和链式表示（特点、定义） 线性表的基本操作建立（正序、逆序、有序）、查找、插入、删除、输出 线性表的应用合并、时间复杂度 循环链表和双向链表 栈和队列 栈和队列的定义 栈的表示、实现和操作（出栈、入栈） 队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列） 串（串的基本概念和基本操作） 数组 数组的定义 数组的地址计算（一维、二维、三维） 特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏） 树和二叉树 树的定义和基本术语 二叉树 二叉树的性质 二叉树的存储结构 二叉树的遍历 树和森林 树的存储结构 树、森林与二叉树的转换 树和森林的遍历 哈夫曼树及其应用 图 图的定义和术语 图的存储结构 图的遍历 查找 查找的基本概念 静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析 动态查找表（二叉排序树和平衡二叉树） 哈希表 排序（直接插入、冒泡、选择、快速和归并）第一章 数据结构课程的主要内容（二）线性表 线性表的类型定义q 线性表是n个（n0)数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。q 在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最后一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。q 线性表（a1,ai-1,ai,ai+1, ,an） n为线性表的长度，i为元素在线性表中的位序。 q 线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用） 线性表的顺序表示和实现顺序表q 线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素。LOC(ai)=LOC(a1)+(i-1)*l l为每个元素所占的空间 q 线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素， 物理位置上也相邻的特点。 q 顺序表是一种随机存取的存储结构q 通常用数组描述顺序表 q 顺序表的表示struct sqlist #define LEN 100 #define LEN 100 int *elem; struct sqlist int aLEN; int length; int aLEN; int length; int listsize; int length; ; ;q 顺序表的操作v 顺序表初始化v 顺序表的插入v 顺序表的删除 移动大量元素v 顺序表的查找v 线性表的插入(n+1)a1,a2,ai-1, ai, ai+1,an 插入位置的判断(n+1) (q) (p) 元素移动的顺序和位置a1,a2,ai-1,b,ai,ai+1,an 表长的变化v 线性表的删除(n-1)a1,a2,ai-1,ai,ai+1,an 删除位置的判断 (p) (q) 元素移动的顺序和位置a1,a2,ai-1, ai+1,an 表长的变化v 时间复杂度求表长 O(1)查找第i个元素、前趋、后继 O(1)查找值为x的元素的位序 O(n)插入元素 O(n) (0+1+n)/(n+1)=n/2删除元素 O(n) (0+1+n-1)/n=(n-1)/2v 顺序表适用于不常进行插入、删除运算，表中元素相对稳定的场合。 线性表的链式表示和实现线性链表q 线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。q 为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其直接后继的信息。即指针为数据元素之间逻辑关系的映象。hq 结点包括两个域：数据域和指针域（链），n个结点链接成一个（单）链表。指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空(NULL)。单链表可由头指针唯一确定。q 链表的表示 #define NULL 0 struct node int data; struct node *next; ;struct node *head; /*head为头指针/若head=NULL，则表示空表。headp-nextpq 为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。此时，head-next 指向第一个结点。q p指向第i个结点，则p-data=ai; p-next-data=a i+1;q 单链表是一种非随机（顺序）存储结构。q 单链表的操作v 查找第i个元素 O(n)指针p从指向第一个结点的位置（head-next）向后移动（p=p-next）i-1次。p-nextspv 插入O(n)（1）查找插入点的前趋结点p （2）生成新结点s （3）s-next=p-next; （4）p-next=s;p-next-nextp-next p删除O(n) p-next=p-next-nextv 建立含头结点的单链表（动态生成） head=(struct node *) malloc (sizeof(struct node); head-next=NULL; q=(struct node *) malloc (sizeof(struct node);（1）顺序从表头至表尾 设p为指向链表当前最后一个结点的指针 p-next=q; p=q;（2）逆序从表尾至表头 q-next =head-next; head-next=q;（3）有序递增或递减 循环链表q 最后一个结点的指针域指向头结点，形成一个环。q 空表：head-next=head; 双向链表q 结点含两个指针域，分别指向直接前趋和后继。q p-next-priou=p-priou-next=pq 双向循环链表 链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。栈和队列 栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。 栈后进先出的线性表（LIFO） 抽象数据类型的定义栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。 基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除） a1 a2 an-1 an 栈底 栈顶 栈的表示和实现顺序栈栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。typedef struct int *base;int *top; sqstack;#define MAX 100Typedef struct int stackMAX int top;SEQSTACK;SEQSTACK *s;构造空栈 s.top = s.base s-top = 0 返回栈顶元素e=*(s.top-1) e=s.stacks.top-1入栈 *s.top+=e s-stacks-top=e s-top=s-top+1出栈e=*-s.top e=s-stacks-top-1 s-top=s-top-1栈满 s.top-s.base=MAX s-top=MAX 链栈栈的链式表示栈顶指针为top栈空 top=NULL;入栈生成新结点ss-link=top; top=s;出栈 输出top-data;top=top-link;栈的应用举例 int check(SEQSTACK *s)数制转换 int bool; char ch;括号匹配的检验 push(s,#); bool=1;行编辑程序ch=getchar();表达式求值while (ch!=n&bool)栈与递归 if (ch=() push(s,ch); if (ch=)if (gettop(s)=#) bool=0; else pop(s); ch=getchar(); if (gettop(s)!=#) bool=0; /*(多于)*/ if (bool) printf(“rigth”);else rintf(“error”); 队列先进先出的线性表（FIFO）抽象数据类型队列的定义队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。 基本操作：入队列（插入） 和出队列（删除） 出队列 a1 a2 an-1 an 入队列 队头 队尾链队列队列的链式表示和实现typedef struct qnode int data; struct qnode *next;QNODEtypedef struct QNODE *front, *rear;LINKQUEUE;LINKQUEUE *q;链队列初始化q-front=q-rear=(QNODE*)malloc(QNODE);q-front-next=NULL;链队列判空q-front=q-rear;元素入队列新生成结点s; s-next=NULL;q-rear-next=s; q-rear=s;元素出队列（非空队列）p=q-front-next; q-front-next=p-nextif (q-rear=p) q-rear=q-front循环队列队列的顺序表示和实现typedef struct int dataMAX int front,rear;SEQQUEUE;SEQQUEUE *q;头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。由于存在假溢出(q-rear=MAX)，可将顺序队列臆造成一个环状空间，称为循环队列。队空 和队满的判别条件相同：q-front=q-rear两种处理办法:(1)增设标志位(2)少用一元素空间。队空：q-front=q-rear队满： q-front=(q-rear+1)%MAX串 串类型的定义 串（String）（或字符串）是由零个或多个字符组成的有限序列。记为：s=a1a2an(n0) S为串名，单引号括起来的字符序列是串的值，n为串的长度。 子串主串中任意个连续字符组成的子序列。 位置字符在序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中位置来表示。 串相等两个串的长度相等，且每个对应位置的字符都相等。 空串零个字符的串为空串，长度为0，用表示。 空格串由一个或多个空格组成的串为空格串。长度为空格字符的个数。 串的基本操作：通常以“串的整体”为操作对象。 串赋值串复制 求子串判空串 串连接子串定位 串比较串替换 求串长串插入 串清空串删除 串的表示和实现 定长顺序存储表示为每个串变量分配一个固定长度地址连续的存储区。#define MAX 255unsigned char sstringMAX+1;0号单元存放串的长度。 堆分配存储表示在程序执行过程中，为每个串变量动态分配（malloc) 一个地址连续的存储区。 串的块链存储表示#define CSIZE 80 /块的大小typedef struct Chunk char chCSIZE;struct Chunk *next;Chunk;typedef struct Chunk *head,*tail; /头尾指针int curlen; /串长度Lstring;数 组 数组的定义 数组的性质 数组元素数目固定，一旦定义，维数和维界就不再改变。 数组元素具有相同的类型。 数据元素的下标关系具有上下界的约束并且下标有序。 数组的描述 ji=0，bi-1, i=1,2,n, bi是数组第i维的长度 D=aj1j2jn|n(0)为数组的维数，ji是数组元素的第i维下标 n=1表示一维数组，是线性表。 n=2表示二维数组，以矩阵形式表示，它也可以看成是线性表，其中每个数据元素本身又是一个线性表。 数组的基本操作 初始化数组 销毁数组 取元素给定一组下标，返回相应的数组元素值。 修改元素值（赋值）给定一组下标，修改相应的数组元素的值。 数组的顺序表示和实现 数组运算通常是随机访问与修改，一般不作插入或删除，故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变动，所以数组采用顺序存储结构表示。 存储单元是一维结构，而数组是多维结构，用一组地址连续的存储单元存放数组元素有次序约定的问题。 对于数组，一旦规定了它的维数和各维的长度（下标的界限），就可分配空间，并根据给定的一组下标求得相应数组元素的存储位置。 一维数组 LOC(ai)=LOC(a0)+i*L 二维数组(m*n) 行序为主序（a00,a01,a0,n-1,a10,a11,am-1,n-1)LOC(i,j)=LOC(0,0)+(i*n+j)*L 列序为主序（a00,a10,am-1,0),a01,a11,am-1,n-1)LOC(i,j)=LOC(0,0)+(j*m+i)*L 三维数组(m*n*p) 左下标（行）为主序（a000,a001,a00,p-1,a010,am-1,n-1,p-1)LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p+k)*L 右下标（列）为主序 多维数组（b1*b2*bn)LOC(j1,j2,jn)=LOC(0,0,0)+(j1*b2*bn+j2*b3*bn+jn-1*bn+jn)*L 若确定了数组的各维长度，则bl*bn为常数，数组元素的存储位置是其下标的线性函数，由于存取数组中任一元素的时间相等，故此结构为随机存储结构。 矩阵的压缩存储 若矩阵阶数很高，且矩阵中有许多值相同的元素或者零元素，为节省存储空间，对矩阵进行压缩存储，即为多个值相同的元只分配一个存储空间，对零元不分配空间 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，这类矩阵为特殊矩阵，否则为稀疏矩阵。特殊矩阵可将非零元压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。 特殊矩阵N阶对称矩阵元素关于主对角线对称aij=aji 0=i,j=j k=i*(i-1)/2+j-1当i=j k=i*(i-1)/2+j-1当ij k=n*(n+1)/2+1 对角矩阵所有的非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和主对角线邻近的上、下方以外，其余元素均为零。 稀疏矩阵 在矩阵A（m*n)中，s为非零元素的个数，t为零元素的个数，若st，则A为稀疏矩阵。稀疏因子d=t/(m*n)=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(root)的结点；（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2Tm，其中每一个集合本身又是一棵树，称为根的子树。 树的基本操作建树 求孩子结点求根结点求兄弟结点求双亲结点结点的插入、删除 树的表示形式树形表示嵌套集合表示广义表表示凹入表表示 基本术语树的结点指一个数据元素及若干指向其子树的分支。通常以结构体来描述。结点的度结点拥有的子树数。度为0的结点称为叶子或终端结点；度不为0的结点称为非终端结点或分支结点。树的度树内各结点度的最大值。孩子和双亲结点的子树的根为该结点的孩子，该结点为孩子的双亲。结点的层次根为第一层，依次类推。兄弟和堂兄弟双亲相同的结点为兄弟，双亲在同一层次的结点为堂兄弟。祖先和子孙从根到该结点所经分支上的所有结点为该结点的祖先；以某结点为根的子树中的任一结点都称为该结点的子孙。树的深度(高度)树中结点的最大层次。有序树和无序树如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。森林是m（m=0)个棵互不相交的树的集合。 二叉树 二叉树的定义 二叉树的每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 二叉树的基本操作建树（空树、非空树）求根结点、双亲、孩子、兄弟结点二叉树的遍历插入、删除 二叉树的五种基本形态空二叉树仅有根结点的二叉树左子树为空的二叉树右子树为空的二叉树左、右子树均非空的二叉树 二叉树的性质在二叉树的第i层上至多有2i-1个结点（i=1)深度为k的二叉树至多有2k-1个结点（k=1)对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1一棵深度为k且有2k-1个结点的二叉树称为满二叉树，其每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n结点一一对应时，称之为完全二叉树。具有n个结点的完全二叉树的深度为k=log2n+1如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（i=11，则双亲结点是i/2(2)如果2in，则结点无左孩子；否则其左孩子是结点2i。(3)如果2i+1n，则结点无右孩子；否则其右孩子是结点2i+1。 二叉树的存储结构 顺序存储结构用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即完全二叉树上编号为i的结点存储在一维数组中下标为i-1的分量中。对一般二叉树，顺序存储结构必须能反映结点之间的逻辑关系（父子关系），故将其每个结点与完全二叉树相 对照进行存储。这种顺序存储结构仅适用于完全二叉树。最坏情况下，k个结点、深度为k的二叉树需要2k-1个结点的存储空间。 链式存储结构头指针指向根结点。 二叉链表存储结点的一个数据元素和分别指向其左、右子树的两个指针。 三叉链表增加一个指向双亲结点的指针域。typedef struct tnodeint data; struct tnode *lchild, *rchild; TNODE; TNODE *root;在n个结点的二叉链表中有n+1个空链域。 建立二叉树 遍历二叉树和线索二叉树遍历二叉树 遍历二叉树是指如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。(即将二叉树的结点排成一个线性队列) 一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。若限定先左（L）后右（R），则遍历方法有先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）三种。 先序遍历二叉树的递归算法访问根-先序遍历左子树-先序遍历右子树void preorder(TNODE *bt) if (bt!=NULL)printf(“%d ”,bt-data); preorder(bt-lchild); preorder(bt-rchild); 中序遍历二叉树的递归算法（inorder)中序遍历左子树-访问根-中序遍历右子树 后序遍历二叉树的递归算法(postorder)后序遍历左子树-后序遍历右子树-访问根 表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。 将表达式表示为二叉树，若表达式=xqy，则根结点存放运算符，左子树表示x，右子树表示y。a+b*(c-d)-e/f波兰式：表达式二叉树的前序 中缀表示：中序逆波兰式：后序 从递归执行过程的角度先序、中序和后序是完全相同的。 线索二叉树遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信息。由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。Typedef struct btnodechar data; struct btnode *lchild, *rchild; int ltag, rtag;BTNODE;ltag=0 lchild指示结点的左儿子ltag=1 lchild指示结点的前趋rtag=0 lchild指示结点的右儿子rtag=1 lchild指示结点的后继 树和森林 树的存储结构 双亲表示法用一组地址连续的空间存放树中的结点，每个结点存放本身的信息和双亲结点所在的位置序号。 孩子表示法 多重链表每个结点有多个指针域，分别指向其每个子树。同构或不同构。 孩子链表 每个结点有一个孩子链表，n个结点链表的头指针顺序存储。 孩子双亲表示法双亲表示和孩子链表表示法结合起来。 孩子兄弟表示法二叉链表表示法*二叉链表作为树的存储结构，链表中的两个指针域分别指向该结点的第一个孩子和该结点的下一个兄弟。 树、森林与二叉树的转换 以二叉链表作为转换的依据。 树转化成二叉树后，二叉树根一定没有右子树。 森林的第二棵树树根看成是第一棵树树根的兄弟。 树与森林的遍历 树的先序遍历是指先访问树的根结点，然后依次先序遍历根的各子树。等价于先序遍历该树对应的二叉树。 树的后序遍历是指先依次后序遍历树的根结点的各子树，然后访问根结点。等价于中序遍历该树对应的二叉树。 先序遍历森林是指从左到右依次按先序遍历森林中的每一棵树，相当于先序遍历该森林对应的二叉树。 后序遍历森林是指从左到右依次按后序遍历森林中的每一棵树，相当于中序遍历该森林对应的二叉树。 赫夫曼树及其应用 最优二叉树赫夫曼树从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作WPL。假设有n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。 赫夫曼算法构造赫夫曼树根据给定的n个权值构成n棵二叉树的集合F，每棵二叉树Ti只有一个带权为wi的根结点。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，其根结点的权值为左右子树根结点的权值之和。在F中删除这两棵树，将新二叉树加入F重复构造，直到F中只含一棵树为止，这棵树就是赫夫曼树。 赫夫曼编码电报码电文的总长尽可能短出现次数多的字符采用尽可能短的编码。任一个字符的编码都不是另一个字符编码的前缀前缀编码。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题。约定赫夫曼树的左分支表示字符0，右分支表示字符1，从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。图图是复杂的非线性结构，结点之间的关系是任意的，任何两个数据元素都可能相关。图的应用极为广泛。l 图的定义和术语l 图是两个集合的二元组，G=（V，E），V表示顶点的有穷非空集合，E是顶点之间关系的有穷集合。l 若图中的每条边都是有方向的，顶点之间的关系表示从v到w的一条弧，v为弧尾或初始点，w为弧头或终端点，该图为有向图。l 若图中的每条边无方向，有必有，顶点之间的关系以无序对表示，表示从v到w的一条边，该图为无向图。l n表示图中顶点数目，e表示边或弧的数目，若不考虑顶点自身的边或弧，无向图e的取值范围是0n(n-1)/2，具有n(n-1)/2条边的无向图为完全图；有向图e的取值范围是0n(n-1)，具有n(n-1) 条边的有向图为有向完全图。有很少条边或弧(enlogn)的图为稀疏图，反之为稠密图。与图的边或弧相关的数称为权，带权的图称为网。l 假设两个图，G=(V,E)和G=(V,G)，如果VV且EE，则称G为G的子图。l 图从顶点v到v的路径是一个顶点序列，路径长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环，序列中顶点不重复的回路为简单路径。除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路为简单回路或简单环。l 无向图l 若边(v,w)E，则称顶点v,w互为邻接点，即v,w相邻接，边(v,w)依附于顶点v,w，边(v,w)和顶点相关联。顶点的度是和v相关联的边的数目，记为TD(v)。l 无向图中，若顶点v到顶点v有路径，称v和v是连通的。若对于图中任意两个顶点v,w都是连通的，则该图为连通图。连通分量是无向图中的极大连通子图。l 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果在树上添加一条边，必定构成一个环。有n-1条边的图不一定是生成树。l 有向图l 若弧(v,w)E，则称顶点v邻接到顶点w，顶点w邻接自顶点v，弧(v,w)和顶点v,w相关联。以顶点v为头的弧的数目为v的入度ID(v)，以v为尾的弧的数目为v的出度OD(v)，顶点v的度TD(v)=ID(v)+OD(v)。l 有向图中，每一对(v,w)V，若v到w和w到v都存在路径，则G是强连通图。有向图中的极大强连通子图是有向图的强连通分量。l 若一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一棵有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。l 图的存储结构l 数组表示法两个数组分别存储数据元素（顶点）信息和数据元素之间关系（边或弧）信息邻接矩阵。l 邻接表l 无向图的邻接表为每个顶点建立一个单链表，链表中的结点表示依附于该顶点的边。结点由三个域组成，其中邻接点域表示与该顶点邻接的点在图中的位置，链域指示下一条边的结点，数据域存储和边相关的信息。l 各顶点链表的表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。l 有向图的邻接表和逆邻接表邻接表链表中的结点表示以该顶点为尾的弧，而逆邻接表链表中的结点表示以该顶点为头的弧。l 十字链表（有向图）两类结点弧结点和顶点结点。l 邻接多重表（无向图）l 图的遍历l 深度优先搜索l 广度优先搜索