数据结构课件第2章

1、第二章 线性表 线性表的基本概念线性表：是由一组数据元素组成，线性表或者是一个空表，或者 可以写成a1,a2, ai, , an，其中ai是取自某个集合S 的元素。 当1in时，数据元素ai-1称为数据元素ai的直 接前趋，而称ai+1为ai的直接后继。 若一个数据元素由若干个数据项组成，则该数据元素又称为记录，含有大量记录的线性表又称为文件。 线性表中元素的个数称为该线性表的长度。 线性表的定义第二章 线性表 线性表的基本概念线性表：是由一组数据元 线性结构的特点1、数据元素的数据类型一致。2、数据元素之间的相对位置呈线性关系。3、存在唯一的一个被称做“第一个”和“最后一个”的数据元素。4、

2、除第一个和最后一个外，集合中每个数据元素均只有一个前驱和一个后继。 线性结构的特点1、数据元素的数据类型一致。Partition(L, L1, L2)： 将L拆分成L1和L2。Search(L, b): 查找满足条件b的数据元素。Sort(L)： 将L中所有数据元素进行排序（降序或者升序）。 Prior(L, elm)： 求元素elm的前驱。Next(L, elm)： 求元素elm的后继。Empty(L)： 判空表函数。Clear(L)： 表置空操作。 线性表可以进行如下运算： Initiate(L)： 初始化操作，设定一个线性表。 Length(L)： 长度的函数，返回元素的个数。 Acce

3、ss(L, i)： 访问第i个数据元素。 Insert(L, i, b)： 在第i个元素之前，插入元素b。 Delete(L, i)： 删除第i个元素。 Merge(L1, L2)： 合并L1和L2，合并结果保存在L1中。Partition(L, L1, L2)： 将L拆分成L1和 线性表的存储结构 在计算机中有不同的方法来表示线性表，最普通、最简单的方法是顺序映像或顺序分配，即采用一组连续的存储单元依次存储线性表中各数据元素。 顺序分配的存储结构采用向量结构：设线性表的长度为N，建立一向量V，用Vi表示第i个分量，第i个分量是线性表第i个元素ai在计算机存储中的映像，即Vi =ai。 顺序存

4、储结构一、顺序存储结构的定义 线性表的存储结构 在计算机中有不同的方法来表示存储地址内存状态元素序号空闲aaaa12in: :bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in线性表的顺序存储结构示意图 若线性表中的第一个存储元素的地址为LOCa1，每个元素占用L个存储单元，则表的第i个元素的存储地址为： LOCai=LOCa1+(i-1)*L LOCai=LOCai-1+L若每个元素仅占用1个存储单元，则表的第i个元素的存储地址为：LOCai=LOCa1+(i-1)存储密度d：d=数据元素的值所需的存储量/该数据元素所需的存储总量在顺序分配的存储结构中，所有的存储单元

5、空间全部被数据元素有效占用，因此，顺序分配结构的存储密度d=1。存储地址内存状态元素序号空闲aaaa12in: :二、顺序存储结构的插入和删除运算 1 删除运算例：设有长为n的线性表a1,a2, , an, 删除ai，并把它送入某单元Y。 Yaia1a2a3ai-1aian:123i-1in-1i+1n:a1a2a3ai-1an:123i-1in-1i+1n:ai+1顺序存储结构的删除操作二、顺序存储结构的插入和删除运算例：设有长为n的线性表a1,顺序存储结构的删除操作算法： 1、如果1=i=n，则将第i个元素送给y。反之，则退出。 2、从第i个存储单元开始，依次将第i+1个元素送给第i个存储

6、单元，将第i+2个元素送到第i+1个存储单元，直到将第n个元素送给第n-1个存储单元。 3、线性表长度减1。 4、返回。删除操作算法的时间复杂性： 1、假设删除每个数据元素的概率相等，即概率为1/n。 2、基本操作为移动数据元素。 3、平均移动次数为 4、所以，删除操作算法的时间复杂性为O(n)。顺序存储结构的删除操作算法：删除操作算法的时间复杂性：# define m 1000typedef struct L_stru int n; /*表长度为n*/ int am; /*数据元素向量为整型*/；void delete(L, i, y) /*删除数据元素函数*/ struct L_stru

