单链表基本运算算法——C/C++

淩亂°似流年 2024-04-17 05:30 64阅读 0赞

## 1、简介 ##

**单链表**是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

## 2、格式 ##

data域--存放结点值的数据域
    next域--存放结点的直接后继的地址（位置）的指针域（链域）

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 3、各个函数接口 ##

//初始化线性表
    void InitList(ListNode*& L) 
    //头插法
    void CreateListF(ListNode*& L, int array[], int n) 
    //尾插法
    void CreateListR(ListNode*& L, int array[], int n) 
    //销毁线性表
    void DestroyList(ListNode*& L) 
    //判断是否为空
    bool ListEmpty(ListNode* L) 
    //求线性表的长度
    int ListLength(ListNode* L) 
    //输出线性表
    void Display(ListNode* L) 
    //查找某个数据元素值
    bool GetData(ListNode* L, int i, int& data) 
    //按元素值查找 
    int LocateData(ListNode* L, int data) 
    //插入数据元素
    bool ListInsert(ListNode*& L, int i, int data) 
    //删除数据元素 
    bool ListDelete(ListNode*& L, int i, int& data)

## 4、函数实现及解释 ##

用到的库基本库<stdio.h>、需要分配地址空间的库<malloc.h>

#include<stdio.h>
    #include<malloc.h>
    
    typedef struct node {
    	int data;									//存放数据
    	struct node* next;							//下一个节点
    }ListNode;										//单节点类型

**4.1、初始化线性表**  
建立一个空的单链表，创建一个头结点，并将其 next 域置为空。

//初始化线性表
    void InitList(ListNode*& L) {
    	L = (ListNode*)malloc(sizeof(ListNode));
    	L->next = NULL;								//创建头结点，其 next 域置为 NULL 
    }

**4.2、头插法**  
该方法从一个空表依次读取数组 a 中的元素，生成一个结点(由 s 指向它)，将读取的数组元素放到该节点的数据域中，然后将其插入到当前链表的表头上（**即头结点之后**）  
**s->next 指向 L->next，L->next 接上 s结点**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

//头插法
    void CreateListF(ListNode*& L, int array[], int n) {
    	ListNode* s;
    	L = (ListNode*)malloc(sizeof(ListNode));
    	L->next = NULL;								//创建头结点，其 next 域置为 NULL
    	for (int i = 0; i < n; i++) {				//循环建立数据节点 s 
    		s = (ListNode*)malloc(sizeof(ListNode));
    		s->data = array[i];						//赋值 
    		s->next = L->next;						//将结点 s 插入到原首结点之前，头结点之后 
    		L->next = s;
    	}
    }

**4.3、尾插法**  
该方法从一个空表依次读取数组 a 中的元素，生成一个结点(由 s 指向它)，将读取的数组元素放到该节点的数据域中，然后将其插入到当前链表的表尾上  
**r->next 指向 s，r 结点接上 s 结点。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]

//尾插法
    void CreateListR(ListNode*& L, int array[], int n) {
    	ListNode* s, * r;
    	L = (ListNode*)malloc(sizeof(ListNode));	//创建头结点
    	r = L;										//r 始终指向尾结点，初始时指向头结点 （头结点序号为 0） 
    	for (int i = 0; i < n; i++) {				//循环建立数据节点 s
    		s = (ListNode*)malloc(sizeof(ListNode));
    		s->data = array[i];						//赋值 
    		r->next = s;							//将结点 s 插入到结点 r 之后 
    		r = s;
    	}
    	r->next = NULL;								//尾结点其 next 域置为 NULL 
    }

**4.4、销毁线性表**

//销毁线性表
    void DestroyList(ListNode*& L) {
    	ListNode* pre = L, * p = L->next;			//pre 指向结点 p 的前驱节点 
    	while (p != NULL) {							//扫描单链表 L 
    		free(pre);								//释放 pre 结点 
    		pre = p;								//pre、p 同步后移一个结点 
    		p = pre->next;
    	}
    	free(pre);									//循环结束时 p 为 NULL，pre指向尾结点释放它 
    }

**4.5、判断是否为空**

//判断是否为空
    bool ListEmpty(ListNode* L) {
    	return L->next == NULL;
    }

**4.6、求线性表的长度**

//求线性表的长度
    int ListLength(ListNode* L) {
    	int n = 0;
    	ListNode* p = L;							//p 指向头结点，n置为0 
    	while (p->next != NULL) {					//不为空，依次遍历 
    		n++;
    		p = p->next;
    	}
    	return n;									//返回长度 
    }

**4.7、输出线性表**

