数据结构课程设计之双向链表操作讲解

1、EAST CHINA INSTITUTE OF TECHNOLOGY数据结构课程设计实验报告之双向链表的相关操作专业：计算机信息管理姓名：陶鹏鹏学号：201140130241教师：吴志强时间：2013.1.4目录1. 问题分析 .11.1基本要求.11.2 分析过程 .12. 数据结构描述 .13. 算法设计 .23.1 算法 1 ：双向链表的建立 .23.2 算法 2：双向链表的查找 . 23.3 算法 3：双向链表的插入 .33.4 算法 4：双向链表的删除 .34. 程序具体步骤 . 45. 程序运行结果 .106. 总结 . .101. 问题分析1.1 【基本要求】 ： 建立双向链表，

2、并进行插入，查找，删除等 操作。1.2 【分析过程】 ： 先通过创建函数建立双向链表，由文本文件 提供数据。可以调用查找函数， 查找与 e 值相同的结点是否存在； 也可以通过插入函数， 在第 i 个结点前插入值为 e 的结点，并且 调节指针的变化；也可以调用删除函数，删除第 i 个结点，调节 好指针，最后通过保存函数保留数据到文本文件中。2. 数据结构描述#include#includeusing namespace std;typedef struct dulnodeint data;struct dulnode *prior;struct dulnode *next;dulnode,*du