7、L； /*定义参数类型*/int i, *y; int j; if(iL.n) /*判断删除数据元素的位置*/ printf(“The delete position is not correct ! n”); else *y=L.ai-1; /*a的下标从0开始，不是从1开始*/ for(j=i; j=L.n-1; j+) /*j=L.n-1即j=n-1*/ L.aj-1=L.aj; L.n=L.n-1; 删除操作算法的程序段：# define m 1000删除操作算法 2 插入运算例：设有长为n的线性表a1,a2, , an, 在第i位置插入新数据元素x。 顺序存储结构的插入操作xa1a2

8、a3ai-1aian:123i-1ini+1:a1a2a3ai-1an-1:123i-1ini+1n+1:aixan 2 插入运算例：设有长为n的线性表a1,a2, , 顺序存储结构的插入操作算法： 1、如果1=i=n+1，则插入数据元素x。反之，则退出。 2、从第n到第i个存储单元的数据元素，依次后移，腾出空位i：第n个元素送给第n+1个存储单元，将第n-1个元素送到第n个存储单元，直到将第i个元素送给第i+1个存储单元。 3、在空位i处插入元素x，线性表长度加1。 4、返回。插入操作算法的时间复杂性1: 1、假设在每个位置插入数据元素的概率相等，即概率为1/n。 2、基本操作为移动数据元素

9、。 3、平均移动次数为 4、所以，插入操作算法的时间复杂性为O(n)。顺序存储结构的插入操作算法：插入操作算法的时间复杂性1:顺序存储结构的插入操作算法： 1、如果1=i=n+1，则插入数据元素x。反之，则退出。 2、从第n到第i个存储单元的数据元素，依次后移，腾出空位i：第n个元素送给第n+1个存储单元，将第n-1个元素送到第n个存储单元，直到将第i个元素送给第i+1个存储单元。 3、在空位i处插入元素x，线性表长度加1。 4、返回。插入操作算法的时间复杂性2： 1、假设在每个位置插入数据元素的概率相等，即概率为1/(n+1)。 2、基本操作为移动数据元素。 3、平均移动次数为 4、所以，插

10、入操作算法的时间复杂性为O(n)。顺序存储结构的插入操作算法：插入操作算法的时间复杂性2：顺序存储结构的插入操作算法： 1、如果1=im) printf(“The list is overflow ! n”); /*溢出*/ else if (iL.n+1) /*判断插入数据元素的位置*/ printf(“The insertion position is not correct ! n”); else if ( i !=L.n+1 ) /*在线性表最末插入不必移动*/ for (j=L.n-1;j=i-1;j-) /*依次移动元素*/ L.aj+1=L.aj; L.n=L.n+1; /*线性

11、表长度加1*/ L.ai-1=x; /*在空位i处插入x*/ 插入操作算法的程序段：# define m 1000插入操作算法的程序段：一、单链表线形链表：在线形表中每一个元素的值和该表中下一个元素的地址放在一起，这两个部分的信息组成一个结点，若干个这样的结点构成了一个线形链表。 链式存储结构在线性链表的存储结构中，若数据域与指针域所需的存储单元空间相等，则线性链表的存储密度d=0.5。ai+1结点的地址ai（指针域）（数据域）逻辑结构中的数据元素ai 对应存储结构中的结点为：一、单链表线形链表：在线形表中每一个元素的值和该表中下一个元例：用图形表示线性表BAT,CAT,HAT,KAT,VAT

12、,WAT的存储结构。地址数据顺序分配 BAT CAT HAT KAT VAT WAT NULLL0+IL0L0+2IL0+3IL0+4IL0+5IL0+6I地址数据指针链接分配初ABCDEF KATF WATNULL CATD HATA BATC VATBE指针表示头指针head BATHATCATKATVATWAT顺序表的特点：可以随机存取表中的任一元素；在作插入和删除操作时,需移动大量的元素。线性表的链式存储结构：用任意的存储单元存储线性表的数据元素。用链指针体现线性表中数据元素之间的逻辑关系。例：用图形表示线性表BAT,CAT,HAT,KAT,VAT单链表的插入操作：例：如图所示链表，表

