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

数据结构课程设计实验报告 题 目 双向链表 学 院 专 业 计算机科学与技术 班 级 学 号 学生姓名 指导教师 编写日期 2010-7-16 目录1. 问题分析.31.1基本要求.31.2分析过程.32. 数据结构描述.33. 算法设计.43.1算法1：双向链表的建立.43.2算法2：双向链表的查找43.3算法3：双向链表的插入.53.4算法4：双向链表的删除.54. 程序清单65. 程序运行结果106. 总结11l 1.问题分析1.1【基本要求】：建立双向链表，并进行插入，查找，删除等操作。1.2【分析过程】：先通过创建函数建立双向链表，由文本文件提供数据。可以调用查找函数，查找与e值相同的结点是否存在；也可以通过插入函数，在第i个结点前插入值为e的结点，并且调节指针的变化；也可以调用删除函数，删除第i个结点，调节好指针，最后通过保存函数保留数据到文本文件中。l 2.数据结构描述#include#includeusing namespace std;typedef struct dulnode int data; struct dulnode *prior; struct dulnode *next; dulnode,*dulinklist;l 3.算法设计3.1算法1：创建双向链表status create_dul(dulinklist &l) /*利用尾插法建立头带头结点的双向链表 */ l=(dulinklist)malloc(sizeof(dulnode); /* 生成头结点 */ l-prior=null; l-next=null; /* 头结点的指针域初始值为空 */ l-data=-1; q=l; /* 尾指针初始指向头结点 */ file* fp; /* 定义文件指针的形式 */ if(fp=fopen(f:test1.txt,r+)=null) /* 打开文本文件 */ printf(cannot open file!n); exit(0); int n; fscanf(fp,%d,&n); for(i=0;idata); /* 在文件读取结点的数据 */ p-next=null; /* 新结点指针域为空 */ p-prior=q; q-next=p; /* 尾结点指针域指向新结点 */ q=p; /* q指针后移，始终指向尾指针 */ fclose(fp); /* 关闭文本文件 */3.2算法2：双向链表的查找stadus locateelem_dul(dulinklist l,elemtype e) /* 查找双线链表中第一个值为e的结点位置*/ p=l-next; /* p指向第一个结点 */ j=1; /* j表示结点位置 */ while(p-data!=e)&p) p=p-next; +j; /* 寻找第一个值为e的结点位置 */ if(!p) return -1; else return 1;3.3算法3：双向链表的插入status listinsert_dul(dulinklist &l,int i,elemtype e) /* 在双向链表l中的第i个位置之前插入新结点s */ p=l; /* p指向头结点 */ j=0; /* j表示结点位置 */ while(p&(jnext; +j; /* 寻找第i-1个结点位置 */ if(!p|ji-1) return error; /* 在l中确定插入位置，p=null或ji-1时，即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode) return error; /* 动态生成新结点失败，则返回错误 */ s-data=e; /* 给新结点的数据域赋值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在双向链表中插入新结点时指针的变化 */ return 0;3.4算法4：双向链表的删除status listdelete_dul(dulinklist &l,int i,elemtype &e) /* 在双向链表l中，删除第i个结点 */ p=l-next; /* p指向第一个结点 */ int j=1; /* j表示结点位置 */ while(p&(jnext; +j; /* 寻找第i个结点 */ if(!p|ji) return error; /* 在l中确定第i个元素的位置指针p，p=null，即第i个元素不存在 */ e=p-data; /* 把指针p的数据域的值赋给e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在双向链表中删除结点时指针的变化 */ free(p); /* 把结点p删掉 */ return 0;l 4.程序清单#include#includeusing namespace std;typedef struct dulnode int data; /* 数据域 */ struct dulnode *prior; /* 指向前驱的指针域 */ struct dulnode *next; /* 指向后继的指针域 */dulnode,*dulinklist;void create_dul(dulinklist &l) /*利用尾插法建立头带头结点的双向链表 */ dulinklist p,q; int i; l=(dulinklist)malloc(sizeof(dulnode); /* 生成头结点 */ l-prior=null; l-next=null; /* 头结点的指针域初始值为空 */ l-data=-1; q=l; /* 尾指针初始指向头结点 */ file* fp; /* 定义文件指针的形式 */ if(fp=fopen(h:test1.txt,r+)=null) /* 打开文本文件 */ printf(cannot open file!n); exit(0); int n; fscanf(fp,%d,&n); for(i=0;idata); /* 在文件读取结点的数据 */ p-next=null; /* 新结点指针域为空 */ p-prior=q; q-next=p; /* 尾结点指针域指向新结点 */ q=p; /* q指针后移，始终指向尾指针 */ fclose(fp); /* 关闭文本文件 */dulinklist listinsert_dul(dulinklist &l,int i,int e) /* 在双向链表l中的第i个位置之前插入新结点s */ dulinklist p,s; p=l; /* p指向头结点 */ int j=0; /* j表示结点位置 */ while(p&(jnext; +j; /* 寻找第i-1个结点位置 */ if(!p|ji-1) return null; /* 在l中确定插入位置，p=null或ji-1时，即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode) return null; /* 动态生成新结点失败，则返回错误 */ s-data=e; /* 给新结点的数据域赋值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在双向链表中插入新结点时指针的变化 */ return 0;dulinklist listdelete_dul(dulinklist &l,int i,int &e) /* 在双向链表l中，删除第i个结点 */ dulinklist p; p=l-next; /* p指向第一个结点 */ int j=1; /* j表示结点位置 */ while(p&(jnext; +j; /* 寻找第i个结点 */ if(!p|ji) return null; /* 在l中确定第i个元素的位置指针p，p=null，即第i个元素不存在 */ e=p-data; /* 把指针p的数据域的值赋给e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在双向链表中删除结点时指针的变化 */ free(p); /* 把结点p删掉 */ return 0;int locateelem_dul(dulinklist l,int e) /* 查找双线链表中第一个值为e的结点位置*/ dulinklist p; int j; p=l-next; /* p指向第一个结点 */ j=1; /* j表示结点位置 */ while(p-data!=e)&p) p=p-next; +j; /* 寻找第一个值为e的结点位置 */ if(!p) return -1; /* 返回第一个值为e的结点位置 */ else return 1;void print_dul(dulinklist l) /* 打印双向链表l */ dulinklist p; p=l; /* p指向头结点 */ while(p) printf(% d,p-data); p=p-next; /* 把双向链表中的数据都打印出来 */void save_dul(dulinklist l) file* fp; if(fp=fopen(h:test2.txt,w+)=null) printf(cannot open file!n); exit(0); while(l)fprintf(fp,%d ,l-data);l = l-next;void main() dulinklist l; int i,e,x; int pos;create_dul(l); /* 调用双向链表建立函数 */ print_dul(l); /* 调用双向链表的打印函数 */ while(1) printf(input x to choose (1.查找,2.插入,3.删除,4.0ver ): n); scanf(%d,&x); switch(x)case 1:printf(n please input the data you want to locate: n); scanf(%d,&e); /* 输入要查找的值 */ pos=locateelem_dul(l,e); /* 调用双向链表的查找函数 */ if(pos=-1) printf(the data is not found! n); else printf(the data is found! n);break;case 2: printf(please input the position you want to insert: n); scanf(%d,&i); /* 输入要插入的位置 */ printf(please input the data you want to insert: n); scanf(%d,&e); /* 输入新结点的数据 */ listinsert_dul(l,i,e); /* 调用双向链表的插入函数 */ print_dul(l); break; /* 调用双向链表的打印函数 */ case 3: printf(n please input the position you want to delete: n); scanf(%d,&i); /* 输入要删除结点的位置 */ listdelete_dul(l,i,e); /* 调用双向链表的删除函数 */ print_dul(l);break; /* 调用双向链表的打印函数 */ case 4: save_dul(l); exit(0); l 5.程序运行结果l 6.总结: 通过此次数据结构的课程设计，我对程序的编程，编译，执行等有了更深的认识。理解到思路对于一个