创建链表和链表操作实验报告.doc

创建链表和链表操作实验报告.doc

《创建链表和链表操作实验报告.doc》由会员分享，可在线阅读，更多相关《创建链表和链表操作实验报告.doc（9页珍藏版）》请在冰点文库上搜索。

数据结构实验报告

报告名称创建链表和链表操作

专业网络工程

班级1001

学号201003120129

姓名张剑

指导教师陈淑红李珍辉黄哲

2012年5月4日

一、实验目的：

掌握线性表的基本操作：

插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、实验内容与基本要求：

实验内容：

1.创建单链表

2．在链表上进行插入、删除操作；

3．设计一个程序，用两个单链表分别表示两个集合，并求出这两个集合的并集。

实验要求：

1．在上机前写出全部源程序；

2．能在机器上正确运行程序；

3．用户界面友好；

三、概要设计：

1.单链表的存储结构：

teypedefstructLNode{

ElemTypedate;

structLNond*next;

}LNode*LinkList;

2.单链表的插入操作：

StatusListTnsert-L（LinkLIst&L,inti,ElemTypee）{

//再带头结点的单链线性表L中的第i个位置之前插入元素e

P=l;j=0;

While（p&&j

P=p->next;++j;

}//寻找第i-1个结点

if（!

p||j>i-1）returnERROR;//i小小于1或者大于表长+1

s=（LinkList）malloc（sizeof（LNode））;//生成新结点

s->date=e;s->next=p->next;//插入L中

p->next=s;

returnok;

}//ListTnsertL

3.单链表的删除操作：

StatusListDelete-L（LinkLIst&L,inti,ElemType&e）{

//在带头结点单链线性表L中，删除低i个元素，并由e返回其值

p=l;j=0;

while（p->next&&j

p=p->next;++j;

}

if（!

（p->next）||j>i-1）

returnERROR;//删除位置不合理

q=p->next;p->next=q->next;//删除并释放结点

e=q->datefree（q）;

returnOK;

}//ListDelete-L

4.链表的合并操作：

voidMergeList-L（LinkList&La,LinkList&Lb,LinkList&Lc）{

//已知单链表La和Lb的元素值

//合并单链表La和Lb，得到新的单链表Lc

pa=La->next;pb=Lb->next;

lc=pc=La;//用La的头结点作为Lc的头结点

while（pa&&pb）{

if（pa->date<=pb->date）{

pc->next=pa;pc=pa;pa=pa->next;

}

else{pc->next=pb;pc=pb;pb=pb->next;}

}

Pc->next=pa?

pa:

pb;//插入剩余段

free（Lb）;//释放Lb头结点

}//MergeList-L

四、详细设计：

#include

#include

#include

#include

typedefintstatus;

typedefcharElemType;

typedefstructLnode //定义链表结点类型

{ElemTypedata;

structLnode*next;

}Lnode,*Linklist;

statusinitlist（Linklist*L）

{ //单链表的初始化

*L=（Lnode*）malloc（sizeof（Lnode））; //创建头结点

（*L）->next=NULL;

return1;

}

statusCreatelist（LinklistL）

{ //创建自己规定长度的单链表

Lnode*p,*q;

inti,j=1,n;

ElemTypem,M;

q=L;

printf（"请输入你要输入单链中元素的个数\n"）;

scanf（"%d",&n）;

scanf（"%c",&m）; //回车缓冲区

for（i=n;i>0;i--）

{p=（Lnode*）malloc（sizeof（Lnode））;

printf（"请输入%2.1d个元素:

",j）;

scanf（"%ld",&M）;

scanf（"%c",&m）; //回车缓冲区

p->data=M;

p->next=q->next;

q->next=p;

q=p;

j++;

}

return1;

}

statusListinsert（LinklistL,inti,ElemTypee）

{ //向单链表指定位置插入一个元素

intj=0;

Lnode*p=L,*s;

while（p&&j

{p=p->next;

++j;

}

if（!

p||j>i-1）{printf（"输入错误!

\n"）;

return0;

}

s=（Lnode*）malloc（sizeof（Lnode））;

s->data=e;

s->next=p->next;

p->next=s;

return1;

}

statusListdelete（LinklistL,inti,ElemType*e）

{ //删除单链表指定位置的元素,返回删除后的。

链表元素

Lnode*p,*q;

intj=0;

p=L;

while（p->next&&j

{p=p->next;

j++;

}

if（!

（p->next）||j>i-1）{printf（"输入错误!

\n"）;

return0;

}

q=p->next;

p->next=q->next;

*e=q->data;

free（q）;

return1;

}

