[题集]指针与链表
以上链表的第一个节点都不存放数据，如果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);
}由于头节点中不存放数据，头指针始终指向头节点，所有操作均在头结点后完成
添加和删除并无很大的区别，只是不需要考虑头指针的指向，所有操作都是从头节点开始。
而头节点中存放数据，则需要考虑头指针的指向来进行操作
添加和删除与上述无太大区别，就不多做废话了。
到这里指针与链表的基础就学完了。
课时总结
链表是一种数据结构，它除了可用指针实现，也可以用数组实现，是一种思想，需要掌握的就是各个节点的链接。
指针域的指向，如何用操作指针来操作指针域，当然用指针实现的链式存储结构是需要从表头或表尾来进行操作的，它不能像数组一样指定下标来进行操作。
原因是数组的内存是固定的具有连续性的，通过下标能轻易的操作所属的内存区域，而链式存储所有内存都是不连续性的，只能通过头指针存储表头的地址，依次进行访问和操作