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

数据结构课程的主要内容数据结构课程的主要内容数据结构的基本概念基本概念和术语算法和算法分析（典型算法）线性表线性表的概念定义和特点线性表的实现依次表示和链式表示（特点、定义）线性表的基本操作建立（正序、逆序、有序）、查找、插入、删除、输出线性表的应用合并、时间困难度循环链表和双向链表栈和队列栈和队列的定义栈的表示、实现和操作（出栈、入栈）队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）串（串的基本概念和基本操作）数组数组的定义数组的地址计算（一维、二维、三维）特别矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）树和二叉树树的定义和基本术语二叉树O二叉树的性质O二叉树的存储结构O二叉树的遍历树和森林O树的存储结构O树、森林与二叉树的转换。树和森林的遍历哈夫曼树及其应用图图的定义和术语图的存储结构图的遍历查找查找的基本概念静态查找表（依次表、有序表、索引依次表）的算法和性能分析动态查找表（二叉排序树和平衡二叉树）哈希表排序（干脆插入、冒泡、选择、快速和归并）第一章数据结构课程的主要内容（二）线性表线性表的类型定义线性表是n个（n0）数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最终一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。线性表(al,aiT,ai,ai+l,an)n为线性表的长度，i为元素在线性表中的位序。线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询(值、位序、前驱、后继)、插入元素、删除元素、函数调用)线性表的依次表示和实现依次表线性表的依次表示(依次存储结构)是指用一组地址连续的存储单元依次存放线性表的数据元素。1.OC(ai)=LOC(al)+(i-l)*l1为每个元素所占的空间线性表的依次存储结构(依次表)具有逻辑上相邻的元素，物理位置上也相邻的特点。依次表是一种随机存取的存储结构通常用数组描述依次表依次表的表示structsqlistttdefineLEN100#define1.EN100int*elem;structsqlistintaLEN:;intlength;intaLEN;intlength;intlistsize;intlength;)；依次表的操作依次表初始化依次表的插入依次表的删除移动大量元素依次表的查找线性表的插入(n+l)al,a2,ai-l,ai,ai+l,an插入位置的推断(n+l)(q)(P)元素移动的依次和位置al,a2,ai-l,b,ai,ai+l,an表长的变更线性表的删除(n-l)al,a2,ai-l,ai,ai+l,an删除位置的推断(p)(q)元素移动的依次和位置al,a2,ai-l,ai+l,an表长的变更时间困难度求表长O(I)查找第i个元素、前趋、后继0(1)查找值为X的元素的位序0(n)插入元素0(n)(0+l+n)(n+l)=n2删除元素0(n)(0+l÷+n-l)n=(n-l)2依次表适用于不常进行插入、删除运算，表中元素相对稳定的场合。线性表的链式表示和实现线性链表线性表的链式存储结构是用一组随意的(可连续、也可不连续)存储单元存储线性表的数据元素。为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其干脆后继的信息。即指针为数据元素之间逻辑关系的映象。结点包括两个域：数据域和指针域(链)，n个结点链接成一个(单)链表。指示链表中第一个结点地址的指针称为头指针，最终一个结点的指针为空(NULL)。单链表可由头指针唯一确定。链表的表示#defineNULLOstructnodeintdata;structnode*next;structnode*head;Ahead为头指针/若head=NULL,则表示空表。h为处理便利，在单链表的第一个结点前附设一个结点，称为头结点。此时，head-next指向第一个结点。P指向第i个结点，则p-data=ai;p-next-data=ai+1;单链表是一种非随机(依次)存储结构。单链表的操作查找第i个元素0(n)指针p从指向第一个结点的位置(head-next)向后移动(p=p-next)i-l次。插入0(n)(1)查找插入点的前趋结点p(2)生成新结点S(3)s-next=p-next;(4)p-next=s;删除0(n)headppnneexxttppp-nextsppp-nneexxtt-nneexxttpp-nneexxttppp-next=p-next-next建立含头结点的单链表(动态生成)head=(structnode*)malloc(sizeof(structnode);head-next=NULL;q=(structnode*)malloc(sizeof(structnode);(1)依次从表头至表尾设p为指向链表当前最终一个结点的指针p-next=q;p=q;(2)逆序从表尾至表头q-next=head-next;head-next=q;(3)有序递增或递减循环链表最终一个结点的指针域指向头结点，形成一个环。空表：head-next=head;双向链表结点含两个指针域，分别指向干脆前趋和后继。p-next-priou=p-priou-next=p双向循环链表链表在空间上利用合理，插入、删除便利，很多场合是线性表的首选存储结构。栈和队列栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。栈后进先出的线性表（LIFO）抽象数据类型的定义栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除）ala2an-1an栈底栈顶栈的表示和实现依次栈栈的依次存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在依次栈中的位置。typedefstructint*base;int*top;sqstack;#defineMAX100TypedefstructintstackMAXinttop;SEQSTACK;SEQSTACK*s;构造空栈s.top=s.bases-top二0返回栈顶元素e=*（s.top-1）e=s.stacks.top-1入栈*s.top+=es-stacks-top=es-top=s-top+l出栈e=*-s.tope=s-stacks-top-ls-top=s-top-l栈满s.top-s.base=MAXs-top=MAX链栈栈的链式表示栈顶指针为top栈空top=NULL;入栈生成新结点sSTink=top;top=s;出栈输出top-data;top=top-link;栈的应用举例intcheck(SEQSTACK*s)数制转换i11tbool;charch;括号匹配的检验push(s,#);bool=l;行编辑程序ch=getchar();表达式求值while(ch!-nbool)栈与递归if(Ch=()push(s,ch);if(Ch=)if(gettop(s)bool=0;elsepop(s);ch=getchar();if(gettop(s)1-#)bool=0;*(多于)*/if(bool)printf(rigth);elserintf(error);队列先进先出的线性表(FIFO)抽象数据类型队列的定义队列是限定在表的一端(对尾)进行插入，而在另一端(队头)进行删除操作的线性表。基本操作：入队列(插入)和出队列(删除)出队列ala2an-lan入队列队头队尾链队列队列的链式表示和实现typedefstructqnodeintdata;structqnode*next;QNODEtypedefstructQNODE*front,*rear;LINKQUEUE;1.INKQUEUE*q;链队列初始化q-front=q-rear=(QNODE*)maHoc(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循环队列队列的依次表示和实现typedefstructintdataMAXintfront,rear;seqqueue；seqqueue*q；头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。由于存在假溢出(q-rear=MAX),可将依次队列臆造成一个环状空间，称为循环队列。队空和队满的判别条件相同：q-front=q-rear两种处理方法：(1)增设标记位(2)少用一元素空间。队空：q-front=q-rear队满：q-front=(q-rear+l)%MAX串串类型的定义串(String)(或字符串)是由零个或多个字符组成的有限序列。记为：S=ala2an(n0)S为串名，单引号括起来的字符序列是串的值，n为串的长度。子串主串中随意个连续字符组成的子序列。位置字符在序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中位置来表JO串相等两个串的长度相等，且每个对应位置的字符都相等。空串零个字符的串为空串，长度为0,用表示。空格串由一个或多个空格组成的串为空格串。长度为空格字符的个数。串的基本操作：通常以串的整体为操作对象。串赋值串复制求子串判空串串连接子串定位串比较串替换求串长串插入串清空串删除串的表示和实现定长依次存储表示为每个串变量安排一个固定长度地址连续的存储区。defineMAX255unsignedcharsstringMAX+l;0号单元存放串的长度。堆安排存储表示在程序执行过程中，为每个串变量动态安排(malloc)一个地址连续的存储区。串的块链存储表示defineCSIZE80块的大小typedefstructChunkcharchCSIZE;structChunk*next;Chunk;typedefstructChunk串长度*head,*tail;头尾指针intcurlen;1.string;数组数组的定义数组的性质数组元素数目固定，一旦定义，维数和维界就不再变更。数组元素具有相同的类型。数据元素的下标关系具有上下界的约束并且下标有序。数组的描述ji=O,bi-l,i=l,2,n,bi是数组第i维的长度D=ajlj2jnn（0）为数组的维数，ji是数组元素的第i维下标n=l表示一维数组，是线性表。n=2表示二维数组，以矩阵形式表示，它也可以看成是线性表，其中每个数据元素本身又是一个线性表。数组的基本操作初始化数组销毁数组取元素给定一组下标，返回相应的数组元素值。修改元素值（赋值）给定一组下标，修改相应的数组元素的值。数组的依次表示和实现数组运算通常是随机访问与修改，一般不作插入或删除，故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变动，所以数组采纳依次存储结构表Jo存储单元是一维结构，而数组是多维结构，用一组地址连续的存储单元存放数组元素有次序约定的问题。对于数组，一旦规定了它的维数和各维的长度（下标的界限），就可安排空间，并依据给定的一组下标求得相应数组元素的存储位置。一维数组LOC(ai)=LOC(a)+i*L二维数组(m*n)行序为主序(a00,al,a,11-1,al,all,am-l,n-l)LOC(i,j)=LOC(O,O)÷(i*n+j)*L列序为主序(aOO,al,am-l,0),al,all,am-l,11-1)LOC(i,j)=LOC(O,O)+(j*m+i)*L三维数组(m*n*p)左下标(行)为主序(aOOO,a001,aOO,p-1,a010,am-l,n-l,PT)LOC(i,j,k)=LOC(O,O,O)+(i*n*p+j*p+k)礼右下标(列)为主序多维数组(bl*b2*bn)LOC(jl,j2,jn)=LOC(O,O,O)+(jl*b2*bn+j2*b3*bn+jnT*bn+jn)*L若确定了数组的各维长度，则bl*bn为常数，数组元素的存储位置是其下标的线性函数，由于存取数组中任一元素的时间相等，故此结构为随机存储结构。矩阵的压缩存储若矩阵阶数很高，且矩阵中有很多值相同的元素或者零元素，为节约存储空间，对矩阵进行压缩存储，即为多个值相同的元只安排一个存储空间，对零元不安排空间假如值相同的元素或者零元素在矩阵中的分布有肯定的规律，这类矩阵为特别矩阵，否则为稀疏矩阵。特别矩阵可将非零元压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。特别矩阵N阶对称矩阵元素关于主对角线对称aij=aji0=i,j=n-l只需存储上三角或下三角元素。存储元素总个数为d+2÷÷n)=n*(n+l)/2假设以行序为主序存储下三角中的元当i=jk=i*(i-l)2+j-l当ijk=j*(j-l)2+i-l上、下三角矩阵矩阵的下(上)三角(不包括对角线)中的元均为常数或零的n阶矩阵。只需存储上(下)三角中的元，再外加一个存储常数c的存储空间。下三角矩阵：当i=jk=i*(iT)2+j-l当ijk=n*(n+l)2÷1对角矩阵全部的非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和主对角线邻近的上、下方以外，其余元素均为零。稀疏矩阵在矩阵A(m*n)中，S为非零元素的个数，t为零元素的个数，若st,则A为稀疏矩阵。稀疏因子-t/(m)=0.05o由于稀疏矩阵的非零元素分布没有任何规律，压缩存储除了存储非零元素值外，还必需同时存储它的位置。稀疏矩阵的每个非零元素由一个三元组(i,j,aij)唯一确定。稀疏矩阵可由表示非零元的三元组及其矩阵的行列数唯一确定。三元组的表示三元组依次表行逻辑链接的依次表十字链表树和二叉树树的定义和基本术语树(tree)是n(n=0)个结点的有限集。在随意一棵非空树中：(I)有且仅有一个特定的称为根(root)的结点；(2)当nl时，其余结点可分为m(m)个互不相交的有限集Tl,T2Tm,其中每一个集合本身又是一棵树，称为根的子树。树的基本操作建树求孩子结点求根结点求兄弟结点求双亲结点结点的插入、删除树的表示形式树形表示嵌套集合表示广义表表示凹入表表示基本术语树的结点指一个数据元素及若干指向其子树的分支。通常以结构体来描述。结点的度结点拥有的子树数。度为0的结点称为叶子或终端结点；度不为0的结点称为非终端结点或分支结点。树的度树内各结点度的最大值。孩子和双亲结点的子树的根为该结点的孩子，该结点为孩子的双亲。结点的层次根为第一层，依次类推。兄弟和堂兄弟双亲相同的结点为兄弟，双亲在同一层次的结点为堂兄弟。祖先和子孙从根到该结点所经分支上的全部结点为该结点的祖先；以某结点为根的子树中的任一结点都称为该结点的子孙。树的深度(高度)树中结点的最大层次。有序树和无序树假如将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。森林是m（m=0）个棵互不相交的树的集合。二叉树二叉树的定义二叉树的每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能随意颠倒（有序树）。二叉树的基本操作建树（空树、非空树）求根结点、双亲、孩子、兄弟结点二叉树的遍历插入、删除二叉树的五种基本形态空二叉树仅有根结点的二叉树左子树为空的二叉树右子树为空的二叉树左、右子树均非空的二叉树二叉树的性质在二叉树的第i层上至多有2i-l个结点（i=l）深度为k的二叉树至多有2k-l个结点（k=l）对任何一棵二叉树T,假如其终端结点数为n,度为2的结点数为n2,则n=n2÷l一棵深度为k且有2k-l个结点的二叉树称为满二叉树，其每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n结点一一对应时，称之为完全二叉树。具有n个结点的完全二叉树的深度为k=log2n+l假如对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（i=l=n）（1）i=l,结点i为二叉树的根；若il,则双亲结点是i2(2)假如2in,则结点无左孩子；否则其左孩子是结点2io(3)假如2i+ln,则结点无右孩子；否则其右孩子是结点2i÷l0二叉树的存储结构依次存储结构用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即完全二叉树上编号为i的结点存储在一维数组中下标为iT的重量中。对一般二叉树，依次存储结构必需能反映结点之间的逻辑关系(父子关系)，故将其每个结点与完全二叉树相比照进行存储。这种依次存储结构仅适用于完全二叉树。最坏状况下，k个结点、深度为k的二叉树须要2k-1个结点的存储空间。链式存储结构头指针指向根结点。二叉链表存储结点的一个数据元素和分别指向其左、右子树的两个指针。三叉链表增加一个指向双亲结点的指针域。typedefstructtnodeintdata;structtnode*lchild,*rchild;TNODE;TNODE*root;在n个结点的二叉链表中有n÷l个空链域。建立二叉树遍历二叉树和线索二叉树遍历二叉树遍历二叉树是指如何按某条搜寻路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。(即将二叉树的结点排成一个线性队列)一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。若限定先左(L)后右(R),则遍历方法有先序遍历(DLR)、中序遍历(LDR)和后序遍历(LRD)三种。先序遍历二叉树的递归算法访问根-先序遍历左子树-先序遍历右子树voidpreorder(TNODE*bt)if(bt!=NULL)printf(%d,bt-data);preorder(bt-lchiId);preorder(bt-rchiId);中序遍历二叉树的递归算法(inorder)中序遍历左子树-访问根-中序遍历右子树后序遍历二叉树的递归算法(postorder)后序遍历左子树-后序遍历右子树-访问根表达式的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。将表达式表示为二叉树，若表达式=Xy,则根结点存放运算符，左子树表示X,右子树表示yoa÷b*(c-d)-ef波兰式：表达式二叉树的前序中缀表示：中序逆波兰式：后序从递归执行过程的角度先序、中序和后序是完全相同的。线索二叉树遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。但以二叉链表作为存储结构时，只能找到结点的左右儿子信息,而没有前趋和后继的信息。由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。Typedefstructbtnodechardata;structbtnode*lchild,*rchild;intltag,rtag;BTNODE;Itag=O!child指示结点的左儿子Itag=I!child指示结点的前趋rtag=0Ichild指示结点的右儿子rtag=lIchild指示结点的后继树和森林树的存储结构双亲表示法用一组地址连续的空间存放树中的结点，每个结点存放本身的信息和双亲结点所在的位置序号。孩子表示法多重链表每个结点有多个指针域，分别指向其每个子树。同构或不同构。孩子链表每个结点有一个孩子链表，n个结点链表的头指针依次存储。孩子双亲表示法双亲表示和孩子链表表示法结合起来。孩子兄弟表示法二叉链表表示法*二叉链表作为树的存储结构，链表中的两个指针域分别指向该结点的第一个孩子和该结点的下一个兄弟。树、森林与二叉树的转换以二叉链表作为转换的依据。树转化成二叉树后，二叉树根肯定没有右子树。森林的其次棵树树根看成是第一棵树树根的兄弟。树与森林的遍历树的先序遍历是指先访问树的根结点，然后依次先序遍历根的各子树。等价于先序遍历该树对应的二叉树。树的后序遍历是指先依次后序遍历树的根结点的各子树，然后访问根结点。等价于中序遍历该树对应的二叉树。先序遍历森林是指从左到右依次按先序遍历森林中的每一棵树，相当于先序遍历该森林对应的二叉树。后序遍历森林是指从左到右依次按后序遍历森林中的每一棵树，相当于中序遍历该森林对应的二叉树。赫夫曼树及其应用最优二叉树赫夫曼树从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中全部叶子结点的带权路径长度之和，记作WPLo假设有11个权值wl,w2,wn,试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。赫夫曼算法构造赫夫曼树依据给定的11个权值构成11棵二叉树的集合F,每棵二叉树Ti只有一个带权为wi的根结点。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，其根结点的权值为左右子树根结点的权值之和。在F中删除这两棵树，将新二叉树加入F重复构造，直到F中只含一棵树为止，这棵树就是赫夫曼树。赫夫曼编码电报码电文的总长尽可能短出现次数多的字符采纳尽可能短的编码。任一个字符的编码都不是另一个字符编码的前缀前缀编码。设计电文总长最短的二进制前缀编码即为以11种字符出现的频率作权，设计一棵赫夫曼树的问题。约定赫夫曼树的左分支表示字符0,右分支表示字符1,从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。图图是困难的非线性结构，结点之间的关系是随意的，任何两个数据元素都可能相关。图的应用极为广泛。图的定义和术语图是两个集合的二元组，G=(V,E),V表示顶点的有穷非空集合，E是顶点之间关系的有穷集合。若图中的每条边都是有方向的，顶点之间的关系V,w表示从V到W的一条弧，V为弧尾或初始点，W为弧头或终端点，该图为有向图。若图中的每条边无方向，有V,W必有W,V,顶点之间的关系以无序对V,W表示，表示从V到W的一条边，该图为无向图。n表示图中顶点数目，e表示边或弧的数目，若不考虑顶点自身的边或弧，无向图e的取值范围是On(n-1)/2,具有n(n-l)/2条边的无向图为完全图；有向图e的取值范围是0"n(n-l),具有n(n-l)条边的有向图为有向完全图。有很少条边或弧(enlogn)的图为稀疏图，反之为稠密图。与图的边或弧相关的数称为权，带权的图称为网。假设两个图，G=(V,E)和G=(V,G),假如VV且EE,则称G为G的子图。图从顶点V到V的路径是一个顶点序列，路径长度是路径上的边或弧的数目。第一个顶点和最终一个顶点相同的路径称为回路或环，序列中顶点不重复的回路为简洁路径。除第一个顶点和最终一个顶点之外，其余顶点不重复出现的回路为简洁回路或简洁环。无向图若边(V,w)E,则称顶点V,W互为邻接点,即V,W相邻接，边(V,W)依附于顶点V,W,边(V,W)和顶点相关联。顶点的度是和V相关联的边的数目，记为TD(v)O无向图中，若顶点V到顶点V有路径，称V和V是连通的。若对于图中随意两个顶点V,W都是连通的，则该图为连通图。连通重量是无向图中的极大连通子图。一个连通图的生成树是一个微小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。假如在树上添加一条边，必定构成一个环。有n-1条边的图不肯定是生成树。有向图若弧(v,w)E,则称顶点V邻接到顶点w,顶点W邻接自顶点V,弧(v,w)和顶点V,w相关联。以顶点V为头的弧的数目为V的入度ID(v),以V为尾的弧的数目为V的出度OD(V),顶点V的度TD(v)=ID(v)+0D(v)。有向图中，每一对(V,w)V,若V到W和W到V都存在路径，则G是强连通图。有向图中的极大强连通子图是有向图的强连通重量。若一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。一棵有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。图的存储结构数组表示法两个数组分别存储数据元素（顶点）信息和数据元素之间关系（边或弧）信息邻接矩阵。邻接表无向图的邻接表为每个顶点建立一个单链表，链表中的结点表示依附于该顶点的边。结点由三个域组成，其中邻接点域表示与该顶点邻接的点在图中的位置，链域指示下一条边的结点，数据域存储和边相关的信息。各顶点链表的表头结点通常以依次结构的形式存储，以便随机访问任一顶点的链表。有向图的邻接表和逆邻接表邻接表链表中的结点表示以该顶点为尾的弧，而逆邻接表链表中的结点表示以该顶点为头的弧。十字链表（有向图）两类结点弧结点和顶点结点邻接多重表（无向图）图的遍历深度优先搜寻广度优先搜寻