数据结构课后习题答案（修订版）(2)

}

if（p!=NULL）/*找到要找的结点*/ {

s=p;q->next=p->next; free（s）;/*删除结点*/ }

else{printf（―没有找到您要找的结点\\n‖）;} }

（2）/*插入学生结点node算法,假设node 在主函数中已经创建*/ void InsertNode （stuNode *head,stuNode *node） {

stuNode *p=head,*q;

q=p;p=p->next; /*从链表的第一个结点开始查找*/ if（node->scorescore） {

node->next=p;

q->next=node;/*将结点插入表头*/ return;/*算法结束*/ }

while（p!=NULL&&p->scorescore） {

q=p;p=p->next; }

if（p= =NULL） {

q->next=node; /*将结点插入链表的表尾*/ }

else /*插入结点*/ {

node->next=p; q->next=node; } }

7．某仓库中有一批零件，按其价格从低到高的顺序构成一个单链表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又新有m个价格为s的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下：

算法提示：

/*定义一个结点，每个结点表示一种零件的相关信息*/

typedef struct NODE {

float price;/*该零件的价格*/

unsigned long number;/*该零件的数量*/ struct NODE*next; }Node;

/*在头结点为head的单链表中插入一个零件信息结点node的算法

如下*/

/*假设该结点node已经在主函数中创建完毕*/ void InsertNode（Node*head,Node*node） {

Node*p=head,*q;

q=p;p=p->next; /*从链表的第一个结点开始查找*/ if（node->priceprice） {

node->next=p;

q->next=node;/*将结点插入表头*/ ruturn;/*算法结束*/ }

while（p!=NULL&&p->priceprice） {

q=p;p=p->next; }

if（p= =NULL） {

q->next=node; /*将结点插入链表的表尾*/ }

else /*插入结点*/ {

node->next=p; q->next=node; } }

8. 设指针P指向单链表的首结点，指针X指向单链表中的任意一个结点，写出在X前插入一个结点i的算法。 算法提示：

/*假设该链表的头结点为head，且链表中的结点用Node定义*/ /*在结点X之前插入结点i的算法如下*/

void InsertNode（Node*head,Node*i,Node*X） {

Node *p=head,*q;

q=p;p=p->next;/*依照题意，p指向链表的第一个结点*/ if（p= =X）/*将结点插入头结点和第一个结点之间*/ {

i->next=p; q->next=i;

return;/*算法结束*/ }

while（p!=NULL&&p!=X）/*查找插入位置*/ {

q=p;p=p->next; }

if（p= =NULL）{return NULL;}/*查找失败*/

}

else {

i->next=p; q->next=i; }

9．设多项式A和B采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在A中。

算法提示：请参考本章 算法3.23 和 算法3.24。

10．设指针a和b分别为两个带头结点的单链表的头指针，编写实现从单连表La中删除自第i个数据元素起，共length个数据元素、并把它们插入到单链表Lb中第j个元素之前的算法。 算法提示：

void DInsert（Node *a,Node *b,int i,int j,int length） {

Node*ap=a->next,*bp=b->next; /*定义了两个分别处理La和Lb的两个指针变量*/

Node*ap1,*ap2,*ap3,*ap4; /*定义了用于处理La的4个指针变量*/ Node*bp1,*bp2; /*定义了用于处理Lb的2个指针变量*/

for（int k=1;knext;} ap1=ap;ap2=ap1->next; ap=ap2;

for（int k=1;knext;} ap3=ap;ap4=ap3->next;

ap1->next=ap4; /*将La中长度为length的子链脱链*/ for（int k=1;knext;} bp1=bp;bp2=bp1->next;

ap3->next=bp2;bp1->next=ap2; /*将长度为length的子链挂接到Lb相应的位置*/ }

11. 设La和Lb是两个有序的循环链表，Pa和Pb分别指向两个表的表头结点，是写一个算法将这两个表归并为一个有序的循环链表。

算法提示：本题可以换个角度考虑，因为对于循环链表考虑的因素较单链表多，所以我们可以将两个循环链表首先处理成两个单链表（方法：将链表的最后一个结点的next域设置为NULL），这样问题就转化为将两个普通链表归并的问题，最后再把归并好的单链表转换成循环链表（方法：将链表的最后一个结点的next域指向该链表的头结点）。下面我们仅给出单链表归并的算法作为参考，具体的转换由于比较简单所以这里就不详述了：

void MergeList（Node*pa,Node*pb） {

Node*pc=pa;

Node*p1=pa->next,*p2=pb->next ;

}

While（p1!=NULL&&p2!=NULL） {

if（p1->datadata） {

pc->next=p1; pc=pc->next; p1=p1->next; } else {

pc->next=p2; pc=pc->next; p2=p2->next; } }

if（p1!=NULL）{ pc->next=p1;} else { pc->next=p2;}

12. 已知有一个单向循环链表，其每个结点中含三个域：pre、data和next，其中data为数据域，next为指向后继结点的指针域，pre也为一个指针域，但是他的值为空（null），试编写一个算法将此单链表改为双向循环链表，即使pre成为指向前驱结点的指针域。

算法提示：/*假设链表的头指针为head，用Node来定义一个结点*/

void Convert（Node*head） {

Node*p=head,*q;

q=p;p=p->next;/*从链表的第一个结点开始处理*/ while（p!=head） {

p->pre=q; q=p;

p=p->next;

}

p->pre=q;/*构成循环*/ }

习题三答案

2.本题较简单，可参考本章栈操作示意图的画法，答案略。

3.参考答案：栈和队列都是操作受限的线性表，因此二者都具备线性表的一般特性；对于栈，元素进栈出栈的原则是“后进先出”，即LIFO，对于队列，元素进出队列的原则是“先进先出”，即FIFO。

4．参考答案：1和4。

6．算法提示：利用栈的LIFO特性，如果是左括号则将其压入栈顶，然后读取下一个字符，如果仍然是左括号，再将其压入栈顶，依次类推，直到出现右括号为止，这时将最靠近栈顶的左括号弹出，它一定与该右括号相匹配。下面以圆括号为例给出算法：

int match（） {

seqstack s; char ch;

initstack（&s） while（2） {

ch=getchar（）； if（ch= =?$?）break;

if（ch= =?(?）push（&s,ch）； else if（ch= =?）?） if（stackempty（$s）） {

printf（”the parenthess match failed!\\n”）； return 0; }

else pop（&s）； }

if（stackempty（&s）） {

printf（”the parenthness match success!\\n”）； return 1; } else {

printf（”the parenthness match failed!\\n”）； return 0; } }

8．参考答案：这是由栈的LIFO特性决定的，可参考图4-4。

9．参考答案：优点，不会出现线性队列中的队头指针“追上”队尾指针的情况，即“假溢出”；判空条件：队头指针等于队尾指针（ …… 此处隐藏：2005字，全部文档内容请下载后查看。喜欢就下载吧 ……