数据结构实验五：链表实验

《数据结构实验五：链表实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一，实验题目实验五：假设有一个单向循环链表，其结点包含三个域：data,pre和next,其中data为数据域next为指针域，其值为后继结点的地址，pre也为指针域，其初值为空(null),试设计算法将此单向循环链改为双向循环链表。二，问题分析木程序要求将-个包含三个域：data,pre和next,K中data为数据域next为指针域，其值为后继结点的地址，pre也为指针域的单向循环链表改为双向循环链表。完成这些问题需耍解决的是空链表的牛成，链表元素的输入和输出，将单向链表改为双向链表等。1,数据的输入形式和输出形式：单链表的元索均为int型，输出

2、的单链表元素也为int型。输出链衣指针所指向的前一个或后一个链农元素时，选择1或2。2,结果的输出形式：首先输出单链表的元素，将单链表转换为双向链表后，输出p指针所指的前一个或后一个链表元索。3,测试数据：(1)输入的单链表元素为:23,553,87,0；(2)输入的单链表元素为：34,7650；三，概要设计1,为了实现上述程序功能，需要：(I)构造一个空的单链表L；(2)逐个输入单链表元素；(3)输出单链表元素；(4)将单链表转换为双向链表；(5)进行简单的双向四,1，链表的结构类型定义:typedefstructdnode{intdata;str

3、uctdnode*pre,*next;Jdlinklist;2,建立空链表伪代码：dlinklist*crcalnull(){dlinklist*L;L=(dlinklist*)malloc(sizeof(dlinklist));L->next=NULL;L->pre=NULL;L->data=NULL;returnL;}3,建单链表伪代码：dlinklist*input(dlinklist*L,intx){dlinklist*s,*r;r=L->next;s=creatnull();s->data=x;L->next=s;s->next=r;ret

4、urnL;}1,将单链衣转换为双向循环链表的伪代码：dlinklist*setdouble(dlinklist*L){dlinklists=L;t=L->next;while(t!=NULL){t->pre=s;s=s->next;t=t->next;}returnL;}五，源程序#include"stdio.h"#include"malloc.h"typedefstructdnode{〃链表的结构类型定义intdata;〃数据域structdnode*pre,*next;[dlinklist;dlinklist*creatnull(){〃建立空链表

5、，即建立空结点dlinklist*L;L=(dlinklist*)malloc(sizeof(dlinklist));//为新节点申请空间L->next=NULL;L->pre=NULL;L->data=NULL;〃置空returnL;}dlinklist*input(dlinklist*L,intx)〃头插法建单链表dlinklist*s,*r;i-L->next;s=creatnull();〃将L指向的下一个节点赋值给r〃建立空点结s->data=x;L->next=s;s->next=r;returnL;〃将x值赋给新建结点的data域〃将s赋

6、值给L指向的下一个结点〃将1•赋给s所指向的下一个结点，完成插入dlinklist*setdouble(dlinklist*L){〃将单链表转换为双向循环链表dlinklist*s,*t;s=L;t=L->next;while(t!=NULL)t->pre=s;s=s->next;t=t->next;returnL;voiddisplay(dlinklist*k)//输出顺序表中数据{k=k->next;while(k!=NULL){printf("%dH,k->data);k=k->next;voidmain(){dlinklist*p,*q;〃定

7、义两个指针型变量p,qintx,i=0;p=creatnull();〃建立空链表q=p；〃使q也指向头结点printf("输入顺序表的元素，(输入0表示输入结束)：“)；while(x!=0){p=input(p,x);〃当x不等于0时，输入链表元素xscanf("%d",&x);}printfC，输入的顺序表元素为：”)；p=setdouble(p);〃将单链表转换为双向循环链表display(p);〃输出链表表元素do{printf("");printf(”1,输出下一个数据：“)；printf(n2,输出上一个数ffi：u)

8、;printfC1请选择要输出的是顺序表元素的上一个还是下一个元素：“);scanf(H%dn,&i);