C语言-链表_基础

链表-基础

1. 数组

1.1 静态数组

例子:int nums[5] = {0};struct person ps[5];
缺点:1,无法修改地址2,无法动态定义长度3,占用内存过大或过小4,增删速度慢
优点数组的内存是连续开辟的,所以读取速度快

1.2 动态数组

例子:int *nums = (int *) calloc(5,sizeof(int));struct person *ps = (struct person *)calloc(5,sizeof(struct person));
缺点:增删速度慢编写代码较为复杂
优点:读取效率高

2. 常用数据结构

1、数组结构:内存连续开辟

2、链表结构:离散开辟

3、树

4、二叉树(均衡二叉树,非均衡二叉树)

5、图

3. 链表结构

分类：

单链表：

• 一个节点只记录下一个节点的地址

双链表：

• 一个节点即记录下一个节点的地址，也记录上一个节点的地址

4. 设计节点

需求：将多个学员信息设计为链表

单链表节点设计：

typedef struct student
{//数据域char name[50];char sex[5];int num;double score;//指针域struct student *next;
}Stu;

双链表节点设计：

typedef truct student
{//数据域char name[50];char sex[5];int num;double score;//指针域struct student *next;struct student *head;
}Stu;

总结：

typedef struct 结构体名称
{//数据域//指针域
}别名;

5. 静态单链表

#include <stdio.h>
typedef struct student
{//数据域char name[50];char sex[5];int num;double score;//指针域struct student *next;
}Stu;
int main(int argc, char const *argv[])
{Stu s01 = {"张三", "男", 1, 99, NULL};Stu s02 = {"李四", "男", 2, 96, NULL};Stu s03 = {"王五", "女", 3, 97, NULL};Stu s04 = {"钱七", "男", 4, 93, NULL};Stu s05 = {"赵八", "女", 5, 97, NULL};Stu *head = &s01;   //将s01作为首节点s01.next = &s02;    //将s02设置为s01的下一个节点   s02.next = &s03;s03.next = &s04;s04.next = &s05;//链表的遍历//pd:当前链表的节点Stu *pd = head;while(pd != NULL){printf("%s %s %d %.2lf\n", pd->name, pd->sex, pd->num, pd->score);//下一个节点赋值给当前节点，为下一轮循环pd = pd->next;}return 0;
}

6. 动态单链表

动态开辟内存，存储结构体学生信息

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{//数据域char name[50];char sex[5];int age;//指针域struct student *next;
}Stu;
int main(int argc, char const *argv[])
{Stu *s01 = calloc(1,sizeof(Stu));strcpy(s01->name, "陈晴朗");strcpy(s01->sex, "男");s01->age = 18;Stu *s02 = calloc(1,sizeof(Stu));strcpy(s02->name, "李槐");strcpy(s02->sex, "男");s02->age = 8;Stu *s03 = calloc(1,sizeof(Stu));strcpy(s03->name, "李宝瓶");strcpy(s03->sex, "女");s03->age = 14;Stu *s04 = calloc(1,sizeof(Stu));strcpy(s04->name, "裴钱");strcpy(s04->sex, "女");s04->age = 12;Stu *s05 = calloc(1,sizeof(Stu));strcpy(s05->name, "崔东山");strcpy(s05->sex, "男");s05->age = 16;Stu *head = s01;   //将s01作为首节点s01->next = s02;    //将s02设置为s01的下一个节点   s02->next = s03;s03->next = s04;s04->next = s05;//链表的遍历//pd:当前链表的节点Stu *pd = head;while(pd != NULL){printf("%s\t%s\t%d\n", pd->name, pd->sex, pd->age);//下一个节点赋值给当前节点，为下一轮循环pd = pd->next;}return 0;
}
// 陈晴朗  男      18
// 李槐    男      8
// 李宝瓶  女      14
// 裴钱    女      12
// 崔东山  男      16

练习：学员管理系统

需求：

