数据结构之多重表的定义与实现

发表于 | 分类于

多重表基础

多重表是《数据结构与算法分析：C语言描述》一书中给出的概念，书中给出了一张多重表示意图，如下所示：
多重表示意图

从图中可以看出多重表是指一个节点有多个链穿过，和矩阵压缩存储中的十字链表十分相似。书中是以大学选课为例说明的，本处以书中例子为蓝本设计实现一种多重表。由于书中并没有给出具体的API，故本文主要根据自己的理解以及结合普通链表的API来编写ADT。本处主要实现如下几个功能：

  • 多重表每条链长度
  • 多重表插入、删除节点
  • 多重表清空

根据图中示意，我们很容易想到表头统一采用数组来管理，每个链表内部保持有序便于插入删除。

多重表的定义与实现

根据书中多重表示意图，我们可以设计多重表的结构如下所示：

1
2
3
4
5
6
7
8
9
10
11
struct MultiNode
{
        unsigned int rowIndex; /*节点所在行*/
        unsigned int colIndex; /*节点所在列*/
        MultiNode *rowNext; /*所在行下一个节点*/
        MultiNode *colNext; /*列所在下一个节点*/
        MultiNode() : rowIndex(0), colIndex(0),
                  rowNext(nullptr), colNext(nullptr) {}
        MultiNode(unsigned int row, unsigned int col) : rowIndex(row), colIndex(col),
                                                 rowNext(nullptr), colNext(nullptr) {}
};

在实现多重表时，行和列分别定义一个哑节点数组，具体实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MultiTable
{
public:
        MultiTable(unsigned int row, unsigned int col);
        ~MultiTable();
        void MakeEmpty(); /*清空整个多重表*/
        bool IsRowEmpty(unsigned int rowIndex); /*某行链表是否为空*/
        bool IsColEmpty(unsigned int colIndex); /*某列链表是否为空*/
        void DeleteNode(unsigned int row, unsigned int col); /*删除某个节点*/
        void InsertNode(unsigned int row, unsigned int col); /*插入某个节点某个节点*/
        void PrintRowList(unsigned int rowIndex); /*打印某行*/
        void PrintColList(unsigned int ColIndex); /*打印某列*/
private:
        unsigned int rowSize;
        unsigned int colSize;
        MultiNode *rowArray; /*行数组*/
        MultiNode *colArray; /*列数组*/
};

如上所示，多重表主要是保存行数和列数以及对应的数组。以下分别实现个函数。

  • 构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MultiTable::MultiTable(unsigned int row, unsigned int col) : rowSize(row), colSize(col),
                                               rowArray(nullptr),colArray(nullptr)
{
        rowSize = rowSize == 0 ? 1 : rowSize;
        colSize = colSize == 0 ? 1 : colSize;

        rowArray = new MultiNode[rowSize];
        colArray = new MultiNode[colSize];
        /*做成循环链表*/
        for (unsigned int i = 0; i < rowSize; i++) {
                rowArray[i].rowNext = &rowArray[i];
        }

        for (unsigned int i = 0; i < colSize; i++) {
                colArray[i].colNext = &colArray[i];
        }
}
  • 析构函数
1
2
3
4
5
6
MultiTable::~MultiTable()
{
        MakeEmpty();
        delete [] rowArray;
        delete [] colArray;
}
  • 清空函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void MultiTable::MakeEmpty()
{
        /*先把行或者列哑节点指向自己*/
        for (unsigned int i = 0; i < colSize; i++) {
                colArray[i].colNext = &colArray[i];
        }
        for (unsigned int i = 0; i < rowSize; i++) {
                MultiNode *cycleIter = rowArray[i].rowNext;
                /*遍历整个链表删除之*/
                while (cycleIter != &rowArray[i]) {
                        rowArray[i].rowNext = cycleIter->rowNext;
                        delete cycleIter;
                        cycleIter = rowArray[i].rowNext;
                }
        }
}
  • 判断某行链表是否为空，如果行不存在也返回false，行从1开始
1
2
3
4
5
6
7
bool MultiTable::IsRowEmpty(unsigned int rowIndex)
{
        if (rowIndex <= 0 || rowIndex > rowSize) {
                return false;
        }
        return rowArray[rowIndex-1].rowNext == &rowArray[rowIndex-1];
}
  • 判断某列链表是否为空，如果行不存在也返回false，列从1开始计算
