数据结构课程设计_双向链表

《数据结构课程设计_双向链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计实验报告题目双向链表学院专业计算机科学与技术班级学号学生姓名指导教师编写日期2010-7-16目录111.问题分析……………………………………………….31.1基本要求…………………………………………………..31.2分析过程…………………………………………………..32.数据结构描述………………………………………….33.算法设计……………………………………………….43.1算法1：双向链表的建立………………………………..43.2算法2：双向链表的查找…………………………………43.3算法3：双向链表的插入………………………………..53.4算法4：双向链表的删除…

2、……………………………..54.程序清单………………………………………………65.程序运行结果…………………………………………106.总结……………………………………………………11l1.问题分析1.1【基本要求】：11建立双向链表，并进行插入，查找，删除等操作。1.2【分析过程】：先通过创建函数建立双向链表，由文本文件提供数据。可以调用查找函数，查找与e值相同的结点是否存在；也可以通过插入函数，在第i个结点前插入值为e的结点，并且调节指针的变化；也可以调用删除函数，删除第i个结点，调节好指针，最后通过保存函数保留数据到文本文件中。l2.数据结构描述#include#i

3、ncludeusingnamespacestd;typedefstructdulnode{intdata;structdulnode*prior;structdulnode*next;}dulnode,*dulinklist;l3.算法设计3.1算法1：创建双向链表11statuscreate_dul(dulinklist&l)/*利用尾插法建立头带头结点的双向链表*/{l=(dulinklist)malloc(sizeof(dulnode));/*生成头结点*/l->prior=NULL;l->next=NULL;/*头结点的指针域初始值为空*/l->data=-1;q

4、=l;/*尾指针初始指向头结点*/FILE*fp;/*定义文件指针的形式*/if((fp=fopen("F:\test1.txt","r+"))==NULL)/*打开文本文件*/{printf("cannotopenfile!");exit(0);}intn;fscanf(fp,"%d",&n);for(i=0;idata);/*在文件读取结点的数据*/p->next=NULL;/*新结点指针域为空*/p->prior=q;q->next=p;/*尾结点指

5、针域指向新结点*/q=p;/*q指针后移，始终指向尾指针*/}fclose(fp);/*关闭文本文件*/}3.2算法2：双向链表的查找staduslocateelem_dul(dulinklistl,elemtypee)/*查找双线链表中第一个值为e的结点位置*/{p=l->next;/*p指向第一个结点*/j=1;/*j表示结点位置*/while((p->data!=e)&&p){p=p->next;++j;}/*寻找第一个值为e的结点位置*/if(!p)return-1;11elsereturn1;}3.3算法3：双向链表的插入statuslistinsert_dul(dulinkli

6、st&l,inti,elemtypee)/*在双向链表l中的第i个位置之前插入新结点s*/{p=l;/*p指向头结点*/j=0;/*j表示结点位置*/while(p&&(jnext;++j;}/*寻找第i-1个结点位置*/if(!p

7、

8、j>i-1)returnERROR;/*在l中确定插入位置，p=NULL或j>i-1时，即插入位置不合法*/if(!(s=(dulinklist)malloc(sizeof(dulnode))))returnERROR;/*动态生成新结点失败，则返回错误*/s->data=e;/*给新结点的数据域赋值*/s->next=p->next

9、;p->next->prior=s;s->prior=p;p->next=s;/*在双向链表中插入新结点时指针的变化*/return0;}3.4算法4：双向链表的删除statuslistdelete_dul(dulinklist&l,inti,elemtype&e)/*在双向链表l中，删除第i个结点*/{p=l->next;/*p指向第一个结点*/intj=1;/*j表示结点位置*/while(p&&(j