初识数据结构：链表实现图书信息管理系统（C语言，仅供参考）

2023-03-30

data next 结点

目录1.创建表结构2.创建表3.打印链表4.查找功能的实现 5.插入功能的实现6.删除功能的实现 7.修改功能的实现   8.计数功能的实现  9.排序功能的实现 10.封装图书信息管理系统1.创建表结构创建书籍信息结构

1.创建表结构

2.创建表

3.打印链表

4.查找功能的实现

5.插入功能的实现

6.删除功能的实现

7.修改功能的实现

8.计数功能的实现

9.排序功能的实现

10.封装图书信息管理系统

1.创建表结构

创建书籍信息结构体和每个结点的结构体


struct Book
{
char id[20];//ISBN
char name[50];//书名
int price;//定价
};//创建书籍信息结构体
typedef struct LNode {
struct Book data;//书籍信息结构体
struct LNode* next;//指向下一元素指针
}LNode,*LinkList;

2.创建表

前插法创建单链表，建立n个元素的链表，正序输入书籍信息，返回头指针L


//创建链表
LinkList CreateList_H(int n) {
LinkList L = (LinkList)malloc(sizeof(LNode));//建立一个带头结点的空链表
    int i;
    LinkList r;
if (L == NULL)//判断是否建立成功
{
perror("CreateList_H");
return 0;
}
L->next = NULL;
r = L;//尾指正r指向头结点
i = 0;
for ( i = 0; i < n; i++)
{
LinkList p = (LinkList)malloc(sizeof(LNode));//生成新节点p
if (p == NULL)//判断是否建立成功
{
perror("CreateList_H");
return 0;
}
scanf("%s %s %d", p->data.id, p->data.name, &(p->data.price));//输入书籍信息赋给p结点上的data
r->next = p;//r指向的结点next域指向p
p->next = NULL;//p结点next域指针赋为空指针
r = p;//r指针指向新节点
}
return L;//返回头指针L
}

正序输入数据创建表

3.打印链表

为方便测试打印链表中所有元素


//打印链表
void printList(LinkList L){
LinkList p = L->next;//创建p指针指向L的首元结点
printf("\n");
while (p!=NULL)//遍历链表，直到p为空
{
printf("%s %s %d\n", p->data.id, p->data.name, p->data.price);
p = p->next;
}
}

4.查找功能的实现

输入要查找书籍名，返回书籍的ISBN


//链表查找
LinkList LocateElem(LinkList L,char* find) {
LinkList p = L->next;//创建p指针指向L的首元结点
while (NULL != p && strcmp(p->data.name,find))//向后扫描，直到p为空或p指向数据域的书籍名相等
{
p = p->next;//p指向下一个结点
}
return p;//查找成功返回书籍地址，查找失败返会NULL
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
printList(L);//打印链表
printf("输入要查找的书名：");
char find_name[20] = "0";
scanf("%s", find_name);
LinkList s = LocateElem(L, find_name);//查找书名为find_name的书籍，储存查找函数返回的地址
    if（s == NULL）//判断是否查找成功
    {
        printf("查找失败");
        return 0;
    }
printf(s->data.id);//打印返回书籍地址处的ISBN
return 0;
}

运行结果：

5.插入功能的实现

传入链表L和准备插入的位置n

要在第n个位置插入时，要找到第n-1个位置结点，插入在第n-1个位置结点后面。


//链表插入
void LinkInsert(LinkList L,int n) {
LinkList p = L;
int i = 0;
for (i = 0; i < n-1; i++)//查找第n-1个结点
{
if (p == NULL)//如果p为空，则跳出循环
break;
p = p->next;
}
if (p == NULL)
{
printf("插入失败");//若p为空，提示插入失败
return;
}
else
{
LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点s
printf("输入要插入的书籍信息：");
scanf("%s %s %d", s->data.id, s->data.name, &(s->data.price));//在s结点data域存储书籍信息
s->next = p->next;
p->next = s;
}
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
printList(L);//打印查看插入前效果
LinkInsert(L, 4);//在链表L中第4个位置插入新结点
printList(L);//打印查看插入后效果
return 0;
}

运行结果：

6.删除功能的实现

删除第n个结点，首先找到第n-1个结点，临时保存第n个结点地址，让第n-1个结点的next域指向第n+1个结点，再释放第n个结点的空间。


//结点删除
void ListDelete(LinkList L, int n) {
LinkList p = L;
int i = 0;
for (i = 0; i < n-1; i++)//查找第n-1个结点
{
if (p->next == NULL)//如果p的next域为空，则跳出循环
break;
p = p->next;
}
if (p->next == NULL)
{
printf("删除失败");//若p为空，提示删除失败
return;
}
else
{
LinkList q = p->next;//保存被删结点地址以备释放
p->next = p->next->next;//p的next域指向被删地址的后一个地址
free(q);//释放q结点空间
        q = NULL;//把q置为空指针
printf("删除成功");
return;
}
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
printList(L);//打印查看删除前效果
ListDelete(L, 5);//删除链表L中第5个元素
printList(L);//打印查看删除后效果
return 0;
}

