静态顺序表的c实现

威斯布鲁特

终于，自己从头到尾敲了一遍顺序表。虽然是静态顺序表，但还是挺满意的。在敲代码过程中，我对指针和结构体的了解更加深入了，还接触到了<merroy.h>,<assert.h>库函数。有时间，实现线性表有集合属性。

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

#define MAXSIZE 50
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

//定义顺序表的静态数组表示
typedef  struct{
ElemType data[MAXSIZE];
int length;
}SqList,*pSqList;



void Init_Sq(pSqList pSq);
void InsertFirst(pSqList pSq, ElemType);
void InsertLast(pSqList pSq, ElemType);
void TraverseList(pSqList pSq);
int ListLength(pSqList pSq);
Status ListInsert(pSqList pSq, int i, ElemType e);
Status ListDelete(pSqList pSq, int i, ElemType * e);
int LocateElem_Sq(pSqList pSq, ElemType e);
void GetElem(pSqList pSq, int i, ElemType * e);
void Union_Sq(pSqList La, SqList Lb);

int main()
{
    SqList list1;
    Init_Sq(&list1);

    int length1;
    scanf("%d",&length1);
    int i;
    ElemType e;

    for(i=0;i<length1;i++)
    {
        scanf("%d",&e);
        InsertLast(&list1, e);
    }

    printf("创建好的线性表list1=");
    TraverseList(&list1);

    printf("像表头插入一个元素:");
    scanf("%d",&e);
    InsertFirst(&list1, e);

    printf("插入一个头元素的list1=");
    TraverseList(&list1);

    printf("在线性表第i个位置前插入e，输入i(输q退出):");
    while(scanf("%d", &i))
    {
        printf("输入元素e:");
        scanf("%d", &e);
        ListInsert(&list1, i, e);
        printf("在线性表第i个位置前插入e，输入i(输q退出):");
    }
    printf("插入元素后的list1:");
    TraverseList(&list1);

    getchar();
    printf("在顺序表中删除list1中删除第i个元素，输入i(输q退出):");
    while(scanf("%d", &i))
    {
        int e;
        ListDelete(&list1, i, &e);
        printf("删除的元素是:%d\n", e);
       printf("在顺序表中删除list1中删除第i个元素，输入i(输q退出):");
    }
    printf("删除元素后的list1:");
    TraverseList(&list1);

    getchar();
    printf("\n");
    SqList list2;
    Init_Sq(&list2);

    int length2;
    scanf("%d", &length2);
    for(i=0;i<length2;i++)
    {
        scanf("%d",&e);
        InsertLast(&list2, e);
    }
    printf("创建好的线性表list2=");
    TraverseList(&list2);

    Union_Sq(&list1, list2);
    printf("list1 U list1 =");
    TraverseList(&list1);

    return 0;
}

//初始化顺序表
void Init_Sq(pSqList pSq)
{
    assert(pSq);  //判断是否开辟结构体空间

//把线性表的每个元素初始化为0

//方法1
//  memset(pSq->data, 0, sizeof(ElemType)*MaxSize);

//方法2
//    for(i=0; i<sizeof(pSq->data)/sizeof(*pSq->data); i++)
//    {
//        pSq->data[i] = 0;
//    }
    pSq->length = 0;
}

//遍历顺序表
void TraverseList(pSqList pSq)
{
    int i;

    for(i=0; i<pSq->length; i++)
    {
        printf("%d", pSq->data[i]);
    }
    putchar('\n');
    return;
}

//求表中元素个数
int ListLength(pSqList pSq)
{
    return pSq->length;
}

//向表头插入一个元素
void InsertFirst(pSqList pSq, ElemType e)
{
    int * p, * q;

    if(pSq->length>=MAXSIZE)
    {
        exit(OVERFLOW);
    }

    q = &pSq->data[0];
    for(p=&pSq->data[pSq->length-1];p>=q;p--) //不能用于首次插入
    {
        *(p + 1) = *p;
    }
    *q = e;
    pSq->length++;
    return;
}

//向表尾插入一个元素
void InsertLast(pSqList pSq, ElemType e)
{
     if(pSq->length>=MAXSIZE)
    {
        exit(OVERFLOW);
    }
    pSq->data[pSq->length] = e;
    pSq->length++;
    return;
}

//在顺序表第i个位置之前插入新的元素e
Status ListInsert(pSqList pSq, int i, ElemType e)
{
    int * q, * p;
    if(i<1 || i>pSq->length+1) return ERROR;
    if(pSq->length>=MAXSIZE)
    {
        exit(OVERFLOW);
    }
    q = &(pSq->data[i-1]);

    for(p=&(pSq->data[pSq->length-1]);p>=q;p--)
        * (p+1) = * p;

    * q = e;
    ++pSq->length;
    return OK;
}

//删除第i个元素，并返回其值
Status ListDelete(pSqList pSq, int i, ElemType * e)
{
    int * p, *q;
    if((i<1) || (i>pSq->length)) return ERROR;
    p = &(pSq->data[i-1]);
    *e = *p;
    q = pSq->data + pSq->length-1;
    for(++p; p<=q; ++p) *(p-1) = *p;
    --pSq->length;
    return OK;
}

//定位一个指定的值在线性表中的具体位置
//若找到，则返回其在顺序表中的位序
int LocateElem_Sq(pSqList pSq, ElemType e)
{
    ElemType * p;
    int i = 1;
    p = pSq->data;

    while(i<=pSq->length&&!(*p++==e)) i++;

    if(i<=pSq->length) return i;
    else return 0;
}

void GetElem(pSqList pSq, int i, ElemType* e)
{
    *e = pSq->data[i-1];
}

//求线性表La与线性表Lb的并集，
//即将所有在线性表Lb中但不在线性表La中的元素插入到La中
void Union_Sq(pSqList La, SqList Lb)
{
    int Lb_len;
    Lb_len = ListLength(&Lb);

    int i;
    for(i=1; i<=Lb_len;i++){
        int e;
        GetElem(&Lb, i, &e);
        if(!LocateElem_Sq(La, e)){
            InsertLast(La, e);
        }
    }
}

小甲鱼

不错，再接再厉！

威斯布鲁特

小甲鱼 发表于 2017-7-23 22:58
不错，再接再厉！

蟹蟹大佬鼓舞。