西电机电院软件技术基础大作业.docx
《西电机电院软件技术基础大作业.docx》由会员分享，可在线阅读，更多相关《西电机电院软件技术基础大作业.docx（21页珍藏版）》请在冰点文库上搜索。
西电机电院软件技术基础大作业
西电机电院软件技术基础大作业
上机报告
班级：
04103201
姓名：
赵伟
学号：
04103123
一、上机目的:
明确线性表和树的相关用法，写出相应的程序，实现相应所需的功能。
二、上机内容
1．设有一个由正整数组成的无序单链表，编写完成下列功能的算法：
①找出最小值结点，且打印该数值；
②若该数值是奇数，则将其与直接后继结点的数值交换；
③若该数值是偶数，则将其直接后继结点删除。
2．编一程序：
①建立一个数据域为1至10的带头结点的链表；
②将此链表就地逆转。
3．设有一个含有数字、英文字母和其它字符的单链表，试编写一个算法将该单链表拆分为三个单链表，使每个单链表中只包含同一类的字符，要求利用原表中的结点空间作为这三个表的结点空间，头结点可以另辟空间。
4．某百货公司仓库中有一批电视机，试按价格从高到低的次序建立一个循环链表，每个结点有价格、数量和指针三个域。
现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。
5．假设称正读反读都相同的字符序列为回文。
例如，‘abba’，‘abcba’都是回文，‘ababab’不是回文，试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。
6．试设计一个程序，求二叉树的结点数目和叶子结点数目。
三、设计说明
1.用一个单链表实现，单链表中的每一个节点储存一个整数，从前到后遍历一遍链表找出最小值，若该值是奇数，则将最小值节点与其后节点交换，若该值是偶数，则将其后节点删除。
2.建立一个单链表，从头结点开始，数据域依次是1到10。
再按照头插法的思想，从第二个节点还是，依次把其后的节点，插到头节点的后面。
即可将链表逆转。
3.建立三个单链表。
其中一个链表用来存输入的数据，其余三个链表置空，从前到后遍历一遍原始链表，若数据域是数字，则继续遍历该链表。
若数据域是英文字母或是其它字符，则将其从原来的链表中删除，并把它分别插入到其它两个链表中。
4.建立一个循环链表，链表的数据域为商品的价格和数量，最后插入（4000,10）节点。
从前到后遍历这个链表，若链表中存在一个节点，其数据域的价格为4000，则数量再加上10即可，若不存在，按照链表的顺序将该节点插入。
5.建立一个顺序表，从键盘上输入字符串，从第一个节点和最后一个节点依次向中间比较。
若发现不同。
则比较结束，该字符串不是回文，否则，是回文。
6.叶子节点的左右孩子节点的数据域均为0.用先序遍历的方法遍历该链表，每遍历到一个节点，就将节点数加1，若节点的左右孩子节点的数据域为0，则叶子节点数加1.
四、调试分析
1.在调试过程中，要充分考虑到各种可能出现的情况。
比如说，当有多个最小值时，需要依次与其后的节点进行操作；再如，到最小值在最后一个节点时，就不能进行任何处理了。
时间复杂度：
O（n）。
2.好像没有遇到什么问题。
时间复杂度：
O（n）。
3.此处要注意结束条件，否则可能没法正常退出。
时间复杂度：
O（n）。
4.本题需要注意，链表中是否有数据域为4000的节点，有的话就不用再新建了。
时间复杂度：
O（n）。
5.本题好像也没有遇到什么问题。
时间复杂度：
O（n）。
6.本题要注意，叶子节点的定义。
否则，程序无法判断节点是否为叶子节点。
时间复杂度：
O（n）。
五、测试结果
1.
2.
3.
4.
5.
6.
六、源程序：
1.
#include
#include
typedefintdatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
linklist*head,*p;
linklist*creatlistr1（）;/*尾插法*/
voidDelete（linklist*p,linklist*head）;
linklist*locate（linklist*head,datatypekey）;
voidoutput（linklist*p）;
intmain（）
{
intMin;
linklist*pMin=（linklist*）malloc（sizeof（linklist））;
printf（"请输入单链表，并以-1结束：
\n"）;
head=creatlistr1（）;
Min=head->next->data;
p=head->next->next;
while（p!
=NULL）
{
if（Min>p->data）
{
Min=p->data;
pMin=p;
}
p=p->next;
}
printf（"最小值为：
%d\n",Min）;
p=head;
while（（p=locate（p,Min））!
=NULL）
{
if（p->next!
=NULL）
{
if（Min%2）
{
（p->data）^=（p->next->data）^=（p->data）^=p->next->data;
}
else
{
Delete（p->next,head）;
}
}
}
printf（"变更后的链表为：
"）;
output（head）;
return0;
}
linklist*creatlistr1（）/*尾插法*/
{
intch;
linklist*head,*s,*r;
head=（linklist*）malloc（sizeof（linklist））;
r=head;
scanf（"%d",&ch）;
while（ch!
=-1）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=ch;
r->next=s;
r=s;
scanf（"%d",&ch）;
}
r->next=NULL;
returnhead;
}
voidoutput（linklist*ll）
{
linklist*p;
for（p=ll->next;p!
=NULL;p=p->next）
{
printf（"%d",p->data）;
}
printf（"\n"）;
}
voidDelete（linklist*p,linklist*head）
{
linklist*q=head;
while（q->next!
=p）
{
q=q->next;
}
q->next=p->next;
free（p）;
}
linklist*locate（linklist*head,datatypekey）
{
linklist*p=head->next;
while（p!
=NULL）
{
if（p->data!
=key）
{
p=p->next;
}
elsebreak;
}
returnp;
}
2.
#include
#include
typedefintdatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
linklist*head;
linklist*reverse1（linklist*head）;
voidoutput（linklist*p）;
intmain（）
{
inti;
head=（linklist*）malloc（sizeof（linklist））;
linklist*s,*r;
r=head;
for（i=0;i<10;i++）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=i+1;
r->next=s;
r=s;
}
r->next=NULL;
output（head）;
reverse1（head）;
output（head）;
return0;
}
voidinsertafter（linklist*p,datatypex）
{
linklist*s;
s=（linklist*）malloc（sizeof（linklist））;
s->data=x;
s->next=p->next;
p->next=s;
}
voidoutput（linklist*ll）
{
linklist*p;
for（p=ll->next;p!
=NULL;p=p->next）
{
printf（"%d",p->data）;
}
printf（"\n"）;
}
linklist*reverse1（linklist*head）
{
linklist*p,*q;
p=head->next;
while（p->next!
=NULL）
{
q=p->next;
p->next=q->next;
q->next=head->next;
head->next=q;
}
returnhead;
}
3.
#include
#include
#include
typedefintdatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
linklist*head,*head2,*head3,*p,*p2,*p3;
linklist*creatlistr1（）;/*尾插法*/
linklist*Delete（linklist*p,linklist*head）;
voidoutput（linklist*p）;
intmain（）
{
printf（"请输入链表,并以'$'结束：
\n"）;
head=creatlistr1（）;
head2=（linklist*）malloc（sizeof（linklist））;
head2->next=NULL;
head3=（linklist*）malloc（sizeof（linklist））;
head3->next=NULL;
p=head->next;
p2=head2;
p3=head3;
while（p!
=NULL）
{
if（isdigit（p->data））
{
p=p->next;
continue;
}
if（isalpha（p->data））
{
p2->next=Delete（p,head）;
p2=p2->next;
p=p->next;
p2->next=NULL;
continue;
}
p3->next=Delete（p,head）;
p3=p3->next;
p=p->next;
p3->next=NULL;
}
output（head）;
output（head2）;
output（head3）;
return0;
}
linklist*creatlistr1（）/*尾插法*/
{
charch;
linklist*head,*s,*r;
head=（linklist*）malloc（sizeof（linklist））;
r=head;
ch=getchar（）;
while（ch!
='$'）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=ch;
r->next=s;
r=s;
ch=getchar（）;
}
r->next=NULL;
returnhead;
}
voidoutput（linklist*ll）
{
linklist*p;
for（p=ll->next;p!
=NULL;p=p->next）
{
printf（"%c",p->data）;
}
printf（"\n"）;
}
linklist*Delete（linklist*p,linklist*head）
{
linklist*q=head;
while（q->next!
=p）
{
q=q->next;
}
q->next=p->next;
returnp;
}
4.
#include
#include
typedefintdatatype;
typedefstructnode
{
datatypeprice;
datatypemount;
structnode*next;
}linklist;
linklist*head,*p;
linklist*creatlistr1（）;/*尾插法*/
voidinsert（linklist*head,datatypeprice,datatypemount）;
voidoutput（linklist*head）;
intmain（）
{
printf（"请按价格从高到低的次序依次输入电视机的价格和数量，格式：
“价格数量”，两组数据之间用空格分开，最后以“00”结束：
\n"）;
head=creatlistr1（）;
insert（head,4000,10）;
output（head）;
return0;
}
linklist*creatlistr1（）/*尾插法*/
{
datatypeprice;
datatypemount;
linklist*head,*s,*r;
head=（linklist*）malloc（sizeof（linklist））;
r=head;
scanf（"%d%d",&price,&mount）;
while（!
（price==0&&mount==0））
{
s=（linklist*）malloc（sizeof（linklist））;
s->price=price;
s->mount=mount;
r->next=s;
r=s;
scanf（"%d%d",&price,&mount）;
}
r->next=head;
returnhead;
}
voidoutput（linklist*ll）
{
linklist*p;
for（p=ll->next;p!
=head;p=p->next）
{
printf（"%d%d\n",p->price,p->mount）;
}
printf（"\n"）;
}
voidinsert（linklist*head,datatypeprice,datatypemount）
{
linklist*s,*p=head->next,*q=head;
s=（linklist*）malloc（sizeof（linklist））;
s->price=price;
s->mount=mount;
while（p!
=head,p->price>4000）
{
p=p->next;
q=q->next;
}
if（p->price==4000）
{
p->mount+=10;
}
else
{
s->next=q->next;
q->next=s;
}
}
5.
#include
#include
#defineMaxnum1024
intmain（）
{
charstr[Maxnum]={0};
inti,j,flag=1;
scanf（"%s",str）;
j=strlen（str）-1;
for（i=0;i{
if（str[i]!
=str[j]）
{
flag=0;
break;
}
}
if（flag）
{
printf（"是回文\n"）;
}
else
{
printf（"不是回文\n"）;
}
return0;
}
6.
#include
#include
typedefintdatatype;
typedefstructNode
{
datatypedata;
structNode*lchild,*rchild;
}Node,*pNode;
intCreateTree（pNode&T）
{
datatypee;
scanf（"%d",&e）;
if（e==0）T=NULL;
else
{
T=（pNode）malloc（sizeof（Node））;
if（!
T）
{
exit（-2）;
}
T->data=e;
CreateTree（T->lchild）;
CreateTree（T->rchild）;
}
return1;
}
intCountNode（pNodeT）
{
intm=0,n=0;
if（T==NULL）
return0;
else
{
m=CountNode（T->lchild）;
n=CountNode（T->rchild）;
return（m+n+1）;
}
}
voidleafcount（pNodep,int*count）
{
if（p==NULL）return;
if（p->lchild==NULL&&p->rchild==NULL）
{
（*count）++;
return;
}
leafcount（p->lchild,count）;
leafcount（p->rchild,count）;
}
intmain（）
{
pNodeT;
intres=0;
printf（"请用前序遍历的顺序建立二叉树，叶子节点的左右子树以0结束:
\n"）;
CreateTree（T）;
printf（"节点数为：
%d\n",CountNode（T））;
leafcount（T,&res）;
printf（"叶子节点数目为:
%d",res）;
return0;
}
升级会员 