前言
上一篇博客我们详细的讲述了顺序表的实现，但以讲述的形式来记录数据结构这部分的笔记效率实在是有些低，所以接下来的部分我就单纯地列出知识点就完事了。嘻嘻嘻！~
单链表
单链表结点的结构体：
typedef struct Node
{
DataType data;
struct Node *next;
} SLNode;
其中，data域用来存放数据元素，next域用来存放指向下一结点的指针。
单链表还分为带头结点结构和不带头结点结构两种。我们把指向单链表的指针称作头指针，头指针所指的不存放数据元素的第一个结点称作头结点。我们一般构造带头结点的单链表（以下讲解的也是带头结点的单链表）。
单链表的操作实现
1.C语言的动态申请内存空间函数
要知道，单链表中的每一个结点，是在需要时才向系统申请的，这称作动态内存空间申请。动态申请的内存空间，当不再需要时，必须手动释放。C语言提供了动态申请内存空间的函数malloc()和动态释放函数内存空间的函数free()。这些函数包含在头文件malloc.h中。
void *malloc(unsigned size);
-> 向系统动态申请size个字节的内存单元空间，函数返回值为所申请内存空间的首地址。
void free(void *p);
-> p为内存空间首地址指针。
sizeof(<以定义的数据类型>)
-> 计算所需内存空间的大小。
2.单链表的操作实现
1.初始化ListInitiate(SLNode **head)
void ListInitiate(SLNode **head) //初始化
{
*head = (SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址
(*head)->next = NULL; //置结束标记NULL
}
2.求当前数据元素个数ListLength(SLNode *head)
int ListInitiate(SLNode *head)
{
SLNode *p = head; //p指向头结点
int size = 0; //size初始化为0
while(p->next!=NULL) //循环计数
{
p = p->next;
size ++;
}
return size;
}
3.插入ListInsert(SLNode *head, int i, DataType x)
int ListInsert(SLNode *head, int i, DataType x)
//在带头结点的单链表head的第i（0<=i<=size）个结点前
//插入一个存放数据元素x的结点。插入成功返回1，失败返回0。
{
SLNode *p, *q;
int j;
p = head;
j = -1;
while(p->next!=NULL && j<i-1)
//最终让p指向第i-1个结点
{
p = p->next;
j++;
}
if(j!=i-1)
{
printf("插入位置参数错误！\n");
return 0;
}
q = (SLNode *)malloc(sizeof(SLNode)); //生成新的结点
q->data = x; //新节点数据域赋值
q->next = p->next; //插入
p->next = q;
return 1;
}
4.删除ListDelete(SLNode head, int t, DataType x)
int ListDelete(SLNode *head, int i, DataType *x)
//删除带头结点单链表head的第i（0<=i<=size-1）个结点
//被删除结点的数据域值由x带回。删除成功返回1，失败返回0。
{
SLNode *p, *s;
int j;
p = head;
j = -1;
while(p->next!=NULL && p->next->next!=NULL && j<i-1)
//最终p指向第i-1个结点
{
p = p->next;
j++;
}
if(j!=i-1)
{
printf("删除位置参数错误！\n");
return 0;
}
s = p->next; //指针s指向第i个结点
*x = s->data; //赋值
p->next = p->next->next; //删除
free(s); //释放内存空间
return 1;
}
5.取数据元素ListGet(SLNode head, int i, DataType x)
int ListGet(SLNode *head, int i, DataType *x)
{
SLNode *p;
int j;
p = head;
j = -1;
while(p->next!=NULL && j<i)
{
p = p->next;
j++;
}
if(j!=i)
{
printf("取元素位置参数错误！\n");
return 0;
}
*x = p->data;
return 1;
}
循环单链表
链表的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。（与单链表的实现差别不大，不做讨论。）
双向链表
双向链表也有循环和非循环两种结构，这里讨论带头节点的双向循环链表。
双向循环链表结点的结构体定义如下：
typedef struct Node
{
DataType data; //数据域
struct Node *next; //指向后驱结点的指针
struct Node *prior; //指向前驱结点的指针
} DLNode;
双向循环链表的操作实现
1.初始化
void ListInitiate(DLNode **head)
{
*head = (DLNode *)malloc(sizeof(DLNode));
(*head)->prior = *head;
(*head)->next = *head;
}
2.插入数据元素
int ListTnsert(DLNode *head, int i, DataType x)
//在带头结点的双向循环链表head的第i（0<=i<=size）个结点前
//插入一个存放数据元素x的结点。成功返回1，失败返回0。
{
DLNode *p, *s;
int j;
p = head->next;
j = 0;
while(p->next!=head && j<i) //寻找第i个结点
{
p = p->next;
j++;
}
if(j!=i)
{
printf("插入位置参数出错！");
return 0;
}
s = (DLNode *)malloc(sizeof(DLNode));
s->data = x;
s->prior = p->prior; //插入步骤
p->prior->next = s;
s->next = p;
p->prior = s;
return 1;
}
3.删除数据元素
int ListDelete()
//删除带头结点双向循环链表head的第i（0<=i<=size-1）个结点
//被删除的结点的数据元素域值由x带回。成功返回1，失败返回0。
{
DLNode *p;
int j;
p = head->next;
j = 0;
while(p->next!=head && j<i)
{
p = p->next;
j++;
}
if(j!=i)
{
printf("删除位置参数错误！");
return 0;
}
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return 1;
}
4.求当前数据元素个数
int ListLength(DLNode *head)
{
DLNode *p = head;
int size = 0;
while(p->next != head)
{
p = p->next;
size ++;
}
return size;
}
5.撤销内存空间
void Destory(DLNode **head)
{
DLNode *p, *p1;
int i, n = ListLength(*head)
p = *head;
for(i = 0, i<=n, i++)
{
p1 = p;
p = p->next;
free(p1);
}
*head = NULL;
}