数据结构 C语言 线性表 顺序表 实现

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

/*
C提供三种预处理。宏定义、文件包含、条件编译 。
宏 定 义:又称为宏代换、宏替换，简称“宏”。宏定义格式：#define 标识符 字符串
文件包含:#include<***.h>或者 #include“***.h(.c)”
条件编译:(#ifndef 和  #endif 成对出现)作用：避免两个字段中间的预处理重复处理。
*/

#ifndef STATUS_H
#define STATUS_H

#define    TRUE        1            //真
#define    FALSE        0            //假
#define YES            1            //是
#define NO          0            //否
#define    OK            1            //通过
#define    ERROR        0            //错误
#define SUCCESS        1            //成功
#define UNSUCCESS    0            //失败
#define    INFEASIBLE    -1            //不可行

#ifndef _MATH_H_                 //系统中已有此状态码定义，要避免冲突
#define    OVERFLOW    -2            //堆栈上溢
#define UNDERFLOW    -3            //堆栈下溢
#endif

/* 状态码识别类型 */
typedef int Status;

/* 宏函数(使用define进行多行定义时要加)*/
//函数暂停一段时间
#define Wait(x)
 {
    double _Loop_Num_;
    for(_Loop_Num_=0.01; _Loop_Num_<=100000.0*x; _Loop_Num_+=0.01);
 }//设立一个空循环

//摁Enter键继续
#define PressEnter
 {
    fflush(stdin);
    printf("Press Enter...");
    getchar();
    fflush(stdin);
 }//fflush清空标准输入流stdin

/*
getchar()函数等待输入,直到按回车才结束。回车前的所有输入字符都会逐个显示在屏幕
但只有第一个字符作为函数的返回值。利用getchar函数让程序调试运行结束后
等待编程者按下键盘才返回编辑界面。
*/

#endif

#define LIST_INIT_SIZE 100     //定义线性顺序表的容量置为100
#define LISTINCREMENT  10      //定义线性顺序表的递增量置为10
typedef int LElemType_Sq;      //定义线性顺序表类型的别名
typedef struct SqList          //定义线性顺序表的结构体并起名为SqList
{
    LElemType_Sq *elem;        //表的首地址
    int length;                //表的当前长度
    int listsize;              //表的容量
} SqList;

//顺序表相关操作列表------------------------------------------------------------
Status InitList_Sq(SqList *L)
{
    //创建一个线性顺序表-------------------------------------------------------1
    (*L).elem = (LElemType_Sq*)malloc(LIST_INIT_SIZE*sizeof(LElemType_Sq));
    if(!(*L).elem)    exit(OVERFLOW);
    (*L).length = 0;
    (*L).listsize = LIST_INIT_SIZE;
    return OK;
}

void ClearList_Sq(SqList *L)
{
    //清除线性顺序表内容-------------------------------------------------------2
    (*L).length = 0;
}

void DestroyList_Sq(SqList *L)
{
    //销毁线性顺序表-----------------------------------------------------------3
    free((*L).elem);
    (*L).elem = NULL;
    (*L).length = 0;
    (*L).listsize = 0;
}

Status ListEmpty_Sq(SqList L)
{
    //判断线性顺序表是否为空---------------------------------------------------4
    return     L.length==0 ? TRUE : FALSE;
}

int ListLength_Sq(SqList L)
{
    //返回该线性顺序表的长度---------------------------------------------------5
    return L.length;
}

Status GetElem_Sq(SqList L, int i, LElemType_Sq *e)
{
    //取得该线性顺序表确定位置的内容并赋予e------------------------------------6
    if(i<1 || i>L.length)
        return ERROR;
    else
        *e = L.elem[i-1];
    return OK;
}

int LocateElem_Sq(SqList L, LElemType_Sq e, Status(*Compare)(LElemType_Sq, LElemType_Sq))
{
    //在线性顺序表中找到与e等值的位置，并返回----------------------------------7
    int i = 1;
    while(i<=L.length && !Compare(e, L.elem[i-1]))
        ++i;
    if(i<=L.length)
        return i;
    else
        return 0;
}

