《数据结构》课程教学资源（讲稿）第2章 线性表

第2章线性表2.1线性表的基本概念2.1.1线性表的定义线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。线性表的一般表示为(al.a2....ai.ai+1.....an)其中al为第一个元素，又称做表头元素，a2为第二个元素，an为最后一个元素，又称做表尾元2.1.2线性表的运算线性表的基本运算如下(1）初始化线性表InitList(&L)：构造一个空的线性表L。(2）销毁线性表DestroyList(&L):释放线性表L占用的内存空间。(3）判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。(4）求线性表的长度ListLength(L)：返回L中元素个数。(5)输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))个元素的值。(7）定位查找LocateElem(L,e)：返回L中第1个值域与e相等的位序。若这样的元素不存在则返回值为0。(8)插入数据元素Listlnsert(&L,,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。(9)删除数据元素ListDelete(&L,i,&e)：删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。2.2线性表的顺序存储2.2.1线性表的顺序存储一顺序表2.2.2顺序表基本运算的实现2.2.1线性表的顺序存储一顺序表线性表的顺序存储结构就是：把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。这样线性表中第一在定义一个线性表的顺序存储类型时需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用data[MaxSize]表示,长度整型变量用length表示,并采用结构体类型表示则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下：typedef structElemType data[MaxSize];int length; SqList,/*顺序表类型*其中,data成员存放元素,length成员存放线性表的实际长度。说明：由于C/C++中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。2.2.2顺序表基本运算的实现17

17 第 2 章 线性表 2.1 线性表的基本概念 2.1.1 线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线 性表的长度,用 n 表示,n≥0。 当 n=0 时,表示线性表是一个空表,即表中不包含任何元素。设序列中第 i(i 表示位序) 个元素为 ai(1≤i≤n)。 线性表的一般表示为: (a1,a2,.ai,ai+1,.,an) 其中 a1 为第一个元素,又称做表头元素,a2 为第二个元素,an 为最后一个元素,又称做表尾元 2.1.2 线性表的运算 线性表的基本运算如下: (1) 初始化线性表 InitList(&L):构造一个空的线性表 L。 (2) 销毁线性表 DestroyList(&L):释放线性表 L 占用的内存空间。 (3) 判线性表是否为空表 ListEmpty(L):若 L 为空表,则返回真,否则返回假。 (4) 求线性表的长度 ListLength(L):返回 L 中元素个数。 (5) 输出线性表 DispList(L):当线性表 L 不为空时,顺序显示 L 中各结点的值域。 (6) 求线性表 L 中指定位置的某个数据元素 GetElem(L,i,&e):用 e 返回 L 中第 i(1≤i ≤ListLength(L))个元素的值。 (7) 定位查找 LocateElem(L,e):返回 L 中第 1 个值域与 e 相等的位序。若这样的元素不存在, 则返回值为 0。 (8) 插入数据元素 ListInsert(&L,i,e):在 L 的第 i(1≤i≤ListLength(L)+1)个元素之前插 入新的元素 e,L 的长度增 1。 (9) 删除数据元素 ListDelete(&L,i,&e):删除 L 的第 i(1≤i≤ListLength(L))个元素,并用 e 返回其值,L 的长度减 1。 2.2 线性表的顺序存储 2.2.1 线性表的顺序存储—顺序表 2.2.2 顺序表基本运算的实现 2.2.1 线性表的顺序存储—顺序表 线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算 机存储器中指定存储位置开始的一块连续的存储空间中。 这样,线性表中第一在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线 线表中的所有元素和定义一个整型变量来存储线性表的长度。 假定数组用 data[MaxSize]表示,长度整型变量用 length 表示,并采用结构体类型表示, 则元素类型为通用类型标识符 ElemType 的线性表的顺序存储类型可描述如下: typedef struct { ElemType data[MaxSize]; int length; } SqList; /*顺序表类型*/ 其中,data 成员存放元素,length 成员存放线性表的实际长度。 说明：由于 C/C++中数组的下标从 0 开始，线性表的第 i 个元素 ai 存放顺序表的第 i-1 位置上。为了清楚，将 ai 在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物 理位序。 2.2.2 顺序表基本运算的实现

一日采用顺序表存储结构我们就可以用C/C++语言实现线性表的各种基本运算。为了方便假设ElemType为char类型，使用如下自定义类型语句typedef char ElemType;1.建立顺序表其方法是将给定的含有个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下：void CreateList(SqList *&L,ElemType a[],int n)/*建立顺序表*/1inti,L=(SqList *)malloc(sizeof(SqList);for (i=0;i<n;i++)L->data[i]=a[i];L->length=n;32.顺序表基本运算算法(1)初始化线性表InitList(L)该运算的结果是构造一个空的线性表L。实际上只需将length成员设置为0即可。(2）销毁线性表DestroyList(L)该运算的结果是释放线性表L占用的内存空间。(3）判定是否为空表ListEmpty(L）该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。(4)求线性表的长度ListLength(L)该运算返回顺序表L的长度。实际上只需返回length成员的值即可。(5)输出线性表DispList(L)该运算当线性表L不为空时，顺序显示L中各元素的值。(6)求某个数据元素值GetElem(L,i,e)该运算返回L中第i(1≤i≤ListLength(L))个元素的值，存放在e中。（7）按元素值查找LocateElem(L,e)该运算顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在，则返回值为0。（8）插入数据元素ListInsert(L,i,e该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素e。(9)删除数据元素ListDelete(L,,e)删除顺序表L中的第i(1≤i≤ListLength(L))个元素。2.3线性表的链式存储2.3.1线性表的链式存储一链表在链式存储中每个存储结点不仅包含有所存元素本身的信息（称之为数据域）而且包含有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息，这称为指针域，这样可以通过前驱结点的指针域方便地找到后继结点的位置提高数据查找速度。在单链表中,假定每个结点类型用LinkList表示,它应包括存储元素的数据域,这里用data表示，其类型用通用类型标识符ElemType表示还包括存储后继元素位置的指针域,这里用next表示。18

18 一旦采用顺序表存储结构,我们就可以用 C/C++语言实现线性表的各种基本运算。为了方便, 假设 ElemType 为 char 类型,使用如下自定义类型语句: typedef char ElemType; 1. 建立顺序表 其方法是将给定的含有 n 个元素的数组的每个元素依次放入到顺序表中，并将 n 赋给顺 序表的长度成员。算法如下： void CreateList(SqList *&L,ElemType a[],int n) /*建立顺序表*/ { int i; L=(SqList *)malloc(sizeof(SqList)); for (i=0;i<n;i++) L->data[i]=a[i]; L->length=n; } 2. 顺序表基本运算算法 (1) 初始化线性表 InitList(L) 该运算的结果是构造一个空的线性表 L。实际上只需将 length 成员设置为 0 即可。 (2) 销毁线性表 DestroyList(L) 该运算的结果是释放线性表 L 占用的内存空间。 (3) 判定是否为空表 ListEmpty(L) 该运算返回一个值表示 L 是否为空表。若 L 为空表,则返回 1,否则返回 0。 (4) 求线性表的长度 ListLength(L) 该运算返回顺序表 L 的长度。实际上只需返回 length 成员的值即可。 (5) 输出线性表 DispList(L) 该运算当线性表 L 不为空时,顺序显示 L 中各元素的值。 (6) 求某个数据元素值 GetElem(L,i,e) 该运算返回 L 中第 i(1≤i≤ListLength(L))个元素的值,存放在 e 中。 (7) 按元素值查找 LocateElem(L,e) 该运算顺序查找第 1 个值域与 e 相等的元素的位序。若这样的元素不存在,则返回值 为 0。 (8) 插入数据元素 ListInsert(L,i,e) 该运算在顺序表 L 的第 i 个位置(1≤i≤ListLength(L)+1)上插入新的元素 e。 (9) 删除数据元素 ListDelete(L,i,e) 删除顺序表 L 中的第 i(1≤i≤ListLength(L))个元素。 2.3 线性表的链式存储 2.3.1 线性表的链式存储—链表 在链式存储中,每个存储结点不仅包含有所存元素本身的信息(称之为数据域),而且包含 有元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息,这称为指针域,这样可 以通过前驱结点的指针域方便地找到后继结点的位置,提高数据查找速度。 在单链表中,假定每个结点类型用LinkList表示,它应包括存储元素的数据域,这里用data表示, 其类型用通用类型标识符 ElemType 表示,还包括存储后继元素位置的指针域,这里用 next 表 示

LinkList类型的定义如下typedef struct LNode/*定义单链表结点类型*/ElemType data;1struct LNode *next:/*指向后继结点*/ LinkList,2.3.2单链表基本运算的实现1.建立单链表先考虑如何建立单链表。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种(1）头插法建表该方法从一个空表开始，读取字符数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。采用头插法建表的算法如下：void CreateListF(LinkList *&L,Elem Type a[l,int n)LinkList *s,int i;L=(LinkList*)malloc(sizeof(LinkList))；/*创建头结点*)L->next-NULL,for(i=0:i<ni++)s-(LinkList *)malloc(sizeof(LinkList));/*创建新结点*/s->data=a[i]; s->next=L->next;/*将*s插在原开始结点之前，头结点之后*/L->next=s;33(2）尾插法建表头插法建立链表虽然算法简单但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致，可采用尾插法建立。该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针，使其始终指向当前链表的尾结点。采用尾插法建表的算法如下void CreateListR(LinkList *&L,ElemType al,int n)LinkList *s,*r,int i,L=(LinkList *)malloc(sizeof(LinkList);/*创建头结点*/r=L,/*始终指向终端结点.开始时指向头结点*for (i=0;i<n;i++)s-(LinkList *)malloc(sizeof(LinkList));/*创建新结点*/s->data=a[i];r->next=s，/*将*s插入*r之后*/r=s,3/*终端结点next域置为NULL*/r->next=NULL,2.插入结点运算插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找19

19 LinkList 类型的定义如下: typedef struct LNode /*定义单链表结点类型*/ { ElemType data; struct LNode *next; /*指向后继结点*/ } LinkList; 2.3.2 单链表基本运算的实现 1. 建立单链表 先考虑如何建立单链表。假设我们通过一个含有 n 个数据的数组来建立单链表。建立单 链表的常用方法有如下两种: (1) 头插法建表 该方法从一个空表开始,读取字符数组 a 中的字符,生成新结点,将读取的数据存放到 新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表 的算法如下: void CreateListF(LinkList *&L,ElemType a[],int n) { LinkList *s;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL; for (i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*/ s->data=a[i]; s->next=L->next; /*将*s 插在原开始结点之前,头结点之后*/ L->next=s; } } (2) 尾插法建表 头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若 希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须 增加一个尾指针 r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下: void CreateListR(LinkList *&L,ElemType a[],int n) { LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ r=L; /*r 始终指向终端结点,开始时指向头结点*/ for (i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*/ s->data=a[i];r->next=s; /*将*s 插入*r 之后*/ r=s; } r->next=NULL; /*终端结点 next 域置为 NULL*/ } 2. 插入结点运算 插入运算是将值为 x 的新结点插入到单链表的第 i 个结点的位置上。先在单链表中找

到第i-1个结点,再在其后插入新结点。3.删除结点运算删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如下图所示。删除结点示意图4.线性表基本运算实现(1）初始化线性表InitList(L)该运算建立一个空的单链表，即创建一个头结点。void InitList(LinkList *&L)1/*创建头结点*/L=(LinkList *)malloc(sizeof(LinkList),L->next=NULL;1销毁线性表DestroyList(L)(2)释放单链表L占用的内存空间。即逐一释放全部结点的空间。void DestroyList(LinkList *&L)LinkList *p=L,*q-p->next;while (q!=NULL)1free(p);p=q;q=p->next;3free(p);1(3）判线性表是否为空表ListEmpty(L)若单链表L没有数据结点，则返回真，否则返回假。int ListEmpty(LinkList *L)1return(L->next=--NULL);求线性表的长度ListLength(L)(4)返回单链表L中数据结点的个数。int ListLength(LinkList *L)LinkList *p-L,int i=0,while (p->next!-NULL)i++;1p=p->next;1return(i);输出线性表DispList(L)(5)逐一扫描单链表L的每个数据结点，并显示各结点的data域值。void DispList(LinkList *L)LinkList *p-L->next;while (p!=NULL)20

20 到第 i-1 个结点,再在其后插入新结点。 3. 删除结点运算 删除运算是将单链表的第 i 个结点删去。先在单链表中找到第 i-1 个结点,再删除其后的 结点。删除单链表结点的过程如下图所示。 删除结点示意图 4. 线性表基本运算实现 (1) 初始化线性表 InitList(L) 该运算建立一个空的单链表,即创建一个头结点。 void InitList(LinkList *&L) { L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL; } (2) 销毁线性表 DestroyList(L) 释放单链表 L 占用的内存空间。即逐一释放全部结点的空间。 void DestroyList(LinkList *&L) { LinkList *p=L,*q=p->next; while (q!=NULL) { free(p); p=q;q=p->next; } free(p); } (3) 判线性表是否为空表 ListEmpty(L) 若单链表 L 没有数据结点,则返回真,否则返回假。 int ListEmpty(LinkList *L) { return(L->next==NULL); } (4) 求线性表的长度 ListLength(L) 返回单链表 L 中数据结点的个数。 int ListLength(LinkList *L) { LinkList *p=L;int i=0; while (p->next!=NULL) { i++; p=p->next; } return(i); } (5) 输出线性表 DispList(L) 逐一扫描单链表 L 的每个数据结点,并显示各结点的 data 域值。 void DispList(LinkList *L) { LinkList *p=L->next; while (p!=NULL)

printf("%c",p->data);p=p->next:printf("n");1(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e)思路：在单链表L中从头开始找到第i个结点,若存在第i个数据结点,则将其data域值赋给变量e。int GetElem(LinkList *L,int i,ElemType &e)intj=0,LinkList *p=L;while (i<i && p!=NULL)1j+t;p=p->next;1if(p==NULL)returnO;/*不存在第i个数据结点*else/*存在第1个数据结点*1e=p->data,return l;33(7）按元素值查找LocateElem(L,e)思路：在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点，则返回位置，否则返回0。int LocateElem(LinkList *L,ElemType e)(LinkList *p=L->next;int n=1;while (p!=NULL&& p->data!=e):p=p->next; n++;if(p=-NULL) return(O);else return(n);1(8）插入数据元素ListInsert(&L,,e)思路：先在单链表L中找到第i-1个结点*p,若存在这样的结点,将值为e的结点*s插入到其后。int ListInsert(LinkList *&L,int i,ElemType e)int j=0;LinkList *p-L,*s;while(i<i-1&&p!=NULL)/*查找第i-1个结点*/{j++;p=p->next;1if（p-NULL)return0,/*未找到位序为i-1的结点*/else/*找到位序为i-1的结点*p*/s-(LinkList *)malloc(sizeof(LinkList);21

21 { printf("%c",p->data); p=p->next; } printf("\n"); } (6)求线性表 L 中指定位置的某个数据元素 GetElem(L,i,&e) 思路：在单链表 L 中从头开始找到第 i 个结点,若存在第 i 个数据结点,则将其 data 域值赋给变量 e。 int GetElem(LinkList *L,int i,ElemType &e) { int j=0; LinkList *p=L; while (j<i && p!=NULL) { j++; p=p->next; } if (p==NULL) return 0; /*不存在第 i 个数据结点*/ else /*存在第 i 个数据结点*/ { e=p->data; return 1; } } (7) 按元素值查找 LocateElem(L,e) 思路：在单链表 L 中从头开始找第 1 个值域与 e 相等的结点,若存在这样的结点,则返 回位置,否则返回 0。 int LocateElem(LinkList *L,ElemType e) {LinkList *p=L->next;int n=1; while (p!=NULL && p->data!=e) { p=p->next; n++; } if (p==NULL) return(0); else return(n); } (8) 插入数据元素 ListInsert(&L,i,e) 思路：先在单链表 L 中找到第 i-1 个结点*p,若存在这样的结点,将值为 e 的结点*s 插 入到其后。 int ListInsert(LinkList *&L,int i,ElemType e) { int j=0; LinkList *p=L,*s; while (j<i-1 && p!=NULL) /*查找第 i-1 个结点*/ { j++; p=p->next; } if (p==NULL) return 0; /*未找到位序为 i-1 的结点*/ else /*找到位序为 i-1 的结点*p*/ { s=(LinkList *)malloc(sizeof(LinkList));