1.上機名稱

實現順序查找表

1. 順序查找表的基本概念
   順序查找表是一種線性數據結構，通常用于存儲一組元素。這些元素在表中按順序排列，查找操作通過逐個比較表中的元素來實現。順序查找表適用于小規模數據或不需要頻繁查找的場景。

2. 順序查找表的特點
   順序查找表的主要特點是其簡單性和直接性。由于元素是按順序存儲的，查找操作需要從表的一端開始，逐個比較元素，直到找到目標元素或遍歷完整個表。這種查找方式的時間復雜度為 O(n)，其中 n 是表中元素的數量。

3. 順序查找表的實現
   順序查找表可以通過數組或鏈表來實現。數組實現的順序查找表在內存中是連續存儲的，而鏈表實現的順序查找表則通過指針鏈接各個元素。
   順序查找表的優缺點
   順序查找表的優點是實現簡單，插入操作的時間復雜度為 O(1)。缺點是查找操作的時間復雜度較高，為 O(n)，尤其是在數據量較大的情況下，查找效率較低。

4. 順序查找表的應用場景
   順序查找表適用于數據量較小、查找操作不頻繁的場景。例如，在小型緩存系統或簡單的任務隊列中，順序查找表可以提供足夠的性能。

5. 順序查找表的優化
   為了提高順序查找表的查找效率，可以采用一些優化策略，如將頻繁訪問的元素移動到表的前面，或者使用二分查找等更高效的查找算法。然而，這些優化通常需要額外的存儲空間或更復雜的數據結構。

2.上機要求

（1）實現無序的順序查找表，實現插入鍵值對、按照關鍵字查詢、刪除記錄等操作
（2）實現有序的順序查找表，實現插入鍵值對、按照關鍵字查詢、刪除記錄等操作

3.上機環境

visual studio 2022
Windows11 家庭版 64位操作系統

4.程序清單(寫明運行結果及結果分析)

4.1 程序清單

4.1.1 頭文件

#pragma once
#include<iostream>
#include<string>
#define MAX_LEN 64
using namespace std;
//在此項目里，默認采用從大到小的排序順序
typedef std::string Key;	//鍵
typedef std::string Value;	//值
enum Type {_ORDER, DIS_ORDER
};
//Node結構體包含兩個成員變量：key和val，分別用于存儲鍵和值。
struct Node{Key key;Value val;
};class Record {
public:Record(int flag);	//用于初始化Record對象，flag表示記錄是有序還是無序。~Record();void push(Key key, Value val); 	//用于將鍵值對添加到記錄中。void search(Key key); 			//用于查找指定鍵的記錄。void search(); 					//用于交互式查找記錄。void erease(Key key); 			//用于刪除指定鍵的記錄。void printinfo(int i);			//用于打印指定索引的記錄信息。void searchkey(int low, int high, Key key);//用于在指定范圍內查找鍵。void view();					//用于查看所有記錄。int getsize();					//用于獲取當前記錄的數量。
private:Node* base;		//基址int curlen;		//現有長度int maxlen;		//空間尺度int flag;		//標記是無序還是有序
};

4.1.2 實現文件

#include "Sq_Search.h"
Record::Record(int flag){this->curlen = 0;this->maxlen = MAX_LEN;this->base = new Node[maxlen];memset(base, 0, sizeof(base));this->flag = flag;
}Record::~Record(){delete[]base;this->curlen = 0;this->maxlen = 0;
}void Record::push(Key key, Value val){if (curlen + 1 > maxlen) {Node* fresh = new Node[maxlen * 2];maxlen *= 2;memset(fresh, 0, sizeof(fresh));for(int i =0;i<curlen;i++){fresh[i].key = base[i].key;fresh[i].val = base[i].val;}delete[]base;base = fresh;}switch (flag){case _ORDER: {int i = 0;while (base[i].key.compare(key) > 0&&i<curlen) i++;int cord = i;for (i = curlen; i > cord && i > 0; i--) {base[i] = base[i - 1];}base[cord].key = key;base[cord].val = val;++curlen;break;}case DIS_ORDER: {base[curlen].key = key;base[curlen].val = val;++curlen;break;}default: {cout << "No Type!" << endl;exit(1);break;}}
}void Record::search(Key key){switch (flag){case _ORDER: {searchkey(0,curlen-1,key);break;}case DIS_ORDER: {int i = 0;while (i < curlen && base[i].key.compare(key))i++;if (i == curlen)cout << "Can't find key!" << endl;else printinfo(i);break;}default:exit(3);break;}
}void Record::search(){cout << "please enter a key to search>>" << endl;string str;cin >> str;search(str);
}void Record::erease(Key key){int i = 0;while (i < curlen && base[i].key.compare(key))i++;if (i == curlen)cout << "Can't find key!" << endl;else {for (int j = i; j < curlen; j++) {base[j].key = base[j + 1].key;base[j].val = base[j + 1].val;}--curlen;cout << "Erease  " << key << ">>" << endl;}
}void Record::printinfo(int i){cout << base[i].val << endl;
}void Record::searchkey(int low, int high,Key key){int mid = (low + high) / 2;if (mid >= high && base[mid].key.compare(key)) { cout << "Can't find key!" << endl; return; }if ( base[mid].key.compare(key) == 0) { printinfo(mid); return; }if ( base[mid].key.compare(key) < 0) { searchkey(low, mid - 1, key); }if ( base[mid].key.compare(key) > 0) { searchkey(mid + 1, high, key); }
}void Record::view(){for (int i = 0; i < curlen; i++) {cout <<base[i].key<<"\t--\t";printinfo(i);}
}int Record::getsize(){return curlen;
}

4.1.3 源文件

#include"Sq_Search.h"
int main() {Record order = Record(_ORDER);Record disorder = Record(DIS_ORDER);order.push("hello", "你好");order.push("world", "世界");order.push("push", "插入");order.push("int", "整型");order.push("max", "最大");order.push("min", "最小");order.push("float", "浮點型");disorder.push("hello", "你好");disorder.push("world", "世界");disorder.push("push", "插入");disorder.push("int", "整型");disorder.push("max", "最大");disorder.push("min", "最小");disorder.push("float", "浮點型");cout << "view order:\n";order.view();cout << "view disorder:\n";disorder.view();order.search("hello");disorder.search("world");order.erease("hello");order.view();order.search();
}

4.2 實現展效果示

上機體會

通過這次實驗，我深刻認識到理論知識和實踐經驗的重要性。在實現順序查找表的過程中，我不僅掌握了基本的算法知識，還學會了如何優化代碼以提高性能。此外，通過對比不同查找方法，我了解了各種方法的優缺點，為未來的應用開發提供了參考。
盡管順序查找表在某些場景下仍有應用價值，但在大規模數據集上，其性能表現并不理想。因此，在實際應用中，我們需要根據具體需求選擇合適的查找方法。對于需要頻繁查找的數據，可以考慮使用哈希查找等高效算法。而對于只需在小規模數據上完成簡單查找的任務，順序查找表仍是一種簡單、可靠的選擇。
在無序查找表中，查找時間復雜度為O（n），在有序查找表中，查找時間復雜度為O（log n）對于數據量大的情況，顯然有序表更占優勢。