计算机软件基础实验报告2.doc

1、北京联合大学实验报告课程（项目）名称： 计算机软件技术基础（实验2） 学 院： 自动化学院 专 业：电气工程与自动化 班 级： 0910030101 学 号： 2009100301126 姓 名： 林驷淇 成 绩： 2011年4月24日一、任务与目的1实验目的(1)掌握链表的概念。(2)熟练掌握线性表的链式存储结构。(3)熟练掌握线性表在链式存储结构上的运算。2实验内容(1)编写算法，根据用户输入的整数创建一个带头结点的单链表，-1作为输入数据的结束符。测试要求：建立空链表、非空链表的情况下测试程序运行情况。 (2)编写算法，在带有头结点的单链表中查找序号为i的结点和值为x的结点并输出。测试要

2、求：在空链表、i与x在链表头、i与x在链表尾、i与x在链表中间、i与x在链表中不存在的情况下测试程序运行情况。 (3)己知单链表中的元素非递减有序排列，编写算法删除单链表中值相同的多余的元素。测试要求：在空链表、有1组相同元素、有2组连续相同元素、有2组以上不连续相同元素的情况下测试程序运行情况。(4)已知单链表中的数据元素递增有序，编写算法，给定的两个数据Min和Max,删除表中值在min与max之间的结点。测试要求：在空链表、max小于链表第1个元素值、min大于链表最后1个元素值、min与max在链表中间的情况下测试程序运行情况。二、原理（条件）Visual C+6.0 三、内容与步骤(

3、1)编写算法，根据用户输入的整数创建一个带头结点的单链表，-1作为输入数据的结束符。测试要求：建立空链表、非空链表的情况下测试程序运行情况。测试数据为：10， 9， 8， 7， 6， 5， 4， 3， 2， 1主函数内的代码：linklist *createlist()int t;linklist *head,*s,*r; /s为新建结点，r为尾结点head=(linklist*)malloc(sizeof(linklist);/开辟空间，建立一个头结点r=head;printf(请输入数字序列，产生单链表，以-1结束。n);scanf(%d,&t);while(t!=-1)s=(linkli

4、st*)malloc(sizeof(linklist);s-data=t;r-next=s;r=s;scanf(%d,&t);r-next=NULL;return head;运行结果：(2)编写算法，在带有头结点的单链表中查找序号为i的结点和值为x的结点并输出。测试要求：在空链表、i与x在链表头、i与x在链表尾、i与x在链表中间、i与x在链表中不存在的情况下测试程序运行情况。主函数内的代码：void findi(linklist *head) /查找结点为i的值linklist *p,*q;int i=0,j=0;printf(输入要查找的结点：n);scanf(%d,&i);if(i=1)q

5、=head-next;else p=head-next;j=1;while(p!=NULL)p=p-next;j+;if(i=j) q=p;break;if(p=NULL)printf(超出范围，不存在);else printf(查找的元素为：); printf(%dn,q-data);测试数据：查找结点为3的值运行结果：void findx(linklist *head) /查找值为x的结点linklist *p;int ch;int j=0;printf(请输入要查找的数值:n);scanf(%d,&ch);p=head-next;j=1;while(p!=NULL&p-data!=ch)

6、 p=p-next;j+;if(p=NULL)printf(你所输入的值不存在！n);elseprintf(第%d个元素为%dn,j,p-data);测试数据：查找值为3的值运行结果：(3)己知单链表中的元素非递减有序排列，编写算法删除单链表中值相同的多余的元素。测试要求：在空链表、有1组相同元素、有2组连续相同元素、有2组以上不连续相同元素的情况下测试程序运行情况。主函数内的代码：linklist *deld(linklist *head)/删除连续相同元素 linklist *p,*q; p=head-next;printf(删除后链表为:n); if(p=NULL) return hea

7、d; else while(p-next!=NULL) q=p-next; if(p-data=q-data) p-next=q-next; free(q); else p=p-next; q=q-next; return head;测试数据：12 45 78 78 96 10 11 11 25 26 28 28 35 36 48 5 5 6 8 9 10 11 12 12 35 38 65 65 78 89运行结果：(4)已知单链表中的数据元素递增有序，编写算法，给定的两个数据Min和Max,删除表中值在min与max之间的结点。测试要求：在空链表、max小于链表第1个元素值、min大于链表

8、最后1个元素值、min与max在链表中间的情况下测试程序运行情况。主函数内的代码：linklist *del2(linklist *head) /删除链表中的min与max之间的元素linklist *p,*q1,*q2=NULL;int max=0,min=0;printf(请输入min和maxn);scanf(%d%d,&min,&max);printf(删除后链表为:n); if(head-next=NULL)return head; if(head-next-datamax)return head;else p=head;while(p-next!=NULL&p-next-datane

9、xt; if(p-next=NULL)return head;else q1=p-next;q2=q1-next; while(q2!=NULL&q2-datanext; p-next=q2;while(q1!=q2)p=q1;q1=q1-next;free(p);return head;测试数据：12 15 18 23 45 78 min为15 max为23运行结果：四、完整程序#include/printf和scanf提供头文件#include/malloc和free提供头文件typedef int datatype;/定义数据元素的类型，命名为datatypetypedef struct

10、 nodedatatype data;struct node *next;linklist;/定义结点类型，命名为linklistlinklist *createlist()int t;linklist *head,*s,*r; /s为新建结点，r为尾结点head=(linklist*)malloc(sizeof(linklist);/开辟空间，建立一个头结点r=head;printf(请输入数字序列，产生单链表，以-1结束。n);scanf(%d,&t);while(t!=-1)s=(linklist*)malloc(sizeof(linklist);s-data=t;r-next=s;r=

11、s;scanf(%d,&t);r-next=NULL;return head;void printnode(linklist *head) /输出程序linklist *r;r=head-next;if(r=NULL)printf(输入为空n);while(r!=NULL)printf(%dt,r-data);r=r-next;printf(n输出结束n);void findi(linklist *head) /查找结点为i的值linklist *p,*q;int i=0,j=0;printf(输入要查找的结点：n);scanf(%d,&i);if(i=1)q=head-next;else p

12、=head-next;j=1;while(p!=NULL)p=p-next;j+;if(i=j) q=p;break;if(p=NULL)printf(超出范围，不存在);else printf(查找的元素为：); printf(%dn,q-data);void findx(linklist *head) /查找值为x的结点linklist *p;int ch;int j=0;printf(请输入要查找的数值:n);scanf(%d,&ch);p=head-next;j=1;while(p!=NULL&p-data!=ch) p=p-next;j+;if(p=NULL)printf(你所输入的

13、值不存在！n);elseprintf(第%d个元素为%dn,j,p-data);linklist *deld(linklist *head)/删除连续相同元素 linklist *p,*q; p=head-next;printf(删除后链表为:n); if(p=NULL) return head; else while(p-next!=NULL) q=p-next; if(p-data=q-data) p-next=q-next; free(q); else p=p-next; q=q-next; return head;linklist *del2(linklist *head) /删除链表

14、中的min与max之间的元素linklist *p,*q1,*q2=NULL;int max=0,min=0;printf(请输入min和maxn);scanf(%d%d,&min,&max);printf(删除后链表为:n); if(head-next=NULL)return head; if(head-next-datamax)return head;else p=head;while(p-next!=NULL&p-next-datanext; if(p-next=NULL)return head;else q1=p-next;q2=q1-next; while(q2!=NULL&q2-datanext; p-next=q2;while(q1!=q2)p=q1;q1=q1-next;free(p);return head;void main()五、结论通过此次试验了解的链表的创建，运用了链表的删除和查找功能的实用。也更加强和巩固了C语言中构造函数的运用。六、评语