数据结构课程的主要内容

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

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

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

4、的存储结构通常用数组描述顺序表-*顺序表的表示struct sqlist#defineLEN100#defineLEN100int*elem;struct sqlistintaLEN;intlength;intaLEN;intlength;intlistsize;intlength;?顺序表的操作顺序表初始化顺序表的插入顺序表的删除移动大量元素顺序表的查找线性表的插入 (n+1)a1,a2, ai-1, ai, ai+1 , an插入位置的判断 (n+1)(q)(p)元素移动的顺序和位置a1,a2, ai-1,b,ai,ai+1 , an表长的变化? 线性表的删除 (n-1)a1,a2, ai

5、-1,ai ,ai+1, an删除位置的判断(p)(q)元素移动的顺序和位置a1,a2, ai-1, ai+1, an表长的变化?时间复杂度求表长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)/2? 顺序表适用于不常进行插入、 删除运算，表中元素相对稳定的场合。? 线性表的链式表示和实现 线性链表线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其直接

6、后继的信息。 即指针为数据元素之间逻辑关系的映象。结点包括两个域：数据域和指针域（链） ，n 个结点链接成一个（单）链表。指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空 (NULL) 。单链表可由头指针唯一确定。h链表的表示#defineNULL 0structnodeintdata;structnode*next;structnode*head;/*head 为头指针 /若 head=NULL ，则表示空表。-*headpp->next为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。此时， head->next 指向第一个结点。p 指向第 i 个结点

7、，则 p->data=ai;p->next->data=a i+1;单链表是一种非随机（顺序）存储结构。单链表的操作?查找第 i 个元素O(n)指针 p 从指向第一个结点的位置（head->next）向后移动（p=p->next）i-1 次。? 插入 O(n)pp->nexts（1）查找插入点的前趋结点p（2）生成新结点 s（3）s->next=p->next;（4）p->next=s;删除 O(n)pp->nextp->next->next-*p->next=p->next->next? 建立含头结点的

8、单链表（动态生成）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;? 双向链表结点含两个指针域，分

9、别指向直接前趋和后继。-*p->next->priou=p->priou->next=p双向循环链表链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。栈和队列栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。? 栈后进先出的线性表（ LIFO）抽象数据类型的定义栈是限定仅在表尾进行插入或删除操作的线性表。 表尾称为栈顶，表头称为 栈底。基本操作：取栈顶元素（查找） 、入栈（插入）和出栈（删除）a1a2a -ann 1栈底栈顶栈的表示和实现顺序栈栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针

10、top 指示栈顶元素在顺序栈中的位置。typedef struct int *base;-*int *top;sqstack;#define MAX 100Typedefstructint stackMAXint top;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+1出栈e=*-s.tope=s->stacks->top-1s->top=s-&g

11、t;top-1栈满s.top-s.base=MAXs->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 (get

12、top(s)=#) bool=0; else pop(s);ch=getchar(); if (gettop(s)!=#) bool=0; /*( 多于) */if (bool) printf(“rigth”);-*else rintf(“error ”);? 队列先进先出的线性表（ FIFO）抽象数据类型队列的定义队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。基本操作：入队列（插入）和出队列（删除）出队列 a1a2a -1an入队列n队头队尾链队列队列的链式表示和实现typedefstruct qnodeintdata;struct qnode *next;Q

13、NODEtypedef 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->nex

14、tif (q->rear=p)q->rear=q->front循环队列队列的顺序表示和实现typedef structint dataMAXint front,rear;SEQQUEUE;SEQQUEUE *q;头指针始终指向队列头元素， 尾指针始终指向队列尾元素的下一个位置。由于存在假溢出 (q->rear=MAX) ，可将顺序队列臆造成一个环状空间，称为循环队列。队空 和队满的判别条件相同：q->front=q->rear-*两种处理办法 :(1) 增设标志位(2) 少用一元素空间。队空： q->front=q->rear队满： q->

15、front=(q->rear+1)%MAX串串类型的定义? 串（ String ）（或字符串）是由零个或多个字符组成的有限序列。记为： s=a1a2 an(n 0)? S 为串名，单引号括起来的字符序列是串的值，n 为串的长度。? 子串主串中任意个连续字符组成的子序列。? 位置字符在序列中的序号为该字符在串中的位置。 子串在 主串中的位置以子串的第一个字符在主串中位置来表示。? 串相等两个串的长度相等，且每个对应位置的字符都相等。? 空串零个字符的串为空串，长度为 0，用 ? 表示。? 空格串由一个或多个空格组成的串为空格串。长度为空格字符的个数。? 串的基本操作：通常以“串的整体”为操

16、作对象。? 串赋值串复制? 求子串判空串? 串连接子串定位-*? 串比较串替换? 求串长串插入? 串清空串删除串的表示和实现? 定长顺序存储表示为每个串变量分配一个固定长度地址连续的存储区。#define MAX 255unsigned char sstringMAX+1;0 号单元存放串的长度。? 堆分配存储表示在程序执行过程中，为每个串变量动态分配（malloc)一个地址连续的存储区。? 串的块链存储表示#define CSIZE 80/typedef struct Chunk char chCSIZE;struct Chunk *next;Chunk;typedef struct 块的大

17、小Chunk *head,*tail;/头尾指针int curlen;Lstring;/ 串长度-*数 组数组的定义 数组的性质数组元素数目固定，一旦定义，维数和维界就不再改变。数组元素具有相同的类型。数据元素的下标关系具有上下界的约束并且下标有序。 数组的描述ji=0 ， ， bi-1, i=1,2,n,bi是数组第i维的长度D=aj1j2 jn |n(>0) 为数组的维数， j i 是数组元素的第i 维下标 n=1 表示一维数组，是线性表。n=2 表示二维数组，以矩阵形式表示， 它也可以看成是线性表，其中每个数据元素本身又是一个线性表。 数组的基本操作初始化数组销毁数组取元素给定一组

18、下标，返回相应的数组元素值。修改元素值（赋值）给定一组下标，修改相应的数组元素的值。数组的顺序表示和实现数组运算通常是随机访问与修改， 一般不作插入或删除， 故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变-*动，所以数组采用 顺序存储结构 表示。 存储单元是一维结构， 而数组是多维结构， 用一组地址连续的存储单元存放数组元素有次序约定 的问题。对于数组，一旦规定了它的维数和各维的长度 （下标的界限），就可分配空间，并根据给定的一组下标求得相应数组元素的存储位置。 一维数组LOC(a i )=LOC(a0)+i*L 二维数组 (m*n)行序为主序（ a00,a 01, ,a 0,n-

19、1 ,a 10,a 11, am-1,n-1 )LOC(i,j)=LOC(0,0)+(i*n+j)*L列序为主序（ a00,a 10, ,a m-1,0) ,a 01,a 11, am-1,n-1 )LOC(i,j)=LOC(0,0)+(j*m+i)*L 三维数组 (m*n*p)左下标（行）为主序（ a000,a 001, a00,p-1 ,a 010, 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(j 1,j 2,j n )=LOC(0,0,0)+(j 1*b 2*b n+j 2

20、*b 3*b n+j n-1 *b n+j n)*L-*若确定了数组的各维长度，则 bl * *b n 为常数，数组元素的存储位置是其下标的线性函数， 由于存取数组中任一元素的时间相等，故此结构为随机存储结构。矩阵的压缩存储 若矩阵阶数很高，且矩阵中有许多值相同的元素或者零元素，为节省存储空间， 对矩阵进行压缩存储， 即为多个值相同的元只分配一个存储空间，对零元不分配空间 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，这类矩阵为特殊矩阵， 否则为稀疏矩阵。 特殊矩阵可将非零元压缩存储到一维数组中， 并找到每个非零元在一维数组中的对应关系。 特殊矩阵N阶对称矩阵元素关于主对角线对称aij

21、=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对角矩阵所有的非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和主对角线邻近的上、下方以外，其余元素均

22、为零。 稀疏矩阵在矩阵 A（m*n)中，s 为非零元素的个数， t 为零元素的个数，若 s<<t ，则 A 为稀疏矩阵。稀疏因子 =t/(m*n)<=0.05 。由于稀疏矩阵的非零元素分布没有任何规律， 压缩存储除了存储非零元素值外，还必须同时存储它的位置。稀疏矩阵的每个非零元素由一个三元组（i ，j ，aij ) 唯一确定。稀疏矩阵可由表示非零元的三元组及其矩阵的行列数唯一确定。三元组的表示 三元组顺序表 行逻辑链接的顺序表 十字链表-*树和二叉树树的定义和基本术语树(tree) 是 n(n>=0) 个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根

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

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

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

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

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

