目录
单链表结构体
- 结构体后的*List是一个指向结构体的指针类型，我们通过它来定义该类型的指针。
- 如：List p ; 则这个p就是指向LinkedList结构体的一个指针，也就是单链表的头指针。（所以说头指针是必然存在的，但单链表不一定有头结点，注意区分头指针和头结点）
typedef struct LinkedList {
int data; //数据域
struct LinkedList *next; //指针域，指向后继结点，存放后继结点的地址
}*List; //List <==> List * ，这里的List是单链表的头指针
带头结点 和 不带头节点 的初始化 带头结点单链表的初始化。①头结点初始化时，其next域必须置为空 head->next = NULL;。②头结点的data数据域如果要用来记录链表长度，则需初始化为0 head->data = 0;
//申请一个头结点 或 初始化一张空表
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //创建头结点，并让头指针指向头结点 (带头结点单链表)
if (head == 0) { //结点空间申请失败，该判断语句可有可无
return NULL;
}
head->next = NULL; //head是头结点，h->next是头结点的地址，该地址是第一个结点的地址，地址为NULL，即为空表
//head->data不用操作，但若想用头结点数据域保存链表长度，可以设置为head->data = 0;
head->data = 0;
return head;
}
不带头结点单链表的初始化
List link_list_create(){
List p;
p = NULL;
return p;
}
求链表长度
单链表求长度有两种方式
① 用头结点的data数据域记录链表长度（只适用于带头结点的链表）。创建头结点时，头结点的data初始化为0。成功执行插入操作后，头结点数据域+1。成功执行删除操作后，头结点数据域-1。时间复杂度为O(1),（故链表带头结点，则推荐用这种方式）
head->data = 0; //创建头结点时，将头结点数据域初始化为0 head->data++; //每插入一个元素，头结点数据域+1 head->data--; //每删除一个元素，头结点数据域-1 head->data; //获取链表长度
② 遍历链表获取长度，时间复杂度为O(n)
//求长度
int link_list_length(List head) {
List p = head->next;
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}
空表判断 带头结点的空表判断head是头结点，h->next是头结点的地址，该地址是第一个结点的地址，地址为NULL，即为空表
boolean isEmpty(List p){
if(p->next == NULL){
return TRUE;
}
return FALSE;
}
或者 (使用头结点数据域记录链表长度时，可用该方法)
boolean isEmpty(List p){
if(p->data == 0){
return TRUE;
}
return FALSE;
}
不带头结点的空表判断 p == NULL; p表示的是第一个结点的地址，p = NULL 表示第一个结点的地址为空，也就是空表
boolean isEmpty(List p){
if(p == NULL){
return TRUE;
}
return FALSE;
}
头插法
在链表头部插入结点（即作为链表第一个元素），时间复杂度为O(1)
//头插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //结点插入成功，链表长度+1
return TRUE;
}
尾插法
在链表尾部插入结点（即作为链表最后一个元素），时间复杂度为O(n)。
新结点插入链表尾部时，新结点的next域必须置为空，即：newNode->next = NULL; 。因为单链表尾结点的next域必须为null，否则我们在调用尾结点的next指针p->next时，系统判断尾结点的next没有值，就会动态地给它分配一个未知地址（而不是帮你将next域置为空）。正常情况下，虽然并不会出现问题，但在遍历链表 或 按内容获取结点 或 第二次插入为节点时，程序就会陷入死循环，最终耗尽cpu性能。你可以将tail_insert()方法中的newNode->next = NULL;这行代码注释掉，然后调用我们后面讲到的show()方法进行测试，你就会看到show()方法会不停息的打印输出一个个未知地址，直至内存耗尽，系统奔溃
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
newNode->data = x;
//newNode->next是动态分配的，如果你不置为空，系统就会动态地给它分配一个未知地址。
newNode->next = NULL;
List p = head; //用p结点做记录
while (p->next != NULL) { //遍历链表，直至尾结点
p = p->next;
}
p->next = newNode; //让尾结点指针，指向新结点
head->data++; //新结点插入成功，链表长度+1
return TRUE;
}
指定位置插入 在第k个位置插入新结点。需要先遍历链表，找到第k-1个结点，然后再修改新结点指针和第k-1个结点的指针，即可实现在第k个位置插入新结点操作。
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i来记录结点位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新结点插入成功，链表长度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}
按位序查找
//按位序查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k个结点
i++;
p = p->next;
}
if (i == k) { //判断i是否等于要查找结点的位序
return p;
}else{
printf("查找位置非法！");
return NULL;
}
}
删除第1个结点
//删除第1个结点
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next; //让头结点next指针，指向头结点下一个结点的next指针所致地址
head->data--; //链表长度减1
return TRUE;
}
return FALSE;
}
删除第k个结点
//删除第k个结点
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("删除位置非法！\n");
return FALSE;
}
int i = 0; //用i记录结点位置
while (p->next != NULL && i < k - 1) { //找到待删结点的前一个结点
i++;
p = p->next;
}
if (i + 1 == k) { //判断i是不是k结点的前一个结点的位置
p->next = p->next->next;
head->data--; //链表长度减1
return TRUE;
} else {
printf("删除位置非法！\n");
return FALSE;
}
}
遍历链表，显示数据 前面讲到了，如果在新结点插入链表尾部时，如果新结点next指针没有置为NULL，则在show()遍历链表时，将链表的结点数据输出后，方法不会中断，而是继续输出一个个未知地址，直至内存空间耗尽。
//显示数据
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
全部代码
#include <stdio.h>
#include <stdlib.h> //malloc需要此头文件
typedef enum {FALSE, TRUE} boolean;
//结构体
typedef struct LinkedList {
int data;
struct LinkedList *next;
} *List; //List <==> List *
//申请一个头结点，并初始化
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //创建头结点，并让头指针指向头结点 (带头结点单链表)
if (head == 0) { //结点空间申请失败，该判断语句可有可无
return NULL;
}
head->next = NULL; //head表示的是头结点的地址，h->next就是头结点的下一个结点，即第一个结点的地址为空，也就是空表
//head->data不用操作，但若想用头结点数据域保存链表长度，可以设置为head->data = 0;
head->data = 0;
return head;
}
//头插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //结点插入成功，链表长度+1
return TRUE;
}
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
newNode->data = x;
//newNode->next是动态分配的，如果不置为空，系统就会默认分配一个未知地址
newNode->next = NULL;
List p = head; //用p结点做记录
while (p->next != NULL) { //遍历链表，直至尾结点
p = p->next;
}
p->next = newNode; //让尾结点指针，指向新结点
head->data++; //新结点插入成功，链表长度+1
return TRUE;
}
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i来记录结点位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申请一个结点，并将要插入的元素填入该结点的数据域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新结点插入成功，链表长度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}
//按序号查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k个结点
i++;
p = p->next;
}
if (i == k) {
return p;
} else {
printf("查找位置非法！");
return NULL;
}
}
//删除第1个结点
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next;
head->data--;
return TRUE;
}
return FALSE;
}
//删除第k个结点
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("删除位置非法！\n");
return FALSE;
}
int i = 0; //用i记录结点位置
while (p->next != NULL && i < k - 1) { //找到待删结点的前一个结点
i++;
p = p->next;
}
if (i + 1 == k) { //判断i是不是k结点的前一个结点的位置
p->next = p->next->next;
head->data--;
return TRUE;
} else {
printf("删除位置非法！\n");
return FALSE;
}
}
//显示数据
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
List head = create_head_node();
printf("当前单链表长度为：%d\n\n", head->data);
head_insert(head, 15);
head_insert(head, 25);
head_insert(head, 35);
printf("第1个结点元素为：%d\n", get(head, 1)->data);
printf("第2个结点元素为：%d\n", get(head, 2)->data);
printf("第3个结点元素为：%d\n", get(head, 3)->data);
printf("当前单链表长度为：%d\n\n", head->data);
tail_insert(head, 45);
tail_insert(head, 55);
printf("第1个结点元素为：%d\n", get(head, 1)->data);
printf("第2个结点元素为：%d\n", get(head, 2)->data);
printf("第3个结点元素为：%d\n", get(head, 3)->data);
printf("第4个结点元素为：%d\n", get(head, 4)->data);
printf("第5个结点元素为：%d\n", get(head, 5)->data);
printf("当前单链表长度为：%d\n\n", head->data);
insert(head, 6, 65);
insert(head, 2, 75);
printf("第1个结点元素为：%d\n", get(head, 1)->data);
printf("第2个结点元素为：%d\n", get(head, 2)->data);
printf("第3个结点元素为：%d\n", get(head, 3)->data);
printf("第4个结点元素为：%d\n", get(head, 4)->data);
printf("第5个结点元素为：%d\n", get(head, 5)->data);
printf("第4个结点元素为：%d\n", get(head, 6)->data);
printf("第5个结点元素为：%d\n", get(head, 7)->data);
printf("当前单链表长度为：%d\n\n", head->data);
show(head);
printf("\n\n");
del_first(head);
show(head);
printf("\n\n");
del(head, 4);
show(head);
return 0;
}
