cd4356

单链表结构体

  • 结构体后的*List是一个指向结构体的指针类型，我们通过它来定义该类型的指针。

  • 如：List  p ;  则这个p就是指向LinkedList结构体的一个指针，也就是单链表的头指针。（所以说头指针是必然存在的，但单链表不一定有头结点，注意区分头指针和头结点）

typedef struct LinkedList {
	int data;                  //数据域
	struct LinkedList *next;   //指针域，指向后继结点，存放后继结点的地址
}*List; //List <==> List * ，这里的List是单链表的头指针



带头结点 和 不带头节点 的初始化

  • 带头结点单链表的初始化。①头结点初始化时，其next域必须置为空 head->next = NULL;。②头结点的data数据域如果要用来记录链表长度，则需初始化为0 head->data = 0;
    cd4356
//申请一个头结点 或 初始化一张空表
List create_head_node() {
	List head = (List)malloc(sizeof(LinkedList)); //创建头结点，并让头指针指向头结点 (带头结点单链表)
	if (head == 0) { //结点空间申请失败，该判断语句可有可无
		return NULL;
	}
	head->next = NULL; //head是头结点，h->next是头结点的地址，该地址是第一个结点的地址，地址为NULL，即为空表
	//head->data不用操作，但若想用头结点数据域保存链表长度，可以设置为head->data = 0;
	head->data = 0;

	return head;
}
  • 不带头结点单链表的初始化
    cd4356
List link_list_create(){
	List p;
	p = NULL; 
	
	return p;
}



求链表长度

单链表求长度有两种方式

  • ① 用头结点的data数据域记录链表长度（只适用于带头结点的链表）。创建头结点时，头结点的data初始化为0。成功执行插入操作后，头结点数据域+1。成功执行删除操作后，头结点数据域-1。时间复杂度为O(1),（故链表带头结点，则推荐用这种方式）
head->data = 0; //创建头结点时，将头结点数据域初始化为0

head->data++; //每插入一个元素，头结点数据域+1

head->data--; //每删除一个元素，头结点数据域-1

head->data; //获取链表长度
  • ② 遍历链表获取长度，时间复杂度为O(n)
//求长度
int link_list_length(List head) {
	List p = head->next;
	int len = 0;
	while (p) {
		len++;
		p = p->next;
	}
	return len;
}



空表判断

  • 带头结点的空表判断
  • head是头结点，h->next是头结点的地址，该地址是第一个结点的地址，地址为NULL，即为空表
boolean isEmpty(List p){
	if(p->next == NULL){
		return TRUE;
	}
	return FALSE;
}


或者 (使用头结点数据域记录链表长度时，可用该方法)

boolean isEmpty(List p){
	if(p->data == 0){
		return TRUE;
	}
	return FALSE;
}
  • 不带头结点的空表判断
  • p == NULL;   p表示的是第一个结点的地址，p = NULL 表示第一个结点的地址为空，也就是空表
boolean isEmpty(List p){
	if(p == NULL){
		return TRUE;
	}
	return FALSE;
}



头插法

  • 在链表头部插入结点（即作为链表第一个元素），时间复杂度为O(1)

cd4356
cd4356

//头插
boolean head_insert(List head, int x) {
	List p = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
	p->data = x;

	p->next = head->next;
	head->next = p;

	head->data++; //结点插入成功，链表长度+1
	return TRUE;
}



尾插法

  • 在链表尾部插入结点（即作为链表最后一个元素），时间复杂度为O(n)。

  • 新结点插入链表尾部时，新结点的next域必须置为空，即：newNode->next = NULL; 。因为单链表尾结点的next域必须为null，否则我们在调用尾结点的next指针p->next时，系统判断尾结点的next没有值，就会动态地给它分配一个未知地址（而不是帮你将next域置为空）。正常情况下，虽然并不会出现问题，但在遍历链表 或 按内容获取结点 或 第二次插入为节点时，程序就会陷入死循环，最终耗尽cpu性能。你可以将tail_insert()方法中的newNode->next = NULL;这行代码注释掉，然后调用我们后面讲到的show()方法进行测试，你就会看到show()方法会不停息的打印输出一个个未知地址，直至内存耗尽，系统奔溃
    cd4356

