Day8.结构体链表

拼搏现实的明天。 2022-08-01 11:12 118阅读 0赞

在学习链表之前，回忆以下上几节所学。

1.文件操作的基础

<table> 
 <tbody> 
  <tr> 
   <td>api的种类：<br> 一、文件读写api<br> fgetx fputc 按照字符读写<br> fgets fputs 按照行读写（读写配置文件）<br> fread fwrite 按照块读写文件（大数据块迁移）<br> 按照格式化读写文件<br> 二、文件控制api<br> 文件是否结束<br> 文件指针的定位和跳转</td> 
  </tr> 
 </tbody> 
</table>

一个重要点

<table> 
 <tbody> 
  <tr> 
   <td>fets(buf, bufmaxlen, fp)<br> 对fgets函数来说，n必须是个正整数，表示从文件按中读出的字符数不超过n-1，存储到字符数组str中，并在末尾加上结束标志'\0'，换言之，n代表了字符数组的长度，即sizeof(str)。如果读取过程中遇到换行符或文件结束标志，读取操作结束。若正常读取，返回指向str代表字符串的指针，否则，返回NULL空指针。</td> 
  </tr> 
 </tbody> 
</table>

具体参考Day6文件读写那章。http://blog.csdn.net/jorg\_zhao/article/details/46559701

2.另外，动态库开发需要提及的是环境的搭建，在我的电脑属性里的系统变量里，一般如下，我电脑上的

![Center][]

如果你编译时，无法找到你所需要的动态库，可能是上图的系统变量问题，你可以在图5中， 在最前面加上 “ **.; **”

3.内存释放的问题

如图所示

![Center 1][]

内存由动态库函数进行分配，必须由动态库函数进行释放，不能在APP中手动释放，否则会引起程序扩大。

我们先以结构体进行引导说明，看下面的一个例子

#include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    struct Student
    {
    	char name[64];
    	int age;
            char *p; 
    };
    struct Teacher
    {
    	char name[64];
    	int age;
    	char *p;
    	struct Student s1;
    	struct Student *ps2;
    };
    void main()
    {
    	struct Teacher t1;
    	struct Student s2;
    
    	t1.age = 35;
    	t1.s1.age = 10;
    
    	//我们想通过ps2去操作ps2所指向的内存空间，但是这个内存空间是不存在的
    	//记住：没有内存，哪有指针！！！！
    	t1.ps2->age = 20;
    
    	system("pause");
    }

ps2是一个指针，但是我们没有分配内存空间就去操作这个内存空间，执行就会down掉！！但是应该怎么做的？？？？

//我们想通过ps2去操作ps2所指向的内存空间，但是这个内存空间是不存在的
    	//记住：没有内存，哪有指针！！！！
    	t1.ps2->age = 20;
    
    	//可以这样做
    	t1.ps2 = &s2;
    	t1.ps2->age = 20;

为了后面的说明，我给出完整的代码

#include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    struct Student
    {
    	char name[64];
    	int age;
    	char *p;
    };
    struct Teacher
    {
    	char name[64];
    	int age;
    	char *p;
    	struct Student s1;
    	struct Student *ps2;
    };
    void main()
    {
    	struct Teacher t1;
    	struct Student s2;
    
    	t1.age = 35;
    	t1.s1.age = 10;
    
    	t1.ps2 = &s2;
    	t1.ps2->age = 20;
    	system("pause");
    }

我们必须要以内存模型进行分析代码，这是程序员必须具备的基本功，不能仅仅看代码而看代码，要从编译器的角度看代码！！切记！！ **看不懂内存，就成不了高手！！**  
![Center 2][]

从上面可知，我们可以在结构体内部套结构体，结构体内部套指针，但是这都是套不同的结构体，如果是下面的代码呢？？？？？

struct AdvTeacher
    {
    	char name[64];
    
    	struct AdvTeacher *t1;
    	struct AdvTeacher t2;
    };

思考以下上面两种自嵌套，哪种是正确的？？？？

**一句话：结构体的实质是自定义数据结构，数据结构是固定大小内存块的别名或模具，就是要告诉编译器要怎么样分配内存。**

