线性表 (Linear List)
1. 概述
线性表(Linear List)是一种最基本、最常用的数据结构。它是由同类型数据元素构成的有限序列。根据存储方式的不同,线性表可以分为顺序表(顺序存储)和链表(链式存储)。
2. 线性表的定义
线性表是由 n 个元素构成的有序序列。通常表示为:
[ L = {a_1, a_2, a_3, \ldots, a_n} ]
其中:
- ( L ) 是线性表的名字。
- ( a_i ) 表示线性表中的第 ( i ) 个元素。
- ( n ) 表示线性表中的元素个数。
3. 线性表的类型
线性表按存储结构分为两种类型:
- 顺序表(Sequential List):使用一段连续的存储单元依次存放线性表的各个元素。
- 链表(Linked List):使用一组任意的存储单元存放线性表的各个元素,这些存储单元可以是连续的,也可以是不连续的。
4. 顺序表
4.1 顺序表的定义
顺序表是一种线性表,其数据元素按顺序存储在一块连续的内存空间中。
4.2 顺序表的基本操作
初始化顺序表
#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; void InitList(SeqList *L) { L->length = 0; }
插入元素
bool ListInsert(SeqList *L, int i, int e) { if (i < 1 || i > L->length + 1) return false; if (L->length == MAXSIZE) return false; for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j-1]; } L->data[i-1] = e; L->length++; return true; }
删除元素
bool ListDelete(SeqList *L, int i, int *e) { if (i < 1 || i > L->length) return false; *e = L->data[i-1]; for (int j = i; j < L->length; j++) { L->data[j-1] = L->data[j]; } L->length--; return true; }
查找元素
int LocateElem(SeqList L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) { return i + 1; } } return 0; }
5. 链表
5.1 链表的定义
链表是一种线性表,其数据元素的存储单元可以是非连续的,通过指针链接各个元素。
5.2 链表的基本操作
定义单链表节点结构
typedef struct Node { int data; struct Node *next; } Node, *LinkList;
初始化链表
void InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) exit(1); (*L)->next = NULL; }
插入元素
bool ListInsert(LinkList L, int i, int e) { LinkList p = L; int j = 0; while (p && j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) return false; LinkList s = (LinkList)malloc(sizeof(Node)); s->data = e; s->next = p->next; p->next = s; return true; }
删除元素
bool ListDelete(LinkList L, int i, int *e) { LinkList p = L; int j = 0; while (p->next && j < i - 1) { p = p->next; j++; } if (!(p->next) || j > i - 1) return false; LinkList q = p->next; p->next = q->next; *e = q->data; free(q); return true; }
查找元素
LinkList GetElem(LinkList L, int i) { LinkList p = L->next; int j = 1; while (p && j < i) { p = p->next; j++; } if (!p || j > i) return NULL; return p; }
6. 线性表的应用
线性表在许多领域有广泛应用,例如:
- 存储有序数据
- 实现栈和队列
- 实现字符串处理
- 实现其他复杂数据结构的基础
线性表作为数据结构的基础,其理解和应用对编程和算法设计非常重要。以上内容涵盖了线性表的基本概念、类型及其常见操作,希望对你有所帮助。
评论