实验二-单链表实现.doc

实 验 报 告
课程名称数据结构课程设计
实验项目 单链表的实现
实验仪器 PC机一台
学 院_____信息管理学院_______
专 业电子商务
班级/学号___电子商务1401______
学生姓名 ____________
实验日期 ___12。27_______
成 绩 _______________________
指导教师 _________________
北京信息科技大学
信息管理学院
（课程上机)实验报告
实验课程名称：数据结构课程设计 专业：电子商务班级：商务1401
学号：姓名：成绩:
实验名称
单链表的实现
实验地点
小营学院机房
实验时间
12。29
1. 实验目的：
1） 理解线性表的逻辑特点；
2） 掌握单链表的定义及C语言实现；
3） 熟练掌握在单链表中实现各种基本操作；
4） 掌握使用单链表解决一些简单应用问题的编程.
2. 实验要求:
1)学时为4学时；
2)在上机前完成源程序;
3）能在机器上正确、调试运行程序；
4）本实验需提交实验报告；
5）实验报告文件命名方法:实验2_xx班_学号后两位_姓名。doc

3. 实验内容和步骤：
1) 基于单链表实现线性表的以下操作：
a) 在表头插入元素
b) 在表尾插入元素
c) 在指定的位置i插入元素
d) 删除操作
e) 查找元素
f) 求表长度
g) 清空操作
h) 判断线性表是否为空
i) 按位序打印线性表中的元素
2) 单链表的简单应用:
a) 调用基本操作编写算法删除第i个开始的k个元素；
b) 计算单链表中值为x的元素的个数；
c) 将x插入到单链表的适当位置上，以保持单链表中元素的有序性;
d) 将线性表元素进行就地逆置
e) 将两个单链表合并为一个单链表。
4. 实验过程:
1)基于单链表实现线性表的以下操作：
在表头插入元素
int Insert_First（LinkList ＊Head_pointer,ElemType x)

