04、数据结构与算法实战:线性表(2)

学习笔记:数据结构与算法(四):线性表(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;
	}
}

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: