1、数据结构课程的主要内容数据结构课程的主要内容 数据结构的基本概念 基本概念和术语 算法和算法分析（典型算法） 线性表 线性表的概念定义和特点 线性表的实现顺序表示和链式表示（特点、定义） 线性表的基本操作建立（正序、逆序、有序）、查找、插入、删除、输出 线性表的应用合并、时间复杂度 循环链表和双向链表 栈和队列 栈和队列的定义 栈的表示、实现和操作（出栈、入栈） 队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列） 串（串的基本概念和基本操作） 数组 数组的定义 数组的地址计算（一维、二维、三维） 特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏） 树和二叉树 树的定义和基本
2、术语 二叉树 二叉树的性质 二叉树的存储结构 二叉树的遍历 树和森林 树的存储结构 树、森林与二叉树的转换 树和森林的遍历 哈夫曼树及其应用 图 图的定义和术语 图的存储结构 图的遍历 查找 查找的基本概念 静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析 动态查找表（二叉排序树和平衡二叉树） 哈希表 排序（直接插入、冒泡、选择、快速和归并）第一章 数据结构课程的主要内容（二）线性表 线性表的类型定义 线性表是n个（n0)数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。 在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最
3、后一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。 线性表（a1,ai-1,ai,ai+1, ,an） n为线性表的长度，i为元素在线性表中的位序。 线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用） 线性表的顺序表示和实现顺序表 线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素。LOC(ai)=LOC(a1)+(i-1)*l l为每个元素所占的空间 线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素， 物理位置上也相邻的特点。 顺序表是一种随机存取的存储结构 通常用数组描述顺序表 顺
4、序表的表示struct sqlist #define LEN 100 #define LEN 100 int *elem; struct sqlist int aLEN; int length; int aLEN; int length; int listsize; int length; ; ; 顺序表的操作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 线性表的删除
5、(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 顺序表适用于不常进行插入、删除运算，表中元素相对稳定的场合。 线性表的链式表示和实现线性链表 线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。 为表示元素间的逻辑关系，除了存储数据元素本身的信
6、息之外，还需存储一个指示其直接后继的信息。即指针为数据元素之间逻辑关系的映象。 结点包括两个域：数据域和指针域（链），n个结点链接成一个（单）链表。指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空(NULL)。单链表可由头指针唯一确定。 链表的表示 #define NULL 0 struct node int data; struct node *next; ;struct node *head; /*head为头指针/若head=NULL，则表示空表。 为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。此时，head-next 指向第一个结点。 p指向第i个结点，则
7、p-data=ai; p-next-data=a i+1; 单链表是一种非随机（顺序）存储结构。 单链表的操作v 查找第i个元素 O(n)指针p从指向第一个结点的位置（head-next）向后移动（p=p-next）i-1次。v 插入O(n)（1）查找插入点的前趋结点p （2）生成新结点s （3）s-next=p-next; （4）p-next=s;删除O(n) p-next=p-next-nextv 建立含头结点的单链表（动态生成） head=(struct node *) malloc (sizeof(struct node); head-next=NULL; q=(struct node
8、 *) malloc (sizeof(struct node);（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 双向循环链表 链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。栈和队列 栈和队列是两种重要的线性结构。从数据结构
9、角度看，它们是操作受限的线性表。 栈后进先出的线性表（LIFO） 抽象数据类型的定义 栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。 基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除） a1 a2 an-1 an 栈底 栈顶 栈的表示和实现 顺序栈栈的顺序存储结构 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。typedef struct int *base; int *top; sqstack;#define MAX 100 Typedef struct int stackMAX int top; S
10、EQSTACK;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;入栈 生成新结点s s-link=top; top=s;出栈 输出top-data; top=top-link;栈的应用举例 int check
11、(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）抽象数据类型队列的
12、定义 队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。 基本操作：入队列（插入） 和出队列（删除） 出队列 a1 a2 an-1 an 入队列 队头 队尾链队列队列的链式表示和实现 typedef struct qnode int data; struct qnode *next; QNODE typedef struct QNODE *front, *rear; LINKQUEUE;LINKQUEUE *q;链队列初始化q-front=q-rear=(QNODE*)malloc(QNODE); q-front-next=NULL;链队列判空 q-front=q-
13、rear;元素入队列 新生成结点s; s-next=NULL; q-rear-next=s; q-rear=s;元素出队列（非空队列） p=q-front-next; q-front-next=p-next if (q-rear=p) q-rear=q-front循环队列队列的顺序表示和实现 typedef struct int dataMAX int front,rear; SEQQUEUE; SEQQUEUE *q;头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。由于存在假溢出(q-rear=MAX)，可将顺序队列臆造成一个环状空间，称为循环队列。队空 和队满的判别条件相同
14、： q-front=q-rear两种处理办法:(1)增设标志位(2)少用一元素空间。队空： q-front=q-rear队满： q-front=(q-rear+1)%MAX串 串类型的定义 串（String）（或字符串）是由零个或多个字符组成的有限序列。记为：s=a1a2an(n0) S为串名，单引号括起来的字符序列是串的值，n为串的长度。 子串主串中任意个连续字符组成的子序列。 位置字符在序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中位置来表示。 串相等两个串的长度相等，且每个对应位置的字符都相等。 空串零个字符的串为空串，长度为0，用表示。 空格串由一个或
15、多个空格组成的串为空格串。长度为空格字符的个数。 串的基本操作：通常以“串的整体”为操作对象。 串赋值 串复制 求子串 判空串 串连接 子串定位 串比较 串替换 求串长 串插入 串清空 串删除 串的表示和实现 定长顺序存储表示 为每个串变量分配一个固定长度地址连续的存储区。 #define MAX 255 unsigned char sstringMAX+1; 0号单元存放串的长度。 堆分配存储表示 在程序执行过程中，为每个串变量动态分配（malloc) 一个地址连续的存储区。 串的块链存储表示 #define CSIZE 80 /块的大小 typedef struct Chunk char
16、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表示二维数组，以矩阵形式表示，它也可以看成是线性表，其
17、中每个数据元素本身又是一个线性表。 数组的基本操作 初始化数组 销毁数组 取元素给定一组下标，返回相应的数组元素值。 修改元素值（赋值）给定一组下标，修改相应的数组元素的值。 数组的顺序表示和实现 数组运算通常是随机访问与修改，一般不作插入或删除，故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变动，所以数组采用顺序存储结构表示。 存储单元是一维结构，而数组是多维结构，用一组地址连续的存储单元存放数组元素有次序约定的问题。 对于数组，一旦规定了它的维数和各维的长度（下标的界限），就可分配空间，并根据给定的一组下标求得相应数组元素的存储位置。 一维数组 LOC(ai)=LOC(a0)+i
18、*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*
19、bn+j2*b3*bn+jn-1*bn+jn)*L 若确定了数组的各维长度，则bl*bn为常数，数组元素的存储位置是其下标的线性函数，由于存取数组中任一元素的时间相等，故此结构为随机存储结构。 矩阵的压缩存储 若矩阵阶数很高，且矩阵中有许多值相同的元素或者零元素，为节省存储空间，对矩阵进行压缩存储，即为多个值相同的元只分配一个存储空间，对零元不分配空间 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，这类矩阵为特殊矩阵，否则为稀疏矩阵。特殊矩阵可将非零元压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。 特殊矩阵N阶对称矩阵元素关于主对角线对称aij=aji 0=i,j=j
20、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为稀疏矩阵。稀疏因子=t/(m*n)=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(root)的结点；（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2Tm，其中每一个集合本身又是一棵树，称为根的子树。 树的基本操作建树 求孩子结点求根结点
21、 求兄弟结点求双亲结点 结点的插入、删除 树的表示形式树形表示嵌套集合表示广义表表示凹入表表示 基本术语树的结点指一个数据元素及若干指向其子树的分支。通常以结构体来描述。结点的度结点拥有的子树数。度为0的结点称为叶子或终端结点；度不为0的结点称为非终端结点或分支结点。树的度树内各结点度的最大值。孩子和双亲结点的子树的根为该结点的孩子，该结点为孩子的双亲。结点的层次根为第一层，依次类推。兄弟和堂兄弟双亲相同的结点为兄弟，双亲在同一层次的结点为堂兄弟。祖先和子孙从根到该结点所经分支上的所有结点为该结点的祖先；以某结点为根的子树中的任一结点都称为该结点的子孙。树的深度(高度)树中结点的最大层次。有序
22、树和无序树如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。森林是m（m=0)个棵互不相交的树的集合。 二叉树 二叉树的定义 二叉树的每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 二叉树的基本操作 建树（空树、非空树） 求根结点、双亲、孩子、兄弟结点 二叉树的遍历 插入、删除 二叉树的五种基本形态空二叉树仅有根结点的二叉树左子树为空的二叉树右子树为空的二叉树左、右子树均非空的二叉树 二叉树的性质在二叉树的第i层上至多有2i-1个结点（i=1)深度为k的二叉树至多有2k-1个结点（k
23、=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，则结点
24、无右孩子；否则其右孩子是结点2i+1。 二叉树的存储结构 顺序存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即完全二叉树上编号为i的结点存储在一维数组中下标为i-1的分量中。对一般二叉树，顺序存储结构必须能反映结点之间的逻辑关系（父子关系），故将其每个结点与完全二叉树相 对照进行存储。 这种顺序存储结构仅适用于完全二叉树。最坏情况下，k个结点、深度为k的二叉树需要2k-1个结点的存储空间。 链式存储结构头指针指向根结点。 二叉链表存储结点的一个数据元素和分别指向其左、右子树的两个指针。 三叉链表增加一个指向双亲结点的指针域。 typedef struct
25、tnode int data; struct tnode *lchild, *rchild; TNODE; TNODE *root; 在n个结点的二叉链表中有n+1个空链域。 建立二叉树 遍历二叉树和线索二叉树遍历二叉树 遍历二叉树是指如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。(即将二叉树的结点排成一个线性队列) 一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。若限定先左（L）后右（R），则遍历方法有先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）三种。 先序遍历二叉树的递归算法访问根-先序遍历左
26、子树-先序遍历右子树void preorder(TNODE *bt) if (bt!=NULL) printf(“%d ”,bt-data); preorder(bt-lchild); preorder(bt-rchild); 中序遍历二叉树的递归算法（inorder)中序遍历左子树-访问根-中序遍历右子树 后序遍历二叉树的递归算法(postorder)后序遍历左子树-后序遍历右子树-访问根 表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。 将表达式表示为二叉树，若表达式=xy，则根结点存放运算符，左子树表示x，右子树表示y。 a+b*(c-d)-e/f 波兰式：表达式二叉树的前序
27、 中缀表示：中序 逆波兰式：后序 从递归执行过程的角度先序、中序和后序是完全相同的。 线索二叉树遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信息。由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。Typedef struct btnode char data; struct btnode *lchild, *rchild; int ltag, rtag; BTNODE; ltag=0 lchild指示结点的左儿子 ltag=1
