【数据结构】线性表

【1】定义

线性表是信息表的一种形式，表中数据元素之间满足线性关系（或线性结构），
    是一种最基本、最简单的数据结构类型。

【2】线性表的特征：

1) 对非空表,a0是表头,无前驱；
    2) an-1是表尾,无后继；
    3) 其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。

【3】线性表的顺序存储（顺序表）的实现

#include <stdio.h>
#include <stdlib.h>
#define MAX 64
typedef int datatype_t;
struct sqlist
{
    datatype_t data[MAX];
    int last;
};

struct sqlist *sqlist_creat()
{
    struct sqlist* sl;
    sl=(struct sqlist*)malloc(sizeof(struct sqlist));
    sl->last=-1;
    return sl;
}

int sqlist_empty(struct sqlist* sl)
{
    if(sl->last==-1)
        return 1;
    return 0;
}

int sqlist_full(struct sqlist* sl)
{
    if(sl->last==MAX-1)
        return 1;
    return 0;
}


datatype_t sqlist_delete_by_pos(struct sqlist* sl,int pos)
{
    if(sqlist_empty(sl)||pos<0||pos>sl->last)
    {
        printf("wrong posn");
        return -1;
    }
    int i=pos;
    datatype_t d=sl->data[pos];
    while(i<sl->last)
    {
        sl->data[i]=sl->data[i+1];
        i++;
    }
    sl->last--;
    return d;
}

void sqlist_delete_by_data(struct sqlist* sl,datatype_t d)
{
    int cnt=0;
    int i;
    for(i=0;i<=sl->last;i++)
    {
        if(sl->data[i]==d)
            cnt++;
        sl->data[i]=sl->data[i+cnt];
    }
    sl->last-=cnt;
}


void sqlist_insert(struct sqlist* sl,datatype_t d)
{
    if(sqlist_full(sl)==1)
    {
        printf("fulln");
        return;
    }
    sl->last++;
    sl->data[sl->last]=d;
}


void sqlist_insert_by_pos(struct sqlist *sl,int pos,datatype_t d)
{
    if(pos>sl->last+1)
    {
        printf("wrong positionn");
        return;
    }
    sl->last++;
    int i=sl->last;
    while(i!=pos)
    {
        sl->data[i]=sl->data[i-1];
        i--;
    }
    sl->data[i]=d;
}

datatype_t sqlist_delete(struct sqlist* sl)
{
    datatype_t d=sl->data[sl->last];
    sl->last--;
    return d;
}

int sqlist_search_by_data(struct sqlist* sl,datatype_t d)
{
    int i;
    for(i=0;i<=sl->last;i++)
    {
        if(sl->data[i]==d)
            return i;
    }
    return -1;
}
datatype_t sqlist_search_by_pos(struct sqlist* sl,int pos)
{
    if(pos>sl->last)
    {
        printf("wrong positionn");
        return -1;
    }
    return sl->data[pos];
}

void sqlist_modify_by_data(struct sqlist* sl,datatype_t pre,datatype_t new)
{
    int i;
    for(i=0;i<=sl->last;i++)
    {
        if(sl->data[i]==pre)
            sl->data[i]=new;
    }
}

void sqlist_modify_by_pos(struct sqlist* sl,datatype_t new,int pos)
{
    if(pos>sl->last)
    {
        printf("wrong positionn");
        return;
    }
    sl->data[pos]=new;
}

void sqlist_show(struct sqlist* sl)
{
    int i;
    for(i=0;i<=sl->last;i++)
        printf("%d ",sl->data[i]);
    putchar(10);
}





void sqlist_union(struct sqlist* s1,struct sqlist* s2)
{
    int flag;
    int i;
    datatype_t tmp;
    for(i=0;i<=s2->last;i++)
    {
        tmp=sqlist_search_by_pos(s2,i);
        flag=sqlist_search_by_data(s1,tmp);
        if(flag==-1)
            sqlist_insert(s1,tmp);
    }
}

int main()
{
    struct sqlist* s1,*s2;
    s1=sqlist_creat();
    s2=sqlist_creat();
    sqlist_insert(s1,1);
    sqlist_insert(s1,2);
    sqlist_insert(s1,3);
    sqlist_insert(s1,4);
    sqlist_insert(s1,5);
    sqlist_insert(s2,6);
    sqlist_insert(s2,7);
    sqlist_insert(s2,2);
    sqlist_insert(s2,9);
    sqlist_insert(s2,10);

    sqlist_union(s1,s2);
    sqlist_show(s1);
    free(s1);
    free(s2);

    return 0;
}