数组可以O(1)查询元素,但需要O(n)才能插入元素
链表可以O(1)插入元素,但需要O(n)才能查询元素
那么是否能让查询和插入的时间复杂度都变为根号n-块状链表(分块数据结构)
假设数据又n个,则建立根号n个头节点(用链表连接),每个节点下有一个根号n长度的数组,这样查询第x个元素只用在链表部分(头节点)跳转至多根号n次后进入数组,在数组中O(1)查询,插入元素只用在头节点跳转根号n次在用根号n的时间在数组中插入元素
注释:把一个块插入到2倍的根号n大小的时候要分成两个块,保证时间复杂度,同理如果相邻两个块大小都太小则合并
const int m=350;//m在根号n大小左右 struct data{ int s,a[2*m+5]; data *next; }; data *root; void insert(int x,int pos){ if(root==NULL){ root=new(data); root->s=1; root->a[1]=x; return; } data *k=root; while(pos>k->s&&k->next!=NULL){ pos-=k->s; k=k->next; } memmove(k->a+pos+1,k->a+pos,sizeof(int)*(k->s-pos+1)); k->s++; k->a[pos]=x; if(k->s==2*m){ data *t=new(data); t->next=k->next; k->next=t; memcpy(t->a+1,k->a+m+1,sizeof(int)*m); t->s=k->s=m; } } void del(int pos){ data *k=root; while(pos>k->s&&k->next!=NULL){ pos-=k->s; k=k->next; } memmove(k->a+pos,k->a+pos+1,sizeof(int)*(k->s-pos)); k->s--; } int find(int pos){ data *k=root; while(pos>k->s&&k->next!=NULL){ pos-=k->s; k=k->next; } return(k->a[pos]); } void destroy(data *k){ if(k->next!=NULL){ destroy(k->next); } delete(k); }