链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
和顺序表不同同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。
所以在链表中，每个数据元素可以配有一个指针用于找到下一个元素即节点，这意味着，链表上的每个“元素”都长下图这个样子：
链表的特性
逻辑结构：线性结构
存储结构：链式结构
特点：内存不连续，需要通过指针链接，大小不固定。解决顺序表插入麻烦的问题
操作：增删改查
struct node
{
int data; //数据域：存储数据
struct node *next; //指针域：存储下一个节点的地址
};
单向链表
有头链表：存在一个头节点，头节点数据域无效，指针域有效
无头链表：每一个节点的数据域和指针域都有效
遍历无头单项链表
#include
#include
typedef char datatype;
typedef struct node
{
datatype data; // 数据域用来保存数据
struct node *next; // 指针域用来保存下一个节点的地址
} node_t, *node_p;
int main(int argc, char const *argv[])
{
// 定义四个节点
node_t A = {'a', NULL};
node_t B = {'b', NULL};
node_t C = {'c', NULL};
node_t D = {'d', NULL};
// 连接四个节点
A.next = &B;
B.next = &C;
C.next = &D;
//定义一个头指针指向第一个节点
node_p p = &A;
//通过指针遍历无头单向链表
while (p != NULL)
{
printf("%c ", p->data);
p = p->next;
}
putchar('\n');
return 0;
}
遍历有头单向链表：
#include
#include
typedef char datatype;
typedef struct node
{
datatype data; // 数据域用来保存数据
struct node *next; // 指针域用来保存下一个节点的地址
} node_t, *node_p;
int main(int argc, char const *argv[])
{
// 定义四个节点
node_t A = {'a', NULL};
node_t B = {'b', NULL};
node_t C = {'c', NULL};
node_t D = {'d', NULL};
// 连接四个节点
A.next = &B;
B.next = &C;
C.next = &D;
//定义一个头结点，数据域无效，指针域有效
node_t S = {'\0',&A};
//定义一个头指针指向头结点
node_p p = &S;
#if 0
p = p->next;
while (p != NULL)
{
printf("%c ", p->data);
p = p->next;
}
putchar('\n');
#else
while (p->next != NULL)
{
p = p->next;
printf("%c ",p->data);
}
#endif
return 0;
}
链表尾插法练习：
写一个有头单向链表，用于保存输入的学生成绩，实现一输入学生成绩就创建一个新的节点，将成绩保存起来。再将该节点链接到链表的尾，直到输入-1结束。
要求：每个链表的节点由动态内存分配得到 , 也就是用malloc。
过程：
malloc申请空间link_node_t大小作为头节点
将新节点放到链表尾部
//链表尾插法
#include
#include
typedef struct student
{
int score;
struct student *next;
} link_node_t, *link_node_p;
int main(int argc, char const *argv[])
{
// 循环输入学生成绩，直到-1结束
link_node_p p = (link_node_p)malloc(sizeof(link_node_t));
if (NULL == p)
{
printf("error!\n");
return -1;
}
p->next = NULL;//初始化头结点
link_node_p ptail = p;//尾节点一开始先指向头结点
int sum = -1;
//循环输入学生成绩，直到-1结束，创建新节点保存学生成绩，尾插到链表
while (1)
{
printf("input:");
scanf("%d", &sum);
if (-1 == sum)
break;
link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));//创建新节点来保存学生成绩
if (NULL == pnew)
{
perror("pnew malloc err!\n");
return -1;
}
pnew->score = sum;
pnew->next = NULL;//新节点指针域置空
ptail->next = pnew;//尾节点的指针域保存新节点的地址
ptail = pnew;//尾节点移动到新节点，因为尾指针ptail要一直指向最后一个节点
}
//循环遍历
while (p->next != NULL)
{
p = p->next;
printf("%d ", p->score);
}
putchar('\n');
return 0;
}
有头单向链表的函数操作：
插入指定节点
删除指定节点：
删除指定数据节点：
链表转置：
1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表。
2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(头插)，插入之前先用t保存一下q的下一个节点以防插入完找不到原来链表。