数据结构与实训
上QQ阅读APP看本书，新人免费读10天
设备和账号都新为新人
上一章目录下一章

2.5 典型题例

【例2-4】若长度为n的线性表采用顺序存储结构，在它的第i个位置插入元素之前，问首先要移动多少个表元素？如果是删除第i个位置的元素，则所需移动元素的个数又是多少？

【分析与解答】长度为n的线性表其元素序号为：1,2,3,…,i-1,i,…,n，所采用的是顺序存储结构，要在第i个位置插入元素，那么表中序号为i,…,n的元素就需要向后移动，移动后对应的序号为i+1,…,n+1，移动元素的个数为(n+1)-i，即n-i+1。如果是删除第i个位置的元素，则表中序号为i+1,…,n的元素就需要向前移动，移动后对应的序号为i,…,n-1，移动元素的个数为(n-1)-(i-1)，即n-i。

【例2-5】对长度为n的线性表，以下操作中，哪些在顺序表上实现比在链表上实现时间效率更高？

（1）输出第i（1≤i≤n）个元素的值；

（2）交换第1个元素和第2个元素的值；

（3）顺序输出这n个元素的值；

（4）输出与给定值x相等的元素在线性表中的序号。

【分析与解答】由顺序表和链表的存储特性可知：

（1）输出第i（1≤i≤n）个元素的值，顺序表的时间复杂度为O(1)，链表对应的时间复杂度为O(n)；

（2）交换第1个元素和第2个元素的值，顺序表的时间复杂度为O(1)，链表对应的时间复杂度为O(1)；

（3）顺序输出这n个元素的值，顺序表的时间复杂度为O(n)，链表对应的时间复杂度为O(n)；

（4）输出与给定值x相等的元素在线性表中的序号，顺序表的时间复杂度为O(n)，链表对应的时间复杂度为O(n)。

所以只有操作（1）在顺序表上实现比在链表上实现时间效率更高。

【例2-6】已知长度为n的线性表l采用顺序存储结构，写一算法，找出线性表中值最小的数据元素。

【分析与解答】先假设顺序表的第0个元素值最小，并将其保存在一临时变量min中，然后从线性表的第1个元素开始，依次将第1,2,…,n-1个元素的值与min的值进行比较。若某元素的值小于min的值，则将该元素的值存放在min中；若不小于min的值，则min的值保持不变。比较结束后，min中存放的就是线性表中值最小的数据元素。

ElementType Minelem(SeqList l)
{
    min=l.elem[0];
    for(i=1;i<l. listlength;i++)
       {
            if (min>l.elem[i])  min=l.elem[i];
       }
     return(min);
} /* minelem */

【例2-7】已知一带头结点的线性表，其头指针为head，写一算法，将该链表中值为value1的所有结点的值改为value2。

【分析与解答】从链表的第一个结点开始，依次判断当前的链结点是否满足条件（其数据域的值是否为value1），若满足，则对链结点数据域的值进行修改（改为value2），若不满足，则不修改。当前链结点判断并处理后，接着判断、处理其后继结点（新的当前链结点），直到链尾结点处理结束。

void v1tov2(LinkList h,ElementType value1,ElementType value2)
{
   p=h->next;
   while(p!=NULL)
   {
      if(p->data==value1) p->data=value2;
      p=p->next;
   }
} /* v1tov2 */

【例2-8】假设某航班（NF_B969N/2007.9.20 17:30:00）有N个座位，座位号依次为1,2,3,…,n，航班订票系统能够实现订票、退票，乘客登记表按照乘客姓名的字母顺序排列。图2-15所示是航班订票系统中所用到的链表结构，图2-15（a）所示是链表结点结构，图2-15（b）所示是已订座位链表，图2-15（c）所示是未订座位链表。

（1）试给出该系统中链表的数据类型定义。

（2）对已订座位链表、未订座位链表，问初始状态各有多少个结点？

（3）订票、退票算法对已订座位链表与未订座位链表如何操作？

图2-15 航班订票系统中所用到的链表结构

【分析与解答】由图2-15可知，已订座位链表与未订座位链表都是带头结点的单链表，已订座位链表的结点包括旅客姓名、身份证号、座位号与指向下一结点的指针，未订座位链表结点旅客姓名、身份证号为空，座位号（从小到大排列）与指向下一结点的指针不为空。

（1）数据类型（旅客信息）DataType定义如下。

#define MAXNAME旅客姓名最大长度
#define MAXID18 /*身份证号的长度*/
typedef struct
{  char name[MAXNAME];/*旅客姓名*/
   char id[MAXID];/*身份证号*/
} DataType;

单链表结点类型定义如下。

typedef struct node
{  DataType passenger;
   int number;    /*座位号*/
   struct node *next;
} DataNode;

指向单链表结点的指针类型定义如下。

typedef DataNode *Slink;

（2）用于描述航班座位状态的有两条单链表：未订座位与已订座位单链表。两条单链表的初始状态是已订座位链表是一个只有头结点的空链表，未订座位链表带头结点共有N+1个结点，每个结点只存放有座位信息。

（3）订票、退票的实现就是对已订座位与未订座位链表的插入与删除操作。订票算法删除未订座位链表中的第一个元素结点，输入的乘客信息存放在该结点中，并将其插入到按乘客姓名升序排列的已订座位链表中。退票算法根据输入的乘客身份证号，先在已订座位链表中查找，若找到相应结点，则将其摘下，并插入到按座位号升序排列的未订座位链表中。

上一章目录下一章