一、链表的概念
? 定义：
? ? ? ? ?链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
? ?特点：
? ? ? ? ? ?链表是一系列节点组成，节点在运行时动态生成（malloc），每一个节点包括两个部分。
? ? ?一 个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域
?链表是一种线性存储结构,线性存储结构又可分两类：
? ? ? ? 一类是 顺序存储结构（即 数组的存储方式），其特点是是逻辑关系上相邻的两个元素在物理位置上也相邻，即在连续的地址块中存储一系列数据。
? ? ? ? ?一类是 链式存储结构（链表的存储方式），其特点为不需要逻辑上相邻的元素在物理位置上也相邻，即在不连续的地址中存储一系列数据 ，所以链表不能向数组一样通过下标随机访问。
那么链表之间的元素又是如何相互关联的呢？
? ? ? ? 它是由一系列的存储数据元素的单元通过指针串接来确定元素之间相互关系的,因此每个单元至少都有两个域—数据域和指针域，这样的单元也被称为节点(Node)。
二、为什么要用链表
? ? ?我们学完c语言之后，我们至少可以通过两种结构来存储数据，一种是“数组”，另外一种是“链表”。为什么还要学习链表呢，因为数组是连续的。
? ? ? ? ? 1、数组的缺点
? ? ? 1）因为他是连续。内存需要一块连续的空间。如果存储数据大的话，系统必须得找一块连续且大的空闲空间，如果找不到，就分配不成功。??? ?
? ? ? 2）数组不可以插入，删除里面的元素，满足不了我们项目的需求。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ?3）数组存放数据时，必须事先定义固定的长度? ? ? ? ??? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ?2、链表的优点?
? ? ? ?1）链表不需要连续地分配内存空间，每一个元素之间不是连续而是分开的，所以不需要很大的内存空间。
? ? ? ?2）链表可以插入，删除和添加等操作，且效率高
? ? ? ?3） 链表不需要像数组预先指定空间的长度，可以现用现分配。
? ? ? ? ? ? 3、链表的缺点
? ? ? ? 1）由于链表的每一个元素里面都有一个地址。相对而已，会占用比较多的内存，空间的开销会比较大。?
三、链表分类
链表可大致分为
? ? ? ? 1）单链表（最普通的链表）
? ? ? ? 2）双向链表（有两个指针域）
? ? ? ? 3）循环链表（首尾相接）
? ? ? ? 4）静态链表（链表的数组表示法）
四、链表的构成：（以上图为例）
#define MAX 20
typedef struct Node｛ // Node 结构体名，可以随便去，但不能是关键字
int data;
strutc Node *next;
}linkList; //linkList 等效于 struct Node?五，链表的操作
?1、链表的创建CreateLinkList
#include<stdio.h>
#include<srdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList(void)
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
2、 链表赋值
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList(void)
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
void PrintList(STU *head) //封装打印链表函数
{
STU *pmove = head->next;
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
int nmain()
{
int i=0;
int num=0;
STU * link = NULL;
STU * p_new = NULL;
link= CreateLinkList();
printf("请输入链表的初始个数：\n");
scanf("%d\n",&num);
for(i=0;i<num;i++)
{
p_new=(STU *)malloc(sizeof(STU));
printf("请输入数据：\n");
scanf("%d\n",&p_new->data);
}
PrintList(link);
return 0;
}3、创建新的单个节点 CreateNode
STU *CreateNode(int data)
{
STU * newhead = ( STU *)malloc(sizeof(STU));
newhead->data=data;
newhead->next=NULL;
return newhead;
}
4、打印链表PrintList()
void PrintList(STU *head)
{
STU *pmove = head->next; //头结点数据是0，因此，从头结点下一个数据开始打印，即head->next
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}5、插入节点（头插法）
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newhead = ( STU *)malloc(sizeof(STU));
newhead->data=data;
newhead->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(int data);
newNode->next = head->next;
head-> = newNode;
}5.1简单的头插法使用（完整代码）
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList()
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newNode = ( STU *)malloc(sizeof(STU));
newNode->data=data;
newNode->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(data);
newNode->next = head->next;
head->next=newNode;
}
void PrintList(STU *head)
{
STU *pmove = head->next;
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
int main()
{
int i;
STU *link=NULL;
link =CreateLinkList();
InsertHeadNode(link, 1);
InsertHeadNode(link, 2);
InsertHeadNode(link, 3);
InsertHeadNode(link, 4);
PrintList(link);
return 0;
}
运行结果
4321
?6、链表插入（中间插入）
//在哪个表插入，第几个位置，插入什么数据
void InsertNode(STU *head,int where，int data)
{
int k=0;
STU *q=head;
STU * newNode2 =CreateNode(int data);
for( k ; k<where ; k++)
{
if(q==NULL)
{
printf("create q fail\n");
exit(0);
}
q =q->next;
}
newNode2->next = q->next;
q->next = newNode2;
}6.1简单的插入（中间）法使用（完整代码）
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList()
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newNode = ( STU *)malloc(sizeof(STU));
newNode->data=data;
newNode->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(data);
newNode->next = head->next;
head->next=newNode;
}
void PrintList(STU *head)
{
STU *pmove = head->next;
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
//在哪个表插入，第几个位置，插入什么数据
void InsertNode(STU *head,int data)
{
int k=0;
int num;
STU *q=head;
STU * newNode2 = CreateNode(data);
printf("请输入插入中间第几个数：\n");
scanf("%d",&num);
for(k=1; k<=num;k++)
{
if(q==NULL)
{
printf("create q fail\n");
exit(0);
}
q =q->next;
}
newNode2->next = q->next;
q->next = newNode2;
}
int main()
{
int i;
STU *link=NULL;
link =CreateLinkList();
InsertHeadNode(link, 1);
InsertHeadNode(link, 2);
InsertHeadNode(link, 3);
InsertHeadNode(link, 4);
PrintList(link);
InsertNode(link,9);
PrintList(link);
return 0;
}
?7、链表查找（查找int类型的数据）
STU * link_search_num(STU *head,int data)
{
STU * pmove = head;
whlie(pmove != NULL)
{
//如果找到是当前结点数据，则返回当前结点的地址
if(pmove->data==data)
{
return pmove;
}
//如果没有找到，则继续对比下一个结点的指针域
pmove=pmove->next;
}
//当循环结束的时候还没有找到，返回一个NULL给主函数
return NULL; //没有找到
}
?7.1链表查找（查找char类型的数据）
typedef struct Node
{
//数据域
int data;
char name[20];
//指针域
struct Node *next;
}STU;
STU * link_search_name(STU *head,char *name)
{
STU * pmove = head;
whlie(pmove != NULL)
{
//如果找到是当前结点数据，则返回当前结点的地址
if(strcmp(pmove->name,name)==0) //找到了
{
return pmove;
}
//如果没有找到，则继续对比下一个结点的指针域
pmove=pmove->next;
}
//当循环结束的时候还没有找到，返回一个NULL给主函数
return NULL; //没有找到
}
7.2简单链表查找使用（完整代码）
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList()
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newNode = ( STU *)malloc(sizeof(STU));
newNode->data=data;
newNode->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(data);
newNode->next = head->next;
head->next=newNode;
}
void PrintList(STU *head)
{
STU *pmove = head->next;
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
STU * link_search_num(STU *head,int data)
{
STU * pmove = head;
while(pmove != NULL)
{
//如果找到是当前结点数据，则返回当前结点的地址
if(pmove->data==data)
{
return pmove;
}
//如果没有找到，则继续对比下一个结点的指针域
pmove=pmove->next;
}
//当循环结束的时候还没有找到，返回一个NULL给主函数
return NULL; //没有找到
}
int main()
{
int i;
STU *link=NULL;
STU *p =NULL;
link =CreateLinkList();
InsertHeadNode(link, 1);
InsertHeadNode(link, 2);
InsertHeadNode(link, 3);
InsertHeadNode(link, 4);
PrintList(link);
p=link_search_num(link,3); // 查找3这个数据
if(p !=NULL)
{
printf("%d\n",p->data); //打印查找的数据
}
else
{
printf("没有这个数据\n");
}
return 0;
}
运行结果
4321
3
?8、链表的删除某个数据
int dellte_List(STU *head,int deldata)
{
//定义两个指针，一个指该删除数据前一个结点（ppre），一个指向该删除数据的结点（pp）
STU *pp = head->next;
STU *ppre = head;
while(pp != NULL)
{
pp= pp->next;
ppre=ppre->next;
if(pp->data==deldata)
{
break;
}
}
if(!pp) //如果p是有该数据，则为真。！p则为假，就不会执行
{
return 0;
}
ppre->next = pp->next;
free(pp);
return 1;
}
删除操作示意图?
?8.1简单删除操作使用
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList()
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newNode = ( STU *)malloc(sizeof(STU));
newNode->data=data;
newNode->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(data);
newNode->next = head->next;
head->next=newNode;
}
void PrintList(STU *head)
{
STU *pmove = head->next; //头结点数据是0，因此，从头结点下一个数据开始打印，即head->next
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
STU * link_search_num(STU *head,int data)
{
STU * pmove = head;
while(pmove != NULL)
{
//如果找到是当前结点数据，则返回当前结点的地址
if(pmove->data==data)
{
return pmove;
}
//如果没有找到，则继续对比下一个结点的指针域
pmove=pmove->next;
}
//当循环结束的时候还没有找到，返回一个NULL给主函数
return NULL; //没有找到
}
int dellte_List(STU *head,int deldata)
{
//定义两个指针，一个指该删除数据前一个结点（ppre），一个指向该删除数据的结点（pp）
STU *pp = head->next;
STU *ppre = head;
while(pp != NULL)
{
pp= pp->next;
ppre=ppre->next;
if(pp->data==deldata)
{
break;
}
}
if(!pp) //如果p是有该数据，则为真。！p则为假，就不会执行
{
return 0;
}
ppre->next = pp->next;
free(pp);
return 1;
}
int main()
{
int i;
STU *link=NULL;
STU *p =NULL;
link =CreateLinkList();
InsertHeadNode(link, 1);
InsertHeadNode(link, 2);
InsertHeadNode(link, 3);
InsertHeadNode(link, 4);
PrintList(link);
p=link_search_num(link,3);
if(p !=NULL)
{
printf("%d\n",p->data);//打印查找的数据
}
else
{
printf("没有这个数据\n");
}
dellte_List(link,3);
PrintList(link);
return 0;
}
?运行结果
4321
3
421
9、链表的反转ReverseList()
int ReverseList(STU *h)
{
STU *q =NULL;
STU *p =NULL;
if(h==NULL)
{
printf("h 是创建失败\n"); //失败不是空表，是没有这个h的头指针
return 0;
}
// h->next ==NULL：只有一个头指针，没结点，即空表，反过来还是一样的
// h->next->next ==NULL：只有一个结点，反过来还是一样的
if( h->next ==NULL || h->next->next ==NULL)
{
return 1;
}
p = h->next->next; //p指向原来链表的第二个结点
h->next->next =NULL; //把链表一分为二，h指向的链表只有一个结点。即原来的链表的第一个结点
while(p!=NULL)
{
q = p;
p=p->next;
q->next=h->next;
h->next= q;
}
return 0;
}9.1简单的链表反转使用（完整代码）
#include<stdio.h>
#include<stdlib.h>
#define ERROR O
#define OK 1
//初始化一个链表里面的需要用的数据，作为模版，为之后创建直接调用
typedef struct Node
{
//数据域
int data;
//指针域
struct Node *next;
}STU;
STU * CreateLinkList()
{
STU * head = NULL;
head=(STU *)malloc(sizeof(STU)); //节点开辟一个空间.head变成指向第一个节点的头指针
if(head==NULL)
{
exit(0);
}
head ->next = NULL;
return head;
}
STU *CreateNode(int data) //插入什么数据，调用此函数，返回这个数据节点指针
//方便使用
{
STU * newNode = ( STU *)malloc(sizeof(STU));
newNode->data=data;
newNode->next=NULL;
return newNode;
}
void InsertHeadNode(STU *head,int data)
{
STU * newNode =CreateNode(data);
newNode->next = head->next;
head->next=newNode;
}
void PrintList(STU *head)
{
STU *pmove = head->next;
while(pmove)
{
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
}
int ReverseList(STU *h)
{
STU *q =NULL;
STU *p =NULL;
if(h==NULL)
{
printf("h 是创建失败\n"); //失败不是空表，是没有这个h的头指针
return 0;
}
// h->next ==NULL：只有一个头指针，没结点，即空表，反过来还是一样的
// h->next->next ==NULL：只有一个结点，反过来还是一样的
if( h->next ==NULL || h->next->next ==NULL)
{
return 1;
}
p = h->next->next; //p指向原来链表的第二个结点
h->next->next =NULL; //把链表一分为二，h指向的链表只有一个结点。即原来的链表的第一个结点
while(p!=NULL)
{
q = p;
p=p->next;
q->next=h->next;
h->next= q;
}
return 0;
}
int main()
{
int i;
STU *link=NULL;
link =CreateLinkList();
InsertHeadNode(link, 1);
InsertHeadNode(link, 2);
InsertHeadNode(link, 3);
InsertHeadNode(link, 4);
PrintList(link);
ReverseList(link);
PrintList(link);
return 0;
}
运行结果
4321
1234
个人总结，适合小白学习，如有错误，请留下指正，谢谢。