13、头指针为head，欲在值为y的数据元素处插入新数据元素x。rxheada1ai-1yanqprxheada1ai-1yanqp单链表的插入操作：例：如图所示链表，表头指针为head，欲在单链表的插入位置可能有4种情况：1）原来链表为空表，则插入结点作为表头结点；2）在链表第1个结点位置插入，则插入结点为新表头结点，原来的表头结点成为第2个结点；3）在链表中间位置插入，则注意修改插入位置前后指针域；4）如果根本不存在所指定结点，则在链表尾部插入结点。考虑所有可能情况的程序如下页：单链表的插入位置可能有4种情况：1）原来链表为空表，则插入结typedef struct node /*定义结点的结构

14、*/ /*程序如下*/ int data; struct node *next;；void insert_link (head, x, y) /*在元素y处插入元素x*/struct node *head; /*定义参数*/int x, y; struct node *q, *p, *r; r=(struct node *) (malloc (sizeof (struct node); /*分配存储空间给r*/ rdata=x; /*元素x保存在r的数据域*/ if (head= =NULL) /*空表，r为唯一结点*/ head=r; rnext=NULL; else if (headdat

15、a= =y) /*第1个结点为y*/ rnext=head; head=r; typedef struct node else q=head; p=headnext; while (p !=NULL) /*循环查找*/ if (pdata !=y) q=p; p=pnext; else break; if (p !=NULL) /*在p指针指向结点处插入新结点r*/ qnext=r; rnext=p; else /*没有值为y的结点，在表尾插入新结点r*/ qnext=r; rnext=NULL; else单链表的删除操作：例：如图所示链表，表头指针为head，欲删除数据域为x的结点。head

16、a1ai-1xan释放该结点空间ai+1rqpnextheada1ai-1xanqpai+1pnext单链表的删除操作：例：如图所示链表，表头指针为head，欲删单链表的删除操作可能有4种情况：1）链表为空表，则没有数据元素可以删除。2）被删除结点为链表的第1个结点，存在两种情况：仅有头结点情况，删后为空表；链表有多个结点情况，头指针需要改变。3）在链表中间位置删除，则注意修改删除位置前后指针域；4）否则查找到链表末，根本不存在所指定结点。考虑所有可能情况的程序如下页：单链表的删除操作可能有4种情况：1）链表为空表，则没有数据元typedef struct node /*定义结点的结构*/ /

17、*程序如下*/ int data; struct node *next;；void delete_link (head, x) /*删除元素x的函数*/struct node *head; /*定义参数*/int x; struct node *q, *p, *r; if (head= =NULL) /*空表*/ printf (“The link list is empty ! n”); else if (headdata = =x) /*第1个结点为x*/ p=head; if (headnext= =NULL) /*仅有头结点情况，删后为空表*/ head=NULL; else head

18、=headnext; /*链表有多个结点情况，头指针需要改变*/ free (p); typedef struct node else p=head; q=p; while (p != NULL) /*循环查找*/ if (pdata !=x) q=p; p=pnext; else break; if (p !=NULL) /*删除p指针指向的结点x*/ r=p; qnext =pnext; free (r); else /*查找完整个链表，没有结点x*/ printf (“x element is not in the link list ! n”); else 二、循环链表 将单链表的最后

19、一个结点的指针域next指向它的头结点所得的链表。如下图所示，访问结点更加方便。H单循环链表空单循环链表HH带表头结点的单循环链表 为了可以统一地表示和处理空表和非空表的情况，在循环链表的第一个结点前增加一个特殊的表头结点。如下图所示。二、循环链表 将单链表的最后一个结点的指针域n三、双向链表 若只有一个指针域，指向该结点的后继，如果要找到它的前趋结点，则需要从表头指针出发。为此要作以下扩充： 每个结点包括三个域：一个数据域，两个指针域：一个指向前趋，称为左链域 llink，一个指向后继，称为右链域 rlink。由此形成双向链表。 其每个结点的物理结构、双向链表、循环双向链表如下所示：结点的物

20、理形式 llinkdatarlinkHBCDA双向链表HBCD循环双向链表A空循环双向链表P三、双向链表 若只有一个指针域，指向该结点的后循环双向链表中插入操作 在结点值域为x的结点右边插入一个值为y的新结点，过程为：1）设立一个搜索指针p，循环地在链表中进行查找。2）若查找到指定的结点，则在其后插入新结点，并修改相关结点的指针域值。3）如果查找不到值为x的结点，则在链表尾插入新结点y。 双向链表结点的指针域存在如下关系： p =prlinkllink =pllinkrlink 插入前指针状态Hxpr插入后指针状态Hxpyqr循环双向链表中插入操作 双向链表结点的指针域存在如下关系：用C语言描

21、述插入操作如下：typedef struct node struct node *llink; /*定义指向直接前驱的指针*/ int data; /*定义数据类型*/ struct node *rlink; /*定义指向直接后继的指针*/; void insert_bilink (head, x, y)struct node *head;int x, y; struct node *p, *q, *r; q= (struct node *) (malloc (sizeof (struct node); /*建立新结点q*/ qdata=y; /*对建立的新结点q进行赋值为y*/ 用C语言描述

22、插入操作如下： if (head = = NULL) /*空表，插入结点y为循环双向链表的唯一结点*/ head=q; qllink=head; qrlink=head; else if (headdata = = x) /*非空表，第1个结点为x，在其右插入y*/ qrlink=headrlink; headrlinkllink=q; headrlink=q; qllink=head; if (head = = NULL) /*空表 else r=head; /*r指针指向当前结点p的前驱结点*/ p=headrlink; while (p !=head) /*指针r一直查找到表尾，指针p一

23、直查找到表头*/ if (pdata !=x) /*当没有找到x时，指针r和p同时前移一个结点*/ r=p; p=prlink; else /*当找到x或指针r指向最后一个结点，退出*/ break; else if (p !=head) /*当在链表中间某个位置找到x时，在指针p右边插入*/ qrlink=prlink; /*将q的后继指向p的后继*/ qrlinkllink=q; /*将q的后继的前驱指向q*/ prlink=q; /*p的后继指向q*/ qllink=p; /*q的前驱指向p*/ else /*当没有找到x时，在指向链表最后1个结点的指针r右边插入*/ qrlink=he

24、ad; qllink=r; rrlink=q; headllink=q; if (p !=head) /*当在循环双向链表中删除操作 在循环双向链表中，删除值域为x的结点，过程为：1）设立一个搜索指针p，循环地在链表中进行查找。2）若查找到值域为x的指定结点，则进行删除，并修改相关结点的指针域值。3）如果查找不到值为x的结点，则输出提示信息。 删除前指针状态Hxp删除后指针状态Hxp释放该结点空间循环双向链表中删除操作删除前指针状态Hxp删除后指针状态Hx用C语言描述删除操作如下：typedef struct node struct node *llink; /*定义指向直接前驱的指针*/ i

25、nt data; /*定义数据类型*/ struct node *rlink; /*定义指向直接后继的指针*/; void delete_bilink (head, x)struct node *head;int x; struct node *p, *q, *r; 用C语言描述删除操作如下： if (head = = NULL) /*空表，无结点可删*/ printf (“The bidirectional loop link-list is empty ! n”); else if (headdata = = x) /*非空表，第1个结点为x，删除第1个结点*/ p=head; if (h

26、eadrlink = = head) /*链表仅有唯一一个结点，且为结点x*/ head=NULL; else /*链表中有多个结点，第1个为结点x*/ headrlinkllink= headllink; headllinkrlink= headrlink; head=headrlink; free (p); if (head = = NULL) else /*非空表，且值为x的结点不在第1个位置*/ p=headrlink; /*p指针前移，指向第2个结点*/ while (p !=head) /*指针p一直查找，循环到表头*/ if (pdata !=x) /*当没有找到x时，指针p前移

27、一个结点*/ p=prlink; else /*当找到结点x，退出*/ break; if (p !=head) /*当在链表中某个位置找到x时，删除指针p指向的结点*/ pllinkrlink=prlink; /*p的前驱的后继指向p的后继*/ prlinkllink=pllink; /*p的后继的前驱指向p的前驱*/ free (p); /*释放该结点所占用的存储空间*/ else /*当没有找到x时，提示信息*/ printf (“No x element in the bidirectional link-list ! n”); else 多项式概述 多项式的算术运算，已经成为线性表处

28、理的一个经典问题，可用两种链表(线性链表或循环线性链表)来表示多项式，研究两个多项式相加运算。 一般多项式的形式为： Pn (x) = p1 xe1 + p2 xe2 + pn xen 其中：pi为多项式的系数，ei为多项式的指数，且满足： 0 e1 e2 en 设一个多项式有n个非零项，n个（带表头结点时为n+1个）结点的线性链表就能唯一的确定这个多项式。设该线性链表有三个域：系数域coef ，指数域exp，指针域next。如下图所示。 expcoefexpcoefcoefexp.p 多项式概述 多项式的算术运算，已经成为线性 多项式相加运算规则：若两指数相等，则系数相加；若两指数不相等，则

29、按指数大小次序分别复制相应的两项。解：用线性链表的形式表示上面的两个多项式，如下图所示。pa13506302104310 PAH1050-630-55PBHpb例：计算下面两个多项式的相加结果,并在PCH中存放结果。 PAH=13X50+6X30+2X10+4X3+1 PBH=10X50-6X30-5X5+3X2 上面两个多项式相加，相加2次，比较6次，主要操作共8次；而PAH有5项，PBH有4项，共9项；相加或比较次数跟多项式的长度正相关。 结论：设多项式PAH有m项，PBH有n项，则相加的时间复杂性为O(m+n)。32pc2350210-554332 PCH10 多项式相加运算规则：若两指

30、数相等，则系数相加；若两指数不算法描述如下： 1、若paexp = pbexp，则俩coef域相加。若相加结果不等于0 ，则写入pc链表中；若相加结果为0，则不写入该结点。指针pa和pb后移。 2、paexp pbexp，则把pa所指结点写入pc链表中。指针pa后移。 3、paexp pbexp) /*pa指数大于pb指数时*/ pc=create_item (pc, pacoef , paexp); pa=panext; /* 则pa后移*/ else /*pb指数大于pa指数时*/ pc=create_item (pc, pbcoef , pbexp); pb=pbnext; /* 则pb

31、后移*/ while (pa != NULL) /* 复制pah链表剩余结点*/ pc=create_item (pc, pacoef , paexp); pa=panext; /* 则pa后移*/ while (pb != NULL) /* 复制pbh链表剩余结点*/ pc=create_item (pc, pbcoef , pbexp); pb=pbnext; /* 则pb后移*/ else if (paexp pcnext =NULL; /*尾结点指针赋空*/ pc=pch; /*指针pc指向头结点*/ pch=pchnext; /*指针pch指向第1个结点*/ free(pc); /*

32、删除临时头结点*/ pcnext =NULL; 数组的定义及其运算数 组 数组是线性表的推广，它是由下标和值组成的偶对（下标，值）的一个集合。即在数组中，对于每一组有定义的下标i1，i2，in总是有一个固定的数值（数据元素）与之对应，这样的数组称为n维数组。例2：二维数组Am*n可定义为：例1：一维数组An可定义为：下标i对应ai下标i, j对应aij 数组的定义及其运算数 组 数组是线性表的推广 也可把数组看成这样一个线性表：它的每个数据元素仍是一个线性表。 如上例2中：A=a1，a2，an，其中每个aj是一个列向量的线性表（即列线性表），aj= a1j，a2j ， ，amj，1j n ；同

33、理也可用行向量表示（即行线性表）。行（列）线性表说明了矩阵的线性二维性。 数组通常只有两种运算：1、Value (array, index)：给定数组array的下标index，存取相应的数据元素2、Assign (array, index, value)：给定数组array的下标index，赋予或修改相应数据元素的值为value。 也可把数组看成这样一个线性表：它的每个数据元 数组的顺序存储结构 由于存储单元是一维结构，而数组是多维结构，则用一组连续的存储单元存放数组的数据元素就有个次序约定，主要有两种方式：1、以行序为主: 有C/C+，BASIC，COBAL，PASCAL；2、以列序为主:

34、 有FORTRAN，MATLAB。 数组的顺序存储结构 由于存储单元是一维结构， 对数组而言，一旦规定了数组的维数和各维的上下界限，便可为它分配存储空间；反之，只要给出一组下标便可求得相应数组元素的存储位置。a11:a1na21:a2n:amna1a11:am1a12:am2:amna1以行为主以列为主 对数组而言，一旦规定了数组的维数和各维的上下界限 数组的存储地址计算公式 1. 一维数组 长度为n的一维数组 An A0, A1, A2, , An-1 ，数组首地址为LOC(A0)，则数组中任一元素Aj （第j1个元素）的地址LOC(Aj)的计算公式为： LOC(Aj) LOC(A0)j；（

35、数组下标从0开始，每个元素存储空间为1） LOC(Aj) LOC(A0)j*L；（数组下标从0开始，每个元素存储空间为L） 以行序为主 数组的存储地址计算公式 1. 一维数组 2. 二维数组 长度为m*n的二维数组 Am*n，数组首地址为LOC(A0, 0)，则数组中任一元素Ai, j （第i1行、第j1列元素）的地址LOC(Ai, j)的计算公式为：LOC(Ai, j)= LOC(A0, 0)+(i*n+j); （每个元素存储空间为1）LOC(Ai, j)= LOC(A0, 0)+(i*n+j) *L; （每个元素存储空间为L） 2. 二维数组 3. 三维数组 长度为d1*d2*d3的三维数

36、组 Ad1*d2*d3，数组首地址为LOC(A0, 0, 0)，则数组中任一元素Ai1, i2, i3 的地址LOC(Ai1, i2, i3)的计算公式为：LOC(Ai1, i2, i3 )= LOC(A0, 0, 0)+(i1*d2*d3+i2*d3+i3); LOC(Ai1, i2, i3 )= LOC(A0, 0, 0)+(i1*d2*d3+i2*d3+i3)*L; 3. 三维数组 4. n维数组 各维长度为d1, d2, d3, dn 的n维数组A，数组首地址为LOC(A0,0)，则数组中任一元素Ai1,in 的地址LOC(Ai1,in)的计算公式为：LOC(Ai1,in )= LOC

37、(A0,0)+(i1*d2*d3*dn+i2*d3*d4*dn+in-1*dn+in)*L; 4. n维数组 n维数组 各维长度为d1, d2, d3, dn 的n维数组A，数组首地址为LOC(A0,0)，则数组中任一元素Ai1,in 的地址LOC(Ai1,in)的计算公式为：LOC(Ai1,in )= LOC(A0,0)+(in*d1*d2*dn-1+in-1*d1*d2*dn-2+i2*d1+i1)*L; 以列序为主 n维数组 以列序为主例：有如下数组定义 float a1054;1、若数组a的首地址为1200，求数组元素a345在按行存储方式下的地址？2、其按列存储方式下的地址？ 注：s

38、izeof(float)=4解：d1=10, d2=5, d3=4; i1=3, i2=4, i3=5;1、LOC(a345)=1200+(i1*d2*d3+i2*d3+i3)*L =1200+(3*5*4+4*4+5)*4=1524;2、LOC(a345)=1200+(i3*d1*d2+i2*d1+i1)*L =1200+(5*10*5+4*10+3)*4=2372;例：有如下数组定义解：d1=10, d2=5, d3=4; 矩阵的压缩存储 特殊矩阵 特殊矩阵：值相同，或非零元素在矩阵中的分布有一定的规律，或矩阵元素本身的数值分布具有一定规律。 对称矩阵 如：n阶对称矩阵：一个n阶对称矩阵A中的元素有下述性质： aij=aji， 1=i， j = n。 n阶对称矩阵中有一半元素是相同的。还有的矩阵中只有上三角或下三角中的元素不为0，为节省空间，采用压缩存储，只存储下三角或上三角的元素。 矩阵的压缩存储 特殊矩阵 特殊矩阵：值相同，或非 例：如果一个4阶对称矩阵A如下所示，只存储下三角元素，则可用如下的一数组元素表示：01234567894352651079 仅需要存储的下三角元素个数123410 个数组下标 例：如果一个4阶对称矩阵A如下所示，只存储下三 例：如果一个n阶对称矩阵A只存在下三