线性结构 线性结构的特点： 线性结构的种类 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素；

Presentation on theme: "线性结构 线性结构的特点： 线性结构的种类 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素；"— Presentation transcript:

1 线性结构 线性结构的特点： 线性结构的种类 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素；
（2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。 线性结构的种类 线性表 栈 队列 串 …… 数据结构

2 数据结构 第2章 线性表 什么是线性表？？ 线性表的基本运算？？ 数据结构

3 线性表 线性表(Linear List) ：一个线性表是n个数据元素的有限序列。数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。 例1： 26个英文字母组成的字母表 （A，B，C、…、Z） 例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况 （6，17，28，50，92，188） 例3：学生健康情况登记表 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 张立立 790633 17 神经衰弱 …….. ……. 数据结构

4 由上述例子可见，线性表中的数据元素类型可以多种多样，但同一线性表中的元素必定具有相同特性，且相邻数据元素之间存在着序偶关系。若记为
( a1, a2,...,ai-1,ai,ai+1,...,an)， 则ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中，每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性表中的位序。 线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1； 其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 是一种典型的线性结构。 数据结构

5 线性表的抽象数据类型定义 ADT List{ 数据对象: D={ai| ai(- ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 基本操作： InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) LocateElem(L,e,compare()) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit()) }ADT List 数据结构

6 如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以利用类型中定义的各种操作。
例2.1：已知集合 A 和 B，求两个集合的并集，使 A＝A∪B。 从集合的观点看，此问题求解的方法很简单，只要对集合 B 中的所有元素一个一个地检查，看看在集合 A 中是否存在相同元素，若不存在，则将该元素插入到集合 A，否则舍弃之。 要在计算机中求解，首先要确定“如何表示集合”。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。 现假设以线性表 LA 和 LB 分别表示集合 A 和 B，即构造两个线性表 LA 和 LB，它们的数据元素分别为集合 A 和 B 中的成员。由此，上述集合求并的问题便可演绎为：要求对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。 　　具体操作步骤为： 　　1．从线性表 LB 中取出一个数据元素； 　　2．依值在线性表 LA 中进行查询； 　　3．若不存在，则将它插入到 LA 中。 　　重复上述三步直至 LB 为空表止。 那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？ GetElem(LB,i,&e) LocateElem(LA,e,equal（)) ListInsert(LA,n+1,e) 数据结构

