单链表结构和顺序存储结构

1. 将单链表的结构与顺序存储结构进行比较

---- 1）存储分配方法

-顺序存储结构使用连续存储单元顺序存储线性表的数据元素.

-单链表采用链式存储结构，带有一组任意的存储单元来存储线性表的元素.

---- 2）时间表现

-搜索: 顺序存储结构O（1），单个链表O（n）

-插入和删除:

顺序存储结构需要一个移动平均表长度一半的元素链表的结构，时间为O（n）. 在某个位置找到指针后链表的结构，单链列表仅具有O（1）插入和删除时间.

---- 3）空间性能

-顺序存储结构需要预先分配的存储空间，该空间太大，浪费而且很小，很容易溢出.

-单链接列表不需要预先分配的存储空间，只要可以分配它们，并且元素的数量不受限制.

从空间限制的角度来看，在静态分配表的情况下，一旦存储空间已满，就无法扩展. 如果添加新元素，则会发生存储溢出；动态存储分配中

尽管可以扩展存储空间，但需要移动大量元素，这会降低操作效率.

线性链表的节点空间仅在需要时才应用，无需事先分配，因此只要有分配空间，就不会出现存储溢出的问题，并且操作效率也比顺序表好.

---- 4）访问方法

-顺序表可以顺序或直接访问.

-线性链表只能从链头顺序访问.

---- 5）逻辑顺序与物理位置之间的关系

-序列表中表元素的逻辑顺序与它们的物理存储顺序完全相同.

-线性链接列表中每个表元素的逻辑顺序和物理存储顺序不一定相同.

---- 6）查找速度

-因为线性链表只能沿着链条进行一一比较，并且可以根据元素序号（下标）直接访问顺序表，所以顺序表的搜索速度比线性表快线性链接列表.

-从插入和删除速度的角度来看，如果要求表中其他元素的相对逻辑顺序在插入和删除后保持不变，则平均顺序表需要移动大约一半的元素，

线性链表只需要修改链接指针，不需要移动元素，因此线性链表比顺序表的插入和删除速度快.

---- 7）使用C指针

-对于序列表，指针p指示数据元素的存储位置，使用* p获取数据元素的值，并使用p ++顺序前进到下一个数据的位置物理元素；

-对于线性链表，指针p表示链表节点的地址. * p不能用于获取节点数据的值，也不能使用p ++将其输入到下一个节点的位置，只能使用<

p-> data获取节点数据的值，请使用p = p-> next转到下一个节点.

2. 结论

----通过以上比较，我们可以得出以下结论:

--- 1）如果需要频繁搜索线性表并且很少执行插入和删除操作，则应使用顺序存储结构.

如果需要频繁插入和删除，则应使用单链列表结构.

--- 2）当线性表中的元素数变化很大或不知道它的大小时，最好使用单链表结构，这样就不必考虑大小的存储空间.

如果提前知道线性表的大致长度，则使用顺序存储结构的效率将大大提高.

3. 静态链表

----由数组描述的链表称为静态链表，也称为游标实现方法.

数组的元素由两个数据字段data和cur组成. 即，阵列的每个下标对应于一个数据和一个cur. 数据字段数据，用于存储数据元素，是我们

要处理的数据；光标cur等效于单链接列表中的下一个指针，将元素的后继对象的下标存储在数组中.

4. 已知带有头节点的循环链表中的头指针为head，并尝试写出DelNode函数，该函数删除并释放所有数据字段值为x的节点.

typedef struct node
{
	int data;
	struct node *next;
} Node;
//删除结点的数据域值为x的结点
void DelNode(Node *head,int x)
{
	Node *p,*q,*s;
	p = head;
	q = p->next;
	while(q!=head)
	{
		if(q->data==x)
		{
			p->next=q->next;
			s=q;
			q=q->next;
			free(s);
		}
		else //不相等，向后移动
		{
			p=q;
			q=q->next;
		}
	}
}

5. 百货商店的仓库中有一批电视，按照价格从低到高的顺序形成一个循环链接列表，每个节点具有价格，数量和链接指针这三个字段.

已有（销售）m套价格为h的电视，请尝试编写算法来修改原始链接列表.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-238790-1.html