专栏首页huiC语言实现单链表

C语言实现单链表

文章目录
  • 单链表常规操作
  • 定义单链表结构体
  • 构造单链表
    • 头插法实现
    • 尾插法实现
    • 单链表的头尾插法详解
  • 单链表判空
  • 计算单链表长度
  • 遍历单链表
  • 单链表头、尾插法构造效果
  • 单链表指定位置插入结点
  • 单链表指定位置删除结点
  • 按址求值
  • 按值求址
  • 单链表去重
  • 源代码

单链表常规操作

/********************* 单链表的常规操作 **************************/

LinkList CreateHeadListH();			// 头插法创建单链表
LinkList CreateHeadListT();			// 尾插法创建单链表
int      ListEmpty();				// 单链表判空
int		 ListLength();				// 求单链表长度
void 	 Travel();					// 遍历单链表
int 	 InsertNode();				// 插入结点
int      DeleteNode();				// 删除结点
ElemType GetElem();					// 按址查值
int 	 GetLocate();				// 按值查址
int 	 RemoveRepeat();			// 去除重复的值

/***************************************************************/

定义单链表结构体

单链表是由多个结点链接组成,它的每个结点包含两个域,一个数据域和一个链接域(地址域)。

  • 数据域 data 用来存放具体的数据。
  • 地址域 next 用来存放下一个节点的位置。
#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;		// 单链表存储元素的数据类型

// 定义单链表结构体
typedef struct Node(){
	ElemType data;			// 单链表结点数据域
	struct Node *next;		// 单链表结点地址域(指向下一个结点)
}*LinkList, Node;

构造单链表

头插法实现

/*
 *	头插法创建单链表(带头结点)
 *	datas 接收数组,用于赋值链表的结点数据
 *	len datas数组的长度,便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
	// 创建头结点
	LinkList head, new_node;
	head = (LinkList)malloc(sizeof(Node));
	// head -> data = len;	// 可以把链表长度存在头结点的数据域中
	head -> next = NULL;

	// 分配新节点并用头插法链接起来
	for(int i=0;i<len;i++){
		new_node = (LinkList)malloc(sizeof(Node));
		new_node -> data = datas[i];
		new_node -> next = head -> next;
		head -> next = new_node;
	}
	return head;
}

头插法构造单链表时一直往单链表的头部插入结点

尾插法实现

/*
 *	尾插法创建单链表(带头结点)
 *	datas 接收数组,用于赋值链表的结点数据
 *	len datas数组的长度,便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
	// 创建头结点
	LinkList head, p, new_node;
	head = (LinkList)malloc(sizeof(Node));
	head -> next = NULL;
	p = head;

	// 分配新节点并用尾插法链接起来
	for(int i=0;i<len;i++){
		new_node = (LinkList)malloc(sizeof(Node));
		new_node -> data = datas[i];
		new_node -> next = NULL;
		p -> next = new_node;
		p = new_node;
	}
	return head;
}

尾插法构造单链表时一直往单链表的尾部插入结点

单链表的头尾插法详解

为了不让文章篇幅过长,关于单链表头尾插法的更多具体内容请观看我的另一篇博客 单链表的头尾插法详解

单链表判空

/*
 *	单链表判空
 *	list 接收单链表
*/
int ListEmpty(LinkList list){
	return (list == NULL || list -> next == NULL);
}

计算单链表长度

/*
 *	计算单链表的长度
 *	list 接收单链表
*/
int ListLength(LinkList list){
	LinkList p = list;
	int len = 0;
	if(ListEmpty(list)){
		return len;
	}
	p = p -> next;
	while(p != NULL){
		len ++;
		p = p -> next;
	}
	return len;
}

遍历单链表

/*
 * 遍历单链表
 * list 单链表
*/
void Travel(LinkList list){
	LinkList p = list;
	if(!ListEmpty(list)){	// 单链表非空情况下才遍历
		p = p -> next;		// 因为带头结点单链表所以要先走一步
		while(p != NULL){
			printf("%d\t", p -> data);
			p = p -> next;
		}
		printf("\n");
	}
}

单链表头、尾插法构造效果

int main(int argc, char const *argv[])
{
	int datas[] = {2, 4, 6, 8, 10};
	// 动态计算datas数组的长度
	// 数组长度 = 数组的总空间大小 / 数组中每个元素所占空间大小
	int len = sizeof(datas) / sizeof(datas[0]);

	printf("头插法构造单链表\n");
	LinkList list_h = CreateHeadListH(datas, len);
	printf("ListEmpty():%d\n", ListEmpty(list_h));		// 判空
	printf("ListLength():%d\n", ListLength(list_h));	// 求长
	printf("Travel():");								
	Travel(list_h);										// 遍历

	printf("\n尾插法构造单链表\n");
	LinkList list_t = CreateHeadListT(datas, len);
	printf("ListEmpty():%d\n", ListEmpty(list_t));
	printf("ListLength():%d\n", ListLength(list_t));
	printf("Travel():");
	Travel(list_t);
	return 0;
}

