`
NOthingAj
  • 浏览: 16290 次
社区版块
存档分类
最新评论

通过数组实现线性表

 
阅读更多

基本实现：

 

一、头文件、宏定义以及函数声明：

 

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INC 10

typedef int ElemType;

typedef enum Status {
    success, range_error, fatal, fail
    } Status;

typedef struct sqlList {
    ElemType *elem; // 结点元素
    int length; // List的当前长度
    int list_size; // List的最大长度
} SqList, *Ptr;
typedef Ptr SqlListptr;

Status List_Init(SqlListptr L);
Status List_Retrival(SqlListptr L, int pos, ElemType *elem);
Status List_Locate(SqlListptr L, int *pos, ElemType elem);
Status List_Insert(SqlListptr L, int pos, ElemType elem);
Status List_delete(SqlListptr L, int pos);

 

 

二、初始化函数：

 

Status List_Init(SqlListptr L) {
    Status s = success;
    L->list_size = LIST_INIT_SIZE;
    L->length = 0;
    L->elem = (ElemType*)malloc(sizeof(ElemType)*L->list_size); // malloc() 返回的是空指针，所以需要强制转换
    if(L->elem == NULL) {
        s = fatal;
    }
    return s;
}

 

 

三、功能函数：

 

// 按位置查找元素
Status List_Retrival(SqlListptr L, int pos, ElemType *elem) {
    Status s = range_error;
    if(L) {
        if((pos-1>=0) && (pos-1) < L->length) {
            *elem = L->elem[pos-1];
            s = success;
        }
    }
    else 
        s = fatal;
    return s;
}

// 按值查找元素
Status List_Locate(SqlListptr L, int *pos, ElemType elem) {
    Status s = range_error;
    if(L) {
        for(size_t i = 0; i < L->length; i++) {
            if(elem == L->elem[i]) {
                *pos = i+1;
                s = success;
                break;
            }
        }
    }
    else    
        s = fatal;
    return s;
}

// 插入元素
Status List_Insert(SqlListptr L, int pos, ElemType elem) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) <= L->length) {
        if(L && L->length < L->list_size ) {
            for(int i = L->length-1; i >= pos-1 ; i--) {
                L->elem[i+1] = L->elem[i];
            } 
            L->elem[pos-1] = elem;
            L->length++;
            s = success;
        }
    } else 
        s = fatal;
    return s;
}

// 删除元素
Status List_delete(SqlListptr L, int pos) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) < L->length) {
        if(L && L->length > 0) {
            for(int i = pos; i <= L->length; i++) {
                L->elem[i-1] = L->elem[i];
            }
            L->length--;
            s = success;
        }
    } else {
        s = fail;
    }
    return s;
}

 

完整实现代码：

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INC 10

typedef int ElemType;

typedef enum Status {
    success, range_error, fatal, fail
} Status;

typedef struct sqlList {
    ElemType *elem; // 结点元素
    int length; // List的当前长度
    int list_size; // List的最大长度
} SqList, *Ptr;
typedef Ptr SqlListptr;

Status List_Init(SqlListptr *L);
Status List_Retrival(SqlListptr L, int pos, ElemType *elem);
Status List_Locate(SqlListptr L, int *pos, ElemType elem);
Status List_Insert(SqlListptr L, int pos, ElemType elem);
Status List_delete(SqlListptr L, int pos);
void List_print(SqlListptr L);
int dealProcess(void);

int main(int argc, char const *argv[])
{
    dealProcess();
    return 0;
}

// 处理过程
int dealProcess() {
    int action;
    Status s;
    SqlListptr L = (SqlListptr)malloc(sizeof(SqList));;
    int position, *elem;
    int *pos, value;

    printf("初始化线性表——1\n");
    printf("按位置查找元素——2\n");
    printf("按值查找元素——3\n");
    printf("插入元素——4\n");
    printf("删除元素——5\n");
    printf("打印元素——6\n");
    printf("输入当前操作：\n");
    
    while((scanf("%d", &action)) != EOF){
        switch (action) {
            case 1:
                s = List_Init(&L);
                if(s == success) {
                    printf("初始化成功\n");
                } else {
                    printf("初始化错误\n");
                }
                break;
            case 2:
                printf("请输入查询位置：\n");
                scanf("%d", &position);
                elem = malloc(sizeof(int));
                s = List_Retrival(L, position, elem);
                if(s == success) {
                    printf("你所查询的元素是：%d\n", *elem);
                } else {
                    printf("该位置无元素\n");
                }
                break;
            case 3:
                pos = malloc(sizeof(int));
                printf("请输入要查询元素的值：\n");
                scanf("%d", &value);
                s = List_Locate(L, pos, value);
                if(s == success) {
                    printf("%d 的位置在 %d\n", value, *pos);
                } else {
                    printf("未找到该元素\n");
                }
                free(pos);
                break;
            case 4:
                printf("请依次输入插入位置和插入的值\n");
                scanf("%d %d", &position, &value);
                s = List_Insert(L, position, value);
                if(s == success) {
                    printf("插入成功\n");
                } else {
                    printf("插入失败\n");
                }
                break;
            case 5:
                printf("请输入要删除的元素的位置\n");
                scanf("%d", &position);
                s = List_delete(L, position);
                if(s == success) {
                    printf("删除成功\n");
                } else {
                    printf("删除失败\n");
                }
                break;
            case 6:
                printf("*****************************\n");
                List_print(L);
                printf("*****************************\n");
                break;
        }
    }
    return 0;
}

// 初始化线性表
Status List_Init(SqlListptr *L) {
    Status s = fail;
    (*L)->length = 0;
    (*L)->list_size = LIST_INIT_SIZE;
    (*L)->elem = malloc(sizeof(int)*LIST_INIT_SIZE);
    s = success;
    return s;
}

// 按位置查找元素
Status List_Retrival(SqlListptr L, int pos, ElemType *elem) {
    Status s = range_error;
    if(L) {
        if((pos-1>=0) && (pos-1) < L->length) {
            *elem = L->elem[pos-1];
            s = success;
        }
    }
    else
        s = fatal;
    return s;
}

// 按值查找元素
Status List_Locate(SqlListptr L, int *pos, ElemType elem) {
    Status s = range_error;
    if(L) {
        for(int i = 0; i < L->length; i++) {
            if(elem == L->elem[i]) {
                *pos = i+1;
                s = success;
                break;
            }
        }
    }
    else
        s = fatal;
    return s;
}

// 插入元素
Status List_Insert(SqlListptr L, int pos, ElemType elem) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) <= L->length) {
        if(L && L->length < L->list_size ) {
            for(int i = L->length-1; i >= pos-1 ; i--) {
                L->elem[i+1] = L->elem[i];
            }
            L->elem[pos-1] = elem;
            L->length++;
            s = success;
        }
    } else
        s = fatal;
    return s;
}

// 删除元素
Status List_delete(SqlListptr L, int pos) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) < L->length) {
        if(L && L->length > 0) {
            for(int i = pos; i <= L->length; i++) {
                L->elem[i-1] = L->elem[i];
            }
            L->length--;
            s = success;
        }
    } else {
        s = fail;
    }
    return s;
}

// 打印元素 
void List_print(SqlListptr L) {
    int flag = 0;
    if(L->length == 0) printf("无元素\n");
    else {
        for(int i = 0; i < L->length; i++) {
            if(flag) printf(" ");
            flag = 1;
            printf("%d", *(L->elem++));
        }
        printf("\n");
    }
}

 

 

总体来说数组线性表实现比较简单，查询元素速度较快，但是插入和删除元素效率很低：

 

插入元素时间复杂度：



 

删除元素时间复杂度：



 

 

  • 大小: 237.1 KB
  • 大小: 123.7 KB
分享到：
| servlet的<url-pattern>匹配问题
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数组实现线性表 数据结构

    线性表是计算机科学中最基础也是最常用的数据结构之一，通过数组实现线性表不仅可以帮助理解数据结构的基础知识，还能为更复杂的数据结构和算法学习打下坚实的基础。通过上述的操作实现，我们可以轻松地创建、操作和...

    数组实现线性表-VS2015.zip_C++

    总之，"数组实现线性表-VS2015"这个项目旨在帮助初学者理解和实践数据结构中的线性表概念，通过C++和Visual Studio 2015，开发者能够更好地掌握数据结构的基础知识和实际应用。通过这个项目的学习，不仅能够提升编程...

    数组实现线性表-VS2015.zip_数组实现线性表格

    在数组实现线性表时，我们首先需要理解数组的基本概念。数组是一种数据结构，它将相同类型的元素存储在一个连续的内存区域中，可以通过索引来访问每个元素。数组的索引通常从0开始，因此一个包含n个元素的数组，其...

    用数组实现线性表的各种操作(C语言)只完成一部分功能，明日继续

    这篇博客"用数组实现线性表的各种操作(C语言)只完成一部分功能，明日继续"可能探讨了如何使用C语言创建和操作线性表，但遗憾的是，由于描述为空，我们无法获取具体实现的细节。 不过，我们可以根据线性表的基本操作...

    用java定长数组实现线性表

    本篇文章将深入探讨如何用Java定长数组实现线性表，以及相关的设计和操作。 首先，我们需要理解什么是定长数组。在Java中，数组是一种固定大小的数据结构，一旦创建，其长度就不能更改。因此，定长数组在内存中分配...

    用Java动态数组扩充实现线性表

    在Java中，我们通常使用数组或链表来实现线性表。本话题聚焦于使用动态数组来实现线性表，这是一种常见的数据结构实现方式，因为它既保留了数组的高效访问特性，又能灵活地调整大小以适应数据的变化。 动态数组，也...

    用数组实现线性表各种操作(C语言)完结

    通过阅读和理解这段代码，读者可以深入学习C语言中数组实现线性表的细节，包括动态内存管理、数组操作以及对基本数据结构的理解。这些知识对于学习数据结构和算法，特别是对于从事软件开发的人来说，都是非常基础且...

    Java 实现线性表

    一、数组实现线性表 1. **数组定义**：在Java中，数组是最基本的线性数据结构，可以存储同一类型的元素。通过声明一个数组变量，我们可以预定义数组的长度，并在初始化时为每个元素分配空间。 ```java int[] array...

    数组描述线性表

    1、创建线性表类：线性表的存储结构使用数组描述，提供操作: 插入、删除、 查找等。 2、设通讯录中每一个联系人的内容有：姓名、电话号码、班级、宿舍。由键 盘输入或文件录入的通讯录信息建立通讯录表，使用线性表...

    用数组实现一个线性表.zip

    线性表是计算机科学中一种基础的数据结构，它是由n（n...通过学习如何用数组实现线性表，我们可以更好地理解数据结构和算法，提升编程能力。在实践中，根据具体需求选择合适的数据结构，能够提高程序的效率和可维护性。

    线性表实现各种操作 使用数组

    用数组实现线性表，并完成各种操作，主要是插入查找、删除插入

    数据结构 线性表实验代码 C语言 数组

    通过实际编程，学生可以深入理解C语言中的数组操作，以及如何通过数组实现线性表的数据结构。同时，这也是一次锻炼动态内存管理和指针操作的好机会，这两者在C语言中至关重要。 总的来说，这个实验代码涵盖了数据...

    【价值比较】应选择数组or链表实现线性表数据结构_C语言编程实现

    1.代码相关CSDN博客文章：https://blog.csdn.net/u013025955/article/details/90644964 2.目录结构： code：源代码；project：VC 6.0工程

    c语言数据结构实现线性表

    一、数组实现线性表 1. 定义结构体：首先，我们需要定义一个结构体，它包含元素值以及数组长度和实际元素数量。例如： ```c typedef struct { int *data; // 存储元素的数组 int capacity; // 数组容量 int size...

    线性表操作 栈和队列的应用 多维数组和串

    顺序队列可以用数组实现，但当队列满或空时可能会遇到问题，因此通常使用循环队列来解决这些问题。循环队列利用数组的循环特性，避免了队列满或空时需要重新分配内存的问题。链式队列则是用链表实现，插入和删除操作...

    线性表的数组实现

    线性表的数组实现，采用抽象数据型ADT的语法说明和语法格式说明进行实现，操作规范。

    线性表的数组表示和实现

    线性表的数组表示和实现 线性表的数组表示和实现

    线性表的C语言实现

    1. **数组实现线性表** 数组是最直观的线性表实现方式，它通过预先分配连续的内存空间来存储元素。在C语言中，可以声明一个固定大小的数组来实现线性表。优点是访问速度快，因为数组支持随机访问，时间复杂度为O(1)...

    《数据结构(C语言版)》 几个线性表的函数

    1. **数组实现线性表** 数组是最基础的数据结构，它提供了随机访问元素的能力。在C语言中，可以使用一维数组来表示线性表，每个元素对应数组中的一个位置。线性表的基本操作包括： - 初始化：创建并分配内存空间给...

    201720130142_黄孔进_实验三1

    总的来说，这个实验旨在让学生熟悉和掌握线性表的基本操作，通过数组实现线性表，以及在实际应用中如何运用这些操作。实验涵盖了数据结构和算法的基础知识，对于计算机科学与技术专业的学生来说，这是非常重要的实践...

Magicbox
Global site tag (gtag.js) - Google Analytics