五、线性表的链式表示和实现

• 1、基本概念
• 2、带头结点的单向链表
• THE END

链式存储结构
qquad 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
qquad 线性表的链式表示又称为非顺序映像或者链式映像;
qquad 用一组物理位置任意的存储单元来存放线性表的数据元素；
qquad 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上；
qquad 链表中的元素的逻辑次序和物理次序不一定相同。
qquad 单向链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。

qquad 结点： 数据元素的存储映像。由数据域和指针域两部分组成；
qquad 链表： n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构。
qquad 单链表： 结点只有一个指针域的链表，称为单向链表或者线性链表；

qquad 双链表： 结点有两个指针域的链表；

qquad 循环链表： 首尾相接的链表称为循环链表；

qquad 头指针： 是指向链表中第一个结点的指针；
qquad 首元结点： 是指链表中存储第一个数据元素 a 1 a_1 a1​的结点；
qquad 头结点： 是在链表的首元结点之前附设的一个结点；

qquad 对于无头结点的单链表，头指针为空时表示空表；
qquad 对于有头结点的单链表，当头结点指向空时，表示空表；
qquad 添加头结点的好处： 首先便于首元结点的处理，首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一样，无需进行特殊处理；其次是便于空表和非空表的统一处理，无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了；
qquad 头结点数据域存放内容： 头结点的数据域可以为空，也可以存放表长度等附加信息，但是注意头结点不计入链表的长度值；
链表的特点：
qquad 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
qquad 访问时只能通过头指针进入链表，并通过每个节点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点花费的时间不同；(链表采用顺序存取法！顺序表示随机存取法)

qquad 单向链表由表头唯一确定，因此单向链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。
qquad 单向链表的存储结构包括“数据域”+“指针域”两部分，其中“数据域”用来存放不同种类的数据，“指针域”存放一个结构体指针，指向下一个链表中的下一个结点。

//定义链表结构体
typedef class Lnode
{
	ElemType data;		//结点的数据域
	Lnode *next;		//结点的指针域
}Lnode, *linkList;

单链表的初始化
qquad 即构造一个空表，生成新节点作为头结点，用头指针L指向头结点，将头结点的指针域置空。

template 
struct Node
{//结点定义
	Elem data;		//数据域
	Node *next;		//指针域
};

template 
class MyList
{//链表定义
private:
	Node *head;
	int cnt;
public:
	MyList();
	~MyList();
	void IsEmpty();		//判断链表是否为空

};

template 
MyList::MyList()
{//链表的初始化
	head = new Node;
	head->next = nullptr;
	cnt = 0;
}

template 
MyList::~MyList()
{//析构链表，删除在类中申请的空间
	Node *rec = head;
	while (rec != nullptr)
	{
		Node *t = rec;
		rec = rec->next;
		delete t;
	}
	head = nullptr;
	cnt = 0;
}

template
void MyList::IsEmpty()
{//判断链表是否为空表
	return head->next == nullptr;
}

template 
void MyList::Clear()
{//除了头结点之后，删除链表中的其他结点
	Node *rec = head->next;
	while (rec != nullptr)
	{
		Node *t = rec;
		rec = rec->next;
		delete t;
	}
	head->next = nullptr;
	cnt = 0;
}

template
int MyList::GetLength()
{//获取链表的长度
	return cnt;
}

template
Node* MyList::GetAddress(Elem data)
{//按值查找某个节点，返回节点的地址
	Node *rec = head;
	while (rec  && rec->data != data)
		rec = rec->next;
	return rec;
}

template
int MyList::GetIdx(Elem data)
{//按值查找某个节点，返回节点的索引
	Node *rec = head;
	int n = -1;
	while (rec != nullptr)
	{
		if (rec->data == data)
			return n;
		rec = rec->next;
		++n;
	}
	return -1;//若链表中没有data，则返回-1

}

qquad 因为线性表只能顺序存取，即在查找是要从头指针找起，查找的时间复杂度为 O ( n ) O(n) O(n)。

template
void  MyList::InsertElem(int i, Elem data)
{//在索引位置i之前插入元素Elem
	if (i < 0)return;		//插入位置有问题
	Node *rec = head;
	int n = -1;
	while (n < i-1 && rec)
	{
		rec = rec->next;
		++n;
	}
	if (rec == nullptr)return;//插入位置有问题
	//构建新的data节点
	Node *newNode = new Node(data);
	newNode->next = rec->next;
	rec->next = newNode;
}

template
void MyList::DeleteElem(int pos)
{//删除位置i的元素
	if (pos < 0 || pos >= cnt)
	{
		cout << "删除位置不合理!" << endl;
		return;
	}

	Node *rec = head;

	for (int i = 0; i < pos; ++i)
		rec = rec->next;

	Node *toDel = rec->next;
	rec->next = toDel->next;
	--cnt;
	delete toDel;
}

qquad 因为线性链表不需要移动元素，只需要修改指针，所以链表插入和删除的时间复杂度为 O ( 1 ) O(1) O(1)
qquad 但是由于单链表进行插入和删除之前需要进行查找操作，由于要从头查找前驱节点，所耗费的时间复杂度为： O ( n ) O(n) O(n)

template
void MyList::HeadInsert(Elem data)
{//头插法构建链表
	Node *nNode = new Node;
	nNode->data = data;
	nNode->next = nullptr;

	if (head->next == nullptr)
	{
		head->next = nNode;
		++cnt;
		return;
	}
	nNode->next = head->next;
	head->next = nNode;
	++cnt;
}

qquad 头插法的时间复杂度为 O ( 1 ) O(1) O(1)。

template
void MyList::My_PushBack(Elem data)
{//尾插法构建链表
	Node *nNode = new Node;
	nNode->data = data;
	nNode->next = nullptr;

	if (head->next == nullptr)
	{
		head->next = nNode;
		tail = nNode;
		++cnt;
		return;
	}

	tail->next = nNode;
	tail = nNode;
	++cnt;
}

qquad 链表尾插法的时间复杂度为 O ( n ) O(n) O(n)。