线性表的顺序表示和c实现

威斯布鲁特

通过这次的练习，虽然自己的自控力一般，容易被游戏，动漫吸引，但我发现数据结构和算法的学习是一个长期的过程。为了完成这次的练习，我复习了函数指针与指针函数的区别，也学习了插入排序算法。

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

//------线性表的动态分配顺序存储结构------
#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int elemType;  //考虑到可扩展性，定义数据元素类型
typedef int Status;
typedef struct {
    elemType * elem;  //存储空间基址
    int length;  //当前长度
    int listsize;  //当前分配的存储容量（以sizeof(elemType)为单位）
}SqList;

Status InitList_Sq(SqList * L);
void InsertLast(SqList * L, elemType e);
Status ListInsert_Sq(SqList * L, int i, elemType);
Status ListDelete_Sq(SqList * L, int i, elemType *e);
Status AgainMalloc(SqList * L);
void TraverseList(SqList * L);
int LocateElem_Sq(SqList L, elemType e,
                  Status (* compare)(elemType, elemType));
Status compare(elemType a, elemType b);
void InsertSort(SqList L);
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc);

int main()
{
    int i;
    int tmp;
    SqList list1;
    InitList_Sq(&list1);

    //向线性表插入元素
   printf("尾插法插入e，输入e(输q退出):");
    while(scanf("%d",&tmp))
    {
        InsertLast(&list1, tmp);
        printf("头插法插入e，输入e(输q退出):");
    }
    printf("插入元素后的list1:");
    TraverseList(&list1);

    getchar();
    //在顺序表中第i个位置之前插入新的元素e
    printf("输入i(输q退出)：");
    while(scanf("%d", &i))
    {
        printf("输入元素e：");
        scanf("%d", &tmp);
        ListInsert_Sq(&list1, i, tmp);
        printf("输入i(输q退出)：");
    }
    printf("插入元素后的list1:");
    TraverseList(&list1);

    getchar(); //为了缓冲
    printf("删除一个元素\n");
    printf("输入i：");
    scanf("%d", &i);
    ListDelete_Sq(&list1, i, &tmp);
    printf("删除一个元素后的线性表list1=");
    TraverseList(&list1);
    printf("删除的元素e: %d\n", tmp);


    SqList list2;
    InitList_Sq(&list2);

     //向线性表插入元素
   printf("尾插法插入e，输入e(输q退出):");
    while(scanf("%d",&tmp))
    {
        InsertLast(&list2, tmp);
        printf("头插法插入e，输入e(输q退出):");
    }
    printf("插入元素后的list2:");
    TraverseList(&list2);

    printf("排序线性表:\n");
    InsertSort(list1);
    printf("排序后的线性表list1:");
    TraverseList(&list1);

    InsertSort(list2);
    printf("排序后的线性表list2:");
    TraverseList(&list2);

    SqList list3;
    InitList_Sq(&list3);
    MergeList_Sq(list1, list2, &list3);
    printf("list1和list2的合集list3=");
    TraverseList(&list3);
}

// 构造一个空的线性表L。
Status InitList_Sq(SqList * L)
{
    L->elem = (elemType * )malloc(LIST_INIT_SIZE*sizeof(elemType));
    if(!L->elem) exit(OVERFLOW);
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

//向表尾插入元素
void InsertLast(SqList * L, elemType e)
{
    if(L->length >= L->listsize)
        AgainMalloc(L);
    L->elem[L->length] = e;
    L->length++;
    return;
}

// 在顺序线性表L中第i个位置之前插入新的元素e,
// i的合法值为1=<i<=ListLength_Sq(L)+1
Status ListInsert_Sq(SqList * L, int i, elemType e)
{
    elemType * q, * p;
    if(i<1 || i>L->length+1) return ERROR;
    if(L->length >= L->listsize) //当前存储空间已满,增加分配
    AgainMalloc(L);

    q = &(L->elem[i-1]); //q为插入位置
    for(p=&(L->elem[L->length-1]); p>=q; --p) *(p+1) = *p;
                                    //插入位置及之后的元素右移
    *q = e;
    ++L->length;
    return OK;
}

Status AgainMalloc(SqList * L) //空间不够时重新分配空间的函数
{
    elemType * newbase; //分配一个临时基址
    newbase = (elemType *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(elemType));
    if(!newbase) exit(OVERFLOW);
    L->elem = newbase; //新基址
    L->listsize += LISTINCREMENT;
    return OK;
}

void TraverseList(SqList * L)
{
    int i;
    for(i=0; i<L->length; i++)
        printf("%d ", L->elem[i]);
    printf("\n");
    return;
}

Status ListDelete_Sq(SqList * L, int i, elemType * e)
{
    //在顺序表L中删除第i个元素，并用e返回其值
    //i的合法值为1=<i<=ListLength_Sq(L)
    if((i<1) || (i>L->length)) return ERROR; //i值不合法

    *e = L->elem[i-1]; //被删除元素的值赋给e

    for(; i<L->length; i++)
    {
        L->elem[i-1] = L->elem[i];
    }
    L->length--;

    return OK;
}

int LocateElem_Sq(SqList L, elemType e,
                  Status (* compare)(elemType, elemType))
{
    //在顺序表L中查找第1个值与e满足compare()的元素的位符
    //若找到，则返回其在L中的位序，否则返回0
    int i = 1;
    elemType * p = L.elem;
    while(i<=L.length && !compare(*(p++), e)) ++i; //(*compare)
    if(i<=L.length) return i;
    else return 0;
}

Status compare(elemType a, elemType b)
{
    if(a==b) return OK;
    else return ERROR;
}

void InsertSort(SqList L)
{
    //递增排序线性表
    for(int i=1; i<L.length; i++){
        if(L.elem[i] < L.elem[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            int j= i-1;
            int x = L.elem[i];        //复制为哨兵，即存储待排序元素
            L.elem[i] = L.elem[i-1];           //先后移一个元素
            while(j > -1 && x < L.elem[j]){  //查找在有序表的插入位置
                L.elem[j+1] = L.elem[j];
                j--;         //元素后移
            }
            L.elem[j+1] = x;      //插入到正确位置
        }
    }

}

void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
{
//已知顺序线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
elemType * pa, * pb, *pc;
pa = La.elem; pb = Lb.elem;
Lc->listsize = Lc->length = La.length+Lb.length;
pc = Lc->elem = (elemType *)malloc(Lc->listsize*sizeof(elemType)); //可以两次调用malloc
if(!Lc->elem) exit(OVERFLOW);  //存储分配失败
elemType * pa_last, * pb_last;
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while(pa<=pa_last && pb<=pb_last)
{
    if(*pa <= *pb) *(pc++) = *(pa++);
    else *(pc++) = *(pb++);
}
while(pa<=pa_last) *(pc++) = *(pa++);
while(pb<=pb_last) *(pc++) = *(pb++);
}

参考资料：
排序算法
函数指针和指针函数