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

前言

下列代码已上传至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元起,快前往官网查看详情吧


网站标题:链表基础功能及实现-创新互联
文章位置:http://pwwzsj.com/article/cdcips.html