数据结构导论.docx

第一章 概论1 数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。2 数据的逻辑结构是指数据元素之间的逻辑关系。共分四种：集合结构：数据之间无关联线性结构：数据之间依次邻接树形结构：具有分支、层次特性图结构：任何两个节点都可以邻接3 数据的存储结构是指数据的逻辑结构在计算机上的实现。一般包括两部分：1) 数据元素 2)数据元素之间的关联方式。关联方式主要有两种：顺序存储方式和链式存储方式。4 一种逻辑结构可以表达为一种或几种存储结构，相应的存储结构称为给定逻辑结构的存储实现或存储映像。5 运算指在某种逻辑结构上进行的操作。6 算法规定了求解给定问题的处理步骤和执行顺序。评估算法好坏的几个方面：1) 正确性：实现预定功能，2) 易读性：易于阅读，便于修改和扩充3) 健壮性：能对非法数据做出反应或进行处理4) 时空性：时间性能和空间性能7 时间复杂度：也就是基本操作的执行次数，用于估计算法的计算量。常见的有常数阶O(1)，对数阶O(log2n)，线性阶O(n)，多项式阶O(nc)c=1,2，指数阶O(cn) c=1,2。通常认为，指数阶的算法是不可行的，低于平方阶的算法是高效率的。8 空间复杂度：算法所耗费的存储空间。一般只分析辅助变量所占的空间。第二章 线性表1 线性表基本概念1) 线性表是一种线性结构，它是由n(n0)个数据元素组成的有穷序列，数据元素又称结点，结点个数n称为表长。当n=0时，线性表不含任何数据元素，称为空表。当n>0时，线性表通常表示成(a1, a2, , an)，a1称为起始结点，an称为终端结点。对任意一对相邻结点ai和ai+1(1in)，ai称为ai+1的直接前驱，ai+1称为ai的直接后继。2) 线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其它每个结点有且仅有一个直接前驱；除终端结点没有直接后继外，其它每个结点有且仅有一个直接后继。2 线性表的顺序存储1) 线性表顺序存储的方法：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。结构定义如下：const int maxsize=100;typedef structDataType datamaxsize;int length; SqlList;SqlList L;2) 线性表的基本运算在顺序表上的实现(1) 插入void InsertSeqlist(SeqList L, DataType x, int i)if(L.length = maxsize) exit(“表已满”);if(i < 1 | i > L.Length+1) exit(“位置错”);for(j=L.length; j >= i; j-) L.dataj = L.dataj-1;L.datai-1 = x;L.length+;(2) 删除void DeleteSeqlist(SeqList L, int i)if(i < 1 | i > L.Length) exit(“位置错”);for(j=i; j < L.length; j+) L.dataj-1 = L.dataj;L.length-;(3) 定位int LocateSeqlist(SeqList L, DataType x)int i = 0;while(i<L.length && L.datai != x) i+;if(i < L.length) return i;return 0;(4) 在线性表的基本操作中，最频繁的操作是数据元素的比较和移动。因此在分析顺序表的实现算法时，一个重要指示就是数据元素的比较和移动次数。3 线性表的链式存储1) 线性表常见的链式存储结构有单链表、循环链表和双向链表，其中最简单的是单链表。单链表是线性表的数据元素用指针链接起来的存储结构，指针表示数据元素之间的逻辑关系。定义如下typedef struct nodeDataType data;struct node * next; Node, *LinkList;2) 线性表的基本运算在单链表上的实现(1) 定位int Locate(LinkList head, DataType x)int i=0;Node *p=head;p=p->next;while(p!=NULL && p->data != x)i+;p=p->next;if(p != NULL) return i+1;return 0;(2) 插入void Insert(LinkList head, DataType x, int i)Node *p,*q;if(i=1) q=head;else q=GetLinkList(head,i-1);if(q=NULL) exit(“找不到插入位置”);p=malloc(sizeof(Node);p->next = q->next;q->next = p;(3) 删除void Delete(LinkList head, int i)Node *p,*q;if(i=1) q=head;else q=GetLinklist(head, i-1);if(q=NULL) exit(“找不到删除位置”);p=q->next;p->next = q->next;free(p);3) 其它链表(1) 如果让最后一个结点的指针指向第一个结点可以构成循环链表。在循环链表中，从任意结点出发都能扫描整个链表。(2) 在单链表的每个结点中再添加一个指向其直接前驱结点的指针prior，头结点prior指针指向最后一个结点，最后一个结点的next指针指向头结点，这样的链表被称为双向循环链表。第三章 栈、队列、数组1 栈1) 栈的基本概念(1) 栈是运算受限的线性表，这种线性表上的插入和删除运算限定在某一端进行。允许进行插入和删除的一端称为栈顶，别一端称为栈底。不含任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为栈顶元素。(2) 栈的修改原则是后进先出(Last In First Out)，因此，栈又称为后进先出线性表，简称后进先出表。栈的插入和删除运算称为进栈和出栈。2) 栈的顺序实现(1) 栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个元素，并用始端作为栈底。栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶位置的变量来实现栈的顺序存储。为了防止“下溢”，栈底没有元素，栈顶的取值范围为0 - (maxsize-1)。定义如下：const int maxsize=6;typedef struct seqstackDataType datamaxsize;int top; SeqStk;(2) 进栈int Push(SeqStk * stk, DataType x)if(stk->top = maxsize-1)error(“栈已满”);return 0;stk->top+;stk->datastk->top = x;return 1;(3) 出栈int Pop(SeqStk * stk)if(EmptyStack(stk)error(“空栈”);return 0;stk->top-;return 1;(4) 取栈顶元素DataType GetTop(SeqStk *stk)if(EmptyStack(stk) return NULL;return stk->datastk->top;3) 栈的链式实现(1) 栈的链式实现称为链栈，可以用带头的单链表实现，首结点作栈顶，尾结点作栈底。定义如下typedef struct nodeDataType data;struct node *next; LkStk;(2) 进栈void Push(LkStk *LS, DataType x)LkStk* temp = (LkStk*)malloc(sizeof(LkStk);temp->data = x;temp->next = LS->next;LS->next = temp;(3) 出栈int Pop(LkStk *LS)LkStk * temp;if(!EmptyStack(LS)temp = LS->next;LS->next = temp->next;free(temp);return 1;return 0;2 队列1) 队列是一种先进先出(First In First Out)的线性表，新加入的数据元素插入队列的尾端。2) 队列的顺序实现(1) 顺序存储实现的队列称为顺序队列，由一个一维数组及两个指示队首和队尾的变量组成。(2) 为了避免元素的移动，可将存储元素的数组首尾相接，形成一个环状，这样的队列称为循环队列(3) 为了解决循环队列无法区分是空队列还是满队列的情况，采用少用一个元素空间的办法解决3) 队列的链式实现(1) 使用一个单链表外加两个指向头尾结点的指针实现，称为链队列。3 数组1) 数组可以看作线性表的一种推广，一维数组又称向量，数组通常只有读和写两种操作2) 二维数组有两种存储方式，一种是行序存储(橫着存)，一种是列序存储(竖着存)3) 为了节省存储空间，对矩阵中多个值相同的元素只分配一个存储空间，零元素不存储的方法被称为矩阵的压缩存储4) 如果值相同的元素或零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。常见的特殊矩阵有对称矩阵和三角矩阵5) 矩阵中非零元素个数很少的矩阵称为稀疏矩阵。对稀疏矩阵的压缩存储可以采用三元组表示法，即用行号，列号，元素值表示矩阵中的非零元素第四章 树1 树的基本概念1) 节点的度：节点所拥有的子树的数目2) 叶子：度为0的节点，也叫终端节点3) 树的度：树中所有节点的度的最大值4) 节点的层次：根的层次为1，其余的为其父节点加15) 树的高深度：树中所有节点层次的最大值6) 有序树：节点的子树是有次序的，不能互换7) 无序树：节点的子树没有次序，可以互换2 二叉树的基本概念1) 有左右两个节点，且节点次序不能互换，即互换后为两个不同的二叉树2) 二叉树第i层上最多有2i-1个节点3) 深度为k的二叉树最多有2k-1个节点4) 对任意二叉树而言，若n0表示叶子，n2表示有左右两个子树的节点，则n0=n2+15) 满二叉树：深度为k且有2k-1个节点6) 完全二叉树：满二叉树删除编号最大的节点后的二叉树7) 含有n个节点的完全二叉树的深度为1 + log2n8) 对第i个节点的完全二叉树而言，左节点为2*i，右节点为2*i+1；对含有n个节点的完全二叉树而言，最后一个非终端节点编号为n/23 二叉树的存储结构1) 顺序存储：由于完全二叉树的节点编号能准确反映节点的逻辑关系，所以可直接用数组表示二叉树；对于非完全节点，则需增加虚拟节点构成完全二叉树，然后再将节点的值存入数组，虚拟节点的值用null表示2) 链式存储：(1) 二叉链表：lchild, data, rchild (2) 三叉链表：lchild, data, parent, rchild4 二叉树的遍历1) 先序遍历void Preorder(BinTree bt)if(bt != null)visit(bt);preorder(bt->lchild);preorder(bt->rchild);2) 中序遍历void inorder(BinTree bt)if(bt != null)inorder (bt->lchild);visit(bt);inorder (bt->rchild);3) 后序遍历void postorder(BinTree bt)if(bt != null)postorder (bt->lchild);postorder (bt->rchild);visit(bt);4) 以下面的二叉树为例，遍历如果如下：先序遍历结果：ABDEGCF中序遍历结果：DBGEACF后序遍历结果：DGEBFCA5) 二叉树的层次遍历void levelorder(BinTree bt)Queue q;BinTree nd;if(bt != null)EnQueue(bt);while(!EmptyQueue(Q)nd = OutQueue(Q);visit(nd);if(nd->lchild != null) EnQueue(q, nd->lchild);if(nd->rchild != null) EnQueue(q, nd->rchild);6) 二叉树遍历的非递归实现，以先序遍历为例void preorder(BinTree bt)Stack s;BinTree nd;if(bt = null) return;nd = bt;while(node != null | !EmptyStack(s)if(nd != null)Visit(nd);Push(nd,s);nd = nd->lchild;elsend=Pop(s);nd=nd->rchild;5 树、森林与二叉树1) 树的存储结构，以下图为例(1) 孩子链表示法带双亲节点的孩子链 (2) 孩子兄弟链表示法(3) 双亲表示法2) 树、森林与二叉树的相互转换1) 树转换为二叉树：将兄弟节点连接起来，只保留第一个兄弟与父节点的连接2) 森林转换为二叉树：将每棵树转换为相应的二叉树，将所有二叉树作为兄弟连接3) 二叉树转换为树或森林：上述2种转换的逆转换6 哈夫曼树与哈夫曼算法1) 哈夫曼树是平均比较次数最少的判定树2) 哈夫曼算法基本思想：每次选取两个最小的权值进行迭代。哈夫曼算法构造的哈夫曼树不是唯一的。3) 给定权值7，18，3，32，5，26，12，8，构造哈夫曼树并计算其带权路径长度带权路径长度=298第五章 图1 基本概念1) 上图中，圆圈称为顶点，连线称为边，连线附带的值称为边的权2) 上图中，a图称为有向图，记作G=(V,E)，b图称为无向图，记作G=<V,E>3) 有向图的边称为弧，箭头起点称为始点或弧尾，终点称为终点或弧头4) 任何两点之间都有边的无向图称为无向完全图，一个具有n个顶点的无向完全图共有n(n-1)/2条连；任何两点间都有弧的有向图称为有向完全图，一个具有n个顶点的有向完全图共有n(n-1)条边5) 无向图中顶点v的度是与该顶点相关联的边的数目；有向图中以顶点v为终点的弧的数目称为v的入度，以顶点v为始点的弧的数目称为v的出度7) 图中两点之间所经过的边(或弧)的数目称为路径长度8) 顶点不重复出现的路径称为简单路径，如a图中的A->B->E->H->I；第一个顶点和最后一个顶点相同的路径称为回路或环，除第一个顶点和最后一个顶点外，其余顶点不重复的回路称为简单回路，如b图中的A->B->C->F->A9) 如果图中任意两个顶点都是连通的，则称图为连通图2 存储结构1) 邻接矩阵0 1 0 1 11 0 1 0 00 1 0 1 11 0 1 0 01 0 1 0 0 50 40 2050 10 10 20 3040 20 20 30 0 1 1 00 0 1 10 0 0 00 0 1 0 30 10 50 10 60 (1) 无权图中Aij代表边(i, j)或弧<i,j>是否存在，有权图中Aij代表边(i, j)或弧<i,j>的权值(2) 无向图的邻接矩阵是个对称矩阵(3) 无向图中，顶点Vi的度是第i行或列的和；有向图中，出度为第i行之和，入度为第i列之和2) 邻接表(1) 无向图a1和a2的邻接表(2) 有向图b1和b2的邻接表(3) 有向图b1和b2的逆邻接表(4) 无向图中，顶点Vi的度为第i个单链表的节点数(5) 有向图中，第i个单链表的节点数只是顶点Vi的出度(6) 有时需要建立逆邻接表，也即以Vi为弧头的邻接表，这时第i个单链表的节点数只是顶点Vi的入度3 图的遍历 - 深度优先算法1) 以图中某个顶点Vi为出发点，首先访问Vi，然后选Vi的任意一个未被访问过的邻接点Vj，以Vj为新出发点继续进行深度优先搜索，依此类推，直到图中所有的顶点都被访问过。2) 深度优先算法类似于先序遍历。4 图的遍历 - 广度优先算法1) 以图中某个顶点Vi为出发点，在访问了Vi之后依次访问Vj的所有邻接点，然后依次从这些邻接点出发按广度优先算法遍历其它顶点，重复这一过程，只到所有顶点都被访问到。2) 广度优先算法类似于树的层次遍历5 最小生成树无向图，最低成本连通网络 - Prim算法1) U=0, V-U=1,2,3,4, 在0和1,2,3,4关联的所有边中，取权值最小的边(0,4)，将顶点4加入集合U2) U=0,4, V-U=1,2,3 , 在0,4和1,2,3关联的所有边中，取权值最小的边(2,4)，将顶点2加入集合U3) U=0,2,4, V-U=1,3 , 在0,2,4和1,3关联的所有边中，取权值最小的边(1,2)，将顶点1加入集合U4) U=0,1,2,4, V-U=3 , 在0,1,2,4和3关联的所有边中，取权值最小的边(2,3)，将顶点3加入集合U5) U=0,1,2,3,4, V-U=, 至此求出最小生成树，E=(0,4), (2,4), (1,2), (2,3)6) 对于有n个顶点的无向图，最小生成树中有且仅有n-1条边6 最小生成树无向图，最低成本连通网络 - Kruskal算法1) 设G=(V,E)，令最小生成树T=(V,)，即没有边的n个顶点，每个顶点自成一个连通分量2) 在E中选权值最小的边，若该边的顶点落在T中不同的连通分量上，则将些边加入T，否则舍去些边，选取下一条代价最小的边3) 依次类推，重复第二步，直到T中所有的顶点都在一个连通分量上7 最短路径有向图，寻找两点之间的最短路径 - Dijkstra算法步骤SuBCDEFGH第1步A-12108第2步A,DD1210817(ADF)第3步A,C,DC1210815(ACE)12(ACF)第4步A,B,C,DB1210815(ACE)12(ACF)第5步A,B,C,D,FF1210815(ACE)12(ACF)16(ACFG)第6步A,B,C,D,E,FE1210815(ACE)12(ACF)16(ACFG)18(ACEH)第7步A,B,C,D,E,F,GG1210815(ACE)12(ACF)16(ACFG)18(ACEH)第8步A,B,C,D,E,F,G,HH1210815(ACE)12(ACF)16(ACFG)18(ACEH)8 拓扑排序有向图，确定节点先后次序1) 选择一个入度为0的顶点，输出该顶点2) 删除该顶点及相关的弧，并将弧头所指结点的入度减13) 重复1，2直到所有入度为0的顶点均被输出第六章 查找1 静态查找 - 顺序表1) 关键字，简称键，用来标识数据元素2) 对于给定的键，顺序表只能按顺序一一查找3) 顺序查找实现如下：int Search(Table t, Key k)T0.key = key;int i=t.n;while(Ti.key != key) i-;return i;2 静态查找 - 有序表1) 键值按大小排列的顺序表称为有序表，这种情况下可用效率更高的二分查找法实现查找操作2) 二分查找法是每次和表中间位置的数据元素进行比较，然后逐步缩小查找区间3) 二分查找法实现如下：int Search(Table t, Key k)int mid;int low=1, high=t.n;while(low<=high)mid = (low+high)/2;if(key=tmid.key) return mid;if(key < tmid.key) high = mid -1;else low=mid+1;return -1;3 静态查找 - 索引顺序表1) 索引顺序表是结合了顺序查找和二分查找的优点而构造的一种存储结构2) 索引顺序表由索引表和顺序表两部分组成，每个索引项由块内关键字和块起始位置组成3) 索引顺序表上的查找分两步：(1) 确定元素所在的块 (2) 在块内顺序查找4 动态查找 - 二叉排序树1) 二叉排序权的左节点小于它的根结点，右节点大于它的根结点2) 对二叉排序树进行中序遍历，可得到一个升序的键值序列5 动态查找 - 散列表1) 通过散列函数在数据元素的键值和存储位置之间建立对应关系2) 除留余数法是一种简单有效且最常用的散列构造方法，具体做法是选择一个不大于表长n的正整数p，以键值除以p所得的余数作为散列地址，通常选p为小于n的素数。3) 平方除中法也是比较常用的散列构造方法，具体做法是以键值平方的中间几位作为散列地址。4) 用链地址法实现的散列表第七章 排序1 直接接入排序 - 插入排序1) 将记录插入一个已排好序的有序表中，得到一个新的、记录数多1的有序表。2) 稳定排序，时间复杂度O(n2)，空间复杂度O(1)3) 算法描述如下：void StraightInsertSort(List R, int n)int i,j;for(i = 2; i <=n; i+)R0 = Ri;/将第i个记录复制到岗哨j = i - 1;/将j设为有序表的最后位置while(R0.key < Rj.key) /移动有序表的元素Rj+1 = Rj;j-;Rj+1 = R0; /将第i个记录插入序列2 冒泡排序 - 交换排序1) 稳定排序，时间复杂度O(n2)2) 算法描述如下：void BubbleSort(List R, int n)int i,j;for(int i=1; i <=n; i+)for(j = i+1; j<=n;j+)if(Ri.key >Rj.key) Swap(Ri,Rj);3 快速排序 - 交换排序1) 选择第一个记录作为基准值，通过一趟排序将待排的记录分为两部分(小于等于基准值，大于基准值)，然后对这两部分继续进行快速排序。2) 不稳定排序，时间复杂度O(nlog2n)，最坏情况下(已排好序的序列)，时间复杂度O(n2)3) 算法描述如下：int QuickPartition(List R, int low, int high)x = Rlow;while(low<high)/当后面的元素大于x时while(low < high) && (Rhigh.key >= x.key) high-;Rlow = Rhigh;/当前面的元素小于x时while(low < high) && (Rlow.key <=x.key) low+;Rhigh =Rlow;Rlow = x;return low;void QuickSort(List R, int low, int high)if(low < high)temp = QuickPartition(R, low, high);QuickSort(R, low, temp -1);QuickSort(R, temp+1, high);4 直接选择排序 - 选择排序1) 每次从n个记录中选取最小的一个进行排序2) 不稳定排序，时间复杂度O(n2)3) 算法描述如下：void SeleceSort(List R, int n)int min,i,j;for(i=1; i <= n-1; i+)min = i;for(j = i + 1; j <=n; j+) if(Rj.key < Rmin.key) min = j;if(min != i) Swap(Rmin,Ri);5 堆排序 - 选择排序1) 最小堆是一棵完全二叉树，其中每个结点的值不大于它的两个孩子的值(如果有的话)。2) 最小堆是一棵完全二叉树，其中每个结点的值不小于它的两个孩子的值(如果有的话)。3) 不稳定排序，时间复杂度O(nlog2n)4) 实现堆排序的关键需要解决两个问题：(1) 将初始序列建成一个堆，将极值(最小值或最小值) 调整到堆顶(2) 输出堆顶元素之后，调整剩余元素成为一个新堆5) 堆排序的过程是一个调整过程称为“筛选”，算法实现如下，以最小堆为例：void Sift(List R, int k, int m)int i,j,x;i = k; j = 2*i; x=Rk.key;while(j<=m)if(j<m && Rj.key > Rj+1.key) j+; /存在右子树且右子树关键字小，Rj是子树中的较小值if(Ri.key < Rj.key)/Ri就是当前合适的位置break;else/ Ri需求沿左分支筛选Swap(Ri,Rj);i = j;j = 2*i;void HeapSort(List R, int n)int i;for(i=n/2; i >=1; i-) Shit(R, i, n); /建堆for(i=n; i>=2; i-) Swap(R1,Ri);/ 交换堆顶元素最小值和最后一个元素Sift(R,1,i-1); /调整堆6 二路归并排序 - 归并排序1) 将n个记录看成是n个有序的子序列，然后进行两两合并。2) 稳定排序，时间复杂度O(nlog2n)3) 算法实现如下：初始关键字<25 9> <78 6> <65 15> <58 18> <45 20>一次归并后<9 25 6 78> <15 65 18 58> 20 45二次归并后<6 9 25 78 13 18 58 65> 20 45三次归并后<6 9 15 18 25 58 65 78 20 45>四次归并后6 9 15 18 20 25 45 58 65 78