数据结构(第二版)习题答案第3章(2)

数据结构答案

printf("List is:\n");
while(p)
{ printf("%5d",p->data);


p=p->next;
}
printf("\n");


}

基于上述结构定义，求单链表中的结点个数的算法程序如下：


int count(linklist head)

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


p=p->next;
}
return c;


}

3.3设计一个算法，求一个带头结点单链表中的结点个数。
【答】：带头结点的单链表的存储结构定义同题
3.2，实现本题功能的算法程序如下（
3_3.c）
#include "linklist.h"
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("\nLength of head is:%d",count(head));
getch();


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



3.4设计一个算法，在一个单链表中值为
y的结点前面插入一个值为
x的结点。即使值为
x的
新结点成为值为
y的结点的前驱结点。
【答】：
#include "linklist.h"
void insert(linklist head,int y,int x)
{/*在值为
y的结点前插入一个值为
x的结点*/


linklist pre,p,s;
pre=head;
p=head->next;



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("\n请输入
y与
x的值:\n");
scanf("%d %d",&y,&x);
insert(head,y,x);
print(head);


}


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



3.5设计一个算法，判断一个单链表中各个结点值是否有序。
【答】：
#include "linklist.h"
int issorted(linklist head,char c)
/*当参数
c=’a’时判断链表是否为升序，当参数
c=’d’是判断链表是否为降序*/
{ int flag=1;


linklist p=head->next;
switch (c)
{case 'a':/*判断带头结点的单链表
head是否为升序
*/



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("单链表
hea
d是降序排列的！
\n");
else printf("单链表
head是无序的！\n");


}


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



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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构(第二版)习题答案第3章(2)在线全文阅读。