链表的基本操作-数据结构实验报告

大学数据结构实验报告

课程名称 数据结构实验 第（四）次实验 实验名称 链表的基本操作 学生姓名 于歌 专业班级 学号 实验成绩 指导老师（签名 ） 日期 2018年10月01日

一、实验目的

1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。

2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。

二、实验要求

1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。

三、实验内容：

1．编写程序完成单链表的下列基本操作： （1）初始化单链表La

（2）在La中插入一个新结点 （3）删除La中的某一个结点

（4）在La中查找某结点并返回其位置 （5）打印输出La中的结点元素值 （6）清空链表 （7）销毁链表

2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

四、思考与提高：

1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？

2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？

五、实验设计

1．编写程序完成单链表的下列基本操作： （1）初始化单链表La LinkList InitList() {

int i,value,n;

LinkList H=(LinkList)malloc(sizeof(LNode)); LinkList P=H; P->next=NULL; do{

printf(\请输入链表的长度:\ scanf(\ if(n<=0)

printf(\输入有误请重新输入！\\n\ }while(n<=0);

printf(\请输入各个元素:\\n\ for(i=0; i

scanf(\

LinkList NEW = (LinkList)malloc(sizeof(LNode)); NEW->data=value; P->next=NEW; NEW->next=NULL; P=NEW; }

printf(\链表建立成功！\\n\ return H->next; }

（2）在La中插入一个新结点

LinkList InsertList(LinkList L,int i,ElemType value) {

LinkList h,q,t=NewLNode(t,value); int x=0; h=q=L; if(i==1)

t->next=h, h=t; else {

while(x++next; t->next=q->next; q->next=t; }

printf(\插入成功！\\n\ return h; }

（3）删除La中的某一个结点

LinkList DeleteList(LinkList L,int i) {

LinkList h,q,de; int x=0; h=q=L; int t; if(i==1)

h=h->next; else {

while(x++next; de=q->next;

if(de->next==NULL) q->next=NULL; else

q->next=de->next; }

printf(\删除成功！\\n\ return h; }

（4）在La中查找某结点并返回其位置

Status LocateList(LinkList L,ElemType value) {

LinkList q=L; int i=0,t;

while(q!=NULL) {

i++;

if(q->data==value) {

printf(\该结点在链表中的位置为第%d个\\n\ return OK; }

q=q->next; }

printf(\该链表中没有该结点！\\n\ return ERROR; }

（5）打印输出La中的结点元素值 Status Print(LinkList L) {