顺序表的定义及基本操作

╰半夏微凉° 2022-08-10 00:56 141阅读 0赞

# 建立顺序表，完成顺序表的基本操作：初始化、插入、删除、输出（遍历） #

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    #define TURE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    #define LIST_INIT_SIZE  100
    #define LISTINCREMENT    10
    typedef int Status;
    typedef int ElemType;
    typedef struct
    {
    	ElemType *elem;
    	int length;
    	int listsize;
    }SqList;
    Status InitList_Sq(SqList &L)
    {
    	//构造一个空的线性表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;
    }//InitList_Sq
    Status ListInsert_Sq(SqList &L,int i,ElemType e)
    {
    	//在顺序线性表中第i个位置插入新的元素e
    	//i的合法值为1<=i<=Listlength.Sq(L)+1
    	ElemType *newbase;
    	ElemType *p;
    	ElemType *q;
    	if(i<1||i>L.length+1)
    		return ERROR;//i不合法
    	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;//增加存储容量
    	}
    	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;
    }//ListInsert_Sq
    Status ListDelete_Sq(SqList &L,int i,ElemType &e)
    {
    	//在顺序线性表L中删除第i个元素，并用e返回其值
        ElemType *p;
    	ElemType *q;
    	if((i<1)||(i>L.length))
    		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;//表长减一
    	return OK;
    }//Lis tDelete_Sq
    void ListShow_Sq(SqList &L)
    {
    	int i;
    	for(i=0;i<L.length;i++)
    	{
    		printf("%5d",L.elem[i]);//输出顺序表
    	}
    	printf("\n");
    }
    int main()
    {
    	int n,a,b,c;
    	SqList Lst;
    	InitList_Sq(Lst);
    	ListInsert_Sq(Lst,1,2);
    	ListInsert_Sq(Lst,2,3);
        ListInsert_Sq(Lst,3,5);
        ListInsert_Sq(Lst,4,8);
        ListInsert_Sq(Lst,5,9);
        printf("创建一个顺序表：\n");
    	ListShow_Sq(Lst);
    	printf("\n请选择要插入新元素的位置：\n");
    	scanf("%d",&a);
    	printf("\n请输入要插入的元素数值：\n");
    	scanf("%d",&c);
    	if(ListInsert_Sq(Lst,a,c)==OK)
    	{
    		printf("合法插入新元素的顺序表为：");
    	ListShow_Sq(Lst);
    	}
    	else
    	{
    		printf("\n插入新元素位置不合法，失败\n");
    	}
    	printf("\n请选择要删除元素的位置：");
    	scanf("%d",&b);
    	if(ListDelete_Sq(Lst,b,n)==OK)
    	{
    		printf("删除后的顺序表为：\n");
    		ListShow_Sq(Lst);
    		printf("删除的元素数值为：%d\n",n);
    	}
    	else
    	{
    		printf("\n删除位置不合法，失败\n");
    	}
    	return 0;
    }