Status PriorElem_Sq(SqList L, LElemType_Sq cur_e, LElemType_Sq *pre_e)
{
    //若cur_e不是线性顺序表的第一个并且在表中存在与之相同的内容----------------8
    int i = 1;
    if(L.elem[0]!=cur_e)
    {
        while(i<L.length && L.elem[i]!=cur_e)
            ++i;
        if(i<L.length)
        {
            *pre_e = L.elem[i-1];
            return OK;
        }
    }
    return ERROR;
}

Status NextElem_Sq(SqList L, LElemType_Sq cur_e, LElemType_Sq *next_e)
{
    //若cur_e不是线性顺序表的最后一个并且在表中存在与之相同的内容--------------9
    int i = 0;
    while(i<L.length && L.elem[i]!=cur_e)
        ++i;
    if(i<L.length-1)
    {
        *next_e = L.elem[i+1];
        return OK;
    }
    return ERROR;
}

Status ListInsert_Sq(SqList *L, int i, LElemType_Sq e)
{
    //在线性顺序表位序i的前面插入e元素----------------------------------------10
    LElemType_Sq *newbase;
    LElemType_Sq *p, *q;
    if(i<1 || i>(*L).length+1)
        return ERROR;
    if((*L).length >= (*L).listsize)
    {
        newbase = (LElemType_Sq*)realloc((*L).elem, ((*L).listsize+LISTINCREMENT)*sizeof(LElemType_Sq));
        if(!newbase)  exit(OVERFLOW);
        (*L).elem = newbase;
        (*L).listsize += LISTINCREMENT;
    }
    q = &(*L).elem[i-1];
    for(p=&(*L).elem[(*L).length-1]; p>=q; --p)
        *(p+1) = *p;
    *q = e;
    (*L).length++;
    return OK;
}

Status ListDelete_Sq(SqList *L, int i, LElemType_Sq *e)
{
    //删除线性顺序表位序为i的元素，并将之返回---------------------------------11
    LElemType_Sq *p, *q;
    if(i<1||i>(*L).length)return ERROR;
    p = &(*L).elem[i-1];
    *e = *p;
    q = (*L).elem+(*L).length-1;
    for(++p; p<=q; ++p)
        *(p-1) = *p;
    (*L).length--;
    return OK;
}

Status ListTraverse_Sq(SqList L, void(*Visit)(LElemType_Sq))
{
    //遍历输出整个线性顺序表--------------------------------------------------12
    int i;
    for(i=0; i<L.length; i++)
        Visit(L.elem[i]);
    return OK;
}

//函数指针----------------------------------------------------------------------
Status Compare(LElemType_Sq e, LElemType_Sq data)   //Compare指针函数的实现
{
    return data==e ? TRUE : FALSE;
}

void PrintElem(LElemType_Sq e)                      //visit指针函数的实现
{
    printf("%d ", e);
}

//求并集相关函数----------------------------------------------------------------
Union(SqList *La, SqList Lb)
{
    //合并两个非递减线性表成新的非递减排列线性(A=A∪B)------------------------13
    int La_len, Lb_len;
    int i;
    LElemType_Sq e;
    La_len = ListLength_Sq(*La);
    Lb_len = ListLength_Sq(Lb);
    for(i=1; i<=Lb_len; i++)
    {
        GetElem_Sq(Lb, i, &e);
        if(!LocateElem_Sq(*La, e, Compare))
            ListInsert_Sq(La, ++La_len, e);
    }
}

Status equal(SqList e1, SqList e2)
{
    //判断两个函数相等否------------------------------------------------------14
    if (e1.length != e2.length)
        return FALSE;
    else
    {
        int i;
        for (i=0 ; i<e1.length; i++)
        {
            if(e1.elem[i] != e2.elem[i])
            {
                return FALSE;
            }
        }
        if (i >= e1.length)
        {
            return TRUE;
        }
    }
}

