线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构
非线性结构：不满足线性结构的数据结构
链表（单向链表的建立、删除、插入、打印）
1、链表一般分为：
单向链表
双向链表
环形链表
2、基本概念
链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，
且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作
链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，
除了存储元素本身的信息外，还要存储其直接后继信息，因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，这里用data表示，
它不局限于一个成员数据，也可是多个成员数据，第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息，这里用next表示，
next的值实际上就是下一个节点的地址，当前节点为末节点时，next的值设为空指针
1 struct link
2 {
3 int data;
4 struct link *next;
5 };
像上面这种只包含一个指针域、由n个节点链接形成的链表，就称为线型链表或者单向链表，链表只能顺序访问，不能随机访问，链表这种存储方式最大缺点就是容易出现断链，
一旦链表中某个节点的指针域数据丢失，那么意味着将无法找到下一个节点，该节点后面的数据将全部丢失
3、链表与数组比较
数组（包括结构体数组）的实质是一种线性表的顺序表示方式，它的优点是使用直观，便于快速、随机地存取线性表中的任一元素，但缺点是对其进行 插入和删除操作时需要移动大量的数组元素，同时由于数组属于静态内存分配，定义数组时必须指定数组的长度，程序一旦运行，其长度就不能再改变，实际使用个数不能超过数组元素最大长度的限制，否则就会发生下标越界的错误，低于最大长度时又会造成系统资源的浪费，因此空间效率差
4、单向链表的建立
#include <stdio.h>
#include <stdlib.h>
struct link *AppendNode (struct link *head);
void DisplyNode (struct link *head);
void DeletMemory (struct link *head);
struct link
{
int data;
struct link *next;
};
int main(void)
{
int i = 0;
char c;
struct link *head = NULL; //链表头指针
printf("Do you want to append a new node(Y/N)?");
scanf_s(" %c", &c);
while (c == 'Y' || c == 'y')
{
head = AppendNode(head);//向head为头指针的链表末尾添加节点
DisplyNode(head); //显示当前链表中的各节点的信息
printf("Do your want to append a new node(Y/N)");
scanf_s(" %c", &c);
i++;
}
printf("%d new nodes have been apended", i);
DeletMemory(head); //释放所有动态分配的内存
return 0;
}
/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */
struct link *AppendNode(struct link *head)
{
struct link *p = NULL, *pr = head;
int data;
p = (struct link *)malloc(sizeof(struct link));//让p指向新建的节点
if (p == NULL) //若新建节点申请内存失败，则退出程序
{
printf("No enough memory to allocate\n");
exit(0);
}
if (head == NULL) //若原链表为空表
{
head = p; //将新建节点置为头节点
}
else //若原链表为非空，则将新建节点添加到表尾
{
while (pr->next != NULL)//若未到表尾，则移动pr直到pr指向表尾
{
pr = pr->next; //让pr指向下一个节点
}
pr->next = p; //让末节点的指针指向新建的节点
}
printf("Input node data\n");
scanf_s("%d", &data); //输入节点数据
p->data = data; //将新建节点的数据域赋值为输入的节点数据值
p->next = NULL; //将新建的节点置为表尾
return head; //返回添加节点后的链表的头指针
}
/* 函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容*/
void DisplyNode (struct link *head)
{
struct link *p = head;
int j = 1;
while (p != NULL) //若不是表尾，则循环打印节点的数值
{
printf("%5d%10d\n", j, p->data);//打印第j个节点数据
p = p->next; //让p指向下一个节点
j++;
}
}
//函数的功能：释放head所指向的链表中所有节点占用的内存
void DeletMemory(struct link *head)
{
struct link *p = head, *pr = NULL;
while (p != NULL) //若不是表尾，则释放节点占用的内存
{
pr = p; //在pr中保存当前节点的指针
p = p->next;//让p指向下一个节点
free(pr); //释放pr指向的当前节点占用的内存
}
}
上面的代码使用了三个函数AppendNode、DisplyNode、DeletMemory
struct link *AppendNode (struct link *head);（函数作用：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针）
void DisplyNode (struct link *head);（函数功能：显示链表中所有节点的节点号和该节点中的数据项的内容）
void DeletMemory (struct link *head);（函数功能：释放head所指向的链表中所有节点占用的内存）
（还使用了malloc函数和free函数）
5、malloc函数