因为数组是在连续的地址上存储元素,所以可以动态的计算数组的长度,方便遍历。

输入结果如下:

头插法构造单链表
ListEmpty():0
ListLength():5
Travel():10     8       6       4       2

尾插法构造单链表
ListEmpty():0
ListLength():5
Travel():2      4       6       8       10

请按任意键继续. . .

单链表指定位置插入结点

代码实现

/*
 * 单链表指定位置插入结点
 * list 单链表
 * data 要插入的结点的数据
 * pos  结点插入的位置(逻辑位置(1,2,3,...))
*/
int InsertNode(LinkList list, ElemType data, int pos){
	LinkList p = list, new_node;
	if(ListEmpty(list)){
		printf("空单链表\n");
		return FALSE;
	}

	// 判断插入位置是否合理
	if(pos <= 0 || pos > ListLength(list) + 1){
		printf("插入位置不合理\n");
		return FALSE;
	}
 	
	// 寻找到要插入位置的前一个结点
	for(int i = 0; i < pos - 1 && p != NULL; i++){
		p = p -> next;
	}

	// 准备新结点
	new_node = (LinkList)malloc(sizeof(Node));
	new_node -> data = data;

	// 此时p就是要插入位置的前一个结点,p -> next就是要插入位置的结点
	new_node -> next = p -> next;	
	p -> next = new_node;
	return TRUE;
}

详细图解

假设原单链表为:head --> 2 --> 6 ,要插入的结点值为 4,插入位置为 2。

只需找要插入位置的前一个结点就行,因为插入位置的前一个结点的地址域保存着要插入位置的结点

此时找到的结点是 new_code1,而 new_code1 -> next 就是结点 new_code2

所以我们只要

new_code3 -> next = new_code1 -> next;
new_code1 -> next = new_code3; 

先让待插入结点的地址域指向插入位置的结点

后让插入位置的前一个结点的地址域指向待插入结点。

1, 2, 3代表单链表结点位置

①,②,③代表插入操作的执行步骤顺序

注意:千万不能先让插入位置的前一个结点的地址域指向待插入结点,后让待插入结点的地址域指向插入位置的结点

new_code1 -> next = new_code3;
// 此时new_code1 -> next 等于 new_code3, now_code3 -> next = new_code3 没有达到链接
new_code3 -> next = new_code1 -> next;	

单链表指定位置删除结点

代码实现

/*
 * 单链表指定位置删除结点
 * list 单链表
 * *val 用来存储删除结点的数据
 * pos  结点删除的位置(逻辑位置(1,2,3,...))
*/
int DeleteNode(LinkList list, ElemType *val, int pos){
	LinkList p = list, r;
	if(ListEmpty(list)){
		printf("空单链表\n");
		return FALSE;
	}

	// 判断删除位置是否合理
	if(pos <= 0 || pos > ListLength(list)){
		printf("删除位置不合理\n");
		return FALSE;
	}

	// 寻找到要删除结点的前一个位置
	for(int i = 0; i < pos - 1 && p != NULL; i++){
		p = p -> next;
	}

	r = p -> next;			// 记录要删除的结点
	*val = r -> data;		// 把删除结点的数据利用指针返回去
	p -> next = r -> next;	// 把链表重新链接起来
	free(r);				// 释放删除结点的资源
	return TRUE;
}

详细图解

假设原单链表为:head --> 2 --> 4 --> 6 ,删除第 2 个结点。

还是跟插入一样只需找要删除位置的前一个结点就行

此时找到的结点是 new_code1,而 new_code1 -> next 就是结点 new_code2 ,就是要删除的结点。

r = new_code1 - > next;				
new_code1 -> next = r -> next;		// new_code1 -> next = new_code2 -> next;
free(r);	

先让变量 r 等于要删除的结点 ,

r = new_code1 - > next; --> r = new_code2;

后让删除位置的前一个结点的地址域指向要删除结点的后一个结点。

new_code1 -> next = r -> next;			// 此时r -> next 等于 new_code2
			↓↓     
new_code1 -> next = new_code2 -> next;	// new_code2 -> next 等于 new_code3
			↓↓
new_code1 -> next = new_code3;

最后释放删除结点空间 free(r)

删除第二个位置节点后的单链表:head --> 2 --> 6

按址求值

