`
java-mans
  • 浏览: 11380662 次
文章分类
社区版块
存档分类
最新评论

【编程珠玑】第十三章 搜索

 
阅读更多

一，概述

第十二章，介绍生成某个范围内随机数，并按顺序输出。

本章主要介绍，存储按序输出的容器或者说存放集合的方法。并实现按序插入，按序输出。

1）set容器

1>set容器小例子：

#include <iostream>
#include <set>
using  namespace std;

int main()
{
    set<int> S;
    S.insert(1);
    S.insert(3);
    S.insert(2);
    S.insert(1);
    set<int>::iterator p;
    for(p=S.begin();p!=S.end();p++)
    	cout<<*p<<" ";
    cout<<endl;

    cout<<"the total elements is:"<<S.size()<<endl;
    return 0;	
}

输出：1 2 3 //自动屏蔽重复元素

the total elements is: 3

2>set容器实现插入元素，并有序输出

class IntSetSTL {
private:
	set<int> S;
public:
	IntSetSTL(int maxelements, int maxval) { }//构造函数
	int size() { return S.size(); }
	void insert(int t) { S.insert(t);}//插入
	void report(int *v)//输出函数
	{	int j = 0;
		set<int>::iterator i;
		for (i = S.begin(); i != S.end(); ++i)
			v[j++] = *i;
	}
};
【注意】不管你按什么顺序输入，你得到的输出都是有序的。


2）数组（类似于插入排序）哨兵放最后

思路：初始化时候，取一个很大元素作为哨兵，哨兵永远置于元素最后。

插入时候遇到重复元素，返回

遇到比自己大的第一个元素，将该元素以及以后的元素后移一位，最后将该元素插入该位置

class IntSetArr {
private:
	int	n, *x;
public:
	IntSetArr(int maxelements, int maxval)
	{	x = new int[1 + maxelements];//先申请个数  +1  说明用到哨兵了
		n=0;
		x[0] = maxval; /* sentinel at x[n] */
	}
	int size() { return n; }
	void insert(int t)
	{	int i, j;
		for (i = 0; x[i] < t; i++)//遇到比要插入元素 t 还小的 就后走
			;
		if (x[i] == t)//说明数组中已经包含t
			return;
		for (j = n; j >= i; j--)//
			x[j+1] = x[j];
		x[i] = t;
		n++;
	}
	void report(int *v) //按序输出每一个元素
	{	for (int i = 0; i < n; i++)
			v[i] = x[i];
	}
};

3）链表（采用递归）依然采用哨兵

思路：node *rinsert(node *p, int t)是关键函数
注意调用的时候，p->next=rinsert(p->next,t); 如果小于则一直等于next
如果p-val > t 则 p =new node(t,p);说明第一个大于t的p被作为新节点（val=t）的next //细细体会，最好画图理解

class IntSetList {
private:
	int	n;
	struct node {
		int val;
		node *next;
		node(int i, node *p) { val = i; next = p; }
	};
	node *head, *sentinel;
	node *rinsert(node *p, int t) //递归插入函数
	{	if (p->val < t) {
			p->next = rinsert(p->next, t);
		} else if (p->val > t) {
			p = new node(t, p);
			n++;
		}
		return p;
	}
public:
	IntSetList(int maxelements, int maxval)  //初始化函数时候，将哨兵置于第一个
	{	sentinel = head = new node(maxval, 0);
		n = 0;
	}
	int size() { return n; }
	void insert(int t) { head = rinsert(head, t); } //调用递归插入函数
	void insert2(int t)
	{	node *p;
		if (head->val == t)
			return;
		if (head->val > t) {
			head = new node(t, head);
			n++;
			return;
		}
		for (p = head; p->next->val < t; p = p->next)
			;
		if (p->next->val == t)
			return;
		p->next = new node(t, p->next);
		n++;
	}
	void insert3(int t)//类似数组的插入
	{	node **p;
		for (p = &head; (*p)->val < t; p = &((*p)->next))//找到第一个大于等于p的节点
			;
		if ((*p)->val == t)
			return;
		*p = new node(t, *p);//创建节点的同时，将节点插入到正确位置
		n++;
	}
	void report(int *v)//输出整个链表
	{	int j = 0;
		for (node *p = head; p != sentinel; p = p->next)
			v[j++] = p->val;
	}
};


第二种实现方法（链表非递归）：主要是找到第一个大于t的节点，然后插入到其前面。

class IntSetList2 {
private:
	int	n;
	struct node {
		int val;
		node *next;
	};
	node *head, *sentinel, *freenode;
public:
	IntSetList2(int maxelements, int maxval)//最大元素个数和哨兵
	{	sentinel = head = new node;
		sentinel->val = maxval;
		freenode = new node[maxelements];
		n = 0;
	}
	int size() { return n; }
	void insert(int t)
	{	node **p;
		for (p = &head; (*p)->val < t; p = &((*p)->next))
			;
		if ((*p)->val == t)
			return;
		freenode->val = t; //将t插入到第一个大于t的元素的前面
		freenode->next = *p;
		*p = freenode++;
		n++;
	}
	void report(int *v)
	{	int j = 0;
		for (node *p = head; p != sentinel; p = p->next)
			v[j++] = p->val;
	}
};


4）二分搜索树（类似链表） 

class IntSetBST {
private:
	int	n, *v, vn;
	struct node {
		int val;
		node *left, *right;
		node(int v) { val = v; left = right = 0; }
	};
	node *root;
	node *rinsert(node *p, int t)
	{	if (p == 0) {
			p = new node(t);
			n++;
		} else if (t < p->val) {
			p->left = rinsert(p->left, t);
		} else if (t > p->val) {
			p->right = rinsert(p->right, t);
		} // do nothing if p->val == t
		return p;
	}
	void traverse(node *p)//中序遍历输出
	{	if (p == 0)
			return;
		traverse(p->left);
		v[vn++] = p->val;
		traverse(p->right);
	}
public:
	IntSetBST(int maxelements, int maxval) { root = 0; n = 0; }
	int size() { return n; }
	void insert(int t) { root = rinsert(root, t); }
	void report(int *x) { v = x; vn = 0; traverse(root); }
};


第二种实现方法 （习题7答案，采用哨兵）

class IntSetBST2 {
private:
	int	n, *v, vn;
	struct node {
		int val;
		node *left, *right;
	};
	node *root, *freenode, *sentinel;

	void traverse(node *p)
	{	if (p == sentinel)
			return;
		traverse(p->left);
		v[vn++] = p->val;
		traverse(p->right);
	}
public:
	IntSetBST2(int maxelements, int maxval)
	{	root = sentinel = new node;  
		n = 0;
		freenode = new node[maxelements];
	}
	int size() { return n; }

	void insert(int t)
	{	sentinel->val = t;
		node **p = &root;       //指向指针的指针
		while ((*p)->val != t)
			if (t < (*p)->val)
				p = &((*p)->left);
			else
				p = &((*p)->right);
		if (*p == sentinel) {
			*p = freenode++;
			(*p)->val = t;
			(*p)->left = (*p)->right = sentinel;
			n++;
		}
	}
	void report(int *x) { v = x; vn = 0; traverse(root); }
};





5）专门用于整数处理的数据结构

class IntSetBitVec {
private:
	enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
	int	n, hi, *x;
	void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }
	void clr(int i)  {        x[i>>SHIFT] &= ~(1<<(i & MASK)); }
	int  test(int i) { return x[i>>SHIFT] &   (1<<(i & MASK)); }
public:
	IntSetBitVec(int maxelements, int maxval)
	{	hi = maxval;
		x = new int[1 + hi/BITSPERWORD];
		for (int i = 0; i < hi; i++)
			clr(i);//所有的位都置零
		n = 0;
	}
	int size() { return n; }
	void insert(int t)
	{	if (test(t))
			return;
		set(t);
		n++;
	}
	void report(int *v)
	{	int j=0;
		for (int i = 0; i < hi; i++)
			if (test(i))
				v[j++] = i;
	}
};

解释：其中i>>SHIFT 相当于 i/32得到对应数组下标【二进制右移5位相当于十进制除以32】
i&MASK相当于 i mod 32，因为每一个数32位。最大只能左移32位。

1<<(i&MASK)相当于获得2的(i&MASK)次幂，就是1左移(i&MASK)位

i=[0,31] 标记在数组第一位 i=[32,63] 标记在数组第二位


下面看一个例子：

#include <iostream>

using namespace std;
int a[10] = {0};
const int shift = 5;
const int maskl = 0x1F;
void setB(int i)
{
 a[i>>shift] |=1<<(i&maskl);
}
void cls(int i)
{
 a[i>>shift] &=~(1<<(i&maskl));
}
int test(int i)
{
 return a[i>>shift] &(1<<(i&maskl));
}
int main()
{
 int num[] = {1,2,3,5,6,4,7,8,9};
 cout<<a[0]<<"   a[0]"<<endl;
 for (int i=0;i<9;i++)
 {
  setB(num[i]);
  cout<<num[i]<<endl;
  cout<<a[0]<<"   a[0]"<<endl;
 }
 for (int i=0;i<9;i++)
 {
  if (test(num[i]))
  {
   cout<<num[i]<<" is set"<<endl;
  }
  else
  {
   cout<<num[i]<<"is not set"<<endl;
   cout<<a[0]<<endl;
  }
 }
 system("pause");
}

【拓展】如何输出一个数的二进制表示

#include <iostream>
using namespace std; 
int main()
{
    int n;
    cout << "input n:";
    cin >> n;
    for(int i=1; i<=32; i++)
    {
       cout << (n<0?1:0); //如果首位为1则为负数 所以小于0 
       n = n<<1;//左移一位
    }
    
    cout << endl;
   
   return 0;
}

利用库函数

#include <stdio.h> 
#include <stdlib.h> 

int   main() 
{ 
        int   i   =   31; 
        char   s[10]; 
  
        itoa(i,   s,   2);     //转换成字符串，进制基数为2 
        printf( "%s ",s);     //输出 

}

用法：char *itoa(int value, char *string, int radix);

　int value 被转换的整数，char *string 转换后储存的字符数组，int radix 转换进制数，如2,8,10,16 进制等

功能：把一整数转换为字符串。

【另一个】atoi （array to integer） ：把字符串转化为整数

int atoi(const char *nptr);

用法：char *str = "12345.67";

　　 n = atoi(str); //输出12345



6）箱（类似散列表）

思路：每一个箱表示一定范围的整数，并用链表链接起来。链表插入采用有序插入，见：3）链表

class IntSetBins {
private:
	int	n, bins, maxval;
	struct node {
		int val;
		node *next;
		node(int v, node *p) { val = v; next = p; }
	};
	node **bin, *sentinel;
	node *rinsert(node *p, int t)//递归  插入结点到合适地方
	{	if (p->val < t) {
			p->next = rinsert(p->next, t);
		} else if (p->val > t) {
			p = new node(t, p);
			n++;
		}
		return p;
	}
public:
	IntSetBins(int maxelements, int pmaxval)
	{	bins = maxelements;
		maxval = pmaxval;
		bin = new node*[bins];
		sentinel = new node(maxval, 0);
		for (int i = 0; i < bins; i++)
			bin[i] = sentinel;
		n = 0;
	}
	int size() { return n; }
	void insert(int t)
	{	int i = t / (1 + maxval/bins);  // CHECK !  映射到某个箱子中
		bin[i] = rinsert(bin[i], t);
	}
	void report(int *v)
	{	int j = 0;
		for (int i = 0; i < bins; i++)
			for (node *p = bin[i]; p != sentinel; p = p->next)
				v[j++] = p->val;
	}
};


二，习题

1）12章的代码

void getSet(int m,int n)//在0 -- n-1 中挑选m个 随机数 
{
    srand(time(NULL));//这个很关键 
    set<int> S;
    for(int i=n-m;i<n;++i)
    {
        int t=rand()%(i+1);
        if(S.find(t) == S.end())
                S.insert(t);
        else
                S.insert(i);
    } 
    set<int>::iterator j;
    for(j=S.begin();
         j!=S.end();++j)
    cout<<*j<<" "; 
}
感觉最关键是要想到，i从n-m开始，如果在i之前找到无重复的数，则insert。否则insert( i )

其实用IntSetSTL 类实现差不多。

2）更改的更健壮，添加错误检查（插入数据是否在范围内，集合是否插满），析构函数（不解释）


3）find( t ) //对于有序集合来说，采用二分查找很合适


4）链表的迭代版本（见上文）核心插入代码如下

void insert(int t)
{	node **p;
	for (p = &head; (*p)->val < t; p = &((*p)->next))
			;
	if ((*p)->val == t)
		return;
	freenode->val = t; //将t插入到第一个大于t的元素的前面
	freenode->next = *p;
	*p = freenode++;
	n++;
}

5）为了避免每次都创造结点（新建一个结点，调用一次存储分配）。

可以一次申请一个结点数组 freenode =new node[maxelements];

用的时候，node p =freenode++; //保证freenode 总是指向当前可用空间


7）感觉答案有些疑惑。哨兵为当前值，放到每个null结点。然后用**p 查找插入位置。这里是不是没有考虑重复插入的问题？？

9）将除法操作变为右移操作，乘法操作变为左移操作。注意 >> << 移位操作符都是二进制移位

除以 4 相当于 >>2 除以8 相当于 >>3 那么除以 6呢？？










分享到：
| SElinux以及防火墙的关闭
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    编程珠玑源码下载编程珠玑书后源代码

    编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码

    编程珠玑 编程珠玑 编程珠玑 编程

    我觉得不错，和大家分享！ 编程珠玑 编程珠玑 编程珠玑

    编程珠玑编程珠玑

    编程珠玑编程珠玑

    编程珠玑 编程珠玑续

    编程珠玑和编程珠玑续两本，上传赚点分，填充填充填充

    编程珠玑之第二章questionC 测试数据

    本资源只是“编程珠玑之第二章questionC: 求变位词问题”的简单的测试数据。

    编程珠玑（续）

    《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇，讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例，这些内容组成一个有机的整体，...

    编程珠玑续本

    编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本

    编程珠玑II（编程珠玑·续） 扫描版6.56M pdf格式

    编程珠玑II（编程珠玑·续） 扫描版6.56M pdf格式

    编程珠玑及其源码

    编程珠玑，编程珠玑续以及源码，本书针对程序设计人员探讨了一系列的实际问题，这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码，但始终非常富有洞察力和创造力地围绕着这些折磨...

    编程珠玑总结笔记

    编程珠玑是一本提升coding能力不可多得的好书，看书时，可以结合这个笔记，突出重点。

    编程珠玑+续

    编程珠玑+续

    编程珠玑 第二版 修订版

    第13章　搜索 127 13.1　接口 127 13.2　线性结构 129 13.3　二分搜索树 132 13.4　用于整数的结构 134 13.5　原理 135 13.6　习题 136 13.7　深入阅读 137 13.8　一个实际搜索问题（边栏） 137 第14章　堆 141 14.1...

    《编程珠玑》源代码

    《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一，在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell，《代码...

    编程珠玑习题集锦

    书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员实际编程...《编程珠玑(第2版)》是计算机科学方面的经典名著。

    编程珠玑高清pdf

    这本书是《编程珠玑》高清pdf，如有侵权请告知。

    编程珠玑.pdf

    第13章 绝妙的取样 123 13.1 取样算法一瞥 123 13.2 Floyd算法 124 13.3 随机排列 125 13.4 原理 127 13.5 习题 127 13.6 深入阅读 128 第14章 编写数值计算程序 129 14.1 问题 129 14.2 牛顿迭代 130 14.3 良好的...

    编程珠玑（第二版）答案

    编程珠玑（第二版）答案

    《编程珠玑》读书笔记

    《编程珠玑》读书笔记

Magicbox
Global site tag (gtag.js) - Google Analytics