实验报告
实验课程名称
数据结构
班级
09计科一班
实验项目名称
单链表实验
指导老师
祁文青
姓 名
***
学 号
****
评 分
实验地点
K4-206
实验日期
9.30-10.14
一、实验目的和要求
1、掌握用Visual C++6.0上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
3、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实验任务
（一）1、单链表基本操作的实现。要求生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。
2、源代码
#include
#include
#include
#include
typedef int elemtype;
typedef struct lnode
{
elemtype date;
struct lnode *next;
}lnode;
lnode *creat(void)
{
lnode *p2,*p1;
lnode *head;
int n;
n=0;
p1=p2=(lnode *)malloc(sizeof(lnode));
head=NULL;
cin>>p1->date;
while(p1->date>0)
{
n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(lnode *)malloc(sizeof(lnode));
cin>>p1->date;
}
p2->next=NULL;
return head;
}
void print(lnode *head)
{
lnode *p;
p=head;
if(head==NULL)
cout<<"空表";
if(head!=NULL)
do
{
cout<date;
p=p->next;
}while(p!=NULL);
cout<next;
free(p1);
}
else
{
while(p1->next&&jnext;
j++;
}
if(p1->next==0||j>i-1)
cout<<"没有发现"<next=p1->next;
free(p1);
}
}
return head;
}
lnode *insert(lnode *&head,int i,elemtype e)
{
lnode *p1,*p2,*s;
int j=0;
p1=head;
s=(lnode *)malloc(sizeof(lnode));
s->date=e;
if(head==NULL&&i==1)
head=s;
else
{
while(p1->next&&jnext;
j++;
}
p2->next=s;
s->next=p1;
}
return head;
}
int main()
{
lnode *head;
head=creat();
int i;
elemtype e;
print(head);
int num;
cout<<"请输入要删除的第几位数："<>num;
del(head,num);
print(head);
cout<<"请输入在第几位插入什么数："<>i>>e;
insert(head,i,e);
print(head);
return 0;
}
3、运行结果
4、结果分析
单步执行可以看出用单链表时，由于不要求逻辑上相邻的元素在物理位置上也相邻，所以单链表没有顺序存储结构素具有的弱点，但是这也导致了单链表不可以随机存取的优点。
（二）1、已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。要求①不破坏la表和lb表的结构。②破坏la表和lb表的结构。
2、源代码
#include
#include
#include
#include
typedef int elemtype;
typedef struct lnode
{
elemtype date;
struct lnode *next;
}lnode;
lnode *hebing(lnode *head1,lnode *head2,lnode *&head);
lnode *creat(void)
{
lnode *p2,*p1;
lnode *head;
int n;
n=0;
p1=p2=(lnode *)malloc(sizeof(lnode));
head=NULL;
cin>>p1->date;
while(p1->date>0)
{
n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(lnode *)malloc(sizeof(lnode));
cin>>p1->date;
}
p2->next=NULL;
return head;
}
void print(lnode *head)
{
lnode *p;
p=head;
if(head==NULL)
cout<<"空表";
if(head!=NULL)
do
{
cout<date;
p=p->next;
}while(p!=NULL);
cout<date<=p2->date)
{
p3->date=p1->date;
p1=p1->next;
}
else
{
p3->date=p2->date;
p2=p2->next;
}
if(n==1)
head=p3;
else
p4->next=p3;
p4=p3;
p3=(lnode *)malloc(sizeof(lnode));
n++;
}
if(p1==NULL)
{
while(p2)
{
p3->date=p2->date;
p2=p2->next;
p4->next=p3;
p4=p3;
p3=(lnode *)malloc(sizeof(lnode));
}
}
else
{
while(p1)
{
p3->date=p1->date;
p1=p1->next;
p4->next=p3;
p4=p3;
p3=(lnode *)malloc(sizeof(lnode));
}
}
p4->next=NULL;
return(head);
}
3、运行结果
4、结果分析
此段代码可以实现将两个链表合并成一个有序链表。
（三）1、编程实现两个循环单链表的合并。
2、源代码
#include
#include
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
int print(LinkList &L,int n);
int hebing(LinkList L1,int n,LinkList L2,int m,LinkList &L);
void creat(LinkList &L,int n)
{
LNode *p1,*p2;
p1=p2=(LNode *)malloc(sizeof(LNode));
L=NULL;
int i;
for(i=0;i>p1->data;
if(i==0)
L=p1;
else
p2->next=p1;
p2=p1;
p1=(LNode *)malloc(sizeof(LNode));
}
p2->next=L;
}
int main()
{
LNode *L1,*L2,*L;
cout<<"请输入第一个单链表的长度："<>n;
creat(L1,n);
print(L1,n);
cout<<"请输入第二个单链表的长度："<>m;
creat(L2,m);
print(L2,m);
cout<<"合并后"<data<<" ";
L=L->next;
}
return 0;
}
int hebing(LinkList L1,int n,LinkList L2,int m,LinkList &L)
{
int i;
LNode *p1;
L=L1;
p1=L1;
for(i=1;inext;
for(i=1;inext;
p1->next=L2->next;
return 0;
}
3、运行结果
4、结果分析
此段代码实现的功能是将两个循环单链表进行合并。
（四）1、将一循环单链表就地逆置
#include
#include
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
int print(LinkList &L,int n);
int nizhi(LNode *&L,int n);
void creat(LinkList &L,int n)
{
LNode *p1,*p2;
p1=p2=(LNode *)malloc(sizeof(LNode));
L=NULL;
int i;
for(i=0;i>p1->data;
if(i==0)
L=p1;
else
p2->next=p1;
p2=p1;
p1=(LNode *)malloc(sizeof(LNode));
}
p2->next=L;
}
int main()
{
LNode *L;
cout<<"请输入个数："<>n;
creat(L,n);
print(L,n);
nizhi(L,n);
cout<<"逆制后..."<data<<" ";
L=L->next;
}
cout<data=p1->data;
p1=p1->next;
L1=p2;
if(i==0)
r=L1;
p2=(LNode *)malloc(sizeof(LNode));
p2->next=L1;
}
r->next=L1;
L=L1;
return 0;
}
3、运行结果
4、结果分析
此段代码用以实现链表的逆制。
三、结论
掌握了用VC++6.0上机调试单链表的基本方法，基本上掌握了单链表的插入、删除、查找、求表长、有序单链表的合并以及单链表的逆制算法的实现。但是仍然有不足之处，需进一步掌握循环单链表的插入、删除、查找算法的实现。
四、教师批阅
12
浙公网安备 33021202002483