[数据结构]学习笔记2：线性表（2）

线性表的链式存储结构

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

比起顺序存储结构，每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）。

也就是说除了存储其本身的信息外，还需要存储一个指示其直接后继的存储位置的信息。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（Node）。

n个结点链接成一个链表，即为线性表（a1,a2，a3，…，an）的链式存储结构。

因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）。
头指针与头结点的异同

单链表存储结构

单链表图例：

空链表图例：

我们在C语言中可以用结构指针来描述单链表。

假设p是指向线性表第i个元素的指针，则该节点a[i]的数据域我们可以用p->data的值来表示，是一个数据元素，结点a[i]的指针域可以用p->next来表示，p->next的值是一个指针。

那么p->next指向谁呢？当然是指向第i+1个元素！
也就是指向a[i+1]的指针。

问题：
-如果p->data = a[i]，那么p->next->data = ？
-答案：p->next->data = a[i+1]

单链表的读取

算法思路：
-声明一个结点P指向链表的第一个结点，初始化j，从1开始；
-当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，j+1;
-若到链表末尾p为空，则说明第i个元素不存在；
-否则查找成功，返回结点p的数据。

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值*/

Status GetElem(LinkList L;int i;ElemType *e){
	int j;
	LinkList p;
	
	p = L->next;
	j = 1;
	
	while(p && j<i){
		p = p->next;
		++j;
	}
	
	if(!p || j>i){
		return ERROR;
	}
	
	*e = p->data;
	
	return OK; 
}