第二章 线性表.

Presentation on theme: "第二章 线性表."— Presentation transcript:

1 第二章 线性表

2 线性结构的特点 在数据元素的非空有限集中： 1、存在唯一的一个被称为“第一个”的数据元素； 2、存在唯一的一个被称为“最后一个”的数据元素；
3、除第一个之外，集合中的每个数据元素有且仅有一个直接前驱； 4、除最后一个之外，集合中的每个数据元素有且仅有一个直接后继。

3 第一节 线性表的概念及逻辑结构 一、线性表（Linear List）的定义 线性表是ｎ个数据元素的有限序列。记为：
第一节 线性表的概念及逻辑结构 一、线性表（Linear List）的定义 线性表是ｎ个数据元素的有限序列。记为： D={a1，a2，……an} ai是一个抽象符号。数据元素间关系与元素具体内容无关。 同一线性表中元素具有相同性质，即属同一数据对象，相邻数据元素间存在着序偶关系。可表示为： R={〈ａi-1，ai〉│i=2..n } 〈ai-1，ai〉表示ai-1是ai直接前驱，ai是ai-1的直接后继。 表中数据元素个数(ｎ≥0)称为线性表的长度。 ｎ＝0表示空表。 非空表，每个元素都有确定的位置，即a1是第一个元素，an是最后一个元素，ai是第i个元素，称i为ai在线性表中的位序。

4 线性表抽象数据类型描述 ADT List { 数据对象：D 数据关系；R 基本操作：
InitList(&L)： 初始化操作，设定一个线性表。 DestroyList(&L): 撤消线性表。 ClearList(&L)： 表置空操作。 ListEmpty(L)： 判空表函数。 ListLength(L)： 长度的函数，返回元素的个数。 GetElem(L,i,&e)： 取第个i数据元素。 LocateElem(L,x)： 定位函数。 PriorElem(L,elm,&pre_e)： 求元素elm的前驱。 NextElem(L,elm,&next_e)： 求元素elm的后继。 ListInsert(&L,i,e)： 在第个i元素之前,插入元素e。 ListDelete(&L,i,&e)： 删除第i个元素。 Listtraverse(L): 遍历线性表元素。 } ADT　List

5 第二节：线性表的顺序表示及实现 一、存储分配方式: 用一组地址连续的存储单元依次存储线性表的数据元素。设： b为存储空间的首地址
一、存储分配方式: 用一组地址连续的存储单元依次存储线性表的数据元素。设： b为存储空间的首地址 L为数据元素长度 elem Length Listsize a1 a2 an 空闲 b b+L b+(n-1)L b+(Listsize-1)L 二、顺序分配的实现： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int Length; int Listsize; }sqlist;

6 线性表的顺序表示及实现 三、特点 【特点1】逻辑上相邻的元素ai和ai+1的存储位置相邻，即以结点“物理位置相邻”来表示线性表中结点之间的逻辑关系，线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称这种实现的线性表为顺序表 【特点2】设第一个元素的存储位置为线性表的开始位置，称为基地址。每个结点的第一个单元的存储地址作为结点的存储地址。每个结点占L个存储单元，结点ai的地址为loc(ai)，则有： loc(ai)=loc(a1)+(i-1)*L 即只要确定了存储线性表的起始地址，就直接确定了线性表中任一数据元素的存储位置，从而实现对线性表元素的随机存取(存取任一数据元素的存取时间都为一常数)。

7 线性表的顺序表示及实现 四、顺序存储分配的算法实现 1、线性表的初始化 Status Initlist_Sq(Sqlist &L)
{ L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType); if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 L.listsize= List-Init-Size; //初始存储容量 return OK; } 元素ai对应着L.elem[i-1]。 L.length=0:表示为空表。 L.length= List-Init-Size表示表满。

8 线性表的顺序表示及实现 DestroyList_Sq(&L): {free(L.elem);L.elem=NULL;}
2、基本操作 DestroyList_Sq(&L): {free(L.elem);L.elem=NULL;} ClearList_Sq(&L)： {L.length=0;} ListLength_Sq(L)： {return(L.length);} GetElem_Sq(L,i,&e)：{ e=L.elem[i-1];} status ListEmpty_Sq(SqList L) { if(L.length==0) return(TRUE); else return(FALSE); }

9 线性表的顺序表示及实现 Status(*compare)(ElemType,ElemType)) { i=1; p=L.elem;
定位函数： int LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType,ElemType)) { i=1; p=L.elem; while(i<=L.length && (*compare)(*p++,e)) i++; if(i<=L.length) return(i); else return(0); } L.elem i-1 e 算法时间复杂度：e是表中元素，定位操作的平均比较次数为（1+2+3+…+n)/n=(n+1)/2，即算法时间复杂度为O(n)。

