单元练习2_答案

void Del(SeqList *L,int i,int k) { int j=i-1+k;

for (j=0;j

{ L->data[i-1+j]=L->data[i+k-2+j]; if (i+k-2+j>L->last) break; } }

void Del(SeqList *L,int i,int k) { int j=i-1+k; if (j>L->last)

{ printf(“超出范围!”) return;

}

for (j=0;jlast-i;j++)

L->data[i-1+j]=L->data[i+k-2+j]; }

4．解：

void Del(node *head,int i,int k) {

node *p,*q; int j; if (i==1)

for (j=1;j<=k;j++) // 删除前k个元素 {

p=head; // p指向要删除的结点 head=head->next;

delete p; }

else {

p=head;

for (j=1;j<=i-2;j++)

p=p->next; // p指向要删除的结点的前一个结点 for (j=1;j<=k;j++) {

q=p->next; // q 指向要删除的结点 p->next=q->next; delete q;

}

}

} 佟198

5． 解：本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：

int counter(head) node *head； { node *p; int n=0; p=head；

while (p!=NULL)

{ if (p->data==x) n++；

p=p->next;

}

return(n); }

6．解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：

node *link (node *head1, *head2) { node *p,*q; p=head1;

while (p->next!=head1)

p=p->next;

q=head2;

while (q->next!=head2)

q=q->next;

p->next=head2; q->next=head1; return (head1); }

模拟考题

1．在顺序存储的线性表第i个位置插入新结点x，试完成下列程序填空。

typedef struct // 将data和last封装在一个结构体 { datatype data[MAXLEN]; // MAXLEN为线性表的最大长度 int last; }SeqList;

int InsList(SeqList *L,int i,datatype x) // 插入结点函数 { int j;

if (L->last= =MAXLEN-1)

{ cout<< \顺序表已满！\

if( i<1 || i>L->last+2 ) // 检查插入位置的正确性 { cout<< \位置出错！\

for (j=L->last; j>=i-1 ; j--) // 结点移动 L->data[j+1]=L->data[j] ;

L->Lata[i-1]= x ; // 新结点插入

L->last ++ ; （或L->last= L->last +1） return(1); }

2．一个带头指针的单链表，写出在值为x的结点之后插入m个结点的算法。 void insertm (lklist head; int m) { p=head->next;

while (p!=NULL) && ( p->data!=x ) p= p->next ; if ( p->data==x )

{ q=p->next;

for ( i=0; i< m ; i++ ) // 找到x，在其后插入m个结点 { s=new (node);

cin<< a ; // 输入待插入的值 s->data= a ; p->next=s; p=s; }

p->next=q; } } 3． 有两个循环单链表，头指针分别为head1和head2，下列函数是将链表head1链接到链表head2，链接后的链表仍然是循环链表，试完成下列程序填空。

（提示：先找到两链表的尾指针，再将第一个链表的尾指针与第二个链表的头结点链接起来）

node *link (node *head1, node *head2) { node *p, *q; p=head1;

while (p->next!=head1)

p= p->next ;

q= head2 ;

while (q->next !=head2 )

q=q->next;

p->next= head2 ; q->next= head1 ; return (head1); }