数据结构线性表实验报告文档格式.doc
《数据结构线性表实验报告文档格式.doc》由会员分享，可在线阅读，更多相关《数据结构线性表实验报告文档格式.doc（8页珍藏版）》请在冰点文库上搜索。
有序顺序表中的数据元素按数据元素值非递减有序。
设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。
（3）
设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。
并设计一个主函数，验证该合并函数的正确性。
程序代码：
2－21
（1）头文件LinList.h如下：
typedefstructnode
{
DataTypedata;
structnode*next;
}SLNode;
/*
（1）初始化ListInitiate（SLNode**head）*/
voidListInitiate（SLNode**head）
{/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
if（（*head=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit
（1）;
（*head）->
next=NULL;
/*置结束标记NULL*/
}
/*
（2）求当前数据元素个数ListLength（SLNode*head）*/
intListLength（SLNode*head）
{
SLNode*p=head;
intsize=0;
while（p->
next!
=head）
{
p=p->
next;
size++;
}
returnsize;
}
/*（3）插入ListInsert（SLNode*head，inti，DataTypex）*/
/*在带头结点的单链表的第i（0<
=i<
=size）个结点前*/
/*插入一个存放数据元素x的结点。
插入成功时返回1，失败返回0*/
intListInsert（SLNode*head,inti,DataTypex）
SLNode*p,*q;
intj;
p=head;
j=-1;
=head&
&
j<
i-1）
/*最终让指针指向第i-1个结点*/
p=p->
j++;
if（j!
=i-1）
printf（"
Theinsertedpositioniserror!
"
）;
return0;
/*生成新结点由指针q指示*/
if（（q=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit
（1）;
q->
data=x;
next=p->
p->
next=q;
return1;
/*（4）删除ListDelete（SLNode*head，inti，DataType*x）*/
/*删除带头结点的单链表head的第i（0<
/*被删除结点的数据元素域由x带回。
删除成功时返回1，失败返回0*/
intListDelete（SLNode*head,inti,DataType*x）
SLNode*p,*s;
p->
next->
Thedeletedpositionofparameteriserror!
s=p->
/*指针s指指向ai结点*/
*x=s->
data;
/*删除*/
free（s）;
/*释放指针s所指结点的内存空间*/
/*（5）取数据元素ListGet（SLNode*head，inti，DataType*x）*/
intListGet（SLNode*head,inti,DataType*x）
SLNode*p;
i）
=i）
Thegottenpositionofparameteriserror!
*x=p->
return1;
/*（6）撤销单链表Destroy（SLNode**head）*/
voidDestroy（SLNode**head）
SLNode*p,*p1;
p=*head;
while（p!
=NULL）
p1=p;
free（p1）;
*head=NULL;
（2）测试主函数如下：
#include<
stdio.h>
/*包含printf（）函数*/
stdlib.h>
/*包含exit（）函数*/
malloc.h>
/*包含malloc（）函数*/
typedefintDataType;
/*定义DataType为int*/
#include"
LinList.h"
/*包含单链表的头文件*/
voidmain（void）
SLNode*head;
/*定义头指针变量*/
inti,x;
ListInitiate（&
head）;
/*初始化*/
for（i=0;
i<
10;
i++）/*插入10个数据元素*/
{
if（ListInsert（head,i,i+1）==0）
{
printf（"
error!
\n"
return;
}
}
if（ListDelete（head,4,&
x）==0）/*删除第四个数据元素*/
printf（"
return;
i<
ListLength（head）;
i++）/*显示当前数据元素*/
if（ListGet（head,i,&
x）==0）/*取数据元素*/
}
else
%d"
x）;
/*显示*/
Destroy（&
/*撤销单链表*/
}
2－22设计一个有序顺序表
头文件程序如下：
#defineNULL0
typedefstruct
DataTypeList[MaxSize];
intsize;
}SeqList;
voidlistInitiate（SeqList*L）/*初始化顺序表L*/
L->
size=0;
/*定义初始化数据元素个数*/
}
intListLength（SeqListL）
returnL.size;
intListInsert（SeqList*L,inti,DataTypex）
intj;
if（L->
size>
=MaxSize）
printf（"
顺序表已满无法插入！
return0;
elseif（i<
0||i>
L->
size）
参数i不合法！
else
for（j=L->
size;
j>
i;
j--）
L->
List[j]=L->
List[j-1];
List[i]=x;
size++;
intListDelete（SeqList*L,inti,DataType*x）
intj;
if（L->
size<
=0）
顺序表已空无数据元素可删！
return0;
elseif（i<
size-1）
else
*x=L->
List[i];
for（j=i+1;
size-1;
j++）
L->
List[j-1]=L->
List[j];
size--;
return1;
intListGet（SeqListL,inti,DataType*x）
if（i<
L.size-1）
*x=L.List[i];
/*测试主函数设计如下：
*/
#include<
#defineMaxSize100
SeqList.h"
intSLOrderInsert（SeqList*L,DataTypex）
intj;
if（L->
=MaxSize-1）
printf（"
return0;
for（j=L->
j>
0&
x<
list[j];
j--）
list[j+1]=L->
list[j+1]=x;
return1;
{
SeqListMyList;
inta[]={1,2,4,5,6,8,9};
/*数组a中的数据元素递增有序*/
inti,n=7;
intx;
ListInitiate（&
MyList）;
for（i=0;
n+1;
i++）
SLOrderInsert（&
MyList,a[i]）;
ListGet（MyList,i,x）;
printf（"
%d"
a[i]）;
实验结果：
（1）2－21运行结果如下：
（2）2－22运行结果如下：
总结与思考
（1）在TC2的使用过程中遇到很多问题，路径问题总是导致错误。
有序顺序表的操作集合和线性表的操作集合类似。
（2）带头结点循环链表的操作实现与带头结点的单链表的操作实现方法相似，但也有差别主要在：
1、在初始化函数中，把语句（*head）->
next=NULL改为（*head）->
next=head。
2、在其它函数中，循环判定条件p->
=NULL和p->
=NULL中的NULL换成头指针head.
升级会员 