作者:whisper
链接:http://proprogrammar.com:443/article/dataStructure_chapter1
声明:请尊重原作者的劳动,如需转载请注明出处
说明:该章主要讲了线性表的定义和基本操作,线性表的实现(顺序存储,链式存储),线性表的应用(顺序表,单链表,循环链表,双向链表,静态链表)
四个名词:前插,后插,头插,尾插
线性表的逻辑结构
线性表是一种最简单的线性结构
线性结构的基本特征:线性结构是一个数据元素的有序(次序)集
(1)集合中必存在唯一的一个“第一元素”;
(3)除最后元素在外,均有唯一的后继;
抽象数据类型线性表的定义如下:
ADT List {
数据对象:
D={ aᵢ | aᵢ ∈ElemSet, i=1,2,...,n, n≥0 } { 称 n 为线性表的表长; 称 n=0 时的线性表为空表。}
数据关系:
R1={ |aᵢ₋₁ ,aᵢ∈D, i=2,...,n } { 设线性表为 (a1,a2, . . . ,ai,. . . ,an), 称 i 为 ai 在线性表中的位序。}
基本操作:
结构初始化操作;结构销毁操作;引用型操作;加工型操作
} ADT List
初始化操作 InitList( &L )
操作结果:构造一个空的线性表 L
结构销毁操作 DestroyList( &L )
初始条件:线性表 L 已存在
操作结果:销毁线性表 L。
引用型操作:
ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ) ,NextElem( L, cur_e, &next_e )、GetElem( L, i, &e )、LocateElem( L, e, compare( ) )
ListTraverse(L, visit( ))(遍历线性表)
初始条件:线性表 L 已存在。Visit( ) 为某个访问函数。
操作结果:依次对 L 中每个元素调用函数 visit( )。一旦 visit( )失败,则操作失败。
注:引用型操作不改变线性表本身,没有引用操作符(&)
加工型操作:
ClearList( &L )、PutElem( &L, i, &e )、ListInsert( &L, i, e )、ListDelete(&L, i, &e)
注:加工型操作会改变线性表本身,有引用操作符(&)
利用上述定义的线性表类型可以实现其它更复杂的操作
上述问题可演绎为:
要求对线性表作如下操作:扩大线性表 LA,将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。
例 1 操作步骤:
(1)从线性表 LB 中依次察看每个数据元素;
GetElem(LB, i)→e
(2)依值在线性表 LA 中进行查访;
LocateElem(LA, e, equal( ))
(3)若不存在,则插入之。
ListInsert(LA, n+1, e)( n 表示线性表 LA 当前长度)
void union(List &La, List Lb) {
La_len = ListLength(La); //求线性表的长度
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb, i, e);//取 Lb 第 i 个数据元素赋给 e
if (!LocateElem(La, e, equal( )))
ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素,则插入之
}//for
}//union
有序表
若线性表中的数据元素相互之间可以比较,并且数据元素在表中依值非递减或非递增有序排列,即 aᵢ≥aᵢ₋₁ 或 aᵢ≤aᵢ₋₁(i = 2,3,…, n),则称该为有序表。
例 2:归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB,求得有序表 LC 也具有同样特性。
设 La = (a1, …, ai, …, an),
Lb = (b1, …, bj, …, bm)
求得 Lc = (c1, …, ck, …, cm+n)且已由(a1, …, ai-1)和(b1, …,bj-1)归并得 (c1, …, ck-1) ,k = 1, 2, …, m+n
则
基本操作
(1)初始化 LC 为空表;
(2)分别从 LA 和 LB 中取得当前元素 ai 和 bj;
(3)若 ai≤bj,则将 ai 插入到 LC 中,否则将 bj 插入到 LC 中;
(4)重复 2 和 3 两步,直至 LA 或 LB 中元素被取完为止;
(5)将 LA 表或 LB 表中剩余元素复制插入到 LC 表中。
void MergeList(List La, List Lb, List &Lc) { // 将非递减有序表 La 和 Lb 归并为 Lc
InitList(Lc); // 构造空的线性表 Lc
i = j = 1; k = 0; aj; bj;// i = j = 1, k = 0
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)){ // La 和 Lb 均不空
GetElem(La, i, ai);
GetElem(Lb, j, bj);
if (ai <= bj) { // 将 ai 插入到 Lc 中
ListInsert(Lc, ++k, ai); ++i;
}else { // 将 bj 插入到 Lc 中
ListInsert(Lc, ++k, bj); ++j;
}
}
while (i <= La_len) { // 当 La 不空时
GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai);
} // 插入 La 表中剩余元素
while (j <= Lb_len) { // 当 Lb 不空时
GetElem(Lb, j++, bj);
ListInsert(Lc, ++k, bj);
} // 插入 Lb 表中剩余元素
} // merge_list
线性表的顺序存储结构
顺序映象
以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系最简单的一种顺序映象方法是:令 y 的存储位置和 x 的存储位置相邻。 用一组地址连续的存储单元依次存放线性表中的数据元素。
以“存储位置相邻”表示有序对,aᵢ> 即:LOC(aᵢ) = LOC(aᵢ₋₁) + C(C为一个数据元素所占存储量)
所有数据元素的存储位置均取决于第一个数据元素的存储位置。
LOC(aᵢ) = LOC(a₁) + (i-1)×C (LOC(a1)为基地址)
注意:
存取结构:与存储结构是两个不同的概念。 存取结构是在一个数据结构上对查找操作的时间性能的一种描述。通常有两种存取结构:随机存取结构和顺序存取结构。
随机存取结构是指在一个数据结构上进行查找的时间性能是 O(1),即查找任意一个数据元素的时间是相等的,均为常数时间,例如顺序表是一种随机存取结构。
顺序存取结构是指在一个数据结构上进行查找的时间性能是 O(n),即查找一个数据元素的时间复杂度是线性的,与该元素在结构中的位置有关,例如单链表是一种顺序存取结构。
顺序映象的 C 语言描述
线性表的静态分配顺序存储结构:
#define LISTSIZE 100 //存储空间最大分配量
typedef struct{
ElemType elem[LISTSIZE];
int length; //当前长度
}Sqlist;
在线性表的静态分配顺序存储结构中,线性表的最多数据元素个数为 LISTSIZE,元素数量不能随意增加,这是以数组方式描述线性表的缺点。
为了实现线性表最大存储数据元素数可随意变化,可以使用一个动态分配的数组来取代上面的固定长度数组,如下描述。
线性表的动态分配顺序存储结构:
#define LIST_INIT_SIZE 100 //初始分配量
#define LISTINCREMENT 10 //分配增量
typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量
// (以 sizeof(ElemType)为单位)
} SqList; // 俗称 顺序表
线性表的基本操作在顺序表中的实现
InitList(&L); // 结构初始化
LocateElem(L, e, compare()) ; // 查找
ListInsert(&L, i, e);// 插入元素
ListDelete(&L, i) ; // 删除元素
(1)线性表操作InitList(&L)的实现:构造一个空表,这对表是一个加工型的运算,因此,将 L设为引用参数,首先动态分配存储空间,然后,将 length 置为 0,
表示表中没有数据元素。
int InitList (SqList &L){
L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit (OVERFLOW); //存储分配失败
L.length=0;
L.listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}
线性表中的按值查找是指在线性表中查找与给定值 x 相等的数据元素。
顺序表中完成该运算最简单的方法是:从第一个元素 a1 起依次和 x 比较,直到找到一个与 x 相等的数据元素,则返回它在顺序表中的存储下标或序号(二者差 1);或者查遍整个表都没有找到与 x 相等的元素,返回 ERROR。
int LocateElem (SqList L, ElemType x){
i=0;
while(i<=L.length-1 && L.elem[i]!= x)
i++;
if (i>L.length-1) return ERROR;
else return i; //返回的是存储位置
}
本算法的主要运算是比较,显然比较的次数与 x 在表中的位置有关,也与表长有关。当 a1=x 时,比较 1 次成功,当 an=x 时比较 n 次成功,按值查找的平均比较次数为(n+1)/2,时间性能为 O(n)。
首先分析:插入元素时,线性表的逻辑结构发生什么变化? (a1, …, ai-1, ai, …, an) 改变为(a1, …, ai-1, e, ai, …, an)
Status ListInsert_Sq(SqList &L, int i, ElemType e) {// 在顺序表 L 的第 i 个元素之前插入新的元素 e,i 的合法范围为 1≤i≤L.length+1
if (i < 1 || i > L.length+1)
return ERROR; // 插入位置不合法
if (L.length >= L.listsize)
return OVERFLOW; // 当前存储空间已满
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入 e
++L.length; // 表长增 1
return OK;
} // ListInsert_Sq
算法时间复杂度为: O( ListLength(L) )
考虑移动元素的平均情况:
假设在第 i 个元素之前插入的概率为 pi, 则在长度为 n 的线性表中插入一个元素所需移动元素次数的期望值为:
若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:
例如:
ListInsert_Sq(L, 5, 66)
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;// 从后向前依次向后移动一位
(4)线性表操作ListDelete(&L, i, &e)的实现:
(a1, …, ai-1, ai, ai+1, …, an) 改变为(a1, …, ai-1, ai+1, …, an)
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法
p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移
--L.length; // 表长减 1
return OK;
} // ListDelete_Sq
算法时间复杂度为: O( ListLength(L))
考虑移动元素的平均情况:
若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:
例如:
ListDelete_Sq(L, 5, e)
p = &(L.elem[i-1]);
q = L.elem+L.length-1;
for (++p; p <= q; ++p) *(p-1) = *p;//从前向后依次左移一位
线性表的链式存储结构
(一)单链表
概念: 用一组地址任意的存储单元存放线性表中的数据元素。
以元素(数据元素的映象) + 指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)
以“结点的序列”表示线性表——称作链表。
以线性表中第一个数据元素 a₁ 的存储地址作为线性表的地址,称作线性表的头指针。
有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。
头指针:
2)头指针具有标识作用,所以常用头指针冠以链表的名字;
头结点:
2)有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了;
结点和单链表的 C 语言描述
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;
单链表操作的实现
GetElem(L, i, e) // 取第 i 个数据元素
ListInsert(&L, i, e) // 插入数据元素
ListDelete(&L, i, e) // 删除数据元素
ClearList(&L) // 重新置为一个空表
CreateList(&L, n) // 生成含 n 个数据元素的链表
(1)线性表的操作 GetElem(L, i, &e)
在单链表中的实现:
单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j和 i。令指针 p 始终指向线性表中第 j 个数据元素。
Status GetElem_L(LinkList L, int i, ElemType &e) {// L 是带头结点链表的头指针,e 返回第 i 个元素
p = L->next; j = 1; // p 指向第 1 个结点,j 为计数器
while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找,直到 p 指向第 i 个元素或 p 为空
if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;
} // GetElem_L
算法时间复杂度为: O(ListLength(L))
(2)线性表的操作ListInsert(&L, i, e)
在单链表中的实现:有序对 <ai-1, ai>改变为 <ai-1, e> 和<e, ai>
可见,在链表中插入结点只需要修改指针。但同时,若要在第 i 个结点之前插入元素,修改的是第 i-1 个结点的指针。
Status ListInsert_L(LinkList &L, int i, ElemType e) {
// L 为带头结点的单链表的头指针,本算法
// 在链表中第 i 个结点之前插入新的元素 e
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于 1
s = new LNode; // 生成新结点
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
} // LinstInsert_L
前插结点:设p指向链表中某结点,s指向待插入的值为 x 的新结点,将*s 插入到*p 的前面,与后插不同的是:首先要找到*p 的前驱*q,然后再完成在*q 之后插入*s,设单链表头指针为 L。
操作如下:
while (q->next!=p) q=q->next; //找*p 的直接前驱
③q->next=s;
前插操作因为要找*p 的前驱,时间性能为 O(n)。
改进的前插:其实前插操作可以用后插操作来实现,即仍然可以将 *s 插入到 *p 的后面,然后将p->data 与 s->data 交换即可。这样即满足了逻辑关系,也能使得时间复杂度为 O(1)。
(3)线性表的操作 ListDelete (&L, i, &e)
在链表中的实现: 有序对<ai-1, ai> 和 <ai, ai+1> 改变为 <ai-1, ai+1>
在单链表中删除第 i 个结点的基本操作为:找到线性表中第 i-1 个结点,修改其指向后继的指针。
q = p->next; p->next = q->next;
e = q->data; delete(q);
Status ListDelete_L(LinkList &L, int i, ElemType &e) {
// 删除以 L 为头指针(带头结点)单链表中第 i 个结点
p = L; j = 0;
while(p->next && j < i-1) {p = p->next; ++j; } // 寻找第 i 个结点,并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; delete(q);
return OK;
} // ListDelete_L
算法的时间复杂度为: O(ListLength(L))
(4)操作ClearList(&L)
在链表中的实现:
void ClearList(&L) {
// 将单链表重新置为一个空表
while (L->next) {
p=L->next; L->next=p->next;
delete(p);
}
} // ClearList
算法时间复杂度:O(ListLength(L))
(5)如何从线性表得到单链表? 头插法,尾插法
链表是一个动态的结构,它不需要予分配空间,因此生成链表的过程是一个结点“逐个插入” 的过程。
头插法:逆位序输入 n 个数据元素的值,建立带头结点的单链表。
操作步骤:
一、建立一个“空表”;
三、输入数据元素 an-1,建立结点并插入;
void CreateList_L(LinkList &L, int n) {
// 头插法建立带头结点的单链表
L = new LNode; L->next = NULL; // 先建立一个带头结点的单链表
for (i = n; i > 0; --i) {
p = new LNode;
scanf(&p->data); // 输入元素值
p->next = L->next; L->next = p; // 插入
}
} // CreateList_L
注:头插法可以实现倒序的效果
算法的时间复杂度为: O(Listlength(L))
尾插法:正序输入 n 个数据元素的值,建立不带头结点的单链表。
LinkList Create_LinkList2( ){
LinkList L=NULL; LNode *s,*r=NULL;//r尾指针,s活动指针
int x; scanf("%d",&x); //设数据元素的类型为 int
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode)); s->data=x;
if (L==NULL) L=s; //第一个结点的处理
else r->next=s; //其它结点的处理
r=s; //r 指向新的尾结点
scanf("%d",&x);
}
if ( r!=NULL) r->next=NULL; //非空表最后结点的指针域为空
return L;
}
尾插法:建立带头结点的单链表。
LinkList Create_LinkList2( ){
LinkList L=(LNode *)malloc(sizeof(LNode));
L->next=NULL; LNode *s,*r=L; //空表,r尾指针,s活动指针
int x; scanf("%d",&x);
while (x!=flag) {//flag结束标志
s=(LNode *)malloc(sizeof(LNode)); s->data=x;
r->next=s;
r=s; //r 指向新的尾结点
scanf("%d",&x);
}
r->next=NULL;
return L;
}
头结点两个优点:
a、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致,无需进行特殊处理;
(二)其它形式的链表
循环链表
最后一个结点的指针域的指针又指回第一个结点的链表。
特点:
(1)对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点开始遍历整个链表。
(3)在做链表合并和分裂时,如果不是必须从链表头开始,则可以直接在链表指针处合并,时间复杂度可达 O(1)。
双向链表
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior; // 指向前驱的指针域
struct DuLNode *next; // 指向后继的指针域
} DuLNode, *DuLinkList;
双向循环链表
“查询” 和单链表相同;
“插入” 和“删除”时需要同时修改两个方向上的指针。
插入:
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;
注:已知p和s,注意不要丢失掉p的直接后继的信息
删除:
p->next = p->next->next;
p->next->prior = p;
特点:
(1)从某个结点出发到其直接前趋结点或直接后继结点,时间复杂度均为 O(1)。
(3)如果是双向循环链表,修改指针要同时考虑在前趋环链和后继环链上的修改。
(4)某个结点的直接前趋的直接后继,或它的直接后继的直接前趋,即为该结点本身。
静态链表
线性表的静态单链表存储结构:
#define MAXSIZE 1000
typedef struct {
ElemType data;
int next;
}component,SLinkList[MAXSIZE];
静态链表适用于不支持“指针”的高级语言,或者最大元素数固定但插入、删除操作频繁的链表应用中。有关基于静态链表上的线性表的操作基本与动态链表相同,除了一些描述方法有些区别外,算法思路是相同的。
特点:
(2)修改指针域即可完成插入和删除操作,不需要移动数据元素,但是也不能随机访问静态链表中的元素;
(3)一次性分配所有存储空间,插入、删除时无需再向操作系统申请或释放空间,但也限制了最大表长。
顺序表和链表的比较
顺序表和链表各有优缺点。
顺序存储优点:
(2)不用为表示结点间的逻辑关系而增加额外的存储开销。
缺点:
(2)需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。
在实际中怎样选取存储结构
顺序表在程序执行之前必须明确规定它的存储规模,也就是说事先对“MAXSIZE”要有合适的设定,过大造成浪费,过小造成溢出。可见对线性表的长度或存储规模难以估计时,不宜采用顺序表;链表不用事先估计存储规模,但链表的存储密度较低。显然链式存储结构的存储密度(数据长度/节点长度)是小于1的。
在顺序表中按序号访问 aᵢ 的时间性能时 O(1),而链表中按序号访问的时间性能O(n),所以如果经常做的运算是按序号访问数据元素,显然顺序表优于链表;而在顺序表中做插入、删除时平均移动表中一半的元素,当数据元素的信息量较大且表较长时,这一点是不应忽视的;在链表中作插入、删除,虽然也要找插入位置,但操作主要是比较操作,从这个角度考虑显然后者优于前者。
顺序表容易实现,任何高级语言中都有数组类型,链表的操作是基于指针的,相对来讲前者简单些,也是用户考虑的一个因素。
本章学习重点
1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
亲爱的读者:有时间可以点赞评论一下
全部评论