数据结构---线性表的顺序表示和实现

数据结构---线性表的顺序表示和实现
16年2月26日19:24:49
线性表的顺序表示，它的优点是容易实现随机存取线性表的第i个元素，但是在插入，删除的操作时，需要移动大量的元素，所以它适用于相对稳定的线性表，如职工工资表，学生学籍表等。以下是我写的源程序：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct SqList {
    int *elem; //动态分配内存的首地址
    int length; //当前线性表的长度
    int listsize; //当前分配的存储空间的容量
}SqList, *pSqList;

/* 初始化函数，主要是对SqList中的三个元素进行赋值初始化。 */
/**
 * Initialise the list.
 * @param L [the list]
 */
void InitList(SqList *L)
{
    L->elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem)
    {
        printf("Cannot malloc memory for L->elem.\n");
        exit(-1);
    }

    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
}

/**
 * Destroy the list.
 * @param L [this list]
 */
void DestroyList(SqList *L)
{
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

/**
 * return the length of the list.
 * @param  L [the list]
 * @return [description]
 */
int ListLength(SqList L)
{
    return L.length;
}

/**
 * This function is test the list empty or not.
 * @param L: the list.
 * @return : is empty, return 1; else return 0.
 */
int IsListEmpty(SqList L)
{
    return L.length ? 0 : 1;
}

/* 在这个线性表中的某个位置插入某个元素，首先注意的是pos的值是否有效，另外，如果随着线性表中元素个数的增加，它的个数可能超过刚开始预定义的 LIST_INIT_SIZE，那样的话，就需要从新分配 LISTINCREMENT增量的内存，从新把分配内存的首地址赋给 L->elem。如果在pos的位置插入元素，pos位置之后的所有元素均需要移动一个位置。 */
/**
 * Insert one value the the list
 * @param  L [the list]
 * @param  pos [the position of this list]
 * @param  val [the value]
 * @return [if success return 1]
 */
int InsertList(SqList *L, int pos, int val)
{
    int *newbase, *p, *q;

    if (pos < 1 || pos > L->length + 1)
    {
        printf("Error position.\n");
        exit(-1);
    }

    if (L->length >= L->listsize)
    {
        newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }

    p = L->elem + pos - 1;
    q = L->elem + L->length - 1;
    for (q; q >= p; q--)
    {
        *(q + 1) = *q;
    }

    *p = val;
    L->length += 1;

    return 1;
}

/* 遍历这个线性表。 */
/**
 * Traverse the list.
 * @param L [the list]
 */
void TraverseList(SqList L)
{
    int i;

    printf("The values of this list are:\n");
    for (i = 0; i < L.length; i++)
    {
        printf("%d ", *(L.elem + i));
    }

    printf("\n");
}

/* 删除某个元素的操作，比如删除pos位置的元素，所有pos位置之后的元素都要向前移动一个位置。*/
/**
 * Delete one entry of this list.
 * @param  L [this list]
 * @param  pos [position in this list]
 * @param  val [the value of the deleted one]
 * @return [if success, return 1]
 */
int DeleteList(SqList *L, int pos, int *val)
{
    int *p, *q;

    if (pos < 1 || pos > L->length + 1)
    {
        printf("Error position.\n");
        exit(-1);
    }

    p = L->elem + pos - 1;
    q = L->elem + L->length - 1;

    *val = *p;
    for (p; p <= q; p++)
    {
        *p = *(p + 1);
    }

    L->length -= 1;

    return 1;
}

int main(int argc, char const *argv[])
{
    SqList L;
    int val;

    InitList(&L);
    printf("After Initialise : L.elem = %p, L.length = %d, L.listsize = %d.\n", L.elem, L.length, L.listsize);
    if (IsListEmpty(L))
    {
        printf("The list is empty.\n");
    }
    InsertList(&L, 1, 1);
    InsertList(&L, 1, 2);
    InsertList(&L, 1, 3);
    InsertList(&L, 1, 4);
    InsertList(&L, 1, 5);
    InsertList(&L, 1, 6);
    InsertList(&L, 1, 7);
    InsertList(&L, 1, 8);
    TraverseList(L);
    if (IsListEmpty(L))
    {
        printf("The list is empty.\n");
    }
    DeleteList(&L, 1, &val);
    printf("The delete value is %d.\n", val);
    DeleteList(&L, 5, &val);
    printf("The delete value is %d.\n", val);
    TraverseList(L);
    DeleteList(&L, 12, &val);
    return 0;
}

程序运行结果是：
After Initialise : L.elem = 0xa00b008, L.length = 0, L.listsize = 100.
The list is empty.
The values of this list are:
8 7 6 5 4 3 2 1
The delete value is 8.
The delete value is 3.
The values of this list are:
7 6 5 4 2 1
Error position.