数据结构_线性表

线性结构 - 线性表的顺序存储表示及其操作

结构 LNode - PtrToLNode - List

1. 实际存储元素的数组Data[MAXSIZE]
2. 游标，指向最后一个元素Last

创建

1. 动态申请大小为一个List的内存,也可以指定其数组的大小
2. 初始化游标Last为-1

查找

1. 遍历数组，直到数组最后一个元素或找到元素X
2. 如果i大于最后一个元素，表示未找到，否则已找到

插入

1. 先判断表是否已满
2. 判断插入的位序是否合法
3. 循环遍历从末位向后复制，空出第i+1的位置
4. 将新元素X赋值给i+i，完成插入
5. 游标Last加1

删除

1. 先判断是删除的位置是否合法
2. 循环遍历从第i位之后的元素向前移一位，将第i个元素覆盖
3. 游标Last减1

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 10
#define ERROR -1

typedef int Position; // 位置
typedef int ElementType; // 元素
typedef struct LNode *PtrToLNode;// 结构体起始位置
struct LNode {
    // 1.实际存储元素的数组
    ElementType Data[MAXSIZE];
    // 2.游标，指向最后一个元素
    Position Last; 
};
typedef PtrToLNode List;

// 创建
List MakeEmpty() {
    List L;
    // 1. 动态申请大小为一个List的内存,也可以指定其数组的大小
    L = (List) malloc(sizeof(struct LNode));
    // 2. 初始化游标Last为-1
    L->Last = -1;
    return L;
}

// 查找
Position Find(List L, ElementType X) {
    Position i = 0;
    // 1. 遍历数组，直到数组最后一个元素或找到元素X
    while (i <= L->Last && L->Data[i] != X) {
        i++;
    }
    // 2. 如果i大于最后一个元素，表示未找到，否则已找到
    if (i > L->Last) {
        return ERROR;
    }
    return i;
}

// 插入
bool Insert(List L, ElementType X, int i) {
    // 1.先判断表是否已满
    if (L->Last == MAXSIZE - 1) {
        printf("表满");
        return false;
    }
    // 2.判断插入的位序是否合法
    if (i < 1 || i > L->Last + 2) {
        printf("位序不合法");
        return false;
    }
    Position j;
    // 3.循环遍历从末位向后复制，空出第i+1的位置
    for (j = L->Last; j >= i - 1; j--) {
        L->Data[j + 1] = L->Data[j];
    }
    // 4.将新元素X赋值给i+i，完成插入
    L->Data[i - 1] = X;
    // 5. 游标Last加1
    L->Last++;
    return true;
}

// 删除操作
bool Delete(List L, int i) {
    // 1. 先判断是删除的位置是否合法
    if (i < 1 || i > L->Last) {
        printf("位序%d不正确", i);
        return false;
    }
    Position j;
    // 2.循环遍历从第i位之后的元素向前移一位，将第i个元素覆盖
    for (j = i - 1; j < L->Last; j++) {
        L->Data[j] = L->Data[j + 1];
    }
    // 3. 游标Last减1
    L->Last--;
    return true;
}

线性结构 - 线性表的链式存储表示及其操作

结构 LNode - PtrToLNode - List

1. 当前结点的数据Data
2. 下一个结点Next

求表长

1. 循环遍历，并累加变量len

查找（按位序）

1. 位序从第一个元素开始
2. p指向第一个结点
3. 如果指针到指定的index还没有找到，或是扫描到最后的元素NULL,则退出
4. 指针指向index位置，同时不为NULL

查找（按元素）

1. p指向第一个结点
2. 当指针遍历到最后为NULL或是找到元素X，则退出
3. 如果p不为NULL，表示找到元素，返回p，否则返回NULL

#include <stdlib.h>
#define ERROR -1

typedef int ElementType; // 元素
typedef struct LNode *PtrToLNode;
struct LNode {
    // 1. 当前结点的数据Data
    ElementType Data;
    // 2. 下一个结点Next
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

// 求表长
int Length(PtrToLNode L) {
    Position P;
    int len = 0;
    P = L;
    while (P) {
        P = P->Next;
        len++;
    }
    return len;
}

// 查找,按index
ElementType FindElementByIndex(List L, int index) {
    Position p;
    // 1. 位序从第一个元素开始
    int cnt = 1;
    // 2. p指向第一个结点
    p = L;
    // 3. 如果指针到指定的index还没有找到，或是扫描到最后的元素NULL,则退出
    while (cnt < index && p) {
        p = p->Next;
        cnt++;
    }
    // 4. 指针指向index位置，同时不为NULL
    if (cnt == index && p) {
        return p->Data;
    } else {
        return ERROR;
    }
}

// 查找，按元素
Position FindElement(List L, ElementType X) {
    Position p;
    // 1. p指向第一个结点
    p = L;
    // 2. 当指针遍历到最后为NULL或是找到元素X，则退出
    while (p && p->Next != X) {
        p = p->Next;
    }
    // 3. 如果不为NULL，表示找到元素，返回p，否则返回NULL
    if (p) {
        return p;
    } else {
        return NULL;
    }
}