线性表

——主要参考了中国大学MOOC数据结构课程的内容
数据名称：线性表（List）
数据对象集：线性表是个元素构成的有序序列
操作集：线性表，整数i表示位置，元素，线性表的基本操作有：

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这个开销较大的操作。但是，它还是比用数组实现的要好，因为把数组整体前后挪动的确比较费时间。