知道了这句话，我们再来看上面的两句代码，编译器看到指针，指针无论是多少级\* \*\* \*\*\*\*\*\*\*\*，编译器永远都会只分配4个字节，但是对于第二句，一直在无限循环，编译器就无法知道到底要分配多少个内存。

有了上面的分析，我们来接触链表。

链表是一种常见的重要的数据类型，它是动态的进行存储分配的结构，链表必须利用指针变量才能实现。

![Center 3][]

![Center 4][]

现在我们看一下代码如何实现链表。

链表的形式如图所示：

![Center 5][]

具体代码实现如下

#include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    struct AdvTeacher
    {
    	char name[64];
    	int age;
    	struct AdvTeacher *next;
    
    };
    void main()
    {
    	struct AdvTeacher t1, t2, t3;
    	struct AdvTeacher *p =NULL;
    	t1.age = 10;
    	t2.age = 20;
    	t3.age = 30;
    
    	t1.next = &t2;
    	t2.next = &t3;
    	t3.next = NULL;
    
    	//遍历准备环境
    	p = &t1;
    	while (p)
    	{
    		printf("age;%d\n", p->age);
    		p = p->next;
    	}
    	system("pause");
    }

但是需要注意的是，静态链表应用范围只是在函数体内，当在函数体外调用函数体内的变量时，由于静态链表在函数体内，内存空间在临时区，无法甩出来，因此这也是静态链表的使用局限性。

现在我们开始单向链表的创建、遍历、添加、删除和销毁等操作。

概念：结构体 两个域：data域和指针域 引用自身的结构体 特点：非顺序存储

分类：带头链表&不带头链表  结点的组织形式：单向链表、双向链表、循环链表等  静态链表&动态链表

![Center 6][]

链表编程元素分析：头结点、当前结点、前驱结点、后继结点          新建结点

pHead     pCurrent    pRrior         pNext               pMalloc

链表编程关键点

1.指针指向谁，就把谁的地址赋值给谁

2.辅助指针变量&操作逻辑的关系

链表概念和基本操作

为了更好的说明具体内容，我们先来按照下面的要求进行编写代码。

1.建立带有头结点的单向链表

编写函数SList\_Creat 建立带有头结点的单向链表。循环创建结点，结点数据域中的数值从键盘输入，以-1作为输入结束标志。链表的头结点地址由函数值返回。

2.顺序访问链表中各结点的数据域

编写函数SList\_Print，顺序输出单向链表各项结点数据域中的内容。

3.在单向链表中插入节点

编写函数SList\_NodeInsert，功能：在值为x的结点前，插入值为y的结点；若值为x的结点不存在，则插在表尾。

4.删除单向链表中的结点

编写函数SList\_NodeDel，删除值为y的结点。

我们先看一下新结点创建以后的图示

![Center 7][]

我们先写创建的函数

SLIST *Creat_SList()
    {
    	//1.创建头结点并初始化。
    	int data = 0;
    	SLIST *pHead = NULL, *pM = NULL, *pCur =NULL;
    	pHead = (SLIST *)malloc(sizeof(SLIST));
    	pHead->data = 0;
    	pHead->next = NULL;
    	//2.循环创建结点，结点数据域中的数值从键盘输入，以-1作为输入结束标志。
    	printf("\nPlease enter the data of node:(-1:quit)");
    	scanf("%d", &data);
    
    	//准备环境
    	pCur = pHead;
    	while (data != -1)
    	{
    		//不断的malloc新结点，并且数据域赋值
    		pM= (SLIST *)malloc(sizeof(SLIST));
    		pM->data = data;
    		pM->next = NULL;
    		//新结点入链表
    		pCur->next = pM;
    		//2当前结点下移，新结点变成当前结点
    		pCur = pCur->next;
    
    		printf("\nPlease enter the data of node(-1:quit)");
    		scanf("%d", &data);
    	}
    	return pHead;
    }

接下来是打印函数

int SList_Print(SLIST *pHead)
    {
    	SLIST *p = NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//准备环境
    	p = pHead->next;
    	printf("链表开始\n");
    	while (p)
    	{
    		printf("%d\n", *p);
    		p = p->next;
    	}
    	printf("链表结束\n");
    }

