C语言实现线性表

简介: C语言实现线性表

线性表是最简单的数据结构之一,

一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

线性表定义(sqList.h文件):

//
// Created by tioncico on 19-4-25.
//
#ifndef TEST\_SQLIST\_H
#define TEST\_SQLIST\_H
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define LIST\_INIT\_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量(当存储空间不够时要用到,暂时未使用`1)
typedef int listElemType;
typedef struct {
    listElemType *elem;
    int length;
    int listSize;
} sqList;
int initList(sqList *);
int destroyList(sqList *);
int listEmpty(sqList);
int listLength(sqList);
int getElem(sqList ,int,listElemType *);
int getElemLocation(sqList,listElemType);
int getElemPrior(sqList,listElemType,listElemType *);
int getElemNext(sqList,listElemType,listElemType *);
int insertList(sqList *,int ,listElemType);
int deletList(sqList *, int,listElemType *);
void printList(sqList);
#endif //TEST\_SQLIST\_H

线性表操作方法(sqList.c文件):

//
// Created by tioncico on 19-4-24.
//
#include "sqList.h"
/**
 * 初始化线性表
 * @param list
 * @return
 */
int initList(sqList *list) {
    //给data分配内存空间
    list->elem = (listElemType *) malloc(sizeof(listElemType) * LIST\_INIT\_SIZE);
    if (list->elem == NULL) {
        return -1;
    }
    list->length = 0;
    list->listSize = LIST\_INIT\_SIZE;
    return 0;
}
/**
 * 判断线性表是否不为空
 * @param list
 * @return
 */
int listEmpty(sqList list) {
    if (list.length == 0) {
        return 0;
    } else {
        return -1;
    }
}
/**
 * 获取表长度
 * @param list
 * @return
 */
int listLength(sqList list) {
    return list.length;
}
/**
 * 获取i位置的元素
 * @param list
 * @param i
 * @param elemType
 * @return
 */
int getElem(sqList list, int i, listElemType *elemType) {
    if (i < 0 || i > list.length) {
        return -1;
    }
    *elemType = list.elem\[i\];
    return 0;
}
/**
 * 获取某个元素的位置
 * @param list
 * @param elemType
 * @return
 */
int getElemLocation(sqList list, listElemType elemType) {
    for (int i = 0; i < list.length; ++i) {
        if (list.elem\[i\] == elemType) {
            return i;
        }
    }
    return -1;
}
/**
 * 获取某个元素之前的元素
 * @param list
 * @param elemType
 * @param priorElem
 * @return
 */
int getElemPrior(sqList list, listElemType elemType, listElemType *priorElem) {
    if (elemType == list.elem\[0\]) {
        return -1;
    }
    int i = getElemLocation(list, elemType);
    if (i == -1) {
        return -1;
    }else{
        *priorElem = list.elem\[i-1\];
        return 0;
    }
    return -1;
}
/**
 * 获取某个元素之后的元素
 * @param list
 * @param elemType
 * @param priorElem
 * @return
 */
int getElemNext(sqList list, listElemType elemType, listElemType *priorElem) {
    if (elemType == list.elem\[list.length-1\]) {
        return -1;
    }
    int i = getElemLocation(list, elemType);
    if (i == -1) {
        return -1;
    }else{
        *priorElem = list.elem\[i+1\];
        return 0;
    }
}
/**
 * 删除该线性表
 * @param list
 * @return
 */
int destroyList(sqList *list) {
    if (list->elem) {
        free(list->elem);
    }
    list->length = 0;
    return 0;
}
/**
 * 在位置i插入一条数据
 * @param list
 * @param i
 * @param elemType
 * @return
 */
int insertList(sqList *list, int i, listElemType elemType) {
    if (i >= 0) {
        if (i > list->listSize) {
            return -1;
        }
        if (!list->elem) {
            return -1;
        }
        listElemType *q = NULL;
        q = &list->elem\[i\];//插入位置
        listElemType *p = NULL;
        for (p = &list->elem\[list->length - 1\]; p >= q; p--) {
            *(p + 1) = *p;
        }
        *q = elemType;
        list->length++;
//        list->listSize += LISTINCREMENT;
        return 0;
    } else {
        i = list->length;
        return insertList(list, i, elemType);
    }
}
/**
 * 删除表
 * @param list
 * @param i
 * @param e
 * @return
 */
int deletList(sqList \*list, int i, listElemType \*e) {
    if (i < 0 || i > list->listSize) {
        return -1;
    }
    listElemType *q = NULL;
    listElemType *p = NULL;
    q = &list->elem\[i\];
    \*e = \*q;//获取到该元素
    p = &list->elem\[list->length - 1\];//最后一个元素
    for (; q <= p; q++) {
        \*q = \*(q - 1);
    }
    list->length--;
    return 0;
}
/**
 * 打印
 * @param list
 */
void printList(sqList list) {
    printf("length:%d,size:%d \\n", list.length, list.listSize);;
    for (int i = 0; i < list.length; ++i) {
        if (i == 0) {
            printf("%d", list.elem\[i\]);
        } else {
            printf(",%d", list.elem\[i\]);
        }
    }
    printf("\\n");
}

调用方式:

#include <stdio.h>
#include "sqList.h"
int main() {
    sqList list;
    //初始化
    int result = initList(&list);
    //指定位置插入数据
    for (int i = 0; i < LIST\_INIT\_SIZE/2; ++i) {
        if (!insertList(&list,i,i*10)){
//            printf("第%d个数%d插入列表\\n",list.length, list.elem\[list.length-1\]);
        }
    }
    //往后插入数据
    insertList(&list,-1,666);
    printf("数据是否为空 %d\\n",listEmpty(list));
    printf("数据长度 %d\\n",listLength(list));
    listElemType elem1;
    getElem(list,13,&elem1);
    printf("获取13位置的值 %d\\n",elem1);
    printf("获取666值的位置 %d\\n",getElemLocation(list,666));
    listElemType elem2;
    getElemPrior(list,666,&elem2);
    printf("获取666前面的值 %d\\n",elem2);
    listElemType elem3;
    getElemNext(list,666,&elem3);
    listElemType elem4;
    deletList(&list,15,&elem4);
    printf("获取15位置删除的值 %d\\n",elem4);
    printList(list);
    destroyList(&list);
    printList(list);
    return 0;
}

输出:

/home/tioncico/CLionProjects/test/cmake-build-debug/test
数据是否为空 -1
数据长度 51
获取13位置的值 130
获取666值的位置 50
获取666前面的值 490
获取15位置删除的值 150
length:50,size:100 
0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140
length:0,size:100
目录
相关文章
|
6月前
|
存储 C语言
C语言线性表的链式表示和实现讲解
C语言线性表的链式表示和实现讲解
37 0
|
6月前
|
存储 C语言 索引
C语言线性表的顺序表示和实现讲解
C语言线性表的顺序表示和实现讲解
33 0
数据结构入门(C语言版)线性表中顺序表介绍及接口实现(下)
在顺序表中,头插相对于尾插来说就不是那么简单了,这里主要是让顺序表整体向后移动,再在头部插入数据。
|
11月前
|
存储 C语言
数据结构 C语言 2.1 线性表抽象数据类型 2.2 小议顺序表
数据结构 C语言 2.1 线性表抽象数据类型 2.2 小议顺序表
41 0
|
C语言
造轮子之-C语言实现ArrayList
造轮子之-C语言实现ArrayList
|
存储 缓存
数据结构入门(C语言版)线性表带头双向循环链表接口实现(下)
这里的查找就是使用一个while循环遍历链表找到某节点的data符合要查找的值
数据结构入门(C语言版)线性表带头双向循环链表接口实现(上)
第一步当然是先使用malloc函数申请内存空间,然后就是两个指针的建立,尾部指针指向头结点头部,头部指针指向头结点尾部,返回带头结点,头结点初始化完成。
|
存储 程序员 C语言
数据结构入门(C语言版)线性表中链表介绍及无头单向非循环链表接口实现
概念: 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。因此,为了表示每个数据元素与其直接后继数据元素之间的逻辑关系,对数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。
|
存储 机器学习/深度学习 算法
数据结构入门(C语言版)线性表中顺序表介绍及接口实现(上)
不论在程序员的工作上,还是在学习或是考研上,数据结构都是一门非常重要且值得我们一直研究探索的学科,可以说数据结构和算法就是编程的核心。OK,接下来我们来到数据结构的入门第一步就是学习线性表,接下来由作者来详细介绍数据结构第一章线性表。
|
存储 C语言
线性表之顺序表(C语言实现)
线性表之顺序表(C语言实现)
124 0