前言

谭浩强老师说过：“指针是c语言的灵魂”，今天说到的链表就是由C语言的灵魂所筑，学会了链表之后可以使用链表轻松实现树、图等数据结构，可以轻松化解考研数据结构大题！在说今天的内容之前先看一下往年出现的有关链表的大题。

一、链表

链表通常适用于一下几种情况

• 在线性表中插入和删除操作大量元素或者很频繁
• 线性表的大小不好确定

1.基本介绍

下面图片是链表在逻辑结构与物理结构上的存储方式（灰色为实际存储结构，蓝色球球为逻辑结构）

记住最主要的一点：链表的每一个节点都由指针域与数据域组成，其中指针域负责记录下一个节点的地址，数据域负责记录本节点数据。一个指针域的节点可以串成单链表，两个指针域的节点可以串成双向、循环链表、二叉树等数据结构。做出改变的仅仅是指针域的关系！

老师说未来四月份会开数据结构的课，到时候应该会详细介绍，目前只需了解即可。
单链表中的一些概念如下：

2.增删改查原理与实战

在链表中插入元素
插入元素的话可以分为头插法、尾插法、中间插入法，下面图片是实现原理，代码分别是头插法、尾插法、中间插法。

//头插法
void head_insert(myList* head,ElemType e){myList *p= (myList*)malloc(sizeof (myList));p->data=e;p->next=head->next;head->next=p;// 如果写成以下样子，将不会有效果// head->next=p->next;
}
//尾插法
void tail_insert(myList* tail,ElemType e){myList *p;p=tail;while (p->next!=NULL){p=p->next;}p->next=(myList*) malloc(sizeof (myList));p->next->data=e;p->next->next=NULL;
}
//随机插入
bool random_insert(myList* head,int i,ElemType e){myList *p=head;int j=0;for(;p!=NULL,j<i-1;j++){p=p->next;}if(p!=NULL){myList *q=(myList*)malloc(sizeof (myList));q->data=e;q->next=p->next;p->next=q;return true;}else{return false;}
}

删除链表中的节点
删除链表中的节点，重中之重是合理的改变节点的指针关系。

代码：

//删除相应元素
bool delete_e(myList* head,ElemType e){for (myList* p=head;p->next!=NULL;p=p->next){if(p->next->data==e){myList *q =p->next;p->next=p->next->next;free(q);}}return false;
}

查找链表中的节点

查找节点一般可以分为：

• 按序号查找
  
• 按值查找
  

按值查找与按序号查找我分别实现了一遍，按值查找只判断找到没找到，按序号查找是将找到的信息返回出来，没有匹配的就返回NULL。

//按位置查找
myList* index_search(myList *head,int i){if(i<=0){return NULL;}myList *p=head;int j=0;// 循环终止条件如果有多个的话需要用逻辑表达式连接// 不可以使用逗号连接，用逗号连接遵循逗号表达式使用规则for(;p->next!=NULL&&j<i-1;j++){p=p->next;}return p->next;
}
//按值查找
bool element_search(myList *head,ElemType e){for (myList* p=head;p->next!=NULL;p=p->next){if(p->next->data==e){return true;}}return false;
}

总体来说还是按值查找用的多一些！

销毁链表
这也是常用的一个功能，比较简单就不细说了！直接上代码不懂的评论区留言吧。

//销毁链表
void destroy_myList(myList* head){myList *p=head->next;myList *q=NULL;while (p!=NULL){q=p;p=p->next;free(q);}head->next=NULL;
}

下面是遍历链表的两个函数

//遍历链表
void print_list(myList *head){if(head->next==NULL){printf("null!!!");}for (myList *p=head;p->next!=NULL;p=p->next){printf("%2c",p->next->data);}printf("\\n");
}
void print(myList *p){if(p!=NULL){printf("%2c\\n",p->data);}else{printf("null\\n");}
}

总结与源码

链表的优缺点

