文档章节

C语言 数据结构与算法 线性表

起什么name呢
 起什么name呢
发布于 2016/03/23 16:56
字数 918
阅读 59
收藏 0

数据结构中逻辑结构分线性和非线性。

线性表即为线性结构中的一种。

线性表的特性 百度百科解释在此

个人总结为 有始有终,顺序排列,首尾不相连(像火车一样)。

线性表的基本操作如下:

初始化,销毁,重置为空表,判断是否为空,查找表的长度,

查找元素的位置,根据位置查找元素,查找元素的上一个元素,查找元素的下一个元素,

插入元素,删除元素,遍历元素。

下面是顺序存储结构的C实现。(有时间可以尝试下链式存储结构的实现)

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INIT_SIZE 10        //初始化表长度
#define INCREMENT_SIZE 5    //增量

typedef int Status;
typedef int Elemtype;

/*
 * 数据存贮结构
 */
typedef struct
{
    Elemtype *elem;    //存储空间基址
    int length;        //当前长度
    int size;        //当前分配的表长大小
}SqList;

/*
 * 初始化线性表
 */
Status InitList(SqList *L)
{
    L->elem = (Elemtype *) malloc(INIT_SIZE * sizeof(Elemtype));
    if (!L->elem)
    {
        return ERROR;
    }
    L->length = 0;
    L->size = INIT_SIZE;
    return OK;
}

/*
 * 销毁
 */
Status DestroyList(SqList *L)
{
    free(L->elem);
    L->length = 0;
    L->size = 0;
    return OK;
}

/*
 * 清空
 */
Status ClearList(SqList *L)
{
    L->length = 0;
    return OK;
}

/*
 * 是否为空
 */
Status isEmpty(const SqList L)
{
    if (0 == L.length)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

/*
 * 获取表长
 */
Status getLength(const SqList L)
{
    return L.length;
}

/*
 * 获取指定位置的元素
 */
Status GetElem(const SqList L, int i, Elemtype *e)
{
    if (i < 1 || i > L.length)
    {
        return ERROR;
    }
    *e = L.elem[i-1];
    return OK;
}

/*
 * 比较元素大小
 */
Status compare(Elemtype e1, Elemtype e2)
{
    if (e1 == e2)
    {
        return 0;
    }
    else if (e1 < e2)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

/*
 * 查找元素的位置
 */
Status FindElem(const SqList L, Elemtype e, Status (*compare)(Elemtype, Elemtype))
{
    int i;
    for (i = 0; i < L.length; i++)
    {
        if (!(*compare)(L.elem[i], e))
        {
            return i + 1;
        }
    }
    if (i >= L.length)
    {
        return ERROR;
    }
}

/*
 * 查找当前元素的前一个元素
 */
Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e)
{
    int i;
    for (i = 0; i < L.length; i++)
    {
        if (cur_e == L.elem[i])
        {
            if (i != 0)
            {
                *pre_e = L.elem[i - 1];
            }
            else
            {
                return ERROR;
            }
        }
    }
    if (i >= L.length)
    {
        return ERROR;
    }
}

/*
 * 查找当前元素的下一个元素
 */
Status NextElem(const SqList L, Elemtype cur_e, Elemtype *next_e)
{
    int i;
    for (i = 0; i < L.length; i++)
    {
        if (cur_e == L.elem[i])
        {
            if (i < L.length - 1)
            {
                *next_e = L.elem[i + 1];
                return OK;
            }
            else
            {
                return ERROR;
            }
        }
    }
    if (i >= L.length)
    {
        return ERROR;
    }
}

/*
 * 插入元素
 */
Status InsertElem(SqList *L, int i, Elemtype e)
{
    Elemtype *new;
    if (i < 1 || i > L->length + 1)
    {
        return ERROR;
    }
    if (L->length >= L->size)
    {
        new = (Elemtype*) realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype));
        if (!new)
        {
            return ERROR;
        }
        L->elem = new;
        L->size += INCREMENT_SIZE;
    }
    Elemtype *p = &L->elem[i - 1];
    Elemtype *q = &L->elem[L->length - 1];
    for (; q >= p; q--)
    {
        *(q + 1) = *q;
    }
    *p = e;
    ++L->length;
    return OK;
}

/*
 * 删除元素
 */
Status DeleteElem(SqList *L, int i, Elemtype *e)
{
    if (i < 1 || i > L->length)
    {
        return ERROR;
    }
    Elemtype *p = &L->elem[i - 1];
    *e = *p;
    for (; p < &L->elem[L->length]; p++)
    {
        *(p) = *(p + 1);
    }
    --L->length;
    return OK;
}

