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

一、链表

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

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;
}

时间复杂度等于链表的长度为

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

数组中直接return,但是在链表中需要使用p->Next一个一个的查找。时间复杂度为。

当链表中的节点遍历结束是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、按值查找

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

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）时间复杂度

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;//返回链表头指针
	}
}