数据结构实验五:链表实验.doc
文本预览下载声明
一 , 实验题目
实验五:
假设有一个单向循环链表,其结点包含三个域: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
显示全部