实用数据结构基础参考答案

B.线性顺序表中包含的元素个数不是任意的

C.线性表中的每个结点都有且仅有一个直接前趋和一个直接后继 D.存在这样的线性表,即表中没有任何结点 (20)在( B )的运算中,使用顺序表比链表好。

A.插入 B.根据序号查找 C. 删除 D.根据元素查找

四.分析下述算法的功能

(1) ListNode *Demo1(LinkList L,ListNode *p)

{ // L是有头结点的单链表

ListNode *q=L->next;

While (q && q->next!=p)

q=q->next;

if (q)

return q;

else

Error(“*p not in L”);

}

(2) void Demo2(ListNode *p,ListNode *q)

{ // p,*q是链表中的两个结点

DataType temp;

temp=p->data;

p->data=q->data;

q->data=temp;

}

解:

(1)返回结点*p的直接前趋结点地址。 (2)交换结点*p和结点*q(p和q的值不变)。

五. 程序填空

(1)已知线性表中的元素是无序的,并以带表头结点的单链表作存储。试写一算法,删除表中所有大于min,小于max的元素,试完成下列程序填空。

Void delete (lklist head; datatype min, max) { q=head->next; while (p!=NULL)

{ if ((p->data<=min ) | | ( p->data>=max ) {q=p; p= p->next ; }

else

9

{ q->next= p->next ;

delete (p) ; p= q->next ; } } }

(2)在带头结点head的单链表的结点a之后插入新元素x,试完成下列程序填空。

struct node { elemtype data; node *next; };

void lkinsert (node *head, elemtype x) { node *s, *p; s= new node ; s->data= x ; p=head->next;

while (p!=NULL) && ( p->data!=a )

____p=p->next ; if (p==NULL)

cout<< \不存在结点a! \ else {_____s->next=p->next______;

___ p->next=s __________; }

}

六.算法设计题

(1)写一个对单循环链表进行遍历(打印每个结点的值)的算法,已知链表中任意结点的地址为P 。 解:

void Show(ListNode *P) { ListNode *t=P; do { printf(\ t=t->rear; }

while (t!=P); }

(2) 对给定的带头结点的单链表L,编写一个删除L中值为x的结点的直接前趋结点的

算法。

解:

void delete(ListNode *L)

10

{

ListNode *p=L,*q;

if(L->next->data==X) {

printf(“值为x的结点是第一个结点,没有直接前趋结点可以删除”); return; }

For(p->next->data!=X;q=p;p=p->next);// 删除指针p所指向的结点

q->next=p->next; delete p;

}

(3) 已知一个单向链表,编写一个函数从单链表中删除自第i个结点起的k个结点。 解:

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;

} } }

(4) 有一个单向链表(不同结点的数据域值可能相同),其头指针为head,编写一个函

数计算值域为x的结点个数。

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

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

11

p=head;

while(p!=NULL) { if(p->data==x)

n++; p=p->next; }

return(n); }

(5)有两个循环单向链表,链头指针分别为head1和head2,编写一个函数将链表head1链接到链表head2,链接后的链表仍是循环链表。

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

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); }

12

联系客服:779662525#qq.com(#替换为@)