DS02-线性表(1)

1、精选课件1 第二章第二章 线性表线性表 21线性表概念 定义：具有相同类型的N个数据元素a0、a1、an-1 的有限系列称为线性表。表示为A=（a0、a1、an-1 ）。数据元素的个数n为线性表长度，长度为零的线 性表称为空表。 说明： 1 一个线性表可用一个标识符来命名，如A=（a0、a1 、an-1）。 2 线性表中的元素要求具有相同的类型。 3 表中的两相邻元素ai、ai+1，称ai是ai+1的前驱元素， 而ai+1是ai的后继元素。 4 线性表中数据元素的相对位置是固定的。 精选课件2 22线性表存储结构 2.2.1 顺序存储方法： 存储方法：在内存开辟一块连续的存储空间用 来依次存放

2、表中的每个元素。 元素位置确定：设有线性表A=（a0、a1、 an-1），由于A中的元素具有相同类型，且占s 字节，那么元素ai的地址为 ai= int n; 精选课件5 如：#define MAXSIZE 100 struct char 学号； char 姓名； int 数据结构； int 操作系统； int 离散数学； int 英语listMAXSIZE； int n; 精选课件6 2 线性表的创建程序： 设list为已定义的存放线性表的数组，n为线 性表的长度。 Void creat_sq_list(int n,list) int i; for (i=0;in;i+) scanf(“%d

3、”, 精选课件7 2.2.2链接存储方法 存储方法： 1 结点：线性表的每个元素除了需要存储自身 的信息外，还需要存储一至两个指示其直接后 继元素或直接前驱元素的地址（链接指针）， 这两部分信息就组成了一个数据通信元素的存 储结构，常称为结点。 2 链表：线性表的各个元素之间的关系用链接 指针把它们连接起来，从而构成链表。 精选课件8 精选课件9 精选课件10 3 单向链表和双向链表： 单向链表：每一个结点只设一个指针域指向其 直接后继结点； 双向链表：每一个结点应有两个指针域，一个 指向直接前驱、另一个指向直接后继结点。 精选课件11 二、单链表中元素位置的确定 链表中任意元素的存储地址只能

