线性表子系统.docx
- 文档编号:15500654
- 上传时间:2023-07-05
- 格式:DOCX
- 页数:22
- 大小:261.22KB
线性表子系统.docx
《线性表子系统.docx》由会员分享,可在线阅读,更多相关《线性表子系统.docx(22页珍藏版)》请在冰点文库上搜索。
线性表子系统
1、实验内容或题目
(1)用结构体描述一个字符型的单项链表。
(2)创建线性表;在线性表中插入元素、删除元素;显示线性表中所有元素等基本操作。
(3)用if语句设计一个选择式菜单。
线性表子系统
*******************************
*1------建表*
*2------插入*
*3------删除*
*4------显示*
*5------查找*
*6------求表长*
*0------返回*
*******************************
请选择菜单号(0--6):
2、实验目的与要求
(1)掌握线性表的特点。
(2)掌握线性表顺序存储结构和链式结构的基本运算。
(3)掌握线性表的创建、插入、删除和显示线性表中元素等基本操作。
3、实验步骤与源程序
实验步骤:
从具体问题抽象出适当的数学模型
设计求解数学模型的算法
编制、运行并调试程序,直到解决实际问题。
源代码
1.#include
#include
#include
typedefstructlinknode
{
chardata;
structlinknode*next;
}linnode;
linnode*head;
intn;
voidCreateList()
{
linnode*p,*s;
charx;
intz=1;
head=(linnode*)malloc(sizeof(linnode));
n=0;
p=head;
printf("\n\t\t请逐个输入结点,以“x”为结束标记!
\n");
printf("\n");
while(z)
{
printf("\t\t输入一个字符数据,并按回车:
");
scanf("%c",&x);
getchar();
if(x!
='x')
{
s=malloc(sizeof(linnode));
n++;
s->data=x;
p->next=s;
s->next=NULL;
p=s;
}
else
z=0;
}
}
voidInsList(inti,charx)
{
linnode*s,*p;
intj=0;
p=head;
while(p!
=NULL&&j
{
j++;
p=p->next;
}
if(p!
=NULL)
{
s=malloc(sizeof(linnode));
s->data=x;
s->next=p->next;
p->next=s;
n++;
}
else
printf("\n\t\t线性表为空或插入位置超出!
\n");
}
voidDelList(charx)
{
linnode*p,*q;
if(head==NULL)
{
printf("\n\t\t链表下溢!
");
return;
}
if(head->next==NULL)
{
printf("\n\t\t线性表已经为空!
");
return;
}
q=head;
p=head->next;
while(p!
=NULL&&p->data!
=x)
{
q=p;
p=p->next;
}
if(p!
=NULL)
{
q->next=p->next;
free(p);
n--;
printf("\n\t结点%c已经被删除!
",x);
}
else
printf("\n\t\t抱歉!
没有找到您要删除的结点。
");
}
voidShowList()
{
linnode*p=head;
printf("\n\t\t显示线性表所有元素:
");
if(head->next==NULL||p==NULL)
printf("\n\t\t链表为空!
");
else
{
printf("\n\t\t");
while(p->next!
=NULL)
{
printf("%5c",p->next->data);
p=p->next;
}
}
}
voidSearchList(charx)
{
linnode*p;
inti=1;
if(head==NULL)
{
printf("\n\t\t链表下溢!
");
return;
}
if(head->next==NULL)
{
printf("\n\t\t线性表为空,没有任何结点!
");
return;
}
p=head->next;
while(p!
=NULL&&p->data!
=x)
{
p=p->next;
i++;
}
if(p!
=NULL)
printf("\n\t\t在表的第%d位上找到值为%c的结点!
",i,x);
else
printf("\n\t\t抱歉,未找到值为%c的结点!
",x);
}
voidmain()
{
intchoice,i,j=1;
charx;
head=NULL;
while(j)
{
printf("\n");
printf("\n\t\t线性表子系统");
printf("\n\t\t*********************************");
printf("\n\t\t*1------建表*");
printf("\n\t\t*2------插入*");
printf("\n\t\t*3------删除*");
printf("\n\t\t*4------显示*");
printf("\n\t\t*5------查找*");
printf("\n\t\t*6------求表长*");
printf("\n\t\t*0------返回*");
printf("\n\t\t*********************************");
printf("\n\t\t请选择菜单号(0--6):
");
scanf("%d",&choice);
getchar();
if(choice==1)
CreateList();
else
if(choice==2)
{
printf("\n\t\t请输入插入的位置i和插入的数据(输入格式:
i,x):
");
scanf("%d,%c",&i,&x);
InsList(i,x);
}
else
if(choice==3)
{
printf("\n\t\t请输入要删除的数值:
");
scanf("%c",&x);
DelList(x);
}
else
if(choice==4)
if(head==NULL)
printf("\n\t\t请先建立线性表!
");
else
ShowList();
else
if(choice==5)
{
printf("\n\t\t请输入要查找的元素:
");
scanf("%c",&x);
SearchList(x);
}
else
if(choice==6)
printf("\n\t\t线性表长度为:
%d",n);
else
if(choice==0)
j=0;
else
printf("\n\t\t输入错误!
请重新输入!
");
}
}
2.#include
#defineMAXLEN100
typedefstruct
{intdata[MAXLEN];
intlast;
}SeqList;
voidshow_list(SeqListh)
{inti=h.last;
for(i;i>=1;i--)
if(h.data[i])
printf("\(%dx^%d\)+",h.data[i],i);
printf("\(%dx^%d\)\n",h.data[0],0);
}
voidcreate_list(SeqList*D)
{intn,i;
intk=99;
printf("请输入多项式X的最高次数:
");
scanf("%d",&n);
for(k;k>=0;k--)
D->data[k]=0;
printf("请按多项式X的次数由大到小输入系数,缺少项用0补齐\n");
for(i=n;i>=0;i--)
{printf("输入X^%d项的系数:
",i);
scanf("%d",&D->data[i]);
}
D->last=n;
}
voidadd_List(SeqListf,SeqListg,SeqList*h)
{inti;
h->last=f.last>g.last?
f.last:
g.last;
for(i=0;i<=h->last;i++)
h->data[i]=f.data[i]+g.data[i];
}
voidmain()
{SeqListf,g,h;
printf("创建的多项式f(x):
\n");
printf("\n");
create_list(&f);
printf("f(x)=");
show_list(f);
printf("创建的多项式g(x):
\n");
printf("\n");
create_list(&g);
printf("g(x)=");
show_list(g);
printf("多项式f(x)和g(x)的和");
add_List(f,g,&h);
printf("h(x)=");
show_list(h);
}
3.#include
#include
#include"stdlib.h"
structpolynomial{
intfactor;
charvar;
intindex;
structpolynomial*next;
};
structpolynomial*Insert(structpolynomial*list,structpolynomial*node)
{
structpolynomial*temp=NULL;
structpolynomial*p=NULL;
if(list==NULL)
list=node;
elseif(list->index
{temp=list;list=node;list->next=temp;}
else{
for(temp=list;temp->next!
=NULL;temp=temp->next)
if(temp->next->index<=node->index)
break;
node->next=temp->next;
temp->next=node;
}
returnlist;
}
structpolynomial*DeletZeroFactor(structpolynomial*list)
{
structpolynomial*temp=NULL;
structpolynomial*p=NULL;
while(list->factor==0)
list=list->next;
for(temp=list;temp->next!
=NULL;temp=temp->next)
{
if(temp->next->factor==0)
temp->next=temp->next->next;
}
returnlist;
}
structpolynomial*Creat()
{
structpolynomial*head=NULL;
structpolynomial*node=NULL;
inti,j;
charinputs[50];
chartmp[10];
memset(inputs,0,50);
printf("请输入多项式(2x3+3x1-5):
\n");
gets(inputs);
for(i=j=0;inputs[i]!
='\0';i++)
{
if(inputs[i]=='x')
{
node=(structpolynomial*)malloc(sizeof(structpolynomial));
memset(node,0,sizeof(structpolynomial));
node->var='x';
memset(tmp,0,10);
if(inputs[j]=='-')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->factor=-atoi(tmp);
}elseif(inputs[j]=='+')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->factor=atoi(tmp);
}elseif(inputs[j]>='0'&&inputs[j]<='9')
{
strncpy(tmp,inputs+j,i-j);
node->factor=atoi(tmp);
}
j=i+1;
}
elseif(inputs[i]=='+'||inputs[i]=='-'||inputs[i+1]=='\0')
{
if(inputs[i+1]=='\0')
i=i+1;
if(inputs[j-1]=='x')
{
memset(tmp,0,10);
if(inputs[j]=='+')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->index=atoi(tmp);
}elseif(inputs[j]=='-')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->index=-atoi(tmp);
}elseif(inputs[j]>='0'&&inputs[j]<='9')
{
strncpy(tmp,inputs+j,i-j);
node->index=atoi(tmp);
}
j=i;
}elseif(inputs[j-1]>='0'&&inputs[j-1]<='9')
{
node=(structpolynomial*)malloc(sizeof(structpolynomial));
memset(node,0,sizeof(structpolynomial));
memset(tmp,0,10);
if(inputs[j]=='+')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->factor=atoi(tmp);
node->index=0;
}elseif(inputs[j]=='-')
{
strncpy(tmp,inputs+j+1,i-j-1);
node->factor=-atoi(tmp);
node->index=0;
}elseif(inputs[j]>='0'&&inputs[j]<='9')
{
strncpy(tmp,inputs+j,i-j);
node->factor=atoi(tmp);
node->index=0;
}
j=i+1;
}
head=Insert(head,node);
}
}
returnhead;
}
structpolynomial*Add(structpolynomial*factor1,structpolynomial*factor2)
{
structpolynomial*head=NULL;
structpolynomial*head1=NULL;
structpolynomial*head2=NULL;
structpolynomial*node1=NULL;
structpolynomial*node2=NULL;
structpolynomial*node=NULL;
if(factor1->index>=factor2->index)
{head1=factor1;head2=factor2;}
else
{head1=factor2;head2=factor1;}
node2=head2;
while(node2!
=NULL)
{
node=node2->next;
for(node1=head1;node1!
=NULL;node1=node1->next)
{
if(node1->index==node2->index)
{
node1->factor=node1->factor+node2->factor;
break;
}
}
if(node1==NULL)
head1=Insert(head1,node2);
node2=node;
}
head=DeletZeroFactor(head1);
returnhead;
}
voidOutput(structpolynomial*list)
{
structpolynomial*node;
printf("求和结果:
\n");
if(list)
printf("%d",list->factor);
if(list->index!
=0)
printf("%c%d",list->var,list->index);
for(node=list->next;node!
=NULL;node=node->next)
{
if(node->factor>0)
printf("+%d",node->factor);
else
printf("%d",node->factor);
if(node->index!
=0)
printf("%c%d",node->var,node->index);
}
printf("\n");
}
voidmain()
{
structpolynomial*f1=NULL;
structpolynomial*f2=NULL;
f1=Creat();
f2=Creat();
f1=Add(f1,f2);
Output(f1);
}
4、测试数据与实验结果(可以抓图粘贴)
5、结果分析与实验体会
这次验证性实验相比以前的长了,复杂了。
但是总而言之,都是c的基本知识,只是函数多了,新东西也多了。
这个验证性的实验主要是让我们了解线性表子系统,掌握一些线性表的特点、线性表顺序存储结构和链式结构的基本运算和线性表的插入、创建、删除和显示线性表等基本操作。
这个实验的主函数主要是通过if语句的多重嵌套来调用相应的函数,实现相应的功能。
而程序的开始则是通过建立链表来存储数据,之后分别则是主函数调用的相关函数的具体程序。
在自主设计的实验则是让我们用线性表的顺序存储结构和链式存储来实现多项式求和的功能。
其主体功能跟验证性实验相差无几,只不过数据的类型有点不同,并且需要求和之外,其它线性表的插入、删除等运算还是差不多的。
但是,这个程序难就难在求和方面。
在求和时,可能出现多种情况,比如同类项相加为0就需要删除,而前面没有的,后面相加却出现了,则需要增加结点。
还有数据类型,它既有系数又有指数,这些都是编程中的困难。
在顺序表中,程序运行当中,并没双重for循坏,甚至三个及以上,故顺序表中时间复杂度为O(n)。
链表中也同样如此。
通过线性表的学习,我发现单靠以前浅薄的知识远远不够,程序的越来越长,问题的越来越复杂,都需要不断努力才能掌握。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 子系统