线性表的动态分配顺序存储结构.docx
《线性表的动态分配顺序存储结构.docx》由会员分享，可在线阅读，更多相关《线性表的动态分配顺序存储结构.docx（12页珍藏版）》请在冰点文库上搜索。
线性表的动态分配顺序存储结构
util.h
//通用头文件:
存放公共函数或变量
#include"stdio.h"
#include"stdlib.h"
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK2
#defineERROR-1
#defineINFEASIBLE-2//不可行
#defineOVERFLOW-3
//声明函数返回值的数据类型
typedefintStatus;
//声明线性表中元素的数据类型
typedefintElemType;
//声明相关辅助函数
StatusCompare（ElemType,ElemType）;
voidVist（ElemType）;
//声明函数指针
typedefStatus（*pCompare）（ElemType,ElemType）;
typedefvoid（*pVisit）（ElemType）;
u.til.cpp
//通用函数的定义
#include"util.h"
StatusCompare（ElemTypee1,ElemTypee2）
{//操作结果：
比较e1和e2是否相等。
若相等，则返回TRUE；否则返回FALSE
if（e1==e2）
returnTRUE;
else
returnFALSE;
}//Compare
voidVisit（ElemTypee）
{//操作结果：
在屏幕上输出e
printf（"%d",e）;
}//Visit
SqList.h
//顺序表头文件
#include"util.h"
//线性表的动态分配顺序存储结构
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间的分配增量
typedefstruct{
ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量
}SqList;
//顺序表的基本操作
StatusInitList_Sq（SqList&）;
StatusDestroyList_Sq（SqList&）;
//声明顺序表的引用型操作
StatusListEmpty_Sq（SqList）;
intListLength_Sq（SqList）;
ElemTypePriorElem_Sq（SqList,ElemType,ElemType&）;
ElemTypeNextElem_Sq（SqList,ElemType,ElemType&）;
ElemTypeGetElem_Sq（SqList,int,ElemType&）;
intLocateElem_Sq（SqList,ElemType,pCompare）;
voidListTraverse_Sq（SqList,pVisit）;
//声明顺序加工型操作
StatusClearList_Sq（SqList&）;
StatusPutElem（SqList&,int,ElemType）;
StatusListInsert_Sq（SqList&,int,ElemType）;
StatusListDelete_Sq（SqList&,int,ElemType&）;
voidUnion（SqList&,SqList）;
voidPurge（SqList&,SqList）;
voidMergeList_Sq（SqList,SqList,SqList&）;
SqList.cpp
//顺序表的操作
#include"SqList.h"
//顺序表的基本操作
StatusInitList_Sq（SqList&L）
{//操作结果：
构造一个空线性表L
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
//申请分配存储空间
if（!
L.elem）exit（OVERFLOW）;//存储分配失败
L.length=0;//顺序表长度初始化为0
L.listsize=LISTINCREMENT;//当前存储容量大小为INCREMENT
returnOK;
}//InitList_Sq
StatusDestroyList_Sq（SqList&L）
{
//初始条件：
顺序表L存在
//操作结果：
销毁顺序表L
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
free（L.elem）;//释放存储空间
L.length=0;
L.listsize=0;
L.elem=NULL;
returnOK;
}//DestroyList_Sq
//顺序表的引用型操作
StatusListEmpty_Sq（SqListL）
{
//初始条件：
顺序表L存在
//操作结果：
查看顺序表L是否为空表，是则返回TRUE；反之返回FALSE
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
if（L.length==0）
returnTRUE;
else
returnFALSE;
}//ListEmpty_Sq
intListLength_Sq（SqListL）
{
//初始条件：
顺序表L存在
//操作结果：
返回顺序表长度
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
returnL.length;
}//ListLength_Sq
ElemTypePriorElem_Sq（SqListL,ElemTypecur_e,ElemType&pre_e）
{
//初始条件：
顺序表L存在
//操作结果：
若cur_e在顺序表中，且不是第一个元素，则用pre_e返回其前驱
//否则操作不可行
intpos=2;//cur_e当前位置pos≥2
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
ElemType*p=L.elem+1;//从顺序表第2个位置查找cur_e
while（pos++<=L.length&&（*p++）!
=cur_e）;//pos范围2≤pos≤L.Length
if（pos>L.length）returnINFEASIBLE;//到表结束未找到cur_e,操作不可行
else{
pre_e=（*--p）;//pre_e为当前值cur_e的前驱
returnpre_e;//返回前驱pre_e
}
}//PriorElem_Sq
ElemTypeNextElem_Sq（SqListL,ElemTypecur_e,ElemType&next_e）
{
//初始条件：
顺序表L存在
//操作结果：
若cur_e在顺序表中，且不是最后一个元素，则用next_e返回其后继
//否则操作不可行
intpos=1;//cur_e当前位置pos≥2
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
ElemType*p=L.elem;//从顺序表第1个位置查找cur_e
while（pos++=cur_e）;//pos范围1≤pos＜L.Length
if（pos==L.length）returnINFEASIBLE;//到表尾未找到cur_e,操作不可行
else{
next_e=（*++p）;//pre_e为当前值cur_e的前驱
returnnext_e;//返回前驱pre_e
}
}//NextElem_Sq
ElemTypeGetElem_Sq（SqListL,intpos,ElemType&e）
{
//初始条件：
顺序表L存在，且1≤pos≤L.Length
//操作结果：
用e返回pos位置的值
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
if（pos<1||pos>L.length）returnERROR;//pos取值范围1≤pos≤L.Length
else{
e=*（L.elem+pos-1）;
returne;//用e返回pos位置的值
}
}//GetElem
intLocateElem_Sq（SqListL,ElemTypee,pCompareequal）
{
//初始条件：
顺序表L存在
//操作结果：
若元素e在顺序表中存在，则返回其在顺序表中第一次出现的位置
//否则，操作不可行
intpos=1;//pos≥1
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
ElemType*p=L.elem;//从顺序表第1个位置查找cur_e
while（pos++<=L.length&&!
equal（*p++,e））;//遍历顺序表查找第一个cur_e
if（pos>L.length）
return0;//到表结束时未找到元素e
else
returnpos;//返回顺序表中出现e的第一个位置
}//LocateElem_Sq
voidListTraverse_Sq（SqListL,pVisitvisit）
{
//初始条件:
顺序表L存在
//操作结果:
遍历顺序表，在屏幕上显示顺序表元素
intpos;
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
for（pos=1;pos<=L.length;pos++）visit（L.elem[pos-1]）;
printf（"\n"）;
}//ListTraverse_Sq
//加工型操作
StatusClearList_Sq（SqList&L）
{
//初始条件：
线性表L已存在
//操作结果：
将L重置为空表
L.length=0;//空表长度为0
returnOK;
}//ClearList_Sq
StatusPutElem_Sq（SqList&L,intpos,ElemTypee）
{
//初始条件：
顺序表L存在，且pos范围为1≤pos≤L.length
//操作结果：
顺序表第pos个位置赋值为e
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
L.elem[pos-1]=e;
returnOK;
}//PutElem_Sq
StatusListInsert_Sq（SqList&L,intpos,ElemTypee）
{
//初始条件：
顺序表L存在，且pos范围为1≤pos≤L.length+1
//操作结果：
将e插入到顺序表第pos个位置，顺序表长度加1
ElemType*newbase;
ElemType*p,*q;
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
if（pos<1||pos>L.length+1）returnINFEASIBLE;//pos值不合法
if（L.length>L.listsize）{//存储空间满，增加分配
newbase=（ElemType*）realloc（L.elem,
（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
//重新分配存储块
if（!
newbase）exit（OVERFLOW）;//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//表长加1
}
q=&L.elem[pos-1];//q指向需要右移的元素位置
for（p=&L.elem[L.length-1];p>=q;p--）*（p+1）=*p;
//右移元素
*q=e;
L.length++;
returnOK;
}//ListInsert_Sq
StatusListDelete_Sq（SqList&L,intpos,ElemType&e）
{
//初始条件：
顺序表L存在，且pos范围为1≤pos≤L.length
//操作结果：
将顺序表中第pos个位置的元素e删除，并用e返回
ElemType*p,*q;
if（!
L.elem）exit（ERROR）;//顺序表不存在，函数调用失败
if（pos<1||pos>L.length）returnINFEASIBLE;//pos值不合法
q=L.elem+pos-1;//p指向被删除元素的位置）
e=*q;//被删除元素赋值给e
for（p=&L.elem[L.length-1];p>=++q;p--）*（p-1）=*p;
//左移元素
L.length--;
returne;
}//ListDelete_Sq
voidUnion（SqList&La,SqListLb）//A∪B
{
inti;
intLa_Len,Lb_Len;
ElemTypee;
pCompareequal;
La_Len=ListLength_Sq（La）;//即La_Len=La.length
Lb_Len=ListLength_Sq（Lb）;//即Lb_Len=Lb.length
for（i=1;i<=Lb_Len;i++）{
GetElem_Sq（Lb,i,e）;//e=Lb.elem[i-1]
if（!
LocateElem_Sq（La,e,equal））
ListInsert_Sq（La,++La_Len,e）;//插入La之后
}
}//union
voidPurge（SqList&La,SqListLb）//提取A集合（纯化）
{
inti;
intLa_Len,Lb_Len;
ElemTypee,en;
pCompareequal;//Compare函数指针
InitList_Sq（La）;//构造一个空顺序表
La_Len=ListLength_Sq（La）;//取La当前长度
Lb_Len=ListLength_Sq（Lb）;//取Lb当前长度
for（i=1;i<=Lb_Len;i++）{//遍历顺序表Lb
GetElem_Sq（Lb,i,e）;//e=Lb.elem[i-1];
if（!
equal（en,e））ListInsert_Sq（La,++La_Len,e）;
en=e;//en=Lb.elem[i-1]
}
}//Purge
voidMergeList_Sq（SqListLa,SqListLb,SqList&Lc）//合并升序序列
{
InitList_Sq（Lc）;//构造一个空顺序表Lc
inti=1;//i指示La位置
intj=1;//j指示Lb位置
intLa_Len,Lb_Len,Lc_Len;
ElemTypeai,bj;//暂存La、Lb中的元素
//取La、Lb、Lc当前长度
La_Len=ListLength_Sq（La）;
Lb_Len=ListLength_Sq（Lb）;
Lc_Len=ListLength_Sq（Lc）;
//将短顺序表取出与长顺序表进行排序，并插入Lc中
while（i<=La_Len&&j<=Lb_Len）{
GetElem_Sq（La,i,ai）;//ai=La.elem[i-1];
GetElem_Sq（Lb,j,bj）;//bj=Lb.elem[j-1];
//将小的值插入Lc
if（ai<=bj）{
ListInsert_Sq（Lc,++Lc_Len,ai）;
i++;
}
else{
ListInsert_Sq（Lc,++Lc_Len,bj）;
j++;
}
}
while（i<=La_Len）{//如果La尚有元素未插入Lc，则全部插入
GetElem_Sq（La,i++,ai）;
ListInsert_Sq（Lc,++Lc_Len,ai）;
}
while（i<=Lb_Len）{//如果Lb尚有元素未插入Lc，则全部插入
GetElem_Sq（Lb,i++,bj）;
ListInsert_Sq（Lc,++Lc_Len,bj）;
}
}//MergeList_Sq
main.cpp
//main（检验基本操作的主程序）
#include"SqList.h"
voidmain（）
{
//定义试验变量
SqListL;
ElemTypee;
inti;
//初始化顺序表
InitList_Sq（L）;
printf（"初始化L后：
L.elem=%dL.length=%dL.listsize=%d\n",L.elem,L.length,L.listsize）;
//在顺序表首部插入：
1，2，3，4，5
for（i=1;i<=5;i++）{
ListInsert_Sq（L,1,i）;
e=L.elem[0];
printf（"第%d个元素为%d，此时L.elem=%dL.length=%dL.listsize=%d\n",i,e,L.elem,L.length,L.listsize）;
}
//判空操作
printf（"顺序表L是否为空：
%d（1是0否）\n",ListEmpty_Sq（L））;
//清空顺序表并判空
ClearList_Sq（L）;
printf（"顺序表L是否为空：
%d（1是0否）\n",ListEmpty_Sq（L））;
//在顺序表尾端插入：
1，2，3，4，5，6，7，8
for（i=1;i<9;i++）{
ListInsert_Sq（L,i,i）;
e=L.elem[i-1];
printf（"第%d个元素为%d，此时L.elem=%dL.length=%dL.listsize=%d\n",i,e,L.elem,L.length,L.listsize）;
}
//求表长操作
printf（"顺序表L长为%d\n",ListLength_Sq（L））;
//删除操作
printf（"删除的第2个元素为%d\n",ListDelete_Sq（L,2,e））;
//销毁顺序表
DestroyList_Sq（L）;
printf（"销毁L后：
L.elem=%uL.length=%dL.listsize=%d\n",L.elem,L.length,L.listsize）;
}
升级会员 