三十一、动态顺序表
示例（数据元素为整数）：
#include <iostream>
using namespace std;
#define INITSIZE 5 // 顺序表的初始大小。
#define EXTSIZE 3 // 每次扩展元素的个数。
typedef int ElemType; // 给数据元素的数据类型起个别名。
struct SeqList // 动态顺序表的结构体。
{
ElemType *data; // 用动态数组存储顺序表中的元素。
unsigned int maxsize; // 顺序表的当前容量。
size_t length; // 顺序表的表长（有效元素的个数）。
};
// 清空顺序表。
void ClearList(SeqList& LL)
{
LL.length = 0; // 表长置为 0。
memset(LL.data, 0, sizeof(ElemType) * LL.maxsize); // 清空数组。
//memset(&LL, 0, sizeof(SeqList)); // 清空结构体，不能启用这行代码。
}
// 初始化顺序表
void InitList(SeqList& LL)
{
LL.maxsize = INITSIZE; // 指定顺序表的容量为缺省值。
LL.data = new ElemType[LL.maxsize]; // 给数组分配内存空间。
ClearList(LL); // 清空顺序表。
}
// 销毁顺序表 LL。
void DestroyList(SeqList& LL)
{
delete[] LL.data; // 释放数组的内存空间。
LL.data = nullptr; // 指针置空。
LL.maxsize = 0; // 顺序表的容量置为 0。
LL.length = 0; // 顺序表的表长置为 0。
}
// 扩展顺序表的内存空间，返回值：false-失败；true-成功。
bool ExtList(SeqList& LL)
{
// 分配新的内存空间。
ElemType* newdata = new (std::nothrow) ElemType[LL.maxsize + EXTSIZE];
// 如果分配失败，返回 0。
if (newdata == nullptr) return false;
// 把新分配的内存清空。
memset(newdata, 0, sizeof(ElemType) * (LL.maxsize + EXTSIZE));
// 把顺序表中原来的内容复制到新分配的内存空间中。
memcpy(newdata, LL.data, sizeof(ElemType) * LL.length);
// 释放原来的内存空间。
delete [] LL.data;
// 把顺序表数据元素的指针指向新分配的内存空间。
LL.data = newdata;
// 重置顺序表的 maxsize 变量。
LL.maxsize = LL.maxsize + EXTSIZE;
return true;
}
// 在顺序表 LL 的第 pos 个位置插入元素 ee，返回值：true-成功；false-失败。
// 注意：在数据结构中，位置 pos 从 1 开始，不是从 0 开始。
// 6 8 2 1 12 4 5 3 7 // 顺序表中的元素。
// 1 2 3 4 5 6 7 8 9 10 // 位置。
// 0 1 2 3 4 5 6 7 8 9 // 数组下标。
bool InsertList(SeqList& LL, const size_t pos, const ElemType& ee)
{
// 如果空间不够了，就扩展内存空间。
if (LL.length == LL.maxsize) { if (ExtList(LL) == false) { cout << "护展顺序表失败。\n";
return false; } }
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length + 1)) {
cout << "插入位置" << pos << "不合法，应该在 1-" << LL.length + 1 << "之间。\n";
return false;
}
// 把 pos 和 pos 之后的元素后移。
if (pos < LL.length + 1)
memmove(LL.data + pos, LL.data + pos - 1, (LL.length - pos + 1) * sizeof(ElemType));
// 把元素 ee 的值赋值给顺序表的第 pos 个元素。
//memcpy(&LL.data[pos - 1], &ee, sizeof(ElemType)); // 采用 memcpy 是为了兼容 ee 为
结构体的情况。
LL.data[pos - 1] = ee; // 在 C++中，结构体也可以用=赋值。
LL.length++; // 表长加 1。
return true;
}
// 求顺序表的表长，返回值表 LL 中元素的个数。
size_t LengthList(const SeqList& LL)
{
return LL.length;
}
// 获取顺序表中第 pos 个元素的值，存放在 ee 中，返回值：false-失败；true-成功。
bool GetElem(const SeqList LL, const size_t pos, ElemType& ee)
{
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length)) return false;
ee = LL.data[pos - 1];
return true;
}
// 在顺序表 LL 的头部插入元素 ee。
bool PushFront(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, 1, ee);
}
// 在顺序表 LL 的尾部插入元素 ee。
bool PushBack(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, LL.length + 1, ee);
}
// 查找 ee 在顺序表 LL 中的位置，返回值：0-元素 ee 在表 LL 中不存在，>0 元素 ee 在表 LL 中的
位置。
size_t FindElem(const SeqList& LL, const ElemType& ee)
{
for (size_t ii = 0; ii < LL.length; ii++)
{
// 如果元素 ee 为结构体，以下代码要修改（比较数据元素的关键字）。
if (LL.data[ii] == ee) return ii + 1;
}
return 0;
}
// 删除顺序表 LL 中的第 pos 个元素，返回值：0-位置 pos 不合法；1-成功。
bool DeleteElem(SeqList& LL, const size_t pos)
{
// 判断位置 pos 是否合法，注意，pos 从 1 开始，不是从 0 开始，0 不符合人类的习惯。
if ((pos < 1) || (pos > LL.length)) {
cout << "删除位置" << pos << "不合法，应该在 1-" << LL.length << "之间。\n";
return false;
}
// 把 pos 之后的元素前移。
memmove(&LL.data[pos - 1], &LL.data[pos], sizeof(ElemType) * (LL.length - pos));
LL.length--; // 表长减 1。
return true;
}
// 删除顺序表 LL 中头元素。
bool PopFront(SeqList& LL)
{
return DeleteElem(LL, 1);
}
// 删除顺序表 LL 中尾元素。
bool PopBack(SeqList& LL)
{
return DeleteElem(LL, LL.length);
}
// 判断顺序表是否为空，返回值：true-空，false-非空。
bool IsEmpty(const SeqList& LL)
{
if (LL.length == 0) return true;
return false;
}
// 显示顺序表中全部的元素。
void PrintList(const SeqList& LL)
{
if (LL.length == 0) { cout << "表为空。\n"; return; }
for (size_t ii = 0; ii < LL.length; ii++)
{
cout << LL.data[ii] << " ";
}
cout << endl;
}
int main()
{
SeqList LL; // 创建顺序表。
InitList(LL); // 初始化顺序表。
ElemType ee; // 创建一个数据元素。
cout << "在表中插入元素（1、2、3、4、5、6、7、8、9、10）。\n";
ee = 1; InsertList(LL, 1, ee);
ee = 2; InsertList(LL, 1, ee);
ee = 3; InsertList(LL, 1, ee);
ee = 4; InsertList(LL, 1, ee);
ee = 5; InsertList(LL, 1, ee);
ee = 6; InsertList(LL, 1, ee);
ee = 7; InsertList(LL, 1, ee);
ee = 8; InsertList(LL, 1, ee);
ee = 9; InsertList(LL, 1, ee);
ee = 10; InsertList(LL, 1, ee);
PrintList(LL);
cout << "在表头插入元素（11），表尾插入元素（12）。\n";
ee = 11; PushFront(LL, ee);
ee = 12; PushBack(LL, ee);
PrintList(LL);
cout << "在第 5 个位置插入元素（13）。\n";
ee = 13; InsertList(LL, 5, ee);
PrintList(LL);
cout << "删除表中第 7 个元素。\n";
DeleteElem(LL, 7); PrintList(LL);
cout << "删除表头元素。\n";
PopFront(LL); PrintList(LL);
cout << "删除表尾元素。\n";
PopBack(LL); PrintList(LL);
GetElem(LL, 5, ee);
cout << "第 5 个元素的值是" << ee << "。\n";
ee = 8;
cout << "元素值为 8 的位置是=" << FindElem(LL, ee) << endl;
DestroyList(LL); // 销毁顺序表。
}
三十二、单链表的建立
示例：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链表的数据元素为整数。
struct LNode // 单链表的结点。
{
ElemType data; // 存放结点的数据元素。
struct LNode* next; // 指向下一个结点的指针。
};
// 初始化链表，返回值：失败返回 nullptr，成功返回头结点的地址。
LNode* InitList()
{
LNode* head = new (std::nothrow) LNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
return head; // 返回头结点。
}
// 销毁链表。
void DestroyList(LNode* head)
{
// 销毁链表是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 在链表的头部插入元素（头插法），返回值：false-失败；true-成功。
bool PushFront(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = head->next;
head->next = tmp;
return true;
}
// 显示链表中全部的元素。
void PrintList(const LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; }
LNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 在链表的尾部插入元素（尾插法），返回值：false-失败；true-成功。
bool PushBack(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到最后一个结点，pp 将指向尾结点（最后一个结点）。
while (pp->next != nullptr) pp = pp->next;
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = nullptr;
pp->next = tmp;
return true;
}
int main()
{
LNode* LL = InitList(); // 初始化链表 LL。
cout << "用头插法向链表中插入元素（1、2、3）。\n";
PushFront(LL, 1);
PushFront(LL, 2);
PushFront(LL, 3);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "用尾插法向链表中插入元素（4、5、6）。\n";
PushBack(LL, 4);
PushBack(LL, 5);
PushBack(LL, 6);
PrintList(LL); // 把链表中全部的元素显示出来。
DestroyList(LL); // 销毁链表 LL。
}
三十三、单链表的其它操作
示例：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链表的数据元素为整数。
struct LNode // 单链表的结点。
{
ElemType data; // 存放结点的数据元素。
struct LNode* next; // 指向下一个结点的指针。
};
// 初始化链表，返回值：失败返回 nullptr，成功返回头结点的地址。
LNode* InitList()
{
LNode* head = new (std::nothrow) LNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
return head; // 返回头结点。
}
// 销毁链表。
void DestroyList(LNode* head)
{
// 销毁链表是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 在链表的头部插入元素（头插法），返回值：false-失败；true-成功。
bool PushFront(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = head->next;
head->next = tmp;
return true;
}
// 显示链表中全部的元素。
void PrintList(const LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; }
LNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 在链表的尾部插入元素（尾插法），返回值：false-失败；true-成功。
bool PushBack(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到最后一个结点，pp 将指向尾结点（最后一个结点）。
while (pp->next != nullptr) pp = pp->next;
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = nullptr;
pp->next = tmp;
return true;
}
// 求链表的表长，返回值：>=0-表 LL 结点的个数。
size_t ListLength(LNode* head)
{
//if (head == nullptr) { cout << "链表不存在。\n"; return 0; }
//LNode* pp = head->next; // 头结点不算，从第 1 个结点开始。
//size_t length = 0;
//while (pp != nullptr) { pp = pp->next; length++; }
//return length;
// 不使用临时变量，如何计算链表（包括头结点）的长度？
if (head==nullptr) return 0;
return ListLength(head->next)+1;
}
// 删除链表第一个结点。
bool PopFront(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head->next; // pp 指向第一个节点。
head->next = head->next->next; // 修改头结点的 next 指针。
delete pp; // 删除第一个节点。
return true;
}
// 删除链表最后一个结点。
bool PopBack(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
// 必须加上这个判断，否则下面的循环 pp->next->next 不成立。
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到倒数第二个结点（包括头结点）。
while (pp->next->next != nullptr) pp = pp->next;
delete pp->next; // 释放最后一个结点。
pp->next = nullptr; // 倒数第二个结点成了最后一个结点。
return true;
}
// 清空链表，清空链表是指释放链表全部的结点，但是，不释放头结点。
void ClearList(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; } // 判断链表是否存在。
LNode* tmp1;
LNode* tmp2 = head->next; // 从头结点的下一个结点开始释放。
while (tmp2 != nullptr)
{
tmp1 = tmp2->next;
delete tmp2;
tmp2 = tmp1;
}
head->next = nullptr; // 这行代码一定不能少，否则会留下野指针。
}
// 查找元素 ee 在链表中的结点地址，如果没找到返回 nullptr，否则返回结点的地址。
LNode* LocateElem(const LNode* head, const ElemType& ee)
{
LNode* pp = head->next; // 从第 1 个存放数据结点开始。
while (pp != nullptr)
{
// 如果数据元素是结构体，以下代码要修改成比较关键字。
if (pp->data == ee) return pp;
pp = pp->next;
}
return pp;
}
// 获取链表中第 n 个结点，成功返回结点的地址，失败返回 nullptr。
// 注意，n 可以取值为 0，表示头结点。
LNode* LocateNode(LNode* head, unsigned int n)
{
if (head == nullptr) { cout << "链表不存在。\n"; return nullptr; }
LNode* pp = head; // 指针 pp 指向头结点，逐步往后移动，如果为空，表示后面没结
点了。
unsigned int ii = 0; // ii 指向的是第几个结点，从头结点 0 开始，pp 每向后移动一次，
ii 就加 1。
while ((pp != nullptr) && (ii < n))
{
pp = pp->next; ii++;
}
if (pp == nullptr) { cout << "位置" << n << "不合法，超过了表长。\n"; return nullptr; }
return pp;
}
// 在指定结点 pp 之后插入元素 ee。
bool InsertNextNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
LNode* tmp = new LNode;
tmp->data = ee;
tmp->next = pp->next;
pp->next = tmp;
return true;
}
// 在指定结点 pp 之前插入元素 ee。
bool InsertPriorNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
// 在指定结点 pp 之前插入采用偷梁换柱的方法：
// 1、分配一个新的结点；
// 2、把 pp 结点的数据和指针复制到新结点中。
// 3、把待插入元素的数据存入 pp 结点中。
LNode* tmp = new LNode;
// 把 pp 结点的数据和指针复制到 tmp 中。
tmp->data = pp->data;
tmp->next = pp->next;
// 把待插入的元素存入 pp 中。
pp->data = ee;
pp->next = tmp;
return true;
}
// 删除指定结点。
bool DeleteNode1(LNode* pp)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
if (pp->next != nullptr) // 如果结点 pp 后面还有结点。
{
// 删除指定结点的思想是：1）把 pp 后继结点的数据和 next 指针复制到 pp 结点；2）删
除 pp 结点的后继结点。
LNode* tmp = pp->next; // tmp 指向 pp 的后继结点。
pp->data = tmp->data; // 把后继结点的数据复制到 pp 结点中。
pp->next = tmp->next; // 把 pp 的 next 指向后继结点的 next。
delete tmp; // 释放后继结点。
return true;
}
else // 如果结点 pp 是最后一个结点。
{
return false; // 可以在函数外面调用 PopBack()函数。
}
}
int main()
{
LNode* LL = InitList(); // 初始化链表 LL。
cout << "用头插法向链表中插入元素（1、2、3）。\n";
PushFront(LL, 1);
PushFront(LL, 2);
PushFront(LL, 3);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "用尾插法向链表中插入元素（4、5、6）。\n";
PushBack(LL, 4);
PushBack(LL, 5);
PushBack(LL, 6);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "链表的表长（包括头结点）：" << ListLength(LL) << endl;
//PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL); PopFront(LL);
PopFront(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
//PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL); PopBack(LL);
PopBack(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
//ClearList(LL);
//PrintList(LL); // 把链表中全部的元素显示出来。
LNode *p1=LocateElem(LL, 4);
cout << "元素为 4 的结点的地址是：" << p1 << "，值是：" << p1->data << endl;
LNode* p2 = LocateNode(LL, 3);
cout << "位序为 3 的结点的地址是：" << p2 << "，值是：" << p2->data << endl;
cout << "在" << p2->data << "之后插入元素 8。" << endl;
InsertNextNode(p2, 8);
PrintList(LL); // 把链表中全部的元素显示出来。
cout << "在" << p2->data << "之前插入元素 7。" << endl;
InsertPriorNode(p2, 7);
PrintList(LL); // 把链表中全部的元素显示出来。
DestroyList(LL); // 销毁链表 LL。
}