｛
Node ＊p；
P=（LinkList)malloc(sizeof（Node）)；
if（p==NULL）
return OverFlow；
p—>data=x；
p—〉next=＊Head_pointer;
*Head_pointer=p;
Return OK;
｝
在表尾插入元素
int Insert_Last（LinkList *Head_pointer，ElemType x)
{
Node *p,＊q；
P=（LinkList）malloc(sizeof（Node）);
if(p==NULL）
return OverFlow；
p—〉data=x；
p-〉next=NULL;
q=＊Head_pointer;
if（q==NULL）
＊Head_pointer=p；
else
{while（q->next！=NULL）
q=q->next；
q-〉next=p；
}
Return OK；
｝
在指定的位置i插入元素
int Insert_i （LinkList ＊Head_pointer，ElemType x,int i)
Node ＊p,＊q；
P=（LinkList）malloc（sizeof(Node)）;
if（p==NULL)
return OverFlow；
p->data=x；
if(i==0）
{p—>next=*Head_pointer;
*Head_pointer=p;
return OK；
｝
else
｛q=*Head_pointer；
while（q—〉next!=NULL＆＆i〉1）
｛q=q—〉next;i—-；}
if（q！=NULL)
p-〉next=q—〉next；
q->next=p；
return OK;
｝
return Error;
}
}
删除操作
int Delete_LinkList （LinkList *Head_pointer，ElemType x）
Node ＊p，＊q;
p=＊Headpointer;
if(p-〉data==x）
｛*Head_pointer=(＊Head_pointer）—>next；
free（p）；
return OK；
｝
q=p；p=p->next；
｝
｝
return Error;
}
查找元素
LinkList Location_LinkList(LinkList Head,ElemType x）
｛LinkList p;
p=Head;
while(p！=NULL）
{if（p—〉data==x）break；
p=p—〉next；
}
return p;
}
求表长度
int Length_LinkList(LinkList Head）
｛Node ＊p;
int sum=0；
p=Head；
while(p!=NULL）
｛sum++;
p=p—〉next；
｝
return sum；
｝
清空操作
void SetNull_LinkList(LinkList *Head_pointer)
{Node ＊p，＊q；
p=*Head_pointer；
while（p!=NULL)
q=p;
p=p->next；
free(q）；
｝
＊Head_pointer=NULL;
}
判断线性表是否为空
void IfNull_LinkList(LinkList ＊Head_pointer）
{if（＊Head_pointer==NULL)
returnTrue;
else return False；
}
按位序打印线性表中的元素
void Show_LinkList(LinkList Head）
｛Node *p；
printf（”\n"）；
p=Head；
if(p==NULL)
printf（”\n空表！”）；
while（p!=NULL）
｛printf("%d”,p-〉data）;
p=p—〉next;
｝
}
2）单链表的简单应用:
调用基本操作编写算法删除第i个开始的k个元素；

计算单链表中值为x的元素的个数;
将x插入到单链表的适当位置上，以保持单链表中元素的有序性；
将线性表元素进行就地逆置
将两个单链表合并为一个单链表。
1.调用基本操作编写算法删除第i个开始的k个元素；
#include ”stdio。h”
#include ”stdlib。h”
typedef struct node
｛
int data;
struct node ＊next；
}Node，＊LinkList;
void Delete_LinkList（LinkList *Head_pointer，int i,int k)
｛
int j=i+k—1；
Node ＊p，＊q,＊m,＊n；
q=＊Head_pointer;
while（q—〉next！=NULL&&i〉1)
｛n=q;q=q—>next；i--；}
p=*Head_pointer；
while（p-〉next！=NULL&＆j〉1)
｛p=p—>next；j——；｝
while（q!=p）
｛
m=q；
q=q—〉next;
free(m)；
}
n—>next=p—>next;
free（p）;
｝
int insert_First（LinkList ＊Head_pointer,int x）
｛
Node *p；
p=（LinkList)malloc（sizeof（Node））;
if（p==NULL）
return —1；
p—〉data=x;
p—〉next=＊Head_pointer；
*Head_pointer=p;
return 1；
｝
void Show_LinkList（LinkList Head）
｛
Node ＊p；
printf("\n"）;
p=Head;
if（p==NULL）
printf（"\n NULL”）；
whilep！=NULL）
{
printf(" %d"，p-〉data）;
p=p->next;
｝
｝
int main （）
{
int m;
int i，k；
LinkList Head;
Head=NULL;
scanf("%d ％d”，＆i，＆k）；
for(m=0；m〈7；m++）
if（!insert_First（＆Head,m))
break；
Show_LinkList（Head);
Delete_LinkList(&Head，i，k）;
Show_LinkList（Head）；
return 0;
｝
2。计算单链表中值为x的元素的个数
#include ”stdio.h”
#include ”stdlib。h"
typedef struct node
｛
int data；
struct node ＊next;
｝Node，*LinkList；
int Location_LinkList(LinkList Head,int x)
{
Node ＊p;
int sum=0;
p=Head;
while(p！=NULL）
｛
if(p->data==x）
sum++；
p=p—〉next；
｝
return sum;
｝
int insert_First（LinkList *Head_pointer，int x）
｛
Node ＊p;
p=（LinkList）malloc（sizeof（Node）)；
if(p==NULL）
return —1;
p—〉data=x；
p->next=*Head_pointer;
＊Head_pointer=p;
return 1；
｝
void Show_LinkList（LinkList Head)
{
Node ＊p；
printf("\n"）;
p=Head；
if(p==NULL)
printf(”\n NULL");
while(p！=NULL)
｛
printf（" %d\n”，p->data);
p=p->next;
｝
｝
int main (）
｛
int m，x，sum；
LinkList Head；
Head=NULL；
scanf（"％d",＆x）;
for（m=0；m〈7；m++)
if(!insert_First（＆Head，m））
break；
Show_LinkList（Head）；
sum=Location_LinkList（Head，x）;
printf（”%d\n”，sum)；
return 0;
｝
3.将x插入到单链表的适当位置上，以保持单链表中元素的有序性
＃include ”stdio.h"
#include "stdlib。h”
typedef struct node
｛
int data；
struct node *next；
｝Node，＊LinkList；
int Location_LinkList（LinkList Head，int x）
｛
Node *p;
int sum=0;
p=Head;
while（p！=NULL）

｛
if(p->data〈=x)
sum++；
p=p—>next；
｝
return sum；
}
int insert_i（LinkList ＊Head_pointer,int x，int i)
｛
Node *p,*q;
p=（LinkList)malloc(sizeof(Node)）；
if(p==NULL）
return -1；
p—〉data=x；
if（i==0)
{
p—〉next=＊Head_pointer;
*Head_pointer=p；
return 1;
｝
else
｛
q=＊Head_pointer；
while(q—>next！=NULL&&i>1）
{q=q-〉next；i-—；}
if（q!=NULL）
｛p—〉next=q—>next；
q-〉next=p；
return 1；
｝
return —2；
｝
｝
void Show_LinkList(LinkList Head)
{
Node ＊p;
printf(”\n”）;
p=Head;
if(p==NULL)
printf（"\n NULL”）；
while（p!=NULL）
｛
printf（” ％d"，p—〉data）；
p=p—>next;
}
｝
int main （)
{
int i，a［7]=｛10，20，30，40，50，60,70};
int x,sum；
LinkList Head；
Head=NULL；
scanf（”%d"，＆x)；
for(i=0；i〈7;i++）
if(insert_i（＆Head,a［i］，i）！=1）
break;
Show_LinkList（Head)；
sum=Location_LinkList（Head,x）;
if（insert_i(＆Head，x，sum)！=1)
printf(”fail!\n”);
Show_LinkList(Head）;
return 0；
}
4。将线性表元素进行就地逆置
＃include ”stdio.h”
＃include ”stdlib。h”
typedef struct node
{
int data；
struct node *next;
｝Node，＊LinkList;
LinkList op_LinkList(LinkList Head）
｛
Node *p，*q；
p=Head；
Head=NULL；
while（p）
{
q=p；
p=p—>next;
q—>next=Head；
Head=q;
}
return Head；
｝
int insert_First（LinkList *Head_pointer,int x）
｛
Node *p；
p=（LinkList)malloc(sizeof（Node））;
if（p==NULL）
return —1；
p-〉data=x；
p—〉next=＊Head_pointer;
＊Head_pointer=p；
return 1；
｝
void Show_LinkList（LinkList Head）
｛
Node ＊p；
printf(”\n”）；
p=Head；
if（p==NULL)
printf（”\n NULL”);
while（p！=NULL）
｛
printf（” ％d\n"，p—〉data)；
p=p—>next;
｝
｝
int main （)
｛
int m;
LinkList Head；
LinkList HL;
Head=NULL；
for（m=0;m〈7；m++)
if(!insert_First（&Head,m））
break;
Show_LinkList（Head)；
HL=op_LinkList（Head）；
Show_LinkList（HL）;
return 0;
｝
5。将两个单链表合并为一个单链表
＃include ”stdio。h”
＃include "stdlib.h”
typedef struct node
｛
int data;
struct node *next;
｝Node,*LinkList；
void contact(LinkList Head，LinkList HT）
{
Node ＊p；
p=Head；
while(p->next)
p=p->next;
p—〉next=HT；
}
int insert_First(LinkList *Head_pointer，int x)
｛
Node *p；
p=（LinkList)malloc（sizeof（Node）)；
if(p==NULL）
return —1；
p-〉data=x；
p—>next=＊Head_pointer；
*Head_pointer=p；
return 1；
｝
void Show_LinkList（LinkList Head)
｛
Node ＊p；
printf(”\n”）;
p=Head；
if(p==NULL)
printf（”\n NULL”）;
while（p！=NULL)
｛
printf(" %d”，p—〉data）;
p=p-〉next；
｝
｝
int main （)
｛
int m;
LinkList Head；
LinkList HT；
Head=NULL；
HT=NULL；
for（m=0；m<20;m++）
if(!insert_First（＆Head,m））
break;
for（m=0；m<10；m++)
if(！insert_First（&HT，m））
break；
Show_LinkList(Head);
Show_LinkList(HT）；
contact（Head，HT);
Show_LinkList（Head）;
return 0;
｝

5. 实验总结：理解线性表的逻辑特点;掌握了单链表的定义及C语言实现。但是还有很多不清楚的地方运行时有许多错误。
说明：
1. 实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好,然后作为实验报告模版供学生使用；
2. 实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3. 实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4. 实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等;
5. 源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页.