线性表 实验报告

《算法与数据结构》试验汇报格式《算法与数据结构》试验汇报试验题目：线性表单链表实现一、.需求和规格说明描述问题，简述题目要处理问题是什么。要求软件做什么。1.熟悉线性表基本操作在单链表实现。2.用自己熟悉编程语言（C＋＋）实现。3.测试要求：（1）创建单链表；（2）在单链表上查找第i个数据结点，返回其data值；（3）在单链表第i个位置上插入一个取值为value新数据结点；（4）删除单链表第i个数据结点，并返回该数据结点取值；（5）求单链表长度。二.设计2.1算法描述存放结构（题目中限定要复述）；主要算法描述(类C/C++语言描述)。创建单链表typedefstructnode//创建单链表

{chardata;

structnode*next;

}link;查找数据link*find(link*l,inti)

//数据查找

{link*p;

p=get(l,i);

cout<<"你要查找数据为："<<p->data<<endl;

returnl;

}插入数据link*ins(link*l,charch,inti)

//数据插入

{link*p,*s;

p=get(l,i-1);

if(p==NULL)

cout<<"输入有误"<<endl;

else

{

s=(link*)malloc(sizeof(link));

s->data=ch;

s->next=p->next;

p->next=s;

}

returnl;

}（四）数据删除link*del(link*l,inti)

//数据删除

{link*p,*s;

p=get(l,i-1);

if(p==NULL)

cout<<"输入有误"<<endl;

else

{s=p->next;

p->next=s->next;

free(s);}

returnl;}2.2实现注释在完成基本要求基础上还实现了什么功效。对测试数据正确实现了试验要求功效。附：试验数据：1)线性表中数据元素取值集合为{1，2，3，4，5，6，7，8}；2）给出在单链表实现时(a)查找第4个数据结点；(b)在第3个位置插入value=9/9.0；(c)删除第4个数据结点；(d)给出单链表长度。二．本程序在实现了试验要求之外，还编写了用户操作指示流程程序，方便用户正确快速使用。2.2实现注释link*print(link*l)

//操作指示

{inti,k,t=0;

charch;

link*p,*q;

cout<<"当前线性表为："<<endl;

p=l;p=p->next;t++;

if(l!=NULL)

do{cout<<p->data<<"";

p=p->next;

t++;}while(p!=NULL);cout<<endl;

cout<<"请选择您要操作：";

cout<<"1、插入";

cout<<"2、查找";

cout<<"3、删除";

cout<<"4、求长";

cout<<"0、退出";

cout<<endl;

cin>>k;

if(k==1)

{cout<<"请输入您要插入数据值：";

cin>>ch;

cout<<"请输入您要插入位置：";

cin>>i;

p=ins(l,ch,i);

q=print(l);}

elseif(k==2){

cout<<"请输入您要查找结点位置：";

cin>>i;

p=find(l,i);

q=print(l);}

elseif(k==3)

{cout<<"请输入您要删除数据位置：";

cin>>i;

p=del(l,i);

q=print(l);}

elseif(k==4)

{cout<<"长度为："<<t-1<<endl;}

elseif(k==0);

else{cout<<"输入错误!"<<endl;

q=print(l);}

returnl;

}三.用户手册说明怎样使用你编写程序，详细列出每一步操作步骤。我经过上网查阅资料，在本程序中添加了用户操作指示程序。在运行本程序时，系统会依照程序内容提醒用户各步操纵。四.调试汇报调试过程中碰到主要问题是怎样处理；算法时空分析和改进构想；经验和体会等。在调试过程中只要碰到了程序检验无误但却不能运行，日后经过请教老师，发觉是指针出现问题，经过数次重复检验和修改，最终正常运行了正确程序。整个算法在运算复杂度上还有很多需要改进，能够经过查阅资料，对分段功效程序经行简化。经过自己认真编写一个程序，发觉了自己在之前学习中还对很多知识了解不全方面，仅仅是纸上谈兵，用于真正实战就乱套了。希望自己在以后学习中能更重视实践！五.运行结果请输入一串单字符数据，以*结束！12345678*当前线性表为：12345678请选择您要操作：1、插入2、查找3、删除4、求长0、退出1请输入您要插入数据值：1请输入您要插入位置：3当前线性表为：121345678请选择您要操作：1、插入2、查找3、删除4、求长0、退出2请输入您要查找结点位置：4你要查找数据为：3当前线性表为：121345678请选择您要操作：1、插入2、查找3、删除4、求长0、退出3请输入您要删除数据位置：4当前线性表为：12145678请选择您要操作：1、插入2、查找3、删除4、求长0、退出4长度为：8Pressanykeytocontinue提交源程序，列出测试结果，包含输入和输出。源程序：#include<iostream>

