数据结构实验1线性表的基本操作.docx
《数据结构实验1线性表的基本操作.docx》由会员分享，可在线阅读，更多相关《数据结构实验1线性表的基本操作.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构实验1线性表的基本操作
实验1线性表的基本操作
一、需求分析
目的：
掌握线性表运算与存储概念，并对线性表进行基本操作。
1.初始化线性表；
2.向链表中特定位置插入数据；
3.删除链表中特定的数据；
4.查找链表中的内容；
5.销毁单链表释放空间；
二、概要设计
●基础题
主要函数：
初始化线性表InitList（List*L，intms）
向顺序表指定位置插入元素InsertList（List*L，intitem，intrc）
删除指定元素值的顺序表记录DeleteList1（List*L,intitem）
删除指定位置的顺序表记录DeleteList2（List*L,intrc）
查找顺序表中的元素FindList（ListL，intitem）
输出顺序表元素OutputList（ListL）
实验步骤：
1，初始化顺序表
2，调用插入函数
3，在顺序表中查找指定的元素
4，在顺序表中删除指定的元素
5，在顺序表中删除指定位置的元素
6，遍历并输出顺序表
●提高题
要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素
方法：
按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。
编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。
方法：
分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L1，L2元素按顺序放进L。
●本程序主要包含7个函数
主函数main（）
初始化线性表InitList（List*L，intms）
向顺序表指定位置插入元素InsertList（List*L，intitem，intrc）
删除指定元素值的顺序表记录DeleteList1（List*L,intitem）
删除指定位置的顺序表记录DeleteList2（List*L,intrc）
查找顺序表中的元素FindList（ListL，intitem）
输出顺序表元素OutputList（ListL）
提高题的程序
voidCombine（List*L1,List*L2,List*L）
voidDeleteList3（List*L,intx,inty）
二、详细设计
初始化线性表InitList（List*L，intms）
voidInitList（List*L,intms）
{
L->list=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;
L->size=0;
L->MAXSIZE=LIST_INIT_SIZE;
}
向顺序表指定位置插入元素InsertList（List*L，intitem，intrc）
voidInsertList（List*L,intitem,intrc）
{
inti;
if（L->size>=L->MAXSIZE）
{
L->list=（int*）realloc（L->list,（L->MAXSIZE+LISTI）*sizeof（int））;
L->MAXSIZE+=LISTI;
}
for（i=L->size-1;i>=rc-1;i--）
{
L->list[i+1]=L->list[i];
}
L->list[rc-1]=item;
L->size++;
}
删除指定元素值的顺序表记录DeleteList1（List*L,intitem）
voidDeleteList1（List*L,intitem）
{
inti,j;
for（i=0;isize;i++）
{
if（L->list[i]==item）
{
break;
}
}
for（j=i;jsize;j++）
{
L->list[j]=L->list[j+1];
}
L->size--;
}
删除指定位置的顺序表记录DeleteList2（List*L,intrc）
voidDeleteList2（List*L,intrc）
{
inti;
for（i=rc-1;isize;i++）
{
L->list[i]=L->list[i+1];
}
L->size--;
}
查找顺序表中的元素
voidFindList（List*L,intitem）
{
inti;
for（i=0;isize;i++）
{
if（L->list[i]==item）
break;
}
if（L->size==i）
{
printf（"找不到\n"）;
}
else
{
printf（"第%d个元素为%d\n",i+1,item）;
}
}
输出顺序表元素OutputList（ListL）
voidOutputList（List*L）
{
inti;
for（i=0;isize;i++）
{
printf（"%d",L->list[i]）;
}
printf（"\n"）;
}
删除x到y之间的所有元素
voidDeleteList3（List*L,intx,inty）
{
inti,j,temp;
if（x>y）
{
temp=x;
x=y;
y=temp;
}
for（i=0,j=0;isize;i++）
{
if（L->list[i]list[i]>y）
{
L->list[j]=L->list[i];
j++;
}
}
L->size=j;
}
将两个有序的线性表进行合并
voidCombine（List*L1,List*L2,List*L）
{
inti,j,k,temp;
if（L1->size>L2->size）
{
temp=L2->size;
}
else
{
temp=L1->size;
}
i=0,j=0,k=0;
while
（1）
{
if（i==L1->size||j==L2->size）
break;
if（L1->list[i]list[j]）
{
L->list[k]=L1->list[i];
k++;
i++;
}
elseif（L1->list[i]>L2->list[j]）
{
L->list[k]=L2->list[j];
k++;
j++;
}
else
{
L->list[k]=L2->list[j];
k++;
j++;
i++;
}
}
if（i==L1->size）
{
for（i=j;isize;i++,k++）
{
L->list[k]=L2->list[i];
}
}
else
{
for（j=i;jsize;j++,k++）
{
L->list[k]=L1->list[j];
}
}
L->size=k;
}
三、调试分析
体会：
线性表内数据都是顺序排放所以实验中比较容易写出程序
时间复杂度：
初始化线性表InitList（List*L，intms）⊙
（1）
向顺序表指定位置插入元素InsertList（List*L，intitem，intrc）⊙（n）
删除指定元素值的顺序表记录DeleteList1（List*L,intitem）⊙（n）
删除指定位置的顺序表记录DeleteList2（List*L,intrc）⊙（n）
查找顺序表中的元素FindList（ListL，intitem）⊙（n）
输出顺序表元素OutputList（ListL）⊙（n）
删除x到y之间的所有元素⊙（n）
将两个有序的线性表进行合并⊙（n）
四、调试与结果测试
继续阅读
升级会员 