#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
// 单链表的基本运用
typedef struct Struct6_student
{
int score;
struct Struct6_student *next;
} Struct6List;
// 打印单链表
void Struct6_print(Struct6List * h)
{
int i = 0;
printf("节点个数:%d\n", h->score);
while (h->next) {
h = h->next;
printf("%d:%d ", ++i, h->score);
}
printf("\n");
}
// 创建 n个节点
Struct6List * Struct6_create(int n)
{
printf("创建单链表：\n");
Struct6List *head, *node, *end; //定义头节点，普通节点，尾节点； 声明结构体变量第一种方式
head = (Struct6List*)malloc(sizeof(Struct6List)); // 申请头结点的内存
if (head == NULL) {
printf("分配内存失败！！\n");
exit(0);
}
//注意：尾部节点相当于普通节点最后一个节点 充当的是临时变量的效果
end = head; // 现在 end 和 head 地址一样
end -> score = n; // 头结点记录元素个数
for (int i = 0; i < n; ++i)
{
node = (Struct6List*)malloc(sizeof(Struct6List)); // 申请定普通节点的内存
node -> score = rand() % 101; // 取0~100的随机数
end -> next = node; // 头结点的下一个节点指向普通节点 或者 普通节点指向下一个普通节点
end = node; // end 变为普通节点
}
end->next = NULL; // 将最后一个普通节点 next置为零 该普通节点变为尾节点
return head;
}
// 增加指定节点
void Struct6_insert(Struct6List *h, int n)
{
int i, m;
Struct6List *node, *end, *tmp;
node = (Struct6List*)malloc(sizeof(Struct6List)); // 申请普通节点内存
if (node == NULL) {
printf("分配内存失败！！\n");
exit(0);
}
end = h;
node -> score = rand() % 101; // 给新增节点赋值
// 处理超出范围
if (n < 1) n = 1;
// 兼容范围小的(插入节点)
for (i = 1; i < n; ++i)
end = end -> next;
if (h->score < n) {
end = end -> next; // 在末尾添加节点 需要遍历完所有节点
node -> next = NULL; // 由于是末尾，需要变为尾部节点
end -> next = node; // 原先末尾节点连接到新增节点
m = h->score + 1; // 增加节点位置
} else {
tmp = end -> next; // 保存插入位置的节点
node -> next = tmp; // 新增节点连接插入位置节点
end -> next = node; // 插入位置前一个节点连接到新增节点
m = n; // 增加节点位置
}
++h->score; // 节点数量增加
printf("在第%d位置增加节点：\n", m);
}
// 删除指定节点
void Struct6_delete(Struct6List *h, int n)
{
struct Struct6_student *tmp, *end; // 声明结构体变量第二种方式
// 处理超出范围
if (h->score < n) n = h->score;
if (n < 1) n = 1;
printf("删除第%d位置节点\n", n);
end = h;
for (int i = n; i > 1; --i)
end = end -> next; // 找到需要删除节点的前一个节点
tmp = end -> next; // 保存需要删除的节点
// 如果删除最后一个节点，需要变为尾节点 否则 直接指向下一个节点
end -> next = h->score == n ? NULL : tmp ->next;
// 释放删除节点的内存
free(tmp);
tmp = NULL;
--h->score; // 节点数量减少
}
// 修改指定节点的值
void Struct6_update(Struct6List * h, int n)
{
// 处理超出范围
if (h->score < n) n = h->score;
if (n < 1) n = 1;
printf("修改第%d个节点的值：\n", n);
for (int i = n; i > 0; --i)
h = h -> next;
h -> score = rand() % 101;
}
// 先进先出 移出并获取结构体的第一个节点
Struct6List * Struct6_blpop(Struct6List *h)
{
Struct6List *tmp = h;
--h->score; // 节点数量减一
tmp = tmp->next;
printf("移出并获取第一节点：%d\n", tmp->score);
h -> next = tmp->next;
tmp -> next = NULL;
return tmp;
}
// 先进后出 移出并获取结构体的最后节点
Struct6List * Struct6_brpop(Struct6List *h)
{
Struct6List *tmp = h, *r;
--h->score; // 节点数量减一
// 得到倒数第二节点
for (int i = h->score; i > 0; --i)
tmp = tmp->next;
r = tmp->next; // 保存最后节点
tmp->next = NULL; // 倒数第二节点变为尾节点
printf("移出并获取最后节点：%d\n", r->score);
return r;
}
// 移出并获取结构体的指定节点
Struct6List * Struct6_bzpop(Struct6List *h, int n)
{
if (n > h->score || n < 1)
{
printf("节点不存在，返回头结点！！\n");
return h;
}
Struct6List *tmp = h, *z;
--h->score; // 节点数量减一
// 得到目标节点前一个
for (int i = 1; i < n; ++i)
tmp = tmp->next;
z = tmp->next; // 保存目标节点
tmp->next = z->next; // n-1节点 连接 n+1节点
z->next = NULL; // 消除连接
printf("移出并获取第%d节点：%d\n", n, z->score);
return z;
}
void main()
{
printf("Struct6:单链表的基本运用\n");
struct Struct6_student *h, *l, *r, *z; // 注意 switch不能声明结构体
int n;
char c;
printf("请输入需要创建的节点个数：");
scanf("%d", &n);
// 创建拥有指定节点个数的单链表
h = Struct6_create(n); // 得到头结点
Struct6_print(h); // 打印单链表
while (TRUE) {
printf("\n'i':在指定位置增加节点 'd':删除指定位置节点 'u':修改指定位置节点 'l':移出并获取第一节点 'r':移出并获取最后节点 'z':移出并获取指定节点 'q':退出操作\n");
printf("请输入需要执行得操作：");
getchar(); // 吃掉换行符
scanf("%c", &c);
switch (c)
{
case 'i':
printf("请输入需要增加的节点位置：");
getchar();
scanf("%d", &n);
// 增加指定单链表的值
Struct6_insert(h, n);
Struct6_print(h); // 打印单链表
break;
case 'd':
printf("请输入需要删除的节点位置：");
getchar();
scanf("%d", &n);
// 删除指定节点
Struct6_delete(h, n);
Struct6_print(h); // 打印单链表
break;
case 'u':
printf("请输入需要修改的节点位置：");
getchar();
scanf("%d", &n);
// 改变对应节点值
Struct6_update(h, n);
Struct6_print(h); // 打印单链表
break;
case 'l':
l = Struct6_blpop(h);
printf("移出并获取结构体的第一个节点：%d\n", l->score);
Struct6_print(h); // 打印单链表
break;
case 'r':
r = Struct6_brpop(h);
printf("移出并获取结构体的最后节点：%d\n", r->score);
Struct6_print(h); // 打印单链表
break;
case 'z':
printf("请输入需要移出并获取的节点位置：");
getchar();
scanf("%d", &n);
z = Struct6_bzpop(h, n);
printf("移出并获取结构体的第%d节点：%d\n", n, z->score);
Struct6_print(h); // 打印单链表
break;
case 'q':
return;
default:
printf("输入错误！请重新输入。\n");
break;
}
}
}
// 单链表的基本运用
