1、简介
- 线性表的数据对象集合为 {a1，a2，.....，an }，每个元素的类型均为 DataType
- 其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除最后一个元素 an 外，每一个元素有且只有一个直接后继元素
- 数据元素之间的关系是一对一的关系
2、基本操作
InitList(*L) 初始化操作，建立一个空的线性表L
ListEmpty(L) 若线性表为空，返回 true，否则返回 false
ClearList(*L) 将线性表清空
GetElem(L, i, *e) 将线性表 L 中的第 i 个位置元素值返回给 e
LocateElem(L, e) 在线性表 L 中查找给定值 e 相等的元素，如果查找成功，返回该元素在表中序号表示成功；
否则，返回 0 表示失败
ListInsert(*L, i, e) 在线性表 L 中的第 i 个位置插入新元素 e
ListDelete(*L, i, *e) 删除线性表 L 中第 i 个位置元素，并用 e 返回其值
ListLength(L) 返回线性表 L 中的元素个数
3、存储结构
3.1、顺序存储结构
-
用一段地址连续的存储单元依次存储线性表的数据元素 (用一维数组来实现)
线性表顺序存储结构代码如下
#define MAXSIZE 20 // 存储空间初始分配量
typedef int ElemType; // ElemType 类型根据实际情况而定，这里假设为 int
typedef struct{
ElemType data[MAXSIZE]; // 数组存储数据元素，最大值 MAXSIZE
int length; // 线性表当前长度
}SqList;
- 获取元素
将线性表 L 中的第 i 个位置元素值返回给 e
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
- 插入元素
在线性表 L 中的第 i 个位置插入新元素 e
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length == MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i<1 || i > L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i <= L->length) /* 若插入数据位置不在表尾 */
{
for(k = L-> length; k >= i;k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k] = L->data[k - 1];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}
- 删除元素
删除线性表 L 中第 i 个位置元素，并用 e 返回其值
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length == 0) /* 线性表为空 */
return ERROR;
if (i<1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*e = L->data[i-1];
if (i < L->length) /* 如果删除不是最后位置 */
{
for(k = i-1; k < L->length-1; k++)/* 将删除位置后继元素前移 */
L->data[k]=L->data[k+1];
}
L->length--;
return OK;
}
- 总结
优点：１、无须为表示表中元素之间的逻辑关系而增加额外的存储空间
2、可以快速地存取表中任一位置的元素
缺点：１、插入和删除操作需要移动大量的元素
２、当线性表长度变化较大时，难以确定存储空间的容量
３、造成存储空间的 "碎片"
3.2、链式存储结构
-
如下图所示，如同一条链子一样存储信息
- 为了表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。
我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。
指针域中存储的信息称为指针或链。这两部分信息组成数据元素 a1 的存储映像，称为节点 (Node)
- 头指针与头结点的异同
头指针：
1、头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
2、头指针具有标识作用，所以常用头指针冠以链表的名字
头结点：
1、头结点是为了操作统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)
2、有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
3、头结点不一定是链表必须要素 - 单链表存储结构
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
- 单链表的读取
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 声明一结点 p */
p = L->next; /* 让 p 指向链表 L 的第一个结点 */
j = 1; /* j 为计数器 */
while (p && j<i) /* p 不为空或者计数器 j 还没有等于 i 时，循环继续 */
{
p = p->next; /* 让 p 指向下一个结点 */
++j;
}
if ( !p || j>i )
return ERROR; /* 第 i 个元素不存在 */
*e = p->data; /* 取第 i 个元素的数据 */
return OK;
}
- 单链表的插入
/* 初始条件：顺序线性表 L 已存在,1 ≤ i ≤ ListLength(L) */
/* 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i) /* 寻找第i个结点 */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* 第i个元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */
s->data = e;
s->next = p->next; /* 将p的后继结点赋值给s的后继 */
p->next = s; /* 将s赋值给p的后继 */
return OK;
}
- 单链表的删除
/* 初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L) */
/* 操作结果：删除L的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while (p->next && j < i) /* 遍历寻找第 i 个元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* 第i个元素不存在 */
q = p->next;
p->next = q->next; /* 将q的后继赋值给p的后继 */
*e = q->data; /* 将q结点中的数据给e */
free(q); /* 让系统回收此结点，释放内存 */
return OK;
}
- 单链表的整表创建
头插法
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; /* 先建立一个带头结点的单链表 */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */
p->data = rand()%100+1; /* 随机生成100以内的数字 */
p->next = (*L)->next;
(*L)->next = p; /* 插入到表头 */
}
}
尾插法
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); /* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
r=*L; /* r为指向尾部的结点 */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */
p->data = rand()%100+1; /* 随机生成100以内的数字 */
r->next=p; /* 将表尾终端结点的指针指向新结点 */
r = p; /* 将当前的新结点定义为表尾终端结点 */
}
r->next = NULL; /* 表示当前链表结束 */
}
- 单链表的整表删除
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 头结点指针域为空 */
return OK;
}
- 单链表结构与顺序存储结构优缺点
存储分配方式: 1、顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
2、单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能: 1、查找: 顺序存储结构O(1)； 单链表O(n)
2、插入和删除: 顺序存储结构需要平均移动表长一半的元素，时间O(n)；
单链表在找出某位置的指针后，插入和删除时间仅为O(1)
空间性能: 1、顺序存储结构需要预分配存储空间，分大了，浪费；分小了，易发生浪费
2、单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
- 经验性结论
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
若需要频繁插入和删除时，宜采用单链表结构
4、静态链表
用数组来代替指针，来描述单链表。
我们把这种用数组描述的链表叫做静态链表
优点: 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点: 没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性
5、循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
6、双向链表
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
线性表结构图解
