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

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。

相关文章

零基础STM32单片机编程入门(一)初识STM32单片机

零基础STM32单片机编程入门(一)初识STM32单片机

文章目录 一.概要二.单片机型号命名规则三.STM32F103系统架构四.STM32F103C8T6单片机启动流程五.STM32F103C8T6单片机主要外设资源六.编程过程中芯片数据手册的作用1.单片机外设资源情况2.STM32单片机内部框图3.STM32单片机管脚图4.STM32单片机每个管脚可配功能5.单片机功耗数据6.FALSH编程时间，擦写次数7.I/O高低电平电压表格8.外设接口
阅读更多...
16.Spring前世今生与Spring编程思想

16.Spring前世今生与Spring编程思想

1.1.课程目标 1、通过对本章内容的学习,可以掌握Spring的基本架构及各子模块之间的依赖关系。 2、 了解Spring的发展历史，启发思维。 3、 对 Spring形成一个整体的认识，为之后的深入学习做铺垫。 4、 通过对本章内容的学习，可以了解Spring版本升级的规律，从而应用到自己的系统升级版本命名。 5、Spring编程思想总结。 1.2.内容定位 Spring使用经验
阅读更多...
BD错误集锦4——IDEA编程连接hbase失败，put操作一直没有通过，并且无异常信息

BD错误集锦4——IDEA编程连接hbase失败，put操作一直没有通过，并且无异常信息

参考文章：https://blog.csdn.net/ZJ18712852367/article/details/81938524
阅读更多...
【文末附gpt升级秘笈】腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑

【文末附gpt升级秘笈】腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑

腾讯元宝AI搜索解析能力升级：千万字超长文处理的新里程碑 一、引言 随着人工智能技术的飞速发展，自然语言处理（NLP）和机器学习（ML）在各行各业的应用日益广泛。其中，AI搜索解析能力作为信息检索和知识抽取的核心技术，受到了广泛的关注和研究。腾讯作为互联网行业的领军企业，其在AI领域的探索和创新一直走在前列。近日，腾讯旗下的AI大模型应用——腾讯元宝，迎来了1.1.7版本的升级，新版本在AI搜
阅读更多...
IPython小白教程：提升你的Python交互式编程技巧，通俗易懂！

IPython小白教程：提升你的Python交互式编程技巧，通俗易懂！

IPython是一个增强的Python交互式shell，它提供了丰富的功能和便捷的交互方式，使得Python开发和数据分析工作更加高效。本文将详细介绍IPython的基本概念、使用方法、主要作用以及注意事项。 一、IPython简介 1. IPython的起源 IPython由Fernando Pérez于2001年创建，旨在提供一个更高效的Python交互式编程环境。 2. IPyt
阅读更多...
从《深入设计模式》一书中学到的编程智慧

从《深入设计模式》一书中学到的编程智慧

软件设计原则   优秀设计的特征   在开始学习实际的模式前，让我们来看看软件架构的设计过程，了解一下需要达成目标与需要尽量避免的陷阱。 代码复用 无论是开发何种软件产品，成本和时间都最重要的两个维度。较短的开发时间意味着可比竞争对手更早进入市场; 较低的开发成本意味着能够留出更多营销资金，因此能更广泛地覆盖潜在客户。 代码复用是减少开发成本时最常用的方式之一。其意图
阅读更多...
Java并发编程—阻塞队列源码分析

Java并发编程—阻塞队列源码分析

在前面几篇文章中，我们讨论了同步容器(Hashtable、Vector），也讨论了并发容器（ConcurrentHashMap、CopyOnWriteArrayList），这些工具都为我们编写多线程程序提供了很大的方便。今天我们来讨论另外一类容器：阻塞队列。 　　在前面我们接触的队列都是非阻塞队列，比如PriorityQueue、LinkedList（LinkedList是双向链表，它实现了D
阅读更多...
剑指offer—编程题7（用两个栈实现一个队列）

剑指offer—编程题7（用两个栈实现一个队列）

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。 代码如下： [java]  view plain copy print ? public class Test07 {       /**       * 用两个栈模拟的队列       *
阅读更多...
剑指Offer—编程题4 （ 替换空格）

剑指Offer—编程题4 （ 替换空格）

一、题目：替换空格 题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。　 　　在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。
阅读更多...
剑指Offer—编程题56（链表中环的入口地址）

剑指Offer—编程题56（链表中环的入口地址）

题目：一个链表中包含环，如何找出环的入口结点？ 解题思路 　　可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中环有n个结点，指针P1在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。  　　剩下的问题就是如何得到环中结点的数目。我们在面试题15的第二个相关题目时用到
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2