数据结构课程设计报告.doc

课程设计报告课程设计题目：链表的创建、插入、删除、修改学生姓名 专 业 计算机科学与技术班 级 学 号 指导教师 艾 2011年 9月 30日一、实验题目：实现链表的创建、插入、删除和修改任务：实现链表的创建、插入、删除、修改和输出 要求：建立一个简单的人机对话，创建、插入、删除、修改和输出功能可以根据需要选择使用。二、实验时间、地点：2011-12-26 2011-12-30、信工楼302三、实验目的本次课程设计的主要目的是综合运用所学的数据结构知识解决一个比较实际问题，侧重对链表、数组、字符串、图、树等相关内容的综合应用，使同学们能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下良好的基础。四、实验要求1. 了解数据结构及其分类、数据结构与算法的密切关系； 2. 熟悉各种基本数据结构及其操作，学会根据实际问题来选择数据结构； 3. 掌握设计算法的步骤和分析方法； 4. 掌握数据结构在排序和查找等常用算法中的应用。5. 独立完成；6 每个人需按照选题规则确定好自己的题目（注意不是多人完成一题，每人独立完成一题），不得以任何理由选择其他的题目，当然在完成自己的题目之后根据个人兴趣可以继续选做其他的题目；7课程设计完成后严格按照报告格式撰写课程设计报告，并于结束后的第三天上交到学习委员统一交给老师；8课程设计的成绩由两部分组成：程序检查成绩（40，每个功能占程序分的20%）报告检查成绩（40）平时考核（20%）五、实现思路链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。再c+中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下 class linkpublic:elemtype data;link *next;这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。void print(link*head) ;/链表结点的输出link*Locate(link*head,elemtype x);/链表的的查询void insert(link*head,elemtype x,elemtype y);/链表结点的插入void deletel(link*head,elemtype x);/链表结点的删除void change(link*p,elemtype x,elemtype y)；/链表的修改由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。流程图：i link*s,*p,*rProtected:PublicPublic:Ncoutdatacoutdata;p-next!=NULLlink*preturn pr-next=NULLs=new link YN Ycoutdata!=x)link*p,*qNhead-next=NULLs-next=p-nextp=NULLp=Locate(head,x)head-next=sL ink*p,*sq-next=p-next delete(p)q=p;YNcoutnextq-data=yq-data=xq!=NULLNYNYAct=2M=eM=fAct=1Int n,act主函数流程图NYN34567Break;Gotoloop1q=nullCase1:NCase2:coutx在表中，已找到！coutx不在表中。找不到！Y.Break;Goto loop1case 7:system(CLS); /清屏a.print(p);Case7:清屏，goto loop2 break;Case6;六、实现过程#include#include#include#define elemtype intclass linkpublic:elemtype data;link *next;class linklistprotected:link*head;public:link*rcreat()link*s,*p,*r;elemtype i;couti;p=r=new link;p-next=NULL;while(i)s=new link;s-data=i;r-next=s;r=s;cini;r-next=NULL; return p; void print(link*head) link*p; p=head-next; while(p-next!=NULL) coutdata; p=p-next; coutdata; coutendl; link*Locate(link*head,int x) link*p; p=head; int j=0; while(p!=NULL)&(jnext;j+; return p; void deletel(link*head,elemtype x) link*p,*q; q=head; p=head-next; while(p!=NULL)&(p-data!=x) q=p; p=p-next; if(p=NULL)coutnext=p-next; delete(p); void insert(link*head,int x,elemtype y) link*p,*s; s=new link; s-data=y; if(head-next=NULL) head-next=s; s-next=NULL; p=Locate(head,x); if(p=NULL) coutnext=p-next; p-next=s; void change(link*p,elemtype x,elemtype y)link*q;q=p-next;while(q!=NULL)if(q-data=x)q-data=y;q=q-next;int count(link*h)link*p;int n=0;p=h-next;while(p!=NULL)n+;p=p-next;return n;void main()int n,act;char m;elemtype x,y;link*p,*q; linklist a;p=a.rcreat();a.print(p);loop1:coutm;if(m=e) /根据提示选择操作act=1;if(m=f)act=2;if(m=g)act=3;if(m=h)act=4;if(m=i)act=5; if(m=q)act=6; if(m=c)act=7;switch(act)case 1:coutx;q=a.Locate(p,x);if(q=NULL)coutx不在表中。找不到！endl;else coutx在表中，已找到！endl;goto loop1;break;case 2:couty;a.deletel(p,y);a.print(p);goto loop1;break; case 3:coutx;couty;a.insert(p,x,y);a.print(p);goto loop1;break;case 4:coutxy;a.change(p,x,y);a.print(p);goto loop1;break;case 5:n=a.count(p);cout链表中结点个数为：nendl;goto loop1; break;case 6:system(CLS); /清屏goto loop2; break;case 7:system(CLS); /清屏a.print(p);goto loop1; break;loop2:;七、实验总结（分析程序的得与失）1、经过运行本程序能够进行链表的创建、插入、删除、修改、统计等功能，已具备链表试验的功能，基本达到了题目的要求。2、在编写程序的过程中，对字符的判断做标记，用switch语句选择运用，使结构更加清晰，能够用goto语句进行循环。使程序的可执行性更强。3、本程序还是有一定缺陷，比如运行界面不够美观、但基本达到了人机交互的功能达到要求4、对本程序自我感觉人机交互做的比较好，能够做到根据选择进行操作，主要依靠循环进行实现，同时我也加入了清屏功能，使操作更加人性化。5、本程序的但还是比较单一，功能不是很完善，可以对界面进行设计，是其更加美观。八、心得体会课程设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。通过本次为期一周的课程设计课，我有很多感触，从我拿到题目开始到完全做出程序，我经历了一个波折的一周，但是这周我受益