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

1、概论数据是信息的载体，是指能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据元素是数据中具有独立意义的个体。在有些场合下，也称为元素、记录、结点、定点等。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。数据结构是指组成数据的元素之间的结构关系。逻辑结构(线性、树形、图、集合) 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法的五个特性：有穷性、确定性、可行性、输入及输出。计算时间复杂度： TOC o 1-5 h z for(i=l； in;i+) x+;0(n)for(i=l;im;i+)for(j=1;j=n;j+)x+;

2、0(m*n)i=lwhile (in) i* =2;0(logn)线性表定义：线性表L是由n个元素a , a，a组成的有限序列，记做L= (a , a，a ),其中n三0为12n12n表长度；当n=0时L为空表，记做L=()。特点： 线性表中每个元素最多有一个直接前驱和一个直接后继。基本运算：初始化线性表initial_list (L)：建立线性表的初始结构，即建立空表。求表长度list_length(L):即求表中的元素个数。按序号取元素get_element(L,i):取出表中序号为i的元素。按值查询list_locate(L,x):取出指定值为x的元素，若存在该元素，则返回其地址；否则，

3、返回一 个不存在的地址值或标记。插入元素list_insert(L,i,x):在表L的第i个元素位置上插入值为x的元素。删除元素list_selete(L,i):删除表L中序号为i的元素。串是由有限个字符a：,a2,a3, ,an组成的序列，记做S=“a,a,a, ,a ”。123n串的5个基本算法和2个常用算法：赋值运算(S=S1)：将一个串(值)S1传送给串S。求长度运算str_length (S)：返回串S的长度值。连接运算(S1+S2)：将串S1和S2连接成一个新串。求子串函数substr (S,i,j)：返回串S中从第i个元素开始的j个元素所组成的子串。串比较：比较两个串的大小。插入

4、运算str_insert(S,i,Sl)：将子串S1插入到串S的从第i个字符开始的位置上。删除算法str_delete(S,i,j)：删除串S中从第i个字符开始的j个字符。数组数组的顺序存储以行序为主序的存储(即行优先次序)以列序为主序的存储(即列优先次序)栈栈是只能在一端进行插入和删除的线性表。栈具有后进先岀或先进后岀的特性。栈的基本算法：初始化栈init_stack(S):设置栈S为空栈。判断栈是否为空stack_empty(S):若栈S为空，返回FALSE。取栈顶元素值stack_top(S, x)：若栈S不空，则将栈S的栈顶元素的值送变量x中，否则应返回出错 信息。入栈push_sta

5、ck(S, x):将值为x的元素插入到栈S的栈顶。若插入前的栈已满，不能入栈时，应报出 错信息。出栈pop_stack(S):若栈S不空，删除栈S的栈顶元素，否则应返回出错信息。判断栈是否已满stack_full(S)：栈S满时，返回TRUE；否则，返回FALSE。队列队列是只能在一端插入、另一端删除的线性表。队列的运算初始化队列init_queue(Q)：设置队列Q为空。判断队列是否为空queue_empty(Q)：若队列Q为空，返回TRUE；否则返回FALSE。取队头元素queue_front(Q,x):若队列Q不空，求出队列Q的队头元素置于x中，否则，返回出错信息。入队En_queue(

6、Q,x):将值为x的元素插入到队列Q中。若插入前队列已满，不能入队时，应报出错信 息。出队Out_ queue(Q,x):若队列Q不空，删除队头，并将该元素的值置于x中，否则，应返回“下溢出” 错误信息。判断队列是否已满queue_full(Q)：若Q已满，返回TRUE；否则返回FALSE。树T是n个结点构成的有限集合(n0),其中有一个结点叫根，其余结点可划分为m个互不相交的子集 T,T,T(m20)，并且这m个子集本身又构成树，称为T的子树。12m树的表示形式：图形表示法嵌套集合表示法凹入表表示法广义表表示法树的运算：初始化树initial_tree(T)：简历数或森林T的初始结构。插入子

7、树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个结点的有限集合，其中n20。当n=0时，T为空树，否则，其中有一个结点为根结点，其 余结点划分为两个互不相交的子集tl、Tr，并且tl、Tr也构成二叉树，分别称

8、为左右子树。LRLR形态个数计算公式：l/(n+l) Cn2n二叉树的性质：性质1：在二叉树的第i层上的结点数W2i-i(i0)。性质2：深度为k的二叉树的结点数W2k-1(k0)。性质3：对任意一颗非空的二叉树T如果其叶子数为气，度为2的结点数为气，则有关系式气=气+1成立。性质4：有n个结点的完全二叉树(n0)的深度为Llog2n+1.( Lx表示不大于x的最大整数) 性质 5：在编号的完全二叉树中，各节点的编号之间的关系为：如果编号为i的结点存在左孩子结点，则其左孩子结点的编号为2i。如果编号为i的结点存在右孩子结点，则其右孩子结点的编号为2i+1。如果编号为i的结点存在父结点，则其父结

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

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

