单链表的实现 | 附学生信息管理系统的实现

目录

1.前言：

2.单链表的相关概念：

2.1定义：

2.2形式：

2.3特点：

3.常见功能及代码 ：

3.1创建节点：

3.2头插：

3.3尾插：

3.4头删：

3.5尾删：

3.6插入（指定位置pos之前）

3.7插入（在指定位置pos之后）

3.8删除（指定位置pos前）

3.9删除（指定位置pos之后）

3.10打印链表：

3.11查找

3.12销毁链表：

4.总代码：

4.1 SList.h

4.2 SList.c

4.3 test.c

5.附：学生信息管理与信息系统：

6.总结：

---

1.前言：

今天，小邓儿带咱们来看看一个常见的数据结构——“单链表”。通过今天的学习，你将熟练地掌握单链表，还可以将其应用在学生信息管理系统中。废话不多说，咱们开始今天的探秘。

2.单链表的相关概念：

2.1定义：

单链表（Singly Linked List）是一种链式存储的线性数据结构，由一系列节点（Node）组成，每个节点包含两个部分：

• 数据域（Data）：存储实际的数据元素。
• 指针域（Next）：存储指向下一个节点的引用（或指针）。

2.2形式：

以整型数据为例：

2.3特点：

• 节点通过指针依次连接，形成链状结构。
• 最后一个节点的指针域为 null（或 None），表示链表的结束。
• 链表的大小是动态的，可以灵活地插入和删除节点。

3.常见功能及代码 ：

3.1创建节点：

3.2头插：

思路:

1.定义一个新节点newnode;

2.newnode的下一个结点指向头节点；

3.将newnode作为新的头节点。

代码：

3.3尾插：

思路：

1.判断该链表是否为空。若是空链表，同头插思路相同；

2.若是不为空。遍历链表，将最后一个节点的下一个节点，指向新节点。

代码：

3.4头删：

思路：

1.判空。若为空，返回NULL;

2.不为空，定义一个next指针（指向头节点下一个节点）；

3.将next作为新的头节点。

代码：

3.5尾删：

思路：

1.判空。若为空，返回NULL;

2.不为空，定义一个pre指针指向NULL,再定义一个ptail指针遍历链表；

3.当ptail的下一个节点不为空，将pre指向ptail所在位置，ptail继续遍历链表，直至ptail下一个指针为空；

4.此时，将pre的下一个指针指为空，并释放ptail指针空间。

代码：

3.6插入（指定位置pos之前）

思路：

1.判空。若为空，调用头插;

2.不为空，定义一个新节点newnode来存储要插入的数据；

3.在定义一个pre指针指向头节点（用来寻找*pos）；

4.找到pos后，将pre的下一个节点指向newnode节点，并将newnode的下一个节点指向pos;

代码：

3.7插入（在指定位置pos之后）

思路：

1.判空。若为空，调用头插;

2.不为空，定义一个新节点newnode来存储要插入的数据；

3.将newnode的下一个节点指向pos的下一个节点；

4.再将pos的下一个节点指向newnode.（注意：这里的3、4步骤不可以颠倒）

正常思路：

如果颠倒：（newnode的下一个节点，就不能指向原先4所在的节点。只能指向newnode节点）

代码：

3.8删除（指定位置pos前）

思路：

1.判断pos是否为头节点，是的话，头删;

2.不是头节点，定义一个pcur节点指向头节点；

3.用pcur来遍历链表，直至pcur的下一个节点是pos;

4.此时，将pcur的下一个节点指向pos的下一个节点，并释放pos节点的空间。

代码：

3.9删除（指定位置pos之后）

思路：

1.判断pos是否为头节点，是的话，头删;

2.不是头节点，定义一个pcur节点指向pos的下一个节点；

3.将pos的下一个节点指向pcur的下一个节点。

代码：

3.10打印链表：

代码：

3.11查找：

代码：

3.12销毁链表：

代码：

4.总代码：

4.1 SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
typedef struct SLNode
{SLDateType data;struct Node* next;
}Node;
Node* BuyNode(SLDateType X);
//打印
void SLPrintf(Node*plist);
//尾插
void SLPushBack(Node** plist, SLDateType X);
//头插
void SLPushFront(Node** plist, SLDateType X);
//尾删
void SLPopback(Node** plist);
//头删
void SLPopFront(Node** plist);
//查找
Node* SLSearch(Node* plist, SLDateType X);
//指定位置前插入
void SLInsert(Node** plist, Node*pos,SLDateType X);
//指定位置之后插入
void SLInsertAfter(Node** plist, Node* pos, SLDateType X);
//删除指定位置的数据
void SLErase(Node** plist, Node* pos);
//删除指定节点后的数据
void SLEraseAfter( Node**plist,Node* pos);
//销毁
void SLDestory(Node** plist);