现在我们可以实现初始化和打印链表的基本功能了，给出完整的代码以供学习

再来看一下销毁结点  
代码

int SList_Destroy(SLIST *pHead)
    {
    	SLIST *pTmp = NULL;
    	SLIST *pCur = NULL;
    	if (pHead == NULL)
    	{
    		return 0;
    	}
    	pCur = pHead;
    	while (pCur)
    	{
    		pTmp = pCur->next;
    		free(pCur);
    		pCur = pTmp;
    	}
    	return 0;
    }

在结点数值为x的前面插入y，我们先看一下示意图

![Center 8][]

//在结点x的前面插入y
    int SList_NodeInsert(SLIST *pHead, int x, int y)
    {
    	SLIST *pCur = NULL, *pPre = NULL, *pM= NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//环境准备
    	pPre = pHead;
    	pCur = pHead->next;
    	//不断的malloc新结点，并且数据域赋值
    	pM = (SLIST *)malloc(sizeof(SLIST));
    	pM->data = y;
    	pM->next = NULL;
    
    	while (pCur)
    	{
    		if (pCur->data == x)
    		{
    			break;
    		}
    		//让pPre下移
    		pPre = pCur;
    		//让当前结点下移
    		pCur = pCur->next;
    	}
    
    	//让新结点链接后继结点
    	pM->next = pPre->next;
    	//让新结点链接前驱结点
    	pPre->next = pM;
    
    }

删除操作

![Center 9][]

代码：

//删除结点为y的链表结点
    int SList_NodeDel(SLIST *pHead, int y)
    {
    	SLIST *pCur = NULL, *pPre = NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//环境准备
    	pPre = pHead;
    	pCur = pHead->next;
    
    
    	while (pCur)
    	{
    		if (pCur->data == y)
    		{
    			break;
    		}
    		//让pPre下移
    		pPre = pCur;
    		//让当前结点下移
    		pCur = pCur->next;
    	}
    	if (pCur == NULL)
    	{
    		printf("没有找到结点，y:%d", y);
    		return -2;
    	}
    	//让新结点链接后继结点
    	pPre->next = pCur->next;
    	//让新结点链接前驱结点
    	free(pCur);
    
    	return 0;
    
    }

这样，我们就全部分析完成了。贴出全部完整代码，测试以下：