4、通过表头指针顺 着链接指针遍历链表结点而得到。 三、线性链表的创建 1 结点的表示及产生 在C中可以用一个包含数据域和指针域的结构体来 表示线性链表的结点。 typedef struct nodechar data; struct node *link1; struct node *link2; NODE; 链表结点通过(NODE*)malloc(sizeof(NODE)函数获得。 精选课件12 线性链表的创建程序 建立n个结点的单链表函数，返回链表的头指针。 NODE *creat_link_list(int n) int i; NODE *head,*p,*q; /*p指向正链表最后结点,

5、q指向新申请结点*/ if (n=0)return(NULL); /*结点数为0返回空表*/ head=(NODE*)malloc(sizeof(NODE); /*申请建立第一个结点*/ p=head; for (i=1;idata); /*输入结点元素的值*/ q= (NODE*)malloc(sizeof(NODE); /*申请建立下一个结点*/ p-link=q; p=q; scanf(“%c”, /*输入最后一个结点的值*/ p-link=NULL; /*最后结点指针置空*/ getchar(); /*暂停*/ return(head); /*返回建成链表的头指针*/ 精选课件13 四

6、、单链表的几种变化形式 1 循环链表：链表中最后一个结点的指针域指向第一个 结点(原单链表末结点置NULL处改为置头指针即可) 2 带表头结点的链表 3带表头结点的循环链表 Head Head Head Head Head 精选课件14 五、双向链表的几种变化形式 1 双向循环链表：链表中最后一个结点的指针域指向第 一个结点 2 带表头结点的双向链表 3带表头结点的双向循环链表 HeadHead 精选课件15 2.3.3 其他存储方法 一、索引存储 把线性表A中的结点划分成子线性表A0A m-1，划 分方法是将A中的具有某种性质的元素归并到同一个 子表中，常使用索引函数来计算出每个元素的索引值

7、 i,将相同索引i值的元素归并到同一个Ai中。 再使用顺序或链接存储方法来存储索引表X和子线 性表A0A m-1。一般情况下索引表用顺序存储，而子 线性表用链接存储方法。 实例见P18 精选课件16 a b c d apple car bear duck busbird cat dog 例: 线性表A=(apple,cat,bus,dog,duck,bear,bird,car)使用索引函数： index(key)=(key的第1个字母ASCII码)-(a的ASCII码)。 则把A划分为A0=(apple), A1=(bus,bird,bear), A2=(cat,car), A3=(dog,d

8、uck) x0 X1 x2 x3 精选课件17 二、分块存储 把线性表A划分成若干块，每一块中的元素顺序是 任意的，但块与块的之间必须按关键字大小排列， 再建立一个索引表，索引表中的一项对应于表中一 块，索引项由大小域(块中的元素个数)、键域(块中最 大值)和链域(结点指针)。 实例见P19. 精选课件18 053015243548393850607065 第一块第二块第三块 058 534 354870 链链 域域 大小大小 域域 键键 域域 分块有序表分块有序表 精选课件19 三、压缩存储 若线性表A=(a0、a1、an-1)中有很多具有相同值 的元素V,由A构造A=(0,a0)、(1,a

9、1 ) 、(n-1,an-1 ), 将A中的所有(j,v)元素删除，得到线性表达式A。 再将A中的元素以顺序或链接方式存储。 例：A=(12,0,0,11,0,18,0,0,17,0,16,0,0,0,15) 经压缩处理后 A=(0,12), (3,11), (5,18), (8,17), (10,16), (14,15) 再对A进行顺序或链接存储。 精选课件20 四、散列存储(HASH函数) 基本思想：把线性表中的每个元素的值K通过一个函数H(k)转换 成该元素在一块连续存储空间(数组)的单元地址(下标)来存放。 实现关键字到地址映射的函数h(k)称为散列函数或哈希(Hash)函 数，h(k

10、)的值称散列地址或哈希地址，用于线性表进行散列存储 的地址空间(数组)称为散列表或哈希表。 冲突问题：有ki=kj,但有H(ki)=H(kj),出现地址冲突。 散列函数构造：原则：减少冲突、计算简单； 常用方法：直接定址、除留余数法等。 冲突处理：开放定址法、链接法。 实例见P23 精选课件21 2.3 线性表的基本运算 2.3.1 线性表的运算概述 1 创建一个空线性表； 2 求线性表的长度； 3 查找表中的第i个元素 4 根据已知关键字求在线性表的位置； 5 在线性表中第i个元素位置插入一个新元素； 6 修改线性表中元素的值； 7 删除线性表中第i个元素； 8 对线性表中的元素按关键字排序

11、； 9 复制一个线性表； 10 合并线性表； 11 拆分线性表； 12 打印线性表（输出线性表）。 精选课件22 2.3.2 线性表的插入 一、插入运算 有长度为n的线性表(a0、a1、an-1 ),现将元素值 为x的元素插入线性表中，使之变为(a0、a1、 ai-1 、x、 ai 、 an-1 )，其长度变为n+1。 二、顺序存储的线性表的插入 算法： 1 将ai、ai+1、 an-1 依次后移一个位置，留 出位置i; 2 将新元素x存入位置i; 3 线性表长度加1。 软件实现见C程序。 精选课件23 int sq_ins(list,n,i,x) int list; int *n; int

12、i,x; int j; if(i*n) return(1); if(*n=MAXSIZE) return(2): for(j=*n;ji,j-) listj=listj-1; listi=x; (*n)+; return(0); 精选课件24 1、算法、算法 创建新结点 newnode=(NODE)malloc(sizeof(NODE); newnode-data=x; 确定插入位置：从头结点顺序搜索i-1次即到达i-1个结点p; 修改指针：newnode-link=p-link; p-link=newnode; Head Head 精选课件25 newnodelink = head ; he

13、ad = newnode； 精选课件26 newnodelink = plink; plink = newnode； 精选课件27 newnodelink = plink; plink = last = newnode； 精选课件28 2.3.2 线性表的删除 一、删除运算 将长度为n的线性表删除第I个元素，使其长度变 为n-1的线性表。 二、顺序存储的线性表删除 算法：从顺序存储的线性表中删除ai的步骤是：领奖将ai+1, ai+2, an-1依次前移一位，线性表长度减1。 实现程序：见sq_del(list,n,i)。 int sq_del(list,n,i) int list, *n,

14、i; int j; if(i*n) return(1); /*第1种情况，i不在可删除位置上*/ for(j=i+1;jlink; p-link=q-link; 精选课件30 2 实现程序： 通过函数link_del()实现上述链表的删除算法。 int link_del(head,i) /*head为链表头指针，I为被删元素位置*/ NODE *head; int i; int j; NODE *p,*q; if(q=NULL)return(1); /*不能删除情况1*/ if(i=0) /*删除头结点*/ q=*head; *head=q-link; free(q); /*修改指针*/ re

15、turn(0); j=0; p=*head; while (+ jlink; if (I0|jlink; p-link=q-link;free(q); /*修改指针,释放空间*/ return(0); 精选课件31 精选课件32 newnodelink = plink; if ( plink =NULL ) last = newnode; plink = newnode; 精选课件33 q = plink; plink = qlink; delete q; if ( plink = NULL ) last = p; 精选课件34 精选课件35 精选课件36 精选课件37 精选课件38 2.4

16、线性表的应用举例: 一、一元多项式的线性表示 一般的n次多项式A(x)按降幂排列，记为： A(x)=anxn+ an-1xn-1+.+ a1x1 +a0，当an0j时称A(x)为n阶多项式。 在数据结构中,一个n阶多项式可用一个线性表A表示： A=（ an， an-1 ， an-2，.， a1， a0 ） 由于多项式中系数不为零的很少，例如： A(x)=8x3000+ 3 为了节约存储空间，应用中只需将多项式中不为零的系数与对 应的幂次数用两个数据项进行描述，并表示成线性表，则有： A=（( am， em)， ( am-1， em-1)，.，( a1， e1)，( a0， e0)） 二、多项式

17、的加法： 一元多项加法运算原则：两个多项式中所有指数相同的项 对应系数相加，若和不为零，则构成“和多项式”中的一项 ，而所有指数不相同的那些项，均应复制到“和多项式中” 。 精选课件39 多项式加法的算法描述多项式加法的算法描述： 设设A A、B B分别表示两个线性表，分别表示两个线性表， A A和和B B相加的结果构成线性表相加的结果构成线性表C,C,其操作步骤如下：其操作步骤如下： 线性表线性表C C置空；置空； 各取线性表各取线性表A A和和B B的第一个元素分别作为各自线性表当前处理的第一个元素分别作为各自线性表当前处理 的元素的元素 比较当前处理的两个元素的指数值，若指数相等且它们相

18、加比较当前处理的两个元素的指数值，若指数相等且它们相加 后的系数和不为零，则把系数和与指数值构成一个数据元素加后的系数和不为零，则把系数和与指数值构成一个数据元素加 到线性表到线性表C C中，各取中，各取A A和和B B的下一个元素进行处理，若指数不等的下一个元素进行处理，若指数不等 ，则把指数大的数据元素追加到，则把指数大的数据元素追加到C C中，再取该元素所在表的下中，再取该元素所在表的下 一元素，另一表的当前处理元素不变；一元素，另一表的当前处理元素不变； 重复步骤重复步骤 2.4.2 2.4.2 多项式加法的顺序存储实现方法多项式加法的顺序存储实现方法 一、数据元素的定义：一、数据元素的定义： # define MAXN 100 typedef struct term float coef; int exp; TERM; TERM polyMAXN; A(x) =4x80 + 7x60 +9x5+5 B(x) =2x80 - 7x60 +3x12 精选课件40 A(x) =4x80 + 7x60 +9x5+5 B(x) =2x80 - 7x60 +3x12 两多项式系数与指数在结构数组两多项式系数与指数在结构数组poly中的存储表示为中的存储表示为 47952-73. 806050806012. 0 1 2 3 4 5 6 7 8 MAXN-