线性表的顺序存储结构

线性表的顺序存储结构：

/*
** 线性表的顺序存储结构 */
#define SQLIST_INIT_SIZE 100 //顺序表存储空间初始分配量
#define SQLIST_INCREMENT 10  //存储空间分配增量
typedef struct tagSqList {
    ListElemType *data;//线性表存储数据基地址
             int  length;//线性表长度(当前元素个数)
             int  size;//为线性表分配的存储空间大小(以sizeof(ListElemType)为单位)
}SqList;

线性表的基本操作：

#include "sqlist_algo.h"
#include <stdlib.h>
#include <memory.h>

/*
** 构造一个空的线性顺序表，并将长度设置为0
*/
void SqList_Init(SqList *list)
{
    list->data = (ListElemType *)malloc(SQLIST_INIT_SIZE*sizeof(ListElemType));
    if (!list->data) exit(EXIT_FAILURE);//存储空间分配失败
    list->length = 0;//线性表长度(当前元素个数)设置为0
    list->size = SQLIST_INIT_SIZE;//为线性表分配的存储空间大小
}

/*
** 插入
*/
int SqList_Insert(SqList *list, int index, ListElemType elem)
{
    ListElemType *base, *pMove, *pInsert;
    if (index < 1 || index > list->length + 1) return 0;//参数出错
    if (list->length == list->size){//当前存储空间已满
        base = (ListElemType *)realloc(list->data, 
            (list->size + SQLIST_INCREMENT) * sizeof(ListElemType));
        if (!base) exit(EXIT_FAILURE);
        list->data = base;//将新申请的内存空间首地址赋给data
        list->size += SQLIST_INCREMENT;//增加存储空间容量
    }
    pInsert = list->data + index - 1;//pInsert为插入位置，数组下标
    for (pMove = list->data + list->length - 1; pMove >= pInsert; --pMove){
        *(pMove+1) = *pMove;//插入位置及之后的元素依次后移(从表尾开始)
    }
    *pInsert = elem;//插入元素
    ++list->length;//表长加1
    return 1;
}

/*
** 判断是否为空
*/
int SqList_Empty(SqList list)
{
    if (list.length == 0) return 1;
    return 0;
}

/*
** 获取表长
*/
int SqList_Length(SqList list)
{
    return list.length;
}

/*
** 遍历线性表
*/
void SqList_Traverse(SqList list, void (*visit)(ListElemType))
{
    ListElemType *p = list.data;//p指向第一个元素
    int i;
    for (i = 1; i <= list.length; i++){
        visit(*p++);
    }
}

/*
** 删除
*/
int SqList_Delete(SqList *list, int index, ListElemType *elem)
{
    ListElemType *pDel, *pTail;
    if (index < 1 || index > list->length) return 0;//参数非法
    pDel = list->data + index - 1;//pDel指向待删除元素位置
    *elem = *pDel;//被删除元素值赋给elem
    pTail = list->data + list->length - 1;//pTail指向表尾元素位置
    for (++pDel; pDel <= pTail; ++pDel){
        *(pDel - 1) = *pDel;//被删除元素以后的元素依次向前移动一位
    }
    list->length--;//表长减1
    return 1;
}

/*
** 定位，返回与elem满足compare()关系的元素的位置
*/
int SqList_Locate(SqList list, ListElemType elem, int (*compare)(ListElemType, ListElemType))
{
    int i = 1;//初始值为第一个元素的位序
    ListElemType *p = list.data;//p指向第一个元素位置
    while (i <= list.length && !compare(elem, *p++)){
        ++i;//没找到满足条件的就继续找
    }
    if (i <= list.length) return i;//找到
    return 0;//没有找到
}

/*
** 清空
*/
void SqList_Clear(SqList *list)
{
    list->length = 0;
}

/*
** 销毁
*/
void SqList_Destroy(SqList *list)
{
    free(list->data);
    list->data = NULL;
    list->length = 0;
    list->size = 0;
}

测试代码如下：

#include <stdio.h>
#include "sqlist_algo.h"

void visit(ListElemType e)
{
    printf(" %d ", e);
}

int compare(ListElemType e1, ListElemType e2)
{
    if (e1 == e2) return 1;
    return 0;
}

//For Test
int main(int argc, char **argv)
{
    SqList List;
    ListElemType e;
    int i = 0, index;
    
    //初始化空表
    SqList_Init(&List);

    //插入元素
    scanf("%d", &e);
    while (e > 0){
        SqList_Insert(&List, ++i, e);
        scanf("%d", &e);
    }
    //判断是否为空
    printf("Empty : %d
", SqList_Empty(List));
    //获取表长
    printf("Length : %d
", SqList_Length(List));
    //遍历
    SqList_Traverse(List, visit);
    //删除
    printf("
Del Index: ");
    scanf("%d", &index);
    if (SqList_Delete(&List, index, &e)){
        printf("Delete %d-th Element %d
", index, e);
    }
    SqList_Traverse(List, visit);
    //定位
    printf("
Locate : ");
    scanf("%d", &e);
    printf("Result: %d
", SqList_Locate(List, e, compare));

    return 0;
}