学习笔记：数据结构与算法（四）：线性表（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;
}
}
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: