实验1 顺序表的定义和应用
1.实验目的：
- 掌握顺序表的定义；
- 掌握顺序表的基本操作：初始化、插入、删除、定位、查找等。
2.实验内容：
用顺序表表示整数集合A, B，实现A=AUB和A=A∩B.
定义顺序表类型，写出向顺序表初始化InitList_Sq (),向某位置插入数据(ListInsert_Sq)，删除某位置数据(ListDelete_Sq)，显示所有数据(ListTraverse_Sq)，根据位置取元素(GetElem_Sq)，定位数据(LocateElem_Sq)的算法，并实现集合A=AUB，A=A∩B。
3.抽象数据类型设计
实验要求可知，本实验使用的数据结构是线性表。线性表的抽象数据类型如下：
ADT List{
数据对象：D={ai|ai∈ElemSet,i=1,2, ……,n,n>=0}
数据关系：R={<ai-1,ai>| ai-1,ai∈D,i=2,3, ……,n}
基本操作：
- InitSeqList(&L)
操作结果：构造一个空的线性表L。
- DestroySeqList(&L)
初始条件：线性表已存在
操作结果：销毁线性表L
- ClearnList(&L)
初始条件：线性表L已存在
操作结果：将L重置为空表
- ListEmpty(L)
初始条件：线性表L已存在
操作结果：若L为空表，则返回true,否则返回false.
- ListLength(L)
初始条件：线性表已存在
操作结果：返回L中数据元素个数
- GetElem(L,I,&e)
初始条件：线性表L已存在，l<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值
- LocateElem(L,e)
初始条件：线性表L已存在
操作结果：返回L中第1个与e相等的元素的位置序号。若这样的数据元素不存在，则返回值为0
- PriorElem（L，cur_e,&pre_e）
初始条件：线性表L已存在
操作结果：若cure_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。
- NextElem(L,cur_e，&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
- ListInsert(&L,i,e)
初始条件：线性表L已存在，1<=i<=ListLength(L)+1
操作结果：在L中第i个位置之前插入新的元素e，L的长度加1
- ListDelete(&L,I,&e)
初始条件：线性表L已存在且非空，1<=i<=ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
}ADT List；
4.存储结构及基本操作的定义与实现
- 顺序表存储结构定义：
<此处为顺序表结构定义>
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType *elem;//储存空间基址
int length; //当前长度·
int listsize; //当前分配的储存容量
}SqList;- 基本操作的函数声明:
int InitList_Sq(SqList &L)；//初始化顺序表
Status InitList_Sq (SqList &L);//顺序表的初始化
Status ListInsert_Sq(SqList &L,int i,ElemType e);//在顺序表L中第i个位置之前插入新的元素e
Status ListDelete_Sq(SqList &L,int i,ElemType &e);//删除元素
Status ListTraverse_Sq(SqList L);//遍历
Status GetElem_Sq(SqList L,int i,ElemType &e);//L为带头结点的单链表的头指针
int LocateElem_Sq(SqList L,ElemType e);
void Listinput(SqList &L,int n);
//顺序表的集合运算
void ListUnion_Sq(SqList La,SqList Lb,SqList &Lc);//交集
void ListIntersec_Sq(SqList La,SqList Lb,SqList &Lc);//并集- 基本操作的函数实现:
<要求：多个函数按顺序编号>
.
//初始化顺序表
Status InitList_Sq (SqList &L)
{//构造空1列表
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(L.elem==NULL) exit(OVERFLOW);//储存分配失败
L.length = 0; //空表长度为0
L.listsize = LIST_INIT_SIZE;//初始储存容量
return OK;
}//InitList_Sq
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
//在顺序表L中第位置之前插入新的元素e
if(i<1||i>L.length+1)return ERROR;
if(L.length>=L.listsize)//储存空间满了扩容
{
ElemType *newbase;
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
L.elem = newbase;
L.listsize+=LISTINCREMENT;
}
ElemType *p,*q;
q=&(L.elem[i-1]);
for(p = &(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
//插入元素往后移
*p= e;
++L.length;
return OK;
}//ListInsert_Sq
Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if((i<1)||(i>L.length))return ERROR;
ElemType *p,*q;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
Status ListTraverse_Sq(SqList L)//遍历顺序表所有元素
{
int i;
for(i=0;i<L.length;i++)
printf("%d",L.elem[i]);
printf("\n");
return OK;
}
//获取元素
Status GetElem_Sq(SqList L,int i,ElemType &e)
{
e=L.elem[i-1];
return OK;
}
//顺序表的定位元素
int LocateElem_Sq(SqList L,ElemType e)
{
int i;
for(i=0;i<L.length;i++)
if(L.elem[i]==e)
return i+1;
return 0;
}
void Listinput(SqList &L,int n)
{
int i;
for(i=0;i<n;i++)
scanf("%d",&(L.elem[i]));
L.length=n;
}5.功能实现与运行截图
使用顺序表存储集合
- A=AUB的代码实现与运行结果:
//A=AUB的代码实现
<此处为源代码>
//并集
void ListUnion_Sq(SqList La,SqList Lb,SqList &Lc)
{
int i;
ElemType e;
for(i=0;i<La.length;i++)
ListInsert_Sq(Lc,Lc.length+1,La.elem[i]);
for(i=1;i<=Lb.length;i++)
{
GetElem_Sq(Lb,i,e);
if(LocateElem_Sq(La,e)==0)
ListInsert_Sq(Lc,Lc.length+1,e);
}
}- A=A∩B的代码实现与运行结果：
//A=A∩B的代码实现
<此处为源代码>
//交集
void ListIntersec_Sq(SqList La,SqList Lb,SqList &Lc)
{
int i;
for(i=0;i<=La.length;i++)
if(LocateElem_Sq(Lb,La.elem[i])!=0)
ListInsert_Sq(Lc,Lc.length+1,La.elem[i]);
}//运行结果截图
<此处为运行结果截图>
