实验一 线性表应用.doc

2011-2012学年《数据结构与算法》实验报告

海南医学院

实验一线性表应用

[实验目的]

本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的各种操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。

[问题描述]

试设计一个非递归算法在O（n）时间内，将一个含有n个元素的单链表实现就地逆置，要求其辅助空间为常量。

[基本要求]

利用单链表存储结构模拟就地逆置过程，输出单链表的初始顺序和逆置后顺序。

[测试数据]

n的初值为5；元素：29，76，18，45，25（正确的结果应为25，45，18，76，29）。也可以自选元素值。

[实现提示]

程序运行后首先要求用户指定元素个数值，然后分别读取元素，输出单链表的初始顺序和逆置后顺序。

[思考]

描述你所设计的算法思路。

用P指针扫描原单链表，先将头节点L的Next域置为NULL而变成一个空链表，然后用*P结点采用头插法插入到L中由前往后将每个结点依次从头结点链表中摘下，作为第一个结点插入到带头结点链表中。

分析你所设计的算法的时间复杂度。

时间复杂度为O(1)

[源程序代码]：

#includeiostream

usingnamespacestd;

typedefstructlist

{

intdata;

structlist*next;

;}LIST;

LIST*creat()//创建链表

{

LIST*head,*p;

intflag=1,d;

head=newLIST;

p=head;

cout输入数据\n;

cind;

head-data=d;

while(flag)

{

LIST*tem=newLIST;

cout输入数据\n;

cind;

if(0!=d)//输入0结束

{

tem-data=d;

p-next=tem;

p=tem;

}

elseflag=0;

}

p-next=NULL;

returnhead;

}

LIST*reverse(LIST*head)//链表逆置

{

if(head==NULL||head-next==NULL)

returnhead;

LIST*p1,*p2,*p3;

p1=head;

p2=head-next;

while(p2)

{

p3=p2-next;

p2-next=p1;

p1=p2;

p2=p3;

}

head-next=NULL;

head=p1;

returnhead;

}

voidDelete(LIST*h)//销毁链表

{

while(h!=NULL)

{

LIST*p=h;

h=h-next;

deletep;

}

}

voidshow(LIST*head)//打印链表

{

if(head==NULL)

cout链表为空\n;

while(head!=NULL)

{

couthead-data;

head=head-next;

}

coutendl;

}

intmain()

{

LIST*head;

head=creat();

cout链表元素为:\n;

show(head);

cout链表逆置后的为:\n;

head=reverse(head);

show(head);

Delete(head);

return0;

}

[选作内容]

利用顺序存储结构模拟实现逆置过程的算法描述及代码。

解：算法如下:

#defineListSize100//假定表空间大小为100

typedefintDataType;//假定DataType的类型为int型

typedefstruct{

DataTypedata[ListSize];//向量data用于存放表结点

intlength;

voidReverseList(Seqlist*L)

{

DataTypetemp;//设置临时空间用于存放data

inti;

for(i=0;i=L-length/2;i++)//L-length/2为整除运算

{temp=L-data[i];//交换数据

L-data[i]=L-data[L-length-1-i];