《ds02_线性表》由会员分享，可在线阅读，更多相关《ds02_线性表（45页珍藏版）》请在金锄头文库上搜索。
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 线性表中数据元素的相对位置是固定的。,22线性表存储结构 2.2.1 顺序存储方法：,存储方法：在内存开辟一块连续的存储空间用来依次存放表中的每个元素。 元素位置确定：设有线性表A=（
2、a0、a1、an-1），由于A中的元素具有相同类型，且占s字节，那么元素ai的地址为 ai=&a0+i*s。 对线性表的顺序存储常采用数组来实现。这是因为数组具有如下特性：,一维数组的特点,连续存储的线性表（别名 向量） 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,线性表的创建： 1 用数组表示线性表： 如： #define MAXSIZE 100 int listMAXSIZE; int n;,如：#define MAXSIZE 100 struct char 学号； char 姓名； int 数据结构； int 操作
3、系统； int 离散数学； int 英语listMAXSIZE； int n;,2 线性表的创建程序： 设list为已定义的存放线性表的数组，n为线性表的长度。 Void creat_sq_list(int n,list) int i; for (i=0;in;i+) scanf(“%d”, ,2.2.2链接存储方法 存储方法： 1 结点：线性表的每个元素除了需要存储自身的信息外，还需要存储一至两个指示其直接后继元素或直接前驱元素的地址（链接指针），这两部分信息就组成了一个数据通信元素的存储结构，常称为结点。,2 链表：线性表的各个元素之间的关系用链接指针把它们连接起来，从而构成链表。,单链表
4、 (Singly Linked List),特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充,单链表的存储映像,3 单向链表和双向链表： 单向链表：每一个结点只设一个指针域指向其直接后继结点； 双向链表：每一个结点应有两个指针域，一个指向直接前驱、另一个指向直接后继结点。,二、单链表中元素位置的确定,链表中任意元素的存储地址只能通过表头指针顺着链接指针遍历链表结点而得到。,三、线性链表的创建,1 结点的表示及产生 在C中可以用一个包含数据域和指针域的结构体来表示线性链表的结点。,typedef struct nodechar data; struct no
5、de *link1; struct node *link2; NODE;,链表结点通过(NODE*)malloc(sizeof(NODE)函数获得。,线性链表的创建程序 建立n个结点的单链表函数，返回链表的头指针。,NODE *creat_link_list(int n) int i; NODE *head,*p,*q; /*p指向正链表最后结点,q指向新申请结点*/ if (n=0)return(NULL); /*结点数为0返回空表*/ head=(NODE*)malloc(sizeof(NODE); /*申请建立第一个结点*/ p=head; for (i=1;idata); /*输入结点
6、元素的值*/ q= (NODE*)malloc(sizeof(NODE); /*申请建立下一个结点*/ p-link=q; p=q; scanf(“%c”, /*返回建成链表的头指针*/,四、单链表的几种变化形式,1 循环链表：链表中最后一个结点的指针域指向第一个结点(原单链表末结点置NULL处改为置头指针即可),2 带表头结点的链表 3带表头结点的循环链表,Head,五、双向链表的几种变化形式,1 双向循环链表：链表中最后一个结点的指针域指向第一个结点,2 带表头结点的双向链表 3带表头结点的双向循环链表,2.3.3 其他存储方法,一、索引存储,把线性表A中的结点划分成子线性表A0A m-1
7、，划分方法是将A中的具有某种性质的元素归并到同一个子表中，常使用索引函数来计算出每个元素的索引值i,将相同索引i值的元素归并到同一个Ai中。 再使用顺序或链接存储方法来存储索引表X和子线性表A0A m-1。一般情况下索引表用顺序存储，而子线性表用链接存储方法。,实例见P18,例: 线性表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,duck),二
8、、分块存储,把线性表A划分成若干块，每一块中的元素顺序是任意的，但块与块的之间必须按关键字大小排列， 再建立一个索引表，索引表中的一项对应于表中一块，索引项由大小域(块中的元素个数)、键域(块中最大值)和链域(结点指针)。,实例见P19.,第一块,第二块,第三块,分块有序表,三、压缩存储,若线性表A=(a0、a1、an-1)中有很多具有相同值的元素V,由A构造A=(0,a0)、(1,a1 ) 、(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) 经
9、压缩处理后 A=(0,12), (3,11), (5,18), (8,17), (10,16), (14,15) 再对A进行顺序或链接存储。,四、散列存储(HASH函数),基本思想：把线性表中的每个元素的值K通过一个函数H(k)转换成该元素在一块连续存储空间(数组)的单元地址(下标)来存放。 实现关键字到地址映射的函数h(k)称为散列函数或哈希(Hash)函数，h(k)的值称散列地址或哈希地址，用于线性表进行散列存储的地址空间(数组)称为散列表或哈希表。,冲突问题：有ki=kj,但有H(ki)=H(kj),出现地址冲突。,散列函数构造：原则：减少冲突、计算简单； 常用方法：直接定址、除留余数法
10、等。,冲突处理：开放定址法、链接法。,实例见P23,2.3 线性表的基本运算 2.3.1 线性表的运算概述 1 创建一个空线性表； 2 求线性表的长度； 3 查找表中的第i个元素 4 根据已知关键字求在线性表的位置； 5 在线性表中第i个元素位置插入一个新元素； 6 修改线性表中元素的值； 7 删除线性表中第i个元素； 8 对线性表中的元素按关键字排序； 9 复制一个线性表； 10 合并线性表； 11 拆分线性表； 12 打印线性表（输出线性表）。,2.3.2 线性表的插入 一、插入运算 有长度为n的线性表(a0、a1、an-1 ),现将元素值为x的元素插入线性表中，使之变为(a0、a1、 a
11、i-1 、x、 ai 、 an-1 )，其长度变为n+1。,二、顺序存储的线性表的插入 算法： 1 将ai、ai+1、 an-1 依次后移一个位置，留 出位置i; 2 将新元素x存入位置i; 3 线性表长度加1。,软件实现见C程序。,int sq_ins(list,n,i,x) int list; int *n; int 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); ,三、链接存储的线性表插入,1、算法 创建新结
12、点 newnode=(NODE)malloc(sizeof(NODE); newnode-data=x; 确定插入位置：从头结点顺序搜索i-1次即到达i-1个结点p; 修改指针：newnode-link=p-link; p-link=newnode;,插入的三种情况 第一种情况：在第一个结点前插入 newnodelink = head ; head = newnode；,（插入前） （插入后）,(插入前) (插入后),第二种情况：在链表中间插入 newnodelink = plink; plink = newnode；,第三种情况：在链表末尾插入 newnodelink = plink; pl
13、ink = last = newnode；,(插入前) (插入后),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, i; int j; if(i*n) return(1); /*第1种情况，i不在可删除位置上*/ for(j=i+1;j*n;j+) /*第2种情况,正常删除，注意删除方
14、向*/ listj-1=listj; /*前移1 位*/ (*n)-; /*长度减1*/ return(0); ,分析：删除第i个元素需要移动(n-i-1)个其他元素，在删除每个元素的概率相同的条件下，可以计算出移动元素的平均次数为： 时间复杂度为O(n)。,三、链接存储的线性表删除 算法：1 确定删除结点的位置，从表头开始搜索出结点i的的前驱结点ai-1，有两种情况：第一种情况: 删除表中第一个元素，第二种情况: 删除表中或表尾元素；2 修改指针。,q=p-link; p-link=q-link;,2 实现程序： 通过函数link_del()实现上述链表的删除算法。 int link_del
15、(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); /*修改指针*/ return(0); j=0; p=*head; while (+ jlink; if (Ilink; p-link=q-link;free(q); /*修改指针,释放空间*/ return(0); ,带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。,非空表 空表,在带表头结点的单链表 第一个结点前插
