链表

目录：
1.链表的简介
2.链表的实现
3.动态链表
4.链表的插入和删除

1.链表的简介

链表是一种常见的数据结构，我们经常会使用数组来存放数据，但使用数组时，要先指定数组的大小，如果向这个数组加入过多的元素，则会超出，导致无法保存数据；如果数据太小，又会非常浪费内存空间。
所以，我们希望有一种存储方式，其储存的元素个数是不受限定的，当进行添加元素时，存储的个数也会增加，这种储存方式就是链表。

在链表中，有一个头指针head变量，用这个指针变量保存第一个元素的地址，其中，这个元素包括两个部分：数据部分和指针部分。数据部分用来存放元素的数据，指针部分用来指向下一个元素。于是，头指针指向第一个元素，第一个元素中的指针又指向第二个元素，第二个元素中的指针又指向第三个元素，依次下去，到了最后一个元素的指针就指向Null，表示指向的地址为空。

2.链表的实现

需要实现链表这种存储方式，必须要使用指针才能完成。结构体和指针一起实现链表功能。
我们看一下一个简单的元素结点，包含有数据部分和指针部分。

struct student
{
	char cname[20];   //学生姓名 （数据部分）
	int inumber;      //学生学号 （数据部分）
	struct student *pNext;    //指向下一个结点的指针  （指针部分） 
};

如果要向链表添加多一结点，那应该如何操作呢？我们看一个图：

当有新的结点添加到链表中时，原来最后一个结点的指针将保存新添加的结点的地址，而新的结点的指针将指向NULL(空)，新的结点就变为最后一个结点。

3.动态链表

建立动态链表就是指程序运行过程中，从无到有建立一个链表，即一个一个分配结点内存空间，然后输入结点中的数据，并建立结点间的相连关系。
下面我们来建立一个动态链表：
首先创建结点结构:

struct student
{
    char cname[20];   //学生姓名 （数据部分）
	int inumber;      //学生学号 （数据部分）
	struct student *pNext;    //指向下一个结点的指针  （指针部分） 
}

然后定义一个Create函数，用来创建链表,其函数返回链表头指针：

Static int icount=0;         //定义一个全局变量表示链表长度，结点计数器
struct student*create()
{
	struct student *pHead=NULL;     //初始化头指针
	struct student *pone，*PoneNew; //初始化两个结构体指针
	*PoneNew=(struct student*) malloc(sizeof (struct student));   //申请一个新的内存空间，使PoneNew指向这个新内存。
	printf("请输入姓名和名字\n")； 
	scanf("%S",&poneNew->cname);    //赋值给新元素内的成员
	scanf("%S",&poneNew->inumber);  //赋值给新元素内的成员
    while(poneNew->inumber ！=0)    //当输入了新学号时
  {
		icount++;       //代表多了一个元素结点 icount加1        
		if(count==1)    //如果该链表第一个元素结点还没有建立
		{
		  poneNew->pNext=NULL;     //将新的结点的指针部分指向空
		  pone=poneNew;            //加入新的结点
		  pHead=poneNew;           //头指针指向新的结点
		} 
		else
		{
		poneNew->pNext=NULL;       //将新的结点的指针部分指向空
		pone->Next=poneNew;        //将原来的结点的指针部分指向新的结点
		pone=poneNew;              //将新的结点地址给pone，使得下一次再增加结点前，pone为最后一个元素结点。
		}	
  }
  return pHead;
 }

以上是从无到有建立一个动态链表的过程。

4.链表的插入和删除

上面我们从0到1建立了动态链表，那如何实现插入和删除操作呢，我们接着往下看。
我们设计一个函数可以实现链表的插入：

