chap06-chap07数据结构集合与搜索

《chap06-chap07数据结构集合与搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6、7章集合与搜索一、集合存储二、集合操作的实现三、查找的基本概念四、二分查找五、二叉排序树（二叉搜索树）六、B-树七、索引查找八、哈希或散列(HASH)查找集合及其表示集合基本概念¢集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。¢集合的成员必须互不相同。¢集合中的成员一般是无序的，没有先后次序关系。¢表示方法：{1,2,3,4,5,6,7,8,9,10}¢集合的操作¢集合操作有求集合的并、交、差、判存在等。集合运算的文氏(Venn)图如何在计算中实现集合？•（1

2、）逻辑结构的设定•（2）存储结构•（3）算法线性结构•顺序存储——顺序表•链式存储——链表顺序存储——顺序表顺序表(SeqList)类的定义constintdefaultSize=100;templateclassSeqList:publicLinearList{protected:T*data;//存放数组intmaxSize;//最大可容纳表项的项数intlast;//数组中最后一个元素的下标voidreSize(intnewSize);//改变数组空间大小public:Seq

3、List(intsz=defaultSize);//构造函数SeqList(SeqList&L);//复制构造函数～SeqList(){delete[]data;}//析构函数intSize()const{returnmaxSize;}//求表最大容量intLength()const{returnlast+1;}//计算表长度intSearch(T&x)const;//搜索x在表中位置，函数返回表项序号intLocate(inti)const;//定位第i个表项，函数返回表项序号boolgetDa

4、ta(inti,T&x);//取第i个元素boolInsert(inti,T&x);//插入boolRemove(inti,T&x);//删除……};集合操作的实现集合的“并”运算P52集合的“并”运算voidUnion(SeqList&LA,SeqList&LB){intn1=LA.Length(),n2=LB.Length();inti,k,x;for(i=0;i

5、if(k==0)//若在LA中未找到插入它{LA.Insert(n1,x);n1++;}//插入到第n个表项位置}}集合操作的实现集合的“交”运算集合的“交”运算voidIntersection(SeqList&LA,SeqList&LB){intn1=LA.Length();intx,k,i=0;while(i

6、);n1--;}//在LA中删除它elsei++;//未找到在A中删除它}}链式结构aaaaafirst12345Λ链表的结点类templatestructLinkNode{//链表结点类的定义Tdata;//数据域LinkNode*link;//链指针域};单链表类templateclassList{//单链表类定义protected:LinkNode*first;//表头指针public:List(){first=newLinkNode;}//构造函

7、数List(Tx){first=newLinkNode(x);}List(List&L);//复制构造函数~List(){}//析构函数voidmakeEmpty();//将链表置为空表intLength()const;//计算链表的长度……集合操作的实现——链表集合的逻辑结构——树形结构输入关系分离集合初始状态{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}(2,4){1}{2,4}{3}{5}{6}{7}{8}{9}{10}(5,7){1}{2,4}{3}{5,7}{6}{

8、8}{9}{10}(1,3){1,3}{2,4}{5,7}{6}{8}{9}{10}(8,9){1,3}{2,4}{5,7}{6}{8,9}{10}(1,2){1,2,3,4}{5,7}{6}{8,9}{10}(5,6){1,2,3,4}{5,6,7}{8,9}{10}(2,3){1,2,3,4}{5,6,7}{8,9}{10}操作的分析•1－判断两个元素是否属于同一个集合(查找过程)•2－合并两个不相交集合(合并过程)并查集(Disjoi