(补充)数据结构与算法.doc

数据结构：数据结构是由一个逻辑结构 S 和 S 上的一个基本运算集构成的整体( S ，)。数据结构的基本任务：数据结构的设计和实现。数据的形式有很多种： 数据的逻辑结构分为 4 种基本类型： 集合：集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。 线性结构：线性结构中的结点按逻辑关系依次排列形成一个“锁链”。 树形结构：树形结构具有分支、层次特性，其形态有点象自然界中的树。 图状结构：图状结构中的结点按逻辑关系互相缠绕，任何两个结点都可以邻接。运算：是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。根据操作的效果，可将运算分成以下两种基本类型： 加工型运算 其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；如：初始化、插入、删除、更新等操作。 引用型运算 其操作不改变原逻辑结构的“值”，只从中提取某些信息作为运算的结果。如：查找、读取等操作。算法：算法就是解决问题的方法和步骤，可以用语言来描述。根据描述算法语言的不同，将算法分为三类：运行终止的程序可执行部分、伪语言算法和非形式算法。非形式算法：用自然语言(如汉语)，同时可能还使用了程序设计语言或伪程序设计语言描述的算法称为非形式算法。算法与程序的关系：算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。算法分析通常从以下几个方面评价算法(包括程序)的质量： 正确性 算法应能正确地实现预定的功能(即处理要求)。 易读性 算法应易于阅读和理解，以便于调试、修改和扩充。 健壮性 当环境发生变化(如遇到非法输入)时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。 高效性 即达到所需要的时空性能。一个算法的时空性能是指该算法的时间性能(或时间效率)和空间性能(或空间效率)。 最坏情况时间复杂性和平均时间复杂性统称为时间复杂性(或时间复杂度)，用 T ( n ) O ( f ( n )表示。其中 f ( n )是算法中频度最大的那条语句频度的数量级。例：求下列算法的时间复杂度。(1)for (i=0; in; i+) x+;【解答】：时间复杂度为O(n)。(2)for (i=0; in; i+) for (j=0; j=i; j+) x+;【解答】：时间复杂度为O(n2)。(3)i=1; while (in) i*=2;【解答】：时间复杂度为O(log2n)。/*设k次，则2k=n，所以k=log2n*/例：下列程序段的时间复杂性的量级为 。for ( i=1 ；i=n；i+) for ( j=i ；j=0，称为线性表的长度，简称表长。当n=0时线性表为空表，记作：L=（）。元素ai-1称为ai的直接前趋，ai+1称为ai的直接后继。顺序表：顺序表是线性表的顺序存储结构，是指在一个足够大的连续的存储空间里，将线性表中的元素按照逻辑上的次序依次进行存储。这样得到的线性表称为顺序表。顺序表的结构如下图所示：（P17） 其中数组datamaxlen用来存储线性表中的各个元素，此外，设置一个变量listlen表示顺序表中的元素个数（表长）。顺序表的类型定义如下：（P17）#define maxsize 100 /假设元素个数不超过100typedef struct datatype datamaxsize; /顺序表中元素的类型用datatype泛指 int last; /表长sqlist;由上述定义不难发现，顺序表具有这样的特点：逻辑上相邻的元素，其存储地址也相邻。顺序表中基本运算的实现1初始化顺序表建立一个空的顺序表L，只需将表长置为0即可。void initiate(sqlist *L) L-last=0; 2求表长即返回顺序表L的last值。int length(sqlist L) return (L.last); 3按给定序号取元素序号为i的元素ai在数组中的下标为i-1，若该元素存在，则返回相应的数组元素值。void get (sqlist L，int i, datatype *x) if（iL.listlen）error(该元素不存在); else *x= L.datai-1;4查找（定位） locate(L,x)：依次将顺序表L中的每个元素与给定的值x进行比较。若找到则返回其序号（下标+1），否则返回0。int locate (sqlist L, datatype x) int i; for ( i=0; iL.listlen; i+) if (L.datai=x) return (i+1); return(0);5插入 insert(L,i,x)：算法思想如下：（1）首先要判断能否进行插入，即表是否为满以及插入位置i是否合理。（2）如果可以进行插入，需要执行下列步骤： 为了给待插入元素x腾出一个空位，需要将aian往后移一位。 将x插入到第i个位置上。 插入后，顺序表L的长度last要加1。void insert (sqlist *L, datatype x, int i ) int j; if (iL-last+1) error (插入位置错误); else if (L- last =maxsize) error (溢出); else for (j=L- last -1; j=i-1; j-) /往后移动元素 L-dataj+1=L-dataj; L-datai-1=x; /插入x L- last +; /修改表长 算法分析：（P20）当插入位置i=1，2n+1时，移动元素的次数分别为n，n-1,1，0。因此平均移动次数为：(0+1+n) / ( n+1) = n / 2，所以插入算法的时间复杂度为O(n)。6删除 delete (L,i)：void delete (sqlist *L, int i) int j； if (L- last L- last | i=0) error(无法删除);else for (j=i；j last -1；j+) L-dataj-1=L-dataj； L- last -； 算法的时间复杂度为O(n)。单链表在顺序表中插入和删除元素时，需要做大量移动元素的操作，比较浪费时间。要想在插入和删除时不需移动元素，可以采用链式存储结构，此时线性表中每个元素称为一个结点，如下图所示： 每个结点包括两个部分：数据域data，用于存储元素的值。指针域next，用于存储后继结点的地址。采用链式存储结构的线性表称为链表。本节介绍的链表，每个结点只有一个指针域，称为单链表。单链表的简单操作（1）静态链表：用数组来存储元素的值和地址。（2）动态链表：根据实际需要，临时动态地分配存储空间来存储线性表中的元素。单链表的类型定义如下：typedef struct datatype data; /存放元素值 struct node *next; /指示后继结点的指针node;一个完整的单链表head如下图所示：其中，head称为头指针，第一个元素a1所在的结点称为首结点（第一个元素结点）。有时，为了使某些运算更方便实现，在首结点之前增加了一个结点，称为头结点，并称此时的链表为带头结点的单链表。单链表中基本运算的实现1建空表一个空的单链表只有一个头结点，且后继指针为空，如下图所示： void initiate (node *L) L= (node *) malloc (sizeof (node); /产生一个头结点 L-next=NULL; /设置后继指针为空2求单链表的长度即求出单链表中元素的个数，用p指针依次指向每个元素结点并进行计数，算法如下：int length (node *L) int n=0; node *p=L-next; while (p!=NULL) n+; p=p-next; return n ;3按给定序号取元素node *get (node *L, int i ) node *p=L-next; int j=0; while ( j!=i & p!=NULL ) p=p-next; j+; return p;4查找（定位）将单链表中各结点的data值逐个地与x进行比较，若找到则返回该结点的指针，否则继续往后搜索，若直到表尾都没有找到，则返回空指针。算法如下：node *locate (node *L, datatype x ) node *p=L-next; while (p!=NULL & p-data!=x ) p=p-next; return p;5插入如下图所示，插入操作主要由两条语句来实现：s-next=p-next； p-next=s； 完整的算法如下：void insert (node *L, int i, datatype x ) node *p=L; int k=0; while (k!=i-1 & p!=NULL) p=p-next; k+; if (p=NULL) error (插入序号错); else s= (node * ) malloc (sizeof (node); s-data=x; s-next=p-next; p-next=s; 6删除如下图所示，删除ai结点需执行的语句为：p-next=p-next-next； 完整的算法如下：void delete (node *L, int i) node *u , *p; p=get(L，i-1); if (p=NULL | p-next=NULL) error (插入序号错); else u=p-next; /指向要删除的结点 p-next=u-next; /绕过要删除的结点 free (u); /释放结点的存储空间单循环链表如果单链表中尾结点的后继指针指向头结点，则构成了一个单循环链表，如下图所示： 显然，在单循环链表中，从任一结点出发都可以搜索到其它各个结点。单循环链表中基本运算的实现与单链表类似：例如，若循环条件为p!=NULL，则改为p!=L即可。双（循环）链表若想不需经过搜索就可以直接求出任一结点的前趋，可以采用双链表。双链表中每个结点除了后继指针外，还增加了一个指向其前趋的指针。双链表也可以是循环的。带头结点的双循环链表如下图所示： 双循环链表的类型定义如下：typedef struct datatype data; struct dunode *prior, *next;dunode;显然，在双循环链表中：p-prior-next = p-next-prior = p关于双循环链表上基本运算的实现主要讨论以下两个：1. 插入： s-prior = p-prior;s-next = p;p-prior-next = s;p-prior = s;2删除：（P33） p-next-prior = p-prior;（下）p-prior-next = p-next; （上）free(p); （双链表）栈的基本概念和运算栈：是只能在一端进行插入和删除的线性表。它是一种运算受到限制的特殊的线性表。如下图所示的栈，插入和删除元素的一端称为栈顶，另一端称为栈底。插入元素和删除元素的操作分别称为入栈和出栈。 由于入栈和出栈都只能在栈顶进行，所以栈具有先进后出 (或后进先出)的特性。栈的基本运算有以下几种：(1)初始化InitStack (S)：建立一个空栈。(2)判断栈是否为空EmptyStack(S)(3)取栈顶GetTop(S) ：返回栈顶元素的值。(4)入栈Push(S,x) ：将值为x的元素压入到栈S中。(5)出栈Pop(S,x) ：删除栈顶元素，并将它的值放到变量x中。顺序栈（栈的顺序实现）以顺序存储方式存储的栈称为顺序栈，其类型说明如下：#define maxsize 8typedef struct datatype datamaxsize; int top; /top值等于栈顶元素的下标 SqStackTp;顺序栈S的结构如下图所示： 顺序栈上运算的实现:1初始化：因为top的值等于顺序栈中元素的个数减1，所以建立一个空栈只需将top置为-1即可。void InitStack(SqStackTp *S) （注意与教材的区别P44） s-top=-1; 2判断栈是否为空：BOOL EmptyStack (SqStackTp S) if (S.top=-1) return(TRUE); else return(FALSE);3取栈顶：datatype GetTop(SqStackTp *S) if (EmptyStack(*S) )error(栈为空); else return(s-datas-top);4入栈： void Push(SqStackTp *S, datatype x) if (S-top=maxsize-1 )error(溢出); /判断栈是否为满 else S-data+s-top= x;5出栈： void Pop(SqStackTp *S, datatype *x) if (EmptyStack(*S) )error( 栈空，不能删除); else *x=S-dataS-top-;链栈（栈的链接实现）用链式存储结构存储的栈称为链栈。一般采用不带头结点的单链表，并且用表头作为栈顶，其结构如下图所示： 在链栈上上实现关于栈的基本运算运算，与单链表的运算相似，只需注意：入栈和出栈操作相当于在链表的表头进行插入和删除，故此处不再详细讨论。typedef struct node DataType data; /存放元素值 struct node *next; /指示后继结点的指针LStackTp;(1)初始化void InitStack(LStackTp *ls) ls=NULL;(2)进栈void Push(LStackTp *ls,DataType x) LStackTp *p;p=( LStackTp *)malloc(sizeof(LStackTp );p-data=x;p-next=ls;ls=p;(3)出栈int Push(LStackTp *ls,DataType *x) LStackTp *p;if(ls!=NULL) p=ls;*x=p-data;free(p);return 1;return 0;(4)判栈空int EmptyStack(LStackTp *ls) if(ls=NULL)return 1;else return 0;(5)读栈顶元素int GetTop(LStackTp *ls,DataType *x) if(ls!=NULL) *x=ls-data;return 1;return 0;队列的基本概念队列：是只能在一端进行插入、在另一端进行删除的线性表，它也是运算受到限制的线性表。通常把插入元素的一端叫做队尾，而把删除元素的一端叫做队头。把队列的插入和删除运算分别叫做入队和出队。队列的结构如下图所示： 由于队列只能在队头进行出队、在队尾进行入队，所以队列具有先进先出的特性。队列的基本运算：(1)初始化InitQueue(Q)：设置一个空队列Q。(2)判断队列是否为空EmptyQueue(Q)(3)取队头GetHead(Q)：返回队头元素的值。(4)入队EnQueue(Q,x)：将值为x的元素插入队列。(5)出队OutQueue(Q) ：删除队头元素，并返回它的值。顺序队列以顺序存储方式存储的队列称为顺序队列。可以用一个数组datamaxsize来存储队列中的元素，并设置一个变量rear（称为尾指针）指向队尾元素，还有一个变量front（称为头指针）指向队头元素的前一个位置。顺序队列的结构如下图所示： 顺序队列的类型定义如下： #define maxsize 20typedef struct DataType datamaxsize; int front,rear;SqQueueTp;为了解决假溢出的问题，一般采用如下图 所示的循环队列来存储队列。 在进行入（出）队运算时，必须判断队列是否为满（空）。为了解决这个问题，采用的方法是保留一个存储单元不用，即仅剩一个空位置时认为队列为满。循环队列上基本运算的实现：1初始化void InitCycQueue(CycQueueTp *Q) Q-front=0; Q-rear=0; 2判断队列是否为空BOOL EmptyCycQueue (CycQueueTp Q) if (Q.front=Q.rear) return TRUE;else return FALSE;3取队头元素如果队列不空，则返回队头元素的值。DataType GetCycQueueHead (CycQueueTp Q) if (EmptyCycQueue (Q)error( 队空); else return (Q.data(Q.front+1)% maxsize); /队头元素在头指针front指向的下一个位置4入队void EnCycQueue(CycQueueTp * Q,datatype x) if (1+Q-rear)% maxsize=Q-front) error( 溢出); /判断队列是否为满else Q-rear=(1+Q-rear) % maxsize; /尾指针向后移一位 Q-dataQ-rear= x;5.出队datatype OutCycQueue(CycQueueTp * Q) if (EmptyCycQueue (*Q) )error( 队空，不能出队); else Q-front=(Q-front+1) % maxsize; return Q-dataQ-front; 链队列链队列是指用链表存储的队列。一般采用带头结点的单链表，其结构如下图所示： 链队列的类型定义如下： typedef struct node *front,*rear;LkQueue;链队列上基本运算的实现如下：1. 初始化空的链队列仅有一个头结点，并且头尾指针均指向头结点。void InitQueue(LkQueue *Q) Q-front=(node *)malloc(sizeof(node); /产生一个头结点 Q-rear=Q-front; /尾指针也指向头结点 Q-front-next=NULL; /尾结点后继指针设置为空2.判断队列是否为空BOOL EmptyQueue(LkQueue Q) return (Q.front=Q.rear); 3取队头元素void GetHead(LkQueue * Q, datatype * x); if (EmptyQueue (*Q) )error( 队空，不能取元素); else *x=Q-front-next-data; /取队头元素（首结点）的值4入队void EnQueue(LkQueue * Q, datatype x) node *P=(node *)malloc(sizeof(node); P-data=x; P-next=NULL; /新队尾的后继指针为空 Q-rear-next=P; /插入到队尾 Q-rear=P; /尾指针指向新的队尾5出队void OutQueue(LkQueue *Q, datatype *x) if (EmptyQueue (*Q) )error( 队空，不能出队); else x=Q-front-next-data; /取队头元素的值 node *u=Q-front-next; /保存待删结点的指针 Q-front-next=u-next; /删除 free(u);if (Q-front-next=NULL) /出队最后一个结点时 Q-rear=Q-front;树：是n个结点构成的有限集合(n0)，其中有一个结点称为根，其余结点可划分为m个互不相交的子集T1,T2Tm (m0)，这m个子集本身又构成树，称为根的子树。下图所示为一棵树，其中A为根，A有三棵子树T1、T2和T3；其中在T1中，B是该子树的根，B又有三棵子树。 下面介绍关于树的一些常见术语：结点：树中的结点包含相应元素的值及其子树的信息。度：一个结点的子树的数目称为该结点的度。树中各结点的最大度称为树的度。如上图中树的度为3。叶子结点：度为0的结点称为叶子结点（或终端结点）。否则称为非终端结点（或分支结点）。孩子结点：某结点的子树的根称为该结点的孩子结点，相应地该结点为其孩子结点的父亲（或双亲）结点。如A的孩子为B，C，D；而H、I的双亲均为C。兄弟结点：同一结点的孩子之间互称为兄弟。如E，F，G为兄弟。祖先：一个结点的祖先是指从根结点到该结点所经分支上的所有结点。后代：以某个结点为根的子树中的任一结点(不包括自身)为该结点的后代。结点的层次：根的层次为1，其余结点的层次为其父结点的层次数加1。树的高度：树中结点的最大层次数称为树的高度（或深度）。有序/无序树：如果树中结点的各子树是看成按从左到右的次序排列的，则称该树为有序树，否则称为无序树。在有序树中，最左边的子树的根为第一个孩子。森林：是m(m0)棵互不相交的树的集合。（树）树的基本运算(1)初始化Initiate(T)：建立一棵空树。(2)求树根Root(T)(3)求父亲Parent(T,x)：求树T中结点x的父亲结点。(4)求孩子Child(T,x,i)：求树T中结点x的第i个孩子结点。(5)求下一个兄弟：NextBrother(T,x)：求树T中结点x的下一个兄弟结点。(6)建树Create(T)(7)插入子树Insert(T,i,x)：将以x为根的子树插入到T中，作为T的第i棵子树。(8)删除子树Delete(T,i)：删除T的第i棵子树。(9)遍历树Travel(T)：按某种顺序依次访问树T中的结点，要求每个结点都要访问一次并且仅访问一次。二叉树：二叉树T是n个结点的有限集合(n0)，当n=0时，为空二叉树，否则其中有一个结点为根，其余结点划分为两个互不相交的子集TL和TR，并且TL和TR也是二叉树，称为根的左子树和右子树。下图为一棵二叉树： 其中，A、C的两棵子树均不空；B的右子树为空；E的左子树为空；D、F、G的两棵子树均为空。二叉树的运算的定义与树类似，略。二叉树有五个重要的基本性质： 性质1：在二叉树的第i层上至多有2i-1个结点。性质2：深度为K的二叉树至多有2k-1个结点。性质3：对任意一棵非空的二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。满二叉树：深度为K并且有2k-1个结点的二叉树称为满二叉树。对满二叉树中的各个结点按从上往下、从左往右的顺序进行编号（根结点编号为1），然后按编号从大到小的顺序依次删除若干个结点，所得到的二叉树称为完全二叉树。下图为完全二叉树： 性质4：有n个结点的完全二叉树(n0)，其深度为log2n+1。性质5：完全二叉树中，编号为i的结点(1in)：(1)如果不为根（i1）,其父亲结点的编号为i/2。(2)如果有左孩子，其左孩子的编号为2i。(3)如果有右孩子，其右孩子的编号为2i+1。二叉树的存储结构二叉链表中结点的结构如下： 类型定义为： typedef struct btnode *bitreptr;struct btnode datatype data; bitreptr lchild,rchild;bitreptr root;顺序存储结构将结点在完全二叉树中的编号作为该结点在数组中的位置来存储。上图中完全二叉树的顺序存储结构如下图所示： 采用这种方式存储，可以由性质5知道各结点间的关系。可以比较方便 实现二叉树的各种基本运算显然，用顺序存储方式存储非完全二叉树时，会导致存储空间的浪费。例如： 二叉树的遍历1先序遍历若二叉树T不空，则：访问T的根结点 先序遍历T的左子树 先序遍历T的右子树2中序遍历若二叉树T不空，则：中序遍历T的左子树 访问T的根结点 中序遍历T的右子树3后序遍历若二叉树T不空，则：后序遍历T的左子树 后序遍历T的右子树 访问T的根结点例：对下图所示二叉树分别进行先序、中序和后序遍历，所得到的访问序列为： 先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI后序序列：CEDBHGJIFA先序遍历的算法如下：（二叉树的遍历）void preorder (bitreptr T) / /先序遍历以T为根指针的二叉树 if (T!=NULL) visite(T); /访问T的根结点 preorder(T-lchild); /先序遍历T的左子树 preorder(T-rchild); /先序遍历T的右子树 中序遍历的算法如下： void inorder(bitreptr T) /中序遍历 if (T!=NULL) inorder(T-lchild); /中序遍历T的左子树 visite(T); /访问T的根结点 inorder(T-rchild); /中序遍历T的右子树 后序遍历的算法如下void postorder(bitreptr T) /后序遍历 if (T!=NULL) postorder(T-lchild); /后序遍历T的左子树 postorder(T-rchild); /后序遍历T的右子树 visite(T); /访问T的根结点简单顺序查找对一个顺序表进行查找，最简单的方法就是从顺序表的一端开始，逐个进行比较。这种方法无论顺序表是否有序都可以。算法如下：#define maxsize 静态查找表表长typedef structkeytype key;rec;typedef structrec itemmaxsize+1;int n;sqtable;int search_sqtable(sqtable R, keytype K) （P131） i=R.n; R.item0.key=K; /设初始比较位置，设岗哨while (R.item i.key!=K ) i-; /从后往前进行查找return(i); 也可以用R.itemn+1作为岗哨（程序如何改写?）int seqsearch(datatype A, int n, keytype k) i=n; A0.key=k; /A0为岗哨while (Ai.key!=k ) i-; /从后往前进行查找return(i);简单顺序查找在查找成功时的平均查找长度为：ASL=(1+2+n)/n=(n+1)/2，查找失败时的查找长度为n+1。有序表的查找对于任何一个顺序表，若其中的所有结点按键值的某种次序排列，则称为有序表。如果顺序表中的元素是按关键字递增（减）有序排列的，可以采用二分查找（折半查找）来提高查找的时间性能。二分查找的过程如下：设查找区域的首尾下标分别用变量low和high表示，将中间元素（下标为mid=(low+high)/2）的关键字与给定值x进行比较，有三种情况： (1) K= R.item mid.key: 则查找成功，返回mid的值。 (2) K R.item mid.key: 在下标从mid+1到high的区域中继续查找。例：在下图所示有序表中查找8。 在查找的过程中，查找区域不断缩小（low增大，high缩小，且low应不大于high），若lowhigh，则表明查找区域为空，查找失败。二分查找的算法如下： int binsearch(sqtable R, keytype K) int mid,low=1,high=R.n; /初始化查找区域 while (low=high) mid=(low+high)/2; switch case K= R.item mid.key : return (mid); case K R.itemmid.key : low=low+1; break;return (0);int binsearch(datatype A,int n, keytype x) int mid,low=1,high=n; /初始化查找区域 while (low=high) mid=(low+high)/2; if (x=Amid.key) return (mid); else if (xhigh) return(0);else mid=(low+high)/2; if (x=Amid.key) return (mid); else if (xAmid.key) return (binsearch(A, low，mid-1，x); else return (binsearch(A, mid+1，high, x);交换排序交换类排序的基本思想是：两两比较待排序列的元素，发现倒序即交换。冒泡排序冒泡排序的基本思想是：从后往前（或从前往后）依次比较相邻的两个元素，发现倒序即交换，每一趟都能将待排序列中最小（或最大）的元素交换到