选项有:1,查询所有学员信息2,添加学员信息3,插入学员信息4,删除学员信息5,修改学员信息(作业)6,查找指定位置的学员(作业)7,退出程序(释放内存)

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{//数据域char name[30];char sex[10];int num;//指针域struct student *next;
}STU;
//记录链表首节点
STU *head = NULL;//查询函数(打印链表)
void print_link(STU *head)
{//定义一个节点作为当前节点STU *pd = head;while (pd != NULL){printf("姓名:%s\t性别:%s\t学号:%d\n",pd->name,pd->sex,pd->num);//获取下一个节点赋值给当前节点pd = pd->next;}printf("\n");
}//计算链表长度
int get_len(STU *head)
{int i = 0;STU *pd = head;while(pd != NULL){i++;pd = pd->next;}return i;
}//添加学员信息逻辑
/*添加新节点到连接尾部参数;head:链表的头节点stu:要添加的新节点返回值链表的头节点
*/
STU *add(STU *head, STU *stu)
{//如果传进来的学员信息为空，直接返回传进来的头结点if (stu == NULL){return head;}//判断链表首节点是否为空,为空表示此时链表还没有节点，直接将数据赋值给首结点if (head == NULL){head = stu;printf("添加成功\n\n");return head;}//查询最后一个节点，找到NULL的前一个节点//假设当前节点就是最后一个节点(即一个也没有)，此时首节点就是最后一个节点STU *lastNode = head;while(lastNode != NULL){//进循环，表示这不是最后一个节点，就判断他的下一个节点是否为空，为空直接跳出循环if (lastNode->next == NULL){break;}else{//此时表示他的下一个节点不是NULL，将它的下一个节点赋值给它lastNode = lastNode->next;}}//没有进循环表示lastNode就是当前链表的最后一个节点//此时就要将本次创建的节点添加到 原链表最后一个节点的后面lastNode->next = stu;printf("添加成功\n\n");return head;
}//尾部添加学员信息
STU *add_student(STU *head)
{//开辟一块堆内存空间赋值 结构体指针变量，用来存储学员信息(即stu指向这片堆内存)STU *stu = calloc(1,sizeof(STU));printf("请输入学员姓名\n");scanf("%s", stu->name);printf("请输入学员性别\n");scanf("%s", stu->sex);printf("请输入学员学号\n");scanf("%d", &stu->num);head = add(head, stu);return head;}//插入学员
STU *inster_student(STU *head)
{STU *stu = calloc(1,sizeof(STU));printf("请输入学员姓名\n");scanf("%s", stu->name);printf("请输入学员性别\n");scanf("%s", stu->sex);printf("请输入学员学号\n");scanf("%d", &stu->num);printf("请输入要插入学员的位置(从0开始)\n");int index = 0;scanf("%d", &index);//排除错误int len = get_len(head);if (index > len){//插入位置超过链表长度，插入链表末位head = add(head, stu);return head;}if (index < 0){printf("输入位置有误\n");return head;}//为0表示插入第一个位置if (index == 0){//将首节点位置变为下一个节点stu->next = head;//将新建的节点赋值给首节点head = stu;printf("添加成功\n");return head;}//寻找插入节点的前一个节点STU *pd = head;for (int i = 0; i < index - 1; i++){pd = pd->next;}stu->next = pd->next; //将前一个节点的原后一个节点赋值给新节点的下一个节点pd->next = stu;printf("添加成功\n\n");return head;
}//删除学员
STU *del_student(STU *head)
{printf("请输入要删除学员的位置(从0开始)\n");int index = 0;scanf("%d", &index);//排除错误int len = get_len(head);if (index > len || index < 0){printf("输入位置有误\n");return head;}//为0表示删除第一个位置if (index == 0){//将首节点的下一个节点变为首节点head = head->next;printf("删除成功\n");return head;}STU *pd1 = head, *pd2;int i = 0;while (i < index){pd2 = pd1;pd1 = pd1->next;i++;}if (pd1 != NULL){pd2->next = pd1->next;}printf("删除成功\n");return head;
}//修改学员
STU *update_student(STU *head)
{STU *stu = calloc(1,sizeof(STU));printf("请输入要修改学员姓名\n");scanf("%s", stu->name);printf("请输入要修改学员性别\n");scanf("%s", stu->sex);printf("请输入要修改学员学号\n");scanf("%d", &stu->num);printf("请输入要修改学员的位置(从0开始)\n");int index = 0;scanf("%d", &index);//排除错误int len = get_len(head);if (index > len || index < 0){printf("输入位置有误\n");return head;}//为0表示修改第一个位置if (index == 0){//将新节点的next指向原首节点的下一个节点stu->next = head->next;printf("修改成功\n");return head;}//不为0int i = 0;//定义两个指针变量记录当前节点和上一个节点STU *pd1 = head, *pd2;while (i < index){pd2 = pd1;pd1 = pd1->next;i++;}pd2->next = stu;stu->next = pd1->next;printf("修改成功\n");return head;
}//查询指定学员位置
STU *find_student(STU *head)
{printf("请输入要查找学员的位置(从0开始)\n");int index = 0;scanf("%d", &index);//排除错误int len = get_len(head);if (index > len || index < 0){printf("输入位置有误\n");return head;}STU *pd = head, *pd1;//为0表示查找的是第一个学员if (index == 0){//直接打印首节点printf("姓名:%s\t性别:%s\t学号:%d\n\n",pd->name,pd->sex,pd->num);return head;}//不为0，寻找当前节点int i = 0;while (i < index){pd1 = pd;pd = pd->next;i++;}printf("姓名:%s\t性别:%s\t学号:%d\n\n",pd->name,pd->sex,pd->num);return head;
}//菜单函数
void my_menu(int tag)
{switch (tag){case 1:print_link(head);break;case 2:head = add_student(head);break;case 3:head = inster_student(head);break;case 4:head = del_student(head);break;case 5:head = update_student(head);break;case 6:head = find_student(head);break;default:printf("输入有误, 请重新输入\n\n");break;}
}//释放内存
void free_link(STU *head)
{STU *pd = head;while (pd != NULL){//记录其下一个节点STU *next = pd->next;//释放当前节点free(pd);//更换当前节点pd = next;}}int main(int argc, char const *argv[])
{while (1){printf("1,查询所有学员信息\n2,添加学员信息\n3,插入学员信息\n4,删除学员信息\n5,修改学员信息\n6,查找指定位置的学员\n7,退出程序\n\n");printf("请输入本次操作的选项（输入对应数字）\n");int tag = 0;scanf("%d", &tag);if (tag != 7){my_menu(tag);}else{free_link(head);printf("欢迎下次光临!\n");break;}}return 0;
}