[题集]指针与链表
以上链表的第一个节点都不存放数据,如果head指向的节点也存放数据,则堆栈程序应该如何修改。
栈的实现:先进先出。删除和添加都在前端
程序思路:
添加:定义一个结构体,不初始化头结点,在添加结点的时候判断头指针是否为空,如果为空,则让头指针指向新添加的节点,节点的指针域为空,如果不为空,则让新结点的指针域链接头指针所指向的节点,头指针指向新结点。
删除:删除在前端,也就是回收头指针所指向的节点,先用一个结构体指针保存头节点的指针域,再释放头节点,再让头指针指向头节点的指针域
代码实现:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
int id;
int score;
struct student* next;
};
typedef struct student ST;
ST* head, * p , * s;
int main()
{
char a;
while (1)
{
printf("请输入需要的功能: 1.增加 2.删除 3.遍历 4.退出\n");
a = _getch();
switch (a)
{
case'1':
Inser();
break;
case'2':
Delete();
break;
case'3':
Display();
break;
case'4':
Quit();
break;
}
}
}
void Inser()
{
p = (ST*)malloc(sizeof(ST));
printf("请输入ID:");
scanf("%d", &p->id);
printf("请输入分数:");
scanf("%d", &p->score);
if (head == NULL)
{
head = p;
head->next = NULL;
}
else
{
p->next = head;
head = p;
printf("\n添加成功\n");
}
}
void Delete()
{
if (head == NULL)
{
printf("\n未找到数据\n");
}
else
{
s = head->next;
free(head);
head = s;
printf("\n删除成功\n");
}
}
void Display()
{
if (head == NULL)
{
printf("\n未找到数据\n");
}
else
{
s = head;
while (s != NULL)
{
printf("\nID:%d\tScore:%d\n", s->id, s->score);
s = s->next;
}
}
}
void Quit()
{
exit(0);
}
定义结构体
程序定义了一个结构体,也定义了三个指针
- head作为头指针,始终指向第一个节点
- p作为分配指针,不断创建新的节点
- s作为操作指针,用于实现各项功能,临时存放地址
添加功能
用p创建一个新的节点载入数据域,先判断头指针是否有指向,如果没有的话让头指针指向新创建的节点,作为头节点
如果有的话,先让新节点的指针域指向头指针内保存的地址,再让头指针指向新节点
删除功能
就完成了增加节点,我们看看如何删除节点,由于是栈实现,先进先出,则删除也是在前端
这儿用到了操作指针s,先判断头头指针是否指向节点,如果没有,则未添加数据
如果有,则先让s指向头节点的指针域,保存头节点后的节点地址,然后再释放头节点,最后将头指针指向s
就完成了删除工作。
不同之处
相比于头节点中不存放数据,头节点中存放数据很容易导致逻辑错误,头指针一不注意就会乱指。
头节点存放数据:头指针指向第一个节点,当需要添加和删除的时候,需要注意头指针的指向,和节点指针域的指向
头节点不存数据:在所有动作之前必须初始化头节点,头指针始终指向这一个节点,所有操作都在头节点后完成,只需要注意指针域的指向,不容易造成逻辑错误
当然,两种方式在进行所有操作之前,都要判断是否为空链表!
下一题:
有一链表添加和删除都在后端,请以head所指向的节点存放数据和未存放数据两种编写程序,并加以比较
添加和删除都在后端,头节点带数据:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
int id;
int score;
struct student* next;
};
typedef struct student ST;
ST* head, * p, * s, * s1;
int main()
{
char a;
while (1)
{
printf("请输入功能:1.添加 2.删除 3.显示 4.退出\n");
a = _getch();
switch (a)
{
case'1':
Inser();
break;
case'2':
Delete();
break;
case'3':
Display();
break;
}
}
return 0;
}
void Inser()
{
p = (ST*)malloc(sizeof(ST));
printf("请输入ID:");
scanf("%d", &p->id);
printf("请输入分数:");
scanf("%d", &p->score);
if (head == NULL)
{
head = p;
p->next = NULL;
}
else
{
s = head;
s1 = head->next;
while (s1 != NULL)
{
s = s1;
s1 = s1->next;
}
s->next = p;
p->next = NULL;
}
}
void Delete()
{
if (head == NULL)
{
printf("\n未存放数据\n");
}
else
{
s = head;
s1 = head->next;
if (s1 == NULL)
{
head = NULL;
free(s);
}
else
{
while (s1->next != NULL)
{
s = s1;
s1 = s1->next;
}
s->next = NULL;
free(s1);
}
printf("\n删除成功\n");
}
}
void Display()
{
if (head == NULL)
{
printf("\n未找到数据\n");
}
else
{
s = head;
while (s != NULL)
{
printf("\n%d\t%d\n", s->id, s->score);
s = s->next;
}
}
}
重点在添加和删除哪儿,我选择了两个操作指针来控制,逻辑清晰一些,程序要求添加和删除都在尾端,则需要利用while找到指针域为NULL的节点,进行添加和删除
添加只需要将尾结点的指针域指向新结点,新结点的指针域再指向NULL即可
而删除则需要找到指针域为空的前一个节点,然后删除指针域为空的节点,再将前一个结点指向空
添加节点
先利用分配指针p新分配一个节点,再判断是否有头结点(头指针是否有数据)
如果有头节点,则利用一个while循环找到尾结点,从头结点开始,S控制当前节点,s1控制后置节点
找到尾端节点后,将尾结点的指针域指向新节点,将新节点的指针域指向NULL
删除功能
先看代码:
还是先判断头指针是否指向数据
如果有的话,则从头节点开始,让s管理当前节点,s1管理后置节点
直到后置节点的指针域为空的时候,找到了尾端结点
随即将当前节点的指针域为空,断开与尾结点的链接,这时s1管理着尾结点,最后回收s1的空间,完成了尾删的动作
头节点不带数据
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
int id;
int score;
struct student* next;
};
typedef struct student ST;
ST* head, * p, * s, * s1;
int main()
{
head = (ST*)malloc(sizeof(ST));
head->next = NULL;
char a;
while (1)
{
printf("请输入功能:1.添加 2.删除 3.显示 4.退出\n");
a = _getch();
switch (a)
{
case'1':
Inser();
break;
case'2':
Delete();
break;
case'3':
Display();
break;
}
}
return 0;
}
void Inser()
{
p = (ST*)malloc(sizeof(ST));
printf("请输入ID:");
scanf("%d", &p->id);
printf("请输入学分:");
scanf("%d", &p->score);
s = head;
s1 = head->next;
while (s1 != NULL)
{
s = s1;
s1 = s1->next;
}
s->next = p;
p->next = s1;
printf("\n添加成功\n");
}
void Delete()
{
s = head;
s1 = head->next;
if (s1 == NULL)
{
printf("\n未找到数据\n");
}
else
{
while (s1->next != NULL)
{
s = s1;
s1 = s1->next;
}
s->next = NULL;
free(s1);
printf("\n删除成功\n");
}
}
void Display()
{
s = head;
s1 = head->next;
if (s1 == NULL)
{
printf("\n未找到数据\n");
}
else
{
while (s1 != NULL)
{
s = s1;
s1 = s1->next;
printf("\nID:%d\t分数:%d\n", s->id, s->score);
}
}
}
void Quit()
{
exit(0);
}
由于头节点中不存放数据,头指针始终指向头节点,所有操作均在头结点后完成
添加和删除并无很大的区别,只是不需要考虑头指针的指向,所有操作都是从头节点开始。
而头节点中存放数据,则需要考虑头指针的指向来进行操作
添加和删除与上述无太大区别,就不多做废话了。
到这里指针与链表的基础就学完了。
课时总结
链表是一种数据结构,它除了可用指针实现,也可以用数组实现,是一种思想,需要掌握的就是各个节点的链接。
指针域的指向,如何用操作指针来操作指针域,当然用指针实现的链式存储结构是需要从表头或表尾来进行操作的,它不能像数组一样指定下标来进行操作。
原因是数组的内存是固定的具有连续性的,通过下标能轻易的操作所属的内存区域,而链式存储所有内存都是不连续性的,只能通过头指针存储表头的地址,依次进行访问和操作