实验1线性表基础实验.docx
《实验1线性表基础实验.docx》由会员分享,可在线阅读,更多相关《实验1线性表基础实验.docx(18页珍藏版)》请在冰点文库上搜索。
实验1线性表基础实验
云南大学软件学院实验报告
课程:
数据结构实验学期:
2014-2015学年第一学期任课教师:
专业:
信息安全学号:
姓名:
成绩:
一、实验目的
1.理解线性表的顺序存储结构。
2.掌握线性表的单链表存储结构。
二、实验软硬件环境(CPU、OS、IDE):
三、实验任务(要求写出核心代码,并对运行结果截图)
1.用C语言实现课本P24:
算法2.4(顺序存储的元素插入算法);
实验测试数据基本要求:
顺序表容量初始化为10,大小初始化为9,连续在第7、8、13的位置插入任意数据,并分别输出元素插入前后顺序表中的元素。
#include
#definemaxsize10//顺序表的初始容量为10;
intmain()
{
inti,j,k,m,n,length=9;
inta[maxsize]={4,2,6,8,5,9,31,23,45};//顺序表的大小初始化为9;
printf("beforeinsertthetableis:
");
for(n=0;n{printf("%3d",a[n]);//输出插入数据前的顺序表;}printf("\n");for(i=0;i<3;i++){printf("请输入你想在哪个位置插入数据(1--%d)(回车结束):",length+2);scanf("%d",&m);start:if(m<1||m>length+2){printf("error!\n");printf("请输入你想在哪个位置插入数据(1--%d)(回车结束):",length+2);scanf("%d",&m);gotostart;//跳转到start;}elseprintf("请输入你想插入的数字(回车结束):");scanf("%d",&k);j=length-1;a[j+2]=00;//给第12位赋值为0;for(j=length-1;j>=m-1;j--){a[j+1]=a[j];//表中元素后移一位;}a[m-1]=k;//将输入的数赋值给指定位置;length++;//长度加一;}for(n=0;n<=length;n++){printf("%3d",a[n]);//输出插入元素后的顺序表;}return0;}2.用C语言实现课本P26:算法2.7(顺序表的合并算法);实验测试数据基本要求:La=(6,11,11,23);Lb=(2,10,12,12,21)#includeintmain(){inta[4]={6,11,11,23},b[5]={2,10,12,12,21},c[8];//顺序表初始化;inti=0,j=0,k=0;while(i<=3&&j<=4)//循环条件;{if(a[i]<=b[j])//将a[i],b[j]中较小一个赋值给数组c[k],再自加;c[k]=a[i],i++,k++;elsec[k]=b[j],k++,j++;}while(i<=3)c[k]=a[i],i++,k++;while(j<=4)//剩余元素再赋给c[k];c[k]=b[j],j++,k++;printf("Aftercombine,theorderis:");for(k=0;k<=8;k++)printf("%5d",c[k]);//输出合并后的顺序表;printf("\n");return0;}3.构造并求带头结点单链表L中第i个结点的指针,若不存在,则返回NULL。实验测试数据基本要求:自定义初始链表长度n(n≥10),i分别为0,5,n,n+1,n+2#include#includetypedefintelemtype;//使用typedef目的是给变量一个易记且意义明确的新名字和简化一些比较复杂的类型声明。typedefstructnode//用结构体定义结点。{elemtypedata;structnode*next;}NODE;NODE*head,*p1,*p2;//声明指针。voidcreatlist()//创建链表。{head=p1=(NODE*)malloc(sizeof(NODE));//创建头结点和首元结点。inti;for(i=0;i<40;i=i+3)//定链表的初始值。{p2=(NODE*)malloc(sizeof(NODE));//创建一个新结点。p2->data=i;p1->next=p2;p1=p2;//首元结点的数据域存i的值。}p1->next=NULL;//尾结点的指针域为空。}voidoutput()//定义输出函数。{p1=head->next;while(p1!=NULL)//指针域不为空就执行循环体。{printf("%4d",p1->data);p1=p1->next;}printf("\n");}main()//主函数。{inti,j,k;creatlist();//创建链表函数的调用。printf("建立的链表为:");output();//输出函数的调用。printf("\n");printf("输入想查找第几个结点的指针:");scanf("%d",&i);if(i==0)//如果输入的i为0,则输出head的地址。printf("%p",head);for(j=0;j<14&&(head->next)!=NULL;j++){if(i>14||head->next==NULL)//如果输入的i大于14,或者指针域为空则返回NULL.{printf("该结点不存在!!");returnNULL;}if(j+1==i){printf("%p",head->next);//输出第i个结点的指针。}head=head->next;//指针后移。}}4.对第3题中带头结点单链表L的第i个结点前插入值为x的结点。插入成功,则输出插入后链表中的所有元素;若插入失败,则给出提示。实验测试数据基本要求:i分别为0,1,n,n+1,n+2;x=100#include#includetypedefintelemtype;//使用typedef目的是给变量一个易记且意义明确的新名字和简化一些比较复杂的类型声明。typedefstructnode//用结构体定义结点。{elemtypedata;structnode*next;}NODE;NODE*head,*p1,*p2,*p3,*P4;//声明指针。voidcreatlist()//创建链表。{head=p1=(NODE*)malloc(sizeof(NODE));//创建头结点和首元结点。inti;for(i=0;i<40;i=i+3)//定链表的初始值。{p2=(NODE*)malloc(sizeof(NODE));//创建一个新结点。p2->data=i;p1->next=p2;p1=p2;//首元结点的数据域存i的值。}p1->next=NULL;//尾结点的指针域为空。}intinsert(NODE*head,NODE*p3)//插入链表。{NODE*p4;intj,m,i;p3=p4=(NODE*)malloc(sizeof(NODE));printf("请输入你想插入的位置(1-14):");scanf("%d",&i);p4=head;for(j=1;j=NULL;j++,p4=p4->next)//循环条件。{if(p4->next==NULL||i>14||i<1){printf("结点不存在!原始链表为:");return0;}}if(i==0)//如果输入0则提示结点不存在。{printf("结点不存在!原始链表为:");return0;}p3->next=p4->next;//插入结点的指针域指向第i个结点的指针域。p4->next=p3;//i的前一个结点的指针域指向i。printf("请输入你想插入的数字:");scanf("%d",&m);p3->data=m;//将输入的数字存在插入结点的数据域。printf("插入数据后的链表为:");}voidoutput()//定义输出函数。{p1=head->next;while(p1!=NULL)//指针域不为空就执行循环体。{printf("%4d",p1->data);p1=p1->next;}printf("\n");}intmain()//主函数。{inti;creatlist();//创建链表函数的调用。printf("建立的链表为:");output();//输出函数的调用。insert(head,p3);output();//输出函数的调用。}5.删除第4题中带头结点单链表L的第i个元素结点。删除成功,则输出删除后链表中所有元素;若删除失败,则给出提示。实验测试数据基本要求:n为当前L的长度,i分别为0,5,n,n+1#include#includetypedefintelemtype;//使用typedef目的是给变量一个易记且意义明确的新名字和简化一些比较复杂的类型声明。typedefstructnode//用结构体定义结点。{elemtypedata;structnode*next;}NODE;NODE*head,*p1,*p2,*p3,*P4;//声明指针。voidcreatlist()//创建链表。{head=p1=(NODE*)malloc(sizeof(NODE));//创建头结点和首元结点。inti;for(i=0;i<40;i=i+3)//定链表的初始值。{p2=(NODE*)malloc(sizeof(NODE));//创建一个新结点。p2->data=i;p1->next=p2;p1=p2;//首元结点的数据域存i的值。}p1->next=NULL;//尾结点的指针域为空。}intqdelete(NODE*head,NODE*p3)//删除链表元素。{NODE*p4;intj,m,i;printf("请输入你想删除的位置(1-14):");scanf("%d",&i);p4=head;for(j=1;j=NULL;j++,p4=p4->next)//循环条件。{if(p4->next==NULL||i>14||i<1){printf("结点不存在!原始链表为:");return0;}}if(i==0)//如果输入0则提示结点不存在。{printf("结点不存在!原始链表为:");return0;}m=p4->data;p3=p4->next;//p3指向待删除的节点p4->next=p3->next;//删除节点i,也可写成p->next=p->next->nextfree(p3);//释放节点i的内存单元printf("删除数据后的链表为:");}voidoutput()//定义输出函数。{p1=head->next;while(p1!=NULL)//指针域不为空就执行循环体。{printf("%4d",p1->data);p1=p1->next;}printf("\n");}intmain()//主函数。{inti;creatlist();//创建链表函数的调用。printf("建立的链表为:");output();//输出函数的调用。qdelete(head,p3);output();//输出函数的调用。}6.构造并新建一个递增有序的单链表,插入一个值为x的元素,并保持其递增有序特性。实验测试数据基本要求:链表元素为(10,20,30,40,50,60,70,80,90,100),x分别为25,85,110和8#include#includetypedefintelemtype;//使用typedef目的是给变量一个易记且意义明确的新名字和简化一些比较复杂的类型声明。typedefstructnode//用结构体定义结点。{elemtypedata;structnode*next;}NODE;NODE*head,*p1,*p2,*p3,*p4,*q;//声明指针。voidcreatelist()//创建链表。{inti;head=p1=(NODE*)malloc(sizeof(NODE));//创建头结点和首元结点。for(i=10;i<=100;i+=10)//定链表的初始值。{p2=(NODE*)malloc(sizeof(NODE));//创建一个新结点。p2->data=i;p1->next=p2;p1=p2;//首元结点的数据域存i的值。}p1->next=NULL;//尾结点的指针域为空。}voidoutput()//定义输出函数。{inti;p3=head;while(p3->next!=NULL)//指针域不为空就执行循环体。{p3=p3->next;printf("%4d",p3->data);}printf("\n");}voidinsert(NODE*head)//定义插入数字函数。{intm;printf("输入你想插入的数字(回车结束):");scanf("%d",&m);p3=head;p4=head->next;while(p4!=NULL&&p4->data<=m)//p4不为空且p4的数据域小于m时,循环。{p3=p4;p4=p4->next;}if((q=(NODE*)malloc(sizeof(NODE)))==NULL)//为新的结点申请空间,如果为空则退出。exit;q->data=m;//将插入的数字存在新结点的数据域。q->next=p3->next;//将p3的后继赋给q的后继。p3->next=q;//将q赋给p3的后继。}intmain()//主函数。{printf("创建的链表为:");createlist();//创建链表函数的调用。output();//输出函数的调用。insert(head);//插入函数的调用。printf("插入数据后的链表为:");output();return0;} 四、实验总结与收获实验总结与收获:1)这次实验中,遇到了很多困难,太久没有接触C语言,很多C语言的知识都忘了,像函数的调用,函数的建立这些格式都不知道怎么使用,于是重新拿着C语言的书看了几天,由于以前C语言学得不太好,以后还得继续好好学C。2)刚开始知道顺序表就是建立数组,于是开始顺序表的实验做得比较快,新接触的链式表由于不知道怎么建立,去找了些例子来看明白了才会建表。3)这次试验学会了如何建立链式表,如何在链式表插入删除数据,如何建立与调用函数.4)在实验的调试修改过程中,学会了以前学C从来没学会的东西,感觉大一的C白学了,以后自己应该抓紧时间好好学习C语言为数据结构打好基础.
printf("%3d",a[n]);//输出插入数据前的顺序表;
}
printf("\n");
for(i=0;i<3;i++)
printf("请输入你想在哪个位置插入数据(1--%d)(回车结束):
",length+2);
scanf("%d",&m);
start:
if(m<1||m>length+2)
printf("error!
\n");
gotostart;//跳转到start;
else
printf("请输入你想插入的数字(回车结束):
scanf("%d",&k);
j=length-1;
a[j+2]=00;//给第12位赋值为0;
for(j=length-1;j>=m-1;j--)
a[j+1]=a[j];//表中元素后移一位;
a[m-1]=k;//将输入的数赋值给指定位置;
length++;//长度加一;
for(n=0;n<=length;n++)
printf("%3d",a[n]);//输出插入元素后的顺序表;
return0;
2.用C语言实现课本P26:
算法2.7(顺序表的合并算法);
La=(6,11,11,23);Lb=(2,10,12,12,21)
inta[4]={6,11,11,23},b[5]={2,10,12,12,21},c[8];//顺序表初始化;
inti=0,j=0,k=0;
while(i<=3&&j<=4)//循环条件;
if(a[i]<=b[j])//将a[i],b[j]中较小一个赋值给数组c[k],再自加;
c[k]=a[i],i++,k++;
c[k]=b[j],k++,j++;
while(i<=3)
while(j<=4)//剩余元素再赋给c[k];
c[k]=b[j],j++,k++;
printf("Aftercombine,theorderis:
for(k=0;k<=8;k++)
printf("%5d",c[k]);//输出合并后的顺序表;
3.构造并求带头结点单链表L中第i个结点的指针,若不存在,则返回NULL。
自定义初始链表长度n(n≥10),i分别为0,5,n,n+1,n+2
typedefintelemtype;//使用typedef目的是给变量一个易记且意义明确的新名字和简化一些比较复杂的类型声明。
typedefstructnode//用结构体定义结点。
elemtypedata;
structnode*next;
}NODE;
NODE*head,*p1,*p2;//声明指针。
voidcreatlist()//创建链表。
head=p1=(NODE*)malloc(sizeof(NODE));//创建头结点和首元结点。
inti;
for(i=0;i<40;i=i+3)//定链表的初始值。
p2=(NODE*)malloc(sizeof(NODE));//创建一个新结点。
p2->data=i;
p1->next=p2;
p1=p2;//首元结点的数据域存i的值。
p1->next=NULL;//尾结点的指针域为空。
voidoutput()//定义输出函数。
p1=head->next;
while(p1!
=NULL)//指针域不为空就执行循环体。
printf("%4d",p1->data);
p1=p1->next;
main()//主函数。
inti,j,k;
creatlist();//创建链表函数的调用。
printf("建立的链表为:
output();//输出函数的调用。
printf("输入想查找第几个结点的指针:
scanf("%d",&i);
if(i==0)//如果输入的i为0,则输出head的地址。
printf("%p",head);
for(j=0;j<14&&(head->next)!
=NULL;j++)
if(i>14||head->next==NULL)//如果输入的i大于14,或者指针域为空则返回NULL.
printf("该结点不存在!
!
returnNULL;
if(j+1==i)
printf("%p",head->next);//输出第i个结点的指针。
head=head->next;//指针后移。
4.对第3题中带头结点单链表L的第i个结点前插入值为x的结点。
插入成功,则输出插入后链表中的所有元素;若插入失败,则给出提示。
i分别为0,1,n,n+1,n+2;x=100
NODE*head,*p1,*p2,*p3,*P4;//声明指针。
intinsert(NODE*head,NODE*p3)//插入链表。
NODE*p4;
intj,m,i;
p3=p4=(NODE*)malloc(sizeof(NODE));
printf("请输入你想插入的位置(1-14):
p4=head;
for(j=1;j
=NULL;j++,p4=p4->next)//循环条件。
if(p4->next==NULL||i>14||i<1)
printf("结点不存在!
原始链表为:
if(i==0)//如果输入0则提示结点不存在。
p3->next=p4->next;//插入结点的指针域指向第i个结点的指针域。
p4->next=p3;//i的前一个结点的指针域指向i。
printf("请输入你想插入的数字:
p3->data=m;//将输入的数字存在插入结点的数据域。
printf("插入数据后的链表为:
intmain()//主函数。
insert(head,p3);
5.删除第4题中带头结点单链表L的第i个元素结点。
删除成功,则输出删除后链表中所有元素;若删除失败,则给出提示。
n为当前L的长度,i分别为0,5,n,n+1
intqdelete(NODE*head,NODE*p3)//删除链表元素。
printf("请输入你想删除的位置(1-14):
m=p4->data;
p3=p4->next;//p3指向待删除的节点
p4->next=p3->next;//删除节点i,也可写成p->next=p->next->next
free(p3);//释放节点i的内存单元
printf("删除数据后的链表为:
qdelete(head,p3);
6.构造并新建一个递增有序的单链表,插入一个值为x的元素,并保持其递增有序特性。
链表元素为(10,20,30,40,50,60,70,80,90,100),
x分别为25,85,110和8
NODE*head,*p1,*p2,*p3,*p4,*q;//声明指针。
voidcreatelist()//创建链表。
for(i=10;i<=100;i+=10)//定链表的初始值。
p3=head;
while(p3->next!
p3=p3->next;
printf("%4d",p3->data);
voidinsert(NODE*head)//定义插入数字函数。
intm;
printf("输入你想插入的数字(回车结束):
p4=head->next;
while(p4!
=NULL&&p4->data<=m)//p4不为空且p4的数据域小于m时,循环。
p3=p4;
p4=p4->next;
if((q=(NODE*)malloc(sizeof(NODE)))==NULL)//为新的结点申请空间,如果为空则退出。
exit;
q->data=m;//将插入的数字存在新结点的数据域。
q->next=p3->next;//将p3的后继赋给q的后继。
p3->next=q;//将q赋给p3的后继。
printf("创建的链表为:
createlist();//创建链表函数的调用。
insert(head);//插入函数的调用。
output();
四、实验总结与收获
实验总结与收获:
1)这次实验中,遇到了很多困难,太久没有接触C语言,很多C语言的知识都忘了,像函数的调用,函数的建立这些格式都不知道怎么使用,于是重新拿着C语言的书看了几天,由于以前C语言学得不太好,以后还得继续好好学C。
2)刚开始知道顺序表就是建立数组,于是开始顺序表的实验做得比较快,新接触的链式表由于不知道怎么建立,去找了些例子来看明白了才会建表。
3)这次试验学会了如何建立链式表,如何在链式表插入删除数据,如何建立与调用函数.
4)在实验的调试修改过程中,学会了以前学C从来没学会的东西,感觉大一的C白学了,以后自己应该抓紧时间好好学习C语言为数据结构打好基础.
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2