usingnamespacestd;

typedefstructnode

{chardata;

structnode*next;

}link;

link*get(link*l,inti)

{link*p;intj=0;

p=l;

while((j<i)&&(p->next!=NULL))

{p=p->next;j++;}

if(j==i)

returnp;

else

returnNULL;

}

link*find(link*l,inti)

//数据查找

{link*p;

p=get(l,i);

cout<<"你要查找数据为："<<p->data<<endl;

returnl;

}

link*ins(link*l,charch,inti)

//数据插入

{link*p,*s;

p=get(l,i-1);

if(p==NULL)

cout<<"输入有误"<<endl;

else

{s=(link*)malloc(sizeof(link));

s->data=ch;

s->next=p->next;

p->next=s;

}returnl;}link*add(link*l)

{link*p,*s;

cout<<"请输入一串单字符数据，以*结束！"<<endl;

charch;

link*HEAD;

link*R,*P,*L;

HEAD=(link*)malloc(sizeof(link));

HEAD->next=NULL;

R=HEAD;

getchar();

ch=getchar();

while(ch!='*')

{P=(link*)malloc(sizeof(link));

P->data=ch;P->next=NULL;

R->next=P;R=R->next;

getchar();

ch=getchar();}

L=HEAD;

cout<<"当前输入线性表为："<<endl;

P=L;P=P->next;

if(L!=NULL)

do{cout<<P->data<<"";

P=P->next;

}while(P!=NULL);

cout<<endl;

p=l;

while(p->next!=NULL)

p=p->next;

s=L;

p->next=s->next;

p=l;

returnl;

}

link*del(link*l,inti)

//数据删除

{link*p,*s;

p=get(l,i-1);

if(p==NULL)

cout<<"输入有误"<<endl;

else

{s=p->next;

p->next=s->next;

free(s);}

returnl;

}link*print(link*l)

//操作指示

{inti,k,t=0;

charch;

link*p,*q;

cout<<"当前线性表为："<<endl;

p=l;p=p->next;t++;

if(l!=NULL)

do{cout<<p->data<<"";

p=p->next;

t++;}while(p!=NULL);

cout<<endl;

cout<<"请选择您要操作：";

cout<<"1、插入";

cout<<"2、查找";

cout<<"3、删除";

cout<<"4、求长";

cout<<"0、退出";

cout<<endl;

cin>>k;

if(k==1)

{cout<<"请输入您要插入数据值：";

cin>>ch;

cout<<"请输入您要插入位置：";

cin>>i;

p=ins(l,ch,i);

q=print(l);}

elseif(k==2)

{cout<<"请输入您要查找结点位置：";

cin>>i;

p=find(l,i);

q=print(l);}

elseif(k==3)

{cout<<"请输入您要删除数据位置：";

cin>>i;

p=del(l,i);

q=print(l);

}

elseif(k==4)

{cout<<"长度为："<<t-1<<endl;

}

elseif(k==0)

;

else

{cout<<"输入错误!"<<endl;

q=print(l);}

returnl;

}intmain()

{

cout<<"请输入一串单字符数据，以*结束！"<<endl;

charch;

//link*head;

link*r,*p,*q,*l;

l=(link*)malloc(sizeof(link));

l->next=NULL;

r=l;

ch=getchar();

//getchar();

while(ch!='*')

{p=(link*)malloc(sizeof(link));

p->data=ch;p->next=NULL;

r->next=p;r=r->next;

ch=getchar();

//getchar();

}

//l=head;

q=print(l);

return0;

}测试结果：请输入一串单字符数据，以*结束！12345678*当前线性表为：12345678请选择您要操作：1、插入2、查找3、删除4、求长0、退出1请输入您要插入数据值：1请输入