合肥师范学院数据结构复习资料

1、概论数据数据元素字段是对元素的详细描述，通常情况下，元素可能包含多个字段。数据结构是指组成数据的元素之间的结构关系。逻辑结构（线性、树形、图、集合）算法算法的五个特性：有穷性、确定性、可行性、输入及输出。计算时间复杂度：for(i=1；in;i+）x+;O(n)for(i=1;im;i+) for(j=1;j=n;j+)x+;i=1while (i0),其中有一个结点叫根，其余结点可划分为 m 个互不相交的子集T1,T2,Tm(m0)，并且这m 个子集本身又构成树，称为T 的子树。树的表示形式：图形表示法嵌套集合表示法凹入表表示法广义表表示法树的运算：初始化树initial_tree(T)：简

2、历数或森林T 的初始结构。插入子树insert_tree(T,S)：将以S 为根的子树作为T 的第一个子树插入到树中。插入兄弟结点insert_sibling(T,S)：将以结点S 为根的树作为T 的兄弟子树插入到树中。查询根结点rootof(T)：查询结点T 所在树的根结点。查询父结点fatherof(T)：查询结点T 的父结点。查询孩子结点childof(T)：查询结点T 的所有或某个孩子结点。查询兄弟结点siblingof(T)：查询结点T 的所有或某个兄弟结点。二叉树 T 是n 个结点的有限集合，其中n0。当n=0 时，T 为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相

3、交的子集TL、TR，并且TL、TR 也构成二叉树，分别称为左右子树。形态个数计算公式：1/(n+1)Cn2n二叉树的性质：性质 1：在二叉树的第i 层上的结点数2i-1(i0)。性质 2：深度为k 的二叉树的结点数2k-1(k0)。性质 3：对任意一颗非空的二叉树T 如果其叶子数为n0，度为 2 的结点数为n2，则有关系式n0=n2+1 成立。4：有nlogn+1.( x 表示不大于x2性质 5：在编号的完全二叉树中，各节点的编号之间的关系为：如果编号为i 的结点存在左孩子结点，则其左孩子结点的编号为2i。如果编号为i 的结点存在右孩子结点，则其右孩子结点的编号为2i+1。如果编号为i 的结点

4、存在父结点，则其父结点的编号为i/2。先序遍历：先访问根结点，再遍历其左、右子树。中序遍历：访问根结点在遍历其左、右子树之间。后序遍历：访问根结点在遍历其左、右子树之后。排序排序是将数据表调整为按关键字从小到大或从大到小的次序排列的过程。分类方法：增排序和减排序：内部排序和外部排序：数据表中的所有数据是否在内存中。稳定排序和不稳定排序：关键字相同的两个元素的相对次序是否变化。排序的基本方法：插入排序、交换排序、选择排序、归并排序和基数排序。直接插入排序将整个待排序子表看做左右两部分，其中左边为有序区，右边为无序区，整个排序过程是将右边无序区中的元素逐个插入到左边的有序区中已构成新的有序区稳定一

5、个存储空间循环 n-1 次（开始有序：比较和移动元素次数为(n-1)和 2(n-1),O(n)。逆序：比较和移动元素次数为(n+2)(n-1)/2和(n+4)(n-1)/O(n)。希尔排序：将待排序列划分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。不稳定；各趟O(n)，需要logn 趟，总为O(nlogn)。22冒泡排序：从一端开始，逐个比较相邻的两个元素，发现倒序即交换。简单算法O(n2)。改进算法稳定（初始正序，比较次数为n-1 次，交换0，O(n)。初始逆序，第i 趟比较与交换均为(n-i)，整个比较和交换为 n(n-1)/2，O(n2)。

6、首先，选定一个元素作为中间元素，然后将表中所有元素与该中间元素相比较，将表中比中间 点，这样便得到一个划分。然后再对左、右两部分分别进行快速排序。不稳定；时间复杂度（O(nlogn)。另一极端情况下O(n2)。一般情况下O(knlogn)，其中k）22选择排序：在每一趟排序中，在待排序子表中选出关键字最小或最大的元素放在其最终位置上。对深度为k 的堆，比较至多 2（k-1）次，而有 n 个结点的完全二叉树的深度logn+1，调整堆比较不超过2log(n-1)+log(n-2)+log2，4n，O(nlogn)2222查找查找：对给定的一个关键字的值，在数据表中搜索出一个关键字的值等于该值的记录

7、或元素。法的总的时间性能。折半查找：如果查找表A 已经按关键字递增（减）有序，此处不妨设为递增数列有序，则可采用二分查找来查找。二叉排序树是一棵二叉树，或者为空，或者满足如下条件：若左子树不空，则左子树上所有结点的值均小于根的值。若右子树不空，则右子树上所有结点的值均大于或等于根的值。其左、右子树均为二叉排序树。平衡二叉树是一棵二叉树，或者为空，或者满足如下条件：左右子树深度之差的绝对值不超过1。左右子树都是平衡二叉树。结点的平衡因子 = 结点的左子树深度 - 结点的右子树深度（A 的左孩子BA 降为新的根结点BRR型调整（将A的右孩子B A降为新的根结点B的左孩子。各子树按照大小关系连接LR

8、（将C将原来的根结点A降为新的根结点CRL（将C提升为新的根结点。将原来的根结点AC）直接插入排序的算法void insert_sort(elementtype An+1)for(i=2;itemp.key) Aj+1=Aj;j=j-1;Aj+1=temp;带有监视哨的代码void insert_sort(elementtype An+1)for(i=2;iA0.key) Aj+1+Aj;j=j-1; Aj+1=A0;设顺序表 L 是一个递增有序表，试写一个算法，将x 插入 L 中，并使 L 仍是一个有序表。void InsertIncreaseList(Sequenlist *L,Datat

9、ype x) int i;for(i=0;ilength & L-datainext)p=p-next;p-next=q-next; return L1;希尔排序的算法void shell_sort(elementtype An+)dh=d1; while(dh=1) for(i=dh+1;idh & Aj.keytemp.key) Aj+dh=Aj;j=j-dh;Aj+dh=temp;dh=db/2;冒泡排序的算法void bubble_sort(elementtype An+1)for(i=1;i=i+1;j-)if(Aj.keyAj-1.key) AjAj-1;改进：提高时间性能void

10、 bubble_sort(elementtype An+) i=1;do exchanged=FALSE; for(j=n;j=i+1;j-)if(Aj.keyAj-1.key) AjAj-1;exchanged=TRUE; i+; while(i=n-1 & exchanged=TRUE);快速排序的算法划分算法：void partition(elementtype A,int s,int t,int& cutpoint) x=As;i=s;j=t; while(i!=j) while(ix.key) j-;if(ij) Ai=Aj;i=i+1; while(ij & Ai.keyx.key

11、) i+; if(ij) Aj=Ai;j=j-1; Ai=x;cutpoint=i;快排算法：void QuickSort(elementtype An,int s,int t) int i; if(st) partition(A,s,t,i);QuickSort(A,s,i-1);QuickSort(A,i+1,t);选择排序的算法：直接选择排序void select_sort(elementtype An) for(i=0;in-1;i+) min=i; for(j=i+1;jn;j+)if(Aj.keyAmin.key) min=j;if(min!=i)AminAi;堆排序堆排序的筛选算

12、法void sift(elementtype A,int k,int m) x=Ak;finished=FALSE; i=k;j=2*i;while(j=m & ! finished) if(jm & Aj.key=Aj.key) finished=TRUE; else Ai=Aj;i=j;j=2*j;Ai=x;堆排序算法void heap_sort(elementtype A,int n) for(i=n/2;i=1,i-)sift(A,i,n);for(i=n;i=2;i-) AiA1;sift(A,1,i-1);以二叉链表为存储结构，编写一算法交换各结点的左右子树。Btree swapt

13、ree(btree b) btree t,t1,t2; if(b=NULL) t=NULL;else t (btree)malloc(sizeof(btree); t-data=b-data;t1=swaptree(b-Lchild); t2=swaptree(b-Rchild); t-Lchild=t2;t-Rchild=T1;return(t);用顺序表将线性表就地逆置void ReverseList( Seqlist *L) Datatype t; int i;for(i=0;ilength/2;i+)t=L-datai;L-datai=L-dataL-length-1-i; L-dat

14、aL-length-1-i=t;用单链表将线性表就地逆置LinkList ReverseList( LinkList head) ListNode *p,*q;if( head-next & head-next-next) p=head-next;q=p-next;p-next=NULL; while(q) p=q;q=q-next;p-next=head-next; head-next=p;return head;return head;归并排序的算法void merge(elementtype A,elementtype B,elementtype C,int la,int lb,int

15、&lc) int ia=1,ib=1,ic=1; while(ia=la & ib=lb) if(Aia=Bib)Cic+=Aia+;else Cic+=Bib+; while(ia=la) Cic+=Aia+;while(ib=lb) Cic+=Bib+;顺序查找算法int seq_search(elementtype A,int n,keytype x) i=n;A0.key=x; while(A1.key!=x)i-; return i;折半查找的算法int bin_search(elementtype A,int n,keytype x) int mid,low=0,high=n-1;

16、 while(low=high) mid=(low+high)/2; if(x=Amind.key) return mid; else if(xhigh)return-1;else mid=(low+high)/2; if(x=Amid.key)ruturn mid; else if(xkey) return P;else if(xkey) P=P-lchild; else P=P-rchild;return P;递归算法Bnode * bst_search(Bnode * T,keytype x) if(T=NULL | t-key=x) return T;else if(xkey)retu

17、rn bst_search(T-lchild,x); else return bst_search(T-rchild,x);二叉排序树中插入结点的实现void insert(Bnode * &T,Bnode *S) if(T=NULL)T=S;else if(S-keykey)insert(T-lchild,S); else insert(T-rchild,S);二叉排序树的构造void create_bst(Bnode * &T); Bnode * u; elementtype x; T=NULL; cinx;while(x!=End_of_Num) u=new Bnode; u-data=

18、x;u-lchild=NULL;u-rchild=NULL; insert(T,u);cinx;假设在长度大于 1 的单循环链表中，既无头结点也无指针。s 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。void DeleteNode(ListNode *s) ListNode *p,*q; p=s;while(p-next!=s) q=p;p=p-next; q-next=s;free(p);输出二叉树 T 的所有结点的值void output(Bitree T) if (T) countleaf(T-child); coutdata; countleaf(T-rchil

19、d, Tvoid countleaf(Bitree T,int &n) if (T) countleaf(T-child, n);if (!T-lchild &!T-rchild)n+; countleaf(T-rchild, n);求二叉树的深度void depth(Bitree T) if (!T) return 0;else return max(high(T-lchild),high(T-rchild)+1;输入一个二叉树的先序序列，构造二叉链表。void create(Bitree &T ) cinch;if (ch=#) T=NULL;else T=new Bnode;T-data

20、=ch; create(T-lchild create(T-rchild 先序遍历的非递归算法： #define maxsize 100 typedef struct Bitree Elemmaxsize; int top;SqStack;void PreOrderUnrec(Bitree t) SqStack s;StackInit(s);p=t;while(p!=null | ! StackEmpty(s) while(p!=null) visite(p-data); push(s,p);p=p-lchild;if(! StackEmpty(s)p=pop(s); p=p-rchild;中

21、序遍历的非递归算法： #define maxsize 100 typedef struct Bitree Elemmaxsize; int top;SqStack;void InOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t;while(p!=null | ! StackEmpty(s) while(p!=null) push(s,p); p=p-rchild;if(! StackEmpty(s)p=pop(s); visite(p-data);p=p-lchild;后中序遍历的非递归算法： #define maxsize 100 typed

22、ef enumL,R typedef struct Bitree ptr; tagtype stacknode; typedef struct stacknod Elemmaxsize; int top;SqStack;void PostOrderUnrec(Bitree t) SqStack s; stacknode x StackInit(s); p=t;do while(p!=null) x.ptr=P; x.tag=L; push(s,x); p=p-lchild;while(! StackEmpty(s) & s.Elems.top.tag=R) x=pop(s); p=x.ptr;

23、 visite(p-data);if(! StackEmpty(s)s.Elems.top.tag=R; p=s.Elems.top.ptr-rchild;while(! StackEmpty(s);一个线性表中的元素为正整数或负整数，设计一个算法，将正整数和负整数分开，使线性表的前部为负整数，后部为正整数，不要求对他们排序，但要求尽量减少交换次数。void ReSort(Seqlist R) int while(ij) while(ij & Ri.key0) i+;while(i=0) j-;R0=Ri; Ri+=Rj;Rj-=R0;编写一个直接插入排序算法，使得查找插入位置时不是采用顺序的方法而是采用二分的方法。void BinInSort(SeqList R) int for(i=2;i=n;i+) low=1;high=i-1;R0=Ri; while(lowR0.key)high=mid-1; elselow=mid+1;for(j=i-1;j=low;j-)Rj+1=Rj;Rj=R0;以单链表为存储结构，写一个直接选择排序算法。# define int typedef struct keyType key; OtherInfoType struct node * RecNode;typedef RecNode * LinkList; voi