数据结构——线性表：字典（C++）

内容概要：

字典的相关概念

注意事项

简单的字典实现

一、字典的相关概念

字典（dictionary）是在数据库中具有存储、查询和删除记录的功能的线性表。

数据库中的记录一般是靠关键码（key）描述的，类似人们的ID号码。

关键码应当具有可比性（comparable）。

二、注意事项

由于关键码类型非常多，不能编写出通用的字典。

关键码不是记录的类的基本属性，也不是类中任意的域，它只是在使用记录时与环境相关的属性。

字典中的任一基本元素包含一条记录及与该记录相关的关键码，记录和关键码的组合称为键值对。

三、一个简单的字典

字典抽象类

键值对模板类

（int-char）字典类

#pragma once

//dictionary_ADT.h

template

class Dictionary

{

private:

void operator =(const Dictionary&){}

Dictionary(Dictionary&){}

public:

Dictionary(){}

virtual ~Dictionary() {}

virtual void clear()=0;

virtual void insert(const Key&,const E&) = 0;

virtual E remove(const Key&) = 0;

virtual E removeAny() = 0;

virtual E find(const Key&)const = 0;

virtual int size() = 0;

};

#pragma once

//key-value pair.h

template

class KVpair

{

private:

Key k;

E e;

public:

KVpair() {}

KVpair(const KVpair&kv) { k = kv.k; e = kv.e; }

KVpair(const Key&k0,const E&e0) { k = k0; e = e0; }

~KVpair() {};

Key key() { return k; }

E element() { return e; }

void setKey(const Key&k0) { k = k0; }

};

#pragma once

//array based dictionary.h

#include"dictionary_ADT.h"

#include"key-value pair.h"

#include

class ADict:public Dictionary

{

private:

KVpair*list;

int Maxsize;

int Size;

public:

ADict(int defaultSize = 100) { list = new KVpair[defaultSize]; Maxsize=100; Size = 0; }

~ADict() { delete list; }

void clear() { delete list; }

void insert(const int&k0,const char&e0)

{

assert(Size <= Maxsize);//list is full

KVpair it(k0,e0);

list[Size++] = it;

}

char remove(const int&k0)

{

for (int i = 0; i < Size; i++)

if (list[i].key() == k0)

{

char temp = list[i].element();

for (int k = 0; k < Size-i-1; k++)

list[i + k] = list[i + k + 1];

Size--;

return temp;

}

return 0;

}

char removeAny()

{

assert(Size != 0);//list is empty

return list[--Size].element();//remove the last one

}

char find(const int&k)const

{

for(int i=0;i

if (list[i].key() == k)

return list[i].element();

return 0;

}

int size() { return Size; }

};

//问题：键值对模板类对象动态数组list为什么会无成员,初步判断应该是由于模板的问题，

//数组元素大小不确定,所以这里把Key和E都分别具体化为int和char类型的，当然也可

//以通过使用链表来解决。

//dictionary_main.cpp

#include"array based dictionary.h"

#include

using namespace std;

int main()

{

ADict cc(10);

for (int i = 0; i < 20; i++)

cc.insert(101 + i,(char)(97 + i));

cout << endl;

cout << cc.find(101) << endl;

cout << "size:" << cc.size() << endl;

cout << "107:" << cc.remove(107) << endl;

cout << "104" << cc.remove(104) << endl;

cout << "after remove size:" << cc.size() << endl;

for (int i = 0; i < cc.size(); i++)

cout<

system("pause");

}

//注：这个程序有些隐性的问题，还没有解决，运行过程中有可能会出现“ *.exe已经触发一个断点”

//的问题，导致程序无法调试，也有可能导致堆和栈的损坏，这是内存超限的问题。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!