今天继续学习线性表中的链表，顺序表的相关知识可以查看相关文章http://t.csdnimg.cn/IhHGp
目录
链表
结构体
分类
1.有头单向链表
2.无头单向链表
操作函数
单向链表的相关操作案例
顺序表和单向链表比较
链表
特点：内存不连续，通过指针进行连接
解决: 长度固定的问题，插入删除麻烦的问题
逻辑结构：线性结构
存储结构：链式存储
操作：增删改查
结构体
struct node_t
{
int data;//数据域
struct node_t * next;//指针域
}；
分类
1.有头单向链表
存在一个头节点，数据域无效，指针域有效
遍历有头单向链表
#include <stdio.h>typedef struct node_t
{int data;struct node_t *next;
} link_node_t, *link_list_t;int main(int argc, char const *argv[])
{// 1.定义几个节点(结构体变量)link_node_t s0;link_node_t s1 = {1, NULL};link_node_t s2 = {2, NULL};link_node_t s3 = {3, NULL};// 2.将节点连接到一起s0.next = &s1;s1.next = &s2;s2.next = &s3;// 3.定义一个头指针，指向头节点link_list_t p = &s0;// // 4.遍历有头单向链表（第一种方法）// while (p->next != NULL)// {// p = p->next;// printf("%d ", p->data);// }// printf("\n");// 4.遍历有头单向链表（第二种方法）p = p->next;while (p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");return 0;
}
2.无头单向链表
所有节点的指针域和数据域都有效
遍历无头单向链表
#include <stdio.h>typedef struct node_t
{int data;struct node_t *next;
} link_node_t, *link_list_t;int main(int argc, char const *argv[])
{// 1.定义几个节点(结构体变量)link_node_t s1 = {1, NULL};link_node_t s2 = {2, NULL};link_node_t s3 = {3, NULL};// 2.将节点连接到一起s1.next = &s2;s2.next = &s3;// 3.定义一个头指针，指向第一个节点link_list_t p = &s1;// 4.遍历无头单向链表while (p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");return 0;
}
操作函数
1.创建一个空的（有头）单向链表
2.向post位置插入一个数据
1、先遍历找到要插入节点的前一个节点，假设这个节点为A；A的下一个节点为B；将C插入A与B之间；
2、先让C的指针域指向B；
3、再让A的指针域指向C；
（注意：顺序不可以调换）
3）删除指定位置的数据
1、先遍历找到要删除节点的前一个节点，假设为A；
2、找一个临时指针指向要删除的节点；
3、将A的指针域指向删除节点的下一个节点；
4、释放被删除节点
4）单向链表的转置
(1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表
(2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)
单向链表的相关操作案例
头文件linklist.h:
#ifndef _LINKLIST_H_
#define _LINKLIST_H_#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node_t
{datatype data; // 数据域struct node_t *next; // 指针域,指向自身结构体的指针
} link_node_t, *link_list_t;// 1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
// 2.向单向链表的指定位置插入数据
// p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p, int post, datatype data);
// 3.遍历单向链表
void ShowLinkList(link_node_t *p);
// 4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
// 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
// 6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
// 7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
// 8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
// 9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data);
// 10.转置链表
void ReverseLinkList(link_node_t *p);
// 11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif
单向链表函数linklist.c：
#include "linklist.h"// 1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList()
{link_list_t p = (link_list_t)malloc(sizeof(link_node_t));if (p == NULL){perror("CreateEpLinkList函数出错\n");return NULL;}p->next = NULL;return p;
}// 2.向单向链表的指定位置插入数据
// p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p, int post, datatype data)
{// 0.容错判断if (post < 0 || post > LengthLinkList(p)){perror("InsertIntoPostLinkList函数出错\n");return -1;}// 1.将头指针移动到被插入位置的前一个节点for (int i = 0; i < post; i++){p = p->next;}// 2.创建一个新的节点，保存即将插入的数据link_list_t pnew = CreateEpLinkList();pnew->data = data;// 3.将新节点赋值插入链表（先赋前面，再赋后面）pnew->next = p->next;p->next = pnew;return 0;
}// 3.遍历单向链表
void ShowLinkList(link_node_t *p)
{while (p->next != NULL){p = p->next;printf("%d ", p->data);}printf("\n");
}// 4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{int len = 0;while (p->next != NULL){p = p->next;len++;}return len;
}// 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)
{// 0.容错判断if (post < 0 || post >= LengthLinkList(p) || IsEpLinkList(p)){perror("DeletePostLinkList函数出错\n");return -1;}// 1.将头指针移动到被删除位置的前一个节点for (int i = 0; i < post; i++){p = p->next;}// 2.进行删除操作// 定义pdel指向被删除的节点link_list_t pdel = p->next;// 跨过被删除的节点p->next = pdel->next;// 释放被删除的节点free(pdel);pdel = NULL;return 0;
}// 6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{return p->next == NULL;
}
// 7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data)
{// 0.容错判断if (post < 0 || post >= LengthLinkList(p) || IsEpLinkList(p)){perror("ChangePostLinkList函数出错\n");return -1;}for (int i = 0; i <= post; i++){p = p->next;}p->data = data;return 0;
}
// 8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data)
{int n = 0;int flag = 0;while (p->next != NULL){p = p->next;if (p->data == data){printf("该数据的位置为：%d\n", n);flag++;}n++;}if (flag == 0){printf("链表里没有该数据\n");}return 0;
}
// 9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
{// 1.定义一个指针指向头节点的下一个节点，此时可以看作q指向一个无头单向链表link_list_t q = p->next;// 2.用q遍历无头单向链表，将每一个节点的数据域和data作比较，如果相同就删除while (q != NULL){if (q->data == data) // 如果相等，说明需要删除q指向的节点{p->next = q->next;free(q);q = p->next;}else // 不相等，指针向后移动{p = p->next;q = p->next;}}return 0;
}// 10.转置链表
void ReverseLinkList(link_node_t *p)
{link_list_t temp = NULL; // 临时保存q下一个节点的地址// 断开前，保存头节点的下一个节点的地址link_list_t q = p->next; // 指向头节点的下一个节点（相当于无头单向链表的头指针）// 1.断头，断开链表p->next = NULL;// 2.遍历无头单向链表while (q != NULL){// 暂时存放q的下一个节点，防止链表丢失temp = q->next;// 头插到有头单向链表头节点的后面q->next = p->next;p->next = q;// 将q重新指向之前的无头单向链表，指向此时的第一个节点q = temp;}
}// 11.清空单向链表
void ClearLinkList(link_node_t *p)
{// while (!IsEpLinkList(p))// {// link_list_t pdel = p->next;// p->next = pdel->next;// free(pdel);// pdel = NULL;// }while (!IsEpLinkList(p)){DeletePostLinkList(p, 0);}
}主函数：main.c：
#include "linklist.h"int main(int argc, char const *argv[])
{int post;int data;link_list_t s1 = CreateEpLinkList();InsertIntoPostLinkList(s1, 0, 1);InsertIntoPostLinkList(s1, 1, 2);InsertIntoPostLinkList(s1, 2, 3);InsertIntoPostLinkList(s1, 3, 4);printf("最初链表数据：\n");ShowLinkList(s1);printf("请输入你要插入的数据的位置和数据：\n");scanf("%d %d", &post, &data);InsertIntoPostLinkList(s1, post, data);printf("插入以后链表数据：\n");ShowLinkList(s1);printf("请输入你要删除的数据的位置：\n");scanf("%d", &post);DeletePostLinkList(s1, post);printf("删除以后链表数据：\n");ShowLinkList(s1);printf("请输入你要修改的数据的位置和数据：\n");scanf("%d %d", &post, &data);ChangePostLinkList(s1, post, data);printf("修改以后链表数据：\n");ShowLinkList(s1);printf("请输入你要删除的数据：\n");scanf("%d", &data);DeleteDataLinkList(s1, data);printf("删除以后链表数据：\n");ShowLinkList(s1);ReverseLinkList(s1);printf("转置以后链表数据：\n");ShowLinkList(s1);printf("请输入你要查找的数据：\n");scanf("%d", &data);SearchDataLinkList(s1, data);ClearLinkList(s1);if (IsEpLinkList(s1)){printf("已经清空单向链表\n");}free(s1);s1->next = NULL;return 0;
}
顺序表和单向链表比较
(1)顺序表在内存当中连续存储的(数组)，但是链表在内存当中是不连续存储的，通过指针将数据链接在一起
(2)顺序表的长度是固定的，但是链表长度不固定
(3)顺序表查找方便，但是插入和删除麻烦，链表，插入和删除方便，查找麻烦
