用链表实现学生信息管理。这里放一下有哪些文件。
下面是具体代码实现。
SList.h文件
#pragma once防止库函数的重复引用,因为库函数会在预编译的时候在程序中展开,会增大程序的体积。
通过typedef对数据重命名,之后需要修改数据就十分方便。并且其他函数不需要太多的改动。
需要注意的是,这里结构体传的是指针,减少没必要的内存消耗。
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct student { char name[20]; char sex[5]; int sno; int age; }SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SListNode; //动态申请一个节点 SListNode* BuySListNode(SLTDataType* data); //单链表打印 void SListPrint(SListNode* plist); //创建单链表 //SListNode* CreateSListNode(int x); //单链表销毁 void SListDestroy(SListNode** pplist); //尾插尾删 void SListPushBack(SListNode** pplist, SLTDataType* x); void SListPopBack(SListNode** pplist); //头插头删 void SListPushFront(SListNode** pplist, SLTDataType* x); void SListPopFront(SListNode** pplist); //查找 SListNode* SlistFind(SListNode* pos, int sno); //在pos位置插入删除 void SListInsertAfter(SListNode* pos, SLTDataType* x); void SListEraseAfter(SListNode* pos);
main.c文件
因为重点在于数据结构链表的使用,所以直接给定一些数据,就不进行重复繁琐的数据输入工作了。
#include "SList.h" void testSList() { SLTDataType stu1 = { "张三", "男", 110701, 22 }; SLTDataType stu2 = { "李四", "男", 110702, 21 }; SLTDataType stu3 = { "王五", "女", 110703, 23 }; SLTDataType stu4 = { "赵六", "女", 110704, 22 }; SLTDataType stu5 = { "周七", "男", 110705, 23 }; SListNode* plist = NULL; SListPushBack(&plist, &stu1); SListPushBack(&plist, &stu2); SListPushBack(&plist, &stu3); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPushFront(&plist, &stu4); SListPushFront(&plist, &stu5); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListNode* node = SlistFind(plist, 110701); printf("%s %d %s %d\n", node->data.name, node->data.sno, node->data.sex, node->data.age); SListInsertAfter(node, &stu3); SListPrint(plist); SListEraseAfter(node); SListPrint(plist); SListDestroy(&plist); } int main() { testSList(); return 0; }
SList.c文件
打印函数的实现,如果链表中的数据类型发生了改变,其他功能函数基本上不需要有什么变化, 打印函数对应修改一下就行了,毕竟打印需要涉及到具体的数据问题了。
void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%s %d %s %d\n", cur->data.name, cur->data.sno, cur->data.sex, cur->data.age); cur = cur->next; } printf("NULL\n"); }
动态申请一个节点,链表不像顺序表。链表在逻辑上是连续的,但是在空间上不一定是连续的。并且一个节点存储一个数据,所以只需要按需开辟空间节点就可以了,没有必要通过初始化来申请一定的空间。
SListNode* BuySListNode(SLTDataType* data) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = *data; newnode->next = NULL; return newnode; }
链表的销毁,链表的节点也是采用动态开辟空间的方式开辟的,所以也需要释放空间,否则会造成内存泄露。因为每个节点都是单独开辟的空间,所以需要针对每一个节点进行释放。从第一个节点开始,一个一个的释放掉,然后把指针移动到下一个节点。直到最后一个空间释放掉,然后返回一个空指针。
void SListDestroy(SListNode** pplist) { SListNode* cur = *pplist; while (cur) { SListNode* next = cur->next; free(cur); cur = next; } *pplist = NULL; }
尾插尾删的功能实现。每一次尾插都需要开辟一个链表节点,这也是为什么开辟节点需要单独写一个函数的原因,因为还有头插和在pos位置插入。在插入之前我们需要检查一下这个链表指针是否是空值,如果是空值则说明,这个数据是第一个数据,开辟的节点空间也是第一个节点,就返回这个节点。如果不是空值则说明这个链表是有值的,我们需要找到当前链表的最后一个节点,然后把数据的节点插入到最后一个节点后面。
尾删则需要找到链表的最后一个节点,释放掉这块空间,然后把倒数第二个节点的next指针置为空。如果不把最后一个节点释放掉也会造成内存泄露。
void SListPushBack(SListNode** pplist, SLTDataType* x) { SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* ptail = *pplist; while (ptail->next != NULL) { ptail = ptail->next; } ptail->next = newnode; } } void SListPopBack(SListNode** pplist) { assert(*pplist); SListNode* ptail = *pplist; while (ptail->next->next != NULL) { ptail = ptail->next; } free(ptail->next); ptail->next = NULL; }
头插头删的函数实现,实现与尾插尾删相似。不过头插时不需要遍历找到最后一个节点,然后进行插入。只需要把新开辟节点的next指针指向当前链表的头结点,然后把新开辟的节点置为头结点就行了。
头删就更简单了,释放掉头结点的空间,然后把第二个节点置为头结点就行了。
void SListPushFront(SListNode** pplist, SLTDataType* x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* next = (*pplist)->next; free(*pplist); *pplist = next; }
在pos插入或者删除数据,这组函数的功能实际上是包括头插头删、尾插尾删的,可以用这组函数分别头插头删、尾插尾删。
void SListInsertAfter(SListNode* pos, SLTDataType* x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(SListNode* pos) { assert(pos); SListNode* cur = pos->next->next; pos->next = cur; }
查找有多种方式,如顺序查找、二分查找这些,也可以按学号、姓名、年龄这些的来查找,我这里只是写了一个按学号进行的顺序查找。
SListNode* SlistFind(SListNode* pos, int sno) { SListNode* cur = pos; while (cur) { if (cur->data.sno == sno) { return cur; } cur = cur->next; } return NULL; }