线性表（从数据结构的三要素出发）

逻辑结构

线性表是具有相同数据类型的$n(n\ge 0)$个数据元素的有限序列，其中$n$为表长，当$n=0$时线性表是一个空表。若用$L$命名线性表，则其一般表示为

$$L=\left(a_1,a_2,\cdots ,a_i,a_{i+1},\cdots ,a_n\right)$$

式中，$a_1$是唯一的“第一个”数据元素，又称表头元素；$a_n$是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表有以下特性：

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

存储结构

顺序存储

它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置，第i个元素的存储位置后面紧接着存储的是第$i+1$个元素，称$i$为元素$a_i$在顺序表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

假设顺序表L存储的起始位置为LOC(A),sizeof(ElemType)是每个数据元素所占用存储空间的大小。

typedef struct {ElemType data[Maxsize];int length;
} SqList;

存在的问题：

• 需要大量连续的存储空间
• 插入删除时，时间复杂度高
• 顺序表一旦确定大小，后续将不可扩充

链式存储

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表

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

存在的问题：

• 失去了顺序存储中随机存取的特性
• 求表长的时间复杂度高
• 访问前驱结点的时间复杂度高

双链表

在单链表中要访问某个结点的前驱(插入、删除操作时),只能从头开始遍历，访问前驱的时间复杂度为 $O(n)$。为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next,分别指向其直接前驱和直接后继。表头结点的 prior域和尾结点的 next 域都是 NULL。

typedef struct DNode {ElemType data;struct DNode *next, prior;
} DNode, *DLinkList;

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL,而改为指向头结点，从而整个链表形成一个环。

循环双链表

由循环单链表的定义不难推出循环双链表。不同的是，在循环双链表中，头结点的prior指针还要指向表尾结点。

静态链表

静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data 和指针域 next,与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标),又称游标。

typedef struct {ElemType data;int next;
} SLinkList[Maxsize];

数据的操作

顺序结构

初始化

void InitList(SqList &L)
{L.length = 0;
}

判满

bool isFull(SqList L)
{if (L.length == Maxsize) return true;return false;
}

判空

bool isEmpty(SqList L)
{if (L.length == 0) return true;return false;
}

插入操作

bool ListInsert(SqList &L, int i, ElemType e)
{if (i < 1 || i > L.length + 1)				// 无效的插入位置return false;if (isFull(L)) 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(SqList &L, int i, ElemType e)
{if (i < 1 || i > L.length + 1)				// 无效的删除位置return false;if (isEmpty(L)) 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(SqList L, ElemType e)
{for (int i = 0; i < L.length; i ++ )if (L.data[i] == e)return i + 1;return -1;
}

链式结构

单链表

初始化

void InitList(LinkList &L)
{L = (LNode *) malloc (sizeof(LNode));L->next = NULL;
}

求表长

int Length(LinkList L)
{LNode *p = L->next;int cnt = 0;			// 记录长度while (p){cnt ++ ;p = p->next;}return cnt;
}

按序号查找结点

LNode * GetElem(LinkList L, int i)
{LNode *p = L->next;int cnt = 0;						// 记录当前遍历到第几个结点了while (p){cnt ++ ;if (cnt == i)return p;p = p->next;}return NULL;
}

按值查找

LNode * LocateElem(LinkList L, ElemType e)
{LNode *p = L->next;while (p){if (p->data == e)return p;p = p->next;}return NULL;
}

插入结点

bool ListInsert(LinkList &L, int i, ElemType e)
{LNode *p = L;int j = 0;while (p && j < i - 1){p = p->next;j ++ ;}if (p == NULL) return false;		// 位置不合法LNode *s = (LNode *) malloc (sizeof(LNode));/*插入结点*/s->data = e;s->next = p->next;p->next = s;return true;
}

删除结点

bool ListDelete(LinkList &L, int i, ElemType e)
{LNode *p = L;int j = 0;while (p && j < i - 1){p = p->next;j ++ ;}if (p == NULL || p->next == NULL) return false;		// 位置不合法LNode *q = p->next;/*删除结点q*/e = q->data;p->next = q->next;free(q);return true;
}

采用头插法建立链表

LinkList List_HeadInsert(LinkList &L)
{LNode *s;int x;L = (LNode *) malloc (sizeof(LNode));L->next = NULL;scanf("%d", &x);while (x != 9999)		// 输入9999停止{s = (LNode *) malloc (sizeof(LNode));s -> data = x;s->next = L->next;L->next = s;scanf("%d", &x);}return L;
}

采用尾插法建立链表

LinkList List_TailInsert(LinkList &L)
{int x;L = (LNode *) malloc (sizeof(LNode));LNode *s, *r = L;		// r是表尾指针scanf("%d", &x);while (x != 9999)		// 输入9999停止{s = (LNode *) malloc (sizeof(LNode));s -> data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;return L;
}

双链表

初始化

void InitList(DLinkList &L)
{L = (DNode *) malloc (sizeof(DNode));L->next = L->prior = NULL;
}

插入结点

bool ListInsert(DLinkList &L, int i, ElemType e)
{DNode *p = L;int j = 0;while (p && j < i - 1){p = p->next;j ++ ;}if (p == NULL) return false;		// 位置不合法DNode *s = (DNode *) malloc (sizeof(DNode));/*插入结点*/s->data = e;s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return true;
}

删除结点

bool ListDelete(DinkList &L, int i, ElemType e)
{DNode *p = L;int j = 0;while (p && j < i - 1){p = p->next;j ++ ;}if (p == NULL || p->next == NULL) return false;		// 位置不合法DNode *q = p->next;/*删除结点q*/e = q->data;p->next = q->next;q->next->prior = p;free(q);return true;
}