（创作不易，感谢有你，你的支持，就是我前行的最大动力，如果看完对你有帮助，请留下您的足迹）
提示：本章的对应项目为学生成绩管理系统 ，大家学完单链表以后就可以尝试去做一个学生成绩管理系统啦！（http://t.csdn.cn/1VrMy）
目录
初始链表：
链表是由n个结点链结成，第一个结点的存储位置叫做头指针，最后一个结点的指针为“空” 结点包括数据域和指针域。
//创建一个结点 typedef struct monster{ //数据域 int id; //怪物编号 char *name; //怪物名称 //指针域 struct monster *pNext;//指向下一节点的指针 } Monster;
在给结构体赋值时，具体形式如下：
我们来画个图便于大家理解：
如图所示，每一个元素的指针域都保存的是下一个元素的地址，而最后一个元素的指针域是空指针NULL；每一个元素串联起来的形式就形成了一个链表。
链表的头指针和头结点：
头指针：链表中第一个结点的存储位置。
头结点：在单链表的第一个结点前附设的一个结点。
两者的异同点：
单链表：
链表的每一个结点中只包含一个指针域。
//单链表 typedef struct student{ int id; //学生编号 char *name; //学生名称 //指向下一节点的指针 struct student *pNext; } Student;
如下情况则不是单链表：
//不属于单链表 typedef struct student{ int id; //学生编号 char *name; //学生名称 //指向下一节点的指针 struct student *pNext; struct student *qNext; } Student;
单链表的读取：
获取第i个结点的数据
声明一个结点指针p指向链表第一个结点𝒂1 ，初始化j从1开始；
当j<i时，遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
若当链表末尾p为空，则说明第i个元素不存在；否则查找成功，返回结点p的数据。
单链表的插入：
在第i个结点之后插入数据元素
创建一个空结点，分配内存空间，设置元素数据
获取第i个结点，设置新结点的后继结点为该结点的后继结点
设置第i个结点的后继结点为新结点
提示：
1. 插入操作最后最好有插入成功或失败的返回值。
2. 如果有头结点，并且记录了链表长度，则最后长度也要加 1
3. 有头结点的单链表插入操作才能统一。
/** 定义链表的结点，包含数据域和指针域 */ typedef struct Node{ ElementType data; //数据域 struct Node * next; //指针域，指向下个结点 }Node; /** * 头结点 * 注意：我们在定义链表时，习惯性的会定义头结点，以便统一链表结点的插入和删除操作 * 头结点也可以称为首元结点，最后一个结点叫做尾元结点 */ typedef struct LinkList{ Node * next; //头指针（如果链表有头结点，next就指向头结点；没有就指向第一个结点） int length; //链表的长度，初始值为0 }LinkList; /** 初始化链表 */ void InitLinkList(LinkList * linkList, ElementType * dataArray, int length) { for(int i = 0; i < length; i++){ InsertLinkList(linkList, i + 1, dataArray[i]); } } /** * 在指定的位置pos插入元素element */ void InsertLinkList(LinkList * linkList, int pos, ElementType element) { //1.创建空结点并为数据域赋值 Node * node = (Node *)malloc(sizeof(Node)); node->data = element; node->next = NULL; //2、找到要插入位置的结点 if(pos == 1){//如果插入的是第一个元素，就非常简单 linkList->next = node; linkList->length++; return; } //通过循环找到要插入的结点位置 Node * currNode = linkList->next; for(int i = 1; currNode && i < pos - 1; i++){ currNode = currNode->next; } //3、将结点插入并对接前面的结点 if(currNode){ node->next = currNode->next; currNode->next = node; linkList->length++; } }
单链表的删除：
删除第i个结点及其数据元素
获取第i个结点，若该节点不是第一个结点，则获取第i-1个结点
将第i-1个结点的后缀结点设为第i个结点的后缀结点
删除第i个结点，释放内存空间，记录并返回删除的数据元素的值
提示：
1. 如果有头结点，并且记录了链表长度，则最后长度也要减1
2. 若没有找到结点，则返回-1
3. 若该链表没有头结点，并且第i个结点是第一个结点，记录第一个结点为第 i+1 个结点，然后释放该节点。
/** 删除并返回指定位置的元素 */ ElementType DeleteLinkListElement(LinkList * linkList, int pos){ ElementType element; //被删除的元素 element.id = -999; //赋一个不可能的值，用来判断是否删除成功 Node * node = NULL; if(pos == 1){ node = linkList->next; if(node){ element = node->data; linkList->next = node->next; free(node);//释放被删除结点的内存 - 容易遗漏 linkList->length--; } return element; } //1、找到要删除结点和它的前缀结点 //2、要删除结点->next赋值给前缀结点->next //3、释放要删除的结点内存 Node * preNode; //前缀结点 node = linkList->next; for(int i = 1; node && i < pos; i++){ preNode = node; node = node->next; } if(node){ element = node->data; preNode->next = node->next; free(node); linkList->length--; } return element; }
单链表的整表删除：
销毁单链表，释放内存空间
1.声明结点p和q
2.将第一个结点赋值给p
3.循环将下一个结点赋值给q,释放p,将q赋值给p
void clearList(LinkList *L) { LinkList p,q; p = (*L)->next; //p为第一个结点 while(p)//没到表尾 { q = p->next; free(p); p = q; } (*L)->next = NULL; (*L)->length = 0; }
