[Data Structure]线性表：顺序表与链表实现

给自己找个事做…也算是开个头，打算慢慢把大二要学的数据结构课的数据结构自己慢慢地来都搭一遍。

先来点简单的。

顺序表：

struct Lnode{
    int data[maxsize];//表本体
    int last;//最后一个元素的下标

    void clear(){
        last = -1;
    }//重置顺序表，将表的长度置为0（即最后一个下标置为-1）

    int FindKth(int k){
        if(k > last || k < 0) return -1;
        return data[k];
    }

    int Find(int x){
        int i = 0;
        while(i <= last && x != data[i])
            i++;
        if(i > last) return -1;
        else return i;
    }

    void insert(int i, int x){
        if(i < 0 || i > last + 1){
            printf("The Error Position
");
            return ;
        }
        for(int j = last; j >= i; j--)
            data[j+1] = data[j];
        data[i] = x;
    }

   void del(int i){
        if(i < 0 || i > last){
            printf("The Error Position
");
            return ;
        }
        for(int j = i + 1; j <= last; j++){
            data[j-1] = data[j];
        }
   }

   inline int length(){return last + 1;}
};
typedef Lnode* List;

分别对建空表、找下标为k的元素、找值为x的元素下标、向表中下标为i-1的后面插入元素x、删除下标为i的元素、返回表长进行了实现

链表（单向）：

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

typedef node* list;

list create(int n){//建表
    list t = (list)malloc(sizeof(node));
    list head = (list)malloc(sizeof(node));;
    head = t;
    t->next = NULL;
    while(n--){
        int tmp;
        cin>>tmp;
        list s = (list)malloc(sizeof(node));
        s->data = tmp;
        t->next = s;
        s->next = NULL;
        t = s;
    }
    return head->next;
}

list FindKth(int k, list head){//找表中第k个元素
    int j = 1;
    list tmp = head;
    while(tmp && j < k){
        j++;
        tmp = tmp->next;
    }
    if(tmp != NULL) return tmp;
    else return NULL; 
}

list Find(int x, list head){//找表中数值域为x的结点
    list tmp = head;
    while(tmp->data != x && tmp){
        tmp = tmp->next;
    }
    if(tmp != NULL) return tmp;
    else return NULL;
}

list insert(int i, int x, list head){ //将data值为x的结点插在第i个位置，即i-1个位置的后方
    list tmp = head;
    list position = FindKth(i-1, tmp);
    list s = (list)malloc(sizeof(node));
    s->data = x;
    if(i == 1){
        s->next = head;
        return s;
    }

    if(position == NULL)return tmp;
    else{
        s->next = position->next;
        position->next = s;
        return tmp;
    }
}

list del(int i, list head){//删掉第i个结点
    list tmp = head;
    list p = FindKth(i-1, tmp);
    if(i == 1){
        tmp = head->next;
        return tmp;
    }

    if(p == NULL || p->next == NULL) return tmp;
    else{
        list t = (list)malloc(sizeof(node));
        t = p->next;
        p->next = t->next;
        free(t);
        return tmp;
    }
}

int Length(list head){
    int j = 0;
    do{
        head = head->next;
        j++;
    }while(head);
    return j;
}

void print(list head){
    while(head){
        cout<<head->data<<" ";
        head = head->next;
    }
}