数据结构之线性表(顺序表）

1.1 线性表的定义

   线性表（List）：零个或多个数据元素的有限序列。

  在数据元素的非空有限集中，线性结构的特点：

 （1）存在唯一的一个被称为“第一个”的数据元素；

 （2）存在唯一的一个称为“最后一个”的数据元素；

 （3）除第一个之外，集合中的每个数据元素均只有一个前驱；

 （4）除最后一个之外，集合中的每个数据元素只有一个后继；

  优点：可以随机访问元素

  缺点：对于插入和删除元素，需要大量的位置移动

1.2 线性表的顺序表示

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

   来看线性表的动态分配的存储结构。    

typedef ElemType int; //假设为int

#define LIST_INIT_SIZE 100 //线性表存储空间初始分配值
#define LISTINCREMENT 10 //线性表存储空间分配增量

typedef struct
{
    ElemType *elem; //存储基地址
    int listsize; //当前线性表存储空间分配大小
    int length; //当前线性表大小
}SqList;

1.3 线性表顺序结构代码实现

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

//宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 100         //线性表存储空间的初始分配量
#define LISTINCREMENT 10           //线性表存储空间的分配增量

typedef int ElemType;

typedef struct LNode
{
    ElemType *elem;                //存储空间基地址
    int length;                    //线性表当前长度
    int listsize;                  //线性表存储空间实际分配大小
}SqList;


/* 函数名称：InitList
 * 函数功能：构造空的线性表
 * 返回值：
 *        ERROR：malloc() error
 *        OK   : 构造成功
*/
int InitList(SqList *L, int length)
{
    if( 0 == length )
    {
        length = LIST_INIT_SIZE;                    //默认分配LIST_INIT_SIZE
    }
    L->elem = (ElemType *)malloc(sizeof(length));
    if(NULL == L->elem)                             //空间分配失败
    {
        fprintf(stderr, "malloc() error.\n");
        return ERROR;
    }
    L->listsize = length;
    L->length = 0;

    return OK;
}

/* 函数名称：InsertList
 * 函数功能：在线性表的第i个位置插入元素e.(第i个位置，即为线性表中第i-1个元素)
 * 返回值：
 *        ERROR：i不合法或realloc失败
 *        OK   ：插入成功
*/
int InsertList(SqList *L, ElemType e, int i)
{
    if(i < 0 || i > L->length + 1)         //i不合法
    {
        return ERROR;
    }

    if(L->length >= L->listsize)            //空间不足
    {
        ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newbase)
        {
            return ERROR;                   //realloc error
        }
        L->elem = newbase;
        L->listsize = L->listsize + LISTINCREMENT;
    }

    ElemType *q = &(L->elem[i]);
    ElemType *p = NULL;
    for(p = &(L->elem[L->length - 1]); p >= q; --p)
    {
        *(p + 1) = *p;
    }
    *q = e;

    L->length++;

    return OK;
}

/* 函数名称：DeleteList
 * 函数功能：删除线性表第i个元素，并将其保存到e中返回
 * 返回值：
 *        ERROR：i不合法
 *        OK   ：删除成功
*/
int DeleteList(SqList *L, int i, ElemType *e)
{
    if(i < 0 || i > L->length)            //i不合法
    {
        fprintf(stderr, "i不合法\n");
        return ERROR;
    }

    ElemType *q = &(L->elem[i]);
    *e = *q;                              //获得第i个元素的值

    ElemType *p = L->elem + L->length - 1;

    for( ; q < p; q++)                    //循环左移
    {
        *q = *(q + 1);
    }

    L->length--;                          //当前长度减1

    return OK;
}


//快速排序
int partition(SqList *L, ElemType low, ElemType high)
{
    ElemType key = L->elem[low];

    while(low < high)                                //
    {
        while(low < high && L->elem[high] >= key)    //
        {
            high--;
        }
        L->elem[low] = L->elem[high];                //
        L->elem[high] = key;

        while(low < high && L->elem[low] <= key)    //
        {
            low++;
        }
        L->elem[high] = L->elem[low];                //
        L->elem[low] = key;
    }

    return low;
}

void quickSort(SqList *L, ElemType low, ElemType high)
{
    ElemType key;
    if(low < high)
    {
        key = partition(L, low, high);
        quickSort(L, low, key - 1);
        quickSort(L, key + 1, high);
    }
}

/* 函数名称：MergeList
 * 函数功能：将线性表La和线性表Lb合并到Lc中，并不删除元素
*/
int MergeList(SqList La, SqList Lb, SqList *Lc)
{
    //线性表La和Lb中的元素均不递减，合并后的Lc也不递减

    ElemType *pa, *pb, *pc;
    Lc->listsize = La.length + Lb.length;

    InitList(Lc, Lc->listsize);

    Lc->length = Lc->listsize;

    pa = La.elem;
    pb = Lb.elem;
    pc = Lc->elem;

    while(pa <= &(La.elem[La.length - 1]) && pb <= &(Lb.elem[Lb.length - 1]))
    {
        if(*pa <= *pb)
        {
            *pc++ = *pa++;
        }
        else
        {
            *pc++ = *pb++;
        }
    }
    while(pa <= &(La.elem[La.length - 1]))
    {
        *pc++ = *pa++;
    }
    while(pb <= &(Lb.elem[Lb.length - 1]))
    {
        *pc++ = *pb++;
    }

    return OK;
}

//打印线性表中元素
void printList(SqList L)
{
    int i = 0;
    for(i = 0; i < L.length; i++)
    {
        printf("%d ",L.elem[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    SqList La, Lb, Lc;
    ElemType e;
    int ret;

    ret = InitList(&La, LIST_INIT_SIZE);
    if(ret == ERROR)
    {
        fprintf(stderr, "InitList() error.\n");
        exit(EXIT_FAILURE);
    }

    int data[6] = {6, 5, 8, 3, 9, 4};
    int i = 0;
    for(i = 0; i < 6; i++)
    {
         ret = InsertList(&La, data[i], i);
         if(ret != OK)
         {
                 fprintf(stderr, "插入元素失败.\n");
                 exit(EXIT_FAILURE);
         }
    }

    printf("初始化后的La:\n");
    printList(La);

    ret = DeleteList(&La, 3, &e);
    if(ret != OK)
    {
        fprintf(stderr, "删除元素失败.\n");
        exit(EXIT_FAILURE);
    }
    printf("删除第3个元素后的La:\n");
    printList(La);

    ret = InsertList(&La, e, 3);
    if(ret != OK)
    {
        fprintf(stderr, "插入元素失败.\n");
        exit(EXIT_FAILURE);
    }
    printf("插入e后的La:\n");
    printList(La);

    //快速排序
    quickSort(&La, 0, La.length - 1);
    printf("排序后的La:\n");
    printList(La);

    printf("\n");
    InitList(&Lb, LIST_INIT_SIZE);

    int bdata[5] = {1, 3, 2, 4, 6};
    for(i = 0; i < 5; i++)
    {
        InsertList(&Lb, bdata[i], i);
    }
    printf("初始化后的Lb:\n");
    printList(Lb);

    //快速排序
    quickSort(&Lb, 0, Lb.length - 1);
    printf("排序后的Lb:\n");
    printList(Lb);

    MergeList(La, Lb, &Lc);
    printf("La与Lb合并后的Lc:\n");
    printList(Lc);

    return 0;
}

 

       

    参考：严蔚敏老师之《数据结构》

                       

                                                        梦醒潇湘love

                                                       2013-01-06 22:06