7 由此得到求并集的算法如下所示,算法2.1： void union(List &LA, List &LB){ 　 // 将所有在线性表LB中但不在LA中的数据元素插入到 LA 中, 　 La_len = ListLength(LA);　// 求得线性表 LA的长度 Lb_len = ListLength(LB);　// 求得线性表 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相同的数据元素时进行插入 　　 }　　　 　 } //union 其中，GetElem和ListInsert的执行时间与表长无关， LocateElem的执行时间与表长成正比，所以算法2.1的时间复杂度为：O(ListLength(LA)*ListLength(LB ))。 数据结构

8 从问题要求可知，LC中的元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中元素逐个插入到LC中即可。
例2.2：已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 从问题要求可知，LC中的元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中元素逐个插入到LC中即可。 为使LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB的当前元素（分别为a和b），则当前应插入到LC中的元素c为：c=a（a<=b）,c=b（a>b）。 数据结构

9 void MergeList(list la，list lb，list &lc){
由此得到上述归并的算法如下所示,算法2.2： void MergeList(list la，list lb，list &lc){ InitList(lc); i=j=1;k=0; la_len=ListLength(la); lb_len=ListLength(lb); while((i<=la_len)&&(j<=lb_len)){ GetElem(la，i，ai); GetElem(lb，j，bj); if(ai<=bj){ListInsert(lc，++k，ai); ++i ;} else{ListInsert(lc，++k，bj); ++j ; } } while( i <=la_len ) { GetElem(la，i++，ai ); ListInsert(lc，++k，ai ); while(j<=lb_len){ GetElem(lb，j++，bj); ListInsert(lc，++k，bi); 其中，GetElem和ListInsert的执行时间与表长无关,所以算法2.1的时间复杂度为：O(ListLength(LA)+ListLength(LB ))。 数据结构

10 线性表的顺序表示和实现 若要在实际的程序设计中真正引用线性表的基本操作，首先必须实现线性表类型。即在计算机中确定它的存储结构并在此存储结构上实现类型中定义的所有基本操作。本节将讨论它的顺序存储结构以及在顺序存储结构中基本操作的实现。 　 数据结构

11 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的各个数据元素。
假设每个数据元素占据的存储量是一个常量 l，则后继元素的存储地址和其前驱元素相隔一个常量l， 即：LOC(ai+1) = LOC(ai) + l 　　　　　　　　　　　　　　↑一个数据元素所占存储量 由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到 　　　　LOC(ai ) = LOC(a1 ) + (i-1)×l 　　　　　　　　　　↑基地址 数据结构

12 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；
顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致； （2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。 数据结构

13 线性表的动态分配顺序存储结构 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。同时，线性表的长度可变，且所需的最大存储空间随问题不同而不同，故我们用如下的结构来定义顺序表。 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以一数据元素存储长度为单位） }SqList; 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.elem[i-1]。 数据结构

14 顺序表典型操作的实现 线性表的建立 此算法的时间复杂度为O (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; } // InitList_Sq 此算法的时间复杂度为O (1)。 数据结构

15 线性表的销毁 void DestroyList( SqList &L ){ 　　 // 释放顺序表 L 所占存储空间 　　if (L.elem) free(L.elem); L.length = 0; L.listsize = 0;　 　} // DestroyList_Sq 　　 此算法的时间复杂度为：O (1) 线性表的清空 void ClearList( SqList &L ){ 　　 // 将顺序表 L的长度置0　　 　 L.length = 0; 　 　} // ClearList_Sq 　　 数据结构

16 判断线性表L是否为空 int ListEmpty(SqList L){ if (L.length==0) return TRUE; else return FALSE; } 此算法的时间复杂度为：O (1) 求线性表L的长度 int ListLength(SqList L){ return L.length; 数据结构

17 获取线性表L中的第i个数据元素的内容 int GetElem(SqList L,int i,ElemType *e){ if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR *e=L.elem[i-1]; //数组中第i-1的单元存储着线性表中第i个数据元素的内容 return OK; } 此算法的时间复杂度为：O (1) 数据结构

18 在顺序表L中查找第1个值与e满足compare()的元素的位序
int LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemType)){ i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; } // LocateElem_Sq 此算法的最坏时间复杂度为：O (L.length) 数据结构

19 在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。一般地可表示为：
顺序表的插入 在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1} 插入后：{k0, k1, …, ki-1,x, ki, …, kn-1} 数据结构

20 数据结构 Status ListInsert_Sq(SqList &L, int i, ElemType e){
// 在顺序线性表L的第i个元素之前插入新的元素e，i的合法值为1≤i≤ListLength_Sq(L)+1 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) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } 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 (L.length) 数据结构

21 删除线性表中的第i个数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1}
顺序表的删除 删除线性表中的第i个数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1} 插入后：{k0, k1, …, ki-1,ki+1, …, kn-1} 数据结构

22 数据结构 Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
// 在顺序线性表L中删除第i个元素，并用e返回其值。 // i的合法值为1≤i≤ListLength_Sq(L)。 if (i<1 || i>L.length) return ERROR; // i值不合法 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 (L.length) 数据结构

23 作业 1.下面程序段的时间复杂度为?? for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++) A[i][j]=i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 2. 执行下面程序段时，执行S语句的次数为？？ for(int i = 1; i <= n; i++) for(int j = 1; j <=I; j++) S; A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 3. 下面算法的时间复杂度为？？ int f(int n){ if(n == 0 || n == 1) return 1; else return n*f(n-1); } 数据结构

24 4.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为____,输出一个二维数组b[m][n]中所有元素值的时间复杂度为____。
5. 在下面程序段中，s=s+p语句的次数为____,p*=j语句的次数为____,该程序段的时间复杂度为____。 int i = 0, s = 0; while(++i<=n){ int p = 1; for(int j = 1; j <= i; j++) p*=j; s = s + p; } 数据结构

25 6.试编写算法"比较"两个顺序表的大小。 何谓顺序表的"大""小"？现作如下规定： 　　设 A=(a1,…,am)和 B=(b1,…,bn)均为顺序表，又A’和B’分别为 A 和 B中除去最大共同前缀后的子表（例如，A=(y,x,x,z,x,z)， B=(y,x,x,z,y,x,x,z)，则两者中最大的共同前缀为(y,x,x,z)，在两表中除去最大共同前缀后的子表分别为A‘=(x,z)和 B’=(y,x,x,z)）。若A’=B’=空表，则 A=B；若A’=空表，而B’≠空表，或者两者均不为空表，且A’的首元小于B’的首元，则 A<B；否则 A>B。 　解题分析： 　(1) 算法要求对两个顺序表进行“比较”，是一种“引用型”操作，因此在算法中不应该破坏已知表。 　(2) 按上述规定，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则两个顺序表的大小主要取决于两表中除去最大公共前缀后的第一个元素。 　　因此，比较两表的大小不应该先比较它们的长度，而应该设一个下标变量j同时控制两个表，即对两表中"位序相同" 的元素进行比较。 数据结构

26 1. 以某种高级语言实现(c,c++,java…) 2. 提交的为源代码（注意编程风格）
要求： 1. 以某种高级语言实现(c,c++,java…) 2. 提交的为源代码（注意编程风格） 3. 设计一些测试用例，所编写的程序能正确通过这些测试用例。 数据结构

27 作业要求 例：123456_张三_数据结构作业1 作业提交至xhji.cugb@163.com 邮件主题格式为：学号_姓名_数据结构作业1
作业在最后的分数上会有所体现 允许讨论，不允许抄袭 作业会放在 （linuxopen社区的acm专区） 数据结构

28 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点。同时对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用。 为此，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。 数据结构

29 N个结点链接成一个表，称为链表。即线性表的链式存储结构。由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表 。
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个“结点”（ ），表示线性表中一个数据元素。其中存储数据元素信息的域称作数据域，存储直接后继存储位置的域称为指针域。指针域中存储的信息又称做指针或链。 N个结点链接成一个表，称为链表。即线性表的链式存储结构。由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表 。 Data link 数据结构

30 例：假设有一个线性表（a,b,c,d），其链式存储可如下：
其逻辑结构为： a b c d /\ 数据结构

31 线性表中所有数据元素都可以从头指针出发找到(头指针即第一个数据元素的存储地址 )。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的“指针”是一个特殊的值 “NULL” （在图上用∧表示），通常称它为“空指针”。 通常，我们在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示： 通常称这类单链表为“带头结点的单链表”。如果不特别声明的话，我们讨论的单链表都指的是这种带头结点的链表。 值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如下图所示。 数据结构

32 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；
链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。 数据结构

33 线性表的单链表存储结构 由上述可见，单链表可由头指针唯一确定，在C语言中可以用“结构指针"来描述。 　　　typedef struct LNode{ 　　　　ElemType data; 　　　　struct LNode *next; 　　　}Lnode, *LinkList; 单链表的建立 Status InitList_L(LinkList &L) { // 构造一个空的单链表L。 L = (LinkList)malloc(sizeof(LNode)); if (!L) exit(ERROR); // 存储分配失败 L->next = NULL; return OK; } // InitList_L 此算法的时间复杂度为O (1)。 数据结构

34 单链表的销毁 void DestroyList( LinkList &L ){ 　　 // 释放单链表 L 所占存储空间 　　while (L){ 　　　p = L; L = L->next; 　　　free(p); 　　} // while 　　L = NULL;　 } // DestroyList_L　　 此算法的时间复杂度为：O (ListLength(L)) 单链表的清空 void ClearList( LinkList &L ){ 　　 // 将单链表L的长度置0　　 　 while (L->next){ 　　　p = L->next; L->next = p->next; 　　　free(p); 　　} // while 　 } // ClearList_L 　　 数据结构

35 数据结构 判断单链表L是否为空 int ListEmpty(LinkList L){
if (L->next==NULL) return TRUE; else return FALSE; } 此算法的时间复杂度为：O (1) 求单链表L的长度 int ListLength(LinkList L){ length = 0; p = L->next; while(p!=NULL){ length++: p = p->next; }//while return length; 此算法的时间复杂度为：O (ListLength(L)) 数据结构

36 数据结构 获取单链表L中的第i个数据元素的内容
Status GetElem_L(LinkList &L,int i, ElemType &e) { // L为带头结点的单链表的头指针。 // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p = L->next; j = 1; // 初始化，p指向第一个结点，j为计数器 while (p && j<i) { // 顺指针向后查找，直到p指向第i个元素或p为空 p = p->next; ++j; } if ( !p || j>i ) return ERROR; // 第i个元素不存在 e = p->data; // 取第i个元素 return OK; } // GetElem_L 此算法的时间复杂度为：O (ListLength(L)) 数据结构

37 在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。一般地可表示为：
单链表的插入 在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1} 插入后：{k0, k1, …, ki-1,x, ki, …, kn-1} k0 … ki-1 ki kn-1 /\ x 插入前 插入后 数据结构

38 数据结构 Status ListInsert_L(LinkList &L, int i, ElemType e) {
// 在带头结点的单链线性表L的第i个元素之前插入元素e p = L; j = 0; while (p && j < i-1) { // 寻找第i-1个结点 p = p->next; ++j; } if (!p || j > i-1) return ERROR; // i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; } // ListInsert_L 此算法的最坏时间复杂度为：O (ListLength(L)) 数据结构

39 删除线性表中的第i个数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1}
单链表的删除 删除线性表中的第i个数据元素。一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1} 插入后：{k0, k1, …, ki-1,ki+1, …, kn-1} k1 … ki-1 ki kn-1 /\ 删除前 k0 x 删除后 数据结构

40 数据结构 Status ListDelete_L(LinkList &L, int i, ElemType &e) {
// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 p = L; j = 0; while (p->next && j < i-1) { // 寻找第i个结点，并令p指向其前趋 p = p->next; ++j; } if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; // 删除并释放结点 e = q->data; free(q); return OK; } // ListDelete_L 此算法的最坏时间复杂度为：O (ListLength(L)) 数据结构

41 插入新元素 顺序表在表尾插入。 单链表在表头插入。 void CreateList_Sq(SqList &L, int n) {
// 建立顺序表L，其数据元素依次为1到n的自然数 InitList_L(L); // 先建立一个空的顺序表 for (i=0; i<n; ++i) ListInsert_Sq(L, L.length, i+1); } // CreateList_Sq void CreateList_L(LinkList &L, int n) { // 建立带表头结点的单链表L，其数据元素依次为1到n的自然数 InitList_L(L); // 先建立一个带头结点的单链表 for (i=n; i>0; --i) ListInsert_L(L, 1, i) ; } // CreateList_L 数据结构

42 将两个有序线性表并为一个 有序线性表 顺序表：需要为新表分配存储空间(以换取时间上的改善，即以空间换时间)。 P26,算法2.7
单链表：不需要为新表分配存储空间。 P31,算法2.12 数据结构

43 单链表的特点 优点： (1) 能有效利用存储空间； 　　因为它是动态存储分配的结构，不需要预先为线性表分配足够大的空间，而是向系统"随用随取"，并且在删除元素时可同时释放空间。 　  (2) 用"指针"指示数据元素之间的后继关系，便于进行"插入"、"删除"等操作； 缺点： 不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的“表长”和数据元素在线性表中的“位序”，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 数据结构

44 循环链表 循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个环。从表中任一结点出发都可找到表中其他的结点。
空的循环链表由只含一个自成循环的头结点表示。 循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"。 a0 a1 an-1　 ai 数据结构

45 在循环链表中，有时使用尾指针，尾指针指向最后一结点，则从最后一个结点的指针又可立即找到链表的第一个结点。
在实际应用中，使用尾指针代替头指针来进行某些操作，往往更简单。如两个链表的合并。 void Merge(cLinkList *La, cLinkList *Lb) { p=Lb->next; Lb->next= La->next; La->next=p->next; free(p); } 数据结构

46 双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就在形成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般也增加一个头结点，指向双向链表的第一个元素。 和单链表类似，将双向链表的头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。 数据结构

47 双向链表的存储结构 类似于单链表，双向链表用如下的“结构指针”来描述。
typedef struct DuLNode{ 　　　　ElemType data; struct DuLNode *prior; 　　　　struct DuLNode *next; 　　　}DuLNode, *DuLinkList; 若d为指向表中某一结点的指针（即d为DuLinkList型的变量），则显然有： d->next->prior = d->prior->next = d; 　　　 数据结构

48 双向循环链表的建立 Status InitList_DuL(DuLinkList &L) { // 构造一个空的双向链表L。 L = (DuLinkList)malloc(sizeof(DuLNode)); if (!L) exit(ERROR); // 存储分配失败 L->prior = L; L->next = L; return OK; } // InitList_DuL 此算法的时间复杂度为O (1)。 双向链表中只涉及一个方向指针的操作，如Listlength、GetElem和LocateElem等与单链表的操作是相同的。 数据结构

49 双向循环链表的插入 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){ // 在带头结点的双链循环线性表L的第i个元素之前插入元素e， if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; if (!(s = (DuLinkList)malloc(sizeof(DuLNode)))) s->data = e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; } // ListInsert_DuL 此算法的时间复杂度为O (ListLength(L))。 数据结构

50 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
双向循环链表的删除 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){ // 删除带头结点的双链循环线性表L的第i个元素 if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; } // ListDelete_DuL 此算法的时间复杂度为O (ListLength(L))。 数据结构

51 线性表的应用举例 （一元多项式的表示及相加）
数学上，一个一元多项式Pn(x) 可以表示为 ： Pn(x)=p0+p1x+p2x2+…+pnxn 它由n+1个系数唯一确定。 因此，在计算机里，一元多项式Pn(x)可用一个线性表P： P =（p0,p1,p2,…,pn） 　 来表示，其中pi为系数，i为指数。 设Qn(x)是一元m次多项式，同样可用线性表Q来示： Q =（q0,q1,q2,…,qm） 不失一般性，设m<n，则两个多项式相加的结果Rn(x)= Pn(x)+ Qn(x)可用线性表R来表示： R =（p0+q0,p1+q1,p2+q2, …,pm+qm,pm+1,…,pn） 　　 数据结构

52 我们可以对P、Q和R采用顺序存储结构，甚至再简单一些，可以用三个n维的整数数组来进行一元多项式的相加。
但是在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。如 S(x) = 1 + 3x x2000 要用到一长度为20001的顺序表来表示，而表中只有3个非零元素，这种对内存空间的浪费是应该避免的。 为了避免上述内存空间的浪费，我们可以只存储非零系数。那么显然，此时我们还需要存储非零系数所对应的指数。 一般情况下的一元n次多项式可写成 Pn(x)=p1xe1+p2xe2+…+pmxem 其中，pi是指数为ei的项的非零系数，且满足 0<=e1<=e2<=…<=em=n 那么用一个长度为m，且每个元素有两个数据项（系数项和指数项）的线性表 ((p1,e1）,(p2,e2),…, (pm,em)） 来表示,且为依ei的大小顺序进行排列的有序表。 数据结构

53 假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点的数据域的指数项，有三种情况：
A17(x) = 7 + 3x + 9x8 + 5x17 B8(x) = 8x + 22x7 -9x8 多项式相加的运算规则如下： 假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点的数据域的指数项，有三种情况： （1）指针qa所指结点的指数值＜指针qb所指结点的指数值时，则保留qa指针所指向的结点，qa指针后移； （2）指针qa所指结点的指数值＞指针qb所指结点的指数值时，则将qb指针所指向的结点插入到qa所指结点前，qb指针后移； （3）指针qa所指结点的指数值＝指针qb所指结点的指数值时，将两个结点中的系数相加,若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。 -1 7 0 3 1 9 8 5 17 ∧ A 8 1 22 7 ∧ B 多项式的单链存储结构 数据结构

54 一元多项式的表示及相加的链表实现 typedef struct{ //项的表示，多项式的项作为LinkList的数据元素 　　float coef; //系数 　　 int expn; //指数 }ElemType; 数据结构

55 数据结构 void AddPolyn(LinkList &Pa, LinkList &Pb) {//多项式加法：Pa = Pa + Pb
qa = Pa->next; qb = Pb->next; qc = Pa; while (qa && qb) { if (qa->data.expn <qb->data.expn) { qc->next = qa; qc = qa; qa = qa->next; } else if(qa->data.expn ==qb->data.expn) { x = qa->data.coef + qb->data.coef; if(x == 0){ s = qa; qa = qa->next; free(s); s = qb; qb = qb->next; free(s); else{ qa->data.coef = x; qc->next = qa; qc = qa; qa = qa->next; s = qb; qb = qb->next; free(s); qc->next = qb; qc = qb; qb = qb->next; pc->next = pa ? pa : pb; // 插入剩余段 free(Lb); // 释放Lb的头结点 } // AddPolyn 数据结构

56 本章小结 线性表 线性表的顺序存储结构 线性表的链式存储结构 循环链表 双向链表 在解决实际问题时的灵活运用
常应用于主要是为查询而很少作插入和删除操作，表长变化不大的线性表。 线性表的链式存储结构 它是一种动态分配的结构，结点的存储空间可以随用随取，并在删除结点时随时释放，以便系统资源更有效地被利用。这对编制大型软件非常重要，作为一个程序员在编制程序时必须养成这种习惯。 循环链表 双向链表 在解决实际问题时的灵活运用 数据结构

57 作业2 数据结构