【数据结构】线性、链式List简单实现

谁借莪１个温暖的怀抱￠ 2021-09-21 04:30 293阅读 0赞

### 文章目录 ###

*   *  线性数组实现
     *  链式实现
     *  总结

--------------------

## 线性数组实现 ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 0
    #define OK 1
    #define OVERFLOW -1
    #define TRUE 1
    #define FALSE 0
    #define INIT_SIZE 5
    
    typedef int ElemType;
    typedef int Status;
    typedef struct List {
        ElemType *elem;
        int capacity;
        int length;
    } List;
    
    void initList(List &L) {
        L.elem = (ElemType *) malloc(sizeof(ElemType) * INIT_SIZE);
        L.length = 0;
        L.capacity = INIT_SIZE;
    }
    
    //获取元素
    ElemType getElem(List &L, int index) {
        if (index < 0 || index >= L.length) exit(ERROR);
        return L.elem[index];
    }
    
    
    Status extendCapacity(List &L) {
        ElemType *newElem = (ElemType *) malloc(sizeof(ElemType) * (L.capacity * 2 + 1));
        for (int i = 0; i < L.length; i++) {
            newElem[i] = L.elem[i];
        }
        L.elem = newElem;
        L.capacity = L.capacity * 2 + 1;
        return OK;
    }
    
    Status addElem(List &L, ElemType e) {
        if (L.length > L.capacity)extendCapacity(L);
        L.elem[L.length++] = e;
        return OK;
    };
    
    Status insertElem(List &L, ElemType e, int index) {
        if (index < 0 || index > L.length)return ERROR;
        if (L.length > L.capacity)extendCapacity(L);
        for (int i = L.length; i > index; i--) {
            L.elem[i] = L.elem[i - 1];
        }
        L.elem[index] = e;
        L.length++;
        return OK;
    }
    
    Status deleteElem(List &L, int index) {
        if (index < 0 || index >= L.length)return ERROR;
        for (int i = index; i < L.length - 1; i++) {
            L.elem[i] = L.elem[i + 1];//i+1<length --> i<length-1
        }
        L.length--;
        return OK;
    }
    
    void printList(List &L) {
        for (int i = 0; i < L.length; i++)
            printf("%d\n", L.elem[i]);
    }
    
    int isEmpty(List &L) {
        if (L.length == 0)return TRUE;
        return FALSE;
    }
    
    //test
    int main() {
        List L;//declare
        initList(L);//初始化
    
        addElem(L, 1);
        addElem(L, 2);
        addElem(L, 3);
        addElem(L, 4);
        addElem(L, 5);
        addElem(L, 6);//到此元素,扩展容量(初始容量5)
        addElem(L, 7);
        insertElem(L, 0, 0);//在头部插入0
        insertElem(L, 0, L.length);//在尾部插入0
    
        deleteElem(L, 0);//删除首元素0
        printList(L);
    
        printf("------------\n");
        printf("%d\n", getElem(L, 3));
        return 0;
    }

## 链式实现 ##

#include <iostream>
    using namespace std;
    typedef int ElemType;
    
    typedef struct LNode {
        ElemType data;
        struct LNode *next;
    } LNode, *LinkList;
    
    void createList(LinkList &L) {
        L = new LNode;//head node
        L->next = NULL;
    }
    
    //初始化并输入n个元素
    void createList(LinkList &L,int n){
        L = new LNode;
        L->next = NULL;
    
        //逆序 前插发
    //    for(int i=0;i<n;i++){
    //        LNode *new_node = new LNode;
    //        cin>>new_node->data;
    //        new_node->next = NULL;
    //        new_node->next = L->next;
    //        L->next = new_node;
    //    }
    
        //正序 后插法
        LinkList p = L;
        for(int i=0;i<n;i++){
            LNode *new_node = new LNode;
            cin>>new_node->data;
            new_node->next = NULL;//init
            p->next = new_node;
            p = p->next;//point tail elem
        }
    
    
    }
    
    
    //取L中第i个元素返回
    ElemType getELem(LinkList L, int i) {
        LinkList p = L;
        int j = 0;
    
        while (p && j < i-1) {
            p = p->next;
            j++;
        }
    
        if (!p || j > i-1) {
            cout << "error i>n,i<0 " << endl;
            return 0;
        }
        return p->next->data;
    }
    
    //在地i个位置插入节点
    void insert(LinkList &L, int i, ElemType e) {
        LinkList p;
        p = L;
        int j = 0;
        while (p && j < i-1) {
            p = p->next;
            j++;
        }
    
        if (!p || j > i) {
            cout << "error i<1-1, i>n+1" << endl;
            return;
        }
    
        LNode *new_node = new LNode;
        new_node->data = e;
        new_node->next = NULL;
    
        //p是最后一个节点
        if(!p->next){
            p->next = new_node;
            return;
        }
    
        new_node->next = p->next;
        p->next = new_node;
    }
    
    //删除L中第i个元素
    void del(LinkList &L, int i) {
        LinkList p = L;//head element
        int j = 0;
        while (p && j < i - 1) {
            p = p->next;
            j++;
        }
    
        if (!(p->next) || j > i - 1) {
            cout << "i<1 , i>n";
            return;
        }
        LNode *del_node = p->next;
    
        //如果del_node后不存在节点
        if (!del_node->next) {
            delete (del_node);
            p->next = NULL;
            return;
        }
        //连接链表
        p->next = p->next->next;
        delete (del_node);
    }
    
    void printList(LinkList L){
        int i=0;
        while(L->next != NULL){
            L=L->next;
            i++;
            printf("No.%d elem:%d\n",i,L->data);
        }
    
    }
    
    //test
    int main() {
        LinkList L;
        createList(L,3);//1 2 3
        insert(L,2,222);
        printList(L);
        del(L,2);
        cout<<"-------------"<<endl;
        printList(L);
    
    
        cout<<"-------------"<<endl;
        ElemType e = getELem(L,1);
        cout<<e<<endl;
    
        return 0;
    }

## 总结 ##

线性表使用数组实现, 特点是读取快, 插入删除慢;  
链表使用一个个node节点, 使用指针关联node之间的关系, 特点是读取慢, 插入删除快;

--------------------

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[https_elltor.com]: https://elltor.com/