数据结构（第二版）习题答案第3章

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p->next ; return p;

（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以

（5）在一个具有 n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间 复杂度是（ B ）。

A．O(1) B．O(n) C．O(n) D．O(nlogn)

（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队 尾结点，则在进行删除操作时（ D ）。

A．仅修改队头指针 B．仅修改队尾指针 C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改 （7）若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（ B ）。

A．O(n) B．O(n) C．O(n) D．O(n × log2)

（8）下面哪个术语与数据的存储结构无关（ D ）。

D．队列 A．顺序表 B．链表 C．散列表

（9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（ A ）。

A．p->next=p->next->next; B．p=p->next; p->next=p->next->next; C．p->next=p->next; D．p =p->next->next;

（10）在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（ B ）。

A．s->next=p;p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p;

3.2 设计一个算法，求一个单链表中的结点个数。

【答】：单链表存储结构定义如下（相关文件：linklist.h）

2

2

2

3

n

#include

11

#include typedef struct node { int data;

struct node *next; }linknode;

typedef linknode *linklist;

/*尾插法创建带头结点的单链表*/ linklist creatlinklist() { linklist head,r,x,s;

head=r=(linklist)malloc(sizeof(linknode));

printf(\请输入一组以 0 结束的整数序列：\\n\ scanf(\ while (x)

{ s=(linklist)malloc(sizeof(linknode)); s->data=x; r->next=s; r=s;

scanf(\

}

r->next=NULL; return head; }

/*输出带头结点的单链表*/ void print(linklist head) { linklist p; p=head->next; printf(\ while(p)

{ printf(\ p=p->next;

}

printf(\}

基于上述结构定义，求单链表中的结点个数的算法程序如下： int count(linklist head) { int c=0;

linklist p=head; while (p) {c++;

12

p=p->next;

}

return c; }

3.3 设计一个算法，求一个带头结点单链表中的结点个数。

【答】：带头结点的单链表的存储结构定义同题 3.2，实现本题功能的算法程序如下（3_3.c） #include \ int count(linklist head) { int c=0;

linklist p=head->next; while (p) {c++; p=p->next;

}

return c; }

main() /*测试函数*/ {linklist head;

head=creatlinklist(); print(head);

printf(\ getch(); }

当输入 5 个数据时，产生的输出结果如下图所示：

3.4 设计一个算法，在一个单链表中值为 y 的结点前面插入一个值为 x 的结点。即使值为 x 的 新结点成为值为 y 的结点的前驱结点。 【答】：

#include \

void insert(linklist head,int y,int x)

{/*在值为 y 的结点前插入一个值为 x 的结点*/ linklist pre,p,s; pre=head; p=head->next;

13

while (p && p->data!=y) { pre=p; p=p->next; }

if (p)/*找到了值为 y 的结点*/

{ s=(linklist)malloc(sizeof(linknode)); s->data=x; s->next=p; pre->next=s; } }

void main() /*测试程序*/ {linklist head; int y,x;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出单链表*/

printf(\请输入 y 与 x 的值:\\n\ scanf(\ insert(head,y,x); print(head); }

程序的一种运行结果如下图所示：

3.5 设计一个算法，判断一个单链表中各个结点值是否有序。 【答】：

#include \

int issorted(linklist head,char c)

/*当参数 c=’a’时判断链表是否为升序，当参数 c=’d’是判断链表是否为降序*/ { int flag=1;

linklist p=head->next; switch (c)

{case 'a':/*判断带头结点的单链表 head 是否为升序*/

14

while (p &&p->next && flag)

{if (p->data<=p->next->data) p=p->next; else flag=0;

}

break;

case 'd':/*判断带头结点的单链表 head 是否为降序*/ while (p &&p->next && flag)

{if (p->data>=p->next->data) p=p->next; else flag=0;

}

break;

}

return flag; }

int main() /*测试程序*/ { linklist head;

head=creatlinklist(); print(head);

if (issorted(head,'a')) printf(\单链表 head 是升序排列的！\\n\ else

if (issorted(head,'d')) printf(\单链表 head 是降序排列的！\\n\ else printf(\单链表 head 是无序的！\\n\}

程序运行时的三种输出结果如下图所示：

3.6 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。 【答】：

#include \ void verge(linklist head)

{/*本函数的功能是就地倒置带头结点的单链表*/

15

linklist p,q; p=head->next;

head->next=NULL; while (p) /*每次从原表取一个结点插入到新表的最前面*/ {q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

} int main() /*测试函数*/ {linklist head;

head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ verge(head); /*就地倒置单链表*/ print(head); /*输出倒置后的单链表*/ }

3.7 设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的 结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。 【答】：

#include \ linklist sprit(linklist head)

{ /*将带头结点的单链表 head 中的奇数值结点删除生成新的单链表并返回*/

linklist L,pre,p,r;

L=r=(linklist)malloc(sizeof(linknode)); r->next=NULL; pre=head;

p=head->next; while (p)

{ if (p->data%2==1) /*删除奇数值结点*/

{ pre->next=p->next;

r->next=p;

r=p;

p=pre->next;

}

else

{ pre=p;

p=p->next;

}

/*保留偶数值结点*/

16

}

r->next=NULL; return L;

/*置链表结束标记*/

}

int main() /*测试函数*/ {linklist head,L;

head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ L=sprit(head); /*分裂单链表 head*/ printf(\原单链表为:\\n\

print(head); /*输出倒置后的单链表*/ printf(\分裂所得奇数单链表为:\\n\ print(L); }

本程序的一组测试情况如下图所示。

3.8 设计一个算法，对一个有序的单链表，删除所有值大于 x 而不大于 y 的结点。 【答】：

#include \

void deletedata(linklist head,datatype x,datatype y)

{ /*删除带头结点单链表中所有结点值大于 x 而不大于 y 的结点*/

linklist pre=head,p,q;

p=head->next; 初始化*/

while (p && p->data<=x) /*找第 1 处大于 x 的结点位置*/

{ pre=p;

p=p->next;

}

while (p && p->data<=y) /*找第 1 处小于 y 的位置*/

p=p->next; q=pre->next; /*删除大于 x 而小于 y 的结点*/

pre->next=p; pre=q->next;

17

while (pre!=p) {free(q); q=pre;

pre=pre->next; }

/*释放被删除结点所占用的空间*/

}

void main() /*测试函数*/ { linklist head,L;

datatypex,y;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出原单链表*/ printf(\请输入要删除的数据区间:\\n\

scanf(\ deletedata(head,x,y);

print(head); /*输出删除后的单链表*/ }

3.9 设计一个算法，在双链表中值为 y 的结点前面插入一个值为 x 的新结点。即使值为 x 的新 结点成为值为 y 的结点的前驱结点。 【答】：

首先定义双链表的数据结构，相关文件 dlink.h，内容如下：

typedef int datatype; /*预定义的数据类型*/ typedef struct dlink_node{ /*双链表结点定义*/ datatype data; struct dlink_node *llink,*rlink; }dnode;

typedef dnode* dlinklist; /*双链表结点指针类型定义*/

/*尾插法创建带头结点的双链表*/

dlinklist creatdlinklist(void) { dlinklist head,r,s; datatype x;

head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点*/ head->llink=head->rlink=NULL;

printf(\请输入双链表的内容：（整数序列，以 0 结束）\\n\ scanf(\

while (x) /*输入结点值信息，以 0 结束*/ { s=(dlinklist ) malloc(sizeof(dnode)); s->data=x;

s->rlink=r->rlink; /*将新结点 s 插入到双链表链尾*/

18

s->llink=r;

r->rlink=s;

r=s;

scanf(\

}

return head; }

/*输出双链表的内容*/ void print(dlinklist head) { dlinklist p; p=head->rlink;

printf(\双链表的内容是：\\n\ while (p)

{ printf(\ p=p->rlink;

}

}

本题的求解程序如下： #include #include \

void insertxaty(dlinklist head,datatype y,datatype x) { dlinklist s,p;

/*首先在双链表中找 y 所在的结点，然后在 y 前面插入新结点*/ p=head->rlink;

while (p && p->data!=y) p=p->rlink;

if (!p) printf(\双链表中不存在值为 y 的结点,无法插入新结点!\\n\ else /*插入值为 x 的新结点*/ { s=(dlinklist)malloc(sizeof(dnode)); s->data=x; s->rlink=p;

s->llink=p->llink; p->llink->rlink=s; p->llink=s;

}

}

void main() /*测试函数*/ { dlinklist head; datatype x,y;

19

head=creatdlinklist(); print(head);

printf(\请输入要输入的位置结点值 y:\\n\ scanf(\

printf(\请输入要输入的结点值 x:\\n\ scanf(\

insertxaty(head,y,x);/*在值为 y 的结点前插入值为 x 的新结点*/ print(head);/*输出新的双链表*/ getch(); }

本程序的一组测试情况如下图所示。

3.10 设计一个算法，从右向左打印一个双链表中各个结点的值。 【答】：

本题的双链表定义同题 3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实 现如下：

#include #include \

void vprint(dlinklist head)

{ /*递归方法从右向左打印双链表的值*/ if (head->rlink)

{vprint(head->rlink);

printf(\

}

}

void main() /*测试函数*/ { dlinklist head;

head=creatdlinklist(); print(head);

printf(\从右向左打印的双链表的内容是:\\n\

20

vprint(head); getch(); }

本程序的一组测试情况如下图所示。

3.11 设计一个算法，将一个双链表改建成一个循环双链表。 【答】：

#include #include \

/*将一个双链表改成循环双链表*/ void dlinktocdlink(dlinklist head) { dlinklist r; r=head;

while (r->rlink) /*寻找尾结点*/ r=r->rlink;

head->llink=r; r->rlink=head; }

void printcdlink(dlinklist head) { /*打印双链表*/ dlinklist p; p=head->rlink; while (p!=head)

{printf(\ p=p->rlink;

}

}

int main() /*测试函数*/ { dlinklist head;

head=creatdlinklist(); dlinktocdlink(head);

printf(\循环双链表的内容是：\\n\ printcdlink(head); }

21

本文来源：https://www.bwwdw.com/article/pzfa.html