第 15 题

if n < 2:            #语句1
    return b

当前待处理部分不足2项时，不需要再比较相邻元素，直接返回列表。这是递归的终止条件。

for i in range(n - 1):
    if b[i][3] < b[i + 1][3]:
        b[i], b[i + 1] = b[i + 1], b[i]

i从0增至n−2，逐对比较相邻影片；若左侧得分更低，就交换整条影片记录。每次比较后，较低得分留在右侧，继续参与下一次比较。因此一趟结束时，前n项中的最低得分被送到下标n−1的位置。

return fsort(b, n - 1)

本趟已确定末项的位置，递归只处理前n−1项，再将其中最低分送到该部分的末尾。如此逐步缩小范围，最终得到按综合得分从高到低排列的列表，各层直接返回递归所得列表。

lst = [[0,0,0,0,1]]          #lst[0][4]指向头节点
for i in range(1,row+1):
    lst.append([i,1,tot,tot,i+1])   #构造链表，初始化每排可选座位区间
lst[-1][4] = -1

主程序用列表模拟链表，每个区间结点依次存储[排数，起始座位号，终止座位号，可选座位数，后继下标]。lst[0]是表头入口记录，lst[0][4]保存首个有效区间的下标；各结点下标4处保存后继下标，−1表示没有后继。初始化时，每排对应一个[1,tot]区间，各排依次连接。区间的逻辑顺序由这些链接决定。

for info in data:
    if info[3] == "购票":
        order_seat(info[1],info[2],lst)
    else:
        add_seat(info[1],info[2],lst)

data已按时间升序排列，程序依次处理购票、退票事件。购票时将info[1]的座位号和info[2]的排号传入order_seat，因此函数参数seat表示待购座位号，row表示本次购票的排号；主程序初始化时的row表示影厅总排数。

pre = 0
p = lst[pre][4]
while p != -1 and lst[p][0] != row:
    pre = p
    p = lst[p][4]

p从首个有效区间开始，沿lst[p][4]保存的后继下标查找。每轮先令pre = p，再令p = lst[p][4]，使pre跟在p之前，保存当前结点的前驱下标。循环遇到目标排的第一个区间时停止。

while p != -1 and lst[p][0] == row:
    ...
    pre = p
    p = lst[p][4]

在目标排内依次检查区间，根据seat位于区间的哪个位置选择处理分支。末尾沿当前结点的后继继续扫描，直到到达链尾或进入其它排。一次购票只会落在一个有效区间中。

空①所在分支对应区间中只有一个座位且该座位被购买的情况，需要从有效链表中删除当前结点。lst[pre][4]保存前驱的后继下标，lst[p][4]保存当前结点的后继下标；让前驱直接连接当前结点的后继，填写：

lst[pre][4] = lst[p][4]

删除首个有效结点时pre为0，这一语句更新表头入口；删除链尾时，原后继为−1，这一语句使前驱成为链尾。这里只修改链接，保留lst中的存储位置，避免其他结点下标改变。

该分支保留原起点，将终点改为seat−1且座位数减1，因此对应购买区间最右端的座位。单座位区间已由前面的分支处理，可同时写明本分支处理多个座位的情况：

seat == lst[p][2] and lst[p][3] > 1

执行到空③时，原结点的终点已变为seat−1，起点lst[p][1]不变，但座位数尚未更新。按“终点−起点＋1”，左半段的数量为(seat−1)−lst[p][1]＋1，因此填写：

lst[p][3] = seat - lst[p][1]

也可直接利用已更新的终点，写成lst[p][3] = lst[p][2] - lst[p][1] + 1。