《链表的分块查找-原理及C++示例代码》由会员分享，可在线阅读，更多相关《链表的分块查找-原理及C++示例代码（6页珍藏版）》请在金锄头文库上搜索。
1、一个快两年没有联系的高中同学突然跟我发消息要我帮忙写个算法设计的作业，其 实本来不是很闲，只是觉得自己很久没有认真的写过专业课的作业了，就答应了，顺便温习 一下链表.事实上我学的不是很好吧。晚上就不会寝室睡觉了，呆在实验室就来看题目。要求是用分块查找法找到创建的链表的某个数据。分块查找？好像我们老师没讲 啊！无奈百度一圈下来，看得不是很明白，也不是完全不明白。最后理解为，给链表分块 当然可以为不等大小的，这里我就用等大小的来直接处理，这样就可以从控制台直接输入块 的大小来查找。其次，还要输入被查找的块。如果这个数在此块以外，就无法找到。最后 把找到的数字的节点数输出来。首先看看原理图，这个是在
2、网上看的，不过原图有点不准确，用fireworks(不要鄙视我古董，我依然喜欢它)处理了下贴上来。分块查找的思路是：1、首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块这里我定义了一个我认为比较雷人的数组用于存放节点的地址。 #define N 30int *addN;每次添加数据时，分配的地址会被保存到这里。add+i=(struct Node *)p1;然后数组的下表自增移动。2、然后在已确定的块中进行顺序查找 由于块内无序，只能顺序查找。for(i=block * BLK ; i(block+1)* BLK & addi!=0 ;i+)这个范围就是由块得大
3、小和第几个来确定的，当然，不能超过范围，这里用的addi!=O 来作条件，因为add数组是在全局定义的，编译时全部初始化为零，自然，越界的就是零 了。这里注意，虽然数组存的值是地址，但是不能直接用，需要转化为结构体的地址才行struct Node *t;t=addi;f(t-id=key) printf (找到第d 个数是%dn,i,key);OK,我的思路大概就是这样，不知道是不是和标准的分块查找算法一样啊。贴出代码为鉴。/*blksearch.c*/#includestdio.h#includestdlib.h #includemalloc.h #includeid);p1-next =
4、NULL; while(p1-id 0) add+i=(struct Node *)p1;if(head = NULL) head = p1;elsep2-next = p1;p2 = p1;p1=(struct Node *)malloc(sizeof(struct Node); if(p1 = NULL | p2 =NULL)prin tf(内存分配失败n); exit(0); scanf(%d,&p1-id);p1-next = NULL;prin tf(链表创建成功n);return head; /*显示链表*/void display(struct Node *pHead) int
5、i=0; if(NULL = pHead)prin tf(链表为空n); elsewhile( pHead != NULL)printf(%d,pHead-id);printf(地址：%d,add+i);pHead = pHead-next;printf(n);/*求链表长度*/int sizeList(struct Node *pHead)int size = 0;while(pHead != NULL)size+;pHead = pHead-next;prin tf(链表长度 %d n,size);return size;/*分块查找链表*/void BlkSearch(struct No
6、de *pHead,int key,int block,int BLK)int i;struct Node *t; if(NULL = pHead)prin tf(链表为空n);else for(i=block * BLK ; i(block+1)* BLK & addi!=0 ;i+) t=addi;f(t-id=key) printf(找到第d 个数是%dn,i,key); return 0;printf(n);prin tf(查找结束n);int main()int len;int key,block,blk;struct Node *mylist=NULL;struct Node *p
7、;puts(输入数字开始创建链表，以小于零的数结束创建：“)； p=creat(mylist);len=sizeList(p);add0=(int *)p;display(p);puts(输入需要查找的数字：)； scanf(%d,&key);puts(输入块的大小：)； scanf(%d,&blk);puts(输入需要查找的块：)； scanf(%d,&block);BlkSearch(p,key,block,blk);return 0;/*blksearch.cend*/ 以下为在VC6.0下测试通过的截图。貂地址矽地址34=地址11地址22地址31地址朋地址伯地址期地址 i能地址33741923583056358328056S2SSS36S311236833363674136S6S3OOO3683224968344836 -11436740S036829443683168368339269 22 85 4G 34 31 59E Z Debug： 1 iTiki i st_ exe 输入数専开始创建链 25 39 S7 11 4S 79 链表创建咸功 琏表长度 药地址： 葩姬址： 25地址： 帘9地址： 轎入需要查找的数字；73 输?l块的犬小】3 输入需妾查找的块：找到第石午数是旳Pr&ss any key to continue