struct Node 
{
	.....                     //省略数据部分
	struct Node * Next;       //指向下一个结点的指针  （指针部分）
}:
	int InsertElement (struct Node *List,int I, struct Node *Node)
	{                // List为链表第一个节点地址，I为要插入的第n个元素，如果存在，返回I，否则返回 0                     
	struct Node *pOne=NULL;
	struct Node *pNewOne=NULL;
	int j=0;      //计数器
	pOne= List;  //指向数组的第一个节点
	
	While((pOne!=NULL)&&j<I-1)   //顺序查找，一直到目标节点的前一节点 
	{  
		pOne=pOne->Next;        //到下一个节点
		j++;                    //计数加1
	}
	if((pOne->Next==NULL)||(j>I-1)) //第I个元素不存在
		return 0:
	pNewOne= ( struct Node *)malloc(sizeof(struct Node));  //申请一个内存空间，并且将内存地址赋值给pNewOne
	{/*拷贝参数Node信息到新增加的节点pNewOne*/
	pNewOne ->Next= Node ->Next;     //（这里的Node是函数里传来的形参）把新的Node的指针部分指向的地址赋给pNewOne里的指针部分。
	pNewOne ->Next= pOne ->Next;     //将下一结点的地址赋值给插入的节点里，也就是让插入的节点指向下一节点（把新节点和后一位连起来）
	pOne ->Next= pNewOne;           //将前一节点的指针部分指向插入的新节点的地址（把新节点和前一位节点的连起来）	
	return j:
}

下面我们再进行链表的删除操作：

struct Node 
{
	.....                     //省略数据部分
	struct Node * Next;       //指向下一个结点的指针  （指针部分）
}:
	int InsertElement (struct Node *List,int I)
	{                // List为链表第一个节点地址，I为要删除的第n个元素，如果存在，返回I，否则返回 0                     
	struct Node *pOnepre=NULL;    //ponepre表示被删除节点的前一个节点
	struct Node *pDeleteOne=NULL; //pDeleteOne表示要删除的节点
	int j=0;      //计数器
	pOnepre= List;  //指向数组的第一个节点
	pDeleteOne=List;
	
	While((pDeleteOne!=NULL)&&j<I-1)   //顺序查找，一直到要删除的目标节点
	{  
		ponepre=pDeleteOne;                 //保存好前一节点
		pDeleteOne=pDeleteOne->Next;        //到下一个节点
		j++;                    //计数加1
	}
	if((pDeleteOne->Next==NULL)||(j>I-1)) //第I个元素不存在
		return 0:
	
	pOne ->Next= pDeleteOne ->Next;     //将要删除的节点的下一节点的地址赋给要删除的节点的前一节点的指针中（有点拗口）
	free(pDeleteOne);      //使用free释放内存空间，删除节点
	return j:
}

好了，以上就是链表的插入和删除操作，希望能对你有帮助~~后面再补充双链表和循环链表的内容。

前言

大家好~
在学习C语言的过程中，动态链表的相关操作总是会把我弄得有点晕。思路是有的，但是写完代码之后就很容易被自己绕晕。
于是今天想把我在链表的创建、输出、插入删除的过程中出现的问题总结一下，理清一下自己的思路，防止以后再犯同样的错。

关于链表

链表是一种常见的重要的数据结构。
它是动态地进行存储分配的一种结构。链表有一个头指针变量，它存放一个地址，该地址指向一个元素。
链表中每一个元素称为结点，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。
可以看出，头指针 head 指向第一个元素，第一个元素又指向第二个元素……
直到最后一个元素，该元素不再指向其他元素，它称为表尾，它的地址部分放一个 NULL（表示空地址）链表到此结束。

可以得出：
1. 链表中各元素在内存中可以不是连续存放的，要找某一元素，必须先找到上一个元素，根据它提供的下一元素地址才能找到下一个元素。
2. 如果不提供头指针 head 则整个链表无法访问。

题目

动态建立一个长度为4的链表，用于存储学生的信息（姓名与学号），并输出；且实现插入与删除功能，所有功能通过写成函数来实现。

C语言代码

PS：我使用的是 Visual Studio 2019，里面的scanf_s就等同于scanf，但字符串的输入需要在后面标注字符串的大小，否则系统会报错，调试不了。

引入函数：

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define LEN sizeof(struct student)

定义结构体：

typedef struct student
{
	char name[20];
	int num;
	struct student* next;
}STU;
int n = 0;

一、动态链表的创建

代码如下：

STU* create()
{
	STU* p1, * p2, * head;
	char name[20];
	int num;
	head = NULL;
	p1 = p2 = (STU*)malloc(LEN); //开创一个空间用于存放结构体内的数据
	printf("请输入学号与姓名：（格式：学号，姓名）\n");
	scanf_s("%d,%s", &p1->num, &p1->name, 20);
	while (p1->num != 0) //num=0时，链表创建结束
	{
		n++; //输入了多少个学生的数据
		if (n == 1)
			head = p1; //把第一个结点的地址赋给head指针
		else
			p2->next = p1; //如果输入的不是第一个结点的数据，就让其内的next指针指向下一个结点的开头
		p2 = p1; //p2指针移动到p1指针处（下一个结点的开头）
		p1 = (STU*)malloc(LEN);//p1又指向新开创结点的开头
		scanf_s("%d,%s", &p1->num, &p1->name, 20);
	}
	p2->next = NULL; //如果输入的num=0，跳出循环，最后一个结点的next指针指向空指针（即指向NULL值）
	return head; //返回第一个结点的地址（这样才能找到后面的所有结点）
}

二、动态链表的输出

代码如下：

void print(STU* head) //输出学生信息的函数
{
	STU* p;
	p = head; //p取head的地址之后，二者同时指向第一个结点的开头
	n == 0;
	printf("\n");
	if (head != NULL)
	{
		do
		{
			printf("学号：%d 姓名：%s\n", p->num, p->name);
			p = p->next; //把next的地址（即下一个结点的开头）赋给p
			n++;
		} while (p != NULL);
	}
	printf("\n现在共有%d个学生的信息：\n", n);
}

三、动态链表的插入

（1）找到位置p（ai-1）
（2）生成新结点s，数据域赋值
（3）新结点指针域指向ai（ai的地址存放在ai-1的指针域）
（4）ai-1的指针域指向新结点s

代码如下：

STU* insert_link(STU* head) //插入结点的函数
{
	STU* p;
	printf("请输入需要插入数据的位置：\n");
	int m;
	scanf_s("%d", &m);
	p = head; //p与head指向第一个结点的开头
	int i = 1; //插入位置
	printf("请输入需要插入的数据 : （格式：学号，姓名）\n");
	STU* j;
	j = (STU*)malloc(LEN);
	scanf_s("%d,%s",  &j->num, &j->name, 20);
	if (m == 1) //如果要在第一个位置插入数据
	{
		j->next = head; //新的结点的next指针直接指向头结点，新的数据就会成为第一个结点
		head = j; //head指针又指向第一个结点的开始
		return head; //返回插入数据后的头结点
	}
	else
	{
		while (i < m - 1)
			/*m-1意味着：如果要在第5个位置插入数据，
			则需要让第4个结点的next指向插入数据的开头*/
		{
			p = p->next; //循环找到需要插入数据的上一个结点的next所在位置
			i++;
		}
	}
	j->next = p->next; //把p的next地址赋给j的next地址，即新的结点可插入两个结点的中间
	p->next = j; //p的next指向j的地址
	return head; //返回第一个结点的地址
}

四、动态链表的删除

（1）找到要删除的结点前一个结点p（原因是删除结点的位置在前一个结点的指针域）
（2）把p->next指向ai的下一个结点（把ai从链上摘除）
（3）释放ai空间

代码如下：

STU* delete_link(STU* head)//删除结点的函数
{
	STU* p1, * p2;
	printf("请输入需要删除数据的位置：\n");
	int m;
	scanf_s("%d", &m);
	p1 = head;
	if (m == 1) //如果删除的是第一个结点
	{
		p2 = p1->next; //直接把下一个地址作为返回值
		free(p1); //释放内存
		return p2;
	}
	else
	{
		int i = 1;
		while (i < m - 1)
		{
			p1 = p1->next;
			i++;
		}
		p2 = p1->next;
		p1->next = p1->next->next; //p1的next指向了需要删除的结点的next指向的结点（即越过了中间需要删除的结点）
		free(p2); //释放需要删除的结点的空间
		return head; //返回第一个结点的地址
	}
}

五、总代码

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define LEN sizeof(struct student)

typedef struct student
{
	char name[20];
	int num;
	struct student* next;
}STU;
int n = 0;
STU* create()
{
	STU* p1, * p2, * head;
	char name[20];
	int num;
	head = NULL;
	p1 = p2 = (STU*)malloc(LEN);//开创一个空间用于存放结构体内的数据
	printf("请输入学号与姓名：（格式：学号，姓名）\n");
	scanf_s("%d,%s", &p1->num, &p1->name, 20);
	while (p1->num != 0)//num=0时，链表创建结束
	{
		n++;//输入了多少个学生的数据
		if (n == 1)
			head = p1;//把第一个结点的地址赋给head指针
		else
			p2->next = p1;//如果输入的不是第一个结点的数据，就让其内的next指针指向下一个结点的开头
		p2 = p1;//p2指针移动到p1指针处（下一个结点的开头）
		p1 = (STU*)malloc(LEN);//p1又指向新开创结点的开头
		scanf_s("%d,%s", &p1->num, &p1->name, 20);
	}
	p2->next = NULL;//如果输入的num=0，跳出循环，最后一个结点的next指针指向空指针（即指向NULL值）
	return head;//返回第一个结点的地址（这样才能找到后面的所有结点）
}
STU* insert_link(STU* head)//插入结点的函数
{
	STU* p;
	printf("请输入需要插入数据的位置：\n");
	int m;
	scanf_s("%d", &m);
	p = head;//p与head指向第一个结点的开头
	int i = 1;//插入位置
	printf("请输入需要插入的数据 : （格式：学号，姓名）\n");
	STU* j;
	j = (STU*)malloc(LEN);
	scanf_s("%d,%s",  &j->num, &j->name, 20);
	if (m == 1)//如果要在第一个位置插入数据
	{
		j->next = head;//新的结点的next指针直接指向头结点，新的数据就会成为第一个结点
		head = j;//head指针又指向第一个结点的开始
		return head;//返回插入数据后的头结点
	}
	else
	{
		while (i < m - 1)
			/*m-1意味着：如果要在第5个位置插入数据，
			则需要让第4个结点的next指向插入数据的开头*/
		{
			p = p->next;//循环找到需要插入数据的上一个结点的next所在位置
			i++;
		}
	}
	j->next = p->next;//把p的next地址赋给j的next地址，即新的结点可插入两个结点的中间
	p->next = j;//p的next指向j的地址
	return head;//返回第一个结点的地址
}

STU* delete_link(STU* head)//删除结点的函数
{
	STU* p1, * p2;
	printf("请输入需要删除数据的位置：\n");
	int m;
	scanf_s("%d", &m);
	p1 = head;
	if (m == 1) //如果删除的是第一个结点
	{
		p2 = p1->next; //直接把下一个地址作为返回值
		free(p1); //释放内存
		return p2;
	}
	else
	{
		int i = 1;
		while (i < m - 1)
		{
			p1 = p1->next;
			i++;
		}
		p2 = p1->next;
		p1->next = p1->next->next;//p1的next指向了需要删除的结点的next指向的结点（即越过了中间需要删除的结点）
		free(p2);//释放需要删除的结点的空间
		return head;//返回第一个结点的地址
	}
}

void print(STU* head)//输出学生信息的函数
{
	STU* p;
	p = head;//p取head的地址之后，二者同时指向第一个结点的开头
	n == 0;
	printf("\n");
	if (head != NULL)
	{
		do
		{
			printf("学号：%d 姓名：%s\n", p->num, p->name);
			p = p->next;//把next的地址（即下一个结点的开头）赋给p
			n++;
		} while (p != NULL);
	}
	printf("\n现在共有%d个学生的信息：\n", n);
}


void main()
{
	STU* pointer;
	pointer = create();//创建动态链表，返回第一个结点的地址赋给pointer
	n = 0;//n清零，为了保证之后函数里，从第一个结点开始遍历
	print(pointer);//输出链表
	pointer = insert_link (pointer);
	n = 0;
	print(pointer);//输出链表
	pointer = delete_link(pointer);
	n = 0;
	print(pointer);//输出链表
	free(pointer);//释放占用的内存
	system("pause");
}

总结

以上就是关于动态链表的一些具体操作，在整理之后，我对链表的结构和一些内容也有了更加深入的了解。
如果大家对于这个内容和代码还有更好的建议，请多多指正~谢谢！

静态链表：
1.静态链表和动态链表的区别：
  静态链表要预先申请一整块足够内存的空间，其能存储的元素个数在创建的那一刻就不能再更改了。
  动态链表：之前实现的单链表，双链表，循环链表都属于动态链表，可以在使用过程中动态申请内存。
2.静态链表是一种用数组描述的链表，其实是为了给没有指针的高级语言设计的一种实现单链表功能的方法（大话数据结构）。
3.静态链表其实包括两个链表，一个是数据链表，一个是空闲链表。
3.静态链表的第一个节点和最后一个节点作为特殊元素处理，
  第一个节点作为备用链表的表头，其cur值指向下一个空闲的节点。
  最后一个节点作为数据链表的表头，其cur值指向第一个有数据的节点。
4.优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进在顺序存储结构中插入和删除元素需要移动大量元素的缺点
   缺点：没有解决连续存储分配带来的表长难以确定的问题。
5.注意静态链表的删除操作，删除操作要更新两个链表，数据链表要更新前一节点的cur,
   空闲链表要把空出的节点放入空闲链表的第一个节点（不能放入空闲链表的末尾，因为找不到空闲链表的末尾），大话数据结构也是放入空闲链表的第一个位置

静态链表C语言实现：

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<signal.h>  //signal()
#include<string.h>
#include<sys/stat.h>
#include<time.h>
#include<stdarg.h>

#if 1
#define INFO_DEBUG    "%d lines in "__FILE__", complie time is "__TIME__" "__DATE__" \n",__LINE__
#define ADI_RUN_ERROR      1
#define ADI_NULL_POINTER  -1
#define ADI_OK             0
#define ADI_PRINT         printf("[%s][%d]:",__FUNCTION__,__LINE__);printf
#define ADI_ASSERT(c,prt,ret)       if(c) {printf(prt);return ret;}
#endif

typedef struct list{
    int elem;
    int cur;//静态链表中把这个称为游标（cursor）
}list;

#define PARAM_FAIL -1
#define P_NULL -2
#define SUCCESS 0
#define LIST_SIZE 10

/*初始化：只创建头结点*/
list* initList(int size)
{
    int i = 0;
    list *head = (list*)malloc(size*sizeof(list));
    if(NULL==head) {printf("NULL");return head;}
    for(i=0;i<(size-1);i++)
    {
		head[i].cur = i+1;//此时整个链表都是空闲链表,注意这里不能用head[i]->cur = i+1 会报错
    }
    head[i].cur = 0;/*目前静态链表为空，最后一个元素的cur为0*/
    return head;
}

/*销毁链表，销毁和初始化成对使用*/
int destoryList(list* list_destory)
{
	if(NULL==list_destory) {printf("NULL");return PARAM_FAIL;}
	free(list_destory);
	return SUCCESS;
}

/*pos从0开始，pos=0为第一个*/
int insertList(list list_insert[],int elem,int pos,int list_size)
{
    int i=0,empty_id=0,cur=0,last_cur=0;
    if((NULL == list_insert)&& (pos>(list_size-2)) )//最后一个元素作为特殊节点不容纳元素，则支持的插入位置要减2 比如size=10,最大支持的pos=8
    {
        ADI_PRINT("err param\n");
        return PARAM_FAIL;
    }

    /*取数据链表的表头*/
    list head_data = list_insert[list_size-1];//不能用 list *head_data = list_insert[list_size-1];,会报错
    cur = list_size-1;//cur的初始值要=list_size-1注意
    while(i<pos)
    {
        last_cur = cur;
        cur = head_data.cur;
    	head_data = list_insert[cur];
    	i++;
    }

    /*取空闲链表的表头list_insert[0]*/
    empty_id = list_insert[0].cur;//拿到第一个空闲位置
    list_insert[empty_id].elem = elem;
    list_insert[0].cur = list_insert[0].cur+1;//空闲位置指向下一个位置
    list_insert[empty_id].cur = list_insert[last_cur].cur;
    list_insert[last_cur].cur = empty_id;

    ADI_PRINT("insert elem = %d\n",elem);
    return SUCCESS;
}

/*删除操作要更新两个链表，数据链表要更新前一节点的cur,
空闲链表要把空出的节点放入空闲链表的第一个节点（不能放入空闲链表的末尾，因为找不到空闲链表的末尾），大话数据结构也是放入空闲链表的第一个位置*/
int delList(list list_del[],int elem,int list_size)
{
    int i=0,empty_id=0,cur=0,ele=0,last_cur=0;
    if(NULL == list_del)
    {
        ADI_PRINT("err NULL\n");
        return P_NULL;
    }

    /*取数据链表的表头*/
    list head_data = list_del[list_size-1];//不能用 list *head_data = list_insert[list_size-1];,会报错
    cur = head_data.cur;
    last_cur = list_size-1;
    while((list_del[cur].elem != elem)&&(0 != cur))
    {
        last_cur = cur;
        cur = list_del[cur].cur;
    }
    /*能找到,cur就是待删除元素在链表中的位置*/
    if(0 != cur)
    {
        //ADI_PRINT("elem cur = %d\n",cur);
		list_del[last_cur].cur = list_del[cur].cur;//将上一个数据节点的cur进行修改
		list_del[cur].cur  = list_del[0].cur;
		list_del[cur].elem = 0;
		/*取空闲链表的表头list_insert[0]，将被删除的元素放入空闲链表的第一个元素*/
		list_del[0].cur = cur;
    }
    else
    {
		ADI_PRINT("can not find ele = %d\n",elem);
		return PARAM_FAIL;
    }
    
    ADI_PRINT("del elem = %d\n",elem);
    return SUCCESS;

}

int printList(list list_prt[],int list_size)
{
    if(NULL == list_prt)
    {
        ADI_PRINT("err NULL\n");
        return P_NULL;
    }
    int i = 0;

    /*取数据链表的表头,按数据排布的顺序*/
    #if 0
    list head_data = list_prt[list_size-1];
    //ADI_PRINT("head_data.cur = %d\n",head_data.cur);
    while(head_data.cur)
    {
    	head_data = list_prt[head_data.cur];
    	//ADI_PRINT("head_data.cur = %d\n",head_data.cur);
    	ADI_PRINT("list[%d] = %d\n",i,head_data.elem);
    	i++;
    }
    #endif

    #if 1
    /*全部打印，按数组0-max顺序*/
    for(int i=0;i<list_size;i++)
    {
		ADI_PRINT("list[%d].ele=%d,list[%d].cur=%d\n",i,list_prt[i].elem,i,list_prt[i].cur);
    }
    #endif
    return SUCCESS;
}

int main()
{
    int ret = 0,pos = 0;
    list *list_test = initList(LIST_SIZE);
    if(NULL == list_test)
    {
        ADI_PRINT("err \n");
        return P_NULL;
    }
    printList(list_test,LIST_SIZE);

    ret = insertList(list_test,0,0,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    ret = insertList(list_test,3,1,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    ret = insertList(list_test,5,2,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    ret = insertList(list_test,7,3,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    ret = insertList(list_test,9,4,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    printList(list_test,LIST_SIZE);
    ret = insertList(list_test,8,4,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}
    printList(list_test,LIST_SIZE);

    ret = delList(list_test,3,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}  
    ret = delList(list_test,7,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;}  
    ret = delList(list_test,9,LIST_SIZE);
    if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} 
    printList(list_test,LIST_SIZE);

    
    return SUCCESS;
}