订阅号可以做网站吗,网站建设介绍ppt,wordpress 图片裁切,seo长尾关键词C 数据结构算法 学习笔记(33) -查找算法及企业级应用
数组和索引
日常生活中#xff0c;我们经常会在电话号码簿中查阅“某人”的电话号码#xff0c;按姓查询或者按字母排 序查询#xff1b;在字典中查阅“某个词”的读音和含义等等。在这里#xff0c;“电话号码簿”和…C 数据结构算法 学习笔记(33) -查找算法及企业级应用
数组和索引
日常生活中我们经常会在电话号码簿中查阅“某人”的电话号码按姓查询或者按字母排 序查询在字典中查阅“某个词”的读音和含义等等。在这里“电话号码簿”和“字典”都可 看作一张查找表而按“姓”或者“字母”查询则是按索引查询 索引把线性表分成若干块每一块中的元素存储顺序是任意的但是块与块间必须按关键字 大小按顺序排列。即前一块中的最大关键字值小于后一块中的最小关键字值。 分块以后为了快速定义块还需要建立一个索引表索引表中的一项对应于线性表中的一 块索引项由键域和链域组成。键域存放相应关键字的键值链域存放指向本块第一个节点和最 后一个节点的指针索引表按关键字由小到大的顺序排列
数组是特殊的块索引一个块一个元素 哈希表是非常经典的块索引! 分块查找的算法分两步进行首先确定所查找的节点属于哪一块即在索引表中查找其所在的块 然后在块内查找待查询的数据。由于索引表是递增有序的可采用二分查找而块内元素是无序 的只能采用顺序查找。块内元素较少则不会对执行速度有太大的影响
二分查找
二分查找法实质上是不断地将有序数据集进行对半分割并检查每个分区的中间元素。再重 复根据中间数确定目标范围并递归实行对半分割直到中间数等于待查找的值或是目标数不在搜 索范围之内
#include iostream
#include stringusing namespace std;int int_compare(const void* key1, const void* key2)
{const int* ch1 (const int*) key1;const int* ch2 (const int*) key2;return (*ch1 - *ch2);
}int char_compare(const void* key1, const void* key2)
{const char* ch1 (const char*)key1;const char* ch2 (const char*)key2;return (*ch1 - *ch2);
}int BinarySearch(void* sorted, int len, int elemSize, void* search, int (*compare)(const void *key1, const void *key2))
{int left 0; int right 0;int middle 0;left 0;right len - 1;while (left right){int ret 0;middle (left right) / 2;ret compare(static_castchar *(sorted)(elemSize*middle), search);if (ret 0){return middle;}else if (ret 0){right middle - 1;}else{left middle 1;}}return -1;
}int main()
{ int arr[] { 1,3,7,9,11 };int search[] {0,1,7,2,11,12};for (int i 0; i sizeof(search) / sizeof(search[0]); i){int index BinarySearch(arr, sizeof(arr) / sizeof(arr[0]),sizeof(int), search[i], int_compare);cout The result is: index endl;}char arr1[] { a,c,d,f,j };char search1[] {0,a,e,j,z};cout endl;cout Char searching... endl;for (int i 0; i sizeof(search1) / sizeof(search1[0]); i){int index BinarySearch(arr1, sizeof(arr1) / sizeof(arr1[0]),sizeof(char), search1[i], char_compare);cout The result is: index endl;}system(pause);return 0;
}穷举搜索
有20枚硬币可能包括4种类型1元、5角、1角和5分。
已知20枚硬币的总价值为10元求各种硬币的数量。 例如4、11、5、0就是一种方案。
而8、2、10、0是另一个可能的方案显然方案并不是 唯一的请编写程序求出类似这样的不同的方案一共有多少种
1编程思路。 直接对四种类型的硬币的个数进行穷举。其中1元最多10枚、5角最多20枚、1角最多 20枚、5分最多20枚。
如果以元为单位则5角、1角、5分会化成浮点型数据容易计算出错。可以将1 元、5角、1角、5分变成100分、50分、10分和5分从而全部采用整型数据处理。
#include iostream
#include stringusing namespace std;int main()
{int a100 0; //one dollar coinint a50 0;int a10 0;int a5 0;int cnt 0;for (a100 0; a100 10; a100){for (a50 0; a50 (1000-a100*100)/50; a50){for (a10 0; a10 (1000-a100*100-a50*50)/10; a10){for (a5 0; a5 (1000 - a100 * 100 - a50 * 50 - a10*10) / 5; a5){if ((a100 * 100 a50 * 50 a10 * 10 a5 * 5) 1000 (a100 a50 a10 a5) 20){cout a100 , a50 , a10 , a5 , endl;cnt;}}}}}cout The total method to have the $10 dollar with 20 coin is: cnt endl;system(pause);return 0;
}穷举法枚举法的基本思想是列举出所有可能的情况逐个判断有哪些是符合问题所要求 的条件从而得到问题的全部解答。 它利用计算机运算速度快、精确度高的特点对要解决问题的所有可能情况一个不漏地进行检 查从中找出符合要求的答案。
用穷举算法解决问题通常可以从两个方面进行分析
1问题所涉及的情况问题所涉及的情况有哪些情况的种数必须可以确定。把它描述 出来。应用穷举时对问题所涉及的有限种情形必须一一列举既不能重复也不能遗漏。重复列 举直接引发增解影响解的准确性而列举的遗漏可能导致问题解的遗漏。
2答案需要满足的条件分析出来的这些情况需要满足什么条件才成为问题的答案。 把这些条件描述出来。
并行搜索
并发的基本概念
所谓并发是在同一实体上的多个事件同时发生。并发编程是指在在同一台计算机上“同时” 处理多个任务。 要理解并发编程我们必须要理解如下一些基本概念 计算机就像一座工厂时刻在运行为人类服务。它的核心是CPU它承担了所有的计算任 务就像工厂的一个现场指挥官。 进程就像工厂里的车间承担“工厂”里的各项具体的“生产任务”通常每个进程对应一 个在运行中的执行程序比如QQ和微信运行的时候他们分别是不同的进程。
因为特殊原因现场指挥官人才短缺整个工厂只有一个指挥官一次只能指导一个车间生 产而所有的车间都必须要有现场指挥官在场才能生产。也就是说一个车间开工的时候 其他车间都必须停工。
背后的含义任一时刻单个CPU一次只能运行一个进程此时其他进程处于非运行状态。 一个车间进程可以包括多条生产线线程就好比车间进程里的生产线。所有生产线 设备和人都属于同一车间的资源受车间统一调度和调配并共享车间所有资源如空 间或洗手间。
背后的含义一个进程可以拥有多个线程每个线程可以可以独立并行执行多个线程共 享同一进程的资源受进程管理。 理解了以上这些概念后我们接下来再继续讲解并行搜索的概念: 假设我们要从很大的一个无序的数据集中进行搜索
假设我们的机器可以一次性容纳这么多 数据。从理论上讲对于无序数据如果不考虑排序已经很难从算法层面优化了。而利用 上面我们提到的并行处理思想我们可以很轻松地将检索效率提升多倍。具体实现思路如下: 将数据分成N个块每个块由一个线程来并行搜索。
#include iostream
#include string
#include Windows.h
#include time.husing namespace std;#define TEST_SIZE (1024*1024*200)
#define NUMBER 20typedef struct _search
{int* data;size_t start;size_t end;size_t count;
}search;//int main1()
//{
// int* data NULL;
// int count 0;
//
// data new int[TEST_SIZE];
//
// for (int i 0; i TEST_SIZE; i)
// {
// data[i] i;
// }
//
// time_t start 0, end 0;
// time(start);
//
// for (int j 0; j 10; j)
// {
// for (int i 0; i TEST_SIZE; i)
// {
// if (data[i] NUMBER)
// {
// count;
// }
// }
// }
//
// time(end);
// cout The time used for the search function is: end - start endl;
// system(pause);
// return 0;
//}DWORD WINAPI ThreadProc(void* lpParam)
{search* s (search*)lpParam;time_t start, end;cout The new thread is executing... endl;time(start);for (int j 0; j 10; j){for (size_t i s-start; i s-end; i){if (s-data[i] NUMBER){s-count;}}}time(end);cout The required time to searching the data is: end - start endl;return 0;
}int main()
{int* data NULL;int count 0;int mid 0;search s1, s2;data new int[TEST_SIZE];for (int i 0; i TEST_SIZE; i){data[i] i;}mid TEST_SIZE / 2;s1.data data;s1.start 0;s1.end mid;s1.count 0;s2.data data;s2.start mid 1;s2.end TEST_SIZE -1;s2.count 0;DWORD threadID1; //Thread 1 identityHANDLE hThread1; //Thread 1 handleDWORD threadID2; //Thread 2 identityHANDLE hThread2; //Thread 2 handlecout Creating the threads... endl;hThread1 CreateThread(NULL, 0, ThreadProc, s1, 0, threadID1); //Creating first threadhThread2 CreateThread(NULL, 0, ThreadProc, s2, 0, threadID2); // Creating second threadWaitForSingleObject(hThread1, INFINITE);WaitForSingleObject(hThread2, INFINITE);cout The process is waiting the thread to return... endl;cout The total count for the search value is: s1.count s2.count endl;system(pause);return 0;
}
文章转载自： http://www.morning.dlhxj.cn.gov.cn.dlhxj.cn http://www.morning.sqnrz.cn.gov.cn.sqnrz.cn http://www.morning.ctlzf.cn.gov.cn.ctlzf.cn http://www.morning.qbfs.cn.gov.cn.qbfs.cn http://www.morning.nwnbq.cn.gov.cn.nwnbq.cn http://www.morning.kpgft.cn.gov.cn.kpgft.cn http://www.morning.mcqhb.cn.gov.cn.mcqhb.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.yldgw.cn.gov.cn.yldgw.cn http://www.morning.inheatherskitchen.com.gov.cn.inheatherskitchen.com http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.ppbqz.cn.gov.cn.ppbqz.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.trzzm.cn.gov.cn.trzzm.cn http://www.morning.rwmft.cn.gov.cn.rwmft.cn http://www.morning.ttcmdsg.cn.gov.cn.ttcmdsg.cn http://www.morning.kryn.cn.gov.cn.kryn.cn http://www.morning.wckrl.cn.gov.cn.wckrl.cn http://www.morning.psxfg.cn.gov.cn.psxfg.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.ldnrf.cn.gov.cn.ldnrf.cn http://www.morning.qztdz.cn.gov.cn.qztdz.cn http://www.morning.zfkxj.cn.gov.cn.zfkxj.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.jczjf.cn.gov.cn.jczjf.cn http://www.morning.kkdbz.cn.gov.cn.kkdbz.cn http://www.morning.ntgrn.cn.gov.cn.ntgrn.cn http://www.morning.yktr.cn.gov.cn.yktr.cn http://www.morning.dhyqg.cn.gov.cn.dhyqg.cn http://www.morning.zlnmm.cn.gov.cn.zlnmm.cn http://www.morning.pswqx.cn.gov.cn.pswqx.cn http://www.morning.flpjy.cn.gov.cn.flpjy.cn http://www.morning.fqssx.cn.gov.cn.fqssx.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn http://www.morning.srrzb.cn.gov.cn.srrzb.cn http://www.morning.nytpt.cn.gov.cn.nytpt.cn http://www.morning.qphdp.cn.gov.cn.qphdp.cn http://www.morning.qbwbs.cn.gov.cn.qbwbs.cn http://www.morning.lqznq.cn.gov.cn.lqznq.cn http://www.morning.pplxd.cn.gov.cn.pplxd.cn http://www.morning.xhjjs.cn.gov.cn.xhjjs.cn http://www.morning.sqqds.cn.gov.cn.sqqds.cn http://www.morning.zzgkk.cn.gov.cn.zzgkk.cn http://www.morning.trnl.cn.gov.cn.trnl.cn http://www.morning.ynrzf.cn.gov.cn.ynrzf.cn http://www.morning.wfbnp.cn.gov.cn.wfbnp.cn http://www.morning.c7624.cn.gov.cn.c7624.cn http://www.morning.zrwlz.cn.gov.cn.zrwlz.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.ktxd.cn.gov.cn.ktxd.cn http://www.morning.rbhcx.cn.gov.cn.rbhcx.cn http://www.morning.tbjtm.cn.gov.cn.tbjtm.cn http://www.morning.kwxr.cn.gov.cn.kwxr.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.jzykw.cn.gov.cn.jzykw.cn http://www.morning.kjdxh.cn.gov.cn.kjdxh.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.rxnxl.cn.gov.cn.rxnxl.cn http://www.morning.yhsrp.cn.gov.cn.yhsrp.cn http://www.morning.zczkm.cn.gov.cn.zczkm.cn http://www.morning.hxxzp.cn.gov.cn.hxxzp.cn http://www.morning.kdlzz.cn.gov.cn.kdlzz.cn http://www.morning.gypcr.cn.gov.cn.gypcr.cn http://www.morning.qcfgd.cn.gov.cn.qcfgd.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.pfntr.cn.gov.cn.pfntr.cn http://www.morning.rykgh.cn.gov.cn.rykgh.cn http://www.morning.rmfh.cn.gov.cn.rmfh.cn http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.bbgr.cn.gov.cn.bbgr.cn http://www.morning.dhrbj.cn.gov.cn.dhrbj.cn http://www.morning.rcjqgy.com.gov.cn.rcjqgy.com http://www.morning.gwsll.cn.gov.cn.gwsll.cn http://www.morning.qbnfc.cn.gov.cn.qbnfc.cn http://www.morning.pwdrc.cn.gov.cn.pwdrc.cn