/*
 *	根据指定位置求结点的值(没有找到返回 0 )
 *	list 单链表
 *	pos  结点位置(逻辑位置(1,2,3,...))
*/
ElemType GetElem(LinkList list, int pos){
	LinkList p = list;
	if(ListEmpty(list)){
		printf("空单链表\n");
		return FALSE;
	}
	if(pos <= 0 || pos > ListLength(list)){
		printf("位置不合理\n");
		return FALSE;
	}

	for(int i = 0; i < pos && p !=NULL; i++){
		p = p -> next;
	}
	return p -> data;
}

按值求址

/*
 *	根据指定的值寻找结点的位置
 *	(如果有多个值相同返回第一个找到的结点的位置, 没找到则返回 0)
 *	list 单链表
 *  data 要查找的值
*/
int GetLocate(LinkList list, ElemType data){
	LinkList p = list;
	int pos = 0;
	if(ListEmpty(list)){
		return FALSE;
	}
	p = p -> next;
	while(p != NULL){
		pos ++;
		if(p -> data == data){
			return pos;
		}
		p = p -> next;
	}
	return FALSE;
}

单链表去重

/*
 *	去除单链表中重复的值(重复的值只保留一个)
 *	list 单链表
 *  返回值:对单链表进行了去重操作返回 1,否则返回 0
*/
int RemoveRepeat(LinkList list){
	LinkList p = list, q, r;
	int flag = 0;
	if(ListEmpty(list)){
		return FALSE;
	}

	p = p -> next;

	while(p != NULL){
		q = p;
		while(q != NULL && q -> next != NULL){
			if(p -> data == q -> next -> data){
				r = q -> next;	// 记录值相同的结点
				q -> next = r -> next;
				free(r);
				flag = 1;
			}else{
				q = q -> next;
			}
		}
		p = p -> next;
	}
	return flag;
}

原理就是每次拿没有比较过的结点跟单例表中的每一个结点进行比较,遇到相同的就删除其中一个结点。

例如:单链表序列为 2 4 2 8 8 6 6 8 12

首先拿第一个结点 2 跟单链表的其他结点比较
2      4       2       8       8       6       6       8       12
↑
    					↓↓
遇到相同的就删除
2      4       8       8       6       6       8       12
    
    					
2比完了一轮去重了2,然后用第二个结点 4 跟单链表的其他没有比较过的结点比较
2      4       8       8       6       6       8       12  
  	   ↑ 
    					↓↓
2      4       8       8       6       6       8       12 
    					
    					
4比完了一轮去重了4,然后用第三个结点 8 跟单链表的其他没有比较过的结点比较
2      4       8       8       6       6       8       12 
    		   ↑
    					↓↓
2      4       8       6       6       12
    
循环类推
2      4       8       6       6       12
    				   ↑
    				↓↓
2      4       8        6       12 
    
最后一步    
2      4       8        6       12
    							↑
    			↓↓
2      4       8        6       12

看看去重效果

去重前的单链表
ListLength():9
Travel():2      4       2       8       8       6       6       8       12

去重后的单链表
ListLength():5
Travel():2      4       8       6       12

源代码

源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单链表的头尾插法详解

    head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL;

    忆想不到的晖
  • 树和二叉树

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(Sub...

    忆想不到的晖
  • 顺序表与链表的比较

    结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

    忆想不到的晖
  • 一些js方法(持续更新) 原

    晓歌
  • 前端每日实战:122# 视频演示如何用纯 CSS 创作一个苹果系统的相册图标

    https://github.com/comehope/front-end-daily-challenges

    前端博客 : alili.tech
  • IDEA 控制台中文乱码的解决方式

    Startup/Connection 中Run中添加environment variables

    剑行者
  • 怎样成为全栈开发工程师[每日前端夜话0xAA]

    在 LinkedIn 和 Facebook 上,有很多人将当前的工作标记为全栈工开发程师。在 Medium 上关于这个问题的文章也收到了很多读者的好评。一些人认...

    疯狂的技术宅
  • 彻底屏蔽优酷广告 By HKL, Monday 12 Au

    不久之前网络上有一个通过修改Hosts来屏蔽各大视频网站广告的方法,谁想到优酷嗅觉灵敏,很快推出了反屏蔽的策略——即便不看广告也会有30秒的黑屏等待。正所谓“道...

    hiplon
  • 【每日一题】集合(京东 2017秋招真题)

    Hello~各位亲爱的小伙伴们。又到了一天一度的编程时间了,今天给大家带来的是奶茶东的招新题。快一起来看看吧。

    短短的路走走停停
  • 全栈开发工程师就是个神话

    全栈开发工程师就是个神话 “全栈开发工程师(full stack developer)”一词经常出现在企业招聘的岗位描述中。但 Hello Pretty 联合创...

    用户1289394

扫码关注云+社区

领取腾讯云代金券