线性表-链式存储(头插与尾插)
对头指针概念的理解，这个很重要。“链表中第一个结点的存储位置叫做头指针”，如果链表有头结点，那么头指针就是指向头结点数据域的指针。画一个图吧。
头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
头结点不是链表所必需的。
在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
头指针具有标识作用，故常用头指针冠以链表的名字。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
单链表也可以没有头结点。如果没有头结点的话，那么单链表就会变成这样：
------------------------------------------------------------------------------------------------------------------
单链表整表创建的算法思路：
- 声明一结点p和计数器变量i；
- 初始化一空链表L；
- 让L的头结点的指针指向NULL,即建立一个带头结点的单链表；
- 循环：
- 生成一新结点赋值给p;
- 随机生成一数字赋值给P的数据域p->data;
- 将p插入到头结点与前一新结点之间。
头插法创建链表
//头插法创建链表的函数
void CreateListHead(LinkList *L, int n)
{
//声明一结点p和计数器变量i
LinkList p;
int i;
srand(time(0)); //初始化随机数种子
//初始化一空链表L，让L的头结点的指针指向NULL,即建立一个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));//开辟一个L结构大小的内存地址
(*L)->next = NULL;//先建立一个带头结点的单链表
for (i=0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); //生成新结点
p->data = rand() % 100 + 1; // 随机生成100以内的数字
p->next = (*L)->next;// 指向下一个
(*L)->next = p;// 插入到表头
}
}
1. 首先用 *L = (LinkList)malloc(sizeof(Node)); 产生头结点，并使L指向此头结点。再用 (*L)->next = NULL; 即可创建一个带头结点的空链表。
2. 接下来就是循环啦。新增结点都需要用 (LinkList)malloc(sizeof(Node)); 来开辟内存空间。生成结点 p 之后就给 p 的 data 赋随机值，然后再给 p 的 next 赋值。画个图就很清晰了：
完整的可执行程序（修复插入操作的函数）：
#include "stdio.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 // 存储空间初始分配量
typedef int Status;// Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int ElemType;// ElemType类型根据实际情况而定，这里假设为int
//
typedef struct Node //为自定义的数据类型定义一个新名字Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; // 定义LinkList结构指针，等同于typedef (struct Node *) LinkList相关解释：
https://zhidao.baidu.com/question/480523838.html?qbl=relate_question_0&word=Node a; struct node a; struct node
typedef struct node { int data; struct node *next; }Node,*LinkList;
这是定义一个结构体，这个结构体有两个属性，一个是int类型的data。另一个是这个结构体本身类型的指针next。给这个结构定义了一个别名:Node，一个指针别名:LinkList。
Node a; 等价于 struct node a; 都是声明一个struct node结构体类型的结构体变量 a。
LinkList b; 等价于 struct node *b; 等价于 Node *b; 声明一个struct node结构体类型的指针变量 b。
//
//从这个结构定义中，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。
//假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data
//的值是一个数据元素，结点ai的指针域可以用 p->next来表示，p->next的值是一个指针。
//p->next指向谁呢？当然是指向第i+1个元素，即指向ai+1的指针。
// 初始化顺序线性表，实参要改变就要传地址，否则传值
Status InitList(LinkList *L) //参数*L传入的L其实就是链表的首地址，也就是头指针
{ //LinkList *L等同于struct Node **L，**L就是变量，*L就是指针，L就是指向指针的指针
*L=(LinkList)malloc(sizeof(Node)); // 产生头结点,并使L指向此头结点
//L是个指针，指向头结点，*L就是指头结点。
if(!(*L)) // 存储分配失败
{
return ERROR;
}
(*L)->next=NULL; // 指针域为空
//因为 *L是头结点，那么 (*L)->next就是首元结点，所以 (*L)->next=NULL;
//这么写就能让首元结点的指针域为空
return OK;
}
// 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; // p指向第一个结点
while(p)
{
i++;
p=p->next;
}
return i;
}// 初始条件：顺序线性表L已存在
// 操作结果：依次对L的每个数据元素输出
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
Status visit(ElemType c)
{
printf("-> %d ",c);
return OK;
}//实参要改变就要传地址，否则传值// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; // 声明一结点p
p = L->next; // 让p指向链表L的第一个结点
j = 1; // j为计数器
while (p && j < i) // p不为空或者计数器j还没有等于i时，循环继续
{
p = p->next; // 让p指向下一个结点
++j;
}
if ( !p || j>i )
return ERROR; // 第i个元素不存在
*e = p->data; // 取第i个元素的数据
return OK;
}// 初始条件：顺序线性表L已存在
// 操作结果：返回L中第1个与e满足关系的数据元素的位序。
// 若这样的数据元素不存在，则返回值为0
int LocateElem(LinkList L,ElemType e)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(p->data==e) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}///随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）///
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); // 初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; // 先建立一个带头结点的单链表
for (i=0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); // 生成新结点
p->data = rand() % 100+1; // 随机生成100以内的数字
p->next = (*L)->next;
(*L)->next = p; // 插入到表头
}
}///随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）///
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); // 初始化随机数种子
*L = (LinkList)malloc(sizeof(Node)); // L为整个线性表
r=*L; // r为指向尾部的结点
for (i=0; i < n; i++)
{
p = (Node *)malloc(sizeof(Node)); // 生成新结点
p->data = rand() % 100+1; // 随机生成100以内的数字
r->next=p; // 将表尾终端结点的指针指向新结点
r = p; // 将当前的新结点定义为表尾终端结点
}
r->next = NULL; // 表示当前链表结束
}// 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)，
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L; // 声明一个结点 p，指向头结点
j = 1;
while (p && j < i) // 寻找第i个结点
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; // 第i个元素不存在
s = (LinkList)malloc(sizeof(Node)); // 生成新结点(C语言标准函数)
s->data = e;
s->next = p->next; // 将p的后继结点赋值给s的后继
p->next = s; // 将s赋值给p的后继
return OK;
}// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i) // 遍历寻找第i个元素
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; // 第i个元素不存在
q = p->next;
p->next = q->next; // 将q的后继赋值给p的后继
*e = q->data; // 将q结点中的数据给e
free(q); // 让系统回收此结点，释放内存
return OK;
}
int main()
{
LinkList L; //L是结构体指针
Status i;
int j,k,pos,value;
char opp;
ElemType e;
i=InitList(&L); //参数*L传入的L其实就是链表的首地址，也就是头指针
printf("链表L初始化完毕，ListLength(L)=%d\n",ListLength(L));
printf("\n1.整表创建（头插法） \n2.整表创建（尾插法） \n3.遍历操作 \n4.插入操作 \n5.删除操作 \n6.获取结点数据 \n7.查找某个数是否在链表中 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
scanf("%c",&opp);
switch(opp){
case '1':
CreateListHead(&L,10);
printf("整体创建L的元素(头插法)：\n");
ListTraverse(L);
printf("\n");
break;
case '2':
CreateListTail(&L,10);
printf("整体创建L的元素(尾插法)：\n");
ListTraverse(L);
printf("\n");
break;
case '3':
ListTraverse(L);
printf("\n");
break;
case '4':
printf("要在第几个位置插入元素？");
scanf("%d",&pos);
printf("插入的元素值是多少？");
scanf("%d",&value);
ListInsert(&L,pos,value);
ListTraverse(L);
printf("\n");
break;
case '5':
printf("要删除第几个元素？");
scanf("%d",&pos);
ListDelete(&L,pos,&e);
printf("删除第%d个元素成功，现在链表为：\n", pos);
ListTraverse(L);
printf("\n");
break;
case '6':
printf("你需要获取第几个元素？");
scanf("%d",&pos);
GetElem(L,pos,&e);
printf("第%d个元素的值为：%d\n", pos, e);
printf("\n");
break;
case '7':
printf("输入你需要查找的数：");
scanf("%d",&pos);
k=LocateElem(L,pos);
if(k)
printf("第%d个元素的值为%d\n",k,pos);
else
printf("没有值为%d的元素\n",pos);
printf("\n");
break;
case '0':
exit(0);
}
}
}尾插法创建链表
我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。
//随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); //初始化随机数种子
*L = (LinkList)malloc(sizeof(Node)); //L为整个线性表
r=*L; //r为指向尾部的结点
for (i=0; i < n; i++)
{
p = (Node *)malloc(sizeof(Node)); // 生成新结点
p->data = rand() % 100+1; //随机生成100以内的数字
r->next=p; //将表尾终端结点的指针指向新结点
r = p; //将当前的新结点定义为表尾终端结点
}
r->next = NULL; //表示当前链表结束
}
与头插法区别下？ *L 是头结点，r这里的角色是尾结点，一开始他们是重合的。
对，然后我们需要在结点 r 的后面插入一个结点 p。这很简单，将 r 的 next 指向 p 结点即可。这时要注意，当完成 p 的插入之后，p 会成为新的 r。当完成循环之后，r->next = NULL; 就完成这个单链表。
r=p;是这个意思吧。就是本来r是在元素的结点，可现在它已经不是最后的结点了，现在最后的结点，所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。循环结束后，那么应该让这个链表的指针域置空，因此有了 r->next = NULL; 完整的程序如上。
------------------------------------------------------------------------------------------------------------------
附录
1、参考：第01话：线性表的概念与定义 -- 简明现代魔法非常好
2、参考：小甲鱼数据结构与算法12_线性表7（存于我的百度云盘）
3、结构体的typedef
typedef struct Student
{
int a;
}Stu;
于是在声明变量的时候就可：Stu stu1;
如果没有typedef就必须用struct Student stu1;来声明，这里的Stu实际上就是struct Student的别名。
另外这里也可以不写Student（于是也不能struct Student stu1;了）
typedef struct
{
int a;
}Stu;
------------------------------------------------------------------------------------------------------------------
