数据结构 | 每日一练（72）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客 姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘 客表的算法。

正确答案

PS：||代表注释

1．[题目分析] 本题所用数据结构是静态双向链表，其结构定义为： typedef struct node {char data[maxsize]；∥用户姓名，maxsize是可能达到的用户名的大长度。

int Llink，Rlink；∥前向、后向链，其值为乘客数组下标值。 }unode； unode user[max]；∥max是可能达到的多客户数。 设av是可用数组空间的小下标，当有客户要订票时，将其姓名写入该单元的data域，然后在静态链表中 查找其插入位置。将该乘客姓名与链表中第一个乘客姓名比较，根据大于或小于第一个乘客姓名，而决定沿第 一个乘客的右链或左链去继续查找，直到找到合适位置插入之。

void Insert（unode user[max],int av）∥user是静态双向链表，表示飞机票订票系统，元素包含data、Llink和Rlink三个域，结点按来客姓名排序。 本算法处理任一乘客订票申请。

{scanf（“%s”，s）； ∥s是字符数组，存放乘客姓名。 strcopy（user[av].data，s）； p=1; ∥p为工作指针（下标）

if(strcmp（user[p].data，s）<0）∥沿右链查找 {while (p!=0 && strcmp（user[p].data，s）<0）{pre=p; p=user[p].Rlink; } user[av].Rlink=p；user[av].Llink=pre； ∥将新乘客链入表中 user[pre].Rlink=av; user[p].Llink=av; } else ∥沿左右链查找 {while (p!=0 && strcmp（user[p].data，s）>0）{pre=p; p=user[p].Llink; } user[av].Rlink=pre；user[av].Llink=p； ∥将新乘客链入表中 user[pre].Llink=av; user[p].Rlink=av; } }∥算法结束

[算法讨论] 本算法只讨论了乘客订票情况，未考虑乘客退票。也未考虑从空开始建立链表。增加乘客时也 未考虑姓名相同者（实际系统姓名不能做主关键字）。完整系统应有（1）初始化，把整个数组空间初始化成双 向静态链表，全部空间均是可利用空间。（2）申请空间。当有乘客购票时，要申请空间，直到无空间可用为 止。（3）释放空间。当乘客退票时，将其空间收回。由于空间使用无优先级，故可将退票释放的空间作为下个 可利用空间，链入可利用空间表中。