线性链表 — 单链表

线性链表 — 单链表线性链表存储结构的特点:用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)数据元素a与其直接后继a+1之间的逻辑关系,对数据元素a来说,除了存储其本身信息外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素a的存储映像,称为结点(node)它包括两个域:存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。…

线性链表存储结构的特点:用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)

数据元素a与其直接后继a+1之间的逻辑关系,对数据元素a来说,除了存储其本身信息外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素a的存储映像,称为结点( node)

它包括两个域:存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针

n个结点(ai(1i≤n)的存储映像)链结成一个链表,即为线性表的式存储结构。又因为此链表的每一个结点中只包含一个指针域,故又称线性链表单链表

线性链表 — 单链表

链表是从头指针开始,头指针的信息就是第一个结点(即第一个数据元素的存储映像)存储地址。最后一个数据元素没有直接后继,故线性链表的最后一个结点的指针为“(NULL)

指针是数据元素之间的逻辑关系的映像。

逻辑上相邻的两个数据元素其存储的物理位置不要求相邻,这种存储结构为非顺序映像链式映像

线性链表 — 单链表

头结点:在单链表的第一个结点之前设一个结点。头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置) 

Status GetElem_L(LinkList L,int i,ElemType &e){
	//L为带头结点的单链表的头指针
	//当第i个元素存在时,其赋值给e并返回OK值,否则返回ERROR
	p = L -> next;j=1;//初始化L,p指向第一个结点,j为计数器
	while(P && j < i){//顺指针向后查找,知道p指向第i个元素或p为空
		p = p -> next;
		++j;
	}
	if(!p || j>i) return ERROR;//第i个元素不存在
	e = p -> data;//取第i个元素
	return OK;
}GetElem_L

  时间复杂度:O(n)

单链表的插入与删除:

插入算法:

线性链表 — 单链表

Status ListInsert_L(LinkList &L, int i,ElemType e){
//在带头结点的单链线性表L中第i个位置插入元素e
	p = L; j = 0;
	while(p && j<i-1){//寻找第i-1个结点
		p=p->next;
		++j;
	}
	if(!p || j>i-1) return ERROR;

	s=(LinkList)malloc(sizeof(LNode));//生成新的结点

	s->data=e;s->next=p->next;//插入到L中
	p->next=s;
	return OK;
}//ListInsert_L

 s=(LinkList)malloc(sizeof(LNode));作用是游戏厅生成一个LNode型的结点,同时将该结点的起始位置赋值给指针变量s

 时间复杂度:O(n)

删除算法:

线性链表 — 单链表

Status ListDelete_L(LinkList &L, int i,ElemType e){
//在带头结点的单链线性表L中删除第i个位置的元素,并由e返回其值
	p = L; j = 0;
	while(p && j<i){//寻找第i个结点,并令p指向其前驱
		p=p->next;
		++j;
	}
	if(!p || j>i-1) return ERROR;

	q=p->next; p->next=q->next;//删除并释放结点
	e=q->data;
	free(q);//粒子还给系统
	return OK;
}//ListDelete_L

  free(q);作用是由系统回收一个LNode型的结点,回收后的空间可以备做再次生成结点时用

  时间复杂度:O(n)

今天的文章线性链表 — 单链表分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/5265.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注