28、二叉树遍历二叉树遍历二叉树是指如何按某条搜索路径巡访树中的每个结点， 使得每个结点均被访问一次，而且仅被访问一次。 ( 即将二叉树的结点排成一个线性队列 )一棵非空二叉树是由根结点、 左子树和右子树三个基本部分组成，依次遍历这三部分， 便能遍历整个二叉树。 若限定先左（L）后右（ R），则遍历方法有先序遍历（DLR）、中序遍历（ LDR）和后序遍历（ LRD）三种。先序遍历二叉树的递归算法访问根 -> 先序遍历左子树 -> 先序遍历右子树void preorder(TNODE *bt) if(bt!=NULL)printf(“%d ”,bt ->data);preorder(

29、bt->lchild);preorder(bt->rchild);中序遍历二叉树的递归算法（inorder)中序遍历左子树 -> 访问根 -> 中序遍历右子树后序遍历二叉树的递归算法(postorder)后序遍历左子树 -> 后序遍历右子树 -> 访问根表达式的前缀表示（波兰式） 、中缀表示和后缀表示（逆波兰式）。-*将表达式表示为二叉树， 若表达式 =x y，则根结点存放运算符，左子树表示 x，右子树表示 y。a+b*(c-d)-e/f波兰式：表达式二叉树的前序中缀表示：中序逆波兰式：后序从递归执行过程的角度先序、中序和后序是完全相同的。线索二叉树遍历二叉

30、树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。 但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信息。由于在 n 个结点的二叉链表中必定存在 n+1 个空链域，可以利用空链域存放结点的前趋和后继的信息。二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索； 加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。Typedef struct btnodechar data;struct btnode *lchild, *rchild;int ltag, rtag;BTNODE;

31、ltag=0lchild指示结点的左儿子-*ltag=1lchild指示结点的前趋rtag=0lchild指示结点的右儿子rtag=1lchild指示结点的后继树和森林树的存储结构双亲表示法用一组地址连续的空间存放树中的结点，每个结点存放本身的信息和双亲结点所在的位置序号。孩子表示法? 多重链表每个结点有多个指针域，分别指向其每个子树。同构或不同构。? 孩子链表 每个结点有一个孩子链表， n 个结点链表的头指针顺序存储。? 孩子双亲表示法双亲表示和孩子链表表示法结合起来。孩子兄弟表示法二叉链表表示法*二叉链表作为树的存储结构，链表中的两个指针域分别指向该结点的第一个孩子和该结点的下一个兄弟。树

32、、森林与二叉树的转换以二叉链表作为转换的依据。树转化成二叉树后，二叉树根一定没有右子树。森林的第二棵树树根看成是第一棵树树根的兄弟。树与森林的遍历-*树的先序遍历是指先访问树的根结点， 然后依次先序遍历根的各子树。等价于先序遍历该树对应的二叉树。树的后序遍历是指先依次后序遍历树的根结点的各子树， 然后访问根结点。等价于中序遍历该树对应的二叉树。先序遍历森林是指从左到右依次按先序遍历森林中的每一棵树，相当于先序遍历该森林对应的二叉树。后序遍历森林是指从左到右依次按后序遍历森林中的每一棵树，相当于中序遍历该森林对应的二叉树。赫夫曼树及其应用最优二叉树赫夫曼树从树中一个结点到另一个结点之间的分支构成

33、这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作 WPL。假设有 n 个权值 w1 ,w2, ,wn ，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 wi ，则其中带权路径长度 WPL最小的二叉树称做最优二叉树或赫夫曼树。赫夫曼算法构造赫夫曼树根据给定的 n 个权值构成 n 棵二叉树的集合 F，每棵二叉树 Ti 只有一个带权为 wi 的根结点。在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新-*二叉

34、树，其根结点的权值为左右子树根结点的权值之和。在 F 中删除这两棵树，将新二叉树加入F重复构造，直到 F 中只含一棵树为止，这棵树就是赫夫曼树。赫夫曼编码电报码电文的总长尽可能短出现次数多的字符采用尽可能短的编码。任一个字符的编码都不是另一个字符编码的前缀前缀编码。设计电文总长最短的二进制前缀编码即为以 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