目录
- 前言
- 链表的定义
- 链表的分类
- 单链表的相关操作
- 链表的优缺点
我们之前使用数组来存放数据，但使用数组时，要先指定数组中包含元素的个数，即数组长度。如果向数组中加入的元素个数超过了数组长度，便不能正确保存其中内容。且这种方式特别浪费空间。这时就希望有一种存储方式，其存储元素的个数是不受限制的，当要添加更多元素时，存储的个数会随之增加，这种方式被称为链表。链表是一种常见的数据结构。
数据的存储结构有两种:
- 连续存储【数组】
数组是由固定数目的同类型的元素按顺序排列而构成的数据结构，其中的元素被存储在一段连续的内存空间中
优点：存取速度很快
缺点：插入删除元素很慢，空间通常是有限制的，事使用前声明数组长度，需要大块连续的内存块 - 离散存储【链表】
链表是一种非连续的数据结构，链表在内存中不连续存储
优点：空间没有限制 插入删除元素很快
缺点：存取速度很慢
- n个结点离散分配
- 彼此通过指针相连
- 每个结点只有一个前驱结点，每个节点只有一个后续结点
- 首节点没有前驱结点，尾节点没有后续结点
专业术语：
首结点：第一个有效节点
尾节点：最后一个有效结点
头节点：第一个有效结点之前的结点，头结点不存放有效数据，且头结点主要为了方便对链表的操作
头指针：指向头结点的指针变量，且存放头结点的地址
尾指针：指向尾节点的指针变量
注：确定一个数组，需要三个参数：元素个数，首地址，长度
如若通过一个函数对链表进行处理，至少需要几个参数？
只需要一个参数：头指针
通过头指针可以推算出链表的其他所有参数（头指针存放头结点的地址，而头结点和其后结点数据类型相同）
定义一个简单的结构体：
struct student
{
char name[20];//数据域
int age;//数据域
struct student * next;//指针域
};
链表中，一个元素包含两部分：数据域和指针域
数据域：能存放有效数据的地方
指针域：用来指向下一个元素
最后一个元素的指针指向NULL，表示指向地址为空
- 单链表
- 双链表
- 循环链表
- 非循环链表
单链表的创建单链表：每个结点只有一个指针，每个结点的指针都指向下一结点，所有结点单线联系
双链表：添加了一个指针域，通过两个指针域，分别指向节点的前结点和后节点
循环链表：最后一个结点的指针指向链表头结点，头尾相连，形成一个环形的数据链；
单链表的建立就是在程序运行的过程中，从无到有的建立一个链表，即一个一个分配结点的内存空间，输入结点的数据，建立结点间的相连关系
头插法：始终让每个新结点放在链表中第一个位置，即对链表进行遍历时先遍历的是最后加入链表的结点
尾插法：每次把新结点放在链表的最后一个位置
int icount;//全局变量表示链表长度
struct student *create() //定义一个creat函数用来创建链表，函数返回链表的头指针
{
struct student *phead=NULL;//初始化链表，头指针为空
struct student *pEnd,*pNew;
icount=0;//初始化链表长度
pEnd=pNew=(struct student *)malloc(sizeof(struct student));
printf("请输入名字和年龄：n");
scanf("%s",pNew->name);
scanf("%d",pNew->age);
while(pNew->age!=0)
{
icount++;
if(icount==1)
{
pNew->next=phead;//使指针指向为空
pEnd=pNew;//跟踪新加入的结点
phead=pNew;//头指针指向首结点
}
else
{
pNew->next=NULL;//新结点的指针为空
pEnd->next=pNew;//原来的结点指向新节点
pEnd=pNew;//pEnd指向新结点
}
pNew=(struct student *)malloc(sizeof(struct student));//分配新节点的内存空间
scanf("%s",&pNew->name);
scanf("%d",&pNew->age)
}
free(pNew);//释放结点空间
return phead;
}
单链表的遍历
将链表创建好后，对链表中的数据进行遍历并进行输出
void print(struct student *phead)
{在这里插入图片描述
struct student *pTemp;//定义一个循环所用的临时指针
int n=1;//链表中的结点序号
printf("一共有%d个学生n",icount);
pTemp=phead;//指针得到首结点的地址
while(pTemp!=NULL)
{
printf("第%d个学生是：n",n);
printf("姓名：%sn",pTemp->name);
printf("年龄：%dn",pTemp->age);
pTemp=pTemp->next;//移动临时指针到下一个结点
n++;//进行自加运算
}
}
单链表的插入
在1位置插入结点的具体步骤：
- 为新建节点申请内存空间和赋值
- 定义一个指针指向这个新建结点的地址
- 将新建节点插入到首节点和普通结点之间，则新建节点将成为2号位，其后结点位数加一
- 将首节点的指针域赋值给新建结点的指针域
- 将首节点的指针域指向新建节点
正确写法：
r=p-.>pnext;//r指向p后面的结点
p->pnext=q;//将p的指针域赋给q
q->pnext=r;
struct student * insert(struct student * phead)
{
struct student *q;//定义q指向新分配的空间
printf("请输入学生的姓名和年龄: n");
q=(struct student *)malloc(sizeof(struct student));//分配内存空间
scanf("%s",&q->name);
scanf("%s",&q->age);
q->next=phead;//新结点的指针指向原来的首结点，保存首结点的地址
phead=pnew;//头指针指向新结点
icount++;//增加链表的结点数量
return phead;//返回头指针
}
单链表的删除
删除普通结点的步骤：
- 首结点的指针域指向普通节点，普通结点的指针域指向尾节点
- 将首节点的指针域指向尾节点，相当于删除普通结点
- 释放普通节点的内存
正确写法：
r=p->pnext;//指向p后面的结点
p->pnext=r->pnext;//指向p后面的后面的结点
free( r );//释放r的内存
void delete(struct Stu * phead,int n)//phead为头结点，n为要删除的结点序号
{
int i;
struct student *pTemp;
struct student *pPre;
pTemp=pHead;
pPre=pTemp;
printf("删除第%d个学生 n",n);
for(i=1;inext;
}
pPre->next=pTemp->next;//连接删除结点两边的结点
free(pTemp);//释放要删除结点的内存空间
icount--;//减少链表中的结点个数
}
链表的优缺点
-
优点：空间没有限制
-
优点： 插入删除元素很快
-
缺点：存取速度很慢
对链表的分享就到这啦，如果有错误，欢迎大家矫正