11、快速排序： 首先，选定一个元素作为中间元素，然后将表中所有元素与该中间元素相比较，将表中比中间 元素小的元素调到表的前面，将比中间元素大的元素调到后面，再将中间数放在这两部分之间以作为分界 点，这样便得到一个划分。然后再对左、右两部分分别进行快速排序。不稳定；时间复杂度(理想情况 下 0 (nlog2n) 。 另一极端情况下0 (n2) 。 一般情况下0 (knlog2n) ，其中 k 为某常数。)选择排序： 在每一趟排序中，在待排序子表中选出关键字最小或最大的元素放在其最终位置上。对深度为 k的堆，比较至多2(k-1 )次，而有n个结点的完全二叉树的深度 log2n+1，调整堆比较不超过 l

12、og(n-1)+log(n-2)+log2，建初始堆比较不超过4n， 0(nlogn)查找查找： 对给定的一个关键字的值，在数据表中搜索出一个关键字的值等于该值的记录或元素。查找长度： 查找一个元素所进行的关键字的比较次数。常以平均查找长度、最大查找长度等来衡量查找算法的总的时间性能。折半査找：如果查找表A已经按关键字递增(减)有序，此处不妨设为递增数列有序，则可采用二分查找 来查找。二叉排序树是一棵二叉树，或者为空，或者满足如下条件：若左子树不空，则左子树上所有结点的值均小于根的值。若右子树不空，则右子树上所有结点的值均大于或等于根的值。其左、右子树均为二叉排序树。平衡二叉树是一棵二叉树，或

13、者为空，或者满足如下条件：左右子树深度之差的绝对值不超过 1。左右子树都是平衡二叉树。结点的平衡因子 = 结点的左子树深度 - 结点的右子树深度平衡化：LL型调整(将A的左孩子B提升为新的根结点。将原来的根结点A降为新的根结点B的右孩 子。各子树按照大小关系连接)；RR型调整(将A的右孩子B提升为新的根结点。将原来的根结点 A降为新的根结点B的左孩子。各子树按照大小关系连接。)；LR型调整(将C提升为新的根结点。 将原来的根结点A降为新的根结点C的右孩子。各子树按照大小关系连接。)；RL型调整(将C提升为 新的根结点。将原来的根结点A降为新的根结点C的左孩子。各子树按照大小关系连接。)直接插入

14、排序的算法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,Datatype x) int i;for(i=0;ilength & L-datainext)p=p-next; p-

15、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 bubble_sort(elementtype An+) i=1;do exchanged=FALSE;

16、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) i+;if(ij) Aj=Ai;j=j-1;Ai=x;cutpoint=i;快排算法：void QuickSo

17、rt(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;堆排序堆排序的筛选算法void sift(elementtype A,int k,int m) x=Ak;finished=FALSE;i=

18、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 swaptree(btree b) btree t,t1,t2;if(b=NULL)t=NULL;else t (btree)mallo

19、c(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-dataL-length-1-i=t;用单链表将线性表就地逆置LinkList ReverseList( LinkList head) List

20、Node *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 &lc) int ia=1,ib=1,ic=1;while(ia=la & ib=lb)if(Aia=Bib)Cic+=Aia+;else

21、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;while(low=high) mid=(low+high)/2; if(x=Amind.key) return mid; else if(xhigh)r

22、eturn-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)return bst_search(T-lchild,x);else return bst_search(T-rchild,x); 二叉排序树中插入结点的实现 v

23、oid 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=x;u-lchild=NULL;u-rchild=NULL;insert(T,u);cinx;假设在长度大于1的单循环链表中，既无头结点也无指针。s为指向链

24、表中某个结点的指针，试编写算法删除结点*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-rchild, n);求一棵二叉树T的叶子结点数目void countleaf(Bitree T,int &n) if (T) countleaf(T-child, n);if (!T-l

25、child &!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=ch;create(T-lchild ); create(T-rchild );先序遍历的非递归算法：#define maxsize 100ty

26、pedef 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;中序遍历的非递归算法：#define maxsize 100 typedef struct Bitree Elemmaxsize;int top;

27、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 100typedef enumL,R tagtype; typedef struct Bitree ptr;tagtype tag;stacknode; typedef

28、struct stacknod Elemmaxsize; int top;SqStack;void PostOrderUnrec(Bitree t) SqStack s;stacknode xStackInit(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;visite(p-data);if(! StackEmpty(s)s.Elems.top.tag=R;p=s.Elems.top.ptr-rch

29、ild;while(! StackEmpty(s);一个线性表中的元素为正整数或负整数，设计一个算法，将正整数和负整数分开，使线性表的前部为负整数，后部为正整数，不要求对他们排序，但要求尽量减少交换次数。void ReSort(Seqlist R) int i=1,j=n;while(ij) while(ij & Ri.key0)i+;while(i=0)j-;R0=Ri;Ri+=Rj;Rj-=R0;编写一个直接插入排序算法，使得查找插入位置时不是采用顺序的方法而是采用二分的方法。void BinInSort(SeqList R) int i,j,low,high;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