顺序表

线性表的顺序存储实现

1. 线性表的顺序存储实现

利用数组的 连续存储空间顺序存放 线性表的各元素

下标 i

0

1

\cdots

i - 1

i

\cdots

n - 1

\cdots

MAXSIZE - 1

Data

a1a_1

a2a_2

\cdots

aia_i

ai+1a_{i+1}

\cdots

ana_n

\cdots

-

typedef struct LNode* List;
struct LNode {
    ElementType Data[MAXSIZE];
    int Last;
};

struct LNode L;
List PtrL;

// 访问下标为 i 的元素:L.Data[i] 或 PtrL->Data[i]
// 线性表的长度:L.Last+1 或 PtrL->Last+1

2. 主要操作的实现

2.1 初始化(建立空的顺序表)

List MakeEmpty() {
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));
    PtrL->Last = -1;
    return PtrL;
}

2.2 查找

int Find(ElementType X, List PtrL) {
    int i = 0;
    while (i <= PtrL->Last && PtrL->Data[i] != X)
        i++;
    if (i > PtrL->Last)  // 如果没有找到,返回 -1
        return -1;
    else  // 找到后返回的是存储位置
        return i;
}

查找成功的平均比较时间为 (n+1)/2(n + 1) / 2 ,平均时间性能为 O(n)O(n)

2.3 插入(在第 i(1in+1)i (1 \le i \le n + 1) 个位置上插入一个值为 XX 的新元素)

void Insert(ElementType X, int i, List PtrL) {
    int j;
    if (PtrL->Last == MAXSIZE - 1) {
        printf("表满\n");
        return;
    }
    if (i < 1 || i > PtrL->Last + 2) {  // 1 <= i <= n + 1
        printf("位置不合法\n");
        return;
    }
    for (j = PtrL->Last; j >= i - 1; j--)
        PtrL->Data[j + 1] = PtrL->Data[j];
    PtrL->Data[i - 1] = X;
    PtrL->Last++;
    return;
}

平均移动次数为 n/2n/2 ,平均时间性能为 O(n)O(n)

2.4 删除(删除表的第 i(1in)i (1 \le i \le n) 个位置上的元素)

void Delete(int i, List PtrL) {
    int j;
    if (i < 1 || i > PtrL->Last + 1) {
        printf("不存在第%d个元素\n", i);
        return;
    }
    for (j = i; j <= PtrL->Last; j++)
        PtrL->Data[j - 1] = PtrL->Data[j];
    PtrL->Last--;
    return;
}

平均移动次数为 (n1)/2(n-1)/2 ,平均时间性能为 O(n)O(n)

最后更新于

这有帮助吗?