数据结构课程的主要内容

1、-*数据结构课程的主要内容数据结构的基本概念?基本概念和术语?算法和算法分析（典型算法）线性表?线性表的概念定义和特点?线性表的实现一一顺序表示和链式表示（特点、定义）?线性表的基本操作一一建立（正序、逆序、有序）、查找、插入、删除、输出?线性表的应用一一合并、时间复杂度?循环链表和双向链表栈和队列?栈和队列的定义?栈的表示、实现和操作（出栈、入栈）?队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）串（串的基本概念和基本操作）数组?数组的定义?数组的地址计算（一维、二维、三维）?特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）树和二叉树?树的定义和基本术语?二叉树O二叉

2、树的性质O二叉树的存储结构O二叉树的遍历?树和森林O树的存储结构O树、森林与二叉树的转换O树和森林的遍历?哈夫曼树及其应用图?图的定义和术语?图的存储结构?图的遍历查找?查找的基本概念?静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析?动态查找表（二叉排序树和平衡二叉树）?哈希表排序（直接插入、冒泡、选择、快速和归并）第一章数据结构课程的主要内容（二）线性表?线性表的类型定义线性表是n个（n0）数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最后一个元素，除次之外，每个元素

3、有唯一的前驱和唯一的后继。线性表（ai,ai,ai,a+i,nan为线性表的长度，i为元素在线性表中的位序。线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用）?线性表的顺序表示和实现一一顺序表线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素。LOC（ai）=LOC（ai）+（i-1）*ll为每个元素所占的空间线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素，物理位置上也相邻的特点。顺序表是一种随机存取的存储结构通常用数组描述顺序表顺序表的表示structsqlistint*elem;int

4、length;intlistsize;)；#defineLEN100structsqlistintaLEN;intlength;);#defineLEN100intaLEN;intlength;顺序表的操作顺序表初始化顺序表的插入顺序表的删除移动大量元素?顺序表的查找?线性表的插入(n+1)a1,&,a-1,a,a+1,制(q)(p)日,&,牛1,b,a,a+1,泰?线性表的删除(n-1)日,血a-1,a,a+1,名(p)(q)日,&,0，ai+1,?时间复杂度求表长O(1)查找第i个元素、前趋、后继插入位置的判断(n+1)元素移动的顺序和位置表长的变化删除位置的判断元

5、素移动的顺序和位置表长的变化O(1)查找值为x的元素的位序O(n)插入元素O(n)(0+1+n)/(n+1)=n/2删除元素O（n）（0+1+n-1）/n=（n-1）/2?顺序表适用于不常进行插入、删除运算，表中元素相对稳定的场合。?线性表的链式表示和实现一一线性链表线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其直接后继的信息。即指针为数据元素之间逻辑关系的映象。结点包括两个域：数据域和指针域（链），门个结点链接成一个（单）链表。指示链表中第一个结点地址的指针称为头指针，最后一个结

6、点的指针为空（NULL）。单链表可由头指针唯一确定。链表的表示#defineNULL0structnodeintdata;structnode*next;structnode*head;/*head为头指针/若head=NULL,则表示空表。headp->next为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。此时，head->next指向第一个结点。P指向第i个结点，贝Up->data=a;p->next->data=ai+i；单链表是一种非随机(顺序)存储结构。单链表的操作?查找第i个元素O(n)指针p从指向第一个结点的位置(head->ne