/*
 * 访问元素
 */
void visit(Elemtype e)
{
    printf("%d ", e);
}

/*
 * 遍历表
 */
Status TraverseList(const SqList L, void (*visit)(Elemtype))
{
    int i;
    for(i = 0; i < L.length; i++)
    {
        visit(L.elem[i]);
    }
    return OK;
}

//测试
int main()
{
    SqList L;
    if (InitList(&L))
    {
        Elemtype e;
        printf("init_success\n");
        int i;
        for (i=0; i<10; i++)
        {
             InsertElem(&L, i+1, i);
        }
        printf("length is %d\n", getLength(L));
        if (GetElem(L, 1, &e)) {
        printf("This first element is %d\n", e);
        }
        else
        {
            printf("element id not exist\n");
        }
        printf("The 5 at %d\n", FindElem(L, 5, *compare));
        PreElem(L, 6, &e);
        printf("The 6's previoud element is %d\n",e);
        NextElem(L, 6, &e);
     printf("The 6's next element is %d\n", e);
        DeleteElem(&L, 1, &e);
        printf("delete first element is %d\n",e);
        TraverseList(L, visit);
    if (DestroyList(&L))
    {
        printf("\ndestory_success");
    }
    }
}

  看了几遍 终于通了,对新手来说其中比较难理解的地方就是插入元素 那个操作里的 位移操作 举例如下

list 里原本有 1 2  3 4 5  当需要插入 6 到 第二个位置 需要把 2 3 4 5 都往后移动 但是在上面的代码里移动的是元素地址 从最后一个开始 从高位往地位移动 所以比较难理解。

© 著作权归作者所有

起什么name呢
粉丝 1
博文 40
码字总数 12807
作品 0
朝阳
高级程序员
私信 提问
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
11.7K
0
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/04/01
0
0
Android OpenGL开发目录

Android OpenGL开发目录 Android OpenGL开发1--VS2017+OpenGL环境的配置 to be continued... 其它目录 Android NDK开发之旅 目录 Android NDK开发之旅1--NDK介绍 Android NDK开发之旅2--C语言...

香沙小熊
2018/01/07
0
0
C语言 数据结构与算法 单向链表

单向链表 线性表的一种(可以理解为线性表的链式链式表示和实现) 逻辑位置相邻 物理位置不相邻 与线性表相比劣势:不能随机存取 与线性表相比优势:插入和删除较快 链式存贮结构一般由一个个...

起什么name呢
2016/03/24
26
0
《大话数据结构》读书笔记(1)

其实去年的时候就看过这本书了。只是,基本上是走马观花, 了解了一些基本概念。这次,为了看懂里面的代码,又特地去复习了一下c语言。还记得上次看的时候,感觉算法果然名不虚传,真的难!现...

幽灵君
2018/12/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot Actuator监控应用

微服务的特点决定了功能模块的部署是分布式的,大部分功能模块都是运行在不同的机器上,彼此通过服务调用进行交互,前后台的业务流会经过很多个微服务的处理和传递,出现异常如何快速定位便成...

zw965
15分钟前
4
0
高性能最终一致性框架Ray之基本概念原理

一、Actor介绍 Actor是一种并发模型,是共享内存并发模型的替代方案。 共享内存模型的缺点: 共享内存模型使用各种各样的锁来解决状态竞争问题,性能低下且让编码变得复杂和容易出错。 共享内...

程序员修BUG
16分钟前
4
0
如何去掉子集合功能中的按钮?

解决方案: 1、找到子集合字段 2、打开字段详细信息,在辅助配置里面进行配置 加入JEPaaS技术交流群,了解更多

JEPaaS云平台
17分钟前
5
0
创龙TI KeyStone C66x多核定点/浮点DSP TMS320C665x + Xilinx Artix-7 FPGA处理器;

广州创龙结合TI KeyStone系列多核架构TMS320C665x及Xilinx Artix-7系列FPGA设计的TL665xF-EasyEVM开发板是一款DSP+FPGA高速大数据采集处理平台,其底板采用沉金无铅工艺的6层板设计,适用于高...

Tronlong创龙
19分钟前
4
0
hbuilder打包常用android权限配置

常用android权限配置 - 开启相机权限 - 允许程序通过WiFi或移动基站的方式获取用户错略的经纬度信息 - 允许程序通过GPS芯片接收卫星的定位信息 - 允许程序获取模拟定位信息,一般用于帮助开发...

小草先森
20分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部