有序双向链表的实现。

使用头节点和尾节点来管理链表，遍历，删除，修改都比较容易。

struct room
{
	int price;
	int mID;

	int type;
	int region;

	int listIdx;
};

struct roomList
{
	int idx;
	int next;
	int prev;
	int tc_id;
};


room g_room[1000];
int g_roomIdx;

int g_tcId;

roomList g_roomListBuf[1000 + 200 + 1];
int g_roomListBufIdx;

int g_roomHeadList[10][10];
int g_roomTailList[10][10];


void init()
{
	g_roomListBufIdx = 1;

	for (int i = 0; i < 10; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			int p = g_roomHeadList[i][j] = g_roomListBufIdx++;
			int q = g_roomTailList[i][j] = g_roomListBufIdx++;

			g_roomListBuf[p].next = q;
			g_roomListBuf[q].prev = p;

			g_roomListBuf[p].prev = g_roomListBuf[q].next = 0;
		}
	}

	++g_tcId;
	
}


void addRoom(int mID, int type, int region, int price)
{
	//int i = g_roomIdx++;

	g_room[mID].mID = mID;
	g_room[mID].price = price;
	g_room[mID].type = type;
	g_room[mID].region = region;

	int j = g_roomListBufIdx++;

	g_room[mID].listIdx = j;


	g_roomListBuf[j].idx = mID;
	g_roomListBuf[j].next = g_roomListBuf[j].prev = 0;
	//g_roomListBuf[j].tc_id = g_tcId;



	int k =  g_roomHeadList[type][region];
	int iter = g_roomListBuf[k].next;
	int tail = g_roomTailList[type][region];

	while ( iter!= tail  && g_room[g_roomListBuf[iter].idx].price < price)
	{
		iter = g_roomListBuf[iter].next;
	}

	int prev = g_roomListBuf[iter].prev;
	
	g_roomListBuf[prev].next = j;
	g_roomListBuf[j].prev = prev;

	g_roomListBuf[j].next = iter;
	g_roomListBuf[iter].prev = j;

}


void modifyPrice(int mID, int price)
{

	int oldPrice = g_room[mID].price;

	g_room[mID].price = price;

	int listIdx = g_room[mID].listIdx;

	int prev = g_roomListBuf[listIdx].prev;
	int next = g_roomListBuf[listIdx].next;

	g_roomListBuf[prev].next = next;
	g_roomListBuf[next].prev = prev;

	int type = g_room[mID].type;
	int region = g_room[mID].region;


	if (oldPrice < price)
	{
		int  iter = next;
		int tail = g_roomTailList[type][region];

		while (iter != tail && g_room[g_roomListBuf[iter].idx].price < price)
		{
			iter = g_roomListBuf[iter].next;
		}

		
		prev = g_roomListBuf[iter].prev;
		g_roomListBuf[prev].next = listIdx;
		g_roomListBuf[listIdx].prev = prev;

		g_roomListBuf[iter].prev = listIdx;
		g_roomListBuf[listIdx].next = iter;
		
	}
	else
	{
		int iter = prev;

		int head = g_roomHeadList[type][region];
		while (iter != head && g_room[g_roomListBuf[iter].idx].price > price)
		{
			iter = g_roomListBuf[iter].prev;
		}

		next = g_roomListBuf[iter].next;
		g_roomListBuf[next].prev = listIdx;

		g_roomListBuf[listIdx].next = next;

		g_roomListBuf[iter].next = listIdx;
		g_roomListBuf[listIdx].prev = iter;
	}
}

测试代码：

void printRoom(int type, int region)
{
	int idx = g_roomHeadList[type][region];
	int iter = g_roomListBuf[idx].next;
	int head = g_roomTailList[type][region];

	while (iter != head)
	{
		int roomIdx = g_roomListBuf[iter].idx;
		std::cout << "room " << g_room[roomIdx].mID << " price " << g_room[roomIdx].price << std::endl;
		iter = g_roomListBuf[iter].next;
	}
}


int main(void)
{
	init();

	addRoom(100, 1, 0, 1560);
	addRoom(90, 1, 0, 980);
	addRoom(10, 1, 0, 8700);
	addRoom(9, 1, 0, 3290);
	addRoom(1, 1, 0, 2200);
	addRoom(2, 1, 0, 4400);

	printRoom(1, 0);
	modifyPrice(9, 7500);

	std::cout << "*********************************************" << std::endl;
	
	printRoom(1, 0);

	return 0;

}

运行结果：

room 90 price 980
room 100 price 1560
room 1 price 2200
room 9 price 3290
room 2 price 4400
room 10 price 8700
*********************************************
room 90 price 980
room 100 price 1560
room 1 price 2200
room 2 price 4400
room 9 price 7500
room 10 price 8700