（一）单链表
与线性表支持随机访问的特点相比，单链表的特点是适合插入与删除。
结构体定义
typedef int ElementType; // 数据元素类型定义
typedef struct LNode // 单链表结构体定义
{
ElementType data; // 数据域
struct LNode *next; // 存储下一个结点的地址
} LNode, *LinkedList; // Lnode表示结点；LinkedList = LNode*表示链表
（二）单链表的主要操作
单链表分为带头结点和不带头结点，这里阐述使用带头结点的单链表。
1.单链表的初始化
初始化一个单链表我们首先需要创建一个新结点。
在C语言中，malloc函数可以给我们分配指定长度的内存空间。
LinkedList init_link_list()
{
LinkedList L = (LinkedList)malloc(sizeof(LNode)); // 创建头结点
L->next = NULL; // 将头结点的指针域置为NULL
return L; // 返回
}
其他内容请见下方完整代码...
完整代码如下：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType; // 数据元素类型定义
typedef struct LNode // 单链表结构体定义
{
ElementType data; // 数据域
struct LNode *next; // 存储下一个结点的地址
} LNode, *LinkedList; // Lnode表示结点；LinkedList = LNode*表示链表
// ----------------------------------------------------------------
LinkedList init_link_list(); // 初始化含头结点的单链表
void iterate_link_list(LNode L); // 遍历单链表
void head_insert(LinkedList L, int n); // 头插法建立单链表（逆序插入）
void rear_insert(LinkedList L, int n); // 尾插法建立单链表（顺序插入）
void insert_element(LinkedList L, int i, ElementType e); // 在第i个位置插入元素e
void delete_element(LinkedList L, int i); // 删除第i个位置的元素e
int get_length(LNode L); // 计算单链表的长度
ElementType get_element(LNode L, int i); // 查找i位置的元素
int locate_element(LNode L, int value); // 查找某个元素的位置
void selection();
// ----------------------------------------------------------------
// ----------------------------------------------------------------
LinkedList init_link_list()
{
LinkedList L = (LinkedList)malloc(sizeof(LNode)); // 创建头结点
L->next = NULL; // 将头结点的指针域置为NULL
return L; // 返回
}
void iterate_link_list(LNode L)
{
LinkedList p = L.next; // p结点指向第一个元素
while (p) // 当 p->next != NULL时，进行遍历访问
{
printf("%d ", p->data); // 打印元素值
p = p->next; // p指针向后移动
}
printf("\n");
free(p); // 释放p结点
}
void head_insert(LinkedList L, int n)
{
for (int i = n; i > 0; i--)
{
LinkedList p = (LinkedList)malloc(sizeof(LNode)); // 生成新结点
scanf(" %d", &p->data); // 输入元素值
p->next = L->next; //
L->next = p; // 插入到表头
}
}
void rear_insert(LinkedList L, int n)
{
LinkedList r = L; // r结点指向头结点
for (int i = n; i > 0; i--) // 循环插入
{
LinkedList p = (LinkedList)malloc(sizeof(LNode)); // 生成新结点
scanf(" %d", &p->data); // 输入元素值
p->next = NULL; // 新结点的next指针域置为NULL
r->next = p; // 插入到表尾
r = r->next; // 表尾元素后移
}
}
void insert_element(LinkedList L, int i, ElementType e)
{
int j = 0; // 当前是第0个元素，即头结点
LinkedList p = L; // p结点指向头结点
while (p)
{
if (j == i - 1) // 找到了i-1位置
{
LinkedList temp = (LinkedList)malloc(sizeof(LNode)); // 创建新结点
temp->data = e; // 将元素e赋值给temp的数据域
temp->next = p->next; // 新插入的结点temp指向p结点的下一个结点
p->next = temp; // 将p的下一个结点指向新插入的结点temp
return;
}
j++; // j++
p = p->next; // p指针向后移动
}
}
void delete_element(LinkedList L, int i)
{
int j = 0; // 当前是第0个元素
LinkedList p = L; // p结点指向头结点
while (p && p->next) // 新加入了p->next!=NULL的判断？ 为了防止删除最后一个元素时(p->next==NULL)进入循环
{
if (j == i - 1) // 找到了i-1位置
{
// 将当前结点后的元素删除
LinkedList r = p->next; // 记录p结点的下一个结点
p->next = r->next; // p->next = p->next->next
free(r); // 释放r结点
return;
}
j++; // j++
p = p->next; // p指针向后移动
}
}
int get_length(LNode L)
{
LinkedList p = L.next; // p指向第一个元素
int length = 0;
while (p) // 当p->next != NULL时
{
length++; // 长度加1
p = p->next; // p指针向后移动
}
return length; // 返回链表长度
}
ElementType get_element(LNode L, int i)
{
int j = 1; // 当前是第几个元素
LinkedList p = L.next; // p结点指向存放第一个元素的结点
while (p) // 当p->next != NULL时
{
if (j == i) // 当前位置j是否等于i位置
return p->data; // 返回元素值
j++; // j++
p = p->next; // p指针向后移动
}
exit(0); // 退出
}
int locate_element(LNode L, int value)
{
int j = 1; // 当前是第几个元素
LinkedList p = L.next; // p结点指向存放第一个元素的结点
while (p) // 当p->next != NULL时
{
if (p->data == value) // 找到了
return j; // 返回
j++; // j++
p = p->next; // p指针向后移动
}
return -1; // 未找到
}
// ----------------------------------------------------------------
void selection()
{
int option = 0; // 当前选项
LinkedList L = NULL; // 初始化
int n = 0; // 插入元素个数
int insertPosition = 0; // 插入元素的位置
int insertElement = 0; // 插入的元素
int deletePosition = 0; // 删除的元素位置
int locatePosition = 0; // 查找的第i个位置
int findElement = 0; // 查找的元素
while (1)
{
printf("========================================================================\n");
printf("\t\t 1. Init Single LinkedList. \t\t\n"); // 初始化带头结点的单链表
printf("\t\t 2. Insert Element(head insert). \t\t\n"); // 头插法建立单链表
printf("\t\t 3. Insert Element(rear insert). \t\t\n"); // 尾插法建立单链表
printf("\t\t 4. Delete element at position i. \t\t\n"); // 删除第i个位置的元素e
printf("\t\t 5. Insert an Element at position i. \t\t\n"); // 在第i个位置插入元素e
printf("\t\t 6. Find the element at position i. \t\t\n"); // 查找i位置的元素
printf("\t\t 7. Find the location of a specified element. \t\t\n"); // 查找某个指定元素的位置
printf("\t\t 8. Current length of the Single LinkedList. \t\t\n"); // 获取单链表长度
printf("\t\t 9. Print Element. \t\t\n"); // 打印元素
printf("\t\t 10. Exit. \t\t\n"); // 退出
printf("========================================================================\n");
printf("Input one number in(1-9): ");
scanf("%d", &option);
switch (option)
{
case 1:
L = init_link_list();
printf("~_~ LinkList successfully initialized.\n");
break;
case 2:
printf("Please enter the number of inserted elements(eg: 10): ");
scanf("%d", &n);
head_insert(L, n);
printf("~_~ Head Insert LinkList successfully.\n");
break;
case 3:
printf("Please enter the number of inserted elements(eg: 10): ");
scanf("%d", &n);
rear_insert(L, n);
printf("~_~ Rear Insert LinkList successfully.\n");
break;
case 4:
printf("Input delete position i (eg: 2): ");
scanf("%d", &deletePosition);
delete_element(L, deletePosition);
break;
case 5:
printf("Input insert position i (eg: 2 66): ");
scanf("%d %d", &insertPosition, &insertElement);
insert_element(L, insertPosition, insertElement);
break;
case 6:
printf("Input insert position i and element e (eg: 2): ");
scanf("%d", &locatePosition);
printf("~_~ The position [%d] element is: %d \n", locatePosition, get_element(*L, locatePosition));
break;
case 7:
printf("Input the element e (eg: 33): ");
scanf("%d", &findElement);
printf("~_~ The element [%d] position is: %d \n", findElement, locate_element(*L, findElement));
break;
case 8:
printf("~_~ Current single list length: %d\n", get_length(*L));
break;
case 9:
printf("~_~ Start Iterate LinkList.\n");
iterate_link_list(*L);
printf("~_~ Iterate LinkList successfully.\n");
break;
case 10:
printf("~_~ Exit successfully.\n");
return;
default:
printf("~_~ Please enter the correct serial number!\n ");
break;
}
}
}
int main()
{
// LinkedList L = init_link_list();
// // head_insert(L, 9); // 头插法
// rear_insert(L, 9); // 尾插法
// printf("current single list length: %d\n", get_length(*L));
// iterate_link_list(*L);
// int i = 0, element = 0;
// printf("input insert position i and element e.(eg: 2 99):");
// scanf("%d %d", &i, &element);
// insert_element(L, i, element);
// printf("current single list length: %d\n", get_length(*L));
// iterate_link_list(*L);
// delete_element(L, 3); // 删除第2个位置的元素
// printf("current single list length: %d\n", get_length(*L));
// iterate_link_list(*L);
selection();
return 0;
}