《数据结构》实验报告一
题目：单链表的查找、插入与删除 班级： 电子0802
学号：
日期： 2011.03.08 姓名： 程序名： cqq1.c
一、上机实验的问题和要求：
单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：
1. 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。
2. 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否
则，则显示“找不到”。
3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插
入在对应位置上，输出单链表所有结点值，观察输出结果。
4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有
结点值，观察输出结果。
6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。
7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。
8. （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元
素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。
二、程序设计的基本思想，原理和算法描述：
1、基本操作函数
link * get(link *l, int i)； //创建链表
link * ins (link *l, int a,int i) //在链表内插入值
link * find(link *l, int a)； //在链表内查找值
link * del(link *l, int i); //在链表内删除值
link * delrepeat( link *l); //在链表内删除重复值
link * deleven(link *l); //删除链表内偶数值
link * rotate(link *l); //形成循环链表
void divide(link *l); //分解成两个链表
cout
2、基本操作
cout
cout
cout
cout
cout
cout
cout
cout
cout
三、源程序及注释：
#include
using namespace std;
typedef struct node
{
int data;
struct node *next;
}link;
void print1(link *l);
link * get(link *l, int i)
{
link *p;
int j=0;
p=l;
while((jnext!=NULL))
{
p=p->next;j++;
}
if(j==i)
return p;
else
return NULL;
}
link * ins (link *l, int a,int i)
{
link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout
else
{
s=(link *)malloc(sizeof(link));
s->data=a;
s->next=p->next;
p->next=s;
}
return l;
}
link * find(link *l, int a)
{
link *p;
int i=0;
int j=0;
p=l;
while(p!=NULL)
{
i++;
if(p->data!=a)
p=p->next;
else
{
cout
j=1;
p=p->next;
}
}
if(j!=1)
cout
return l;
}
link * del(link *l, int i)
{
link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout
else
{
s=p->next;
p->next=s->next;
free(s);
}
return l;
}
link * delrepeat( link *l) // 删除相同元素并释放内存
{
link *s, *r, *t;
if ( l-> next == NULL )
return l;
s = l-> next;
while ( s-> next )
{
t = s; r = s-> next;
while ( t-> next )
{
if ( s-> data == r-> data
{
t-> next = r-> next;
free(r);
r = t-> next;
}
else
{
t = t-> next;
r = t-> next;
}
}
s = s-> next;
if ( !s )
return l;
}
return l;
}
link * deleven(link *l)
{
link *q=l;
link *p=l->next;
while(p)
{
if(p->data%2==0)
{
link *r=p;
q->next=p->next;
p=p->next;
free(r);
}
)
{
p=p->next;
q=q->next;
}
}
return l;
}
link * rotate(link *l)
{
link * p=l;
while(p->next)p=p->next;
p->next=l;
link * t=l->next;
while(t!=l)
{
t=t->next;
}
cout
return l;
}
void divide(link *l)
{
link * a=l;
link * b=(link *)malloc(sizeof(node));
b->next=NULL;
link *Lb=b;
int i=1;
link * La=l;
link * p=l->next;
while(p)
{
if(i++%2==0)
{
La->next=p->next;
p->next=NULL;
Lb->next=p;
Lb=Lb->next;
p=La->next;
}
{
p=p->next;
La=La->next;
}
}
cout
print1(a);
cout
print1(b);
}
void print1(link *l)
{
int i,k;
int a;
link *p,*q;
cout
p=l;p=p->next;
if(l!=NULL)
do
{
coutdata
p=p->next;
}while(p!=NULL);
cout
}
link * print(link *l)
{
int i,k;
int a;
link *p,*q;
cout
p=l;p=p->next;
if(l!=NULL)
do
{
coutdata
p=p->next;
}while(p!=NULL);
cout
cout
cout
cout>k; if(k==1) { cout>a; cout>i; p=ins(l,a,i); q=print(l); } else if(k==2) { cout>a; p=find(l,a); q=print(l); } else if(k==3) { cout>i; p=del(l,i); q=print(l); } else if(k==4) { cout
}
else if(k==6)
{
p=rotate(l);
q=print(l);
}
else if(k==7)
{
divide(l);
}
else if(k==0);
else
{cout
return l;
}
int main()
{
cout
int ch[20];
int i;
//link *head;
link *r,*p,*q,*l;
l=(link *)malloc(sizeof(link));
l->next=NULL;
r=l;
for(i=0;i
{
cin>>ch[i];
p=(link *)malloc(sizeof(link));
p->data=ch[i];p->next=NULL;
r->next=p;r=r->next;
}
q=print(l);
return 0;
}
四、运行输出结果：
五、调试和运行程序过程中产生的问题及采取的措施：
1、本次实验采用C++语言，程序基本能实现实验所要求的操作功能，但是首次使用C++来完成所有链表的操作，有很多小细节不够注意，比如定义结点与结点的使用，需要多操作，多熟悉语。
2、最后两个操作
void rotate(link *l); //变为循环链表
void divide(link *l); //分解成两个链表
一旦执行，将破坏链表的结构，无法再进行其他操作，需要结束整个程序。可以设置一个主函数结束标志，此处就不详细说明。
六、对算法的程序的讨论、分析，改进设想，其它经验教训： 程序是8个基本操作，设置不同的数字对应这些基本操作，由用户自己选择执行，这样程序灵活，也便于用户使用和观察。
在创建链表时，原来设计的是输入固定长度的链表，后来改进为由用户输入任意长度的数据，只需要用一个标志数字表示结束即可。
七、对实验方式、组织、设备、题目的意见和建议：
这个实验基本涵盖了单链表所有的简单操作，只要能写完程序并顺利运行，也就掌握了单链表的相关知识内容。但是由于涵盖内容偏多，课内无法完成，必须在课外花很多时间，建议老师对此有所调整。
《数据结构》实验报告一
题目：单链表的查找、插入与删除 班级： 电子0802
学号：
日期： 2011.03.08 姓名： 程序名： cqq1.c
一、上机实验的问题和要求：
单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：
1. 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。
2. 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否
则，则显示“找不到”。
3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插
入在对应位置上，输出单链表所有结点值，观察输出结果。
4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有
结点值，观察输出结果。
6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。
7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。
8. （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元
素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。
二、程序设计的基本思想，原理和算法描述：
1、基本操作函数
link * get(link *l, int i)； //创建链表
link * ins (link *l, int a,int i) //在链表内插入值
link * find(link *l, int a)； //在链表内查找值
link * del(link *l, int i); //在链表内删除值
link * delrepeat( link *l); //在链表内删除重复值
link * deleven(link *l); //删除链表内偶数值
link * rotate(link *l); //形成循环链表
void divide(link *l); //分解成两个链表
cout
2、基本操作
cout
cout
cout
cout
cout
cout
cout
cout
cout
三、源程序及注释：
#include
using namespace std;
typedef struct node
{
int data;
struct node *next;
}link;
void print1(link *l);
link * get(link *l, int i)
{
link *p;
int j=0;
p=l;
while((jnext!=NULL))
{
p=p->next;j++;
}
if(j==i)
return p;
else
return NULL;
}
link * ins (link *l, int a,int i)
{
link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout
else
{
s=(link *)malloc(sizeof(link));
s->data=a;
s->next=p->next;
p->next=s;
}
return l;
}
link * find(link *l, int a)
{
link *p;
int i=0;
int j=0;
p=l;
while(p!=NULL)
{
i++;
if(p->data!=a)
p=p->next;
else
{
cout
j=1;
p=p->next;
}
}
if(j!=1)
cout
return l;
}
link * del(link *l, int i)
{
link *p,*s;
p=get(l,i-1);
if(p==NULL)
cout
else
{
s=p->next;
p->next=s->next;
free(s);
}
return l;
}
link * delrepeat( link *l) // 删除相同元素并释放内存
{
link *s, *r, *t;
if ( l-> next == NULL )
return l;
s = l-> next;
while ( s-> next )
{
t = s; r = s-> next;
while ( t-> next )
{
if ( s-> data == r-> data
{
t-> next = r-> next;
free(r);
r = t-> next;
}
else
{
t = t-> next;
r = t-> next;
}
}
s = s-> next;
if ( !s )
return l;
}
return l;
}
link * deleven(link *l)
{
link *q=l;
link *p=l->next;
while(p)
{
if(p->data%2==0)
{
link *r=p;
q->next=p->next;
p=p->next;
free(r);
}
)
{
p=p->next;
q=q->next;
}
}
return l;
}
link * rotate(link *l)
{
link * p=l;
while(p->next)p=p->next;
p->next=l;
link * t=l->next;
while(t!=l)
{
t=t->next;
}
cout
return l;
}
void divide(link *l)
{
link * a=l;
link * b=(link *)malloc(sizeof(node));
b->next=NULL;
link *Lb=b;
int i=1;
link * La=l;
link * p=l->next;
while(p)
{
if(i++%2==0)
{
La->next=p->next;
p->next=NULL;
Lb->next=p;
Lb=Lb->next;
p=La->next;
}
{
p=p->next;
La=La->next;
}
}
cout
print1(a);
cout
print1(b);
}
void print1(link *l)
{
int i,k;
int a;
link *p,*q;
cout
p=l;p=p->next;
if(l!=NULL)
do
{
coutdata
p=p->next;
}while(p!=NULL);
cout
}
link * print(link *l)
{
int i,k;
int a;
link *p,*q;
cout
p=l;p=p->next;
if(l!=NULL)
do
{
coutdata
p=p->next;
}while(p!=NULL);
cout
cout
cout
cout>k; if(k==1) { cout>a; cout>i; p=ins(l,a,i); q=print(l); } else if(k==2) { cout>a; p=find(l,a); q=print(l); } else if(k==3) { cout>i; p=del(l,i); q=print(l); } else if(k==4) { cout
}
else if(k==6)
{
p=rotate(l);
q=print(l);
}
else if(k==7)
{
divide(l);
}
else if(k==0);
else
{cout
return l;
}
int main()
{
cout
int ch[20];
int i;
//link *head;
link *r,*p,*q,*l;
l=(link *)malloc(sizeof(link));
l->next=NULL;
r=l;
for(i=0;i
{
cin>>ch[i];
p=(link *)malloc(sizeof(link));
p->data=ch[i];p->next=NULL;
r->next=p;r=r->next;
}
q=print(l);
return 0;
}
四、运行输出结果：
五、调试和运行程序过程中产生的问题及采取的措施：
1、本次实验采用C++语言，程序基本能实现实验所要求的操作功能，但是首次使用C++来完成所有链表的操作，有很多小细节不够注意，比如定义结点与结点的使用，需要多操作，多熟悉语。
2、最后两个操作
void rotate(link *l); //变为循环链表
void divide(link *l); //分解成两个链表
一旦执行，将破坏链表的结构，无法再进行其他操作，需要结束整个程序。可以设置一个主函数结束标志，此处就不详细说明。
六、对算法的程序的讨论、分析，改进设想，其它经验教训： 程序是8个基本操作，设置不同的数字对应这些基本操作，由用户自己选择执行，这样程序灵活，也便于用户使用和观察。
在创建链表时，原来设计的是输入固定长度的链表，后来改进为由用户输入任意长度的数据，只需要用一个标志数字表示结束即可。
七、对实验方式、组织、设备、题目的意见和建议：
这个实验基本涵盖了单链表所有的简单操作，只要能写完程序并顺利运行，也就掌握了单链表的相关知识内容。但是由于涵盖内容偏多，课内无法完成，必须在课外花很多时间，建议老师对此有所调整。