数据结构复习重点

1、学习好资料欢迎下载数据结构复习重点1、数据结构的概念、分类；渐进的时间复杂度（大。表示法）。（P391.13）2、顺序表的定义和特点，插入、删除和查找算法（P49）,对它们的性能估计，包括搜索算法的平均搜索长度，插入与删除算法的对象平均移动次数（P842.3）;单链表的定义和特点，带表头结点单链表的插入、删除和查找算法（P82P63）；3、栈、队列定义、特点，栈满栈空、队满队空条件及表达（Pl15）;4、（1）数组的概念、特点；顺序存储方式的计算（P1834.1）；（2）广义表的概念、存储表示、Head与tail操作（P1844.10,4.11）;5、二叉树的定义、性质、存储表示，遍历规则；堆

2、的定义；堆的建立、插入、删除方法；树的定义，相关概念以及存储表示方法，树的二叉树表示、遍历规则；森林与二叉树的转换规则；Huffman树的建立，WPL#算；Huffman编码的建立，电文总码数计算。（P2469,11,16,17,18,19,20）6、散列表的构造，线性探测法，双散列探测法解决冲突计算。（出56.9）7、静态搜索表的顺序搜索和折半搜索算法；（P300,P305）.二叉搜索树的表示、搜索、插入、删除方法。（P3423,8,9）.8、图的定义、相关概念以及存储表示；图的遍历规则及得到生成树的方法；用Kruskal、Prim方法构造最小生成树；单源求最短路径方法；AOV3络定义，拓扑

3、排序方法；AOER络定义，关健路径的求法。（10,17,补充3题）9、希尔排序方法、快速排序方法、两路归并排序方法、直接插入排序、起泡排序、直接选择排序方法。（Pmi2）10、文件的定义，组成，存储结构；稠密索引、稀疏索引概念；多关键码文件组织方法（倒排表，P48915）。顺序表，插入、删除和查找算法template<classT>intSeqList<T>:Search(T&x)const/*搜索函数：在表中顺序搜索与给定值x匹配的表项，找到则函数返回该表项是第几个元素，否则函数返回0,表示搜索失败*/intb=0;/用来标记for(inti=0;i<=

4、last;i+)if(datai=x)b=i+1;cout<<b<<""/顺序搜索returnb;/搜索失败template<classT>boolSeqList<T>二Insert1(inti,T&x)/*将新元素x插入到表中第i(0<=i<=last+1)个表项之后。函数返回插入成功的信息，若插入成功，则返回true ;否则返回 个元素位置。*/if(last=maxSize-1) return false; if(i<0|i>last+1) return false; / for(int

5、j=last;j>=i;j-) dataj+1=dataj; / datai=x;/last+; /false。i=0是虚拟的，实际上是插入到第1/表满，不能插入参数i不合理，不能插入依次后移，空出第i号位置插入插入成功returntrue;template<classT>boolSeqList<T>二Remove1(inti,T&x)/*从表中删除第i(1<=i<=last+1)个项，通过引用型参数x返回删除的元素值。函数返回删除成功的信息，若删除成功则返回 if(last=-1) return false; / if(i<1|i>

6、;last+1)return false; / x=datai-1;for(int j=i;j<=last;j+) dataj-1=dataj; / last-;/maxSize-; return true; template <class T> bool SeqList<T>:Insert2(T& x)true ,否则返回 false 。*/表空，不能删除参数i不合理，不能删除依次前移，填补删除成功/*不考虑顺序表元素的顺序直接在表尾插入所要插入的新元素值*/表满，不能插入if(last=maxSize-1)returnfalse;/datalast=x

7、;/last+;return true;template <class T>bool SeqList<T>二Remove2(int i,T &x) /*不考虑顺序表元素的顺序, 个元素*/if(last=-1) return false; / if(i<1|i>last+1)return false; / x=datai-1;datai-1=datalast-1; / last-;/return true;在表尾直接插入通过最后的元素填到第i个元素，从而删除第i表空，不能删除参数i不合理，不能删除最后的元素填到第i个元素 删除第i个元素成功单链表的定

8、义和特点，带表头结点单链表的插入、删除和查找算法template<classT>LinkNode<T>*List<T>二Search(Tx)在表中搜索含数据x的结点，搜索成功是函数返回该结点地址；否则返回NULLffloLinkNode<T>*current=first->link;while(current!=NULL)if(current->data=x)break;elsecurrent=current->link;returncurrent;template<classT>boolList<T>二

9、Insert(inti,T&x)/将新元素x插入在链表第i个位置。LinkNode<T>*current=Locate(i-1);if(current=NULL)returnfalse;LinkNode<T>*newNode=newLinkNode<T>(x);if(newNode=NULL)cerr<<"存储分配错误！"<<endl;exit(1);newNode->link=current->link;/连接在current之后current->link=newNode;/插入成功re

10、turntrue;template<classT>LinkNode<T>*List<T>二Locate(inti)/定位函数。返回表中i个元素的地址。若i<0或i超出表中结点个数，则返回NULLif(i<0)returnNULL;/iLinkNode<T>*current=first;intk=0;while(current!=NULL&&k<i)/current=current->link;k+;returncurrent;/若返回NULL表示i值太大template<classT>boolList<T>二Remove(inti,T&x)/将表中的第i个元素删去，通过引用型参数不合理循链找第i个结点返回第i个结点地址,x返回该元素的值。LinkNode<T>*current=Locate(i-1);if(current=NULL|current->link=NULL)re