本文共 4219 字，大约阅读时间需要 14 分钟。

线性表、顺序表与链表技术文档

一、线性表

1.基本概念

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长。当n=0时，线性表是一个空表。

几个概念：

• ai表示线性表中的第i个元素。
• a1是表头元素；an是表尾元素。
• 除第一个元素外，每个元素有且仅有一个前驱；除最后一个元素外，每个元素有且仅有一个后继。

2.基本操作

1. 初始化

void InitList(List* L) {    L->data = (int*)malloc(InitSize * sizeof(int));    L->length = 0;    L->MaxSize = InitSize;}

2. 销毁

void DestroyList(List* L) {    for (int i = 0; i < L->length; i++) {        L->data[i] = 0;    }    L->length = 0;}

3. 插入操作

插入元素需将之后的元素从后往前移。

bool ListInsert(List* L, int n, int e) {    if (n > L->length + 1) {        return false;    }    for (int i = L->length; i > n; i--) {        L->data[i] = L->data[i - 1];    }    L->data[n - 1] = e;    L->length++;    return true;}

4. 删除操作

删除元素需将之后的元素从前往后移。

bool ListDelete(List* L, int n, int* e) {    if (n < 0 || n > L->length + 1) {        return false;    }    *e = L->data[n - 1];    for (int i = n - 1; i < L->length; i++) {        L->data[i] = L->data[i + 1];    }    L->length--;    return true;}

5. 查找操作

按值查找函数需要遍历整个表。

int LocateElem(List* L, int n) {    for (int i = 0; i < L->length; i++) {        if (L->data[i] == n) {            return i;        }    }    return -1;}

6. 其他操作

• Length(L): 返回表长。
• PrintList(L): 输出所有元素。
• Empty(L): 判空操作。

二、顺序表

1. 存储结构

• 顺序表是具有相同类型的n（n≥0）个数据元素的有限序列。
• 顺序存储：逻辑上相邻的元素存储在物理位置上也相邻。

2. 实现方式

1. 静态分配

使用静态数组实现，大小固定。

typedef struct SeqList {    int data[MaxSize];    int length;} SeqList;

2. 动态分配

使用动态数组实现，支持扩展。

typedef struct SeqList {    int* data;    int MaxSize;    int length;} SeqList;

3. 特点

• 随机访问：O(1)时间内访问任意元素。
• 存储密度高。
• 插入删除不方便，需移动大量元素。

3. 基本操作

1. 初始化

void InitList(SeqList* L) {    L->data = (int*)malloc(InitSize * sizeof(int));    L->length = 0;    L->MaxSize = InitSize;}

2. 销毁

void DestroyList(SeqList* L) {    for (int i = 0; i < L->length; i++) {        L->data[i] = 0;    }    L->length = 0;}

3. 插入操作

bool ListInsert(SeqList* L, int n, int e) {    if (n > L->length + 1) {        return false;    }    for (int i = L->length; i > n; i--) {        L->data[i] = L->data[i - 1];    }    L->data[n - 1] = e;    L->length++;    return true;}

4. 删除操作

bool ListDelete(SeqList* L, int n, int* e) {    if (n < 0 || n > L->length + 1) {        return false;    }    *e = L->data[n - 1];    for (int i = n - 1; i < L->length; i++) {        L->data[i] = L->data[i + 1];    }    L->length--;    return true;}

5. 查找操作

按位查找函数直接访问数组元素。

int GetElem(SeqList* L, int n) {    return L->data[n - 1];}

三、链表

1. 存储结构

• 链表：逻辑上相邻，物理上不一定相邻。
• 每个节点存储数据和指向下一个节点的指针。

2. 实现方式

1. 不带头结点

typedef struct LNode {    int data;    struct LNode* next;} LNode, *LinkList;

2. 带头结点

typedef struct LNode {    int data;    struct LNode* next;} LNode, *LinkList;

3. 基本操作

1. 插入操作

bool ListInsert(LinkList L, int i, int e) {    if (i < 1) {        return false;    }    Node* p = L;    int j = 0;    while (p != NULL && j < i - 1) {        p = p->next;        j++;    }    if (p == NULL) {        return false;    }    InsertNextNode(p, e);    return true;}bool InsertNextNode(Node* p, int e) {    Node* s = (Node*)malloc(sizeof(Node));    if (s == NULL) {        return false;    }    s->data = e;    s->next = p->next;    p->next = s;    return true;}

2. 删除操作

bool ListDelete(LinkList L, int i, int* e) {    if (i < 1) {        return false;    }    Node* p = L;    int j = 0;    while (p != NULL && j < i - 1) {        p = p->next;        j++;    }    if (p == NULL) {        return false;    }    DeleteNode(p);    return true;}bool DeleteNode(Node* p) {    Node* q = p->next;    p->data = q->data;    p->next = q->next;    free(q);    return true;}

3. 查找操作

按位查找：

Node* GetElem(LinkList L, int i) {    if (i < 0) {        return NULL;    }    Node* p = L;    int j = 0;    while (p != NULL && j < i) {        p = p->next;        j++;    }    return p;}

按值查找：

Node* LocateNode(LinkList L, int e) {    Node* p = L->next;    while (p != NULL && p->data != e) {        p = p->next;    }    return p;}

4. 表长计算

int Length(LinkList L) {    Node* p = L->next;    int len = 0;    while (p != NULL) {        p = p->next;        len++;    }    return len;}

5. 打印链表

void PrintList(LinkList L) {    Node* p = L->next;    while (p != NULL) {        printf("%d ", p->data);        p = p->next;    }}

【总结】

链表与顺序表各有优缺点，链表的插入删除操作较为灵活，但需处理指针操作的复杂性。顺序表支持随机访问，但插入删除操作效率较低。线性表是两者的基础，理解其操作对后续学习至关重要。

转载地址：http://sqef.baihongyu.com/