严蔚敏版《数据结构》第二章线性表的算法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

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

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test