10 线性表的顺序表示及实现 status PriorElem_Sq(SqList L,ElemType e,ElemType &pre_e,
Status(*compare)(ElemType,ElemType)) { i=LocateElem_Sq(L, e,compare); if(i>=2) { pre_e=L.elem[i-2]; return(1);} else return(0); } status NextElem_Sq(SqList L,ElemType e,ElemType &next_e, if(i&&i<L.length) { next_e=L.elem[i]; return(1);} 算法分析：算法的时间复杂度与定位函数的时间复杂度有关。即算法时间复杂度为O(n)。

11 插入算法 ◆插入运算：在表的第i(1≤i≤n+1)个位置上，插入一个新结点x。假设插入前的状态为： i i n-1 a1 a2 …… ai-1 ai an 后移一个位置 在第i个位置插入一个元素x后的状态： i i i n a1 a2 …… ai-1 x ai an 插入后ai-1,ai的逻辑关系发生了变化，x成了ai-1的后继，ai的前驱。在顺序存储结构中也要反映这种逻辑关系的变化，即除非i=n+1,否则，在物理位置上从ai到an都必须后移一个元素位置。

12 插入算法 算法思想：若i<=L.length，先将ai～an后移一个位置，然后插入。
Status Listinsert_Sq(Sqlist &L,int i, Elemtype e) { if (i<1‖i >L.length+1) return ERROR; //判断i的正确性 if (L.length>=L.listsize) //判断是否有空闲的存储空间 { newbase=（ElemType *）realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=Listincrement; } //扩展存储空间 q=&(L.elem[i-1]); //需要后移的数据元素的开始位置 for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //移动元素 *q=e; //插入 ++L.length; //修改表的长度 return OK; }

13 删除算法 ◆删除运算：删除表的第i(1≤i≤n)个元素。 删除前的状态为： i i i n-1 a1 a2 …… ai-1 ai ai+1 an 前移一个位置 删除第i个元素后的状态： i i n-2 a1 a2 …… ai-1 ai+1 an 删除第i个结点后ai-1,ai+1的逻辑关系发生了变化，在存储结构上通过移动元素使之在逻辑上相邻的元素在物理上也相邻。 算法思想：只需将ai+1～an依次向前移动一个位置，并修改其长度。

14 删除算法 Status Listdelete_Sq(Sqlist &L,int i, Elemtype &e)
{ if (i<1‖i >L.length) return ERROR;//判断I的正确性 p=&(L.elem[i-1]); //指示被删元素位置 e=*p; //返回被删元素的值 q=L.elem+L.length-1; //指示最后元素位置 for (++p;p<=q;++p) *(p-1)=*p; //移动元素 --L.length; //修改表的长度 return OK; } 另一种移动方法 ： e=L.elem[i-1]; for(j=i;j<L.length;j++) L.lem[j-1]=L.lem[j];

15 ∑ ∑ 插入、删除算法分析 等概率下： Ei =n / 2 Ed =（n-1）/ 2 算法时间复杂度：O(n)
设在线性表第 i 个元素前插入一新元素的概率为 Pi，删除第 i 个元素的概率为 Qi，元素移动为算法的基本操作。则插入和删除的平均移动期望值为： n+1 ∑ i=1 Ei= Pi（n-i+1） n ∑ i=1 Ed= Qi （n-i） 等概率下： Ei =n / Ed =（n-1）/ 2 算法时间复杂度：O(n) 线性表顺序存储结构优点:可随机存取表中任一结点。 缺点：插入删除操作可能要移动大量元素。

16 L ^ 第三节：线性表的链式表示及实现 一、线性链表（单链表） 特点：用一组任意的存储单元存放线性表的结点(可以不连续)。
逻辑关系的表示：将元素ai与ai+1的地址存储在一起。 data next 结点 数据域 指针域 线性链表的三要素： 1、设立一个指针变量head来指向第一个结点。 2、每一个结点的存储地址都由前一结点的指针域指示。 3、最后一个结点无后继结点，其指针域为空。 a1 L 头指针 a2 ^ an … 元素结点 尾结点

17 L ^ L ^ L ^ 线性表的链式表示及实现 例: 设有线性表为: (Zhao,Qian,Sun,Li,Zhou) 单链表的特点：
1、链表中各结点逻辑上有序，物理上可能无序。 2、任何两个结点的存储位置之间没有固定的联系。要访问任一元素，必须从头指针出发进行寻找。因此，单链表是顺序访问结构。 3、增设一个头结点作为链表的第一个结点可使某些算法更简单，头结点的数据域可以不存任何信息，指针域指示第一个结点（首元素）的地址。 zhao Qian ^ Zhou L sun Li ^ L 空链表：

18 单链表的C语言描述 typedef struct Lnode { Elemtype data； struct Lnode *next；
} Lnode， *Linklist；

19 线性链表的运算 1、线性链表的初始化的实现 （带头结点） LinkList InitList_L(void)
{ head=(ListNode *)malloc(sizeof(ListNode)); head->next=NULL; return(head); } 2、撤消线性链表 void DestroyList_L(LinkList *L) { p=*L; *L=NULL; while(p) { q=p->next; free(p); p=q; } 3、置空线性链表 void clearList_L(LinkList *L) { p=L->next; L->next=NULL; while(p) { q=p->next; free(p); p=q; }

20 线性链表的访问运算 4、访问第i个数据元素 Status GetElem_L(LinkList L,int i,ElemType &e)
{ p=L->next;j=1; while(p&& j <i){ p=p->next;j++}; if(!p||j>i) return(ERROR); e=p->data; return(OK); } 算法分析： 基本操作：移动指针。若1≤i≤n，则循环体执行i-1次，否则执行n次。成功平均移动指针次数为: （0+1+2+…+n-1)/n=(n-1)/2。 算法时间复杂度为O(n)。

21 a b x S 线性链表的插入运算 5、结点插入运算：在第i个数据元素前插入一个新元素 基本思想：先找到第i个结点的前驱结点，然后执行插入。
P a b 在p后插入结点s： S->next=p->next; P->next=s; x S 基本思想：先找到第i个结点的前驱结点，然后执行插入。 Status Listinsert_L(Linklist L,int i,Elemtype e) { p=L; j=0; while (p&&j<i-1) { p=p->next; ++j } if ( !p ‖j>i-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; return OK; }

22 p->next=q->next;
线性链表结点的删除 6、结点删除运算：删除第i个数据元素 删除p后面的结点： P a c b q=p->next; p->next=q->next; q free(q); 基本思想：先找到第i个结点的前驱结点，然后执行删除。 Status ListDelete_L(Linklist L,int i,Elemtype &e) { p=L; j=0; while (p->next&&j<i-1) { p=p->next; ++j } if ( !p->next ‖j>i-1) return ERROR; q=p->next; p->next=q->next; free(q); return OK; } 算法时间复杂度：O(n)。

23 线性链表的生成 7、线性链表生成 基本思想：首先初始化线性链表，然后依次生成结点并插入到链表中。插入时，可插入到表头，也可以插入到表尾，依元素间的逻辑顺序而定。若从第一个元素开始输入，必须插入到表尾，反之则插入到表头。 void CreateList(LinkList &L, int n) { L =InitList_L() for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(Lnode)); scanf(p->data); p->next=L->next; L->next=p; } 插入到尾的算法？

24 两个有序链表的合并运算 将单链表la和lb归并到链表lc，la和lb非递减有序，lc也非递减有序。 基本思想：设pa、pb指向la和lb当前待比较的结点，pc指向lc的最后一个结点。则有：pa->data<=pb->data，把pa所指结点连接到pc结点之后。 否则，把pb所指结点连接到pc结点之后。 ai ^ an La … pa pa->data<=pb->data c1 ck Lc … pc pa->data>pb->data b2 ^ bn Lb pb

25 两个有序链表的合并运算 void Mergelist_L(Linklist &La, Linklist &Lb, Linklist &Lc)
{ pa=La->next; pb=Lb->next; Lc=pc=La; while (pa&&pb) { if ( pa->data<=pb->data) { pc->next=pa;pc=pa;pa=pa->next;} else { pc->next=pb;pc=pb;pb=pb->next;} } pc->next =pa?pa:pb; free(Lb); 算法时间复杂度： O(m+n)

26 第四节 循环链表 L L 在单链表中，将最后一个结点的指针域指向开始结点或头结点，就得到单链形式的循环链表，简称单循环链表。
循环链表：首尾相接的链表。 在单链表中，将最后一个结点的指针域指向开始结点或头结点，就得到单链形式的循环链表，简称单循环链表。 特点：从任一结点出发，可以访问表中所有其它结点。 为使得空表和非空表的运算统一，在循环链表中设置一个头结点。它的值域或为空，或按需要设定。这样，循环链表至少存在一个结点。当插入或删除运算时，不再需要改变表头指针。 a1 a2 an L L 空单循环链表

27 循环链表 若在循环链表中设置尾指针而不是头指针，既可方便地插到an,又可方便地插到a1，还可以使某些某些操作简化，如两个线性表合并为一个表。 ④ a1 a2 an A p ① ② A ⑤ Q ③ a1 a2 an B P=A->next;A->next=B->next->next;Q=B->next; B->next=p;A=B; free(Q);

28 L L 第五节 双向链表 双向链表：每个结点设置两个指针域，一个指向直接前驱，一个指向直接后继。
双向循环链表：在双向链表中，若第一个结点（或头结点）的前向指针指向最后一个结点，最后一个结点的后向指针指向第一个结点（或头结点），则就是双向循环链表。 双向循环链表一般都有头结点。 a1 a2 an L L 双向空链表

29 双向链表结点结构 后向指针 数据 前向指针 双向链表结点的存储结构定义 typedef struct Dublnode{
Elemtype data; struct Dublnode *prior ； struct Dublnode *next ； }Dublnode,*Dublinklist ；

30 ① ② P a b c 双向链表运算 删除结点p 主要操作 p->prior->next=p->next;
p->next->prior=p->peior;

31 a b x 双向链表运算 ② 在结点p前插入值为x的结点 P ④ ① ③ s 主要操作
S=(Dublnode *)malloc(sizeof(Dublnode)); S->data=x; S->prior=p->prior p->prior->next=s; S->next=p; p->prior=s;

32 线性表存储结构的讨论 线性表的两种存储结构：顺序表和链表。 1、基于空间的考虑 顺序表存储空间一般存在存储空间浪费。
链表的存储空间根据需要而分配，无存储空间浪费。 线性表长度基本固定时，采用顺序表，否则采用链表。 2、基于时间的考虑 顺序表是随机存取结构，存取的时间复杂度为O(1)。 链表是顺序存取结构，时间复杂度为O(n)。 顺序表插入和删除运算可能要移动大量元素。 链表插入和删除运算修改指针就可实现，无需移动元素。

33 链表应用实例—一元多项式表示及运算 多项式pn(x)可表示成: pn(x)=a0+a1x+a2x2+…+anxn
线性表表示： （a0，a1，a2，…，an） 指数隐含在系数ai的序号中。 顺序表：n+1个单元。当n很大、0系数较多时，浪费空间和时间。 如：s(x)=1+3x1000+2x20000 采用线性链表的存储结构灵活性大。其结点结构为： typedef struct Node{ float coef; int expn; struct Node *next }PolyNode,*polynomial; p 1 3 1000 2 2000 ۸

34 链表应用实例—一元多项式表示及运算 多项式相加运算规则： 指数相同，系数相加，若不为0，则构成一项。 指数不同，则两项系数照抄。
设 A(x)=A(x)+B(x) p、q分别指向两个多项式中当前被检测的结点。若： p->exp<q->exp: 结果多项式的当前结点为p; p->exp=q->exp: p->coef=p->coef+q->coef 删除结点q,若结果为0，删除结点p; p->exp>q->exp: 将结点q插入到A多项式中。 若B多项式结点未取完，则把剩余结点链到A多项式后面。

35 链表应用实例—一元多项式相加运算 B(x)=8x+22x7-9x8 运算结果：A(x)=7+11x +22x7 +5x17
pa 7 3 1 9 8 5 17 ۸ A pb 8 1 22 7 -9 8 ۸ B pa 7 11 1 8 5 17 ۸ 运算结果：A(x)=7+11x +22x7 +5x17

36 链表应用实例—一元多项式相加运算 { p=pa->next;q=(*pb)->next; pre=pa;
void AddPoly(polynomial pa, polynomial *pb) { p=pa->next;q=(*pb)->next; pre=pa; while(p!=NULL && q!=NULL) if(p->expn<q->expn) { pre=p;p=p->next;} else if(p->expn==q->expn) { p->coef=p->coef+q->coef; if(p->coef!=0) pre=p; else { pre->next=p->next;free(p);} p=pre->next;u=q;q=q->next;free(u); } else{ u=q;q=q->next;u->next=p;pre->next=u;pre=u;} if(q!=NULL) pre->next=q; free(*pb);*pb=NULL;

37 一元多项式相乘运算的实现 =A(x) ×(b1xe1+b2xe2+……+bnxen) =∑biA(x)xei (i=1,2,……,n)
M(x)=A(x)×B(x) =A(x) ×(b1xe1+b2xe2+……+bnxen) =∑biA(x)xei (i=1,2,……,n) 实现方法： 1、多项式链表初始化。 2、用B多项式的每一项去乘A多项式的每一项，将乘得的结果插入到M多项式中。 for(p=Lb.next;p;p=p->next; for(q=La.next;q;q=q->next) {coef=p->coef*q->coef; expn=p->exn+q->expn; 用expn查找M多项式链表，返回小于或等于expn值的结点指针，若小于，则在其后插入一个新结点，否则，系数相加。 }

38 作业 P14 2.6、2.7、2.8 2.17、2.18、2.19、2.22 2.25、2.29 上机实验： P81 1、1.4 2、1.5