数据结构考研分类复习真题 第二章 答案[54]

．[题目分析] 本题所用数据结构是静态双向链表其结构定义为

typedef struct node

{char data[maxsize];∥用户姓名maxsize是可能达到的用户名的最大长度

int LlinkRlink;∥前向后向链其值为乘客数组下标值

}unode;

unode user[max];∥max是可能达到的最多客户数

设av是可用数组空间的最小下标当有客户要订票时将其姓名写入该单元的data域然后在静态链表中查找其插入位置将该乘客姓名与链表中第一个乘客姓名比较根据大于或小于第一个乘客姓名而决定沿第一个乘客的右链或左链去继续查找直到找到合适位置插入之

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

{scanf(%ss);∥s是字符数组存放乘客姓名

strcopy(user[av]datas);

p=;∥p为工作指针(下标)

if(strcmp(user[p]datas)<)∥沿右链查找

{while (p!= && strcmp(user[p]datas)<){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!= && strcmp(user[p]datas)>){pre=p; p=user[p]Llink; }

user[av]Rlink=pre;user[av]Llink=p;∥将新乘客链入表中

user[pre]Llink=av; user[p]Rlink=av;

}

}∥算法结束

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

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []