C++数据结构补充（线性表及其链式存储结构：单链表）

线性表链式存储结构的特点就是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以存在内存中未被占用的任意位置。

链式存储结构中，除了要存元素，还要存后一个元素的地址（指针）。把存储数据元素信息的域称为数据域，把存储后继位置的域称为指针域，指针域中存储的信息称为指针。两者结合后称为结点Node。

N个结点连接成一个链表，如果有一个指针域，则为单向链表；如果有两个指针域，则为双向链表。

链表中第一个结点的存储位置叫头指针（不是头结点），最后一个结点的指针为空。

头结点和头指针的区别？

头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向头结点的指针。一般用头指针来为链表命名。无论链表是否为空，头指针都不能为空，因此头指针是链表存在的必要元素。

头结点是为了操纵的统一和方便而设立的，放在第一个元素的结点之前，头结点的数据域一般不存储数据，只存储地址。头结点不一定是链表的必要组成。

单向链表的结构体构造如下：

typedef int ElemType;
typedef int Status;
typedef struct Node  //将结构体命名为Node
{
	ElemType data; //数据域
	struct Node* Next; //指针域
}Node;
typedef struct Node* LinkList;

1、单链表的访问

单向链表不支持随机访问，只能从第一个挨个找。

Status GetElem(LinkList L, int i, ElemType *e)
{
	int j;
	LinkList p; //指针，指向一个结点
	p = L->Next;  //p指向链表位置的第一个结点
	j = 1;
	while (p && j < i) //当p不为空且未到达i位置时
	{
		p = p->Next;
		++j;
	}
	if (!p || j > i)
	{
		return false;
	}
	*e = p->data;
	return true;
}

2、单链表的插入

单链表的插入只需要改变相邻结点的指针域，如图所示：

可以总结为以下两句话，它们的顺序是不能颠倒的。

s->Next=p->Next;

p->Next=s;

Status ListInsert(LinkList* L, int i, ElemType e)
{
	int j;
	LinkList p, s;//声明了两个Node类型的指针
	p = *L;
	j = 1;
	//找到第i个结点
	while (p && j < i)
	{
		p = p->Next;
		j++;
	}
	//如果找不到第i个位置，报错
	if (!p || j > i)
	{
		return false;
	}
	//创建结点，存放数据
	s = (LinkList)malloc(sizeof(Node));  //返回分配内存空间的首地址
	s->data = e;
	//更新指针域
	s->Next = p->Next;
	p->Next = s;
	return true;
}

3、单链表的删除

单链表的删除与插入同理，需要先修改指针域，再释放结点空间。

实际实现代码为：p->next=p->next->next

Status ListDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, q;
	p = *L;
	j = 1;
	while (p->Next && j < i)
	{
		p = p->Next;
		++j;
	}
	if (!(p->Next) || j > i)
	{
		return false;
	}	
	q = p->Next;
	p->Next = q->Next;
 
	*e = q->data;
	free(q);
	return true;
}

4、单链表的创建

单链表不像顺序存储结构数据这么几种，它的数据可以是分散在内存各个角落的，其增长也是动态的，它的空间大小和位置不用预先划定，可以根据系统的情况和实际的需求即时生成。

单链表的建立过程是一个动态生成链表的过程，从“空表”的初始状态起，依次建立各结点并逐个插入链表。

方法一：头插法，从空表开始，生成新结点，将新结点插入到当前链表的表头上。链表中结点的次序和输入顺序相反。

Status CreateListHead(LinkList* L, int n)
{
	LinkList p;
	int i;
	srand(time(0)); //初始化随机数
 
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->Next = NULL;
 
	for (i = 0; i < n; i++)
	{
		p= (LinkList)malloc(sizeof(Node));//生成新结点
		p->data = rand() % 100 + 1;//生成1~100的随机数
		p->Next = (*L)->Next;
		(*L)->Next = p;
	}
}

方法二：尾插法，将新结点插入到当前链表的表尾。链表中结点的次序和输入相同。

Status CreateListTail(LinkList* L, int n)
{
	LinkList p, r;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r = *L; //r是指向尾节点的指针
 
	for (i = 0; i < n; i++)
	{
		p= (LinkList)malloc(sizeof(Node));
		p->data = rand() % 100 + 1;
		r->Next = p;
		r = p;  //将p结点赋值给r结点，该节点又叫p又叫r，迭代将r作为尾节点
	}
	r->Next = NULL;
}

 5、单链表的删除

即在内存中释放，以便留出空间。单链表整表删除的算法思路为：

• 声明结点p和q；
• 将第一个结点赋值给p，下一个结点赋值给q；
• 循环执行释放p和将q赋值给p的操作；

Status ClearList(LinkList* L)
{
	LinkList p, q;
	p = (*L)->Next;
	while (p)
	{
		q = p->Next;  //使用q来临时保存p的下一个结点
		free(p);        //释放p
		p = q;         //使q作为新的p
	}
	(*L)->Next = NULL;
}

6、总结

综合顺序存储和链式存储，可以得到以下经验性结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；若需要频繁插入和删除，宜采用单链表结构。