单链表：n个节点离散分配 彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。
首节点：第一个有效节点 尾节点：最后一个有效节点
头节点：头结点的数据类型和首节点的类型一样没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作。
头指针：（指向头节点的指针变量） 尾指针：指向尾节点的指针
确定一个链表需要几个参数：
只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。 链表的优缺点：
优点：空间没有限制
插入删除元素很快
缺点：存取速度很慢。
1.头文件，线性表的结点类型创建，还有main函数，及其对线性表进行操作的相关函数声明
# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>
# include <time.h>
typedef int ElemType;
typedef struct
{
ElemType data;
struct Node *next;
}Node;
typedef Node * LinkList;
bool visit(ElemType c);
bool InitList(LinkList *L); //初始化线性顺序表
bool ListEmpty(LinkList L); //若L为空表，则返回true，否则返回false
bool ClearList(LinkList *L); //清空线性链表
int ListLength(LinkList L); //求链表长度
bool GetElem(LinkList L,int i,ElemType *e); //找到第i个节点，并将其数据域保存到*e中
int LocateElem(LinkList L,ElemType e); //找到数据域为e的这个节点，返回第一次出现的那个节点是第几个节点，否则返回0
bool ListInsert(LinkList *L,int i,ElemType e); //在第i个节点前插入一个节点，该节点的值为e
bool ListDelete(LinkList *L,int i,ElemType *e); //删除单链表第i个节点，并将其保存到*e中
bool ListTraverse(LinkList L); //输出单链表
void CreateListHead(LinkList *L, int n); //头差法创建单链表
void CreateListTail(LinkList *L, int n); //尾插法创建单链表
int main()
{
LinkList L;
ElemType e;
bool i;
int j,k;
i=InitList(&L);
printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
i=ClearList(&L);
printf("清空L后：ListLength(L)=%d\n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
GetElem(L,5,&e);
printf("第5个元素的值为：%d\n",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%d\n",k,j);
else
printf("没有值为%d的元素\n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==false)
printf("删除第%d个数据失败\n",j);
else
printf("删除第%d个的元素值为：%d\n",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%d\n",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
i=ClearList(&L);
printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));
CreateListHead(&L,20);
printf("整体创建L的元素(头插法)：");
ListTraverse(L);
i=ClearList(&L);
printf("\n删除L后：ListLength(L)=%d\n",ListLength(L));
CreateListTail(&L,20);
printf("整体创建L的元素(尾插法)：");
ListTraverse(L);
return 0;
}
输出一个基本类型的元素
//输出一个基本类型的元素
bool visit(ElemType c)
{
printf("%d", c);
return true;
}
初始化链表
//初始化链表
bool InitList(LinkList *L)
{
(*L) = (LinkList)malloc(sizeof(Node));
if ( !(*L) )
{
printf("动态内存分配失败！\n");
return false;
}
(*L)->next = NULL;
return true;
}
判断链表是否为空
//判断链表是否为空
bool ListEmpty(LinkList L)
{
if (L->next == NULL)
return true;
return false;
}
清空链表
//清空链表
bool ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
return true;
}
求链表长度
//求链表长度
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
找到第i个节点，并将其数据域保存到*e中
//找到第i个节点，并将其数据域保存到*e中
bool GetElem(LinkList L,int i,ElemType *e)
{
LinkList p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (p == NULL || j > i)
{
return false;
}
(*e) = p->data;
return true;
}
找到数据域为e的这个节点，返回第一次出现的那个节点是第几个节点，否则返回0
//找到数据域为e的这个节点，返回第一次出现的那个节点是第几个节点，否则返回0
int LocateElem(LinkList L,ElemType e)
{
int i = 1;
LinkList p = L->next;
while (p != NULL)
{
if (p->data == e)
return i;
i++;
p = p->next;
}
return 0;
}
在第i个节点前插入一个节点，该节点的值为e
//在第i个节点前插入一个节点，该节点的值为e
bool ListInsert(LinkList *L,int i,ElemType e)
{
int j = 1;
LinkList p = *L;
while (p && j < i)
{
p = p->next;
i++;
}
if (p == NULL || j > i)
{
return false;
}
LinkList q = (LinkList)malloc(sizeof(Node));
q->next = p->next;
p->next = q;
q->data = e;
return true;
}
删除单链表第i个节点，并将其保存到*e中
//删除单链表第i个节点，并将其保存到*e中
bool ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList p = *L, q;
int j = 1;
while (p->next != NULL && j < i)
{
p = p->next;
j++;
}
if (p->next == NULL || j > i)
return false;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return true;
}
输出单链表
//输出单链表
bool ListTraverse(LinkList L)
{
LinkList p = L->next;
while (p != NULL)
{
visit(p->data);
p = p->next;
}
printf("\n");
return true;
}
头插法创建单链表
//头插法创建单链表
void CreateListHead(LinkList *L, int n)
{
srand(time(NULL));
LinkList p, q;
int i = 0;
*L = (LinkList)malloc(sizeof(Node));
p = (*L);
p->next = NULL;
for (i = 0; i < n; ++i)
{
q = (LinkList)malloc(sizeof(Node));
q->data = rand()%100 + 1;
q->next = p->next;
p->next = q;
}
}
尾插法创建单链表
//尾插法创建单链表
void CreateListTail(LinkList *L, int n)
{
srand(time(NULL));
LinkList p, q;
int i = 0;
(*L) = (LinkList)malloc(sizeof(Node));
p = *L;
for (; i < n; ++i)
{
q = (LinkList)malloc(sizeof(Node));
if (q == NULL)
{
printf("动态内存分配失败！\n");
exit(-1);
}
q->data = rand()%100+1;
p->next = q;
p = q;
}
}