链表基础功能及实现-创新互联

前言

下列代码已上传至GitHub
若有错误，欢迎指正
链表基础功能包括新建新链表，打印链表元素，释放链表内存，新增节点，删除节点，排序，查找节点······

创新互联公司从2013年创立，是专业互联网技术服务公司，拥有项目做网站、网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元和平做网站,已为上家服务,为和平各地企业和个人服务,联系电话:028-86922220实战 一、添加一个结构体

struct cell {
	ElementType val;
	struct cell* next;
};

在这里，ElementType为任意类型，为了方便下面功能实现，我们假定ElementType为int，即

typedef int ElementType;

二、新建链表（Build）

···假定新链表以0为结尾，且首位不为0···

c/c++实现：

struct cell* Build() {
	struct cell* head, * p, * tail;
	head = p = tail = NULL;
	int n = 0;	//计录当前节点数
	while (true) {
		if (!n) {	//若n节点数为0，则添加一个头节点
			head = (struct cell*)malloc(sizeof(struct cell));	//为头节点申请一个新空间
			scanf("%d", &head->val);	//输入头节点
			tail = head;	//此时头节点也是尾节点
			tail->next = NULL;
			n = 1;
		}
		else {
			p = (struct cell*)malloc(sizeof(struct cell));	//为新节点申请一个新空间
			scanf("%d", &p->val);
			if (p->val == 0) {	//若输入为0，则释放此时p节点的内存并跳出循环
				free(p);
				break;
			}
			tail->next = p;	//tail指向p，实现节点连接
			tail = p;	//tail移动到p，实现tail移动到尾节点位置
			tail->next = NULL;
		}
	}
	return head;
}

三、打印链表（Print）

c/c++实现：

void Print(struct cell* head) {
	while (head) {
		printf("%d ", head->val);
		head = head->next;
	}
}

打印链表就是把链表每一个节点遍历一遍就完了，没什么好说的

四、释放链表内存（Release）

c/c++实现：

void Release(struct cell* head) {
	struct cell* p;
	while (head) {
		p = head->next;
		free(p);
		head = p;
	}
}

这个也是遍历链表，但与打印链表不同的是，由于释放当前节点，需要保存下一节点的位置，不然释放节点处后面的节点将变成野指针，释放head后将无法访问到下一节点位置，所以需要用p保存head下一节点地址

五、新增节点（Add）

c/c++实现：

struct cell* Add(struct cell* head, int n) {
	if (head == NULL || n< 0) {	//若为空链表或n不合法，则返回NULL
		return NULL;
	}
	struct cell* p, * p0;
	p0 = head;
	p = (struct cell*)malloc(sizeof(struct cell));	//为新增节点p申请一个新空间
	scanf("%d", &p->val);
	if (n == 1) {	//当新增节点位置为头节点处时
		p->next = head;
		return p;
	}
	else {
		for (int i = 1; i< n - 1; i++) {
			p0 = p0->next;	//p0记录新增节点位置的前一个节点
			if (p0 == NULL) {	//若n超过链表长度，则返回原头节点head
				return head;
			}
		}
		p->next = p0->next;		//***标注A***
		p0->next = p;
	}
	return head;
}

标注A：必须先将新节点指向下一节点位置,再将前一节点指向新节点（若相反,则会丢失下一节点地址）

六、删除节点（Del）

c/c++实现：

struct cell* Del(struct cell* head, int n) {
	if (head == NULL || n<= 0) {	//若为空链表或n不合法，则返回NULL
		return NULL;
	}
	struct cell* p, * p0;
	p = p0 = head;
	if (n == 1) {	//当删除节点为头节点时
		head = head->next;
		free(p);	//***标注B***
	}
	else {
		for (int i = 1; i< n - 1; i++) {
			p0 = p0->next;	//p0记录删除节点位置的前一个节点
			if (p0 == NULL) {	//若n超过链表长度，则返回原头节点head
				return head;
			}
		}
		p = p0->next;
		if (p) {	//检测p是否为NULL，即p0是否为位节点
			p0->next = p->next;
			free(p);	//***标注B***
		}
	}
	return head;
}

标注B：删除节点需要释放内存

七、查找（Find） 1）通过节点查找元素（FindElement）

c/c++实现：

ElementType FindElement(struct cell* head, int n) {
	if (head == NULL || n<= 0) {	//若为空链表或n不合法，则返回0
		return 0;
	}
	for (int i = 1; i< n; i++) {
		head = head->next;
		if (head == NULL) {	//若n超过链表长度，则返回0
			return 0;
		}
	}
	return head->val;
}

2）通过元素查找节点（FindSite）

c/c++实现：

bool FindSite(struct cell* head, ElementType n) {
	int x = 1;	//记录节点位置
	bool TorN = false;
	while (head) {
		if (head->val == n) {
			printf("%d ", x);
			TorN = true;	//若找到则标记true
		}
		head = head->next;
		x++;
	}
	if (x) {
		return true;
	}
	printf("NULL");
	return false;	//未找到返回0并打印NULL
}

总结：通过节点查找元素，只需要定位节点位置即可；通过元素查找节点，则会有多种可能性，需要遍历链表一个一个抓取

后记

2022/11/26
要期末考了，先鸽一段时间再写blog
争取一个星期写两篇（理论上可以做到，只要不摆）

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：链表基础功能及实现-创新互联
URL地址：http://6mz.cn/article/cdcips.html