运行结果：

7.修改功能的实现

调用查找函数查找要修改的结点后修改


//修改链表
void modifyList(LinkList L) {
char find_name[50] = "0";
printf("输入要修改结点的书籍名：\n");
scanf("%s", find_name);
LinkList p = LocateElem(L, find_name);//调用查找函数，返回地址存储在p指针中
if (p == NULL)//判断查找是否成功
{
printf("修改失败，查找未完成\n");
return;
}
printf("输入修改书籍信息：\n");
scanf("%s %s %d", p->data.id, p->data.name, &(p->data.price));//修改书籍信息
printf("修改成功");
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
printList(L);//打印链表
modifyList(L);//修改
printList(L);//打印链表
return 0;
}

运行结果：

8.计数功能的实现


//计数
int countList(LinkList L) {
LinkList p = L->next;//创建p指针指向L的首元结点
int count = 0;//创建count计数
while (p != NULL)//遍历链表，直到p为空
{
count++;
p = p->next;
}
return count;//返回count
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
//printList(L);//打印链表
int count = countList(L);//返回元素个数
printf("链表元素个数为%d\n", count);
//printList(L);//打印链表
return 0;
}

运行结果：

9.排序功能的实现

使用冒泡排序的方法，比较两个结点data.id域的字符串，详情可查看冒泡排序（超详细）

函数strcmp的功能是比较两个字符串的大小。也就是把两个字符串从首字符开始逐个字符的进行比较，直到某个字符不相同或者其中一个字符串比较完毕才停止比较。字符的比较为ASCII码的比较。


//排序链表
void sortList(LinkList L) {
int count = countList(L);//调用计数函数计算链表元素个数n
int i = 0;
for (i = 0; i < count - 1; i++)//外层循环，遍历n-1个元素
{
int num = count - 1 - i;//记录内层循环所需次数
LinkList p = L->next;//令p指向L的首元结点
LinkList q = p->next;//令q指向p的下一个结点
LinkList tail = L;//L储存p的前一个结点
while (num--)//内层循环
{
if (strcmp((p->data.id), (q->data.id)) > 0)//调用strcmp函数比较p结点和q结点的data.id域内的字符串
{
//交换p结点和q结点
p->next = q->next;
q->next = p;
tail->next = q;
}
tail = tail->next;//tail指向下一结点
p = tail->next;//p指向tail的下一结点
q = p->next;//q指向p的下一结点
}
}
printf("排序完成!\n");
}

测试：


int main() {
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
printList(L);//打印链表
sortList(L);//排序
printList(L);//打印链表
return 0;
}

运行结果：

10.封装图书信息管理系统


void menu()
{
printf("********************************\n");
printf("*****   1.打印    2.查找   *****\n");
printf("*****   3.插入    4.删除   *****\n");
printf("*****   5.修改    6.计数   *****\n");
printf("*****   7.排序    0.退出   *****\n");
printf("********************************\n");
}
int main()
{
LinkList L = CreateList_H(10);//建立n个元素的链表，正序输入书籍信息，返回头指针L
int input = 0;//储存输入的值
int n = 0;
do
{
menu();//打印菜单
printf("请选择:>");
scanf("%d", &input);
switch (input)
{
case 1:
printf("打印：\n");
printList(L);//打印链表
break;
case 2:
printf(""); printf("输入要查找的书名：");
char find_name[20] = "0";
scanf("%s", find_name);
LinkList s = LocateElem(L, find_name);//查找书名为find_name的书籍，储存查找函数返回的地址
if(s == NULL)//判断是否查找成功
{
printf("查找失败");
return 0;
}
printf(s->data.id);//打印返回书籍地址处的ISBN
printf("\n");
break;
case 3:
printf("输入要插入的位置：");
scanf("%d", &n);
LinkInsert(L, n);//在链表L中第4个位置插入新结点
break;
case 4:
printf("输入要删除的位置：");
scanf("%d", &n);
ListDelete(L, n);//删除链表L中第5个元素
break;
case 5:
modifyList(L);//修改
break;
case 6: 
{
int count = countList(L);//返回元素个数
printf("链表元素个数为%d\n", count);
break;
}
case 7:
sortList(L);//排序
break;
case 0:
printf("退出程序\n");
break;
default:
printf("输入错误，请重新选择:\n");
break;
}
} while (input);//输入值为0时退出
return 0;
}