文档详情

数据结构实验五:链表实验.doc

发布:2018-10-13约3.25千字共5页下载文档
文本预览下载声明
一 , 实验题目 实验五: 假设有一个单向循环链表,其结点包含三个域:data,pre和next,其中data为数据域next为指针域,其值为后继结点的地址,pre也为指针域,其初值为空(null),试设计算法将此单向循环链改为双向循环链表。 二, 问题分析 本程序要求将一个包含三个域:data,pre和next,其中data为数据域next为指针域,其值为后继结点的地址,pre也为指针域的单向循环链表改为双向循环链表。完成这些问题需要解决的是空链表的生成,链表元素的输入和输出,将单向链表改为双向链表等。 数据的输入形式和输出形式:单链表的元素均为int型,输出的单链表元素也为int型。输出链表指针所指向的前一个或后一个链表元素时,选择1或2。 结果的输出形式:首先输出单链表的元素,将单链表转换为双向链表后,输出p指针所指的前一个或后一个链表元素。 测试数据: (1)输入的单链表元素为:23,553,87,0; (2)输入的单链表元素为:34,7650; 概要设计 为了实现上述程序功能,需要:(1)构造一个空的单链表L;(2)逐个输入单链表元素;(3)输出单链表元素;(4)将单链表转换为双向链表;(5)进行简单的双向链表功能测试 本程序包含5个函数: 主函数:main(); 建立空链表函数:creatnull(); 输入单链表元素函数:input(); 转换为双向循环链表函数:setdouble(); 单链表输出函数:display(); 个函数间的关系如右图所示: 详细设计 链表的结构类型定义: typedef struct dnode{ int data; struct dnode *pre,*next; }dlinklist; 建立空链表伪代码: dlinklist *creatnull(){ dlinklist *L; L=(dlinklist*)malloc(sizeof(dlinklist)); L-next=NULL;L-pre=NULL;L-data=NULL; return L;} 建单链表伪代码: dlinklist* input(dlinklist *L,int x){ dlinklist *s,*r; r=L-next; s=creatnull(); s-data=x; L-next=s; s-next=r; return L;} 将单链表转换为双向循环链表的伪代码: dlinklist *setdouble(dlinklist *L){ dlinklist *s,*t; s=L; t=L-next; while(t!=NULL){ t-pre=s; s=s-next; t=t-next;} return L;} 源程序 #include stdio.h #include malloc.h typedef struct dnode{ //链表的结构类型定义 int data; //数据域 struct dnode *pre,*next; }dlinklist; dlinklist *creatnull(){ //建立空链表,即建立空结点 dlinklist *L; L=(dlinklist*)malloc(sizeof(dlinklist)); //为新节点申请空间 L-next=NULL; L-pre=NULL; L-data=NULL; //置空 return L; } dlinklist* input(dlinklist *L,int x) //头插法建单链表 { dlinklist *s,*r; r=L-next; //将L指向的下一个节点赋值给r s=creatnull(); //建立空点结 s-data=x; //将x值赋给新建结点的data域 L-next=s; //将s赋值给L指向的下一个结点 s-next=r; //将r赋给s所指向的下一个结点,完成插入 return L; } dlinklist *setdouble(dlinklist *L){ //将单链表转换为双向循环链表 dlinklist *s,*t; s=L; t=L-next; while(t!=NULL) { t-pre=s; s=s-next; t=t-next; } return L; } void display(dlinklist *k) //输出顺序表中数据 { k=k-next; w
显示全部
相似文档