深入理解数据结构——模拟链表

#include <iostream>
#include <string>

using namespace std;

typedef int Etype;     // 自定义链表的数据元素为整数。
//定义数据元素节点结构
typedef struct SimNode
{
	Etype data;          // 存放结点的数据元素。
	int next;           // 存放下一个元素地址。
};

typedef string HeadEtype;     // 自定义表头的数据元素为整数。
//定义表头结构
typedef struct SimChainList
{
	SimNode *node;       //用于指向数组的指针
	int maxsize;		//用于指定存储值大小
	int first;          //指向第一个节点
};

//模拟链表初始化
void CreatSimChainList(SimChainList &L,int MaxSpaceSize) {

	L.maxsize = MaxSpaceSize;
	L.node = new SimNode[L.maxsize];//新建一个结构体数组
	for (int i = 0; i < L.maxsize-1; i++) {
		L.node[i].next = i + 1;//使得每个元素的地址为序号
	}
	L.node[L.maxsize - 1].next = -1;//最后一个元素的后驱地址设为-1；
	L.first = 0;//第一个数据点的地址定义为0
}

//模拟链表中节点空间的分配
int GetNode(SimChainList&L) {
	if (L.first == -1) return -1;//如果为空表
	int i = L.first;//表头指向的第一个元素未必是1，可能是10
	L.first = L.node[i].next;//表头指针指向链表下一节点
	return i;
}

//模拟链表中节点空间的释放
void FreeNode(SimChainList &L,int i) {
	L.node[i].next = L.first;
	L.first = i;
}

//模拟链表的第k个节点后面插入节点
bool InsertSimChainList(SimChainList& L, int& first, int k, Etype& x) {
	if (k < 0) return false;//如果插入节点小于0

	int current = first;//第一个元素的序号
	for (int index = 1; index < k && current != -1; index++){//找到第k个元素
		current = L.node[current].next;
	}
	if (k > 0 && current == -1) return false;//当前节点为内存空间的最后一个节点，所以不能插入了
	int q = GetNode(L);//获取一个节点空间
	L.node[q].data = x;//将x存入q空间
	if (k) {
		L.node[current].next = q;//将q插到k节点后面
		L.node[q].next = L.node[current].next;//将k+1节点后移
	}
	else {
		//k插入第一个节点，作为链表的首节点		
		L.node[q].next = first;//把q插在第一个节点前面，q后面的节点就是first
		q = first;//再把q节点的序号，改为第一个节点。
	}
	return true;
}

//在first指向的链表中删除第k个节点
bool DeleteSimChainList(SimChainList &L,int &first,int k) {
	if (k < 1 || first == -1) return false;
	int current = first;//指向链表第一个元素
	if (k == 1)//删除第一个节点
	{
		first = L.node[first].next;//将第一个元素更换为第二个元素
	}
	else {
		int q = first;
		for (int index = 1; index < k - 1 && q != -1;index++) {
			q = L.node[q].next;
		}
		current = q;//
		if (q == -1 || L.node[q].next == -1) return false;//当前元素为空，或者下一个元素为空

		q = L.node[q].next;//把第k个元素替换成k+1个元素
		L.node[q].next = L.node[current].next;//q当前指向k+1;qnext就是k+2的节点，q的下一个节点换成原表k的下一个节点


	}
	FreeNode(L, current);//释放k节点空间
	return true;
}

//模拟链表的输出
void OutputSimChainList(SimChainList& L, int& first) {
	int current = first;
	while (current != -1) {
		cout << L.node[current].data << endl;
		current = L.node[current].next;
	}
}