用map和連結清單實作大量資料的有序的插入和查找

 對于大量資料的插入和查找，我們應該如何選擇資料結構呢？

思路：

我們知道連結清單插入快，但是查找慢，map查找快，但是無序，想要有序的查找和插入，那就把兩者結合起來使用。

連結清單：手寫一些函數對連結清單進行基本的插入和删除，每次插入完成後需要更新map。

map:  map用來儲存每個插入點的指針，用map查找插入點的指針，然後直接插入。map的各種操作的時間複雜度都是O（lgN）。

插入函數：

struct Node* inserter(struct Node *p,int key,int i) //把key插入到的前面 ,0插入到p的前，1後 
{
	struct Node *now;
	now=(struct Node*)malloc(sizeof(struct Node));
	now->data=key;
	if(i==0) //插入到前面 
	{
		now->prime=p->prime;
		p->prime->next=now;
		now->next=p;
		p->prime=now;
		return now;
	}
	else
	{
		now->prime=p;
		now->next=p->next;
		if(p->next!=NULL)
			p->next->prime=now;
		p->next=now;
		return now;
	}
    //傳回的now指針用來更新map
}
           

 傳回的now指針用來更新map

map:

#include<map>  //記得加頭檔案

map<int,struct Node*> m;
struct Node *head,*now,*next;
	head=(struct Node*)malloc(sizeof(struct Node));
	head->prime=NULL;
	head->data=-1;
	now=(struct Node*)malloc(sizeof(struct Node));//第一個 
	head->next=now;
	now->next=NULL;
	now->data=1;
	now->prime=head;
	m[1]=now; //把第一個數的指針儲存
           

題目練習

AC代碼（後面有更好的思路）：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<map> 
#define Max 100010
#define max(a,b) a>b?a:b;
#define min(a,b) a>b?b:a;
using namespace std;
int live[Max]; //記錄是否被删除 
struct Node{
	int data;
	struct Node* next;
	struct Node* prime;
};
struct Node* inserter(struct Node *p,int key,int i) //把key插入到的前面 ,0前，1後 
{
	struct Node *now;
	now=(struct Node*)malloc(sizeof(struct Node));
	now->data=key;
	if(i==0) //插入到前面 
	{
		now->prime=p->prime;
		p->prime->next=now;
		now->next=p;
		p->prime=now;
		return now;
	}
	else
	{
		now->prime=p;
		now->next=p->next;
		if(p->next!=NULL)
			p->next->prime=now;
		p->next=now;
		return now;
	}
}
void show(struct Node *q) //顯示還有表内的人 
{
	struct Node *p=q;
	p=p->next;
	while(p!=NULL) //輸出格式 ，空格 
	{
		if(!live[p->data])
		{
			printf("%d",p->data);  //最後記得調整格式問題
			break;
		}
		p=p->next;
	}
	p=p->next;
	while(p!=NULL)
	{
		if(!live[p->data])
		{
			printf(" %d",p->data);  //最後記得調整格式問題 
		}
		p=p->next;
	}
	printf("\n");
}
int main()
{
	map<int,struct Node*> m;
	struct Node *head,*now,*next;
	head=(struct Node*)malloc(sizeof(struct Node));
	head->prime=NULL;
	head->data=-1;
	now=(struct Node*)malloc(sizeof(struct Node));//第一個 
	head->next=now;
	now->next=NULL;
	now->data=1;
	now->prime=head;
	m[1]=now; //第一個 
	int num,j,n,M;
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&num,&j);
		now=m[num];//要插入的地方 
		m[i]=inserter(now,i,j);
	}
	scanf("%d",&M);
	memset(live,0,sizeof(live));
	for(int i=0;i<M;i++)
	{
		scanf("%d",&num);
		live[num]=1;//需要删除的同學 
	}
	show(head);
	return 0;
}
           

（辛苦的寫完代碼後，發現有些時候可以隻用線性表就能完成快速的查找.....）

當插入的資料類型為整型的時候，我們用如下結構體來儲存資料：

struct Node{
    int data;
    int prime; //指向前面一個數的位置
    int next;  //指向後面一個數的位置
}node[100010];
           

我們可以直接利用節點的資料，達到直接通路下一個節點，每次插入完成後像連結清單一樣調整前面資料就好，查找、插入的時間複雜度都是O(1)。