//顺序表归并相关操作------------------------------------------------------------
void MergeSqList_1(SqList La, SqList Lb, SqList *Lc)
{
    //调用顺序表函数进行合并--------------------------------------------------15
    int La_len, Lb_len;
    int i, j, k;
    LElemType_Sq ai, bj;
    i = j = 1;
    k = 0;
    InitList_Sq(Lc);
    La_len = ListLength_Sq(La);
    Lb_len = ListLength_Sq(Lb);
    while(i<=La_len && j<=Lb_len)
    {
        GetElem_Sq(La, i, &ai);
        GetElem_Sq(Lb, j, &bj);
        if(ai<=bj)
        {
            ListInsert_Sq(Lc, ++k, ai);
            i++;
        }
        else
        {
            ListInsert_Sq(Lc, ++k, bj);
            j++;
        }
    }
    while(i<=La_len)
    {
        GetElem_Sq(La, i++, &ai);
        ListInsert_Sq(Lc, ++k, ai);
    }
    while(j<=Lb_len)
    {
        GetElem_Sq(Lb, j++, &bj);
        ListInsert_Sq(Lc, ++k, bj);
    }
}

void MergeSqList_2(SqList La, SqList Lb, SqList *Lc)
{
    //调用顺序表函数进行合并--------------------------------------------------16
    LElemType_Sq *pa, *pb, *pc;
    LElemType_Sq *pa_last, *pb_last;
    pa = La.elem;
    pb = Lb.elem;
    (*Lc).listsize = (*Lc).length = La.length + Lb.length;
    pc = (*Lc).elem = (LElemType_Sq *)malloc((*Lc).listsize*sizeof(LElemType_Sq));
    if(!pc)     exit(OVERFLOW);
    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++;
}