//输出线性表
    void Display(ListNode* L) {
    	ListNode* p = L->next;						//p 指向首结点 （首结点序号为 1） 
    	while (p != NULL) {							//不为空，依次遍历 
    		printf("%d ", p->data);
    		p = p->next;							//p 移向下一个节点 
    	}
    	printf("\n");
    }

**4.8、查找第 i 个元素值**

//查找某个数据元素值
    bool GetData(ListNode* L, int i, int& data) {
    	ListNode* p = L->next;						//p 指向首结点 （首结点序号为 1） 
    	if (i <= 0) {								//i 错误返回假 
    		return false;
    	}
    	int j = 0;
    	while (j < i - 1 && p != NULL) {			//找第 i 个结点 p 
    		j++;
    		p = p->next;
    	}
    	if (p == NULL) {							//不存在 
    		return 0;
    	}
    	else {										//存在返回 true 
    		data = p->data;
    		return true;
    	}
    }

**4.9、查找元素值**

//按元素值查找 
    int LocateData(ListNode* L, int data) {
    	int i = 1;
    	ListNode* p = L->next;						//p 指向头结点 ，i 置为 1（首结点序号为 1） 
    	while (p != NULL && p->data != data) {		//查找 data 值，其序号为 i 
    		p = p->next;
    		i++;
    	}
    	if (p == NULL) {							//不存在 
    		return false;
    	}
    	else {										//存在并返回序号 i 
    		return i;
    	}
    }

**4.10、插入数据元素**  
在第 i 个位置插入，即连接至第 i-1 结点后面。

//插入数据元素
    bool ListInsert(ListNode*& L, int i, int data) {
    	ListNode* p = L, * s;						//p 指向头结点 （头结点序号为 0） 
    	if (i <= 0) {								//i 错误返回假 
    		return false;
    	}
    	int j = 0;									//j 置为 0 
    	while (j < i - 1 && p != NULL) {			//查找第 i-1 个结点 p 
    		j++;
    		p = p->next;
    	}
    	if (p == NULL) {							//未找到 
    		return false;
    	}
    	else {										//找到第 i-1 个结点 p ,插入新结点并返回 true 
    		s = (ListNode*)malloc(sizeof(ListNode));
    		s->data = data;							//创建新结点 s,其值为 data 
    		s->next = p->next;						//头插法 
    		p->next = s;
    		return true;
    	}
    }

**4.11、删除数据元素**  
删除第 i 个元素，即第 i-1 结点直接连接到第 i+1 结点。

//删除数据元素 
    bool ListDelete(ListNode*& L, int i, int& data) {
    	ListNode* p = L, * q;						//p 指向头结点 （头结点序号为 0） 
    	if (i <= 0) {								//i 错误返回假 
    		return false;
    	}
    	int j = 0;									//j 置为 0 
    	while (j < i - 1 && p != NULL) {			//查找第 i 个结点 p 
    		j++;
    		p = p->next;
    	}
    	if (p == NULL) {							//未找到 
    		return false;
    	}
    	else {										//找到第 i-1 个结点 p 
    		q = p->next;							//q 指向第 i 个结点 
    		if (q == NULL) {						//若不存在第 i 个结点 
    			return false;
    		}
    		data = q->data;
    		p->next = q->next;						//删除 q 结点，第 i-1 个结点 指向第 i+1 个结点 
    		free(q);								//释放 q 结点 
    		return true;
    	}
    }

## 5、结果展示 ##

主函数

int main() {
    	int array[] = { 1,3,5,7,9 };
    	int n = sizeof(array) / sizeof(int);
    	ListNode* L = (ListNode*)malloc(sizeof(ListNode));
    	CreateListR(L, array, n);
    	printf("创建单链表成功!\n");
    	printf("输出单链表为：");
    	Display(L);
    	//	DestroyList(L);
    	int i = 5, j = 0;
    	GetData(L, i, j);
    	printf("查找第%d个元素值为%d\n", i, j);
    	int x = 9;
    	int num = LocateData(L, x);
    	printf("查找元素值%d是第%d个元素\n", x, num);
    	ListInsert(L, 6, 11);
    	printf("插入成功!\n");
    	Display(L);
    	int y = 0;
    	ListDelete(L, 6, y);
    	printf("删除成功!\n");
    	printf("%d\n", y);
    	Display(L);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ba3e3ad4961c4ecf94ef1afec1e62373.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/17420b569e854f069c1ee897124d8c12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f346cd6e4c734793a4ff1bc2d8e81124.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/c5722ee40e4d4dc39ccacb0f68dc52d4.png