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

2024-04-05 01:48
文章标签 搜索 编程 第十三章 珠玑

本文主要是介绍【编程珠玑】第十三章 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一，概述

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

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

        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呢？？ 

  


      







这篇关于【编程珠玑】第十三章 搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/877363。

相关文章

C#反射编程之GetConstructor()方法解读

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
Linux 网络编程 --- 应用层

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码： 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口，https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

Java的垃圾收集（Garbage Collection，GC）机制是Java语言的一大特色，它负责自动管理内存的回收，释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍： 一、垃圾收集机制概述： 对象存活判断：垃圾收集器定期检查堆内存中的对象，判断哪些对象是“垃圾”，即不再被任何引用链直接或间接引用的对象。内存回收：将判断为垃圾的对象占用的内存进行回收，以便重新使用。
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2