[线性表](2.3)单链的基本操作
对链表的基本操作有:创建,查找,插入,删除,修改,也就是我们常常说的增删改查
建立带有头结点的单向链表
建立链表就是根据需要一个一个的开辟新结点,在结点中存放数据,并建立结点之间的链接关系,建立单向链表有两个关键的问题:
第一、结点的存储空间必须是由程序来动态分配的
第二、结点之间必须形成链状
建立单向链表的主要操作步骤如下:
- 读取数据
- 生成新节点
- 将数据存入节点的成员变量中
- 将新结点添加到链表中
- 重复上述操作直至输入结束
我们用一段代码来说明:建立一个学生电话簿的单向链表
从图可以知道,我们需要一个头指针,一个头结点,还有一个不断创建结点的指针
先上代码:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inputst(void);
void aboutst(void);
struct st1
{
char name[20];
long long tel;
struct st1* next;
};
struct st1* head, * input, * p;
//head为头节点,p为头指针,input用于不断创建节点
int main()
{
head = (struct st1*)malloc(sizeof(struct st1));
head->next = NULL;
char a;
while (1)
{
printf("请输入功能:1.创建,2.查看");
a = _getche();
switch (a)
{
case '1':
Inputst();
break;
case '2':
aboutst();
break;
}
}
system("pause");
return 0;
}
void Inputst(void)
{
char name[20];
input = (struct st1*)malloc(sizeof(struct st1));
if (input == NULL)
{
printf("分配失败");
return 0;
}
printf("请输入姓名:");
gets(name);
strcpy(input->name, name);
printf("请输入电话:");
scanf("%I64d", &input->tel);
p = head;
while (p->next != NULL)
{
p = p->next;
}
p->next = input;
input->next = NULL;
printf("创建成功\n");
}
void aboutst(void)
{
int n = 0;
p = head->next;
if (p != NULL)
{
while (p != NULL)
{
printf("姓名:%s 电话:%I64d\n", p->name, p->tel);
p = p->next;
n++;
}
printf("\n共记录%d条电话信息", n);
}
else
{
printf("未存储信息\n");
}
}
首先先看结构体的定义:
- 结构体拥有三个成员,其中name和tel为数据域,next为指针域
- 程序拥有三个结构体指针,head,input,p
接下来咱们创建一个链表:
- 在主函数内,我们用head指针充当头结点
- 我们可以看到语句head->next指向空,将头结点的指针域指向为空
这儿用图表示就是:
这时主函数其他数据是输入选择,与链表无关
那么创建链表,我们已经完成了一个头节点的创建,这个时候,我们来看Input函数内
从上述代码可知,程序又为input开辟了一片内存
这时要求输入了,在input的数据域内载入数据
假设我们输入:Axuan,10086
那么input所指向内存中并有了数据
这时我们如何将两者连接起来呢?思路:
- 利用头指针指向头结点(在头结点内我们不使用数据域)
- 判断头结点的指针域是否为空
- 不为空则将指针移到头指针的指针域(下一个节点)继续判断
- 直到找到为空的指针域
- 将为空的指针域指向input所创建的结点
- 将所创建节点的指针域指向空
代码:
从上图可以看到,我们将p作为头指针:
判断头结点的指针域是否为空
- 找到为空的指针域
- 将为空的指针域指向input所创建的结点
- 将所创建节点的指针域指向空
这时一个单向链表结构就创建好了
到这儿我们可以知道:
- P作为头指针,负责指向结点加以操作
- head作为头结点,充当火车头的角色,方便管理后面的节点(务必使用)
- Input的作用于不断创建节点