一：基本知识
2：特点：内存不连续，通过指针链接
解决: 长度固定的问题，插入删除麻烦的问题
- 逻辑结构：线性结构
- 存储结构：链式存储
- 操作：增删改查
二：单向链表
结构体：
struct node_t
{
int data;//数据域
struct node_t * next;//指针域
}；
2.1.1分类
1>有头单向链表
存在一个头节点，数据域无效，指针域有效
2>无头单向链表
所有节点的指针域和数据域都有效
两者遍历：
#include <stdio.h>
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, char const *argv[])
{
// 定义几个节点
struct node_t s;
struct node_t s3 = {3, NULL};
struct node_t s2 = {2, NULL};
struct node_t s1 = {1, NULL};
s.next=&s1;
//节点链接
s1.next=&s2;
s2.next=&s3;
// 定义一个指针，指向第一个节点
//struct node_t *p = &s1;
struct node_t *p=&s;
//遍历无头节点
// while (p != NULL)
// {
// printf("%d ", p->data);
// putchar('\n');
// p = p->next;
// }
//遍历有头结点
while(p->next!=NULL)
{
p=p->next;
printf("%d ",p->data);
}
putchar('\n');
return 0;
}三：头文件定义
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;
//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.遍历单向链表
void ShowLinkList(link_node_t *p);
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
//7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
//8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
//9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data);
//10.转置链表
void ReverseLinkList(link_node_t *p);
//11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif
四：代码实现
#include"linklist.h"
//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList()
{
link_node_t *p=(struct node_t *)malloc(sizeof(link_node_t));
if(p==NULL)
{
perror("开辟失败");
return NULL;
}
p->next=NULL;
return p;
}
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data)
{
//容错判断
if(post<0||post>LengthLinkList(p))//判断链表长度是否为空
{
perror("插入失败");
return -1;;
}
//讲头指针移动到北插入未知的前一个节点
for(int i=0;i<=post-1;i++)
{
p=p->next;
}
link_list_t pnew =CreateEpLinkList();
//赋值
pnew->data=data;
pnew->next=NULL;
//将节点插入链表(先连后面，再连前面)
pnew->next=p->next;
p->next=pnew;
return 0;
}
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{
int num=0;
while(p->next!=NULL)
{
p=p->next;
num++;
}
return num;
}
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)
{
//容错判断
if(post<0||post>=LengthLinkList(p)||IsEpLinkList(p))
{
perror("删除失败：");
return -1;
}
//将头指针移动到被删除未知的前一个节点
for(int i=0;i<post;i++)
{
p=p->next;
}
//定义一个指针指向被删除节点
link_list_t pdel=p->next;
//将被删除节点的next域指向前一个数据的next域
p->next=pdel->next;
//释放被删除空间的空间
free(pdel);
pdel=NULL;
return 0;
}
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{
return p->next==NULL;
}
//3.遍历单向链表
void ShowLinkList(link_node_t *p)
{
p=p->next;
//遍历无头单向链表
while(p!=NULL)
{
printf("%d",p->data);
p=p->next;
}
// int n=LengthLinkList(p);
// for(int i=0;i<n;i++)
// {
// p=p->next;
// printf("%d",p->data);
// }
putchar('\n');
return ;
}
//7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data)
{
if(post<0||post>=LengthLinkList(p)||IsEpLinkList(p))
{
perror("失败：");
return -1;
}
for(int i=0;i<=post;i++)
{
p=p->next;
}
p->data=data;
return 0;
}
//8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data)
{
int sum=0;
while(p->next!=NULL)
{
p=p->next;
if(p->data==data)
return sum;
sum++;
// return -1;
}
return -1;
}
//9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
{
//定义一个指针指向头结点的下一个节点，，此时q可以看做指向一个无头单向链表
link_node_t *q=p->next;
//用q遍历无头单向链表，将每一个节点的数据与与data作比较，如果相同就删除
while(q!=NULL)
{
if(q->data==data)//如果相等，说明需要删除q所指向的节点
{
//跨过被删除节点
p->next=q->next;
//释放被删除节点
free(q);
//将q指向链表删除节点的下一个节点
q=p->next;
}
else//不相等，直接向后移
{
p=p->next;
q=q->next;
}
}
return 0;
}
//10.转置链表
void ReverseLinkList(link_node_t *p)
{
//定义一个指针去保存q下一个节点的地址
link_list_t temp=NULL;
//定义一个指针指向头结点的下一个节点（相当于无头单向链表的头指针）
link_list_t q=p->next;
//断开链表
p->next=NULL;
//遍历无头指针
while(p!=NULL)
{
//暂时存放下一个节点，防止丢失
temp=p->next;
//头插到有头单向链表的后面
q->next=p->next;
p->next=q;
//将q重新指向之前的无头单向链表，指向第一个节点
q=temp;
}
return;
}
//11.清空单向链表
void ClearLinkList(link_node_t *p)
{
//link_list_t pdel=NULL;
while(!IsEpLinkList(p))
{
DeleteDataLinkList(p,0);
// pdel=p->next;
// p->next=pdel->next;
// free(pdel);
// pdel=NULL;
}
return;
}