首页 > 代码库 > 通用块状链表
通用块状链表
在这里写下模板。以后方便用
#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#define max_size 3000using namespace std;const int best_size = max_size - 20;struct node{ int size; int date[max_size]; struct node * next;}block_list;//创建节点 struct node * createnode(){ struct node * temp = (struct node *)malloc(sizeof(struct node)); temp->next = NULL; temp->size = 0; return temp;} //初始化块状数组 //n为块状数组存储的数据总数//block_size为每一块初始存入的数据个数 一般为sqrt(n)//date为数据源 ,从0开始计数 void init(int n, char * date, int block_size){ struct node * temp = &block_list; struct node * temp2 = temp; int i; int k; for(i = 0, k = 0; k < n; i++,k++) { if(i == block_size) { temp2 = temp; temp = temp->next; i = 0; } if(temp!= NULL) { temp->date[i] = date[k]; temp->size ++; } else { temp = createnode(); temp2 ->next = temp; temp->date[i] = date[k]; temp->size ++; } }}//向块状插入数据//pos为插入位置 date为数据bool insertdate(int pos, int date){ struct node * temp = &block_list; struct node * temp2 = temp; int sum = block_list.size; int flag; while(sum<pos) { temp2 = temp; temp = temp->next; if(temp == NULL) { temp2 -> date[temp2 -> size] = date; temp2 ->size ++; return true; } sum += temp->size; } for(flag = temp -> size ; flag >= (temp -> size - (sum - pos)); flag --) { temp -> date[flag] = temp -> date[flag-1]; } temp -> date[flag] = date; temp -> size ++; return true;}//删除位置为pos的数据 bool deletedate(int pos){ struct node * temp = &block_list; int sum = block_list.size; int flag; while(sum<pos) { temp = temp->next; if(temp == NULL) return false; sum += temp->size; } for(flag = temp->size - (sum - pos)-1 ; flag < temp -> size -1; flag ++) { temp -> date[flag] = temp -> date[flag+1]; } temp -> size --; return true;}//分割一个块//参数为这个块的地址 bool splitnode(struct node * aim){ int size = aim -> size; struct node * temp = createnode(); temp -> next = aim -> next; aim -> next = aim; for(int i = best_size, k = 0; i < size; i++, k++) { aim -> date[i] = temp -> date[k]; aim -> size --; temp -> size ++; } return true;}//合并两个节点 //必须为两个相邻的节点!!!! bool combinenode(struct node * aim1, struct node * aim2){ if( aim1 -> size + aim2 -> size > best_size) return false; for(int i = aim1 -> size, j = 0; j < aim2 -> size; j++, i++) { aim1 -> date[i] = aim2 -> date[j]; aim1 -> size ++; } aim1-> next = aim2 ->next; free(aim2); return true;}int selectdate(int pos){ struct node * temp = &block_list; int sum = block_list.size; int flag; while(sum<pos) { temp = temp->next; if(temp == NULL) return false; sum += temp->size; } return temp -> date[temp -> size - (sum - pos)-1]; }/*char test[1000001];int main(){ char t[2]; int num; int pos; char d[2]; scanf("%s",test); int len = strlen(test); init(len,test,sqrt(len)); scanf("%d",&num); for(int i=0;i<num;i++) { scanf("%s",t); if(t[0] == ‘Q‘) { scanf("%d",&pos); printf("%c\n",selectdate(pos)); } else { scanf("%s %d",d,&pos); insertdate(pos,d[0]); } } }*/
去掉注释的代码可以直接A掉2887题目
通用块状链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。