4.2 SList.c

#include"SList.h"
Node* BuyNode(SLDateType X)
{Node* newnode = (Node*)malloc(sizeof(SLDateType));if (newnode == NULL){perror("malloc fail\n");return NULL;}newnode->data = X;newnode->next = NULL;return newnode;
}
void SLPrintf(Node* plist)
{if(plist==NULL){exit(1);}Node* pcur = plist;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
void SLPushBack(Node** phead, SLDateType X)
{assert(phead);Node* newnode = BuyNode(X);if (*phead == NULL){*phead = newnode;}else{Node* ptail = *phead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}
void SLPushFront(Node** phead, SLDateType X)
{assert(phead);Node* newnode = BuyNode(X);newnode->next = *phead;*phead = newnode;
}
void SLPopback(Node** plist)
{assert(plist&&*plist);if ((plist && *plist) == NULL){free(*plist);*plist= NULL;}else{Node* pre = NULL;Node* ptail =* plist;while (ptail->next){pre = ptail;ptail = ptail->next;}pre->next = NULL;free(ptail);ptail = NULL;}
}
void SLPopFront(Node** plist)
{assert(plist && *plist);if ((plist && *plist) == NULL){free(*plist);*plist = NULL;}else{Node*next=(*plist)->next;free(*plist);*plist = next;}
}
Node* SLSearch(Node* plist, SLDateType X)
{assert(plist);Node* pcur = plist;while (pcur->data != X){pcur = pcur->next;}if (pcur->next){return pcur;}else return NULL;
}
void SLInsert(Node**plist,Node*pos, SLDateType X)
{assert(plist && pos);if (pos == plist){SLPushFront;}else{Node* newnode=BuyNode(X);Node* pre = *plist;while (pre->next != pos){pre = pre->next;}pre->next = newnode;newnode->next= pos;}
}
void SLInsertAfter(Node** plist, Node* pos, SLDateType X)
{assert(plist && pos);if (pos == plist){SLPushFront;}else{Node* newnode = BuyNode(X);newnode->next = pos->next;pos->next = newnode;}
}
void SLErase(Node** plist, Node* pos)
{assert(plist && pos);if (pos == *plist){SLPopFront(&plist);}else {Node* pcur = *plist;while((pcur->next) != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}
void SLEraseAfter(Node**plist, Node* pos)
{assert( pos);Node* pcur = pos->next;pos->next = pcur->next;free(pcur);pcur = NULL;
}
void SLDestory(Node** plist)
{Node* pcur = *plist;while (pcur){Node* pre = pcur->next;free(pcur);pcur = pre;}*plist = NULL;
}

4.3 test.c

#include"SList.h"
void test1()
{Node* p1 = (Node*)malloc(sizeof(Node));Node* p2 = (Node*)malloc(sizeof(Node));Node* p3 = (Node*)malloc(sizeof(Node));assert(p1&&p2&&p3);if (p1 == NULL){return 0;}p1->data = 1;p2->data = 2;p3->data = 3;p1->next = p2;p2->next = p3;p3->next = NULL;Node* plist = p1;SLPrintf(plist);
}
void test2()
{Node* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);//SLPrintf(plist);SLPushFront(&plist, 5);SLPrintf(plist);SLPopback(&plist);SLPrintf(plist);SLPopFront(&plist);SLPrintf(plist);Node* P = SLSearch(plist, 2);if (P){printf("找到%d了\n", P->data);}else printf("未找到\n");SLInsert(&plist, P, 6);//SLPrintf(plist);SLInsertAfter(&plist, P, 7);SLPrintf(plist);SLErase(&plist, P);SLPrintf(plist);SLEraseAfter(&plist,7);SLPrintf(plist);SLDestory(plist);
}int main()
{test2();return 0;
}

5.附：学生信息管理与信息系统：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>typedef struct Student {char id[10];char name[20];float score;
} Stu;typedef struct LinkNode {Stu* data;struct LinkNode* next;
} Node;// 初始化单链表
void InitList(Node** L) {*L = (Node*)malloc(sizeof(Node));if (*L == NULL) {perror("malloc failed!\n");exit(1);}(*L)->next = NULL;(*L)->data = NULL;
}// 创建新结点
Node* CreateNode(Stu* x) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc failed!\n");exit(1);}newNode->data = x;newNode->next = NULL;return newNode;
}// 插入记录(尾插）
void Insert(Node** L, Stu* x) {Node* newNode = CreateNode(x);if (*L == NULL) {*L = newNode;}else {Node* ptail = *L;while (ptail->next) {ptail = ptail->next;}ptail->next = newNode;}
}// 查找功能1:按姓名查找
Node* SearchByName(Node* L, char* name) {Node* pcur = L->next;while (pcur) {if (strcmp(pcur->data->name, name) == 0) {return pcur;}pcur = pcur->next;}return NULL;
}// 查找功能2:按学号查找
Node* SearchByID(Node* L, char* id) {Node* pcur = L->next;while (pcur) {if (strcmp(pcur->data->id, id) == 0) {return pcur;}pcur = pcur->next;}return NULL;
}// 删除功能：按学号删除记录
void Delete(Node** L, char* id) {Node* c = SearchByID(*L, id);if (c == NULL) {printf("未找到学号为 %s 的记录！\n", id);return;}Node* pre = *L;while (pre->next != c) {pre = pre->next;}pre->next = c->next;free(c->data);free(c);printf("删除成功！\n");
}// 修改功能：按学号修改记录
void Change(Node** L, char* id) {Node* c = SearchByID(*L, id);if (c == NULL) {printf("未找到学号为 %s 的记录！\n", id);return;}Stu* s = (Stu*)malloc(sizeof(Stu));if (s == NULL) {perror("malloc failed!\n");exit(1);}printf("请输入修改后的信息（学号 姓名 成绩）：\n");scanf("%s%s%f", s->id, s->name, &s->score);strcpy(c->data->id, s->id);strcpy(c->data->name, s->name);c->data->score = s->score;free(s);printf("修改成功！\n");
}// 输出所有记录
void DispList(Node* L) {Node* pcur = L->next;if (!pcur) {printf("链表为空，无记录可显示！\n");return;}printf("所有记录如下：\n");while (pcur) {printf("学号：%s，姓名：%s，成绩：%.2f\n",pcur->data->id, pcur->data->name, pcur->data->score);pcur = pcur->next;}
}// 销毁链表
void Destroy(Node** L) {Node* pcur = *L;while (pcur) {Node* temp = pcur;pcur = pcur->next;free(temp->data);free(temp);}*L = NULL;
}// 显示菜单
void show_screen() {printf("\n***************       功能选择     *****************\n");printf("*************** 1: 录入学生记录     ***************\n");printf("*************** 2: 添加学生记录     ***************\n");printf("*************** 3: 按学号删除记录   ***************\n");printf("*************** 4: 按学号修改记录   ***************\n");printf("*************** 5: 按姓名查找记录   ***************\n");printf("*************** 6: 显示所有记录     ***************\n");printf("*************** 7: 清屏             ***************\n");printf("*************** 8: 退出管理系统     ***************\n");
}int main() {Node* LinkStudent = NULL;InitList(&LinkStudent);while (1) {int choose;show_screen();printf("请选择：\n");scanf("%d", &choose);int c;while ((c = getchar()) != '\n' && c != EOF); // 清空scanf缓冲区switch (choose) {case 1: // 添加学生信息printf("请输入学生信息（学号 姓名 成绩），输入三次：\n");for (int i = 0; i < 3; i++) {Stu* s = (Stu*)malloc(sizeof(Stu));if (s == NULL) {perror("malloc failed!\n");exit(1);}scanf("%s%s%f", s->id, s->name, &s->score);Insert(&LinkStudent, s);}break;case 2: // 添加单条学生记录{Stu* s = (Stu*)malloc(sizeof(Stu));if (s == NULL) {perror("malloc failed!\n");exit(1);}printf("请输入学生信息（学号 姓名 成绩）：\n");scanf("%s%s%f", s->id, s->name, &s->score);Insert(&LinkStudent, s);}break;case 3: // 按学号删除记录{char id[10];printf("请输入要删除的学号：");scanf("%s", id);Delete(&LinkStudent, id);}break;case 4: // 按学号修改记录{char id[10];printf("请输入要修改的学号：");scanf("%s", id);Change(&LinkStudent, id);}break;case 5: // 按姓名查找记录{char name[20];printf("请输入要查找的姓名：");scanf("%s", name);Node* result = SearchByName(LinkStudent, name);if (result) {printf("找到记录：学号：%s，姓名：%s，成绩：%.2f\n",result->data->id, result->data->name, result->data->score);}else {printf("未找到姓名为 %s 的记录！\n", name);}}break;case 6: // 显示所有记录DispList(LinkStudent);break;case 7: // 清屏system("cls");break;case 8: // 退出管理系统Destroy(&LinkStudent);printf("退出系统，拜拜！\n");return 0;default: // 输入错误printf("无效选项，请重新输入！\n");break;}}return 0;
}

6.总结：

小邓儿的本次学生信息管理系统，在插入、删除部分只用了一种方式，不是很完善，咱们可以用自行思考，看看怎么样加入其他方式，使得系统选择更多O(∩_∩)O

好了，今天的分享就到这里儿。别忘了点赞收藏😄😄😄