04、数据结构和算法 - 实战：线性表（2）

单链表的整表创建

单链表和顺序存储结构不同，数据分散在内存的角落，属于动态增长的，根据系统情况和实际需求生成。

创建思路

1、 声明结点p和计数器变量i；
2、 初始化空链表L；
3、 让L的头节点的指针指向NULL，建立一个带头结点的单链表；
4、 循环实现后继结点的赋值和插入；

头插法

从空表开始，生成新结点，读取数据存放在新节点的数据域中，然后将新结点插入到当前链表的表头上，直到结束。（类似于生活中排队第一个人插队，永远插在第一，向前扩展）
伪代码如下

void 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;
		p->next = (*L)->next;
		(*L)->next = p;
	}
}

尾插法

头插法生成的链表中结点的次序和输入的顺序相反。因此将新结点插入到最后，这种为尾插法。
伪代码如下

void CreateListTail(LinkList *L, int n)
{
   
     
	LinkList p, r;
	int i;

	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r = *L;
	
	for( i =0; i <n ;i ++)
	{
   
     
		p = (Node *)malloc(sizeof(Node)); //生成新结点
		p->data = rand()%100 + 1;
		r->next = p;
		r = p;
	}
}

单链表的整表删除

在内存中释放掉
算法思路如下：

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

伪代码如下

Status CreateListTail(LinkList *L)
{
   
     
	LinkList p, q;
		
	p = (*L)->next;	
	
	while(p)
	{
   
     
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return 0;
}

对比优缺点

对于单链表结构与顺序存储结构优缺点的分析。从分配方式、时间性能、空间性能三方面比较。

存储分配方式：顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；单链表用链式存储结构，用一组任意的存储单元存放线性表的元素。
时间性能：1. 查找 顺序O（1），单链表O（n）2. 插入和删除 顺序O（n），单链表O（1）
空间性能：顺序存储结构需要预先分配存储空间，大容易浪费，小容易溢出；单链表不需要分配存储空间，元素个数不受限制。

结论：线性表需要频繁查找，很少插入和删除，采用顺序存储结构；相反，需要频繁插入和删除，采用单链表结构。
各有优缺点，不能统一论。

静态链表

定义：用数组代替指针来描述单链表，叫做静态链表，这种描述方法叫做游标实现法 。
在该图中，大小为1000.有三行，游标，下标和数据。
第一个下标0，中间不存放数据，游标代表了第一个没有数据的下标，也就是5.
最后一个下标999，中间也不存放数据，游标代表了第一个存放数据的下标，也就是1.
伪代码如下

#define MAXSIZE 1000;
typedef struct
{
   
     
	ElemType data;
	int cur;//游标(Cursor)
}Component,StaticLinkList[MAXSIZE];

初始化

相当于初始化数组，伪代码如下。

Status InitList(StaticLinkList space)
{
   
     
	int i;
	for( i = 0; i < MAXSIZE - 1; i++)
		space[i].cur = i+1;
	space[MAXSIZE - 1].cur = 0;
	return 0;
}

插入操作

由于静态链表中操作的是数组，不存在像动态链表的结点申请和释放的问题，需要自己实现函数从而做到插入和删除操作。
例如，在A后面插入B元素

令A指向B的位置5，B指向C的位置2，下标0的游标改成6.在这里采用备用链路的思想。
伪代码有两部分，首先是获得空闲分量的下标：然后是插入的

int Malloc_SLL(StaticLinkList space)
{
   
     
	int i = space[0].cur;
	if(space[0].cur)
		space[0].cur = space[i].cur;
		//把它的下一个分量作为备用,待插入位置的游标地址
	return i;
}

Status InsertList(StaticLinkList L, int i, ElemTyoe e )
{
   
     
	int i, k ,l;
	k = MAXSIZE - 1;
	if( i < 1 || i> ListLength(L) + 1)
		return ERROR;
	
	j = Malloc_SLL(L);
	if(j)
	{
   
     
		L[j].data = e;
		for( l = 1 ; l <= i - 1 ;i ++)
		{
   
     
			k=L[k].cur;
		}
		L[j].cur = L[k].cur;
		L[k].cur = j;
		return OK;
	}
	return ERROR;
}

删除操作

由于静态链表中操作的是数组，不存在像动态链表的结点申请和释放的问题，需要自己实现函数从而做到插入和删除操作。
例如，把C删除
令B指向D的位置3，下标0的游标改成2.在这里采用备用链路的思想。
伪代码，首先是删除第i个数据元素

int ListDelete(StaticLinkList L, int i)
{
   
     
	int j,k;
	if( i < 1 || i > ListLength(L))
	{
   
     
		return 	ERROR;
	}
	k= MAX_SIZE - 1;
	for( j = 1 ; j <= i-1; j++)
		k = L[k].cur; //第一次之后k=1，第二次之后k=5
	j = L[k].cur; //j=2
	L[k].cur = L[j].cur; //把B的游标2改为3
	Free_SLL(L, j);
	return OK;
}
伪代码第二部分：把下标为k的空闲节点回收到备用链表
```c
void Free_SLL(StaticLinkList space, int k)
{
   
 
	space[k].cur = space[0].cur;
	space[0].cur = k;
}

伪代码第三部分：返回L中数据元素的个数

```java 
int ListLength(StaticLinkList L)
{
   
     
	int j = 0;
	int i = L[MAXSIZE - 1 ].cur;
	while(1)
	{
   
     
		i = L[i].cur;
		j++;
	}
	return j;
}

静态小结

优点：
在插入和删除操作时，只需要修改游标，不需要移动元素。改进在顺序存储结构中插入和删除操作移动大量元素的缺点。
缺点
没有解决连续存储分配（数组）带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性
总结：为了给没有指针的编程语言设计的一种实现单链表的功能。

单链表小结

题目：快速找到未知长度单链表的中间节点
普通方法：首先遍历一遍单链表确定长度L，然后从头节点出发循环L/2次。复杂度O（L+L/2）=O（3L/2）
优化方法：快慢指针原理，设置两个指针*search和 *mid都指向头节点，*search 的移动速度是 mid的两倍，当search指向末尾节点的时候，mid就在中间了。
实现代码：

Status GetMidNode(LinkList L, ElemType *e)
{
   
     
	LinkList search,mid;
	mid = search = L;
	while(search -> next !=NULL)
	{
   
     
		if(search->next->next != NULL)
		{
   
     
			search = search->next->next;
			mid = search->next;
		}
		else
			search=search->next;
		*e = mid->data;
		return OK;
	}
}