目录
结点：由数据元素域和一个或若干个指针域组成的一个结构体。
链表：链式存储结构的线性表。
一? 单链表的表示和实现
1.单链表的存储结构
typedef char DataType;
typedef struct Node
{ //单链表的储存结构
DataType data; //存放数据
struct Node* next; //存放指针
}SLNode;1.? 每个存储结点都包含两部分：数据域，指针域
2.? 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
1.1.??头指针、头结点与首元结点
?头指针是指向链表中第一个结点
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。
首元结点是指链表中存储线性表第一个数据元素a0的结点。
1.2.??带头结点单链表和不带头结点单链表的比较
? 1）? 带头结点的单链表的第一个数据元素插入时，其插入在头结点后。
? ?2）? 不带头结点的单链表的第一个数据元素插入时，其插入在头指针后。
? ?3）?不带头结点的单链表的其余数据元素插入时，其插入在前一节点后。
?
? ?4）??删除带头结点的单链表的第一个数据时，头结点指针指向第二个数据
? ?5）?删除不带头结点的单链表的第一个数据时，头指针指向第二个数据
?结论：插入操作时，有头结点链表方便
单链表一般构造成带头结点的单链表
2. 单链表的初始化
malloc(m)函数:向系统动态申请m字节长度的地址空间，并返回这段空间的首地址；
free(p)函数:释放指针p所指变量的存储空间，即彻底删除一个变量。
sizeof(x)运算符:计算变量x的长度（字节数）；
以上有库函数/算符都在<malloc.h> 中
void ListInitiate(SLNode** hear)
{ //单链表的初始化
*hear = (SLNode*)malloc(sizeof(SLNode));
(* hear)->next = NULL; //链尾标记NULL
}3.? 单链表的长度
int ListLength(SLNode* hear)
{ //单链表的长度
SLNode* p = hear; //p 指向头结点
int size;
for (size = 0; p->next != NULL; size++)
{
p = p->next;
}
return size;
}4.? 单链表的插入
实现步骤：
1.? 将插入处前一节点指针指向所插入节点的指针
? ?（即? 将所插入节点的指针指向插入处的节点，防止插入处节点丢失）；
2.? 将插入处前一节点指针指向所插入节点。
? ? ? ? ? x 节点先 生成再使用。
int ListInsert(SLNode* head, int i, DataType x)
{ //在顺序表的第i个位置之前插入数据值x
//插入成功返回1，插入失败返回0
SLNode* p, * q;
p = head;
int j = 0;
for (j; p->next != NULL && j < i - 1; j++)
{
p = p->next;
}
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;
}5.? 单链表的删除
实现步骤：
1.? 将要删除节点前一节点的指针指向删除节点的后一节点
? ?（即? 使得要没有指针指向删除节点）；
2.? 释放删除节点。
int ListDelete(SLNode* head, int i, DataType* x)
{ //删除顺序表L中位置i的数据元素值并存放到参数x中
//删除成功返回1，失败返回0
SLNode* p, * s;
p = head;
int j = -1;
for (j; p->next != NULL && j < i - 1; j++)
{
p = p->next;
}
if (j != i - 1)
{
printf("删除位置错误！\n");
return 0;
}
s = p->next;
*x = s->data;
p->next = s->next;
free(s);
return 1;
}
6.? 单链表的输出
int ListGet(SLNode* head, int i, DataType* x)
{ //取顺序表中第i个元素存于x中
//取出成功返回1，失败返回0
SLNode* p;
p = head;
int j = 0;
for (j; p->next != NULL && j < i; j++)
{
p = p->next;
}
if (j != i)
{
printf("参数i不合法！\n");
return 0;
}
*x = p->data;
return 1;
}7.? 单链表的撤销
void Destroy(SLNode **head)
{ //撤销单链表
SLNode* p, * q;
p = *head;
for (p; p != NULL; free(q))
{
q = p;
p = p->next;
}
*head = NULL;
}完整代码
#include<stdio.h>
#include<malloc.h>
typedef char DataType;
typedef struct Node
{ //单链表的储存结构
DataType data; //存放数据
struct Node* next; //存放指针
}SLNode;
void ListInitiate(SLNode** hear)
{ //单链表的初始化
*hear = (SLNode*)malloc(sizeof(SLNode));
(* hear)->next = NULL; //链尾标记NULL
}
int ListLength(SLNode* hear)
{ //单链表的长度
SLNode* p = hear; //p 指向头结点
int size;
for (size = 0; p->next != NULL; size++)
{
p = p->next;
}
return size;
}
int ListInsert(SLNode* head, int i, DataType x)
{ //在顺序表的第i个位置之前插入数据值x
//插入成功返回1，插入失败返回0
SLNode* p, * q;
p = head;
int j = 0;
for (j; p->next != NULL && j < i - 1; j++)
{
p = p->next;
}
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;
}
int ListDelete(SLNode* head, int i, DataType* x)
{ //删除顺序表L中位置i的数据元素值并存放到参数x中
//删除成功返回1，失败返回0
SLNode* p, * s;
p = head;
int j = -1;
for (j; p->next != NULL && j < i - 1; j++)
{
p = p->next;
}
if (j != i - 1)
{
printf("删除位置错误！\n");
return 0;
}
s = p->next;
*x = s->data;
p->next = s->next;
free(s);
return 1;
}
int ListGet(SLNode* head, int i, DataType* x)
{ //取顺序表中第i个元素存于x中
//取出成功返回1，失败返回0
SLNode* p;
p = head;
int j = 0;
for (j; p->next != NULL && j < i; j++)
{
p = p->next;
}
if (j != i)
{
printf("参数i不合法！\n");
return 0;
}
*x = p->data;
return 1;
}
void Destroy(SLNode **head)
{ //撤销单链表
SLNode* p, * q;
p = *head;
for (p; p != NULL; free(q))
{
q = p;
p = p->next;
}
*head = NULL;
}
void main(void)
{
SLNode* head;
DataType x;
ListInitiate(&head);
ListInsert(head, 1, 'a');
ListInsert(head, 2, 'b');
ListInsert(head, 3, 'c');
printf("%d\n", ListLength(head));
ListGet(head, 3, &x);
printf("%c\n", x);
ListDelete(head, 2, &x);
printf("%d\n", ListLength(head));
ListGet(head, 2, &x);
printf("%c\n", x);
Destroy(&head);
}
二? 循环单链表
在初始化函数中，将语句(*head)->next = NULL改为(*head)->next =head。
在其他函数中，循环判断条件
p->next！= NULL和p->next ->next！= NULL中的NULL改为头指针head。
void ListInitiate(SLNode** hear)
{ //单链表的初始化
*hear = (SLNode*)malloc(sizeof(SLNode));
(* hear)->next = hear; //链尾标记hear
}三? 双向链表
双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。
它有带头结点和不带头结点，循环和非循环结构。双向链表是解决查找前驱结点问题的有效途径。
1.? 双向链表表的存储结构、初始化
?初始化时，前驱指针和后继指针各自构成自己的循环单链表。
2.? 双向链表的插入、删除
