Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <string>
- #include <iostream>
- using namespace std;
- struct list{
- string element;
- string key;
- list* next;
- list* prevEl;
- list* nextEl;
- };
- struct LinkedMap{
- list* a[500009];
- list* lastEl;
- LinkedMap(){
- for (int i = 0; i < 500009; i++)
- a[i] = nullptr;
- lastEl = nullptr;
- }
- void put(string strKey, string el, int hashKey){
- list *findEl = a[hashKey];
- list *prevElement = findEl;
- while (findEl != nullptr && findEl->key != strKey) {
- prevElement = findEl;
- findEl = findEl->next;
- }
- if (findEl == nullptr) {
- list *newElement = new list;
- newElement->next = nullptr;
- newElement->element = el;
- newElement->key = strKey;
- newElement->nextEl = nullptr;
- if (prevElement == nullptr) {
- a[hashKey] = newElement;
- }
- else {
- prevElement->next = newElement;
- }
- if (lastEl != nullptr)
- lastEl->nextEl = newElement;
- newElement->prevEl = lastEl;
- lastEl = newElement;
- }
- else {
- findEl->element = el;
- }
- }
- string get(string strKey, int hashKey) {
- list* findEl = a[hashKey];
- while (findEl != nullptr && findEl->key != strKey) {
- findEl = findEl->next;
- }
- if (findEl == nullptr)
- return "none";
- else
- return findEl->element;
- }
- void del(string strKey, int hashKey){
- list* findEl = a[hashKey];
- list* prevElement = a[hashKey];
- while(findEl != nullptr && findEl -> key != strKey){
- prevElement = findEl;
- findEl = findEl -> next;
- }
- if (findEl != nullptr && findEl -> key == strKey){
- if (findEl == a[hashKey]) {
- a[hashKey] = findEl->next;
- }
- else {
- prevElement->next = findEl->next;
- }
- if (findEl->nextEl != nullptr) {
- findEl->nextEl->prevEl = findEl->prevEl;
- }
- if (findEl->prevEl != nullptr){
- findEl->prevEl->nextEl = findEl->nextEl;
- }
- if (findEl == lastEl)
- lastEl = findEl->prevEl;
- delete(findEl);
- }
- }
- string next(string strKey, int hashKey){
- list* findEl = a[hashKey];
- while(findEl != nullptr && findEl -> key != strKey){
- findEl = findEl -> next;
- }
- if (findEl != nullptr && findEl -> key == strKey){
- if (findEl->nextEl == nullptr)
- return "none";
- else
- return (findEl->nextEl->element);
- }
- else
- return "none";
- }
- string prev(string strKey, int hashKey){
- list* findEl = a[hashKey];
- while(findEl != nullptr && findEl -> key != strKey){
- findEl = findEl -> next;
- }
- if (findEl != nullptr && findEl -> key == strKey){
- if (findEl->prevEl == nullptr)
- return "none";
- else
- return (findEl->prevEl->element);
- }
- else
- return "none";
- }
- };
- int primeNum[26] = {25013, 25031, 25033, 25037, 25057, 25073,
- 25087, 25097, 25111, 25117, 25121, 25127,
- 25147, 25153, 25163, 25169, 25171, 25183,
- 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261};
- int FindHashKey(string str){
- int ans = 0, degree = 1;
- for (int i = 0; i < str.size(); i++) {
- ans = (abs(ans + (int) str[i] * degree) % 500009);
- degree *= primeNum[(int)str[0] - (int)'a'];
- }
- return ans;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- ifstream in;
- ofstream out;
- in.open("linkedmap.in");
- out.open("linkedmap.out");
- in.tie(NULL);
- LinkedMap lMap;
- while(!in.eof()){
- string com, element, key;
- in >> com;
- if (com.size() == 0)
- break;
- if (com == "put"){
- in >> key >> element;
- lMap.put(key, element, FindHashKey(key));
- }
- if (com == "get"){
- in >> key;
- out << lMap.get(key, FindHashKey(key)) << "\n";
- }
- if (com == "delete"){
- in >> key;
- lMap.del(key, FindHashKey(key));
- }
- if (com == "next"){
- in >> key;
- out << lMap.next(key, FindHashKey(key)) << "\n";
- }
- if (com == "prev"){
- in >> key;
- out << lMap.prev(key, FindHashKey(key)) << "\n";
- }
- }
- in.close();
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement