首页 > 代码库 > 顺序表的功能实现
顺序表的功能实现
顺序表的创建，插入，删除，清空，销毁，查找，输出功能
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#defineTRUE 1
#defineFALSE 0
#defineOK 1
#defineERROR 0
#defineINFEASIBLE -1
#defineOVERFLOW -2
typedefint Status ;
typedefint ElemType ;
//线性表的动态分配顺序存储结构
#defineLIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#defineLISTINTCREMENT 10 //线性表存储空间的分配增量
typedefstruct
{
ElemType *elem ; // 存储空间基址
int length ; //当前长度
int listsize ; //当前分配的存储容量
}SqList;
//初始化顺序表
StatusInitList_Sq(SqList &L)
{
L.elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType)) ;
if(!L.elem)
exit(OVERFLOW) ; //存储空间分配失败
L.length = 0 ; //空表长度为0
L.listsize = LIST_INIT_SIZE ; // 初始存储容量
return OK ;
}
voidCreateList(SqList&L) //创建顺序表
{
int i;
printf("请输入你要创建的顺序表元素个数");
scanf("%d",&L.length);
printf("请输入你要创建的顺序表:\n");
for(i = 0 ; i < L.length ; i++)
scanf("%d" , &L.elem[i]) ;
}
//查找
Statuslocation( SqList &L,ElemType e)//查找元素的位置
{
int i = 0 ;
while(L.elem[i]!=e &&i<L.length)
i++;
if(i>L.length) return -1;
else return i+1;//因为c语言是从下标0开始的当i=0时实际上是顺序表的第i+1个元素
}
//在顺序表中第i个位置插入一个新的元素e
StatusListInsert_Sq(SqList &L ,int i ,ElemType e)
{
ElemType *newbase,*q,*p;
if(i < 1 || i > L.length+1 )
return ERROR ; // i不合法
if(L.length >= L.listsize)
{
//当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem , (L.listsize+LISTINTCREMENT) * sizeof(ElemType)) ;
if(!newbase)
exit(OVERFLOW) ;// 分配地址失败
L.elem = newbase ; //新基址
L.listsize +=LISTINTCREMENT ; // 增加储存容量
}
q = &(L.elem[i-1]) ; //q为插入位置
for(p = &(L.elem[L.length - 1]) ; p>= q ; --p )
*(p+1) = *p ;//插入位后的元素右移
*q = e ; //插入e
++L.length ; //表长加1
return OK ;
}
//在顺序表中删除第i个元素，并用e返回其值
StatusListDelete_Sq(SqList &L , int i , ElemType &e)
{
ElemType *q,*p;
if(i < 1 || i > L.length+1 )
return ERROR ; // i不合法
p = &(L.elem[i-1]) ; //p为被删除元素的位置
e = *p ;//被删除元素的值赋给e
q = L.elem + L.length - 1 ;//表尾元素的位置
for(++p ; p <=q ; ++p)
*(p - 1) = *p ; //被删除的元素之后的元素左移
--L.length ; //表长减1
return OK ;
}
//判断表是否为空
StatusListEmpty(SqList &L)
{ //如果L为空表，返回TRUE，否则返回FALSE
if(L.length==0)
{
printf("此表为空表\n");
return TRUE ;
}
else return FALSE;
}
//将表置空
void ClearList(SqList &L)//将L重置为空表
{
for(int i = 0; i < L.length; i++)
{
L.elem[i] = NULL;
}
printf("表已经清空\n");
}
//销毁表
voidBurning_List(SqList &L)
{
L.length = 0;
// free(L) ;
printf("表已经销毁\n");
}
void print( SqList &L)//输出顺序表
{
int i ;
for(i = 0 ; i < L.length ; i++)
printf("%3d" , L.elem[i]);
printf("\n") ;
}
voidmain()
{
SqList la ;
int i , j ;
ElemType e ;
InitList_Sq(la) ;
CreateList(la) ;//创建表
//查找
printf("请输入要查找的元素:\n") ;
scanf("%d" , &e) ;
j=location(la , e) ;
printf("该元素的位置为%d\n" , j) ;
//插入
printf("请输入要插入的位置和元素:\n");
scanf("%d%d" , &i , &e) ;
ListInsert_Sq(la,i,e) ;
printf("输出插入后的顺序表:\n") ;
print(la) ;
//删除
printf("请输入要删除的位置:\n") ;
scanf("%d" , &i) ;
ListDelete_Sq(la,i,e) ;
printf("删除的那个元素是:%d\n" , e) ;
printf("输出删除后的顺序表:\n") ;
print(la) ;
//清空
ClearList(la) ;
print(la) ;
//销毁
Burning_List(la) ;
print(la) ;
}
顺序表的功能实现