An implementation of an ordered doubly linked list.

Use the head node and tail node to manage the linked list, it is easier to traverse, delete, and modify.

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;}}

Test code:

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;}

Run result:

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