顺序表的基本运算的实现？

刺骨的言语ヽ痛彻心扉 2022-05-12 07:40 172阅读 0赞

1.线性表的顺序存储又称为顺序表

2.顺序表必须占用一整块事先分配大小的固定的存储空间（一组地址连续的存储单元），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，所以进行插入或删除操作时，平均需要移动半个表的元素，这是相当费时的操作，不便于存储空间的管理。

下面我们来具体介绍顺训表具体运算的实现：

#include<stdio.h>
    #include<malloc.h>
    #define MaxSize 20//为顺序表分配具体的存储空间
    
    typedef char Elemtype;
    
    typedef struct
    {
        Elemtype data[MaxSize];
        int length;
    }sqlist;

//下面我们先来声明要用到的一些基本函数以及这些函数在Main()函数内的调用

//函数的声明
    void InitList(sqlist *&L);
    void CreateList(sqlist *&L,Elemtype a[],int n);
    bool ListInsert(sqlist *&L,int i,Elemtype e);
    void DispList(sqlist *L);
    bool ListEmpty(sqlist *L);
    int ListLength(sqlist *L);
    bool GetElem(sqlist *L,int i,Elemtype &e);
    int LocateElem(sqlist *L,Elemtype e);
    bool ListDelete(sqlist *&L,int i,Elemtype &e);
    void DestroyList(sqlist *&L);
    bool ListDeletes_t(sqlist *&L,ElemType s,Elemtype t);
    //基本函数在主函数中的调用
    int main()
    {
    	sqlist *L;
    	ElemType e;
    	ElemType a[5]={'a','b','c','d','e'};
    
    	//初始化顺序表
    	InitList(L);
    	//建立数据表
    	CreateList(L,a,5);
    	//输出顺序表
    	DispList(L);
    	//输出顺序表的长度
    	printf("%d\n",ListLength(L));
    	//判断该顺序表是否为空
    	if(ListEmpty(L)==false) printf("该顺序表不为空\n");
    	else printf("该顺序表为空\n");
    	//对某个元素进行输出
    	if(GetElem(L,3,e)==1) printf("%c\n",e);
    	else printf("该元素不存在\n");
    	printf("%d\n",LocateElem(L,'a'));
    	//插入数据
    	ListInsert(L,4,'f');   DispList(L);
    	ListInsert(L,4,'g');   DispList(L);
    	ListDelete(L,3,e);     DispList(L);
    	 
    	
    	ListDeletes_t(L,'d','f');
    	DispList(L);
    		printf("%d\n",ListLength(L));
    	DestroyList(L);
    	return 0;
    }

--------------------

//初始化顺序表

void InitList(sqlist *&L)
    {
        L=(sqlist *)malloc(sizeof(sqlist));
        L->length=0;
    
    }

//建立顺序表

void CreateList(sqlist *&L,Elemtype a[],int n)
    {
        int i;
        L=(sqlist *)malloc(sizeof(sqlist));
        for(i=0;i<n;i++)
            L->data[i]=a[i];
        L->length=n;
    
    }

//插入数据元素

bool ListInsert(sqlist *&L,int i,Elemtype e)
    {
        int j;
        //对i进行判断，即对要插入的元素进行判断是否在该顺序表规定的范围内
        if(i<1||i>L->length+1)
            return false;
        if(L->length>=MaxSize)
        {
            printf("线性表溢出！");
            return false;
        }
        for(j=L->length;j>=i;j--)
            L->data[j]=L->data[j-1];
        L->data[i-1]=e;
        L->length++;
        return true;
    
    }

//删除L中的某个元素

bool listDelete(sqlist *&L,int i,Elemtype &e)
    {
        int j;
        if(L->length==0)
        {
            printf("线性表L为空！\n");
            return false;
        }
        else if(i<1||i>L->length)
        {
            printf("要删除的数据元素不存在！\n");
            return false;
        }
        else
        {
        e=L->data[i-1];
        for(j=i;j<L->length;j++)
            L->data[j-1]=L->data[j];
        
        L->length--;
        return true;
        }
    
    }

//判断顺序表是否为空

bool EmptyList(sqlist *L)
    {
        return (L->length==0);
    
    }

//输出顺序表的长度

int ListLength(sqlist *L)
    {
        return (L->length);
    }

//输出顺序表

void DispList(sqlist *L)
    {
        int i;
        for(i=0;i<L->length;i++)
            printf("%c",L->data[i]);
        printf("\n");
    }

//输出顺序表中的某个元素值

bool GetElem(sqlist *&L,int i,Elemtype &e)
    {
        if(i<1||i>L->length)
            return false;
        e=L->data[i-1];
        return true;
    
    }

//输出某个元素值所在顺序表中的位置

int LocataElem(sqlist *L,ELemtype e)
    {
        int i=0;
        while(i<L->length&&L->data[i]!=e)
            i++;
        if(i>=L->length)
            return 0;
        else
            return i+1;
    
    }

//删除元素值介于s和t之间的元素

bool ListDeletes_t(sqlist *&L,Elemtype s,Elemtype t)
    {
    	if(s>=t||L->length==0)
    		return false;
    	int k=0;
    	for(int i=0;i<L->length;i++)
    		if(L->data[i]<s||L->data[i]>t)
    		{
    			L->data[k]=L->data[i];
    		    k++;
    		}
    		L->length=k;
    		return true;
    }