//主函数------------------------------------------------------------------------
int main()
{
    SqList L;
    int i;
    LElemType_Sq e;

    printf("▼1n▲函数 InitList_Sq 测试...n");        //1.函数InitList_Sq测试
    {
        printf("初始化顺序表 L ...n");
        InitList_Sq(&L);
        printf("n");
    }
    PressEnter;

    printf("▼4n▲函数 ListEmpty_Sq 测试...n");        //4.函数ListEmpty_Sq测试
    {
        ListEmpty_Sq(L) ? printf(" L 为空！！n") : printf(" L 不为空！n");
        printf("n");
    }
    PressEnter;

    printf("▼10n▲函数 ListInsert_Sq 测试...n");        //10.函数ListInsert_Sq测试
    {
        for(i=1; i<=6; i++)
        {
            printf("作为示范，在 L 第 %d 个位置插入 "%d"...n", i, 2*i);
            ListInsert_Sq(&L, i, 2*i);
        }
        printf("n");
    }
    PressEnter;

    printf("▼12n▲函数 ListTraverse_Sq 测试...n");    //12.函数ListTraverse_Sq测试
    {
        printf(" L 中的元素为：L = ");
        ListTraverse_Sq(L, PrintElem);
        printf("nn");
    }
    PressEnter;

    printf("▼5n▲函数 ListLength_Sq 测试...n");        //5.函数ListLength_Sq测试
    {
        i = ListLength_Sq(L);
        printf(" L 的长度为 %d n", i);
        printf("n");
    }
    PressEnter;

    printf("▼11n▲函数 ListDelete_Sq 测试...n");        //11.函数ListDelete_Sq测试
    {
        ListDelete_Sq(&L, 6, &e);
        printf("删除 L 中第 6 个元素 "%d" ...n", e);
        printf(" L 中的元素为：L = ");
        ListTraverse_Sq(L, PrintElem);
        printf("nn");
    }
    PressEnter;

    printf("▼6n▲函数 GetElem_Sq 测试...n");            //6.函数GetElem_Sq测试
    {
        GetElem_Sq(L, 4, &e);
        printf(" L 中第 4 个位置的元素为 "%d" n", e);
        printf("n");
    }
    PressEnter;

    printf("▼7n▲函数 LocateElem_Sq 测试...n");          //7.函数LocateElem_Sq测试
    {
        i = LocateElem_Sq(L, 7, Compare);
        printf(" L 中第一个元素值大于 "7" 的元素的位置为 %d n", i);
        printf("n");
    }
    PressEnter;

    printf("▼8n▲函数 PriorElem_Sq 测试...n");        //8.函数PriorElem_Sq测试
    {
        PriorElem_Sq(L, 6, &e);
        printf("元素 "6" 的前驱为 "%d" n", e);
        printf("n");
    }
    PressEnter;

    printf("▼9n▲函数 NextElem_Sq 测试...n");        //9.函数NextElem_Sq测试
    {
        NextElem_Sq(L, 6, &e);
        printf("元素 "6" 的后继为 "%d" n", e);
        printf("n");
    }
    PressEnter;

    printf("▼2n▲函数 ClearList_Sq 测试...n");        //2.函数ClearList_Sq测试
    {
        printf("清空 L 前：");
        ListEmpty_Sq(L) ? printf(" L 为空！！n") : printf(" L 不为空！n");
        ClearList_Sq(&L);
        printf("清空 L 后：");
        ListEmpty_Sq(L) ? printf(" L 为空！！n") : printf(" L 不为空！n");
        printf("n");
    }
    PressEnter;

    printf("▼3n▲函数 DestroyList_Sq 测试...n");        //3.函数DestroyList_Sq测试
    {
        printf("销毁 L 前：");
        L.elem ? printf(" L 存在！n") : printf(" L 不存在！！n");
        DestroyList_Sq(&L);
        printf("销毁 L 后：");
        L.elem ? printf(" L 存在！n") : printf(" L 不存在！！n");
        printf("n");
    }
    PressEnter;

    printf("▼13n▲函数 Union 测试...n");
    SqList La, Lb;
    LElemType_Sq a[] = {3, 5, 8, 11, 12};
    LElemType_Sq b[] = {2, 4, 6, 7, 9, 10, 13};
    InitList_Sq(&La);                   //创建线性顺序表La
    InitList_Sq(&Lb);                   //创建线性顺序表Lb
    for(i=1; i<=5; i++)
        ListInsert_Sq(&La, i, a[i-1]);  //初始化La
    for(i=1; i<=7; i++)
        ListInsert_Sq(&Lb, i, b[i-1]);  //初始化Lb
    printf("La = ");                    //输出La
    ListTraverse_Sq(La, PrintElem);
    printf("n");
    printf("Lb = ");                    //输出Lb
    ListTraverse_Sq(Lb, PrintElem);
    printf("nn");
    printf("La = La∪Lb = ");            //输出新表La的内容
    Union(&La,Lb);
    ListTraverse_Sq(La, PrintElem);
    printf("nn");
    PressEnter;

    printf("▼14n▲函数 equal 测试...n");
    equal(La,Lb)?printf("表La和Lb相等n"):printf("表La和Lb不相等n");
    equal(La,La)?printf("表La和La相等n"):printf("表La和La不相等n");
    PressEnter;

    printf("▼15n▲函数 MergeSqList_1 测试...n");
    SqList Lc1;
    InitList_Sq(&La);
    InitList_Sq(&La);                    //初始化La
    for(i=1; i<=5; i++)
        ListInsert_Sq(&La, i, a[i-1]);
    InitList_Sq(&Lb);                    //初始化Lb
    for(i=1; i<=7; i++)
        ListInsert_Sq(&Lb, i, b[i-1]);
    MergeSqList_1(La, Lb, &Lc1);        //合并A与B,算法2.6
    printf("合并La和Lb为Lc1 = ");         //输出Lc1
    ListTraverse_Sq(Lc1, PrintElem);
    printf("nn");
    PressEnter;

    printf("▼16n▲函数 MergeSqList_2 测试...n");
    SqList Lc2;
    InitList_Sq(&La);
    InitList_Sq(&La);                    //初始化La
    for(i=1; i<=5; i++)
        ListInsert_Sq(&La, i, a[i-1]);
    InitList_Sq(&Lb);                    //初始化Lb
    for(i=1; i<=7; i++)
        ListInsert_Sq(&Lb, i, b[i-1]);
    MergeSqList_2(La, Lb, &Lc2);        //合并A与B,算法2.6
    printf("合并La和Lb为Lc2 = ");         //输出Lc1
    ListTraverse_Sq(Lc2, PrintElem);
    printf("nn");
    PressEnter;

    return 0;
}

最后

以上就是独特冬日为你收集整理的数据结构 C语言 线性表 顺序表 实现的全部内容，希望文章能够帮你解决数据结构 C语言 线性表 顺序表 实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。