当前位置:   article > 正文

数据结构(一)——顺序表(C语言实现)_c语言中index和elem

c语言中index和elem

定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性,通常有如下4类基本结构:

  • 集合:结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他的关系。如:广义表
  • 线性结构:结构中的数据元素之间存在一个对一个的关系。如:链表
  • 树形结构:结构中的数据元素之间存在一个对多个的关系。如:二叉树
  • 图(网)状结构:结构中的数据元素之间存在多个对多个的关系。如:1

在线性结构中,根据存储方式分为顺序表链表,根据对表的操作限制,分为队列

顺序表的特征是,在内存中占用连续的存储单元,可以简单的理解为顺序表就是数组。只是根据需要,在实际应用中动态分配顺序表占用的内存单元。而数组是在编译的时候,预分配了指定大小的内存单元,因此如下代码段会在编译的时候报错。

int len = 10;
char arr[len];
  • 1
  • 2

但是顺序表又会有数据全部的特点:可以根据下标直接访问、不方便插入和删除元素(因为需要移动后续的元素)。

实现

定义结构

typedef int SeqType; //存储单元类型

typedef struct{
    SeqType *elem; //存储空间基地址
    int length; //当前长度
    int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

结构体内,有三个元素:存储空间基地址,类似于数组首地址;当前长度,记录顺序表中有效存储单元个数;当前分配的存储容量,顺序表中,最多容纳的存储单元个数。当顺序表中所有存储单元已经被使用,在下次插入元素之前,需要新增存储单元。这点是数组所不具有的特性。

*注:定义一个存储单元类型SeqType是为了使顺序表适和更多数据类型,使用的时候修改SeqType类型即可

定义操作

创建顺序表

/**
 * 创建顺序表
 */
SqList createList_sq() {
    //SqList list;
    //return list;

    SqList* list = (SqList*)malloc(sizeof(SqList));
    return *list;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

这里提供两种创建顺序表的代码,一种是由系统分配list占用的内存,一种是自己动态分配的内存,需要在程序运行之前手动释放占用的内存空间。

初始化顺序表

/**
 * 初始化顺序表
 * 返回1 表示初始化成功
 * 返回0 表示初始化失败
 */
int initList_sq(SqList &L) { //只有在C++中才会有引用的存在
    L.elem = (SeqType *) malloc(sizeof(SeqType) * LIST_INIT_SIZE);
    if (!L.elem)
        return 0; //内存分配失败,存储空间不够
    L.length = 0; //表示顺序表为空
    L.listsize = LIST_INIT_SIZE; //表示顺序表里,最大存储单元个数
    return 1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

分配顺序表的存储单元,初始化顺序表属性的值。

插入元素

/**
 * 插入顺序表
 * 下标是负数就插入到结尾
 */
int insertList_sq(SqList &L, int index, SeqType val) {
    if (index > L.length) { //存储的下表超出顺序表实际的长度
        printf("插入的下标超出顺序表的实际长度");
        return 0;
    }
    if (index < 0) //下标是负数,插入到结尾
        index = L.length;
    if (L.length == L.listsize) { //顺序表的存储单元已经存满
        printf("顺序表的存储单元已满,继续分配新的存储单元。");
        SeqType* newBase = (SeqType*) realloc(L.elem,
                (L.listsize + LISTINCREMENT) * sizeof(SeqType)); //继续分配存储单元
        if (!newBase) {
            printf("分配内存单元失败");
            return 0;
        }
        L.elem = newBase;
        L.listsize += LISTINCREMENT;
    }
    //寻找合适的插入位置,index后面的元素向后移动
    for (int i = L.length; i > index; i--) {
        L.elem[i] = L.elem[i - 1]; //向后移动
    }
    L.elem[index] = val; //插入元素
    L.length++;
    return 1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

将元素插入到指定的位置。插入之前,需要先判断顺序表中是否已经存满,再根据需要新增存储单元,最后插入元素。

/**
 * 插入顺序表(结尾的位置)
 * 与上面的函数是重名函数,这叫函数重载,在C++里面支持
 */
int insertList_sq(SqList &L, SeqType val) {
    return insertList_sq(L, L.length, val);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

*引用和重载,是C++中才支持,因此需要在cpp文件中编译。

删除元素

/**
 * 删除指定的元素
 * 返回0 找不到指定的元素,删除失败。
 * 返回1 找到待删除的元素,删除成功。
 */
int removeList_sq(SqList &L, SeqType val) {
    int index = -1; //记录匹配到的下标
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == val) {
            //找到匹配的val,结束循环
            index = i;
            break;
        }
    }
    if (index < 0)
        return 0;
    for (; index < L.length - 1; index++) {
        L.elem[index] = L.elem[index + 1];
    }
    L.length--;
    return 1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

删除指定元素,需要先找到下标。依次移动下标后面的结点,修改length值。

/**
 * 根据下标删除是指定的结点,并返回元素的值
 * 返回0 下标超出顺序表长度,删除失败。
 * 返回1 下标正确,删除元素,并且将已删除元素值转给elem
 */
int removeList_sq(SqList &L, int index, SeqType &elem) {
    if (index >= L.length) //下标超出顺序表的长度
        return 0;
    index = index < 0 ? L.length : index; //下标负数表示删除最后一个节点
    elem = L.elem[index];
    for (int i = index; i < L.length - 1; i++) {
        L.elem[i] = L.elem[i + 1];
    }
    L.length--;
    return 1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

先取到指定下标的元素,赋值给elem,然后依次移动下标后面的结点。最后修改length值。

销毁顺序表

/**
 * 销毁顺序表
 */
void destoryList_sq(SqList &L) {
    free(L.elem); //释放存储空间
    L.length = 0;
    L.listsize = 0;
//  free(&L);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

重点释放顺序表的存储单元。如果顺序表自身的内存也是动态分配的,需要手动释放。

最后附上,头文件的定义。

/*
 * sqlist.h
 *
 * 线性表的顺序存储
 *  Created on: 2016年8月30日
 *      Author: flueky
 */

#ifndef SQLIST_H_
#define SQLIST_H_

#define LIST_INIT_SIZE 50
#define LISTINCREMENT 10

typedef int SeqType; //存储单元类型

typedef struct{
    SeqType *elem; //存储空间基地址
    int length; //当前长度
    int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;

/**
 * 创建顺序表
 */
SqList createList_sq();

/**
 * 初始化顺序表
 */
int initList_sq(SqList &);

/**
 * 插入顺序表
 */
int insertList_sq(SqList &,int index,SeqType);

/**
 * 插入顺序表(结尾的位置)
 */
int insertList_sq(SqList &,SeqType);

/**
 * 在顺序表中移除指定位置元素,下标从0开始
 */
int removeList_sq(SqList &,int,SeqType &);

/**
 * 在顺序表中删除指定元素
 */
int removeList_sq(SqList &,SeqType);
/**
 * 销毁顺序表
 */
void destoryList_sq(SqList &);

#endif /* SQLIST_H_ */
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

  1. 摘自严蔚敏版《数据结构》。
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号