第2章 线 性 表

 

1．选择题

ADBAB  CBCBC  DCBAD  ACBDD

2．填空题

（1）线性，任何，栈顶，队尾，队首

（2）n-i+1

（3）n-i　

（4）先栈顶指针，后存入元素　

（5）先取出元素，后移动栈顶指针　

（6）前一个位置　

（7）先移动队首元素，后取出元素　

（8）n-1

3．问答题

（1）略。

（2）略。

（3）略。

（4）①this指向表的最后节点，②this指向空表。

4．上机操作题

（1）算法如下：

void Insert(SqList &L,ElemType x)

{

    int i=0,j;

    while(i<L->length && L.data[i]<x) i++;

    for(j=L->length-1;j>=i;j--)

         L.data[j+1]=L.data[j];

    L.data[i]=x;

    L->length++;

}

（2）算法如下：

void Delete(SqList &L,int i,int k)

{

    int j;

    if(i<L.length && i>=0 && i+k<=L.length)

    {   

        for(j=i+k;j<L.length;j++)

        L.data[j-k+1]=L.data[j];

        L.length-=k;

    }

    else

    printf("参数不正确\n");

}

（3）算法如下：

void Replace(SqList &L,ElemType x,ElemType y)

{

   int i;

   for(i=0;i<L.length;i++)

      if(L.data[i]==x)

        L.data[i]=y;

}

（4）算法如下：

pre=head;

current=head->next;

while(this!=head&&current->data>ptr->data)

{

   pre=current;

   current=current-next;

}

ptr->next=current;

pre->next=ptr;

（5）算法如下：

①先遍历A、B两个循环链表的尾部。

Atail=A;

while(Atail->next!=A)

  Atail=Atail->next

Btail=B;

while(Btail->next!=B)

  Btail=Btail->next

②接下来将两个字符串连起来，最后的链表以A为首。

Atail->next=B;

Btail->next=A;