顺序存储线性表实现

淡淡的烟草味﹌ 2022-05-08 02:42 324阅读 0赞

在计算机中用一组地址连续的[存储单元][Link 1]依次存储线性表的各个[数据元素][Link 2],称作线性表的顺序存储结构。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的[随机存取][Link 3]，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

给出两种基本实现：

/*
    静态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INITSIZE 100
    #define ElemType int
    #define Status int
    #define OK     1
    #define ERROR  0
    
    typedef struct
    {
    	ElemType elem[LIST_INITSIZE];
    	int length;
    }SqList;
    
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负)，也可以根据需求改
    //虽然思想略简单，但是要写的没有错误，还是需要锻炼coding能力的
    
    Status InitList(SqList *L)
    {
        L->length = 0;//长度为0
        return OK;
    }
    
    Status ListInsert(SqList *L, int i,ElemType e)
    {
        int j;
        if(i<1 || i>L->length+1)
            return ERROR;//判断非法输入
        if(L->length == LIST_INITSIZE)//判满
        {
            printf("表已满");//提示
            return ERROR;//返回失败
        }
        for(j = L->length;j > i-1;j--)//从后往前覆盖，注意i是从1开始
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        (L->length)++;//表长加1
        return OK;//反回成功
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i = 0;i < L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DisCreat(SqList A,SqList *B,SqList *C)
    {
        int i;
        for(i = 0;i < A.length;i++)//依次遍历A中元素
        {
            if(A.elem[i]<0)//判断
                ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
            else
                ListInsert(C,C->length+1,A.elem[i]);
        }
    }
    
    int main(void)
    {
        //复制的
    	SqList L;
    	SqList B, C;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
    	InitList(&L);
    	InitList(&B);
    	InitList(&C);
    	for (i = 1; i <= 9; i++)
    		ListInsert(&L,i,data[i-1]);
        printf("插入完成后L = : ");
    	ListPrint(L);
        ListDelete(&L,1,&e);
    	printf("删除第1个后L = : ");
    	ListPrint(L);
        DisCreat(L , &B, &C);
    	printf("拆分L后B = : ");
    	ListPrint(B);
    	printf("拆分L后C = : ");
    	ListPrint(C);
    	printf("拆分L后L = : ");
    	ListPrint(L);
    }

静态：长度固定

动态：不够存放可以加空间（搬家）

/*
    子任务名任务:1_2 动态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define Status int
    #define OVERFLOW -1
    #define OK 1
    #define ERROR 0
    #define ElemType int
    
    typedef struct
    {
    	ElemType * elem;
    	int length;
    	int listsize;
    }SqList;
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DeleteMin(SqList *L);//删除最小
    
    Status InitList(SqList *L)
    {
        L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
    	if(!L->elem)//申请失败
    		return ERROR;
    	L->length = 0;//长度0
    	L->listsize = LIST_INIT_SIZE;//容量100
    	return OK;//申请成功
    }
    
    Status ListInsert(SqList *L,int i,ElemType e)
    {
        int j;
        ElemType *newbase;
        if(i<1 || i>L->length+1)
            return ERROR;//非法输入
            
        if(L->length >= L->listsize)//存满了，需要更大空间
        {
            newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
            if(!newbase)//申请失败
                return ERROR;
            L->elem = newbase;//调指针
            L->listsize+= LISTINCREMENT;//新容量
        }
        
        for(j=L->length;j>i-1;j--)//从后往前覆盖
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        L->length++;//长度+1
        return OK;
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i=0;i<L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DeleteMin(SqList *L)
    {
        //表空在Listdelete函数里判断
        int i;
        int j=0;//最小值下标
        ElemType *e;
        for(i=0;i<L->length;i++)//寻找最小
        {
            if(L->elem[i] < L->elem[j])
                j=i;
        }
        ListDelete(L,j+1,&e);//调用删除，注意j要+1
    }
    
    int main(void)
    {
    	SqList L;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
    	InitList(&L);
    	for (i = 1; i <= 9; i++)
    	{
    		ListInsert(&L,i,data[i-1]);
    	}
    	printf("插入完成后 L = : ");
    	ListPrint(L);
        ListDelete(&L, 2, &e);
    	printf("删除第 2 个后L = : ");
    	ListPrint(L);
        DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    }

[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[Link 3]: https://baike.baidu.com/item/%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96