专升本数据结构笔记 第二章：线性表
阿洛学长笔记 love ttz
线性表
任务一 线性表的定义和基本操作（阿洛学长）
一、线性表的定义
线性表是由n（n≥0）个类型相同的数据元素a1,a2,…,an组成的有限序列，数据元素之间是一对一的关系，记作
L＝(a1, a2, …, ai－1, ai, ai＋1, …, an)
（由n（n≥0）个类型相同的数据元素，组成的有限序列，数据元素之间是一对一的关系，为线性表）
可以理解为有序数组
二、线性表的基本操作
任务二 线性表的顺序存储结构（阿洛学长）
线性表的顺序存储是指，在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。
采用顺序存储结构的线性表称为顺序表。
一、顺序表的结构特点
假设线性表中有n个数据元素，每个元素占用k个存储单元，其中第一个数据元素a1的存储地址称为线性表的起始位置或基地址，线性表的顺序存储结构如图2-1所示。
线性表的顺序存储结构是一种随机存取的存储结构。
若已知线性表的起始位置（基地址）和表中每个数据元素所占存储单元的大小k，就可以计算出线性表中任意一个数据元素的存储地址，这种存取元素的方法称为随机存取法
顺序表的存储结构通常用一维数组来描述，用C语言实现线性表的顺序存储结构的类型定义如下：
#define c 100 //线性表的最大长度
typedef struct
{
ElemType elem [MAXSIZE]; //存储线性表中数据元素的数组
int length; //线性表的当前长度
}SeqList;
也可以这样来定义：
typedef struct
{
ElemType *elem; //线性表中数据元素的基地址
int length; //线性表的当前长度
int listsize; //当前为线性表分配的存储容量
}SeqList;
定义一个顺序表的方法有两种：
方法一：SeqList L，表示将L定义为SeqList类型的变量；
对表中数据元素进行操作应使用L.elem[i]
方法二：SeqList *L，表示将L定义为指向SeqList类型的指针。
对表中数据元素进行操作应使用L->elem[i]
二、顺序表的基本操作
1．初始化顺序表 （构造一个空的顺序表，并分配存储空间）
2．插入数据元素
3．删除数据元素
4．查找数据元素
1．初始化顺序表
初始化顺序表操作是指构造一个空的顺序表，并为其分配存储空间。
其算法描述如下：
Status InitList (SqList *L)
{ //初始化顺序表
L -> elem = (ElemType *) malloc (MAXSIZE * sizeof (ElemType));
//分配存储空间
if (! L -> elem) return OVERFLOW; //存储空间分配失败
L -> length = 0; //当前线性表长度为0
L -> listsize = LIST_MAX_SIZE; //初始化存储容量
return TRUE; }
2．插入数据元素
在n元素和m元素中插入X 总长度为k
初始位置
序列： i i+1 … k
元素： n m … k
插入X后的位置
序列： i i+1 i+2 … k+1
元素： n x m … k+1
（元素往后退1）
算法描述如下：
Status ListInsert (SqList *L, int i, ElemType e)
{int j;
if (i < 1 || i > L -> length + 1)
return FALSE; //i值不合法，出错处理
if (L -> length = L.listsize) //当前存储空间满
return OVERFLOW
for (j = L -> length – 1; j >= i - 1; j --)
L -> elem [j + 1] = L -> elem[j];
//第i个位置之后的元素依次向后移
L -> elem[i –1] = e; //将e插入到第i个位置
L -> length ++; //表长增1
return TRUE; }
n个元素移动1次，累计就n*1=n
3．删除数据元素
在n元素和m元素中删除n 总长度为k
初始位置
序列： i i+1 i+2 … k
元素： n x m … k
插入X后的位置
序列： i i+1 i+2 … k+1nc
元素：x m c… k+1
（元素往前加1）
算法描述如下：
Status ListDelete (SqList *L, int i)
{//在顺序表L中删除第i个数据元素，其中1≤i≤L->length
int j;
if (i < 1 || i > L -> length) return FALSE; //i值不合法，出错处理
for (j = i; j < L -> length; j ++)
L -> elem[j - 1] = L -> elem[j];
//第i个位置之后的元素依次向前移
L -> length --; //表长减1
return TRUE; }
n个元素移动1次，累计就n*1=n
4．查找数据元素
在顺序表中查找值为e的数据元素，并返回该元素在表中的位置。
方法：从第一个数据元素开始，依次将表中的元素与e进行比较，若相等，则返回该元素在表中的位置；否则，查找失败。
算法描述如下：
int Locate (SqList L, ElemType e)
{//在顺序表中查找值为e的数据元素，查找成功，返回该元素的位置；否则返回0
for (i = 0; i < L.length; i ++)
if (L.elem[i] == e)
return i + 1; //查找成功，返回序号
return 0; } //查找失败，返回0
该算法的时间复杂度为O(n)n
所有元素都与查找元素e进行对比了一次，n*1=n
【例2-1】一个线性表L中的数据元素按升序排列，编写一个算法，实现在线性表中插入一个数据元素item，使得线性表仍然保持升序排列。
算法如下：
void Insert (SqList L, ElemType item)
{ int i;
int j;
if (item >= L.elem[L.length - 1]) //item值大于表中最大的数据元素
L.elem[L.length] = item; //将item插入到表尾
else{ i = 0;
while (item >= L.elem[i]) //寻找item的插入位置i
i ++;
ListInsert (&L, i, item); } //将item插入到位置i
L.length ++; } //表长增1
任务三 线性表的链式存储结构 （阿洛学长）
一、单链表的结构特点
二、单链表的基本操作
三、静态链表及其基本操作
四、循环链表及其基本操作
五、双向链表及其基本操作
一、单链表的结构特点
数据域和指针域组成
二、单链表的基本操作
1．建立单链表
2．插入数据元素
3．删除数据元素
4．查找数据元素
5．求单链表的长度
1．建立单链表
LinkList *Create (LinkList *L)
{//建立一个单链表，将新结点插入表尾
Node *r, *s;
ElemType c;
int i;
*L = (LinkList) malloc (sizeof(Node)); //为头结点分配存储空间
r = *L; //r初值指向头结点
for (i = 1; i <= n; i ++)
{READ (c); //获取一个数据元素
s = (LinkList) malloc (sizeof(Node)); //生成一个新结点
s -> data = c; //将要插入数据元素的值赋给新结点的数据域
s -> next = NULL; //链表末尾结点指针域为空
r -> next = s; //将新结点插入到当前链表的表尾上
r = s; } //r始终指向链表的当前表尾
return L; }
该算法的时间复杂度为O(n)
2．插入数据元素
Status ListInsert (LinkList *L, int i, ElemType e)
{//在单链表L中第i个位置插入一个数据元素e
Node *p, *s;
int j = 0;
p = *L;
while (p != NULL && j < i - 1)
{//找到第i－1个结点
p = p -> next;
j ++; }
if (j != i - 1) return FALSE; //未找到插入位置，出错处理
s = (LinkList) malloc (sizeof (Node));//生成新结点
s -> data = e; //将要插入数据元素的值赋给新结点的数据域
s -> next = p-> next; //插入新结点
p -> next = s;
return TRUE; }
该算法的时间复杂度为O(n)
3．删除数据元素
Status ListDelete (LinkList *L, int i, ElemType *e)
{//删除单链表L中的第i个结点，并用e返回被删除的元素
Node *p, *r;
int j = 0;
p = *L;
while (p -> next != NULL && j < i - 1)
{//找到第i－1个结点
p = p -> next;
j ++; }
if (j != i - 1) return FALSE; //未找到要删除的结点，出错处理
r = p -> next; //指针r指向要删除的结点
p -> next = p -> next -> next; //删除结点r
*e = r -> data; //将删除结点的值保存在e中
free (r); //释放被删除结点所占的内存空间
return TRUE; }
该算法的时间复杂度为O(n)
4．查找数据元素
LinkList GetElem (LinkList L, int i)
{//在单链表L中查找第i个结点，并返回该结点的指针
Node *p;
int j = 0;
p = L; //指针p初值指向头结点
while ((p -> next != NULL) && (j < i))
{ //逐个结点扫描
p = p -> next; //指向下一个结点
j ++; } //已扫描过的结点数
return p; } //返回第i个结点
算法的时间复杂度为O(n)
（2）按值查找
查找单链表中值为e的结点，算法描述如下
LinkList Locate (LinkList L, ElemType e)
{ //在单链表中查找值为e的结点，并返回该结点的指针
Node *p;
p = L -> next; //指针p初值指向表中第1个结点
while ((p != NULL) && (p -> data != e))
//从表中第1个结点开始逐个比较
p = p -> next;
return p; } //返回值为e的结点
5．求单链表的长度
int ListLength (LinkList L)
{ //返回单链表的长度
Node *p;
int j = 0; //用来保存单链表的长度
p = L -> next; //指针p初值指向表中第1个结点
while (p != NULL) //用指针p依次指向表中各个结点
{ p = p -> next;
j ++; }
return j; } //返回单链表的长度
三、静态链表及其基本操作
1．初始化静态链表
2．分配结点
3．回收结点
1．初始化静态链表
2．分配结点
3．回收结点
四、循环链表及其基本操作
将表中最后一个结点的指针域指向头结点，从而形成一个首尾相接的链表，称为循环链表。
所有结点被链接到一个环上，从循环链表中任一结点出发均可找到表中其他结点。
五、双向链表及其基本操作
1．插入数据元素
2．删除数据元素
1．插入数据元素
算法描述如下：
Status DListInsert (DLinkList *L,int i, ElemType e)
{ //在双向循环链表L中第i个位置插入一个数据元素e
DNode *s, *p
if (! (p = GetElem (L, i))) return FALSE; //插入位置不合法
s = (DLinkList) malloc (sizeof (DNode) //生成新结点
if (! s) return FALSE;
s -> data = e; //将e赋给新结点的数据域
s -> prior = p -> prior; //新结点的前驱指向p结点的前驱
p -> prior -> next = s; //p结点前驱的后继指向新结点
s -> next = p; //新结点的后继指向p结点
p -> prior = s; //p结点的前驱指向新结点
return TRUE; }
2．删除数据元素
算法描述如下：
Status DListDelete (DLinkList *L,int i, ElemType *e)
{//删除双向链表L中的第i个结点
DNode *p
if (! (p = GetElem (L, i))) return FALSE;//i值不合法
*e = p -> data; //将要删除结点的值赋给e
p -> prior -> next = p -> next; //要删除结点前驱的后继指向其后继
p -> next -> prior = p -> prior; //要删除结点后继的前驱指向其前驱
free (p); //释放p结点
return TRUE;
}