数据结构浙江大学06-线性表链式存储04

2023-12-31 03:58:24

一、链表

将逻辑上相邻的元素通过链连接起来,而不要求在物理上相邻

typedef struct LNode* List;
struct LNode {
	ElementType Data;//该节点的数据元素
	List Next;//下一个节点的位置
};
struct Lnode L;
List PtrL;

二、主要操作实现

1、求表长

使用链表遍历的方法求表长。

p->Next依此遍历结点,并使用j计数

int Length(List PtrL) {
	List p = PtrL;//p指向表的第一个结点
	int j = 0;
	while (p) {
		p = p->Next;//链表往后挪一位,终止条件:链表结束
		j++;//计数
	}
	return j;
}

时间复杂度等于链表的长度为O(n)

2、按序号查找第k个元素

数组中直接returna[k-1],但是在链表中需要使用p->Next一个一个的查找。时间复杂度为O(n)

当链表中的节点遍历结束是p为NULL作为终止条件

List FindKth(int K, List PtrL) {
	List p = PtrL;
	int i = 1;
	while (p != NULL && i < K) {//指针为空则遍历结束
		p = p->Next;//依此查找
		i++;//记录元素编号
	}
	if (i == K)
		return p;//找到对应位置元素
	else 
		return NULL;//没有找到则返回NULL
}
3、按值查找

在链表中的节点依此查找并比对节点中的值和目标值是否相等。时间复杂度为O(n)

List Find(ElementType X, List PtrL) {
	List p = PtrL;
	while (p != NULL && p->Data != X)//终止条件:链表遍历结束,或找到目标值
		p = p->Next;
	return p;//返回找到的节点,如果没有找到则为NULL
}
4、插入

在第i-1个结点后插入一个值为X的新结点

插入操作实现,需要注意的点:

1)当插入的位置在表头时:先申请新的节点,然后将新节点的next指针指向表头。此时整个列表的头指针会发生变化;

2)若插入位置不是表头,通过按序号查找元素FindKth查找i-1个节点。要注意考虑节点不存在的情况;

3)申请节点,并进行插入操作;

4)插入时要注意先将新节点的Next指针赋值后再将原链接断开指向新节点,顺序不可以颠倒。

List Insert(ElementType X, int i, List PtrL) {
	List p, s;//新指针
	if (i == 1) {//新节点插入表头的情况
		s = (List)malloc(sizeof(struct LNode));//申请新节点的存储空间
		s->Data = X;//赋值
		s->Next = PtrL;
		return s;//返回新的表头
	}
	p = FindKth(i - 1, PtrL);//若插入的不是表头,要查找插入节点的前一个节点
	if (p == NULL) {//未查找到i-1个节点
		cout << "参数i误" << endl;
		return NULL;
	}
	else {
		s = (List)malloc(sizeof(struct LNode));
		s->Data = X;
		s->Next = p->Next;//将新节点插入到第i-1个节点后面
		p->Next = s;//将第i-1节点的指针修改为指向新节点
		return PtrL;
	}

}
5、删除

删除链表的第i个位置上的结点。

因为是单项链表,要查找到上一个结点,即第i-1个结点。

此时要注意,使用新建指针指向被删除结点,因为结点的存储空间是malloc申请的,需要free释放掉!!!

要注意的情况:
1)若要删除的是头结点,有头结点本来结束空的情况,即整个链表是空的,此时直接返回NULL不用删除结点。

2)时间复杂度O(n)

List Delete(int i, List PtrL) {
	List p, s;//新指针
	if (i == 1) {//新节点插入表头的情况
		s = PtrL;//使用新节点指向表头
		if (PtrL != NULL)
			PtrL = PtrL->Next;//如果链表中存在元素,则将头指针指向下一个结点
		else
			return NULL;//如果链表为空,则直接返回NULL
	}
	p = FindKth(i - 1, PtrL);//若删除的不是表头,要查找删除节点的前一个节点
	if (p == NULL) {//未查找到i-1个节点
		cout << "删除的前一个结点不存在" << endl;
		return NULL;
	}
	else if (p == NULL) {//未找到要删除的第i个结点
		cout << "要删除的结点不存在" << endl;
		return NULL;
	}else
	{
		s = p->Next;//将新指针指向第i个结点
		p->Next = s->Next;//将第i个结点从链表中删除
		free(s);//释放被删除结点空间
		return PtrL;//返回链表头指针
	}
}

文章来源:https://blog.csdn.net/qq_50117708/article/details/135306477
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。