欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构:顺序表的ADT(C语言描述)

程序员文章站 2024-03-20 14:25:16
...

数据结构:顺序表ADT

顺序表的实现:

#define MAXSIZE 1024			//顺序表可能的最大长度,假设为1024 
typedef int elemtype;			//其中的int型可以更改为任意类型 
typedef struct sequlist 
{	
elemtype data[MAXSIZE];		//定义顺序表为一维数组 	
int last;			//last为表中最后一个数据元素的下标位置 
}
SequenList;				//顺序表的结构类型

1. 顺序表的初始化:

SequenList * Init_SequenList()
{
SequenList * L;	//定义顺序表指针变量
L=(SequenList*)malloc(sizeof(SequenList));		//申请分配内存空间
if(L!=NULL)	//申请分配内存空间成功
{
L->last=-1;	 		//设置顺序表的长度last为-1,表示顺序表是空表
}
return L;	//返回顺序表的首地址
 } 

2. 求顺序表的长度:

int SequenList_Length(SequenList *L)
{
return(L->last+1);	//返回顺序表的长度
}

3. 插入运算:

int Insert_SequenList(SequenList * L,elemtype x,int i)
/*在顺序表中指定的位置插入值为x的结点
L是SequenList类型的指针变量
x是带插入结点的数据元素值
i是在顺序表中的插入位置*/
{
int j;
if(L->last>=MAXSIZE-1)	 	//检查顺序表是否已满
{
return 0; //顺序表满插入失败,函数返回0
}
if(i<1||i>L->last+2)	 	//插入位置有效性检查
{
return -1;	//位置非法,则插入失败,函数返回-1
}
for(j=L->last;j>=i-1;j--)	 	//在第i个位置插入新结点x
L->data[j+1]=L->data[j];		//结点依次向后移动一个位置
L->data[i-1]=x;	//插入x到第i个位置
L->last=L->last+1;	//将顺序表长度加一
return 1; //插入成功,函数返回1
 } 

4. 删除

int Delete_SequenList(SequenList * L,int i)	//删除第i个位置的结点
{
int j;	//检查指定位置的有效性
if(i<1||i>L->last+1)	 	//位置非法删除失败,函数返回0
{
return 0;
}
else
{
for(j=i;j<=L->last;j++)
L->data[j-1]=L->data[j];	//结点前移
L->last--;	 	//表长减1
}
return 1;	//删除成功,函数返回1
}

5. 取数据元素

elemtype GetData_SequenList(SequenList * L,int i)	//顺序表取结点算法
{
if(i<1||i>L->last+1)	//位置有效性检查
{
return 0;	//位置无效,函数返回0
}
else
return(L->data[i-1]);	//返回所需结点的值
 } 

6. 查找

int Search_SequenList(SequenList * L;elemtype key)	//顺序表查找算法
{
int i;
for(i=0;i<=L->last;i++)	//表中元素依次与key进行比较
if(L->data[i]==key)	//找到与key相等的元素
return(i+1);	//返回其在顺序表中的位置
return 0;	//查找失败,返回0
}

7. 遍历

int Print_SequenList(SequenList *L)	//顺序表遍历算法
{
int i;
if(L->last==-1)	//顺序表为空,返回值为0
{
return 0;
}
for(i=0;i<=L->last;i++)
{
printf("a[%2d]=%4d\t",i+1,L->data[i]);	//输出表中元素
if((i+1)%5==0)
printf("\n");	//控制每行输出的元素个数
}
retuen 1;
 }