##题目要求编写一个哈希散列表，其中每个散列链表都是一个有尾节点的有序链表，而且所有链表在物理上都共享一个尾节点。
#在运行时，该代码再插入第二个数字时报错“读取访问权限冲突。this->first 是 0xFF7”，但在第一个数字插入时没有报错。代码如下
#include <iostream>
using namespace std;
//节点类
class Node {
public:
int value;
Node* next;
Node() {};
Node(int a) { value = a; }
~Node() {};
};
//链表类
class SortedChain {
public:
Node* first;
Node* tail;
SortedChain() {
first = new Node(-1);
tail = new Node(1061109567);
first->next = tail;
} //tail表示无穷大
~SortedChain() {};
bool IsEmpty()const { return first->next == 0; } //判断链表是否为空
int Length()const; //返回链表长度
bool Search(const int& k, int& e)const; //搜索，k是要搜索的数
SortedChain& Delete(const int &k,int e); //删除
SortedChain& Insert(const int & e); //插入
SortedChain& DistinctInsert(const int & e); //不允许重复关键字的插入
void Output();
};
//链表长度（算上tail）
int SortedChain::Length()const {
int n = 0;
Node* p = first;
while (p) {
n++;
p = p->next;
}
return n;
}
//链表搜索
bool SortedChain::Search(const int& k, int& e)const {
Node* p = first;
while (p->value < k) { //当前数小于k
p = p->next;
}
if (p && p->value == k) {
e = p->value;
return true; //找到了
}
return false; //链表为空，或者当前数据已经大于k
}
//链表删除
SortedChain& SortedChain::Delete(const int& k, int e) {
Node* p = first;
Node* tp = 0; //记录p的前一位，用于删除p
while (p->value < k) {
tp = p;
p = p->next;
}
//找到了
if (p->value == k) {
e = p->value;
if (p == first) { first = p->next; } //p是首节点
else { tp->next = p->next; } //p是普通节点
delete p;
return *this;
}
//没找到
cout << "没有可以删除的节点" << endl;
return *this;
}
//链表插入
SortedChain& SortedChain::Insert(const int& e) {
Node* p = first;
Node* tp = 0; //保存p的前一位，用于在tp后插入节点
Node* temp = new Node(e);
while (p->value < e) {
tp = p;
p = p->next;
}
temp->next = p;//把temp插到p前面
if (tp) { tp->next = temp; } //tp不为0，不是在头节点插入
else { first = temp; }//在头节点插入
return *this;
}
//不允许重复关键字的插入函数
SortedChain& SortedChain::DistinctInsert(const int& e) {
Node* p = first->next;
Node* tp = first;
Node* temp = new Node(e);
while (p->value < e) {
tp = p;
p = p->next;
}
//关键字已存在
if (p->value == e) {
cout << "关键字已存在，无法重复插入" << endl;
return *this;
}
//关键字不存在
temp->value = e;
temp->next = p;//把temp插到p前面
tp->next = temp; //tp不为0，不是在头节点插入
//else { first = temp; }//在头节点插入
return *this;
}
//打印链表函数
void SortedChain::Output() {
Node* p = first;
if (first->next == tail ) { cout << "链表为空" << endl; }
else {
while (p != tail) {
cout << p->value << " ";
p = p->next;
}
cout << endl;
}
}
class hashChainsWithTails {
public:
int m;
SortedChain* ht;
hashChainsWithTails(int divisor = 11) {
m = divisor;
ht = new SortedChain[m];
}
~hashChainsWithTails() { delete[]ht; }
bool Search(const int & k, int & e) {
return ht[k % m].Search(k, e);
}
hashChainsWithTails Insert(const int& e);
hashChainsWithTails Delete(const int& k, int& e);
void Output();
};
//插入哈希表
hashChainsWithTails hashChainsWithTails::Insert(const int& e) {
ht[e % m].DistinctInsert(e);
return *this;
}
//删除哈希表元素
hashChainsWithTails hashChainsWithTails::Delete(const int& k, int& e) {
ht[k % m].Delete(k, e);
return *this;
}
void hashChainsWithTails::Output() {
for (int i = 0; i < m; i++) {
cout << "第" << i << "：";
ht[i].Output();
}
}
int main() {
hashChainsWithTails n;
int i = 5, j;
while (i--) {
cin >> j;
n.Insert(j);
}
n.Output();
return 0;
}
