故人何以

用户名：gurenheyi

访问量：18429

签　名：

我变秃了，也变强了

等　　级
排　　名	344
经　　验	5334
参赛次数	3
文章发表	58
年　　龄	22
在职情况	学生
学　　校
专　　业

　　自我简介：

大鹏一日同风起，扶摇直上九万里。

TA的其他文章

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值-题解(C++代码)
浏览：439

C语言训练-尼科彻斯定理-题解(C++代码)
浏览：162

C语言训练-求车速-题解(C++代码)
浏览：275

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

数据结构-静态链表（C++代码）

　　作者: 故人何以　　　　发表时间：2019-12-30 18:46:13 浏览：448　|　评论：1　

原题链接：数据结构-静态链表

# 思路
搞清楚**静态链表**和**普通链表**的区别就可以了。
普通链表，节点的增加、删除，申请栈内存，通过new、delete操作。
静态链表，可用内存已经固定死了，要想实现节点的增加、删除，可增加一条空闲链表来管理存储空间。
space[0]，空闲链表的虚拟链表头。
space[1]，实际链表的虚拟链表头。
new 操作，等同于 摘除空闲链表的真实链表头。
delete 操作，等同于 将待删除节点倒插进空闲链表。
# 细节
注意输出格式要求。
还有删除节点的时候，为了真实模拟内存，不能将节点的内容清空。
# 代码
```cpp
#include <iostream>
#include <string>
#include <iomanip>

#define MAXSIZE 11					// 存储空间的大小

struct ListNode						// 链表节点
{
	std::string elem;
	int next;						// 值为0等同于空指针
};

ListNode space[MAXSIZE];			// 存储空间

int gDummy = 1;						// 链表相关信息
int gListSize = 0;

void initSpace();									// 初始化存储空间
void showSpace();									// 打印存储空间的状态
int searchElem(std::string elem);					// 返回 elem 所在节点的地址 
bool deleteListNode(int pos, std::string &elem);	// 删除第 pos 个节点
bool insertListNode(int pos, std::string elem);		// 在第 pos 个节点前插入节点

int main()
{
	initSpace();

std::string command, elem;
	int pos;
	while (std::cin >> command)
	{
		if ("show" == command)
		{
			showSpace();
			std::cout << "********************" << std::endl;
		}
		else if ("search" == command)
		{
			std::cin >> elem;
			pos = searchElem(elem);
			// 格式：2字符，右对齐
			std::cout << std::setw(2) << std::right << pos << std::endl;
			std::cout << "********************" << std::endl;
		}
		else if ("delete" == command)
		{
			std::cin >> pos;
			deleteListNode(pos, elem);
		}
		else if ("insert" == command)
		{
			std::cin >> pos >> elem;
			insertListNode(pos, elem);
		}
	}

return 0;
}

// 初始化存储空间，存储空间分为2条链表，活动链表、空闲链表
void initSpace()
{
	// 空闲链表，space[0]为虚拟链表头
	for (int i = 0; i < MAXSIZE; i++)
	{
		space[i].next = (i + 1) % MAXSIZE;
	}
	// 取 空闲链表 的头结点，作为 活动链表 的虚拟链表头
	space[0].next = 2;
	space[1].next = 0;
}

// 打印存储空间的状态
void showSpace()
{
	for (int i = 0; i < MAXSIZE; i++)
	{
		// 格式：姓氏8字符，左对齐；数字2字符，右对齐
		std::cout << std::setw(8) << std::left << space[i].elem;
		std::cout << std::setw(2) << std::right << space[i].next;
		std::cout << std::endl;
	}
}

// 返回 elem 所在节点的地址 
int searchElem(std::string elem)
{
	// 活动链表的头结点
	int ptr = space[gDummy].next;
	while (0 != ptr && space[ptr].elem != elem)
	{
		ptr = space[ptr].next;
	}
	return ptr;
}

// 删除第 pos 个节点
bool deleteListNode(int pos, std::string &elem)
{
	// 范围检查
	if (pos <= 0 || pos > gListSize)
	{
		return false;
	}

int ptr = gDummy;
	int cnt = 0;
	// 找到第 pos - 1 个节点
	while (cnt < pos - 1)
	{
		ptr = space[ptr].next;
		cnt++;
	}

int node = space[ptr].next;	// 待删除节点
	space[ptr].next = space[node].next;
	gListSize--;

// 普通链表，delete node
	// 静态链表，倒插进空闲链表
	space[node].next = space[0].next;
	space[0].next = node;
	// 不能清空节点的内容，否则不能AC
	// space[node].elem = "";

return true;
}

// 在第 pos 个节点前插入节点
bool insertListNode(int pos, std::string elem)
{
	// 范围检查
	if (pos <= 0 || pos > gListSize + 1 || MAXSIZE - 2 == gListSize)
	{
		return false;
	}

int ptr = gDummy;
	int cnt = 0;
	// 找到第 pos - 1 个节点
	while (cnt < pos - 1)
	{
		ptr = space[ptr].next;
		cnt++;
	}

// 普通链表，new ListNode(elem, nullptr)
	// 静态链表，拿出空闲链表的头结点
	int node = space[0].next;
	space[0].next = space[node].next;

// 插入
	space[node].elem = elem;
	space[node].next = space[ptr].next;
	space[ptr].next = node;

gListSize++;
	return true;
}
```
2019-12-30 18:46:13 星期一

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

SinzoL

清晰

2022-07-10 06:25:28

故人何以

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

【数组的距离】（C语言代码）

A+B for Input-Output Practice (I) （C++代码）

点我有惊喜！你懂得！

C二级辅导-等差数列（C语言代码）

数据结构-静态链表（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【排队买票】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

字符逆序（C语言代码）

DNA （C语言代码）

Cylinder （C语言描述+详细分析）

时间转换（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

故人何以

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

【数组的距离】 （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

点我有惊喜！你懂得！

C二级辅导-等差数列 （C语言代码）

数据结构-静态链表 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【排队买票】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

字符逆序 （C语言代码）

DNA （C语言代码）

Cylinder （C语言描述+详细分析）

时间转换 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

【数组的距离】（C语言代码）

C二级辅导-等差数列（C语言代码）

数据结构-静态链表（C++代码）

　　评论区

【排队买票】（C语言代码）

字符逆序（C语言代码）

时间转换（C语言代码）