数据结构-实验1-线性表的基本操作
- 格式：doc
- 大小：48.52 KB
- 文档页数：9
.
. 实验1 线性表的基本操作
一、 需求分析
目的：
掌握线性表运算与存储概念，并对线性表进行基本操作。
1.初始化线性表；
2.向链表中特定位置插入数据；
3.删除链表中特定的数据；
4.查找链表中的内容；
5.销毁单链表释放空间；
二、概要设计
基础题
主要函数：
初始化线性表InitList（List* L，int ms）
向顺序表指定位置插入元素InsertList（List* L，int item，int rc）
删除指定元素值的顺序表记录DeleteList1(List* L,int item)
删除指定位置的顺序表记录 DeleteList2（List* L,int rc）
查找顺序表中的元素 FindList（List L，int item）
输出顺序表元素OutputList（List L）
实验步骤：
1，初始化顺序表
2，调用插入函数
3，在顺序表中查找指定的元素
4，在顺序表中删除指定的元素
5，在顺序表中删除指定位置的元素
6，遍历并输出顺序表
提高题 .
. 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素
方法：
按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。
编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。
方法：
分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。
本程序主要包含7个函数
主函数main()
初始化线性表InitList（List* L，int ms）
向顺序表指定位置插入元素InsertList（List* L，int item，int rc）
删除指定元素值的顺序表记录DeleteList1(List* L,int item)
删除指定位置的顺序表记录 DeleteList2（List* L,int rc）
查找顺序表中的元素 FindList（List L，int item）
输出顺序表元素OutputList（List L）
提高题的程序
void Combine(List* L1,List* L2,List* L)
void DeleteList3(List* L,int x,int y)
二、 详细设计
初始化线性表InitList（List* L，int ms）
void InitList(List* L,int ms)
{
L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
L->size=0;
L->MAXSIZE=LIST_INIT_SIZE;
} .
.
向顺序表指定位置插入元素InsertList（List* L，int item，int rc）
void InsertList(List* L,int item,int rc)
{
int i;
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,int item)
void DeleteList1(List* L,int item)
{
int i,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,int rc）
void DeleteList2(List* L,int rc)
{
int i;
for (i=rc-1;isize;i++)
{
L->list[i]=L->list[i+1];
}
L->size--;
}
查找顺序表中的元素
void FindList(List* L,int item)
{
int i;
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（List L）
void OutputList(List* L)
{
int i;
for (i=0;isize;i++)
{
printf("%d ",L->list[i]);
}
printf("\n");
}
删除x到y之间的所有元素
void DeleteList3(List* L,int x,int y)
{
int i,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;
}
将两个有序的线性表进行合并
void Combine(List* L1,List* L2,List* L)
{
int i,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++;
}
else if (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，int ms） ⊙(1)
向顺序表指定位置插入元素InsertList（List* L，int item，int rc）
⊙(n)
删除指定元素值的顺序表记录DeleteList1(List* L,int item) ⊙(n)
删除指定位置的顺序表记录 DeleteList2（List* L,int rc）⊙(n)
查找顺序表中的元素 FindList（List L，int item）⊙(n)
输出顺序表元素OutputList（List L）⊙(n)
删除x到y之间的所有元素 ⊙(n)