1
2
3
4
5
6
7
bool MultiTable::IsColEmpty(unsigned int colIndex)
{
        if (colIndex <= 0 || colIndex > colSize) {
                return false;
        }
        return colArray[colIndex-1].colNext == &colArray[colIndex-1];
}
  • 删除某行某列对应的节点，不存在就什么也不做，行列均从1开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void MultiTable::DeleteNode(unsigned int row, unsigned int col)
{
        if (row <= 0 || row > rowSize || col <= 0 || col > colSize) {
                return;
        }
        MultiNode *rowIter = &rowArray[row-1]; /*行链表*/
        MultiNode *colIter = &colArray[col-1]; /*列链表*/
        while (rowIter->rowNext != &rowArray[row-1] && rowIter->rowNext->colIndex < col) {
                rowIter = rowIter->rowNext;
        }

        while (colIter->colNext != &colArray[col-1] && colIter->colNext->rowIndex < row) {
                colIter = colIter->colNext;
        }

        bool nodeExist = rowIter->rowNext != &rowArray[row-1] && rowIter->rowNext->colIndex == col;
        nodeExist = nodeExist &&  colIter->colNext != &colArray[col-1] && colIter->colNext->rowIndex == row;
        if (nodeExist) {
                MultiNode *toBeDeleteNode = rowIter->rowNext; /*待删除节点*/
                rowIter->rowNext = toBeDeleteNode->rowNext;
                colIter->colNext = toBeDeleteNode->colNext;
                delete toBeDeleteNode;
        }
        return;
}
  • 在一行中插入节点，如果已存在就更新（本处啥也不做）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void MultiTable::InsertNode(unsigned int row, unsigned int col)
{
        if (row <= 0 || row > rowSize || col <= 0 || col > colSize) {
                return;
        }

        MultiNode *rowIter = &rowArray[row-1]; /*行链表*/
        MultiNode *colIter = &colArray[col-1]; /*列链表*/
        while (rowIter->rowNext !=  &rowArray[row - 1] && rowIter->rowNext->colIndex < col) {
                rowIter = rowIter->rowNext;
        }

        while (colIter->colNext != &colArray[col-1] && colIter->colNext->rowIndex < row) {
                colIter = colIter->colNext;
        }
        bool nodeExist = rowIter->rowNext != &rowArray[row-1] && rowIter->rowNext->colIndex == col;
        nodeExist = nodeExist &&  colIter->colNext != &colArray[col-1] && colIter->colNext->rowIndex == row;
        if (!nodeExist) {
                MultiNode *newNode = new MultiNode(row, col); /*新建节点*/
                newNode->rowNext = rowIter->rowNext;
                newNode->colNext = colIter->colNext;
                rowIter->rowNext = newNode;
                colIter->colNext = newNode;
        }
        return;
}
  • 打印某一行（行不存在不做任何事）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void MultiTable::PrintRowList(unsigned int rowIndex)
{
        if (rowIndex <= 0 || rowIndex > rowSize) {
                return;
        }
        MultiNode *rowIter = rowArray[rowIndex-1].rowNext; /*初始化遍历迭代器*/
        cout << "Row "<< rowIndex << " Data is follow：" <<endl;
        while (rowIter != &rowArray[rowIndex-1]) {
                cout << "(" << rowIter->rowIndex << "," << rowIter->colIndex << ");";
                rowIter = rowIter->rowNext;
        }
        cout << endl;
        return;
}
  • 打印某一行（列不存在不做任何事）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void MultiTable::PrintColList(unsigned int colIndex)
{
        if (colIndex <= 0 || colIndex > colSize) {
                return;
        }
        MultiNode *colIter = colArray[colIndex-1].colNext; /*初始化遍历迭代器*/
        cout << "Col "<< colIndex << " Data is follow：" <<endl;
        while (colIter != &colArray[colIndex-1]) {
                cout << "(" << colIter->rowIndex << "," << colIter->colIndex << ");";
                colIter = colIter->colNext;
        }
        cout << endl;
        return;
}

代码测试

就以书中图中为例，进行一些插入删除操作最后打印结果来检测代码是否正确，检测代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <vector>
#include <random>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <functional>
using namespace std;
using namespace chrono;

int main()
{
	MultiTable testTable(4, 5);

        testTable.InsertNode(1, 1);
        testTable.InsertNode(1, 3);
        testTable.InsertNode(1, 4);

        testTable.InsertNode(4, 4);
        testTable.InsertNode(4, 2);

        testTable.InsertNode(3, 3);
        testTable.InsertNode(3, 4);
        testTable.InsertNode(3, 1);
        testTable.InsertNode(3, 5);

        testTable.InsertNode(2, 2);
        testTable.InsertNode(2, 5);

        cout<< testTable.IsRowEmpty(1) << endl;
        cout<< testTable.IsRowEmpty(2) << endl;
        cout<< testTable.IsRowEmpty(3) << endl;
        cout<< testTable.IsRowEmpty(4) << endl;

        cout<< testTable.IsColEmpty(1) << endl;
        cout<< testTable.IsColEmpty(2) << endl;
        cout<< testTable.IsColEmpty(3) << endl;
        cout<< testTable.IsColEmpty(4) << endl;
        cout<< testTable.IsColEmpty(5) << endl;

        testTable.DeleteNode(2, 2);
        testTable.DeleteNode(2, 5);

        cout<< testTable.IsRowEmpty(2) << endl;

        testTable.MakeEmpty();

        cout<< testTable.IsRowEmpty(1) << endl;
        cout<< testTable.IsRowEmpty(2) << endl;
        cout<< testTable.IsRowEmpty(3) << endl;
        cout<< testTable.IsRowEmpty(4) << endl;

        cout<< testTable.IsColEmpty(1) << endl;
        cout<< testTable.IsColEmpty(2) << endl;
        cout<< testTable.IsColEmpty(3) << endl;
        cout<< testTable.IsColEmpty(4) << endl;
        cout<< testTable.IsColEmpty(5) << endl;


        testTable.InsertNode(1, 1);
        testTable.InsertNode(1, 3);
        testTable.InsertNode(1, 4);

        testTable.InsertNode(4, 4);
        testTable.InsertNode(4, 2);

        testTable.InsertNode(3, 3);
        testTable.InsertNode(3, 4);
        testTable.InsertNode(3, 1);
        testTable.InsertNode(3, 5);

        testTable.InsertNode(2, 2);
        testTable.InsertNode(2, 5);

        testTable.PrintRowList(1);
        testTable.PrintRowList(2);
        testTable.PrintRowList(3);
        testTable.PrintRowList(4);

        testTable.PrintColList(1);
        testTable.PrintColList(2);
        testTable.PrintColList(3);
        testTable.PrintColList(4);
        testTable.PrintColList(5);

	return 0;
}

参考资料

数据结构与算法分析