【正确答案】正确答案：本题所用数据结构是静态双向链表，其结构定义为： typedef struct node {char data[maxsize]； ／／用户姓名，maxsize是可能达到的用户名的最大长度 int Llink，R1ink； ／／前向链、后向链，其值为乘客数组下标值，0表示尾 }unode； unode user[max]； ／／max是可能达到的最多客户数 设av是可用数组空间的下标(初始值是1)，当有客户要订票时，将其姓名写入该单元的data域，然后在静态链表中查找其插入位置。将该乘客姓名与链表中第一个乘客姓名比较，根据大于或小于第一个乘客姓名，而决定沿第一个乘客的右链或左链去继续查找，直到找到合适位置插入之。核心语句段如下： if(strcmp(user[p]．data，s)<0) ／／沿右链查找，S是乘客姓名 {while(p!=0&&strcmp(user[p]．data，s)<0) ／／p初值为1，p=0表示链表尾 {pre=p； p=user[p]．Rlink；) ／／pre是前驱，初值为0 user[av]．R1ink=p；user[av]．Llink=pre； ／／将乘客链入表中 if(pre!=0)user[pre]．R1ink=av； if(p!=0)user[p]．Llink=av； } else／／沿左链查找 (while(p!=o&&strcmp(user[p]．data，s)>o) {pre=p； p=user[p]．Llink；} user[av]．R1ink=pre ； user[av]．L1ink=p； ／／将乘客链入表中 if(pre!=0)user[pre]．L1ink=av； if(p!=0)user[p]．Rlink=av； } 本算法只讨论了乘客订票情况，未考虑乘客退票，也未考虑从空开始建立链表。增加乘客时也未考虑姓名相同者(实际系统姓名不能做主关键字)。完整系统应有(1)初始化。把整个数组空间初始化成双向静态链表，全部空间均是可利用空间。(2)申请空间。当有乘客购票时，要申请空间，直到无空间可用为止。(3)释放空间。当乘客退票时，将其空间收回。由于空间使用无优先级，故可将退票释放的空间作为下个可利用空间，链入可利用空间表中。