数据结构-线性表

线性表

同一类型元素

有序

线性结构

线性表顺序存储

定义

typedef struct _node *PtrToSqList;
struct _node {
    int data[1024];
    int last;
};
typedef PtrToSqList List;

用数组储存线性表

1024 可替换为任何合适的数

last 本质上是指向表尾的指针，因为数组角标的特殊性，直接使用表尾角标即可

C语言值传递，传递大数组显然很蠢比，不如传数组指针

初始化

List makeEmpty() {
    List l = (List) malloc(sizeof(Node));
    l->last = -1;
}

申请内存，不然空指针

last = -1​ 表示表空

插入

bool insert(List l, int position, int value) {
    int index = position - 1;
    if (!(index >= 0 && index <= l->last + 1)) {
        printf("位置非法");
        return false;
    }
    else if (l->last == 1023) {
        printf("表满");
        return false;
    }
    else {
        for (int i = l->last; i >= index; i--) {
            l->data[i + 1] = l->data[i];
        }
        l->data[index] = value;
        l->last++;
        return true;
    }
}

凡是数组相关的，形参有位置一定要判断是否合法

注意角标

删除

bool delete(List l, int position) {
    int index = position - 1;
    if (!(index >= 0 && index <= l->last)) {
        printf("位置非法");
        return false;
    }
    else if (l->last == -1) {
        printf("表空");
        return false;
    }
    else {
        for (int i = index; i <= l->last; i++) {
            l->data[i] = l->data[i + 1];
        }
        l->last--;
        return true;
    }

}

链表-线性表链式存储

单链表一定要有一个空的头结点，主要目的是保持引用传递时，头结点指针不会随着第一个结点的变化而变化，进而引起不必要的维护漏洞

定义

struct _node {
    int data;
    struct _node *next;
} Node;
typedef struct _node *List;
typedef struct _node *PtrToList;

List 虽然跟 PtrToList 定义一致，但是 List 侧重于其指向的内容，PtrToList 侧重于自己是一个指针的身份事实

初始化

List makeEmpty() {
    List head = (List) malloc(sizeof(Node));
    head->next = NULL;
    List l = head;
    return l;
}

申请内存，不然空指针

注意 l 将永远指向 head 结点，但仅限单链表

表长度

int length(List l) {
    PtrToList p = l;
    int cnt = -1;
    while (p) {
        p = p->next;
        cnt++;
    }
    return cnt;

}

逻辑相连，动态的代价就是长度不确定性

插入

bool insert(List l, int position, int value) {
    int lent = length(l);
    PtrToList pre = l;
    List tmp = (List) malloc(sizeof(Node));
    tmp->data = value;

    if (!(position >= 1 && position <= lent + 1)) {
        printf("位置非法");
        return false;
    }
    else {
        for (int i = 1; i <= position - 1; i++) {
            pre = pre->next;
        }
        tmp->next = pre->next;
        pre->next = tmp;
        return true;
    }


}

索引

按位索引

int findByPosition(List l, int position) {
    int lent = length(l);
    PtrToList p = l;
    if (!(position >= 1 && position <= lent)) {
        printf("位置非法");
        return false;

    }
    else {
        for (int i = 1; i <= position; i++) {
            p = p->next;
        }
        return p->data;
    }
}

检测位置合法性

按值索引

int findByValue(List l, int value) {
    int lent = length(l);
    PtrToList p = l;

    for (int i = 1; i <= lent; i++) {
        p = p->next;
        if (p->data == value) {
            return i;
        }
    }
    return false;

}

没找到应该返回 false

删除

bool delete(List l, int position) {
    int lent = length(l);
    PtrToList pre = l;
    if (!(position >= 1 && position <= lent)) {
        printf("位置非法");
        return false;
    }
    else {
        for (int i = 1; i <= position - 1; i++) {
            pre = pre->next;
        }
        PtrToList cur = pre->next;
        pre->next = cur->next;
        free(cur);
        return true;
    }

}