一丶概念
链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。
和顺序表不同同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。
二丶特点
解决: 长度固定的问题,插入删除麻烦的问题
逻辑结构:线性结构
存储结构:链式存储
操作:增删改查
struct node
{int data; //数据域:存储数据struct node *next; //指针域:存储下一个节点的地址
};
三丶单向链表
1.分类
有头链表:存在一个头节点,头节点数据域无效,指针域有效。
无头链表:每一个节点的数据域和指针域都有效。
2.有头单向链表
存在一个头节点,数据域无效,指针域有效
#include <stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域struct node *next;//指针域
} node_t, *node_p;
int main(int argc, char const *argv[])
{node_t A={1,NULL};//输入数据node_t B={2,NULL};node_t C={3,NULL};node_t D={4,NULL};A.next=&B;B.next=&C;C.next=&D;node_p p;//头指针指向头节点node_t S = {'\0',&A};p=H.next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");return 0;
}
3.无头单向链表
所有节点的指针域和数据域都有效
#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{datatype data; //数据域用来存数据struct node *next; //指针域用来存下一个节点的地址
} node_t, *node_p;// node_t A; //等同于 struct node A;
// node_p p; //等同于 struct node *p;int main(int argc, char const *argv[])
{//1.定义4个节点node_t A = {'a', NULL};node_t B = {'b', NULL};node_t C = {'c', NULL};node_t D = {'d', NULL};//2.连接四个节点A.next = &B; //连接A和BB.next = &C;C.next = &D;//3.定义一个头指针指向第一个节点node_p p = &A;//4. 通过指针遍历无头单向链表while (p != NULL){printf("%c ", p->data); //打印节点中的数据域 a b c dp = p->next; //让p指向下一个节点}printf("\n");return 0;
}
链表尾插法练习
写一个有头单向链表,用于保存输入的学生成绩,实现一输入学生成绩就创建一个新的节点,将成绩保存起来。再将该节点链接到链表的尾,直到输入-1结束。
要求:每个链表的节点由动态内存分配得到 , 也就是用malloc。
过程:
1. malloc申请空间link_node_t大小作为头节点
2. 将新节点放到链表尾部
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域存放数据struct node *next;//指针域记录下一个结点地址
} node_t, *node_p;
void ShowLinklist(node_p p)//打印数据
{while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
int main(int argc, char const *argv[])
{int score = 0;// 创建一个头节点node_p p_head = (node_p)malloc(sizeof(node_t));if (NULL == p_head)//容错判断{printf("malloc err");return -1;}//让头指针的指针域置空p_head->next = NULL;//创建一个尾节点node_p p_tail = (node_p)malloc(sizeof(node_t));if (NULL == p_head){printf("p_tail malloc err");return -1;}p_tail = p_head;//让尾节点指向头节点while (1){//循环输入成绩scanf("%d", &score);//输入-1时停止结束循环if (score == -1)break;//新建一个节点p_newnode_p p_new = (node_p)malloc(sizeof(node_t));if (NULL == p_new)//容错判断{printf("p_new malloc err");return -1;}p_new->data = score; //将数据存入新的节点p_new->next = NULL;//让新的节点的指针域置空p_tail->next = p_new;//让尾节点连接到新的节点p_tail=p_new;//更新尾节点}node_p p = p_head->next;ShowLinklist(p);return 0;
}
4.有头单向链表的函数操作
1. 先遍历找到要插入节点的前一个节点,假设这个节点为A;A的下一个节点为B;将C插入A与B之间;
2.先让C的指针域指向B;
3.再让A的指针域指向C;
(注意:顺序不可以调换)
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new) // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data; // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new; // 前一个节点的指针域等于新节点的地址return 0;
}
删除的思想
2、找一个临时指针指向要删除的节点;
3、 将A的指针域指向删除节点的下一个节点;
4、 释放被删除节点
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next; node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next; // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1); // 将被删除指针释放,指针置空p1 = NULL;
}
转置的思想:
(1) 将头节点与当前链表断开,断开前保存下头节点的下一个节点,保证后面链表能找得到,定义一个q保存头节点的下一个节点,断开后前面相当于一个空的链表,后面是一个无头的单向链表
(2) 遍历无头链表的所有节点,将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)
void ReverseLinkList(node_p p)
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}
完整的单链表操作
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data; // 数据域存放数据struct node *next; // 指针域记录下一个结点地址
} node_t, *node_p;
node_p CreateEpLinkist() // 创建一个空的有头单向链表
{node_p p = (node_p)malloc(sizeof(node_t)); // 开辟节点空间大小if (NULL == p){printf("CreatEpLinklist err");return NULL;}p->next = NULL; // 初始化头结点return p;
}
int StrlenLinklist(node_p p)//计算单链表长度
{int len = 0;while (p->next != NULL){p = p->next;len++;}return len;
}
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new) // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data; // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new; // 前一个节点的指针域等于新节点的地址return 0;
}
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next; node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next; // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1); // 将被删除指针释放,指针置空p1 = NULL;
}
void ModifyLinklist(node_p p, int post, int data) // 修改函数
{for (int i = 0; i <= post; i++) // 让指针指向要修改的节点位置p = p->next;p->data = data; // 指针域等于新的数据
}
void SearchLinklist(node_p p, int data)//查找数据
{int i = 0;p = p->next;while (p != NULL){if (p->data == data){printf("%d\n", i);//打印第一个相同数据的下标break;}p = p->next;i++;}
}
void ClearLinklist(node_p p)//清空链表
{while(StrlenLinklist(p)!=0){DeleteLinklist(p,0);//删除第一个节点}
}
void ShowLinklist(node_p p)// 打印数据
{while (p->next)// 当指针p的指针域为空时停止循环{p = p->next;printf("%d ", p->data);}printf("\n");
}
void ReverseLinkList(node_p p)//链表转置
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}}
int IsEpLinklist(node_p p)
{return p->next == NULL;
}
int main(int argc, char const *argv[])
{node_p p = CreateEpLinkist(); // 创建一个空的有头单向链表InsertLinklist(p, 0, 1);// 进行插入数据InsertLinklist(p, 1, 2);InsertLinklist(p, 2, 3);InsertLinklist(p, 3, 4);InsertLinklist(p, 4, 5);InsertLinklist(p, 5, 6);ShowLinklist(p);// 打印数据DeleteLinklist(p, 0);// 删除数据ShowLinklist(p);// 打印数据ModifyLinklist(p, 0, 0); // 修改数据ShowLinklist(p);// 打印数据SearchLinklist(p, 2);ReverseLinkList(p);ShowLinklist(p);// 打印数据ClearLinklist(p);if(IsEpLinklist(p))printf("IsEpLinkList\n");free(p);p =NULL;return 0;return 0;
}
5.单向循环链表
四丶总结:
顺序表和单向链表比较:
(1).顺序表在内存当中连续存储的(数组),但是链表在内存当中是不连续存储的,通过指针将数据链接在一起
(2).顺序表的长度是固定的,但是链表长度不固定
(3).顺序表查找方便,但是插入和删除麻烦,链表,插入和删除方便,查找麻烦