当前位置:首页 > 芯闻号 > 充电吧
[导读]1、对单链表结构和顺序存储结构做对比---- 1)存储分配方式-- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。-- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。---

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。即数组的每个下标都对应一个data和一个cur。数据域data,用来存放数据元素,是我们

要处理的数据;游标cur相当于单链表中的next指针,存放该元素的后继在数组中的下标。

4、已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的DelNode函数。


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的电视机,试编写算法修改原链表。

typedef struct node
{
	float price; //价格
	int num; //数量
	struct node *next;
} Node;
//销售m台价格为h的电视机
void DelNode(Node * head,float h,int m)
{
	Node *p,*q,*s;
	p = head;
	q = p->next;
	int i=0;
	while(q->pricenext;		
	}
	if(q->price==h&&q->num>=m)
	{
		q->num=q->num-m;
		if(p->num==0)
		{
			p->next=q->next;
			free(q);
		}
	}
	else if(q->price==h&&q->num<m)
	{
		cout<<"此价格的产品不足%d台。"<<m<<endl;
	}
	else 
	{
		cout<<"无此产品。"<<endl;
	}
}






本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