//尾插
boolean tail_insert(List head, int x) {
	List newNode = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
	newNode->data = x;
	//newNode->next是动态分配的，如果你不置为空，系统就会动态地给它分配一个未知地址。
	newNode->next = NULL;

	List p = head; //用p结点做记录
	while (p->next != NULL) { //遍历链表，直至尾结点
		p = p->next;
	}

	p->next = newNode;  //让尾结点指针，指向新结点
	head->data++;  //新结点插入成功，链表长度+1

	return TRUE;
}



指定位置插入

  • 在第k个位置插入新结点。需要先遍历链表，找到第k-1个结点，然后再修改新结点指针和第k-1个结点的指针，即可实现在第k个位置插入新结点操作。
    cd4356
//指定位置插入
boolean insert(List head, int k, int x) {

	if (k < 1) {
		printf("插入位置非法！");
		return FALSE;
	}

	List p = head;
	int i = 0; //用i来记录结点位置
	while (p->next != NULL && i < k - 1) {
		i++;
		p = p->next;
	}

	if (i + 1 == k) {
		List tmp = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
		tmp->data = x;

		tmp->next = p->next;
		p->next = tmp;

		head->data++;  //新结点插入成功，链表长度+1

		return TRUE;
	} else {
		printf("插入位置非法！");
		return FALSE;
	}
}



按位序查找

//按位序查找
List get(List head, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}

	List p = head;
	int i = 0;
	while (p->next != NULL && i < k) { //找到第k个结点
		i++;
		p = p->next;
	}

	if (i == k) {   //判断i是否等于要查找结点的位序
		return p;
	}else{
		printf("查找位置非法！");
		return NULL;
	}
}



删除第1个结点

//删除第1个结点
boolean del_first(List head) {
	if (head->next != NULL) {
		head->next = head->next->next;  //让头结点next指针，指向头结点下一个结点的next指针所致地址
		head->data--;  //链表长度减1
		return TRUE;
	}
	return FALSE;
}



删除第k个结点

//删除第k个结点
boolean del(List head, int k) {
	List p = head;
	if (p->next == NULL && k < 1) {
		printf("删除位置非法！\n");
		return FALSE;
	}

	int i = 0; //用i记录结点位置
	while (p->next != NULL && i < k - 1) { //找到待删结点的前一个结点
		i++;
		p = p->next;
	}

	if (i + 1 == k) {  //判断i是不是k结点的前一个结点的位置
		p->next = p->next->next;
		head->data--;  //链表长度减1
		return TRUE;
	} else {
		printf("删除位置非法！\n");
		return FALSE;
	}
}



遍历链表，显示数据

  • 前面讲到了，如果在新结点插入链表尾部时，如果新结点next指针没有置为NULL，则在show()遍历链表时，将链表的结点数据输出后，方法不会中断，而是继续输出一个个未知地址，直至内存空间耗尽。
//显示数据
void show(List head) {
	List p = head->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
}



全部代码

#include <stdio.h>
#include <stdlib.h> //malloc需要此头文件

typedef enum {FALSE, TRUE} boolean;

//结构体
typedef struct LinkedList {
	int data;
	struct LinkedList *next;
} *List; //List <==> List *



//申请一个头结点，并初始化
List create_head_node() {
	List head = (List)malloc(sizeof(LinkedList)); //创建头结点，并让头指针指向头结点 (带头结点单链表)
	if (head == 0) { //结点空间申请失败，该判断语句可有可无
		return NULL;
	}
	head->next = NULL; //head表示的是头结点的地址，h->next就是头结点的下一个结点，即第一个结点的地址为空，也就是空表
	//head->data不用操作，但若想用头结点数据域保存链表长度，可以设置为head->data = 0;
	head->data = 0;

	return head;
}


//头插
boolean head_insert(List head, int x) {
	List p = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
	p->data = x;

	p->next = head->next;
	head->next = p;

	head->data++; //结点插入成功，链表长度+1
	return TRUE;
}


//尾插
boolean tail_insert(List head, int x) {
	List newNode = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
	newNode->data = x;
	//newNode->next是动态分配的，如果不置为空，系统就会默认分配一个未知地址
	newNode->next = NULL;

	List p = head; //用p结点做记录
	while (p->next != NULL) { //遍历链表，直至尾结点
		p = p->next;
	}

	p->next = newNode;  //让尾结点指针，指向新结点
	head->data++;  //新结点插入成功，链表长度+1

	return TRUE;
}