#define _CRT_SECURE_NO_WARNINGS
    #include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    typedef struct Node
    {
    	int data;
    	struct Node *next;
    }SLIST;
    
    SLIST *Creat_SList();
    int SList_Print(SLIST *pHead);
    //在结点x的前面插入y
    int SList_NodeInsert(SLIST *pHead, int x, int y);
    //删除结点为y的链表结点
    int SList_NodeDel(SLIST *pHead, int y);
    int SList_Destroy(SLIST *pHead);
    
    SLIST *Creat_SList()
    {
    	//1.创建头结点并初始化。
    	int data = 0;
    	SLIST *pHead = NULL, *pM = NULL, *pCur =NULL;
    	pHead = (SLIST *)malloc(sizeof(SLIST));
    	pHead->data = 0;
    	pHead->next = NULL;
    	//2.循环创建结点，结点数据域中的数值从键盘输入，以-1作为输入结束标志。
    	printf("Please enter the data of node:(-1:quit)\n");
    	scanf("%d", &data);
    
    	//准备环境
    	pCur = pHead;
    	while (data != -1)
    	{
    		//不断的malloc新结点，并且数据域赋值
    		pM= (SLIST *)malloc(sizeof(SLIST));
    		pM->data = data;
    		pM->next = NULL;
    		//新结点入链表
    		pCur->next = pM;
    		//2当前结点下移，新结点变成当前结点
    		pCur = pCur->next;
    
    		printf("Please enter the data of node(-1:quit)\n");
    		scanf("%d", &data);
    	}
    	return pHead;
    }
    
    int SList_Print(SLIST *pHead)
    {
    	SLIST *p = NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//准备环境
    	p = pHead->next;
    	printf("链表开始\n");
    	while (p)
    	{
    		printf("%d\n", *p);
    		p = p->next;
    	}
    	printf("链表结束\n");
    	return 0;
    }
    
    
    int SList_Destroy(SLIST *pHead)
    {
    	SLIST *pTmp = NULL;
    	SLIST *pCur = NULL;
    	if (pHead == NULL)
    	{
    		return 0;
    	}
    	pCur = pHead;
    	while (pCur)
    	{
    		pTmp = pCur->next;
    		free(pCur);
    		pCur = pTmp;
    	}
    	return 0;
    }
    
    //在结点x的前面插入y
    int SList_NodeInsert(SLIST *pHead, int x, int y)
    {
    	SLIST *pCur = NULL, *pPre = NULL, *pM= NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//环境准备
    	pPre = pHead;
    	pCur = pHead->next;
    	//不断的malloc新结点，并且数据域赋值
    	pM = (SLIST *)malloc(sizeof(SLIST));
    	pM->data = y;
    	pM->next = NULL;
    
    	while (pCur)
    	{
    		if (pCur->data == x)
    		{
    			break;
    		}
    		//让pPre下移
    		pPre = pCur;
    		//让当前结点下移
    		pCur = pCur->next;
    	}
    
    	//让新结点链接后继结点
    	pM->next = pPre->next;
    	//让新结点链接前驱结点
    	pPre->next = pM;
    
    	return 0;
    }
    
    //删除结点为y的链表结点
    int SList_NodeDel(SLIST *pHead, int y)
    {
    	SLIST *pCur = NULL, *pPre = NULL;
    	if (pHead == NULL)
    	{
    		return -1;
    	}
    	//环境准备
    	pPre = pHead;
    	pCur = pHead->next;
    
    
    	while (pCur)
    	{
    		if (pCur->data == y)
    		{
    			break;
    		}
    		//让pPre下移
    		pPre = pCur;
    		//让当前结点下移
    		pCur = pCur->next;
    	}
    	if (pCur == NULL)
    	{
    		printf("没有找到结点，y:%d", y);
    		return -2;
    	}
    	//让新结点链接后继结点
    	pPre->next = pCur->next;
    	//让新结点链接前驱结点
    	free(pCur);
    
    	return 0;
    
    }
    
    
    
    void main()
    {
    	int ret = 0;
    	SLIST *pHead = NULL;
    	pHead = Creat_SList();
    
    	ret = SList_Print(pHead);
    
    	//插入操作
    	ret = SList_NodeInsert(pHead, 20, 40);
    	ret = SList_Print(pHead);
    
    	//插入操作
    	ret = SList_NodeInsert(pHead, 100, 50);
    	ret = SList_Print(pHead);
    
    	ret = SList_NodeDel(pHead, 30);
    	ret = SList_Print(pHead);
    
    	ret = SList_Destroy(pHead);
    	system("pause");
    }

我们输入10 20 30，输出结果如图：

![Center 10][]

好，单链表的细节和完成 全部结束。对于双链表的问题，我打算不给出帖子了。针对本人的学习范畴，不会涉及，所以可能后续给出，时间紧迫，还请见谅。

工程代码的下载文件地址：http://pan.baidu.com/s/1mgxLSdq

[Center]: /images/20220731/7dfd3c48f30e4dd6acc1b85f45724a48.png
[Center 1]: /images/20220731/aad93d37cc4f4f80b0dafbaee3df7401.png
[Center 2]: /images/20220731/d0a626c736a24bf9b78689a191f03273.png
[Center 3]: /images/20220731/4b318a7fe40f45eda56e0ec8cf7a2dea.png
[Center 4]: /images/20220731/fe650065dc9f487e92b9a0d4831dcc59.png
[Center 5]: /images/20220731/537cbfb8c0fb4292b5ec545d80718760.png
[Center 6]: /images/20220731/7c5075b7f5dd45d3b68d51a30a764b9b.png
[Center 7]: /images/20220731/a4f7a0bf32074125b1818d14cffed254.png
[Center 8]: /images/20220731/7387e91b61cc48c48d69c2d384f7d658.png
[Center 9]: /images/20220731/38fc9674fdae404a899fc1d3c62b1531.png
[Center 10]: /images/20220731/132322c7d5a148f4947ce998ece99720.png