voidprint（LinklistL）

{ //输出单链表中的元素

Linklistp;

p=L->next;

printf（"输出单链表：

\n"）;

while（p!

=NULL）

{printf（"%5ld",p->data）;

p=p->next;

}

printf（"\n"）;

}

structLnode*inter_link（structLnode*chain1,inta,structLnode*chain2,intb）

{ //单链表的合并

inttemp;

structLnode*head,*p1,*p2,*p3;

//判断a，b大小并合并

if（a>=b）

{

head=p1=chain1;

p2=chain2;

}

else

{

head=p1=chain2;

p2=chain1;

temp=a,a=b,b=temp;

}

p3=head;

while（p2!

=NULL）

{

p1=p1->next;

p3->next=p2;

p3=p2;

p2=p2->next;

p3->next=p1;

p3=p1;

}

returnhead;

}

main（）

{

inti,n,a,b,h;

structLnode*p1,*p2;

ElemTypee;

printf（"请输入创建的链表的个数:

"）;

scanf（"%1d",&n）;

switch（n）

{

case1:

{

LinklistL;

initlist（&L）;

/*创建链表*/

Createlist（L）;

print（L）;

/*插入元素*/

printf（"请输入需要插入元素的值和位置\n"）;

scanf（"%ld",&e）;

scanf（"%d",&i）;

Listinsert（L,i,e）;

print（L）;

printf（"请输入需要插入元素的值和位置\n"）;

scanf（"%ld",&e）;

scanf（"%d",&i）;

Listinsert（L,i,e）;

print（L）;

/*删除元素*/

printf（"请输入要删除的元素的位置:

"）;

scanf（"%d",&i）;

Listdelete（L,i,&e）;

print（L）;

printf（"被删除元素为:

%ld\n",e）;

};break;

case2:

{

LinklistL,H;

initlist（&L）;

initlist（&H）;

/*创建链表*/

Createlist（L）;

print（L）;

Createlist（H）;

print（H）;

L=inter_link（L,a,H,b）;

printf（"\n合并后的链表：

\n：

"）;

print（L）;

};break;

default:

printf（"Enterdataerror!

\n"）;

}

}

五、调试分析及测试结果：

测试数据：

1．（3，9，5，6，11，8）；

2．在5之前插入4，7，并删除11

求集合{1，12，8，6，4，9}和{2，5，12，7，4}的并集

测试结果及分析：

1.运行程序，首先进入选择界面，选择输入需要创建的链表数为1个，输入单链表中的元素个数为六个。

按照操作要求一次输入六个元素3,9，5,6，11,8。

按回车键结束，此时程序输出单链表，单链表创建成功。

图1：

单链表的创建与输出

2.当程序弹出“请输入需要插入元素的值和位置时”执行单链表的插入操作。

按要求输入需要4,插入元素的值“4”和元素的位置“3”，按回车结束，重新输出单链表，插入成功。

图2：

单链表的插入操作

3.进行删除操作，根据提示输入删除元素的位置“7”，输出单链表后，第七个语速消失，元素删除成功。

图3：

单链表的删除操作

4.单链表的合并：

再一次运行程序，选择需要创建链表的个数为2个。

按照提示一次输入两个单链表的元素个数和元素值；按回车键结束，此时进行两个单链表的合并操作，输入合并后的链表。

图4：

链表的合并

六、实验心得及经验教训：

由于c语言没学好，刚开始做实验时感到无从下手，根本不知道怎样去写源代码。

后来通过参考书籍和上网查阅资料，依样画葫芦的弄出了代码，但在程序上一编译，出现了很多错误，根本就不能运行。

在编译器的中找到出错的地方，一个个的去改正，有些是由于粗心造成的，有些是因为没有定义造成的。

最常见的就是漏掉“；”和大小写不分。

但有些程序改了好几遍的都该不过来，这就需要不断的去尝试，againandagain,虽然心里会觉得很烦，但改出来，就会有一种成就感，并非得不偿失。

通过本次实验，我知道了写程序是一个循序渐进的过程，并不能一口就吃一个胖子；其次，还要又足够的耐心。

当然，扎实的专业知识是少不了的，因此，上课要认真听讲，课外要花点时间巩固提高。

这样，做实验写程序时就不会手忙脚乱！