关于链表调试，由于链表在内存中并不是连续存在的，因此编译器的虚拟内存视图在调试的时候是排不上用场的，大家调试的话可以使用以下方法；通过单步调试，直接在变量窗口，把头指针L，依次点开，观察每一个结点是否符合自己的预期。同时大家在练习时，不要输入过多的数据，数据数量小于等于上课的即可。

源代码
这个代码实现了对链表的增删查（改与查重的话比较简单大家可以下去添上），每一个函数功能都在函数的正上方，感兴趣的同学可以自己研究研究，有不懂的地方欢迎评论区留言！

//
// Created by Zhu Shichong on 2023/1/9.
//
#include <stdio.h>
#include<stdlib.h>
#define bool int
#define true 1
#define false 0
typedef char ElemType;
//数组类型
struct myList{ElemType data;struct myList* next;
};
typedef struct myList myList;
//头插法
void head_insert(myList* head,ElemType e){myList *p= (myList*)malloc(sizeof (myList));p->data=e;p->next=head->next;head->next=p;// 如果写成以下样子，将不会有效果// head->next=p->next;
}
//尾插法
void tail_insert(myList* tail,ElemType e){myList *p;p=tail;while (p->next!=NULL){p=p->next;}p->next=(myList*) malloc(sizeof (myList));p->next->data=e;p->next->next=NULL;
}
//随机插入
bool random_insert(myList* head,int i,ElemType e){myList *p=head;int j=0;for(;p!=NULL,j<i-1;j++){p=p->next;}if(p!=NULL){myList *q=(myList*)malloc(sizeof (myList));q->data=e;q->next=p->next;p->next=q;return true;}else{return false;}
}
//按位置查找
myList* index_search(myList *head,int i){if(i<=0){return NULL;}myList *p=head;int j=0;// 循环终止条件如果有多个的话需要用逻辑表达式连接// 不可以使用逗号连接，用逗号连接遵循逗号表达式使用规则for(;p->next!=NULL&&j<i-1;j++){p=p->next;}return p->next;
}
//按值查找
bool element_search(myList *head,ElemType e){for (myList* p=head;p->next!=NULL;p=p->next){if(p->next->data==e){return true;}}return false;
}//删除相应元素
bool delete_e(myList* head,ElemType e){for (myList* p=head;p->next!=NULL;p=p->next){if(p->next->data==e){myList *q =p->next;p->next=p->next->next;free(q);}}return false;
}
//销毁链表
void destroy_myList(myList* head){myList *p=head->next;myList *q=NULL;while (p!=NULL){q=p;p=p->next;free(q);}head->next=NULL;
}
//遍历链表
void print_list(myList *head){if(head->next==NULL){printf("null!!!");}for (myList *p=head;p->next!=NULL;p=p->next){printf("%2c",p->next->data);}printf("\\n");
}
void print(myList *p){if(p!=NULL){printf("%2c\\n",p->data);}else{printf("null\\n");}
}
int main() {// 创建一个头结点（头结点一般不用于存储信息）myList *head=(myList*)malloc(sizeof (myList));head->next=NULL;printf("tail insert some data!\\n");tail_insert(head,'h');tail_insert(head,'o');tail_insert(head,'w');tail_insert(head,'a');tail_insert(head,'r');tail_insert(head,'e');tail_insert(head,'y');tail_insert(head,'o');tail_insert(head,'u');print_list(head);printf("after head_insert:");head_insert(head,'q');head_insert(head,'q');print_list(head);printf("after random_insert:");random_insert(head,3,'t');print_list(head);delete_e(head,'t');printf("after delete:");print_list(head);printf("search:%c \\nsearch_reasult:%d\\n", 'q',element_search(head,'q'));myList *q= index_search(head,10);print(q);q= index_search(head,1);print(q);q= index_search(head,100);print(q);q= index_search(head,-100);print(q);printf("list destroyed!!\\n");destroy_myList(head);print_list(head);return 0;
}

警示自己：循环里面的循环变量变动可以使用,隔开，但是循环终止条件必须使用逻辑运算符隔开！！！