数据结构课程设计-双向链表的操作.doc

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 双向链表 专业 计算机科学与技术 班级 10计本2班 学号10012133 姓名 联系方式 指导教师20 11 年 12 月 29日目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、稀疏矩阵各种运算的性质变换4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：4.3、测试过程中遇到的主要问题及采取的解决措施：5、时间复杂度的分析：6、源程序清单和执行结果7、c程序设计总结8、致谢9、参考文献1、数据结构课程设计任务书1.1、题目 双向链表的操作1.2、要求1. 建立双向链表l，含n个结点且按整数值递增排列的（输入任意）；2. 删除双向链表中多余的值相同的元素 3. 求出的长度 4. 将双向链表就地逆置 5. 向双向链表中插入值，插入后双向链表仍有序2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：输入矩阵1任意输入建立双向链表排序删除相同元素输出当前列表和长度插入删除相同元素输出当前列表和长度逆置并输出3、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；3.1、程序中所采用的数据结构及存储结构的说明为单向链表增加一个指向前趋的指针，则可以构成双向链表/-双向链表存储表示-typedef struct lnodeint data;struct lnode * next,*prior;/设置分别指向前后的指针lnode,*linklist;在此，节点inode中有两个指针域，其一指向直接后继，另一指向直接前趋。3.2、算法的设计思想a) 双向链表创建 创建头结点，通过插入，实现有序排列。b）插入插入时指向头结点先进行数据域的大小比较，在符合条件前向后依次比较，然后插入时先将其指针分别指向前趋和后继，再将其前趋的next，和后继的prior指向该节点c) 删除相同元素遍历链表，相同时删除节点，并判断是否是尾节点。 d）求长度输出当前链表的l头节点记录的表长。 e）逆置指向最后一个节点，将其重新定义为头结点，从后往前逆置各节点。4、调试与测试：4.1、调试方法与步骤：第一步：随机输入创建双向链表；第二步：通过删除操作完成其创建，并输出；第三步：求出长度，插入输出；第四步：逆置并输出。4.2、测试结果的分析与讨论：（测试要写出测试用例及每个用例结果的的截图）5、时间复杂度的分析：时间复杂度为 o。6、 源程序清单和执行结果#includeusing namespace std;typedef struct lnodeint data;struct lnode * next,*prior;lnode,*linklist;void create_link(linklist & l); /创建有序双向链表void insert_link(linklist & l,int x); /插入x到链表lvoid show_link(const linklist & l); /显示链表int length_link(const linklist & l) return l-data; ; /返回链表长void reverse_link(linklist & l); /逆置链表void delete_same_link(linklist & l); /删除相同元素int main() linklist h; cout输入链表中的元素 :; create_link(h); /创建有序双向链表 cout创建的链表为:; show_link(h); cout链表长度为:length_link(h)endl; cout要插入的数 :; int x; while(cinx) insert_link(h,x); /插入元素到链表 cout当前链表为：; show_link(h); cout当前链表长度为：length_link(h)endl; cout要插入的数 :; cout将链表逆置后为:; reverse_link(h); /逆置链表 show_link(h); delete_same_link(h); /删除相同元素 cout删除链表中相同的元素后链表为：; show_link(h); cout当前链表长度为：length_link(h)data=0; s-next=null; s-prior=null; l=s; while(cinx) insert_link(l,x); /x元素插入链表l cin.clear(); while(cin.get()!=n) continue;void insert_link(linklist & l,int x) /x元素插入链表l lnode *p=l-next,*q=l; /p指向当前结点，q指向当前结点的前驱结点 lnode *s=new lnode; /生成插入的结点s s-data=x; while(p!=null) if(p-data data) /插入结点的元素比链表当前结点元素大时，p、q指向下一个结点 q=q-next; p=p-next; else /当前结点的元素大于插入结点的元素时 s-prior=p-prior; /将s插入到p之前 s-next=p; p-prior-next=s; p-prior=s; +l-data; /表长+1 break; if(p=null) /链表为空或者插入结点元素最大时直接将结点插入表尾 s-next=q-next; q-next=s; s-prior=q; +l-data; void show_link(const linklist & l) /显示链表 lnode *p=l-next; while(p!=null) coutdatanext; coutnext,*q=l,*s; while(p-next!=null) p=p-next; /将p定位到最后一个结点 l-next=p; /重定位头结点指针指向链表最后一个元素 while(p!=l) /逆置各个结点 s=p-prior; p-next=s; p-prior=q; q=p; p=s; q-next=null; /新链表的最后一个结点指向nullvoid delete_same_link(linklist & l) /删除相同元素 lnode *p=l-next,*s=p-next; /p指向当前结点，s指向当前结点的后继 while(s!=null) /遍历链表 if(p-data = s-data) /相等时删除结点 p-next=s-next; delete s; s=p-next; if(s!=null) s-prior=p; /当p不是尾结点。因为p为尾结点时s=null -l-data; else p=p-next; /后移指针 s=s-next; 7、c程序设计总结在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写