为什么要使用链表
在未学习链表时，我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快，但是它的弊端也很明显：
- 使用前需声明数组的长度，一旦声明长度就不能更改
- 插入和删除操作需要移动大量的数组元素，效率慢
- 只能存储一种类型的数据.
而链表则可以实现以上这些数组所不具备的功能，此时引入了结构体来实现创建链表的操作。
链表的特点：
- n个节点离散分配
- 每一个节点之间通过指针相连
- 每一个节点有一个前驱节点和一个后继节点
- 首节点没有前驱节点，尾节点没有后继节点
首先先定义一个简单的结构体
struct link{
int data; //定义数据域
struct link *next; //定义指针域，存储直接后继的节点信息
};数据域的内容可以自己指定，指针域用来存放下一个节点的地址。
创建链表前须知
首节点：存放第一个有效数据的节点
头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空
头指针：指向头节点的指针
尾节点：存放最后一个有效数据的节点
尾指针：指向尾节点的指针
建立一个单向链表
方法：定义方法向链表中添加节点来建立一个单向链表
思路：首先定义一个结构体指针变量p，使用malloc函数为新建节点申请内存空间，让p指向这个节点(指向它刚申请的内存空间），再将其添加到链表中。此时需考虑两种情况：
1.若单链表为空表，则将新建节点置为头节点
//若此时只在链表中插入头节点
struct link *p = head;
p = (struct link *)malloc(sizeof(struct link)); //让p指向新建节点创建的内存空间
if(p == null){ //新建节点申请内存失败
exit(0);
}
//此时head也指向头节点的地址
p->next = null; //因为没有后续节点，所以新建节点指针域置空2.链表非空，则将新建节点添加到表尾
//此时已存在头节点,再插入一个节点（首节点）
struct link *p = null,*pr = head;
p = (struct link *)malloc(sizeof(struct link));
if(p == null){
exit(0);
}
if(head == null){
head = p;
}else{
while(pr->next != null){ //当头节点的指针域不为null
pr = pr->next; //pr指向下一个节点的地址
}
pr->next = p; //使头节点的指针域存储下一个节点的地址
}完整操作
#include
#include
struct link *appendnode(struct link *head);
void displaynode(struct link *head);
void deletememory(struct link *head);
//定义结构体
struct link{
int data; //定义数据域
struct link *next; //定义指针域
};
int main(){
int i =0; //定义i，记录创建的节点数
char c;
struct link *head = null; //创建头指针，初始化为null
printf("do you wang to append a new node(y or n)?");
scanf(" %c",&c);
while(c == 'y' || c == 'y'){ //如果确定继续添加结点
head = appendnode(head); //通过函数获得链表的地址，appendnode函数返回的是链表的头指针
//可以根据头指针指向的地址来获取链表中保存的数据
displaynode(head); //根据头指针打印链表
printf("do you want to append a new node(y or n)?");
scanf(" %c",&c);
i ;
}
printf("%d new nodes hava been appended!\n",i);
deletememory(head); //释放占用的内存
}
struct link *appendnode(struct link *head){ //声明创建节点函数
struct link *p = null,*pr = head; //创建p指针，初始化为null；创建pr指针，通过pr指针来给指针域赋值
int data ;
p = (struct link *)malloc(sizeof(struct link)) ; //为指针p申请内存空间，必须操作，因为p是新创建的节点
if(p == null){ //如果申请内存失败，则退出程序
printf("no enough momery to allocate!\n");
exit(0);
}
if(head == null){ //如果头指针为null,说明现在链表是空表
head = p; //使head指针指向p的地址(p已经通过malloc申请了内存，所以有地址）
}else{ //此时链表已经有头节点 ，再一次执行了appendnode函数
//注：假如这是第二次添加节点
//因为第一次添加头节点时，pr = head，和头指针一样指向头节点的地址
while(pr->next!= null){ //当pr指向的地址，即此时的p的指针域不为null(即p不是尾节点)
pr = pr->next; //使pr指向头节点的指针域
}
pr->next = p; //使pr的指针域指向新键节点的地址，此时的next指针域是头节点的指针域
}
printf("input node data:");
scanf("%d",&data);
p->data = data; //给p的数据域赋值
p->next = null; //新添加的节点位于表尾，所以它的指针域为null
return head; //返回head的地址
}
void displaynode(struct link *head){ //输出函数，打印链表
struct link *p = head; // 定义p指针使其指向头节点
int j = 1; //定义j记录这是第几个数值
while(p != null){ //因为p = p->next,所以直到尾节点打印结束
printf("]d\n",j,p->data);
p = p->next; //因为节点已经创建成功，所以p的指向由头节点指向下一个节点(每一个节点的指针域都指向了下一个节点)
j ;
}
}
void deletememory(struct link *head){ //释放资源函数
struct link *p = head,*pr = null; //定义p指针指向头节点
while(p != null){ //当p的指针域不为null
pr = p; //将每一个节点的地址赋值给pr指针
p = p->next; //使p指向下一个节点
free(pr); //释放此时pr指向节点的内存
}
} 第二种创建链表方式-优化
#include
#include
struct stu *create(int n);
void print(struct stu *head);
struct stu{
int id;
char name[50];
struct stu *next;
};
int main(){
int n;
struct stu *head = null; //创建头指针
printf("请输入你想要创建的节点个数：\n");
scanf("%d",&n);
head = create(n);
print(head);
}
struct stu *create(int n){
struct stu *head,*node,*end; //定义头节点，普通节点，尾节点
head = (struct stu *)malloc(sizeof(struct stu)); //给头节点申请内存
end = head; //若是空表，则头尾地址一致
for(int i=0;iid,node->name); //给数据域赋值
end->next = node; //让上一个节点的数据域指向当前节点
end = node; //end指向当前节点，最终end指向尾节点
}
end->next = null; //给end的指针域置空
return head; //返回头节点的地址
}
void print(struct stu *head){
struct stu *p = head;
int j =1;
p = p->next; //不打印头节点的数据域中的值
while(p != null){
printf("%d\t%d\t%s\n",j,p->id,p->name);
p = p->next;
j ;
}
} 前插法创建链表 --逆序输出
struct link *create(int n){
struct link *headnode ,*node;
headnode = (struct link *)malloc(sizeof(struct link)); //为头节点申请内存
headnode ->next = null; //让头节点的指针域置空
for(int i=0;idata); //新建节点数据域传值
node->next = headnode->next; //新建节点的数据域指向头节点 == 创建尾节点
headnode->next = node; //将新建节点数据域传给头节点
}
return headnode;
}
删除节点
void deletenode(struct stu *head,int n){ //删除n处的节点
struct stu *p = head,*pr = head;
int i =0;
while(inext; //p指向下一节点
i ;
}
if(p!=null){ //当p不为空时，即p不能指向尾节点之后的节点
pr->next = p->next;
free(p);
} else{
printf("节点不存在！\n");
}
} 我在这着重解释一下p->next = null和p!=null的区别，因为我刚开始也经常弄错！！
- while(p->next ！= null) 循环结束时，此时p的位置是尾节点的位置，但如果用于输出函数的判断条件，则尾节点的数据不会输出。
- while(p!=null) 循环结束时， 此时p指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。
插入节点
void insertnode(struct stu *head,int n){ //插入节点
struct stu *p = head,*pr;
pr = (struct stu*)malloc(sizeof(struct stu)); //让pr指向新建节点申请的内存
printf("input data:\n");
scanf("%d %s",&pr->id,pr->name);
int i = 0;
//当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空
while(inext;
i ;
}
if(p!=null){ //如果p没越界
pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址
p->next = pr; //使插入节点指向新建节点
}else{
printf("节点不存在！\n");
}
} 修改节点
void change(struct stu *head,int n){
struct stu *p = head;
int i = 0;
while(inext;
i ;
}
if(p != null){
printf("请输入修改之后的值:\n");
scanf("%d %s",&p->id,p->name);
}else{
printf("节点不存在！\n");
} 链表的逆序
思路：假如此时链表有两个有效节点，头节点为0号，中间的节点为1号，尾节点为2号
1.定义三个指针pf指向链表的头节点（0号），tmp，pb初始化为null
2.让pb指向pf的下一个节点（1号），并将此时头节点的指针域置空（变为尾节点）
3.第一次while循环，让tmp指向pb（1号），然后让pb指向下一个节点，再让tmp让1号节点的指针域（tmp->next = pf)指向pf(上一个节点）（0号），再将pf指向tmp（1号）(pf = tmp)
4.第二次while循环，让tmp指向pb（2号），然后让pb指向下一个节点，此时pb==null，所以这是最后一次循环，再让tmp让2号节点的指针域（tmp->next = pf)指向pf（1号），再将pf指向tmp（2号）
5.此时链表逆序完成，让头指针指向首节点（2号），返回头指针即可
逆序后
stu *link_reversed_order(stu *head)
{
stu *pf = null, *pb = null, *tmp = null;
pf = head; //将头节点的地址赋值给pf
if(head == null) { //如果链表为空
printf("链表为空，不需要逆序！\n");
return head;
} else if(head->next == null) { //如果只有一个节点
printf("链表只有一个节点，不需要逆序！\n");
return head;
} else {
pb = pf->next; //pb指向pf的下一个节点
head->next = null; //头节点的指针域置空(变为尾节点)
while(pb != null) //当pb不为空时
{
tmp = pb; //将pb的地址赋值给temp
pb = pb->next; //pb指向下一个节点
tmp->next = pf; //pb的上一个节点的指针域指向pf
pf = tmp; //让pf指向tmp
}
head = pf;
return head;
}
}*/所有操作
#include
#include
struct stu *create(int n);
void print(struct stu *head);
void deletenode(struct stu *head,int n);
void insertnode(struct stu *head,int n);
void change(struct stu *head,int n);
struct stu{
int id;
char name[50];
struct stu *next;
};
int main(){
int n,j,in,cn;
char c;
struct stu *head = null; //创建头指针
printf("请输入你想要创建的节点个数：\n");
scanf("%d",&n);
head = create(n);
print(head);
while(true){
printf("请选择你想要执行的操作：\n");
printf("1.插入节点\n2.删除节点\n3.修改节点\n4.退出程序\n");
scanf(" %c",&c);
if(c =='1'){
printf("你想要在哪插入节点：\n");
scanf("%d",&in);
insertnode(head,in);
print(head);
}else if(c == '2'){
printf("你想要删除哪个节点的数据：\n");
scanf("%d",&j);
deletenode(head,j);
print(head);
}else if(c =='3'){
printf("你想要修改哪个节点的数据：\n");
scanf("%d",&cn);
change(head,cn);
print(head);
}else if(c =='4'){
exit(0);
}
}
}
struct stu *create(int n){
struct stu *head,*node,*end; //定义头节点，普通节点，尾节点
head = (struct stu *)malloc(sizeof(struct stu)); //给头节点申请内存
//head->id = n; //头节点的数据域保存链表的长度
end = head; //若是空表，则头尾地址一致
for(int i=0;iid,node->name); //给数据域赋值
end->next = node; //让上一个节点的数据域指向当前节点
end = node; //end指向当前节点，最终end指向尾节点
}
end->next = null; //给end的指针域置空
return head; //返回头节点的地址
}
void print(struct stu *head){
struct stu *p = head;
int j =1;
p = p->next; //不打印头节点的数据域中的值
while(p != null){
printf("%d\t%d\t%s\n",j,p->id,p->name);
p = p->next;
j ;
}
}
void deletenode(struct stu *head,int n){ //删除n处的节点
struct stu *p = head,*pr = head;
int i =0;
while(inext;
i ;
}
if(p!=null){
pr->next = p->next;
free(p);
} else{
printf("节点不存在！\n");
}
}
void insertnode(struct stu *head,int n){ //插入节点
struct stu *p = head,*pr;
pr = (struct stu*)malloc(sizeof(struct stu)); //让pr指向新建节点申请的内存
printf("input data:\n");
scanf("%d %s",&pr->id,pr->name);
int i = 0;
//当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空
while(inext;
i ;
}
if(p!=null){ //如果p没越界
pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址
p->next = pr; //使插入节点指向新建节点
}else{
printf("节点不存在！\n");
}
}
void change(struct stu *head,int n){
struct stu *p = head;
int i = 0;
while(inext;
i ;
}
if(p != null){
printf("请输入修改之后的值:\n");
scanf("%d %s",&p->id,p->name);
}else{
printf("节点不存在！\n");
}
}