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

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

一、顺序存储定义

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

二、顺序存储方式

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 ;   // 线性表长度减一
   }
}