3、linklist;3. 算法设计3.1 算法 1：创建双向链表status create_dul(dulinklist &l)/*双向链表 */利用尾插法建立头带头结点的l-prior=NULL; l-next=NULL; l-data=-1; q=l; /* FILE* fp; /*/* 头结点的指针域初始值为空 */ 尾指针初始指向头结点 */定义文件指针的形式 */l=(dulinklist)malloc(sizeof(dulnode); /*生成头结点 */if(fp=fopen(F:test1.txt,r+)=NULL); /* 打开文本文件*/printf(cannot open

4、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; /* qfclose(fp); /*/* 在文件读取结点的数据 */ 新结点指针域为空 */尾结点指针域指向新结点 */ 指针后移，始终指向尾指针 */关闭文本文件 */3.2 算法 2：双向链表的查找stadus locateelem_dul(dulinklist l,elemtype e) ;/*中第一个值为 e 的结点位置 */查找双线链表p=l-next;/* pj=1;/* j指向第一个

5、结点 */ 表示结点位置 */while(p-data!=e)&p)p=p-next;寻找第一个值为 e 的结点位置 */+j; /*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;

6、 /*在 I 中确定插入位置，p=NULL或ji-1 时，即插入位置不合法 */if(!(s=(duIinkIist)maIIoc(sizeof(duInode)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 IistdeIete_duI(duIinkIist &I,int i,eIemtype &e);/*表

7、I 中，删除第 i 个结点 */p=I-next;/* pint j=1;/* jwhiIe(p&(jnext;指向第一个结点 */表示结点位置 */+j;/*寻找第 i 个结点 */if(!p|ji) return ERROR; /*置指针p, p=NULL即第i个元素不存在*/在 l 中确定第 i 个元素的位e=p-data;/*p-prior-next=p-next; p-next-prior=p-prior;针的变化 */free(p);/*把指针 p 的数据域的值赋给 e */*在双向链表中删除结点时指把结点 p 删掉 */return 0;4. 程序具体步骤#include std

8、io.h#include stdlib.h typedef int elemtype;typedef struct lnode /定义结点类型elemtype data;struct lnode *next;struct lnode *prior;lnode,*linklist;int initlist(linklist &L) /初始化单链表L=(linklist)malloc(sizeof(lnode); /表头附加结点if(!L) exit(-2);L-next=L;L-prior=L;return 1;/ 初始化了一个空表void createlist(linklist &L) /尾插

9、法生成双向循环链表int x;linklist q=L;printf(请输入要插入元素的值(输入0结束):n); scanf(%d,&x);while(x)linklist p=(linklist)malloc(sizeof(lnode);p-data=x;q-next=p;L-prior=p;p-prior=q;p-next=L;q=p;scanf(%d,&x);void shuchulist(linklist &L) / 遍历有头结点的双向循环链表linklist p=L-next;while(p-next!=L)printf(%4d,p-data); p=p-next;printf(%4

10、d,p-data);printf(n);int lengthlist(linklist L)/ 通过链表的遍历来统计长度 linklist p=L-next;int count=0;while(p!=L)p=p-next;count+;return count;int listdelete_i(linklist &L,int i)/ 删除带头结点的双向循环链表中第 i 个元素linklist p=L;int j=0;if(ilengthlist(L)return 0;while(jnext; +j; p-prior-next=p-next;/ 删除结点 p free(p);/ 释放结点 pre

11、turn 1;int listdelete_x(linklist &L,elemtype x)/ 删除值为 x 的元素 linklist p=L-next,q;int i=0;while(p!=L)if(p-data=x)q=p-next;p-next-prior=p-prior;p-prior-next=p-next;free(p);p=q;+i;else p=p-next;return i;void paixu(linklist L)/将链表排成非递减链表int t;linklist p;for(int i=1;inext;for(int j=0;jdatap-next-data) t=p

12、-data; p-data=p-next-data; p-next-data=t; p=p-next;void linklistinsert(linklist &L,elemtype e)/ 在非递减有序双向循环链表 中实现插入元素 e 仍有序linklist p=L-next;linklist q=(linklist)malloc(sizeof(lnode);q-data=e;if(L-prior-dataprior-next=q;q-prior=L-prior;q-next=L;L-prior=q;else while(p-datanext;/ 把 e 插到第一个大于或等于它的元素之前 p

13、-prior-next=q;q-prior=p-prior; q-next=p; p-prior=q;int panduan(linklist L)/ 判断双向循环链表中元素是否对称 linklist p=L-next,q=L-prior;if(lengthlist(L)%2) while(p-data=q-data&p!=q) p=p-next;q=q-prior; if(q=p) return 1;else return 0;else while(p-data=q-data&p-next!=q) p=p-next;q=q-prior; if(p-data=q-data) return 1;

14、else return 0;void jioushu(linklist L)/把链表中奇数放到偶数之前linklist p=L-next,q,s;s=L-prior; while(p!=s) if(p-data%2) p=p-next;else q=p-next; p-prior-next=p-next; p-next -prior=p-prior;/ 链表中取出p-prior=L-prior;L-prior-next=p;p-next=L;L-prior=p;p=q;void main（）linklist La;int menu,flag,i,x,c;doprintf（制作人：陶鹏鹏 n）;

15、printf（学 号： 201140130241n）;printf（专 业：计算机信息管理 n）;printf（指导老师：吴志强 n）;printf（n）; printf（n）;printf（1. 利用尾插法建立双向循环链表链表 n）;printf（2. 遍历双向循环链表 n）;printf（3. 双向循环链表中删除一个指定元素 n）;printf（4. 在非递减有序双向循环链表中实现插入元素 e 仍有序 n）;printf（5. 判断双向循环链表中元素是否对称若对称返回 1 否则返回 0n）;printf（6. 设元素为正整型 , 实现算法把所有奇数排列在偶数之前 n）;printf（0.

16、退出 n）;printf（n 请输入所选菜单 （0-6）: ）;scanf（%d,&menu）;switch（menu）case 1: initlist（La）;createlist（La）;break;case 2: printf（ 链表中的元素为 :n）;shuchulist（La）;break;case 3: printf（ 请选择删除方式： 1 删除值为 x 的结点 2 删除第 i 个结点 ）;scanf（%d,&c）;if（c=1）printf（ 请输入要删除元素的值 : ）; scanf（%d,&x）; flag=listdelete_x（La,x）;if（flag）printf（

17、 删除成功 !n）;printf（ 删除后的链表为 :n）; shuchulist（La）;else printf（ 删除失败 !n）;else if(c=2)printf( 请输入要删除的位置 : ); scanf(%d,&i); flag=listdelete_i(La,i);if(flag) printf( 删除成功 !n); printf( 删除后的链表为 :n); shuchulist(La);else printf( 删除失败 !n);break;:n);case 4: printf( 把原始链表初始化为非递减有序列表为 paixu(La); shuchulist(La);prin

18、tf( 请输入要插入的元素的值 : ); scanf(%d,&x);linklistinsert(La,x);printf( 插入后的链表为 :n); shuchulist(La);break;case 5: flag=panduan(La);if(flag)printf( 链表对称 !n);elseprintf( 链表不对称 !n);break;case 6: printf( 排列之前为 :n);shuchulist(La);jioushu(La);printf( 排列之后为 :n); shuchulist(La); break;case 0: exit(0);while(menu);5. 程序运行结果創作人：陶鹏鹏/並=计算机信息管理* -利用尾插洁建立双向循环链表犍表匸遽由飓向谊环琏表B 双向循那桩表中删除一个指定元素R 一在菲递湖有序双向循环链表中齐期插入元素*仍直庁b.判商双向信处链表中元素是否对称若对称返回1否则返回日6翹元素为正產型实现算法把所有奇数轴列在偶数之前R青输入所选菜单=6. 总结:通过此次数据结构的课程设计，我对程序的