线性表

作者: 漫游之光 | 来源:发表于2018-09-12 20:47 被阅读0次

——主要参考了中国大学MOOC数据结构课程的内容
数据名称:线性表(List)
数据对象集:线性表是n(\geq0)个元素构成的有序序列(a_1,a_2,…,a_n)
操作集:线性表L\in List,整数i表示位置,元素X\in ElementType,线性表的基本操作有:

  1. List MakeEmpty():初始化一个空线性表L;
  2. ElementType FindKth( int K, List L ):根据位序K,返回相应元素 ;
  3. int Find( ElementType X, List L ):在线性表L中查找X的第一次出现位置;
  4. void Insert( ElementType X, int i, List L):在位序i前插入一个新元素X;
  5. void Delete( int i, List L ):删除指定位序i的元素;
  6. int Length( List L ):返回线性表L的长度n。

线性表有两种主要实现方法,用数组的方法实现和用链表的方式实现,这个程序可能存在一些bug,但是思路是不变的。

#include<stdio.h>
typedef struct L* List;
 
struct L{
    int max;
    int index;
    int* data;
};

List MakeEmpty(){
    List list= (List)malloc(sizeof(struct L));
    list->max = 100;
    list->index = -1;
    list->data = (int)malloc(list->max*sizeof(int));
    return list;
}

int Find(int X, List L){
    int i;
    for(i=0;i<=L->index;i++){
        if(L->data[L->index]==X){
            return i;
        }
    } 
    return -1;
}

void Delete(int i, List L){
    if(i<0||i>L->index){
        printf("位置不存在!\n");
        return;
    }
    int j;
    for(j=i;j<L->index;j++){
        L->data[j] = L->data[j+1];
    }
    L->index--;
}

int FindKth(int K, List L){
    if(K<0||K>L->index){
        printf("位置不存在!\n");
        return -1;
    }
    return L->data[K];
}


void Insert(int X,int i,List L){
    L->index++;
    if(i<0||i>L->index){
        printf("插入位置不正确!\n");
        return;
    }
    int j;
    if(L->index>=L->max){
        int* temp = (int)malloc(sizeof(int)*L->max*2);
        for(j=0;j<L->index;j++){
            temp[j] = L->data[j];
        }
        free(L->data);
        L->data = temp;
    }
    for(j=L->index-1;j>=i;j--){
        L->data[j+1] = L->data[j];
    }
    L->data[i] = X;
}

int Length(List L){
    return L->index+1;
}

可以看出FindKth需要的时间是O(1), 而Insert和Delete需要的时间是O(N);如果用链表实现,Insert和Delete的开销较小而FindKth开销较大。

#include<stdio.h>
typedef struct node* Node;

struct node{
    int data;
    struct node* next;
};

void printNode(Node node){
    if(node==NULL){
        return;
    }
    Node temp = node;
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Node findKth(Node node,int kth){
    int i = 1;
    Node temp = node;
    while(i<kth&&temp!=NULL){
        temp = temp->next;
        i++;
    }
    if(i==kth&&temp!=NULL){
        return temp;
    }else{
        return NULL;
    }
}

Node find(Node node,int data){
    Node temp = node;
    while(temp!=NULL&&temp->data!=data){
        temp = temp->next;
    }
    return temp;
}

Node createNode(int data){
    Node node = (Node)malloc(sizeof(struct node));
    node->next = NULL;
    node->data = data;
    return node;
}

Node insert(Node node,int i,int data){
    if(i==1){
        Node temp = createNode(data);
        temp->next = node;
        return temp;
    }
    Node temp = findKth(node,i-1);
    if(temp==NULL){
        printf("位置错误!\n");
    }else{
        Node insert = createNode(data);
        Node next = temp->next;
        temp->next = insert;
        insert->next = next; 
    }
    return node;
}


Node deleteNode(Node node,int i){
    if(i==1){
        Node temp = node->next;
        free(node);
        return temp;
    }
    Node temp = findKth(node,i-1);
    if(temp==NULL){
        printf("位置错误!\n");
    }else{
        if(temp->next!=NULL){
            Node del = temp->next;
            temp->next = del->next;
            free(del);
        }
    }
    return node;
}

以前对用链表实现的线程表认识有问题,认为其插入和删除操作开销小,没有意识到在插入或删除的时候,需要去调用FindKth这个开销较大的操作。但是,它还是比用数组实现的要好,因为把数组整体前后挪动的确比较费时间。

相关文章

  • 线性表的相关操作

    集合 --- 创建线性表 解散 --- 销毁线性表 长度 --- 得到线性表的长度 出列 --- 从线性表删除一个...

  • [数据结构]第二章线性表(1)——线性表

    线性表 线性表的基本概念 线性表的定义 线性表是具有相同数据类型的n(n>=0)个元素的有限序列。 线性表的基本操...

  • 数据结构与算法(二)

    线性表及其顺序存储结构 线性表的基本概念 线性结构又称为线性表,线性表是最简单也是最常用的一种数据结构。 线性表的...

  • 线性表及应用

    线性表 “线性表(List):零个或多个数据元素的有限序列。” 线性表的顺序存储结构 线性表的顺序存储结构,指的是...

  • 数据结构03-线性表之顺序表

    第三章 线性表之顺序表 第三章 线性表之顺序表一、什么是线性表?1> 概念2> 线性表的基本操作二、线性表的顺序存...

  • 数据结构之线性表

    1、线性表-顺序表线性表-顺序表

  • 线性表数据结构

    线性表 线性表就是数据排成像一条线的结构,每个线性表上的数据最多只有前和后两个方向。与线性表对立的是非线性表,如二...

  • 大话数据结构 - 线性表

    代码GitHub地址 线性表 线性表需要相同的数据类型 线性表的处理方式都是先取代,后目的。比如删除链式线性表的某...

  • 数据结构-线性表(顺序表和链表)

    大纲:理解线性表的逻辑结构掌握线性表的顺序存贮结构和链式存贮结构;掌握线性表基本操作的实现。了解线性表的应用。 线...

  • 数据结构 线性表 单链表 c语言实现可运行

    线性表 线性表概念 线性表定义:具有相同特性数据元素的有限序列。线性表的逻辑结构:线性结构。只有一个表头,只有一个...

网友评论

      本文标题:线性表

      本文链接:https://www.haomeiwen.com/subject/whibgftx.html