《链表的分块查找》由会员分享，可在线阅读，更多相关《链表的分块查找（6页珍藏版）》请在金锄头文库上搜索。
1、一个快两年没有联系的高中同学突然跟我发消息要我帮忙写个算法设计的作业，其实本 来不是很闲，只是觉得自己很久没有认真的写过专业课的作业了，就答应了，顺便温习一下 链表.事实上我学的不是很好吧。晚上就不会寝室睡觉了，呆在实验室就来看题目。要求是用分块查找法找到创建的链表的某个数据。分块查找？好像我们老师没讲啊！无 奈百度一圈下来，看得不是很明白，也不是完全不明白。最后理解为，给链表分块，当然可 以为不等大小的，这里我就用等大小的来直接处理，这样就可以从控制台直接输入块的大小 来查找。其次，还要输入被查找的块。如果这个数在此块以外，就无法找到。最后，把找到 的数字的节点数输出来。首先看看原理图，这个
2、是在网上看的，不过原图有点不准确，用fireworks（不要鄙视 我古董，我依然喜欢它）处理了下贴上来。2212 L33 92042443824IS58744953Ji111D1. . 3j17addr （地址）228G展丫（关键字）y 10 11 12 U 14 15 16 17 18分块查找的思路是：1、首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块这里我定义了一个我认为比较雷人的数组用于存放节点的地址。 #define N 30int *addN;每次添加数据时，分配的地址会被保存到这里。add+i=（struct Node *）p1;然后数组的下表自增
3、移动。2、然后在已确定的块中进行顺序查找 由于块内无序，只能顺序查找。for(i=block * BLK ; i(block+1)* BLK & addi!=0 ;i+)这个范围就是由块得大小和第几个来确定的，当然，不能超过范围，这里用的addi!=O 来作条件，因为add数组是在全局定义的，编译时全部初始化为零，自然，越界的就是零 了。这里注意，虽然数组存的值是地址，但是不能直接用，需要转化为结构体的地址才行struct Node *t;t=addi;f(t-id=key) printf(找到第宀个数是%dn,i,key);OK,我的思路大概就是这样，不知道是不是和标准的分块查找算法一样啊。
4、贴出代码为鉴。/*blksearch.c*/#includestdio.h#includestdlib.h#includemalloc.h#includeid);p1-next = NULL; while(p1-id 0) add+i=(struct Node *)p1; if(head = NULL) head = p1;else p2-next = p1;p2 = p1;p1=(struct Node *)malloc(sizeof(struct Node); if(p1 = NULL | p2 =NULL)prin tf(内存分配失败n); exit(0); scanf(%d,&p1-i
5、d);p1-next = NULL;prin tf(链表创建成功n);return head; /*显示链表*/void display(struct Node *pHead) int 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
6、+;pHead = pHead-next;prin tf(链表长度 %d n,size);return size;/*分块查找链表*/void BlkSearch(struct Node *pHead,int key,int block,int BLK)int i;struct Node *t;if(NULL = pHead)prin tf(链表为空n);elsefor(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);
7、prin tf(查找结束n);int main()int len;int key,block,blk;struct Node *mylist=NULL;struct Node *p;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 下测试通过的截图。