//指定位置插入
boolean insert(List head, int k, int x) {

	if (k < 1) {
		printf("插入位置非法！");
		return FALSE;
	}

	List p = head;
	int i = 0; //用i来记录结点位置
	while (p->next != NULL && i < k - 1) {
		i++;
		p = p->next;
	}

	if (i + 1 == k) {
		List tmp = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
		tmp->data = x;

		tmp->next = p->next;
		p->next = tmp;

		head->data++;  //新结点插入成功，链表长度+1

		return TRUE;
	} else {
		printf("插入位置非法！");
		return FALSE;
	}
}


//按序号查找
List get(List head, int k) {
	if (k < 1) {
		printf("查找位置非法！");
		return NULL;
	}

	List p = head;
	int i = 0;
	while (p->next != NULL && i < k) { //找到第k个结点
		i++;
		p = p->next;
	}

	if (i == k) {
		return p;
	} else {
		printf("查找位置非法！");
		return NULL;
	}
}


//删除第1个结点
boolean del_first(List head) {
	if (head->next != NULL) {
		head->next = head->next->next;
		head->data--;
		return TRUE;
	}
	return FALSE;
}


//删除第k个结点
boolean del(List head, int k) {
	List p = head;
	if (p->next == NULL && k < 1) {
		printf("删除位置非法！\n");
		return FALSE;
	}

	int i = 0; //用i记录结点位置
	while (p->next != NULL && i < k - 1) { //找到待删结点的前一个结点
		i++;
		p = p->next;
	}

	if (i + 1 == k) {  //判断i是不是k结点的前一个结点的位置
		p->next = p->next->next;
		head->data--;
		return TRUE;
	} else {
		printf("删除位置非法！\n");
		return FALSE;
	}
}


//显示数据
void show(List head) {
	List p = head->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
}



int main() {
	List head = create_head_node();

	printf("当前单链表长度为：%d\n\n", head->data);

	head_insert(head, 15);
	head_insert(head, 25);
	head_insert(head, 35);
	printf("第1个结点元素为：%d\n", get(head, 1)->data);
	printf("第2个结点元素为：%d\n", get(head, 2)->data);
	printf("第3个结点元素为：%d\n", get(head, 3)->data);
	printf("当前单链表长度为：%d\n\n", head->data);


	tail_insert(head, 45);
	tail_insert(head, 55);
	printf("第1个结点元素为：%d\n", get(head, 1)->data);
	printf("第2个结点元素为：%d\n", get(head, 2)->data);
	printf("第3个结点元素为：%d\n", get(head, 3)->data);
	printf("第4个结点元素为：%d\n", get(head, 4)->data);
	printf("第5个结点元素为：%d\n", get(head, 5)->data);
	printf("当前单链表长度为：%d\n\n", head->data);


	insert(head, 6, 65);
	insert(head, 2, 75);
	printf("第1个结点元素为：%d\n", get(head, 1)->data);
	printf("第2个结点元素为：%d\n", get(head, 2)->data);
	printf("第3个结点元素为：%d\n", get(head, 3)->data);
	printf("第4个结点元素为：%d\n", get(head, 4)->data);
	printf("第5个结点元素为：%d\n", get(head, 5)->data);
	printf("第4个结点元素为：%d\n", get(head, 6)->data);
	printf("第5个结点元素为：%d\n", get(head, 7)->data);
	printf("当前单链表长度为：%d\n\n", head->data);

	show(head);
	printf("\n\n");

	del_first(head);
	show(head);

	printf("\n\n");
	del(head, 4);
	show(head);

	return 0;
}
# c语言 # 链表 # 数据结构
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

“小满”安全车控操作系统正式在AtomGit开源

10月24日，由中国汽车工业协会指导，普华基础软件股份有限公司主办的“小满”安全车控操作系统开源发布会暨共建计划说明会成功举行。普华基础软件宣布将安全车控操作系统“小满”（简称“小满”）V24.10源代码正式在开放原子开源基金会（简称“基金会”）旗下AtomGit开源协作平台开源，并在AtomGit平

avatar 开放原子开发者工作坊

开放原子大赛——CIKM 2024赛果揭晓，10强争霸，角逐第33届国际信息与知识管理大会

开放原子大赛——CIKM 2024赛果揭晓，10强争霸，角逐第33届国际信息与知识管理大会

avatar 开放原子开发者工作坊

50万奖金池！开放原子大赛——第二届OpenHarmony创新应用挑战赛正式启动

50万奖金池！开放原子大赛——第二届OpenHarmony创新应用挑战赛正式启动

avatar 开放原子开发者工作坊