严蔚敏版《数据结构》第二章线性表的算法C语言实现

前端之家收集整理的这篇文章主要介绍了严蔚敏版《数据结构》第二章线性表的算法C语言实现前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

首先,今天是中秋,明天是国庆,在这说声节日快乐啊。

说点题外话,今天出去走了走,看到药店就进去称体重了。尼玛,竟然轻了4斤,本来就是100刚出头,现在倒好,直接掉下100了。我想这可能是因为最近天天熬夜,而且最近学校还规定天天要去早读(直接导致睡眠不足),直到过了英语4级。唉,大一时不能考,不知今年12月能否考过啊。所以说各位还要注意休息啊,记得要早点休息。昨天晚上就11点后就因为写这个代码直到一点才睡的。可能因为当时头脑有点晕,也许代码会有点乱或者瑕疵说着遗漏什么的,作为新人的我欢迎各位指出来哦。

看到书上的伪代码,就有把它搞成C语言的冲动。也许是还不成熟吧,别人都是直接看伪代码的,还有人会写出伪代码,可我还没达到这种境界。所以只有用C语言实现它了。

其实在写之前也看了别人写的一些之类的,所以我的算是山寨吧,哈哈,不过和书上的伪代码也差不多了。

好了,不再多说什么了,下面就是代码了,有点长。

code:

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 4

typedef int Status;
typedef int ElemType;


typedef struct
{
    ElemType *elem;                     //存储机制
    int length;                         //当前线性表的长度
    int listsize;                       //当前分配的存储容量
}sqlist;


Status InitList_Sq(sqlist *L);          //初始化建立线性表

void DestroyList_Sq(sqlist *L);         //销毁线性表

void ClearList_Sq(sqlist *L);           //置空线性表

Status Listempty_Sq(sqlist *L);         //判断线性表是否为空

Status ListLength_Sq(sqlist *L);         //获取线性表的长度(元素个数)

/*获取线性表第i个个位置的值*/
Status Getlem(sqlist *L,int i,ElemType *e);

/*求线性表的前继元素*/
Status PriorElem(sqlist *L,ElemType cur_e,ElemType *pre_e);

/*求线性表的后继元素*/
Status NextElem(sqlist *L,ElemType *next_e);

/*在第i个位置插入元素e*/
Status ListInsert_Sq(sqlist *L,ElemType e);

/*删除线性表的第i个元素*/
Status ListDelete_Sq(sqlist *L,ElemType *e);

/*遍历输出顺序表中所有元素*/
Status ListTransver_Sq(sqlist *L);

/*对顺序表中元素进行排序*/
void ListSort_Sq(sqlist *L);

/*倒置顺序表中所有元素*/
void ListInvert_Sq(sqlist *L);


/*初始化线性表*/
Status InitList_Sq(sqlist *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(L->elem == NULL)
    {
        printf("内存分配失败!\n");
        return OVERFLOW;
    }
    L->length = 0;      //线性表(空表)的长度为0
    L->listsize =  LIST_INIT_SIZE;      //表的初始存储容量为LIST_INIT_SIZE
    return OK;
}


/*销毁线性表*/
void DestroyList_Sq(sqlist *L)
{
    if(L->elem != NULL)
    {
        L->elem = NULL;     //释放线性表内存空间
        L->length = 0;
        L->listsize = 0;
    }
}


/*置空线性表*/
void ClearList_Sq(sqlist *L)
{
    L->length = 0;
}


/*判断线性表是否为空*/
Status Listempty_Sq(sqlist *L)
{
    if(L->length == 0)
        return TRUE;
    else
        return FALSE;
}


/*获取线性表的长度*/
Status ListLength_Sq(sqlist *L)
{
    return L->length;
}


/*获取线性表的第i个元素的值*/
Status Getlem(sqlist *L,ElemType *e)
{
    if(i < 1 || i > L->length)
    {
        printf("没有第%d个元素!\n",i);
        return ERROR;
    }
    if(L->elem == NULL)
    {
        printf("该线性表为空!\n");
        return ERROR;
    }
    *e = L->elem[i-1];
    return OK;
}


/*求线性表的前继元素*/
Status PriorElem(sqlist *L,ElemType *pre_e)
{
    int i = 2;              //从第二个元素开始
    while(i <= L->length)
    {
        if(L->elem[i-1] == cur_e)
        {
            *pre_e = L->elem[i-2];
            return OK;
        }
        i++;
    }
    return ERROR;
}


/*求线性表中的后继元素*/
Status NextElem(sqlist *L,ElemType *next_e)
{
    int i = 1;
    while(i < L->length - 1)
    {
        if(L->elem[i-1] == cur_e)       //之所以不是i,是因为防止第一个元素没有后继
        {
            *next_e = L->elem[i];
            return OK;
        }
        i++;
    }
    return ERROR;
}


/*在线性表的第i个位置插入元素e*/
Status ListInsert_Sq(sqlist *L,ElemType e)
{
    if(i < 1 ||i > L->length+1)
        return ERROR;
    if(L->length >= L->listsize)
    {
        ElemType *newbase = (ElemType *)realloc(L->elem,sizeof(ElemType)*(L->listsize+LISTINCREMENT));
        if(!newbase)
            return OVERFLOW;        //存储分配失败
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }
    ElemType *q = &(L->elem[i-1]);     //q为插入位置
    ElemType *p;                    //是p指向最后一个元素
    for(p = &(L->elem[L->length - 1]); p >=q; p--)
        *(p+1) = *p;
    *q = e;                         //插入e
    L->length ++;
    return OK;
}


/*删除线性表的第i个元素*/
Status ListDelete_Sq(sqlist *L,ElemType *e)
{
    if(i < 1 || i > L->length)
    {
        printf("需要删除的位置不存在!\n");
        return ERROR;
    }
    ElemType *p = &(L->elem[i-1]);      //p为被删除元素的位置
    *e = *p;                             //被删除的元素的值赋给e
    ElemType *q = L->elem + L->length - 1;  //表尾元素的位置
    for(p = p+1; p <= q; p++)
        *(p-1) = *p;                    //被删除元素之后的元素左移
    L->length --;
    return OK;
}


/*遍历输出顺序表中所有元素*/
Status ListTransver_Sq(sqlist *L)
{
    int i;
    if(L->length == 0)
    {
        printf("\t该表为空!\n\n");
        return ERROR;
    }
    else
    {
        printf("\t该线性表为:");
        for(i = 1; i <= L->length ; i++)     //刚才忘记了=,导致使出有问题
            printf("%d ",L->elem[i-1]);
        printf("\n\n");
    }
    return OK;
}


/*对顺序表中元素进行排序*/
void ListSort_Sq(sqlist *L)
{
    int i,j,tmp,max;
    for(i = 0; i < L->length - 1; i++)
    {
        max = i;
        for(j = i; j < L->length; j++)
        {
            if(L->elem[max] < L->elem[j])
                max = j;
        }
        tmp = L->elem[i];
        L->elem[i] = L->elem[max];
        L->elem[max] = tmp;
    }
}       /*选择排序法*/


/*倒置顺序表中所有元素*/
void ListInvert_Sq(sqlist *L)
{
    int i = 0,j = L->length,tmp;
    while(i < j)
    {
        tmp = L->elem[i];
        L->elem[i] = L->elem[j];
        L->elem[j] = tmp;
        i ++;
        j --;
    }
}


int main()
{
    sqlist L;
    ElemType e;
    int i;


    /*初始化列表*/
    if(InitList_Sq(&L) == NULL)
        printf("\t初始化列表失败!\n\n");
    else
        printf("\t初始化列表成功!\n\n");


    /*判断该线性表是否为空*/
    printf("\t列表是否为空?\n");
    if(Listempty_Sq(&L) == NULL)
        printf("\t该线性表是为空!\n\n");
    else
        printf("\t该线性表不为空!\n\n");


    /*该线性表的长度*/
    printf("\t该线性表的长度:%d\n\n",ListLength_Sq(&L));


    /*向线性表中插入元素*/
    for(i = 1; i <= 8; i++)
        ListInsert_Sq(&L,i,i+1);
    ListTransver_Sq(&L);
    printf("\t该线性表的长度:%d\n\n",ListLength_Sq(&L));


    /*查找数的前驱*/
    printf("\t将要查找元素的前驱!\n");
    printf("\t输入要查找的值: ");
    scanf("%d",&i);
    if(PriorElem(&L,&e) == 1)
        printf("\t存在前驱,且前驱为:%d\n\n",e);
    else
        printf("\t不存在前驱元素!\n\n");


    /*查找数的后继*/
    printf("\t将要查找元素的后继!\n");
    printf("\t输入要查找的值: ");
    scanf("%d",&i);
    if(NextElem(&L,&e) == 1)
        printf("\t存在后继,且后继为:%d\n\n",e);
    else
        printf("\t不存在后继元素!\n\n");


    /*删除线性表中的第i个元素*/
    printf("\t删除元素!\n");
    printf("\t删除前:");
    ListTransver_Sq(&L);
    printf("\t输入要删除的第几个元素:");
    scanf("%d",&i);
    ListDelete_Sq(&L,&e);
    printf("\t删除后:");
    ListTransver_Sq(&L);


    /*元素排序*/
    printf("\t排序前:");
    ListTransver_Sq(&L);
    printf("\t排序后:");
    ListSort_Sq(&L);
    ListTransver_Sq(&L);


    /*导致线性表的元素*/
    printf("\t倒置前:");
    ListTransver_Sq(&L);
    printf("\t倒置后:");
    ListInvert_Sq(&L);
    ListTransver_Sq(&L);
    return 0;
}

运行结果:

原文链接:https://www.f2er.com/datastructure/383232.html

猜你在找的数据结构相关文章