数据结构复习要点.doc

A—熟练掌握B—理解C—了解第一章::包括数据的逻辑结构、数据的存储结构和数据的相关运算。C四类数据组织结构:集合、线性表、树形、图状结构C数据的存储方式:顺序存储和链式存储。、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B本章重点:()?()..求下段程序的时间复杂度:voidmergesort(inti,intj){ intm; if(i!=j){ m=(i+j)/2; mergesort(i,m); mergesort(m+1,j); merge(i,j,m);}}其中mergesort()用于对数组a[n]归并排序,调用方式为mergesort(0,n-1);,merge()用于两个有序子序列的合并,是非递归函数,时间复杂度为。解:分析得到的时间复杂度的递归关系:为merge()所需的时间,(c为常量)。因此 令,有有第二章::…..(利用静态数组或动态内存分配)。。相应的表示与操作。包括循环链表、双向链表。:基于时间的考虑--分别适用于静态的和动态的操作:比如静态查找和插入删除);基于空间的考虑--…….B这也适用于后面用两种方式存储的其他数据结构。★本章重点:很熟悉顺序表,单链表、双链表,循环链表的基本操作;并学会在各种链表上进行一些算法设计(与基本操作类似的操作或组合),请仔细复****均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。[题目分析]因为两链表已按元素值递增次序排列,将其合并时,均从第一个结点起进行比较,将小的链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时,将链表结点逆置。voidUnion(LinkListla,LinkListlb) ∥la,lb分别是带头结点的两个单链表的头指针,链表中的元素值按递增序排列,本算法将两链表合并成一个按元素值递减次序排列的单链表。 {pa=la->next;pb=lb->next;∥pa,pb分别是链表la和lb的工作指针    la->next=null;          ∥la作结果链表的头指针,先将结果链表初始化为空。   while(pa!=null&&pb!=null)∥当两链表未访问结束     if(pa->data<=pb->data)       { q=pa->next;          ∥将pa的后继结点暂存于q。          pa->next=la->next;   ∥将pa结点链于结果表中,同时逆置。la->next=pa;pa=q;                ∥恢复pa为当前待比较结点。}     else{q=pb->next;∥将pb的后继结点暂存于q。pb->next=la->next;∥将pb结点链于结果表中,同时逆置。la->next=pb;pb=q;∥恢复pb为当前待比较结点。}     while(pa!=null)∥将la表的剩余部分链入结果表,并逆置。          {q=pa->next;pa->next=la->next;la->next=pa;pa=q;}       while(pb!=null)          {q=pb->next;pb->next=la->next;la->next=pb;pb=q;}}∥算法Union结束。注意:(1)此处q用作暂存后继结点,操作后pa或pb还回原指向位置;这与我们原来不改变pa或pb的指向,增加一个q=pa或pb作为摘取结点进行添加操作起到的作用一样。(2)此处要完成逆序插入操作故用头插法(基于头指针la或lb),注意尾插法(附设一个尾指针,基于该指针插入)的可完成顺序插入。(注意:逆序另一种方式也要掌握!)练****练****题2编程1——(带头结点)是否是递增的(注意比排序算法应该简单,链表排序也要会实现)(即表A中的元素在B中)。(思考:如果递归程序怎么写?)第三章::分别有后进先出、先进先出的特性。B