7、xt)向后移动?插入O(n)(2)生成新结点s(p=p->next)i-1次。(1)查找插入点的前趋结点p(3) s->next=p->next;(4) p->next=s;删除O(n)p->next=p->next->next?建立含头结点的单链表(动态生成)head=(structnode*)malloc(sizeof(structnode);head->next=NULL;q=(structnode*)malloc(sizeof(structnode);(1)顺序一一从表头至表尾设p为指向链表当前最后一个结点的指针p->next=q;

8、p=q;(2)逆序一一从表尾至表头q->next=head->next;head->next=q;(3)有序一一递增或递减循环链表最后一个结点的指针域指向头结点，形成一个环空表：head->next=head;双向链表结点含两个指针域，分别指向直接前趋和后继。-*p->next->priou=p->priou->next=p双向循环链表链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。栈和队列栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。?栈一一后进先出的线性表（LIFO）抽象数据类型的定义o栈是限定

9、仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除）aia2an-1an栈底栈顶栈的表示和实现o顺序栈一一栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。typedefstructint*base;int*top;sqstack;#defineMAX100TypedefstructintstackMAXinttop;SEQSTACK;SEQSTACK*s;构造空栈s.top=s.base返回栈顶元素e=*(s.top-1)入栈*s.top+=e出栈e=*

10、-s.tops->top=0e=s.stacks.top-1s->stacks->top=es->top=s->top+1e=s->stacks->top-1s->top=s->top-1s.top-s.base=MAXs->top=MAX栈满链栈一一栈的链式表示栈顶指针为top栈空top=NULL;入栈生成新结点ss->link=top;top=s;出栈输出top->data;top=top->link;栈的应用举例intcheck(SEQSTACK*s)括号匹配的检验行编辑程序表达式求值栈与递归数制转换intbo

11、ol;charch;push(s,'#');bool=1;ch=getchar();while(ch!=n'&&bool)if(ch=，(')push(s,ch);if(ch=')')if(gettop(s)='#')bool=0;elsepop(s);ch=getchar();if(gettop(s)!=#')bool=0;/*'('多于')'*/if(bool)printf("rigth");elserintf（"error"）;?

12、队列一一先进先出的线性表（FIFO）抽象数据类型队列的定义队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。基本操作：入队列（插入）和出队列（删除）出队列aia2an-ian入队列“队头队i队队列一一队列的链式表示和实现typedefstructqnodeintdata;structqnode*next;QNODEtypedefstructQNODE*front,*rear;LINKQUEUE;LINKQUEUE*q;链队列初始化q->front=q->rear=（QNODE*）malloc（QNODE）;q->front->next=NUL

13、L;-*链队列判空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;头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个

14、位置。由于存在假溢出(q->rear=MAX),可将顺序队列臆造成一个环状空间，称为循环队列。队空和队满的判别条件相同：q->front=q->rear-*两种处理办法：(1)增设标志位(2)少用一元素空间。队空：q->front=q->rear队满：q->front=(q->rear+1)%MAX串串类型的定义?串(String)(或字符串)是由零个或多个字符组成的有限序列。记为：s='aa2an'(n0)?$为串名，单引号括起来的字符序列是串的值，n为串的长度。?子串一一主串中任意个连续字符组成的子序列。?子置一一字符在序列中的序号

15、为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中位置来表示。?串相等一一两个串的长度相等，且每个对应位置的字符都相等。?空串一一零个字符的串为空串，长度为0,用？表示。?空格串一一由一个或多个空格组成的串为空格串。长度为空格字符的个数。?串的基本操作：通常以“串的整体”为操作对象。?串赋值串复制?求子串判空串?串连接子串定位?串比较串替换?求串长串插入?串清空串删除串的表水和实现?定长顺序存储表不为每个串变量分配一个固定长度地址连续的存储区。#defineMAX255unsignedcharsstringMAX+1;0号单元存放串的长度。?堆分配存储表示在程序执行过程中，为每

16、个串变量动态分配（malloc）一个地址连续的存储区。?串的块链存储表示#defineCSIZE80/块的大小typedefstructChunkcharchCSIZE;structChunk*next;Chunk;typedefstructChunk*head,*tail;/头尾指针intcurlen;/串长度Lstring;数组数组的定义- 数组的性质数组元素数目固定，一旦定义，维数和维界就不再改变。数组元素具有相同的类型。数据元素的下标关系具有上下界的约束并且下标有序。- 数组的描述ji=0,，bi-1,i=1,2,n,bi是数组第i维的长度D=aij2jn|n(>0)为数组的维数

17、，ji是数组元素的第i维下标n=i表示一维数组，是线性表。n=2表示二维数组，以矩阵形式表示，它也可以看成是线性表，其中每个数据元素本身又是一个线性表。- 数组的基本操作初始化数组销毁数组取元素一一给定一组下标，返回相应的数组元素值。修改元素值(赋值)一一给定一组下标，修改相应的数组元素的值。数组的顺序表示和实现- 数组运算通常是随机访问与修改，一般不作插入或删除，故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变-*动，所以数组采用顺序存储结构表示。- 存储单元是一维结构，而数组是多维结构，用一组地址连续的存储单元存放数组元素有次序约定的问题。- 对于数组，一旦规定了它的维数和各维的

18、长度(下标的界限)，就可分配空间，并根据给定的一组下标求得相应数组元素的存储位置。- 一维数组LOC(ai)=LOC(a0)+i*L- 二维数组(m*n)行序为主序(aoo,a01,ao,n-i,aio,a11,mm-i,n-i)LOC(i,j)=LOC(0,0)+(i*n+j)*L列序为主序(a00,a10,.,am-1,0),a0i,a11,mm-i,n-i)LOC(i,j)=LOC(0,0)+(j*m+i)*L- 三维数组(m*n*p)左下标(行)为主序(a。,a001,a00,p-i,a010,mm-i,n-i,p-i)LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p+

19、k)*L右下标(列)为主序- 多维数组(b1*b2*bn)LOC(ji,j2,jn尸LOC(0,0,0)+(j1*b2*bn+j2*b3*bn+jn-1*bn+jn)*L-*-若确定了数组的各维长度，则bl*bn为常数，数组元素的存储位置是其下标的线性函数，由于存取数组中任一元素的时间相等，故此结构为随机存储结构。矩阵的压缩存储- 若矩阵阶数很高，且矩阵中有许多值相同的元素或者零元素，为节省存储空间，对矩阵进行压缩存储，即为多个值相同的元只分配一个存储空间，对零元不分配空间- 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，这类矩阵为特殊矩阵，否则为稀疏矩阵。特殊矩阵可将非零元压缩存储到

20、一维数组中，并找到每个非零元在一维数组中的对应关系。- 特殊矩阵N阶对称矩阵一元素关于主对角线对称aij=aji0<=i,j<=n-1只需存储上三角或下三角元素。存储元素总个数为(1+2+n)=n*(n+1)/2假设以行序为主序存储下三角中的元当i>=jk=i*(i-1)/2+j-1当i<jk=j*(j-1)/2+i-1-*上、下三角矩阵矩阵的下(上)三角(不包括对角线)中的元均为常数或零的n阶矩阵。只需存储上(下)三角中的元，再外加一个存储常数c的存储空间。下三角矩阵：当i>=jk=i*(i-1)/2+j-1当i<jk=n*(n+1)/2+1对角矩阵所有的

21、非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和主对角线邻近的上、下方以外，其余元素均为零。- 稀疏矩阵在矩阵A(m*n)中，s为非零元素的个数，t为零元素的个数，若s<<t,则A为稀疏矩阵。稀疏因子=t/(m*n)<=0.05。由于稀疏矩阵的非零元素分布没有任何规律，压缩存储除了存储非零元素值外，还必须同时存储它的位置。稀疏矩阵的每个非零元素由一个三元组(i,j,aj)唯一确定。稀疏矩阵可由表示非零元的三元组及其矩阵的行列数唯一确定。三元组的表示- 三元组顺序表- 行逻辑链接的顺序表- 十字链表-*树和二叉树树的定义和基本术语树(tree)是n(n>=

22、0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根(root)的结点；(2)当n>1时，其余结点可分为m(m>0)互不相交的有限集T1,T2Tm其中每一个集合本身又是一棵树，称为根的子树。树的基本操作建树求孩子结点求根结点求兄弟结点求双亲结点结点的插入、删除树的表水形式树形表示嵌套集合表示广义表表示凹入表表示基本术语树的结点一一指一个数据元素及若干指向其子树的分支。通常以结构体来描述。结点的度一一结点拥有的子树数。度为0的结点称为叶子或终端结点；度不为0的结点称为非终端结点或分支结点。树的度一一树内各结点度的最大值。孩子和双亲一一结点的子树的根为该结点的孩子，该

23、结点为孩子-*的双亲。结点的层次一一根为第一层，依次类推。兄弟和堂兄弟一一双亲相同的结点为兄弟，双亲在同一层次的结点为堂兄弟。祖先和子孙一一从根到该结点所经分支上的所有结点为该结点的祖先；以某结点为根的子树中的任一结点都称为该结点的子孙。树的深度（高度）结一树中结点的最大层次。有序树和无序树一一如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。森林是m（m>=0件棵互不相交的树的集合。二叉树二叉树的定义二叉树的每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。二叉树的基本操作建树（

24、空树、非空树）求根结点、双亲、孩子、兄弟结点二叉树的遍历插入、删除二叉树的五种基本形态空二叉树仅有根结点的二叉树左子树为空的二叉树右子树为空的二叉树左、右子树均非空的二叉树二叉树的性质在二叉树的第i层上至多有2i-1个结点(i>=1)深度为k的二叉树至多有2k-1个结点(k>=1)对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1一棵深度为k且有2k-1个结点的二叉树称为满二叉树，其每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的

25、满二叉树中编号从1至n结点一一对应时，称之为完全二叉树。具有n个结点的完全二叉树的深度为k=log2n+1如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(i<=1<=n)i=1,结点i为二叉树的根；若i>1,则双亲结点是i/2(2)如果2i>n,则结点无左孩子；否则其左孩子是结点2i。(3)如果2i+1>n,则结点无右孩子；否则其右孩子是结点2i+1。-*二叉树的存储结构顺序存储结构用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即完全二叉树上编号为i的结点存储在一维数组中下标为i-1的分量中。对一般二叉树，顺序存储结构

26、必须能反映结点之间的逻辑关系（父子关系），故将其每个结点与完全二叉树相对照进行存储。这种顺序存储结构仅适用于完全二叉树。最坏情况下，k个结点、深度为k的二叉树需要2k-1个结点的存储空间。链式存储结构一一头指针指向根结点。二叉链表一一存储结点的一个数据元素和分别指向其左、右子树的两个指针。三叉链表一一增加一个指向双亲结点的指针域。typedefstructtnodeintdata;structtnode*lchild,*rchild;TNODE;TNODE*root;在n个结点的二叉链表中有n+1个空链域。建立二叉树-*遍历二叉树和线索二叉树遍历二叉树遍历二叉树是指如何按某条搜索路径巡访树中的

27、每个结点，使得每个结点均被访问一次，而且仅被访问一次。（即将二叉树的结点排成一个线性队列）一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。若限定先左（L）后右（R）,则遍历方法有先序遍历（DLR、中序遍历（LDR和后序遍历（LRD三种。先序遍历二叉树的递归算法访问根，先序遍历左子树，先序遍历右子树voidpreorder（TNODE*bt）if（bt!=NULL）printf（"d”，bt->data）;preorder（bt->lchild）;preorder（bt->rchild）;中序遍历二叉树的递归算法（ino

28、rder）中序遍历左子树，访问根->中序遍历右子树后序遍历二叉树的递归算法（postorder）后序遍历左子树，后序遍历右子树->访问根表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。-*将表达式表示为二叉树，若表达式=乂y,则根结点存放运算符，左子树表木x,右子树表木y。a+b*(c-d)-e/f波兰式：表达式二叉树的前序中缀表示：中序逆波兰式：后序从递归执行过程的角度先序、中序和后序是完全相同的。线索二叉树遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信

29、息。由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。Typedefstructbtnodechardata;structbtnode*lchild,*rchild;intltag,rtag;BTNODE;ltag=0lchild指示结点的左儿子ltag=1Ichild指示结点的前趋rtag=0Ichild指示结点的右儿子rtag=1Ichild指示结点的后继树和森林树的存储结构双亲表

30、示法用一组地址连续的空间存放树中的结点，每个结点存放本身的信息和双亲结点所在的位置序号。孩子表示法?多重链表一一每个结点有多个指针域，分别指向其每个子树。同构或不同构。?孩子链表多一每个结点有一个孩子链表，n个结点链表的头指针顺序存储。?孩子双亲表示法一一双亲表示和孩子链表表示法结合起来。孩子兄弟表示法一一二叉链表表示法*二叉链表作为树的存储结构，链表中的两个指针域分别指向该结点的第一个孩子和该结点的下一个兄弟。树、森林与二叉树的转换以二叉链表作为转换的依据。树转化成二叉树后，二叉树根一定没有右子树。森林的第二棵树树根看成是第一棵树树根的兄弟。树与森林的遍历-*树的先序遍历是指先访问树的根结点

31、，然后依次先序遍历根的各子树。等价于先序遍历该树对应的二叉树。树的后序遍历是指先依次后序遍历树的根结点的各子树，然后访问根结点。等价于中序遍历该树对应的二叉树。先序遍历森林是指从左到右依次按先序遍历森林中的每一棵树，相当于先序遍历该森林对应的二叉树。后序遍历森林是指从左到右依次按后序遍历森林中的每一棵树，相当于中序遍历该森林对应的二叉树。赫夫曼树及其应用最优二叉树一一赫夫曼树从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为

32、树中所有叶子结点的带权路径长度之和，记作WPL假设有n个权值wi,W2,wn,试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为w,则其中带权路径长度WPLt小的二叉树称做最优二叉树或赫夫曼树。最夫曼算法构造赫夫曼树根据给定的n个权值构成n棵二叉树的集合F,每棵二叉树Ti只有一个带权为wi的根结点。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，其根结点的权值为左右子树根结点的权值之和。在F中删除这两棵树，将新二叉树加入F重复构造，直到F中只含一棵树为止，这棵树就是赫夫曼树。赫夫曼编码电报码电文的总长尽可能短一一出现次数多的字符采用尽可能短的编码。任一个字符的编码都不是另一个

33、字符编码的前缀一一前缀编码。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题。约定赫夫曼树的左分支表示字符'0',右分支表示字符1',从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。图图是复杂的非线性结构，结点之间的关系是任意的，任何两个数据元素都可能相关。图的应用极为广泛。图的定义和术语图是两个集合的二元组，G=(V,E),V表示顶点的有穷非空集合，E是顶点之间关系的有穷集合。若图中的每条边都是有方向的，顶点之间的关系<v,w>表示从v到w的一条吸V为弧尾或初始点，w为弧头或终端点，该图为有向图-*若图中的每条边无方向，有v,w必有w,v,顶点之间的关系以无序对v,w表示，表示从v到w的一条也该图为无向图。n表示图中顶点数目，e表示边或弧的数目，若不考虑顶点自身的边或弧，无向图e的取值