数据结构——线性表的顺序存储结构(C/C++语言描述）

短命女 2021-09-23 00:50 399阅读 0赞

最近复习数据结构，在读数据结构的经典作《大话数据结构》(程杰），以下是近期对于线性表的顺序存储结构的整理，后期尽量持续更新。

一、顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

二、顺序存储方式

1. 顺序存储的结构代码为：

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 20         /* 存储空间初始分配量 */
    #define INCREACEMENT 10       /* 存储空间分配增量 */
    typedef int ElemType;      /* ElemType 类型根据实际情况而定，这里指定为int */
    typedef int Status;        /* Status 类型根据实际情况而定，这里指定为int */
    #define OK 1
    #define ERROR 0
    typedef struct
    {
          ElemType *elem;  // 存储空间基地址，此处为int型，视情况而定 
          int length;  // 元素表当前长度 
          int size;  //当亲分配的存储容量 
    }SqList;

2. 顺序表的初始化操作(**分配一个预定大小的数组空间，并将顺序表的长度设为0)**：

Status InitList(SqList &L){
    	L.elem = (ElemType *)malloc(MAXSIZE*sizeof(int));
    	if(!L.elem){
    		return;
    	}
    	L.length = 0;
    	L.size = MAXSIZE;
    	return OK;
    } 
    
    Status CreatList(SqList &L){
    	L.elem = (ElemType *)malloc(MAXSIZE*sizeof(int));
    	if(!L.elem){
    		return ERROR;
    	}
    	L.length = 0;
    	L.size = MAXSIZE;
    	printf("请输入表的长度:");
        scanf("%d",&L.length);
        printf("请输入%d个数:",L.length);
        for(int i=0;i<L.length;i++)
        scanf("%d",&L.elem[i]);
    }

3. 获取元素操作(将线性表的第i个位置的元素返回）：

Status GetElem(SqList &L, int i, int &e){
    	if(i < 1 || i > L.length){
    		return ERROR;
    	}
    	e = L.elem [i-1];
    	return OK;
    }

4. 插入操作：

Status InsertList(SqList &L,int i, int e){
        int *p = NULL;
        int *q = NULL;
        if (i > L.length  + 1 || i < 1) return ERROR;   // 先判断要插入的序号在不在线性表长度之内
        if(L.length >= L.size )  { // 如果线性表的长度大于等于分配的大小时，需重新分配线性表大小
            int * newbase = (int *)realloc(L.elem, (L.length + INCREACEMENT)*sizeof(int));
            if (!newbase) return ERROR;
            L.elem = newbase;    // 基地址改变
            L.size += INCREACEMENT;  // 分配的大小加倍
        }
        q = &(L.elem [i-1]);   // 要插入的位序
        for (p = &(L.elem [L.length-1]);p>=q;p--) { //循环实现要插入位置以后的数都要后移一位
            *(p+1) = *p;
        }
        *q=e;  //给要插入的位序赋值要插入的值
        L.length +=1;  //线性表加1
    }

5. 删除操作：

Status DelectList(SqList &L, int i, int &e) {
        int *p,*q;
        if (i < 1 || i > L.length ) return ERROR;  // 先判断要删除的位序的值是否在线性表中
        else {        
           p = &L.elem[i-1];   // 要删除的位序
           e = *p;    // 将删除的数赋值给e
           q = L.elem + L.length - 1;   // 线性表最后的位序
           for (++p; p <= q; ++p) {
               *(p-1) = *p;  // 循环实现删除位序后的数据前移一位
           }
           --L.length ;   // 线性表长度减一
       }
    }