c语言数据结构双向链表

数据结构上机实验

课后练习报告

姓名：冯天明

学号：

班级：通信141

2015年9月28日星期一

实验三：

编写一个程序，实现双链表的各种基本运算，并在此基础上设计一个主程序完成

以下功能。

1.初始化双链表L

2.依次采用尾插法或者头插法插入元素a,b,c,d,e

3.输出双链表L

4.输出双链表的长度

5.判断双链表是否为空

6.输出双链表的第四个元素

7.输出元素a的位置

8.在第三个元素位置插入元素f

9输出双链表L

10.删除双链表L的第四个元素

11.输出双链表L

12.释放双链表

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#defineOK0

#defineERROR-2

#defineOVERFLOW-1

typedefcharElemType;

typedefstructDuLNode//定义双向链表

(

ElemTypedata;

DuLNode*prior;

DuLNode*next;

}DuLNode,*DuLinkList;

voidInitDuLinkList(DuLinkListh)〃创建一个空表

h=newDuLNode;//(DuLinkList)malloc(sizeof(DuLNode));

h->next=h->prior;

voidCreateDuLinkList(DuLinkListh,intn)〃初始化链表

DuLNode*p,*q;

InitDuLinkList(h);

q=h;

printf("输入％个元素：\n",n);

fbr(inti=0;i<n;i++)

{

p=(DuLinkList)malloc(sizeof(DuLNode));

scanf("%c",&p->data);

fflush(stdin);

q->next=p;

p->prior=q;

q=p;

}

q->next=NULL;

)

intDestroyList(DuLinkListL)〃销毁链表

(

DuLNode*p=L;

while(L->next)//直到达最后一个节点

(

p=L->next;

L->next=p->next;

free(p);

)

L->prior=NULL;

returnOK;

)

intListEmpty(DuLinkListL)

(

return(L->next==NULL&&L->prior==NULL);

)

DuLNode*GetElem(DuLinkListh,inti)//获取对应节点的元素

(

DuLNode*p;

p=h->next;

intj=1;

while(p&&j<i)

{

p=p->next;

++j；

}

if。==i)

returnp;

else

returnNULL;

)

intDuLinkListInser(DuLinkListh,inti,ElemTypee)

{

DuLNode*p,*s;

p=GetElem(h,i-l);

if(!p)returnERROR;

s=(DuLinkList)malloc(sizeof(DuLNode));

s->data=e;

if(p->next)〃如果插入的不是尾节点

(

p->next->prior=s;

s->next=p->next;

s->prior=p;

p->next=s;

else〃插入的是尾节点

{

s->next=p->next;

p->next=s;

s->prior=p;

returnOK;

)

intDeleListElem(DuLinkListL,inti)

(

DuLNode*p,*q;

p=GetElem(L,i-l);

if(!p)returnERROR;〃删除的元素不存在

if(p->next)〃如果删除的不是最后一个节点

(

q=p->next;

q->next->prior=p;

p->next=q->next;

}

else

(

q=p->next;

p->next=NULL;

}

free(q);

returnOK;

)

intLocateElem(DuLinkListL,ElemTypee)

(

intloca=0;

DuLNode*p;

p=L->next;

if(P)

(

while(p!=L)

{

++loca;

if(p&&p->data==e)〃元素匹配，返回节点

returnloca;

if(!p)

returnERROR;

p=p->next;

)

)

returnERROR;

)

intListLength(DuLinkListL)

(

DuLNode*p=L;

inti=0;

while(p->next)//遍历链表，记录节点数

(

p=p->next;

++i；

}

returni;

)

voidDisplayList(DuLinkListL)

(

DuLNode*p;

p=L->next;

if(ListEmpty(L))

(

printf("链表为空！\n");

return;

)

printf("链表的内容为:")；

while(p)〃遍历链表，输出节点data

(

printf("%4c",p->data);

p=p->next;

}

printf("\n");

intmain()

DuLNodeL,*temp;

intloca;

CreateDuLinkList(&L,5);〃初始化链表

DisplayList(&L);〃输出链表

if(ListEmpty(&L))

{

printf("链表为空!\n");

)

else

(

printf("链表不为空!\n");

}

temp=GetElem(&L,4);〃获取第四个位置的元素

printf("链表第四个元素是:%c\n",temp->data);

loca=LocateElem(&L,'a');

printf("元素a在链表的第％d个位置\n",loca);〃寻找a元素在链

表的某个节点

printf("在第三个位置插入元素f:");

DuLinkListInser(&L,3,'f);〃插入元素f在第三个位置

DisplayList(&L);

DeleListElem(&L,4);