数据结构实验4(排序算法的实现及性能分析)
最后更新于：2022-04-01 20:52:04
实现了选择排序, 插入排序, 冒泡排序, 快速排序, 改进后的快速排序, 以及两路合并排序.
通过随机函数随机生成100个数, 进行各种排序, 记录排序开始时间以及结束时间, 计算消耗的时间来比较算法的优略.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
#include "cstdlib"
#include "ctime"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
template
void SelectSort(T A[], int n)
{
int small;
for(int i = 0 ; i < n; ++i) {
small = i;
for(int j = i + 1; j < n; ++j)
if(A[j] < A[small]) small = j;
swap(A[i], A[small]);
}
}
template
void InsertSort(T A[], int n)
{
for(int i = 1; i < n; ++i) {
int j = i;
T tmp = A[j];
while(j > 0 && tmp < A[j - 1]) {
A[j] = A[j - 1];
j--;
}
A[j] = tmp;
}
}
template
void BubbleSort(T A[], int n)
{
int i = n - 1, j, last;
while(i > 0) {
last = 0;
for(int j = 0; j < i; ++j)
if(A[j + 1] < A[j]) {
swap(A[j], A[j + 1]);
last = j;
}
i = last;
}
}
template
void QSort(T A[], int left, int right)
{
int i, j;
if(left < right) {
i = left, j = right + 1;
do {
do i++; while(A[i] < A[left]);
do j--; while(A[j] > A[left]);
if(i < j) swap(A[i], A[j]);
}while(i < j);
swap(A[left], A[j]);
QSort(A, left, j - 1);
QSort(A, j + 1, right);
}
}
template
void QuickSort(T A[], int n)
{
QSort(A, 0, n - 1);
}
template
void MagicQSort(T A[], int left, int right)
{
int i, j;
if(right >= 9) {
if(left < right) {
i = left, j = right + 1;
do {
do i++; while(A[i] < A[left]);
do j--; while(A[j] > A[left]);
if(i < j) swap(A[i], A[j]);
}while(i < j);
swap(A[left], A[j]);
MagicQSort(A, left, j - 1);
MagicQSort(A, j + 1, right);
}
}
else {
InsertSort(A, right - left + 1);
return;
}
}
template
void MagicQuickSort(T A[], int n)
{
MagicQSort(A, 0, n - 1);
}
template
void Merge(T A[], int i1, int j1, int i2, int j2)
{
T *tmp = new T[j2 - i1 + 1];
int i = i1, j = i2, k = 0;
while(i <= j1 && j <= j2) {
if(A[i] <= A[j]) tmp[k++] = A[i++];
else tmp[k++] = A[j++];
}
while(i <= j1) tmp[k++] = A[i++];
while(j <= j2) tmp[k++] = A[j++];
for(int i = 0; i < k; ++i)
A[i1++] = tmp[i];
delete []tmp;
}
template
void MergeSort(T A[], int n)
{
int i1, j1, i2, j2, size = 1;
while(size < 1) {
i2 = i1 + size;
j1 = i2 - 1;
if(i2 + size - 1 > n - 1) j2 = n - 1;
else j2 = i2 + size - 1;
Merge(A, i1, j1, i2, j2);
i1 = j2 + 1;
}
size *= 2;
}
int main(int argc, char const *argv[])
{
clock_t start, finish;
srand(time(NULL));
int n = 100, i;
int *a = new int[n];
int *b = new int[n];
int *c = new int[n];
int *d = new int[n];
int *e = new int[n];
int *f = new int[n];
cout << "待排序序列为:" << endl;
for(int i = 0; i < n; ++i)
{
a[i] = rand()%91;
cout << a[i] << " ";
b[i] = a[i];
c[i] = a[i];
d[i] = a[i];
e[i] = a[i];
f[i] = a[i];
}
cout << endl;
start = clock();
SelectSort(a, n);
cout << "经过简单选择排序后的序列为:" << endl;
for(i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
start = clock();
InsertSort(b, n);
cout << "经过直接插入排序后的序列为:" << endl;
for(i = 0; i < n; ++i)
cout << b[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
start = clock();
BubbleSort(c, n);
cout << "经过冒泡排序后的序列为:" << endl;
for(i = 0; i < n; ++i)
cout << c[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
start = clock();
QuickSort(d, n);
cout << "经过快速排序后的序列为:" << endl;
for(i = 0; i < n; i++)
cout << d[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
start = clock();
MergeSort(e, n);
cout << "经过两路合并排序后的序列为:" << endl;
for(i = 0; i < n; i++)
cout << e[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
start = clock();
MagicQuickSort(f, n);
cout << "经过改进后的快速排序后的序列为:" << endl;
for(i = 0; i < n; ++i)
cout << f[i] << " ";
cout << endl;
finish = clock();
cout << "开始时间为:" << start << " " << "结束时间为:" << finish << " " << "持续时间为:" << (double)(finish - start)/ CLOCKS_PER_SEC << endl;
return 0;
}
~~~
';
拓扑排序的实现_TopoSort
最后更新于：2022-04-01 20:52:02
拓扑排序是求一个AOV网(顶点代表活动, 各条边表示活动之间的领先关系的有向图)中各活动的一个拓扑序列的运算, 可用于测试AOV网络的可行性.
整个算法包括三步:
1.计算每个顶点的入度, 存入InDegree数组中.
2.检查InDegree数组中顶点的入度, 将入度为零的顶点进栈.
3.不断从栈中弹出入度为0的顶点并输出, 并将该顶点为尾的所有邻接点的入度减1, 若此时某个邻接点的入度为0, 便领其进栈. 重复步骤,直到栈为空时为止. 此时, 或者所有顶点都已列出, 或者因图中包含有向回路, 顶点未能全部列出.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure, HasCycle };
template
struct ENode
{
ENode() { nxtArc = NULL; }
ENode(int vertex, T weight, ENode *nxt) {
adjVex = vertex;
w = weight;
nxtArc = nxt;
}
int adjVex;
T w;
ENode *nxtArc;
/* data */
};
template
class Graph
{
public:
virtual ~Graph() {}
virtual ResultCode Insert(int u, int v, T &w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class LGraph: public Graph
{
public:
LGraph(int mSize);
~LGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
protected:
ENode **a;
int n, e;
/* data */
};
template
void LGraph::Output()
{
ENode *q;
for(int i = 0; i < n; ++i) {
q = a[i];
while(q) {
cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')';
q = q -> nxtArc;
}
cout << endl;
}
cout << endl << endl;
}
template
LGraph::LGraph(int mSize)
{
n = mSize;
e = 0;
a = new ENode*[n];
for(int i = 0; i < n; ++i)
a[i] = NULL;
}
template
LGraph::~LGraph()
{
ENode *p, *q;
for(int i = 0; i < n; ++i) {
p = a[i];
q = p;
while(p) {
p = p -> nxtArc;
delete q;
q = p;
}
}
delete []a;
}
template
bool LGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false;
ENode *p = a[u];
while(p && p -> adjVex != v) p = p -> nxtArc;
if(!p) return false;
return true;
}
template
ResultCode LGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(Exist(u, v)) return Duplicate;
ENode *p = new ENode(v, w, a[u]);
a[u] = p;
e++;
return Success;
}
template
ResultCode LGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
ENode *p = a[u], *q = NULL;
while(p && p -> adjVex != v) {
q = p;
p = p -> nxtArc;
}
if(!p) return NotPresent;
if(q) q -> nxtArc = p -> nxtArc;
else a[u] = p -> nxtArc;
delete p;
e--;
return Success;
}
template
class ExtLgraph: public LGraph
{
public:
ExtLgraph(int mSize): LGraph(mSize) {}
void TopoSort(int *order);
private:
void CallInDegree(int *InDegree);
/* data */
};
template
void ExtLgraph::TopoSort(int *order)
{
int *InDegree = new int[LGraph::n];
int top = -1; // 置栈顶指针为-1, 代表空栈
ENode *p;
CallInDegree(InDegree); // 计算每个顶点的入度
for(int i = 0; i < LGraph::n; ++i)
if(!InDegree[i]) { // 图中入度为零的顶点进栈
InDegree[i] = top;
top = i;
}
for(int i = 0; i < LGraph::n; ++i) { // 生成拓扑排序
if(top == -1) throw HasCycle; // 若堆栈为空, 说明图中存在有向环
else {
int j = top;
top = InDegree[top]; // 入度为0的顶点出栈
order[i] = j;
cout << j << ' ';
for(p = LGraph::a[j]; p; p = p -> nxtArc) { // 检查以顶点j为尾的所有邻接点
int k = p -> adjVex; // 将j的出邻接点入度减1
InDegree[k]--;
if(!InDegree[k]) { // 顶点k入度为0时进栈
InDegree[k] = top;
top = k;
}
}
}
}
}
template
void ExtLgraph::CallInDegree(int *InDegree)
{
for(int i = 0; i < LGraph::n; ++i)
InDegree[i] = 0; // 初始化InDegree数组
for(int i = 0; i < LGraph::n; ++i)
for(ENode *p = LGraph::a[i]; p; p = p -> nxtArc) // 检查以顶点i为尾的所有邻接点
InDegree[p -> adjVex]++; // 将顶点i的邻接点p -> adjVex的入度加1
}
int main(int argc, char const *argv[])
{
ExtLgraph lg(9);
int w = 10; lg.Insert(0, 2, w); lg.Insert(0, 7, w);
lg.Insert(2, 3, w); lg.Insert(3, 5, w);
lg.Insert(3, 6, w); lg.Insert(4, 5, w);
lg.Insert(7, 8, w); lg.Insert(8, 6, w);
int *order = new int[9];
lg.TopoSort(order);
cout << endl;
delete []order;
return 0;
}
~~~
';
数据结构实验3(飞机最少环城次数问题)
最后更新于：2022-04-01 20:52:00
使用图算法解决应用问题: 设有n个城市, 编号为0 ~ n - 1, m条航线的起点和终点由用户输入提供. 寻找一条换乘次数最少的线路方案.
使用有向图表示城市间的航线, 只要两城市之间有航班, 则图中这两点间存在一条权为1的边. 用Dijkstra算法实现求最少换乘次数.
在MGraph类中增加Choose函数以及Dijkstra函数即可.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent, OutOfBounds };
template
class Graph
{
public:
virtual ~Graph() {};
virtual ResultCode Insert(int u, int v, T w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class MGraph: public Graph
{
public:
MGraph(int mSize, const T& noedg);
~MGraph();
ResultCode Insert(int u, int v, T w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Choose(int *d, bool *vis);
void Dijkstra(int v, int *d, int *path);
int Vertices() const { return n; }
void Output();
protected:
T **a;
T noEdge;
int n, e;
/* data */
};
template
void MGraph::Output()
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
if(a[i][j] == noEdge) cout << "NE\t";
else cout << a[i][j] << "\t";
cout << endl;
}
cout << endl << endl << endl;
}
template
MGraph::MGraph(int mSize, const T &noedg)
{
n = mSize, e = 0, noEdge = noedg;
a = new T *[n];
for(int i = 0; i < n; ++i) {
a[i] = new T[n];
for(int j = 0; j < n; ++j)
a[i][j] = noEdge;
a[i][i] = 0;
}
}
template
MGraph::~MGraph()
{
for(int i = 0; i < n; ++i)
delete []a[i];
delete []a;
}
template
bool MGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false;
return true;
}
template
ResultCode MGraph::Insert(int u, int v, T w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] != noEdge) return Duplicate;
a[u][v] = w;
e++;
return Success;
}
template
ResultCode MGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] == noEdge) return NotPresent;
a[u][v] = noEdge;
e--;
return Success;
}
template
int MGraph::Choose(int *d, bool *vis)
{
int pos = -1;
T m = INF;
for(int i = 0; i < n; ++i)
if(d[i] <= m && !vis[i]) {
m = d[i];
pos = i;
}
return pos;
}
template
void MGraph::Dijkstra(int v, int *d, int *path)
{
if(v < 0 || v > n - 1) throw OutOfBounds;
bool *vis = new bool[n];
for(int i = 0; i < n; ++i) {
vis[i] = false;
d[i] = a[v][i];
if(i != v && d[i] < INF) path[i] = v;
else path[i] = -1;
}
vis[v] = true;
d[v] = 0;
for(int i = 1; i < n; ++i) {
int x = Choose(d, vis);
vis[x] = true;
for(int j = 0; j < n; ++j)
if(!vis[j] && d[x] + a[x][j] < d[j]) {
d[j] = d[x] + a[x][j];
path[j] = x;
}
}
}
int main(int argc, char const *argv[])
{
int n, m;
cout << "请输入城市个数:";
cin >> n;
cout << "请输入航线条数:";
cin >> m;
MGraph A(n, INF);
int c, f;
cout << "请输入每条航线的起点和终点: " << endl;
for(int i = 0; i < m; ++i)
{
cout << "航线" << i + 1 <<": ";
cin >> c >> f;
A.Insert(c, f, 1);
}
char s;
int i = 0, j = 0;
do{
int v, w;
cout << "请输入你的起点和终点:";
cin >> v >> w;
while(v < 0 || w < 0 || w > n - 1 || v > n - 1)
{
cout << "输入错误!请重新输入:";
cin >> v >> w;
}
int *b = new int[n];
int *d = new int[n];
int *path = new int[n];
A.Dijkstra(v, d, path);
int e = n - 1;
for(int j = 0; j < n; ++j)
b[j] = -2;
if(w != v)
{
j = w;
while(path[j] != -1)
{
b[e] = path[j];
e--;
j = path[j];
}
if(e == n - 1 || d[j] == INF) cout << "该路间无线路!" << endl;
else {
cout << "从" << v << "到" << w << "的换乘次数最小的线路方案为:";
for(int k = 0; k < n; ++k)
if(b[k] != -2) cout << b[k] << ",";
cout << w << endl;
}
}
if(w == v) cout << "从" << v << "到" << w << "该路间无需乘飞机!" << endl;
delete []b;
delete []d;
delete []path;
cout << "请问是否继续查询路线?请输入Y/N:";
cin >> s;
while(s != 'Y' && s != 'y' && s != 'n' && s != 'N') {
cout << "输入错误!请重新输入:";
cin >> s;
}
}while(s == 'Y' || s == 'y');
return 0;
}
~~~
';
数据结构实验3(图的DFS和BFS实现)
最后更新于：2022-04-01 20:51:57
实现邻接矩阵和邻接表两种不同存储结构上实现图的基本运算, 在MGraph类中扩充增加DFS()和BFS()函数.
包含的运算: 插入一条边, 删除一条边, 查询边是否存在, 图的深度优先搜索和广度优先搜索.
广度优先搜索利用队列作为辅助的数据结构, 元素类型是树的结点.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent };
template
class SeqQueue
{
public:
SeqQueue(int mSize);
~SeqQueue() { delete []q; }
bool IsEmpty() const { return front == rear; } // front与rear相等时循环队列为空
bool IsFull() const { return (rear + 1) % maxSize == front; } // front与(rear + 1) % maxSize相等时循环队列满
bool Front(T &x) const;
bool EnQueue(T x);
bool DeQueue();
void Clear() { front = rear = 0; }
/* data */
private:
int front, rear, maxSize; // 队头元素 队尾元素 数组最大长度
T *q;
};
template
SeqQueue::SeqQueue(int mSize)
{
maxSize = mSize;
q = new T[maxSize];
front = rear = 0;
}
template
bool SeqQueue::Front(T &x) const
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
x = q[(front + 1) % maxSize];
return true;
}
template
bool SeqQueue::EnQueue(T x)
{
if(IsFull()) { // 溢出处理
cout << "SeqQueue is full" << endl;
return false;
}
q[(rear = (rear + 1) % maxSize)] = x;
return true;
}
template
bool SeqQueue::DeQueue()
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
front = (front + 1) % maxSize;
return true;
}
template
class Graph
{
public:
virtual ~Graph() {};
virtual ResultCode Insert(int u, int v, T &w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class MGraph: public Graph
{
public:
MGraph(int mSize, const T& noedg);
~MGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
void DFS();
void BFS();
protected:
T **a;
T noEdge;
int n, e;
void DFS(int v, bool *vis);
void BFS(int v, bool *vis);
/* data */
};
template
void MGraph::Output()
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
if(a[i][j] == noEdge) cout << "NE\t";
else cout << a[i][j] << "\t";
cout << endl;
}
cout << endl << endl << endl;
}
template
MGraph::MGraph(int mSize, const T &noedg)
{
n = mSize, e = 0, noEdge = noedg;
a = new T *[n];
for(int i = 0; i < n; ++i) {
a[i] = new T[n];
for(int j = 0; j < n; ++j)
a[i][j] = noEdge;
a[i][i] = 0;
}
}
template
MGraph::~MGraph()
{
for(int i = 0; i < n; ++i)
delete []a[i];
delete []a;
}
template
bool MGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false;
return true;
}
template
ResultCode MGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] != noEdge) return Duplicate;
a[u][v] = w;
e++;
return Success;
}
template
ResultCode MGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] == noEdge) return NotPresent;
a[u][v] = noEdge;
e--;
return Success;
}
template
void MGraph::DFS()
{
bool *vis = new bool[n];
memset(vis, false, n);
for(int i = 0; i < n; ++i)
if(!vis[i]) DFS(i, vis);
delete []vis;
}
template
void MGraph::DFS(int v, bool *vis)
{
vis[v] = true;
cout << ' ' << v;
for(int i = 0; i < n; ++i)
if(a[v][i] != noEdge && a[v][i] != 0 && !vis[i]) DFS(i, vis);
}
template
void MGraph::BFS()
{
bool *vis = new bool[n];
memset(vis, false, n);
for(int i = 0; i < n; ++i)
if(!vis[i]) BFS(i, vis);
delete []vis;
}
template
void MGraph::BFS(int v, bool *vis)
{
SeqQueue q(n);
vis[v] = true;
cout << ' ' << v;
q.EnQueue(v);
while(!q.IsEmpty()) {
q.Front(v);
q.DeQueue();
for(int i = 0; i < n; ++i)
if(a[v][i] != noEdge && a[v][i] != 0 && !vis[i]) {
vis[i] = true;
cout << ' ' << i;
q.EnQueue(i);
}
}
}
template
struct ENode
{
ENode() { nxtArc = NULL; }
ENode(int vertex, T weight, ENode *nxt) {
adjVex = vertex;
w = weight;
nxtArc = nxt;
}
int adjVex;
T w;
ENode *nxtArc;
/* data */
};
template
class LGraph: public Graph
{
public:
LGraph(int mSize);
~LGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
protected:
ENode **a;
int n, e;
/* data */
};
template
void LGraph::Output()
{
ENode *q;
for(int i = 0; i < n; ++i) {
q = a[i];
while(q) {
cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')';
q = q -> nxtArc;
}
cout << endl;
}
cout << endl << endl;
}
template
LGraph::LGraph(int mSize)
{
n = mSize;
e = 0;
a = new ENode*[n];
for(int i = 0; i < n; ++i)
a[i] = NULL;
}
template
LGraph::~LGraph()
{
ENode *p, *q;
for(int i = 0; i < n; ++i) {
p = a[i];
q = p;
while(p) {
p = p -> nxtArc;
delete q;
q = p;
}
}
delete []a;
}
template
bool LGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false;
ENode *p = a[u];
while(p && p -> adjVex != v) p = p -> nxtArc;
if(!p) return false;
return true;
}
template
ResultCode LGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(Exist(u, v)) return Duplicate;
ENode *p = new ENode(v, w, a[u]);
a[u] = p;
e++;
return Success;
}
template
ResultCode LGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
ENode *p = a[u], *q = NULL;
while(p && p -> adjVex != v) {
q = p;
p = p -> nxtArc;
}
if(!p) return NotPresent;
if(q) q -> nxtArc = p -> nxtArc;
else a[u] = p -> nxtArc;
delete p;
e--;
return Success;
}
int main(int argc, char const *argv[])
{
int n, g;
cout << "请输入元素的个数: ";
cin >> n;
MGraph A(n, INF);
LGraph B(n);
cout << "请输入边的条数: ";
cin >> g;
int *a = new int[g];
int *b = new int[g];
int *w = new int[g];
for(int i = 0; i < g; ++i)
{
cout << "请输入边及权值: ";
cin>> a[i] >> b[i] >> w[i];
A.Insert(a[i], b[i], w[i]);
B.Insert(a[i], b[i], w[i]);
}
cout << "该图的深度优先遍历为:" << endl;
A.DFS();
cout << endl;
cout << "该图的广度优先遍历为:" << endl;
A.BFS();
cout << endl;
cout << "请输入要搜索的边: ";
int c, d;
cin >> c >> d;
if(A.Exist(c, d)) cout << "邻接矩阵中该边存在!" << endl;
else cout << "邻接矩阵中该边不存在!" << endl;
if(B.Exist(c, d)) cout << "邻接表中该边存在!" << endl;
else cout << "邻接表中该边不存在!" << endl;
cout << "请输入要删除的边: ";
int e, f;
cin>> e >> f;
if(A.Remove(e, f) == Success) cout << "邻接矩阵中删除该边成功!" << endl;
else if(A.Remove(e, f) == NotPresent) cout<<"邻接矩阵中该边不存在!"<
';
数据结构实验2(二叉链表实现二叉树的基本运算)
最后更新于：2022-04-01 20:51:55
包含的二叉树运算: 删除一个二叉树, 求一颗二叉树的高度, 求一颗二叉树中叶子结点数, 复制一颗二叉树, 交换一颗二叉树的左右子树,
自上到下, 自左到右层次遍历一颗二叉树.
增加相关功能完善即可, 层次遍历利用队列作为辅助的数据结构, 元素类型是指向二叉树中结点的指针类型.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T& x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode* l, BTNode* r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode* lChild, *rChild;
};
template
class Queue
{
public:
virtual bool IsEmpty() const = 0; // 队列为空返回true
virtual bool IsFull() const = 0; // 队列满返回true
virtual bool Front(T &x) const = 0; // 队头元素赋给x，操作成功返回true
virtual bool EnQueue(T x) = 0; // 队尾插入元素x，操作成功返回true
virtual bool DeQueue() = 0; // 删除队头元素，操作成功返回true
virtual bool Clear() = 0; // 清除队列中所有元素
};
template
class SeqQueue:public Queue
{
public:
SeqQueue(int mSize);
~SeqQueue() { delete []q; }
bool IsEmpty() const { return front == rear; } // front与rear相等时循环队列为空
bool IsFull() const { return (rear + 1) % maxSize == front; } // front与(rear + 1) % maxSize相等时循环队列满
bool Front(T &x) const;
bool EnQueue(T x);
bool DeQueue();
bool Clear() { front = rear = 0; return true; }
/* data */
private:
int front, rear, maxSize; // 队头元素 队尾元素 数组最大长度
T *q;
};
template
SeqQueue::SeqQueue(int mSize)
{
maxSize = mSize;
q = new T[maxSize];
front = rear = 0;
}
template
bool SeqQueue::Front(T &x) const
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
x = q[(front + 1) % maxSize];
return true;
}
template
bool SeqQueue::EnQueue(T x)
{
if(IsFull()) { // 溢出处理
cout << "SeqQueue is full" << endl;
return false;
}
q[(rear = (rear + 1) % maxSize)] = x;
return true;
}
template
bool SeqQueue::DeQueue()
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
front = (front + 1) % maxSize;
return true;
}
template
class BinaryTree
{
public:
BinaryTree(): s(100){ root = NULL; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
int High(BTNode *p); // 返回二叉树高度
int Num(BTNode *p); // 返回二叉树叶子结点数
BTNode *Copy(BTNode *t); // 复制二叉树
void Exchange(BTNode *&t); // 交换二叉树左右子树
void Level_Traversal(void(*Visit)(T &x)); // 层次遍历二叉树
BTNode* root;
protected:
SeqQueue s;
private:
void Clear(BTNode *t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
void Level_Traversal(void(*Visit)(T &x), BTNode *t);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear()
{
Clear(root);
}
template
void BinaryTree::Clear(BTNode *t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, BinaryTree& left, BinaryTree& right)
{
if(root || &left == &right) return;
root = new BTNode(x, left.root, right.root);
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
PreOrder(Visit, root);
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
InOrder(Visit, root);
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
PostOrder(Visit, root);
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
template
int BinaryTree::High(BTNode *p)
{
if(p == NULL) return 0;
else if(p -> lChild == NULL && p -> rChild ==NULL) return 1;
else return(High(p -> lChild) > High(p -> rChild) ? High(p -> lChild) + 1 : High(p -> rChild) + 1);
}
template
int BinaryTree::Num(BTNode *p)
{
if(p) {
if(p -> lChild == NULL && p -> rChild == NULL) return 1;
else return Num(p -> lChild) + Num(p -> rChild);
}
else return 0;
}
template
BTNode*BinaryTree::Copy(BTNode *t)
{
if(t == NULL) return NULL;
BTNode *q = new BTNode(t -> element);
q -> lChild = Copy(t -> lChild);
q -> rChild = Copy(t -> rChild);
return q;
}
template
void BinaryTree::Exchange(BTNode *&t)
{
if(t) {
BTNode *q = t -> lChild;
t -> lChild = t -> rChild;
t -> rChild = q;
Exchange(t -> lChild);
Exchange(t -> rChild);
}
}
template
void BinaryTree::Level_Traversal(void(*Visit)(T &x), BTNode *t)
{
BTNode *a;
Visit(t -> element);
if(t -> lChild) s.EnQueue(t -> lChild);
if(t -> rChild) s.EnQueue(t -> rChild);
while(s.Front(a) == true) {
if(a -> lChild) s.EnQueue(a -> lChild);
if(a -> rChild) s.EnQueue(a -> rChild);
Visit(a -> element);
s.DeQueue();
}
}
int main(int argc, char const *argv[])
{
BinaryTree t[100], a, b, tmp;
int num = 0, high = 0;
t[7].MakeTree('H', a, b);
t[8].MakeTree('I', a, b);
t[3].MakeTree('D', t[7], t[8]);
t[4].MakeTree('E', a, b);
t[5].MakeTree('F', a, b);
t[6].MakeTree('G', a, b);
t[1].MakeTree('B', t[3], t[4]);
t[2].MakeTree('C', t[5], t[6]);
t[0].MakeTree('A', t[1], t[2]);
cout << "二叉树z的层次遍历结果:\n";
t[0].PreOrder(Visit);
cout << endl;
tmp.root = tmp.Copy(t[0].root);
cout << "tmp复制二叉树z后层次遍历结果:\n";
tmp.PreOrder(Visit);
cout << endl;
t[0].Exchange(t[0].root);
cout << "交换左右子树后二叉树z的层次遍历结果:\n";
t[0].PreOrder(Visit);
cout << endl;
num = t[0].Num(t[0].root);
cout << "二叉树z的叶子结点数为:\n" << num << endl;
high = t[0].High(t[0].root);
cout << "二叉树z的高度为:\n" << high << endl;
t[0].Clear();
return 0;
}
~~~
';
图的邻接表实现_LGraph
最后更新于：2022-04-01 20:51:53
邻接表是图的另一种有效的存储表示方法. 每个顶点u建立一个单链表, 链表中每个结点代表一条边, 为边结点. 每个单链表相当于邻接矩阵的一行.
adjVex域指示u的一个邻接点v, nxtArc指向u的下一个边结点. 如果是网, 增加一个w域存储边上的权值.
构造函数完成对一维指针数组a的动态空间存储分配, 并对其每个元素赋初值NULL. 析构函数首先释放邻接表中所有结点, 最后释放一维指针数组a所占的空间.
包含的函数Exist(): 若输入的u, v无效, 则函数返回false. 否则从a[u]指示的边结点开始, 搜索adjVex值为v的边结点, 代表边, 若搜索成功, 返回true, 否则返回false.
函数Insert(): 若输入的u, v无效, 则插入失败, 返回Failure. 否则从a[u]指示的边开始, 搜索adjVex值为v的边结点, 若不存在这样的边结点, 则创建代表边的新边结点, 并将其插在由指针a[u]所指示的单链表最前面, 并e++. 否则表示是重复边, 返回Duplicate.
函数Remove(): 若输入的u, v无效, 则删除失败, 返回Failure. 否则从a[u]指示的边开始, 搜索adjVex值为v的边结点, 若存在这样的边, 删除边, e--, 返回Success. 否则表示不存边, 返回NotPresent.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure };
template
struct ENode
{
ENode() { nxtArc = NULL; }
ENode(int vertex, T weight, ENode *nxt) {
adjVex = vertex;
w = weight;
nxtArc = nxt;
}
int adjVex;
T w;
ENode *nxtArc;
/* data */
};
template
class Graph
{
public:
virtual ~Graph() {}
virtual ResultCode Insert(int u, int v, T &w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class LGraph: public Graph
{
public:
LGraph(int mSize);
~LGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
protected:
ENode **a;
int n, e;
/* data */
};
template
void LGraph::Output()
{
ENode *q;
for(int i = 0; i < n; ++i) {
q = a[i];
while(q) {
cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')';
q = q -> nxtArc;
}
cout << endl;
}
cout << endl << endl;
}
template
LGraph::LGraph(int mSize)
{
n = mSize;
e = 0;
a = new ENode*[n];
for(int i = 0; i < n; ++i)
a[i] = NULL;
}
template
LGraph::~LGraph()
{
ENode *p, *q;
for(int i = 0; i < n; ++i) {
p = a[i];
q = p;
while(p) {
p = p -> nxtArc;
delete q;
q = p;
}
}
delete []a;
}
template
bool LGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false;
ENode *p = a[u];
while(p && p -> adjVex != v) p = p -> nxtArc;
if(!p) return false;
return true;
}
template
ResultCode LGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(Exist(u, v)) return Duplicate;
ENode *p = new ENode(v, w, a[u]);
a[u] = p;
e++;
return Success;
}
template
ResultCode LGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
ENode *p = a[u], *q = NULL;
while(p && p -> adjVex != v) {
q = p;
p = p -> nxtArc;
}
if(!p) return NotPresent;
if(q) q -> nxtArc = p -> nxtArc;
else a[u] = p -> nxtArc;
delete p;
e--;
return Success;
}
int main(int argc, char const *argv[])
{
LGraph lg(4);
int w = 4; lg.Insert(1, 0, w); lg.Output();
w = 5; lg.Insert(1, 2, w); lg.Output();
w = 3; lg.Insert(2, 3, w); lg.Output();
w = 1; lg.Insert(3, 0, w); lg.Output();
w = 1; lg.Insert(3, 1, w); lg.Output();
return 0;
}
~~~
';
图的邻接矩阵实现_MGraph
最后更新于：2022-04-01 20:51:51
邻接矩阵有两种, 不带权图和网的邻接矩阵. 不带权图的邻接矩阵元素为0或1, 网的邻接矩阵中包含0, INF, 和边上的权值, 权值类型T可为整型, 实型. 三元组(u, v, w)代表一条边, u, v是边的两个定点, w表示u v的关系:
a[u][u] = 0, 两种邻接矩阵的主对角元素都是0. a[u][v] = w, 若 在E中, 则w = 1(不带权图)或w = w(i, j)(网). 若不在E中,
则w = noEdge, noEdge = 0(不带权图)或noEdge = INF(网).
保护数据成员T **a指向动态生成的二维数组, 用来存储邻接矩阵.
包含的函数Exist(): 若输入参数u, v无效或a[u][v] == noEdge, 则不存在边, 返回false, 否则返回true.
函数Insert(): 若输入参数u, v无效返回Failure. 若a[u][v] != noEdge, 表示边已经存在, 函数返回Duplicate. 否则添加边, 返回Success, 具体做法: a[u][v] = w, e++.
函数Remove(): 若输入参数u, v无效, 不能执行删除运算, 返回Failure. 若a[u][v] == noEdge, 表示图中不存在边, 函数返回Notpresent. 否则从邻接矩阵中删除边, 返回Success, 具体做法: a[u][v] = noEdge, e--.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure };
template
class Graph
{
public:
virtual ~Graph() {};
virtual ResultCode Insert(int u, int v, T &w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class MGraph: public Graph
{
public:
MGraph(int mSize, const T& noedg);
~MGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
protected:
T **a;
T noEdge;
int n, e;
/* data */
};
template
void MGraph::Output()
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
if(a[i][j] == noEdge) cout << "NE\t";
else cout << a[i][j] << "\t";
cout << endl;
}
cout << endl << endl << endl;
}
template
MGraph::MGraph(int mSize, const T &noedg)
{
n = mSize, e = 0, noEdge = noedg;
a = new T *[n];
for(int i = 0; i < n; ++i) {
a[i] = new T[n];
for(int j = 0; j < n; ++j)
a[i][j] = noEdge;
a[i][i] = 0;
}
}
template
MGraph::~MGraph()
{
for(int i = 0; i < n; ++i)
delete []a[i];
delete []a;
}
template
bool MGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false;
return true;
}
template
ResultCode MGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] != noEdge) return Duplicate;
a[u][v] = w;
e++;
return Success;
}
template
ResultCode MGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] == noEdge) return NotPresent;
a[u][v] = noEdge;
e--;
return Success;
}
int main(int argc, char const *argv[])
{
MGraph mg(4, 99);
int w = 4; mg.Insert(1, 0, w); mg.Output();
w = 5; mg.Insert(1, 2, w); mg.Output();
w = 3; mg.Insert(2, 3, w); mg.Output();
w = 1; mg.Insert(3, 0, w); mg.Output();
w = 1; mg.Insert(3, 1, w); mg.Output();
return 0;
}
~~~
';
散列表ADT_HashTable
最后更新于：2022-04-01 20:51:48
M为除留余数法的模数, ht是指向动态生成的一维数组指针, empty是标志数组的指针.
成员函数Find()在散列表中搜索与x关键字相同的元素. 若表中存在与x关键字值相同的元素, 则将其复制给x, pos指示该位置, 函数返回Success. 若表已满, 函数返回Overflow. 若表未满, 函数返回NotPresent, pos指示首次遇到的空值位置.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int NeverUsed = -100;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent };
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) = 0;
virtual ResultCode Insert(T &x) = 0;
virtual ResultCode Remove(T &x) = 0;
/* data */
};
template
class HashTable: public DynamicSet
{
public:
HashTable(int divisor = 11);
~HashTable() {
delete []ht;
delete []empty;
}
ResultCode Search(T &x);
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Output();
/* data */
private:
ResultCode Find(T &x, int &pos);
T h(T x);
int M;
T *ht;
bool *empty;
};
template
void HashTable::Output()
{
for(int i = 0; i < M; ++i)
cout << i << ' ';
cout << endl;
for(int i = 0; i < M; ++i)
if(ht[i] == NeverUsed) cout << "NU" << ' ';
else cout << ht[i] << ' ';
cout << endl;
for(int i = 0; i < M; ++i)
if(empty[i]) cout << "T " << ' ';
else cout << "F " << ' ';
cout << endl;
}
template
T HashTable::h(T x)
{
return x % 11;
}
template
HashTable::HashTable(int divisor)
{
M = divisor;
ht = new T[M];
empty = new bool[M];
for(int i = 0; i < M; ++i)
empty[i] = true;
for(int i = 0; i < M; ++i)
ht[i] = NeverUsed;
}
template
ResultCode HashTable::Find(T &x, int &pos)
{
pos = h(x); // h为散列函数, h(x) < M
int i = pos, j = -1;
do{
if(ht[pos] == NeverUsed && j == -1) j = pos; // 记录首次遇到空值的位置
if(empty[pos]) break; // 表中没有与x有相同关键字的元素
if(ht[pos] == x) { // ht[pos]的关键字与值与x的关键字值相同
x = ht[pos];
return Success; // 搜索成功, ht[pos]赋值给x
}
pos = (pos + 1) % M;
}while(pos != i); // 已搜索完整个散列表
if(j == -1) return Overflow; // 表已满
pos = j; // 记录首次遇到的空值位置
return NotPresent;
}
template
ResultCode HashTable::Search(T &x)
{
int pos;
if(Find(x, pos) == Success) return Success;
return NotPresent;
}
template
ResultCode HashTable::Insert(T &x)
{
int pos;
ResultCode reslt = Find(x, pos);
if(reslt == NotPresent) {
ht[pos] = x;
empty[pos] = false;
return Success;
}
if(reslt == Success) return Duplicate;
return Overflow;
}
template
ResultCode HashTable::Remove(T &x)
{
int pos;
if(Find(x, pos) == Success) {
ht[pos] = NeverUsed;
return Success;
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
HashTable ht;
int x = 80; ht.Insert(x); ht.Output();
x = 80; ht.Insert(x); ht.Output();
x = 40; ht.Insert(x); ht.Output();
x = 65; ht.Insert(x); ht.Output();
x = 28; ht.Insert(x); ht.Output();
x = 24; ht.Insert(x); ht.Output();
x = 35; ht.Insert(x); ht.Output();
x = 58; ht.Insert(x); ht.Output();
return 0;
}
~~~
';
二叉搜索树ADT_BSTree
最后更新于：2022-04-01 20:51:46
二叉搜索树或是一颗空二叉树, 或是具有以下性质的二叉树:
1.若左子树不为空, 则左子树上所有结点的关键字值均小于根结点的关键字值.
2.若右子树不为空, 则右子树上所有结点的关键字值均大于根结点的关键字值.
3.左右子树也分别是二叉搜索树.
性质: 若以中序遍历一颗二叉搜索树, 将得到一个以关键字值递增排列的有序序列.
1.搜索实现: 若二叉树为空, 则搜索失败. 否则, 将x与根结点比较. 若x小于该结点的值, 则以同样的方法搜索左子树, 不必搜索右子树. 若x大于该结点的值, 则以同样的方法搜索右子树, 而不必搜索左子树. 若x等于该结点的值, 则搜索成功终止.
search()为递归搜索, search1()为迭代搜索.
2.插入实现: 插入一个新元素时, 需要先搜索新元素的插入位置. 如果树种有重复元素, 返回Duplicate. 搜索达到空子树, 则表明树中不包含重复元素. 此时构造一个新结点p存放新元素x, 连至结点q, 成为q的孩子, 则新结点p成为新二叉树的根.
3.删除实现: 删除一个元素时, 先搜索被删除结点p, 并记录p的双亲结点q. 若不存在被删除的元素, 返回NotPresent.
(1)若p有两颗非空子树, 则搜索结点p的中序遍历次序下的直接后继结点, 设为s. 将s的值复制到p中.
(2)若p只有一颗非空子树或p是叶子, 以结点p的唯一孩子c或空子树c = NULL取代p.
(3)若p为根结点, 删除后结点c成为新的根. 否则若p是其双亲确定左孩子, 则结点c也应成为q的左孩子, 最后释放结点p所占用的空间.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
enum ResultCode{ Underflow, Overflow, Success, Duplicate, NotPresent }; // 赋值为0, 1, 2, 3, 4, 5
template
class DynamicSet
{
public:
virtual ~DynamicSet() {}
virtual ResultCode Search(T &x) const = 0;
virtual ResultCode Insert(T &x) = 0;
virtual ResultCode Remove(T &x) = 0;
/* data */
};
template
struct BTNode
{
BTNode() { lChild = rChild = NULL; }
BTNode(const T &x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T &x, BTNode *l, BTNode *r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode *lChild, *rChild;
/* data */
};
template
class BSTree : public DynamicSet
{
public:
explicit BSTree() { root = NULL; } // 只可显示转换
virtual ~BSTree() { Clear(root); }
ResultCode Search(T &x) const;
ResultCode Search1(T &x) const;
ResultCode Insert(T &x);
ResultCode Remove(T &x);
protected:
BTNode *root;
private:
void Clear(BTNode *t);
ResultCode Search(BTNode *p, T &x) const;
/* data */
};
template
void BSTree::Clear(BTNode *t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template< class T>
ResultCode BSTree::Search(T &x) const
{
return Search(root, x);
}
template
ResultCode BSTree::Search(BTNode *p, T &x) const
{
if(!p) return NotPresent;
if(x < p -> element) return Search(p -> lChild, x);
if(x > p -> element) return Search(p -> rChild, x);
x = p -> element;
return Success;
}
template
ResultCode BSTree::Search1(T &x) const
{
BTNode *p = root;
while(p) {
if(x < p -> element) p = p -> lChild;
else if(x > p -> element) p = p -> rChild;
else {
x = p -> element;
return Success;
}
}
return NotPresent;
}
template
ResultCode BSTree::Insert(T &x)
{
BTNode *p = root, *q = NULL;
while(p) {
q = p;
if(x < p -> element) p = p -> lChild;
else if(x > p -> element) p = p -> rChild;
else {
x = p -> element;
return Duplicate;
}
}
p = new BTNode(x);
if(!root) root = p;
else if(x < q -> element) q -> lChild = p;
else q -> rChild = p;
return Success;
}
template
ResultCode BSTree::Remove(T &x)
{
BTNode *c, *s, *r, *p = root, *q = NULL;
while(p && p -> element != x) {
q = p;
if(x < p -> element) p = p -> lChild;
else p = p -> rChild;
}
if(!p) return NotPresent;
x = p -> element;
if(p -> lChild && p -> rChild) {
s = p -> rChild;
r = p;
while(s -> lChild) {
r = s;
s = s -> lChild;
}
p -> element = s -> element;
p = s;
q = r;
}
if(p -> lChild) c = p -> lChild;
else c = p -> rChild;
if(p == root) root = c;
else if(p == q -> lChild) q -> lChild = c;
else q -> rChild = c;
delete p;
return Success;
}
int main(int argc, char const *argv[])
{
BSTree bst;
int x = 28; bst.Insert(x);
x = 21; bst.Insert(x);
x = 25; bst.Insert(x);
x = 36; bst.Insert(x);
x = 33; bst.Insert(x);
x = 43; bst.Insert(x);
return 0;
}
~~~
';
ListSet_对半搜索的迭代算法
最后更新于：2022-04-01 20:51:44
递归函数效率低, 常使用相应的迭代算法.
mid, left, right均为元素下标, 如果当前表不为空, 则令x与l[mid]比较. 若两者相等, 则搜索成功. 若前者小于后者, 则继续查找左半部分, 否则查找右半部分. 下标范围分别为[left, mid - 1], [mid + 1, right]. 如果当前搜索表为空表, 搜索失败返回NotPresent.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "assert.h"
using namespace std;
const int MAXN = 9999;
enum ResultCode
{
Underflow, Overflow, Success, Duplicate, NotPresent
};
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) const = 0; // 表中搜索与x关键字相同的元素, 若存在则赋值给x并且返回Success, 否则返回NotPresent
virtual ResultCode Insert(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Duplicate, 若表已满返回Overflow, 若表未满返回Success
virtual ResultCode Remove(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Success, 否则返回NotPresent
virtual bool IsEmpty() const = 0; // 集合为空返回true
virtual bool IsFull() const = 0; // 集合为满返回true
/* data */
};
template
class ListSet: public DynamicSet
{
public:
ListSet( int mSize );
~ListSet() { delete []l; }
bool IsEmpty() const { return n == 0; }
bool IsFull() const { return n == maxSize; }
ResultCode Search(T &x) const;
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Print();
private:
T *l;
int maxSize, n;
/* data */
};
template
void ListSet::Print()
{
for(int i = 0; i < n; ++i)
cout << l[i] << "\t";
cout << endl;
}
template
ListSet::ListSet(int mSize)
{
maxSize = mSize;
l = new T[maxSize];
n = 0;
}
template
ResultCode ListSet::Insert(T &x)
{
assert(!IsFull());
l[n++] = x;
l[n] = MAXN;
return Success;
}
template
ResultCode ListSet::Remove(T &x)
{
}
template
ResultCode ListSet::Search(T &x) const
{
int mid, left = 0, right = n -1;
while(left <= right) {
mid = (left + right) / 2;
if(x < l[mid]) right = mid - 1;
else if(x > l[mid]) left = mid + 1;
else {
x = l[mid];
return Success;
}
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
ListSet ls(20);
int x = 21; ls.Insert(x);
x = 30; ls.Insert(x);
x = 36; ls.Insert(x);
x = 41; ls.Insert(x);
x = 52; ls.Insert(x);
x = 54; ls.Insert(x);
x = 66; ls.Insert(x);
x = 72; ls.Insert(x);
x = 83; ls.Insert(x);
x = 97; ls.Insert(x);
ls.Print();
x = 35;
if(ls.Search(x) == Success) cout << "Found " << x << endl;
else cout << "Not Found " << x << endl;
return 0;
}
~~~
';
ListSet_对半搜索的递归算法
最后更新于：2022-04-01 20:51:42
对半搜索是一种二分搜索, 将表划分为长度几乎相等的两个子表.
共有函数Search()调用私有函数BSearch(). 而后递归调用BSearch()函数实现对有序表的对半搜索.
mid, left, right均为元素下标, 如果当前表不为空, 则令x与l[mid]比较. 若两者相等, 则搜索成功. 若前者小于后者, 则继续查找左半部分, 否则查找右半部分. 下标范围分别为[left, mid - 1], [mid + 1, right]. 如果当前搜索表为空表, 搜索失败返回NotPresent.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "assert.h"
using namespace std;
const int MAXN = 9999;
enum ResultCode
{
Underflow, Overflow, Success, Duplicate, NotPresent
};
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) const = 0; // 表中搜索与x关键字相同的元素, 若存在则赋值给x并且返回Success, 否则返回NotPresent
virtual ResultCode Insert(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Duplicate, 若表已满返回Overflow, 若表未满返回Success
virtual ResultCode Remove(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Success, 否则返回NotPresent
virtual bool IsEmpty() const = 0; // 集合为空返回true
virtual bool IsFull() const = 0; // 集合为满返回true
/* data */
};
template
class ListSet: public DynamicSet
{
public:
ListSet( int mSize );
~ListSet() { delete []l; }
bool IsEmpty() const { return n == 0; }
bool IsFull() const { return n == maxSize; }
ResultCode Search(T &x) const;
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Print();
private:
T *l;
int maxSize, n;
int BSearch(T &x, int left, int right) const;
/* data */
};
template
void ListSet::Print()
{
for(int i = 0; i < n; ++i)
cout << l[i] << "\t";
cout << endl;
}
template
ListSet::ListSet(int mSize)
{
maxSize = mSize;
l = new T[maxSize];
n = 0;
}
template
ResultCode ListSet::Insert(T &x)
{
assert(!IsFull());
l[n++] = x;
l[n] = MAXN;
return Success;
}
template
ResultCode ListSet::Remove(T &x)
{
}
template
ResultCode ListSet::Search(T &x) const
{
int i = BSearch(x, 0, n - 1);
if(i == -1) return NotPresent;
x = l[i];
return Success;
}
template
int ListSet::BSearch(T &x, int left, int right) const
{
if(left <= right) {
int mid = (left + right) / 2;
if(x < l[mid]) return BSearch(x, left, mid - 1);
else if(x > l[mid]) return BSearch(x, mid + 1, right);
else return mid;
}
return -1;
}
int main(int argc, char const *argv[])
{
ListSet ls(20);
int x = 21; ls.Insert(x);
x = 30; ls.Insert(x);
x = 36; ls.Insert(x);
x = 41; ls.Insert(x);
x = 52; ls.Insert(x);
x = 54; ls.Insert(x);
x = 66; ls.Insert(x);
x = 72; ls.Insert(x);
x = 83; ls.Insert(x);
x = 97; ls.Insert(x);
ls.Print();
x = 66;
if(ls.Search(x) == Success) cout << "Found " << x << endl;
else cout << "Not Found " << x << endl;
return 0;
}
~~~
';
ListSet_有序表搜索
最后更新于：2022-04-01 20:51:39
一个有序表可以看成是一个已按关键字排序的有序集.
表的最后添增设了一个被称作哨兵的元素, 关键字为INF. 若表长为n, 需要在l[n]位置存放哨兵元素. 增加哨兵元素以后, 在for循环中不再需要通过下标来判定是否已经查完整个表. 当表中l[i]的关键字值大于等于指定元素x的关键字时, for循环结束.
搜索失败的平均搜索长度: n / 2 + 2.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "assert.h"
using namespace std;
const int MAXN = 9999;
enum ResultCode
{
Underflow, Overflow, Success, Duplicate, NotPresent
};
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) const = 0; // 表中搜索与x关键字相同的元素, 若存在则赋值给x并且返回Success, 否则返回NotPresent
virtual ResultCode Insert(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Duplicate, 若表已满返回Overflow, 若表未满返回Success
virtual ResultCode Remove(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Success, 否则返回NotPresent
virtual bool IsEmpty() const = 0; // 集合为空返回true
virtual bool IsFull() const = 0; // 集合为满返回true
/* data */
};
template
class ListSet: public DynamicSet
{
public:
ListSet( int mSize );
~ListSet() { delete []l; }
bool IsEmpty() const { return n == 0; }
bool IsFull() const { return n == maxSize; }
ResultCode Search(T &x) const;
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Print();
private:
T *l;
int maxSize, n;
/* data */
};
template
void ListSet::Print()
{
for(int i = 0; i < n; ++i)
cout << l[i] << "\t";
cout << endl;
}
template
ListSet::ListSet(int mSize)
{
maxSize = mSize;
l = new T[maxSize];
n = 0;
}
template
ResultCode ListSet::Insert(T &x)
{
assert(!IsFull());
l[n++] = x;
l[n] = MAXN;
return Success;
}
template
ResultCode ListSet::Remove(T &x)
{
}
template
ResultCode ListSet::Search(T &x) const
{
for(int i = 0; l[i] <= x; ++i)
if(l[i] == x) {
x = l[i];
return Success;
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
ListSet ls(20);
int x = 11; ls.Insert(x);
x = 22; ls.Insert(x);
x = 33; ls.Insert(x);
x = 44; ls.Insert(x);
x = 88; ls.Insert(x);
x = 100; ls.Insert(x);
ls.Print();
x = 88;
if(ls.Search(x) == Success) cout << "Found " << x << endl;
else cout << "Not Found " << x << endl;
return 0;
}
~~~
';
ListSet_无序表搜索
最后更新于：2022-04-01 20:51:37
无序表搜索就是一个个的遍历, 从头开始逐个检查, 直到表中关键字值等于给定关键字值, 则查找成功. 或者查完整个表, 查找失败为止.
搜索失败的平均搜索长度:(n + 1) / 2.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "assert.h"
using namespace std;
enum ResultCode
{
Underflow, Overflow, Success, Duplicate, NotPresent
};
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) const = 0; // 表中搜索与x关键字相同的元素, 若存在则赋值给x并且返回Success, 否则返回NotPresent
virtual ResultCode Insert(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Duplicate, 若表已满返回Overflow, 若表未满返回Success
virtual ResultCode Remove(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Success, 否则返回NotPresent
virtual bool IsEmpty() const = 0; // 集合为空返回true
virtual bool IsFull() const = 0; // 集合为满返回true
/* data */
};
template
class ListSet: public DynamicSet
{
public:
ListSet( int mSize );
~ListSet() { delete []l; }
bool IsEmpty() const { return n == 0; }
bool IsFull() const { return n == maxSize; }
ResultCode Search(T &x) const;
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Print();
private:
T *l;
int maxSize, n;
/* data */
};
template
void ListSet::Print()
{
for(int i = 0; i < n; ++i)
cout << l[i] << "\t";
cout << endl;
}
template
ListSet::ListSet(int mSize)
{
maxSize = mSize;
l = new T[maxSize];
n = 0;
}
template
ResultCode ListSet::Insert(T &x)
{
assert(!IsFull());
l[n++] = x;
return Success;
}
template
ResultCode ListSet::Remove(T &x)
{
}
template
ResultCode ListSet::Search(T &x) const
{
for(int i = 0; i < n; ++i)
if(l[i] == x) {
x = l[i];
return Success;
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
ListSet ls(20);
int x = 34; ls.Insert(x);
x = 88; ls.Insert(x);
x = 77; ls.Insert(x);
x = 55; ls.Insert(x);
x = 44; ls.Insert(x);
x = 100; ls.Insert(x);
ls.Print();
x = 88;
if(ls.Search(x) == Success)
cout << "Found " << x << endl;
return 0;
}
~~~
';
数据结构实验2(设计哈弗曼编码和译码系统)
最后更新于：2022-04-01 20:51:35
设计一个哈弗曼编码和译码系统, 要求如下:
B——建树：读入字符集和各字符频度，建立哈夫曼树。
T——遍历：先序和中序遍历二叉树。
E——生成编码：根据已建成的哈夫曼树，产生各个字符的哈夫曼编码。
C——编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。
D——译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt。
P——打印：屏幕显示文件textfile.txt，codefile.txt，result.txt。
X——退出。
提示: 修改教材中二叉树结点类BTNode, 增加一个指向双亲的parent域, 修改二叉树类的函数MakeTree设置该域的值. 通过遍历哈夫曼树, 产生每个叶子结点的哈夫曼编码. 当遍历访问某个叶节点时, 从该叶结点到根的路径可以确定该叶结点所代表的字符的编码.
忘记初始化debug了一晚上, 顺便复习文件操作. 代码用到了优先队列类以及二叉树类.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cassert"
#include "fstream"
using namespace std;
template
class PrioQueue
{
public:
PrioQueue(int mSize = 0);
~PrioQueue() { delete []q; }
bool IsEmpty() const { return n == 0; } // 优先队列为空返回true
bool IsFull() const { return n == maxSize; } // 优先队列为满返回true
void Append(const T& x); // 优先队列中添加值为x的元素
void Serve(T& x); // 优先队列中弹出队列中优先权最高的元素, 并赋值给x
private:
void AdjustDown(int r, int j); // 向下调整
void AdjustUp(int j); // 向上调整
void Print();
T* q;
int n, maxSize;
/* data */
};
template
void PrioQueue::Print()
{
for(int i = 0; i < n; ++i)
cout << q[i] << "\t";
cout << endl;
}
template
PrioQueue::PrioQueue(int mSize)
{
maxSize = mSize;
n = 0;
q = new T[maxSize];
}
template
void PrioQueue::AdjustUp(int j)
{
int i = j;
T tmp = q[i];
while(i > 0 && tmp < q[(i - 1) / 2]) {
q[i] = q[(i - 1) / 2];
i = (i - 1) / 2;
}
q[i] = tmp;
}
template
void PrioQueue::Append(const T& x)
{
assert(!IsFull());
q[n++] = x;
AdjustUp(n - 1);
}
template
void PrioQueue::Serve(T& x)
{
x = q[0];
q[0] = q[--n];
AdjustDown(0, n - 1);
}
template
void PrioQueue::AdjustDown(int r, int j)
{
int child = 2 * r + 1;
T tmp = q[r];
while(child <= j) {
if(child < j && q[child] > q[child + 1]) child++;
if(tmp <= q[child]) break;
q[(child - 1) / 2] = q[child];
child = 2 * child + 1;
}
q[(child - 1) / 2] = tmp;
}
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T &x, const char &y) {
element = x;
ch = y;
lChild = rChild = parent = NULL;
memset(z, -1, sizeof(z));
}
BTNode(const T& x, const char &y, BTNode* l, BTNode* r) {
element = x;
ch = y;
lChild = l;
rChild = r;
parent = NULL;
memset(z, -1, sizeof(z));
}
T element;
BTNode* lChild, *rChild, *parent;
char ch;
int val, z[100];
};
template
class BinaryTree
{
public:
BinaryTree() { root = NULL; i = -1; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, const char &y, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
void Create_code(); // 生成编码
void Create_code_out(); // 输出编码
void Code(); // 编码
void Compile(); // 译码
void Print();
BTNode* root;
/* data */
private:
int i;
void Clear(BTNode* t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
void Create_code(BTNode *t);
void Create_code_out(BTNode *t);
void Code(BTNode *t);
void Compile(BTNode *t);
void Make(BTNode *t, char a);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear(BTNode* t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, const char &y, BinaryTree &left, BinaryTree &right)
{
if(root || &left == &right) return;
root = new BTNode(x, y, left.root, right.root);
if(left.root != right.root) {
left.root -> parent = root;
right.root -> parent = root;
left.root -> val = 0;
right.root -> val = 1;
}
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
cout << "先序遍历为:" << endl;
PreOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
cout << "中序遍历为:" << endl;
InOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
cout << "后序遍历为:" << endl;
PostOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
template
class HfmTree: public BinaryTree
{
public:
operator T() const{ return weight; }
T getW() { return weight; }
void putW(const T &x) { weight = x; }
void SetNull() { BinaryTree::root = NULL; }
private:
T weight;
};
template
HfmTree CreatHfmTree(T w[], char q[], int n)
{
PrioQueue > pq(n);
HfmTree x, y, z, zero;
for(int i = 0; i < n; ++i) {
z.MakeTree(w[i], q[i], x, y);
z.putW(w[i]);
pq.Append(z);
z.SetNull();
}
for(int i = 1; i < n; ++i) {
pq.Serve(x);
pq.Serve(y);
z.MakeTree(x.getW() + y.getW(), 'e', x, y);
z.putW(x.getW() + y.getW());
pq.Append(z);
z.SetNull();
}
pq.Serve(z);
return z;
}
HfmTree HfmT;
int num;
void Make_HfmT()
{
char s[100];
int w[100];
cout << "请输入字符个数:" << endl;
cin >> num;
cout << "请输入权值:" << endl;
for(int i = 0; i < num; ++i)
cin >> w[i];
cout << "请输入相应字符集:" << endl;
cin >> s;
HfmT = CreatHfmTree(w, s, num);
}
void Traversal_HfmT()
{
HfmT.PreOrder(Visit);
HfmT.InOrder(Visit);
HfmT.PostOrder(Visit);
}
template
void BinaryTree::Create_code()
{
Create_code(root);
}
template
void BinaryTree::Create_code(BTNode *t)
{
if(t) {
if(t -> parent) {
for(int j = 0; j <= i; ++j)
t -> z[j] = t -> parent -> z[j]; // 复制双亲编码域
i++;
t -> z[i] = t -> val; // 编码中加入自己编码
}
Create_code(t -> lChild);
Create_code(t -> rChild);
i--;
}
}
template
void BinaryTree::Create_code_out()
{
Create_code_out(root);
}
template
void BinaryTree::Create_code_out(BTNode *t)
{
if(t) {
if(t -> lChild == t -> rChild) {
cout << t -> ch << ':';
int i = 0;
while(t -> z[i] != -1) {
cout << t -> z[i];
i++;
}
cout << endl;
}
Create_code_out(t -> lChild);
Create_code_out(t -> rChild);
}
}
template
void BinaryTree::Code()
{
Code(root);
}
template
void BinaryTree::Code(BTNode *t)
{
ofstream outt("textfile.txt");
if(!outt) {
cout << "Open textfile.txt failed." << endl;
return ;
}
ofstream outc("codefile.txt", ios::trunc);
if(!outc) {
cout << "Open codefile.txt failed." << endl;
return ;
}
outc.close();
char s[100];
cout << "请输入由字符集组成的任意字符串:" << endl;
cin >> s;
outt << s;
outt.close();
int len = strlen(s);
cout << "编码为:" << endl;
for(int i = 0; i < len; ++i)
Make(root, s[i]);
cout << endl;
}
template
void BinaryTree::Make(BTNode *t, char a)
{
int i = 0;
if(t) {
if(t -> ch == a) {
ofstream outc("codefile.txt", ios::app);
while(t -> z[i] != -1) {
cout << t -> z[i];
outc << t -> z[i];
i++;
}
outc.close();
return ;
}
Make(t -> lChild, a);
Make(t -> rChild, a);
}
}
template
void BinaryTree::Compile()
{
Compile(root);
}
template
void BinaryTree::Compile(BTNode *t)
{
ifstream inf("codefile.txt");
if(!inf) {
cout << "Open codefile.txt failed." << endl;
return;
}
ofstream outs("result.txt",ios::trunc);
if(!outs) {
cout << "Open result.txt failed." << endl;
return;
}
outs.close();
char *re;
char tmp;
int n = 0;
while(inf.get(tmp) != '\0') n++;
inf.close();
re = new char[n+1];
int n2 = 0;
ifstream in("codefile.txt");
if(!in) {
cout<<"Open codefile.txt failed." << endl;
return;
}
while(in.get(tmp) != '\0') re[n2++] = tmp;
BTNode *c;
cout << "译码为 :";
int n3 = 0;
while(n3 < n) {
while(t) {
c = t;
if(re[n3] == '0') // 左0右1根据0或1向左走向右走直到叶子结点
t = t -> lChild;
else
t = t -> rChild;
n3++;
}
ofstream outs("result.txt", ios::app);
if(!outs) {
cout << "Open result.txt failed." << endl;
return;
}
cout << c -> ch;
outs << c -> ch;
outs.close();
t = root;
n3--;
}
cout << endl;
}
void Print()
{
char ch;
ifstream a("textfile.txt");
ifstream b("codefile.txt");
ifstream c("result.txt");
if(!a) {
cout << "Open textfile.txt failed." << endl;
return ;
}
if(!b) {
cout << "Open codefile.txt failed." << endl;
return ;
}
if(!c) {
cout << "Open result.txt failed." << endl;
return ;
}
cout << "textfile.txt内容为:" << endl;
while(a.get(ch) != '\0') cout << ch;
cout << endl;
cout << "codefile.txt内容为:" << endl;
while(b.get(ch) != '\0') cout << ch;
cout << endl;
cout << "result.txt内容为:" << endl;
while(c.get(ch) != '\0') cout << ch;
cout << endl;
a.close();
b.close();
c.close();
}
void Menu()
{
cout << "欢迎使用哈夫曼编码和译码系统" << endl;
cout << "**************" << endl;
cout << "******菜单******" << endl;
cout << "*******B-建树*******" << endl;
cout << "*******T-遍历*******" << endl;
cout << "*****E-生成编码*****" << endl;
cout << "*******C-编码*******" << endl;
cout << "*******D-译码*******" << endl;
cout << "*******P-打印*******" << endl;
cout << "*******X-退出*******" << endl;
cout << "**************" << endl;
}
int main(int argc, char const *argv[])
{
char ch;
Menu();
while(cin >> ch && ch != 'X') {
switch(ch) {
case 'B': {
Make_HfmT();
HfmT.Create_code();
break;
}
case 'T': {
Traversal_HfmT();
break;
}
case 'E': {
cout << "编码为:" << endl;
HfmT.Create_code_out();
break;
}
case 'C': {
HfmT.Code();
break;
}
case 'D': {
HfmT.Compile();
break;
}
case 'P': {
Print();
break;
}
default: {
cout << "输入有误, 请重新输入." << endl;
break;
}
}
Menu();
}
return 0;
}
~~~
';
堆ADT_Heap
最后更新于：2022-04-01 20:51:33
一个大小为n的堆是一棵包含n个结点的完全二叉树, 该树中每个结点的关键字值大于等于其双亲结点的关键字值.
堆顶: 二叉树的根, 它的关键字是整棵树上最小的.(最小堆)
建堆运算时, CreatHeap()函数完成将一个以任意次序排列的元素排列, 通过向下调整建成最小堆.
实现运算AdjustDown的方法是: 向下调整heap[r]. 设tmp = hear[r], 如果tmp大于其左, 右孩子中的较小者, 则将tmp与该较小元素交换,
调整后继续将tmp与它的左右孩子比较. 如果比较小的孩子大, 则继续交换. 直到不需要再调整或者已经到堆底.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
template
void AdjustDown(T heap[], int r, int j)
{
int child = 2 * r + 1;
T tmp = heap[r];
while(child <= j) {
if(child < j && heap[child] > heap[child + 1]) child++;
if(tmp < heap[child]) break;
heap[(child - 1) / 2] = heap[child];
child = 2 * child + 1;
}
heap[(child - 1) / 2] = tmp;
for(int i = 0; i <= j; ++i)
cout << heap[i] << "\t";
cout << endl;
}
template
void CreatHeap(T heap[], int n)
{
for(int i = (n - 2) / 2; i > -1; --i)
AdjustDown(heap, i, n - 1);
}
int main(int argc, char const *argv[])
{
int heap[] = {61, 28, 81, 43, 36, 47, 83, 5};
for(int i = 0; i < 8; ++i)
cout << heap[i] << "\t";
cout << endl;
CreatHeap(heap, 8);
return 0;
}
~~~
';
优先队列ADT_PrioQueue
最后更新于：2022-04-01 20:51:30
如果定义最小值为最高优先权, 使用最小堆为例.
每次入队新元素都要向上调整, 同理, 弹出优先权最高的元素时要向下调整, 使之成为堆.
将新元素插入p[j]后的调整工作由AdjustUp()函数完成, 该函数按照与函数AdjustDown()相反的方向比较路径, 由下向上, 与双亲结点进行比较. 若双亲结点的元素值比孩子结点元素值大, 则调整之, 直到或者其双亲不大于待插入元素, 或者以及到达堆顶.
程序中首先将新元素插在q[j]处, 令tmp元素等于新元素q[j], 从i = j开始, 将tmp与其双亲q[(i - 1) / 2]比较. 如果tmp小于q[(i - 1) / 2], 则将q[(i - 1) / 2]向下移到q[i]处, 直到或者tmp >= q[(i - 1) / 2], 或者已达到堆顶.
若优先队列未满, 则函数Append()首先在优先队列的最后插入新元素, 然后调用AdjustUp()进行向上调整, 将队列重新调整为堆.
若优先队列非空, 则函数Sever()首先将堆顶元素赋值给x, 然后将原来的堆底元素取代堆顶元素, 同时让堆大小减一, 最后使用调用函数AdjustDown()进行向下调整.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cassert"
using namespace std;
template
class PrioQueue
{
public:
PrioQueue(int mSize = 0);
~PrioQueue() { delete []q; }
bool IsEmpty() const { return n == 0; } // 优先队列为空返回true
bool IsFull() const { return n == maxSize; } // 优先队列为满返回true
void Append(const T& x); // 优先队列中添加值为x的元素
void Serve(T& x); // 优先队列中弹出队列中优先权最高的元素, 并赋值给x
private:
void AdjustDown(int r, int j); // 向下调整
void AdjustUp(int j); // 向上调整
void Print();
T* q;
int n, maxSize;
/* data */
};
template
void PrioQueue::Print()
{
for(int i = 0; i < n; ++i)
cout << q[i] << "\t";
cout << endl;
}
template
PrioQueue::PrioQueue(int mSize)
{
maxSize = mSize;
n = 0;
q = new T[maxSize];
}
template
void PrioQueue::AdjustUp(int j)
{
int i = j;
T tmp = q[i];
while(i > 0 && tmp < q[(i - 1) / 2]) {
q[i] = q[(i - 1) / 2];
i = (i - 1) / 2;
}
q[i] = tmp;
Print();
}
template
void PrioQueue::Append(const T& x)
{
assert(!IsFull());
q[n++] = x;
AdjustUp(n - 1);
}
template
void PrioQueue::Serve(T& x)
{
assert(!IsFull());
x = q[0];
q[0] = q[--n];
AdjustDown(0, n - 1);
}
template
void PrioQueue::AdjustDown(int r, int j)
{
int child = 2 * r + 1;
T tmp = q[r];
while(child <= j) {
if(child < j && q[child] > q[child + 1]) child++;
if(tmp <= q[child]) break;
q[(child - 1) / 2] = q[child];
child = 2 * child + 1;
}
q[(child - 1) / 2] = tmp;
Print();
}
int main(int argc, char const *argv[])
{
PrioQueue pq(8); // 实现过程
pq.Append(71); pq.Append(74); pq.Append(2);
pq.Append(54); pq.Append(93); pq.Append(52);
pq.Append(28);
int i;
cout << endl;
pq.Serve(i);
pq.Serve(i);
return 0;
}
~~~
';
二叉树ADT_BinaryTree
最后更新于：2022-04-01 20:51:28
二叉树是结点的有限集合, 该集合或者为空集, 或者是由一个根和两棵互不相交的称为该根的左子树和右子树的二叉树组成.
二叉树可以为空集, 可以有空二叉树, 也可以有空的左子树 或/和 又子树.
二叉树的性质: 1.第i层至多有2^(i - 1)个结点. 2.高度为h的二叉树上至多有2*h - 1个结点. 3.包含n个元素的二叉树高度至少为>=log2(n + 1)取整. 3.任意一颗二叉树中, 若叶结点的个数为n0, 度为2的结点个数为n2, 则必有n0 = n2 + 1.
树与二叉树区别: 1.树不能为空树, 二叉树可以为空. 2.树的子树之间是无序的, 其子树不分次序. 二叉树中结点的子树要分左右子树.
满二叉树: 高度为h的二叉树恰好有2^h - 1个结点.
完全二叉树: 一棵二叉树中, 只有最下面两层结点的度可以小于2, 并且最下面一层的叶结点集中在靠左的若干位置上.
扩充二叉树(2 - 树): 除叶子结点外, 其余结点都必须有两个孩子.
树与二叉树区别: 1.树不能为空树, 二叉树可以为空. 2.树的子树之间是无序的, 其子树不分次序. 二叉树中结点的子树要分左右子树.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T& x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode* l, BTNode* r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode* lChild, *rChild;
};
template
class BinaryTree
{
public:
BinaryTree() { root = NULL; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
/* data */
protected:
BTNode* root;
private:
void Clear(BTNode* t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear(BTNode* t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, BinaryTree& left, BinaryTree& right)
{
if(root || &left == &right) return;
root = new BTNode(x, left.root, right.root);
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
PreOrder(Visit, root);
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
InOrder(Visit, root);
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
PostOrder(Visit, root);
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
int main(int argc, char const *argv[])
{
BinaryTree a, b, x, y, z; // 构造过程见课本75页.
char e;
y.MakeTree('E', a, b);
z.MakeTree('F', a, b);
x.MakeTree('C', y, z);
y.MakeTree('D', a, b); // 用y前y已经被置空
z.MakeTree('B', y, x);
cout << endl << "PreOrder\t";
z.PreOrder(Visit);
cout << endl << "InOrder\t\t";
z.InOrder(Visit);
cout << endl << "PostOrder\t";
z.PostOrder(Visit);
cout << endl;
cout << "Tree's size = " << z.Size() << endl;
cout << "Tree's count = " << z.Count() << endl;
z.BreakTree(e, y, x);
cout << endl << "PreOrder\t";
z.PreOrder(Visit);
cout << endl << "InOrder\t\t";
z.InOrder(Visit);
cout << endl << "PostOrder\t";
z.PostOrder(Visit);
cout << endl;
cout << "Tree's size = " << z.Size() << endl;
cout << "Tree's count = " << z.Count() << endl;
return 0;
}
~~~
';
数据结构实验1(一元多项式的相加和相乘)
最后更新于：2022-04-01 20:51:26
实验要求：
1.设计带表头的结点的单链表表示多项式类。
2.在该类上增加成员函数void PolyMul(Polynominal &r)，并重载*运算符。
3.实现菜单驱动的main函数，测试多项式的各个运算：输入多项式，显示多项式，以及多项式加法和乘法运算。
4.采用带表头的非循环链表存储多项式。
大致结构以及加法的运算书上的代码已经给出。乘法运算：将乘数多项式的每一项与被乘数多项式的所有项分别相乘(系数相乘，指数
相加)，得到中间多项式。调用PolyAdd函数将这些中间多项式依次加到结果多项式中。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
class Term
{
public:
Term(int c, int e);
Term(int c, int e, Term *nxt);
Term* InsertAfter(int c, int e); // 在this指针指示的结点后插入新节点
private:
int coef, exp; // coef * x^exp
Term* link;
friend ostream & operator << (ostream &, const Term &);
friend class Polynominal;
/* data */
};
Term::Term(int c, int e) : coef(c), exp(e)
{
link = 0;
}
Term::Term(int c, int e, Term *nxt) : coef(c), exp(e)
{
link = nxt;
}
Term *Term::InsertAfter(int c, int e) // 为新项申请结点的存储单元，并用Term函数将c, e, this -> link 的值填入新节点的相应域
{
link = new Term(c, e, link);
return link;
}
ostream & operator << (ostream& out, const Term& val)
{
if(val.coef == 0) return out;
if(val.coef != 1) out << val.coef;
switch(val.exp) {
case 0: break;
case 1: out << "x"; break;
default: out << "x^" << val.exp; break;
}
return out;
}
class Polynominal
{
public:
Polynominal();
~Polynominal();
void AddTerms(istream& in);
void Output(ostream& out) const;
void PolyAdd(Polynominal& r);
void PolyMul(Polynominal& r);
private:
Term* theList;
friend ostream & operator << (ostream &, const Polynominal &);
friend istream & operator >> (istream &, Polynominal &);
friend Polynominal & operator + (Polynominal &, Polynominal &);
friend Polynominal & operator * (Polynominal &, Polynominal &);
/* data */
};
Polynominal::Polynominal()
{
theList = new Term(0, -1); // 表头结点
theList -> link = NULL; // 尾结点为空
}
Polynominal::~Polynominal()
{
Term *p = theList -> link;
while(p != NULL) {
theList -> link = p -> link;
delete p;
p = theList -> link;
}
delete theList;
}
void Polynominal::AddTerms(istream& in) // 按降幂输入各项，构造单循环链表
{
Term* q = theList;
int c, e;
while(true) {
cout << "Input a term(coef, exp):" << endl << endl;
cin >> c >> e;
q = q -> InsertAfter(c, e); // 将c，e插入表尾结点q之后
if(e < 0) break; // 当输入指数小于0时，构造结束
}
}
void Polynominal::Output(ostream& out) const
{
int first = 1;
Term *p = theList -> link;
for( ; p != NULL && p -> exp >= 0; p = p -> link) {
if(!first && (p -> coef > 0)) out << "+"; // 在非第一项的正系数前输出+号
first = 0;
out << *p; // 调用Term类上重载的"<<"操作
}
cout << endl;
}
void Polynominal::PolyAdd(Polynominal& r)
{
Term *q, *q1 = theList, *p; // q1指向表头结点
p = r.theList -> link; // p指向第一个要处理的结点
q = q1 -> link; // q1是q的前驱，p和q就指向两个当前进行比较的项
while(p != NULL && p -> exp >= 0) { // 对r的单链表遍历，直到全部结点都处理完
while(p -> exp < q -> exp) { // 跳过q -> exp大的项
q1 = q;
q = q -> link;
}
if(p -> exp == q -> exp) { // 指数相等时，系数相加
q -> coef = q -> coef + p -> coef;
if(q -> coef == 0) { // 若相加后系数为0，则删除q
q1 -> link = q -> link;
delete (q);
q = q1 -> link; // 重置q指针
}
else { // 若相加后系数不为0，则移动q1和q
q1 = q;
q = q -> link;
}
}
else q1 = q1 -> InsertAfter(p -> coef, p -> exp); // 若p -> exp > q -> exp则以p的系数和指数生成新结点，插入q1后
p = p -> link;
}
}
void Polynominal::PolyMul(Polynominal& r)
{
Polynominal result; // 存储结果
Term *n = result.theList; // n指向result的头结点
n = n -> InsertAfter(0, 0); // 将0, 0插入result的头结点之后
Term *p = r.theList -> link; // p指向第一个要处理的结点
while(p -> exp >= 0) { // 对r的单链表遍历，直到全部结点都处理完
Polynominal tmp; // tmp存储当前结果
Term *m = tmp.theList; // m指向tmp头结点
Term *q = theList -> link; // q指向表头结点的后继结点
while(q -> exp >= 0) { // 遍历当前单链表
m = m -> InsertAfter((p -> coef) * (q -> coef), (p -> exp) + (q -> exp)); // 生成新结点插入m后
q = q -> link;
}
result.PolyAdd(tmp); // 当前结果加到result上
p = p -> link;
}
Term *q = theList -> link;
while(q != NULL) { // 清空原数据
theList -> link = q -> link;
delete q;
q = theList -> link;
}
q = theList;
q = q -> InsertAfter(0, 0);
PolyAdd(result); // result加到当前对象上
}
ostream & operator << (ostream &out, Polynominal &x)
{
x.Output(out);
return out;
}
istream & operator >> (istream &in, Polynominal &x)
{
x.AddTerms(in);
return in;
}
Polynominal & operator + (Polynominal &a, Polynominal &b)
{
a.PolyAdd(b);
return a;
}
Polynominal & operator * (Polynominal &a, Polynominal &b)
{
a.PolyMul(b);
return a;
}
int main(int argc, char const *argv[])
{
cout << "***********" << endl;
cout << " 按1进行多项式加法" << endl;
cout << " 按2进行多项式乘法" << endl;
cout << " 按0退出程序" << endl;
cout << "***********" << endl;
int num;
while(cin >> num && num) {
cout << "请输入多项式p：" << endl;
Polynominal p, q;
cin >> p;
cout << p << endl;
cout << "请输入多项式q：" << endl;
cin >> q;
cout << q << endl;
if(num == 1) {
Polynominal ans = p + q;
cout << "p + q = " << ans << endl;
}
else {
Polynominal ans = p * q;
cout << "p * q = " << ans << endl;
}
cout << "***********" << endl;
cout << " 按1进行多项式加法" << endl;
cout << " 按2进行多项式乘法" << endl;
cout << " 按0退出程序" << endl;
cout << "***********" << endl << endl;
}
cout << endl << "感谢检查" << endl;
return 0;
}
~~~
';
数据结构实验1(顺序表逆置以及删除)
最后更新于：2022-04-01 20:51:24
在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置。
在顺序表类SeqList中增加成员函数bool DeleteX(const T &x)，删除表中所有元素值等于x的元素。若表中存在这样的元素，则删除之，且函数返回true。否则函数返回false。
直接在SeqList类增加两个成员函数完成相应功能，逆置的话用到了stl中的栈，原elements入栈后紧着着赋值覆盖原来的元素值就实现了逆置。删除所有等于x的元素则扫一遍顺序表，若找到等于x的元素就调用Delete()函数，最后比较原长度以及现长度就知道有没有删除成功。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "stack"
using namespace std;
template
class LinearList
{
public:
virtual bool IsEmpty() const = 0; // 为空则返回true
virtual int Length() const = 0; // 返回长度
virtual bool Find(int i, T &x) const = 0; // 若a[i]存在则x = a[i]，返回true，不存在返回flase
virtual int Search(T x) const = 0; // 若存在等于x的元素则返回下标，否则返回-1
virtual bool Insert(int i, T x) = 0; // i == -1则x插在第一个元素之前， 否则x插在a[i]后，插入成功返回true
virtual bool Delete(int i) = 0; // 删除元素a[i]，删除成功返回true
virtual bool Update(int i, T x) = 0; // 修改元素a[i]为x，若修改成功则返回true
virtual void Output(ostream &out) const = 0;
/* data */
protected:
int n;
};
template
class SeqList:public LinearList
{
public:
SeqList(int mSize);
~SeqList() {delete []elements;}
bool IsEmpty() const;
int Length() const;
bool Find(int i, T &x) const;
int Search(T x) const;
bool Insert(int i, T x);
bool Delete(int i);
bool Update(int i, T x);
void Output(ostream &out) const;
void Reverse(); // 顺序表的逆置
bool DeleteX(const T &x); // 删除表中所有等于x的元素，成功则返回true
/* data */
private:
int maxLength, n;
T *elements;
};
template
SeqList::SeqList(int mSize)
{
maxLength = mSize;
elements = new T[maxLength];
n = 0;
}
template
bool SeqList::IsEmpty() const
{
return n == 0;
}
template
int SeqList::Length() const
{
return n;
}
template
bool SeqList::Find(int i, T &x) const
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
x = elements[i];
return true;
}
template
int SeqList::Search(T x) const
{
for(int i = 0; i < n; ++i)
if(elements[i] == x) return i;
return -1;
}
template
bool SeqList::Insert(int i, T x)
{
if(i < -1 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
if(n == maxLength) { // 数组满了
cout << "OverFlow" << endl << endl;
return false;
}
for(int j = n - 1; j > i; --j)
elements[j + 1] = elements[j];
elements[i + 1] = x;
n++;
return true;
}
template
bool SeqList::Delete(int i)
{
if(!n) { // 数组已经为空
cout << "UnderFlow" << endl << endl;
return false;
}
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
for(int j = i + 1; j < n; ++j)
elements[j - 1] = elements[j];
n--;
return true;
}
template
bool SeqList::Update(int i, T x)
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl << endl;
return false;
}
elements[i] = x;
return true;
}
template
void SeqList::Output(ostream &out) const
{
for(int i = 0; i < n; ++i)
out << elements[i] << " ";
out << endl << endl;
}
template
void Union(SeqList &A, SeqList &B)
{
T x;
for(int i = 0; i < B.Length(); ++i) {
B.Find(i, x);
if(A.Search(x) == -1) A.Insert(A.Length() - 1, x);
}
}
template
void SeqList::Reverse()
{
stack s;
for(int i = 0; i < n; ++i)
s.push(elements[i]);
for(int i = 0; i < n; ++i) {
elements[i] = s.top();
s.pop();
}
cout << "转置成功" << endl;
}
template
bool SeqList::DeleteX(const T &x)
{
int flag = n;
for(int i = 0; i < n; ++i)
if(elements[i] == x) {
Delete(i);
i--;
}
if(flag != n) return true;
return false;
}
int main(int argc, char const *argv[])
{
SeqList A(20), B(20);
for(int i = 0; i < 5; ++i)
A.Insert(i - 1, i); // A = {0, 1, 2, 3, 4}
cout << "顺序表A为：" << endl;
A.Output(cout);
for(int i = 5; i < 10; ++i)
B.Insert(i - 6, i); // B = {5, 6, 7, 8, 9}
cout << "顺序表B为：" << endl;
B.Output(cout);
A.Update(1, 5); // A = {0, 5, 2, 3, 4}
cout << "更新后顺序表A为：" << endl;
A.Output(cout);
int flag = A.Search(2); // 元素中是否有2
if(flag != -1) cout << "有等于2的元素" << endl;
else cout << "无等于2的元素" << endl;
int x;
A.Find(2, x); // x = a[2];
cout << "a[2] == " << x << endl;
B.Insert(-1, 0); // B = {0, 5, 6, 7, 8, 9}
cout << "插入0后顺序表B为：" << endl;
B.Output(cout);
B.Insert(3, 2); // B = {0, 5, 6, 7, 2, 8, 9}
cout << "插入2后顺序表B为：" << endl;
B.Output(cout);
B.Delete(4); // B = {0, 5, 6, 7, 8, 9}
cout << "删除4后顺序表B为：" << endl;
B.Output(cout);
Union(A, B); // 合并A, B到A A = {0, 2, 3, 4, 5, 6, 7, 8, 9}
cout << "合并A，B到A后顺序表A为：" << endl;
A.Output(cout);
B.Reverse(); // B = {9, 8, 7, 6, 5, 0};
cout << "转置后顺序表B为：" << endl;
B.Output(cout);
B.Insert(-1, 9);
cout << "插入9后顺序表B为：" << endl;
B.Output(cout);
x = 9;
if(B.DeleteX(x)) cout << "删除表中x成功" << endl;
else cout << "表中无等于x的元素" << endl;
cout << "顺序表B为：" << endl;
B.Output(cout);
return 0;
}
~~~
';
稀疏矩阵ADT_SeqTriple
最后更新于：2022-04-01 20:51:21
压缩存储稀疏矩阵的非零元素，存储非零元素的行号，列号，值。用一个三元式(row, col, value)唯一表示，可以按行排序或者列排
序，成为行三元组或列三元组。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
template
struct node
{
/* data */
int row, col;
T value;
};
template
class SeqTriple
{
public:
SeqTriple(int mSize);
~SeqTriple() { delete []trip; }
void Add(const SeqTriple &B, const SeqTriple &C) const;
void Mul(const SeqTriple &B, const SeqTriple &C) const;
void Transpose(SeqTriple &B);
friend istream &operator >> (istream &in, const SeqTriple &);
friend ostream &operator << (ostream &out, const SeqTriple &);
/* data */
private:
int maxSize, m, n, t; // 最大元素个数，稀疏矩阵的行数，列数以及非零元个数
node *trip;
};
~~~
下面重点分析三中转置稀疏的方法，转置A矩阵到B矩阵中。
1.将三元组A中所有元素的行，列交换后保存到B中，然后按B中的行号排序。时间复杂度：O(n*logn)
2.对三元组A扫描n遍(i = 0 ~ n -1)，每遍扫描t次(j = 0 ~ t - 1)。第I遍扫描时，找出A中列号col等于I第j行元素(可以是多个)，并将第j
行元素转置后存入B中的位置k。时间复杂度：O(n * t)
实现代码：
~~~
k = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < t; ++j)
if(A[j].col == i) {
B[k].col = A[j].row;
B[k].row = A[j].col;
B[k++].value = A[j].value;
}
~~~
3.方法2只用了一个指针k，用来指示转置后元素在B中存放的位置，因此在B中必须按0 ~ n - 1的顺序存放，导致反复扫描A，效率不
高。方法3使用n个指针k[i](n是指针的列数)，指向稀疏矩阵M中的第i列的第一非零元素在转置后的三元组B中的存放位置。
稀疏矩阵M中下标0列的第1个非零元素也是转置后的矩阵中下标0行的第1个非零元素，他在转置后的三元组B中的位置一定是0，
k[0] = 0。用num[0]表示M中下标0列的非零元素的个数，k[1]表示M中下标1列的第1个非零元素在B中的位置，k[1] = k[0] + num[0]。
可以得到以下式子：
k[0] = 0 i = 0
k[i] = k[i - 1] + num[i - 1] 1 <= i && i < n
时间复杂度：O(n + t)
实现代码：
~~~
template
void SeqTriple::Transpose(SeqTriple &B) const // 将this转置赋给B
{
int *num = new T[n], *k = new int[n];
B.m = n, B.n = m, B.t = t;
if(t > 0) {
memset(num, 0, sizeof(num));
for(int i = 0; i < t; ++i)
num[trip[i].col]++;
k[0] = 0;
for(int i = 0; i < n; ++i)
k[i] = k[i - 1] + num[i - 1];
for(int i = 0; i < t; ++i) { // 扫描this对象的三元组表
int j = k[trip[i].col]; // 求this对象的第i项在B中的位置j
B.trip[j].row = trip[i].col; // 将this对象的第i项转置到B中的位置j
B.trip[j].col = trip[i].row;
B.trip[j].value = trip[i].value;
}
}
delete [] k;
}
~~~
';