线性表的基本操作.ppt

第二章 线性表 线性表的定义、逻辑结构特点及基本运算 线性表的顺序存储及基本运算 线性表的链式存储及基本运算 数组的逻辑结构定义及其存储方式 线性表的应用 1 1 线性表的定义及特点 线性表 n(n0)个具有相同特性的数据元素的有限序列 其中 n表示线性表的长度，即数据元素的个数 n=0时表为空表 n0时记为: （a1, a2， ai-1， ai， ai+1， an） 基本特征 有且只有一个“第一元素”，有且只有一个“最后元素” 除第一元素之外，其它元素都有唯一的直接前趋 除最后元素之外，其它元素都有唯一的直接后继 2 2 元素的含义 数据元素在不同问题中的含 义各不相同 可以是一个数、一个符号， 一个记录，或其它更复杂的 信息 这里的学生成绩表是一个线 性表 数据元素是每一个学生的信 息，包括：学号、姓名、成 绩共三个数据项 学号姓名 计算机导 论 04081101陈小洁80 04081102马丽丽75 04081103林春英82 04081104王澄娟90 04081150张吉祥70 数据元素数据元素 3 3 线性表上常用的的运算 基本运算 初始化线性表 表置空 求线性表中第i个元素 查找满足给定条件的数据元素 在线性表的第i个位置之前插入一个新的数据元素 删除线性表中的第i个数据元素 查找表中第i个元素的前驱 查找表中第i个元素的后继 按一个或多个数据项值的递增或递减次序重新排列线性表中 的数据元素 实际应用中，根据不同的要求选择适当的基本运算解 决问题 4 4 ADTADT 抽象数据类型 对数据的定义定义 对关系的定义定义 对运算的定义定义 D,S,P D:D:数据集合数据集合 S:S:关系集合关系集合 P:P:操作的集合操作的集合 通过固有数据类型来实现实现 抽象数据类型 5 5 ADT triplet 数据对象: D=V1,V2,V3 数据关系: R=, 基本操作: initriplet( char no8; float score STUDENT； STUDENT s20; 在C语言中可借助数组实现 若每个元素占m个存储单元 第i+1个和第i个元素的存储位置 满足如下关系： LOC(ai+1)=LOC(ai)+m 第i个和第一个元素的存储位置 满足如下关系 LOC(ai)=LOC(a1)+(i-1)*m LOC(a1)是线性表的起始地址 取a1和ai的时间是相同的 是一种随机存取的存储结构 8 8 顺序表的类型定义 #define MAXSIZE maxlen /maxlen表示线性表可能的最大数据元素数目 typedef int elemtype; /elemtype表示数据元素类型，此处定义为int typedef struct elemtype vMaxsize; /存放线性表元素的数组 int len; /表示线性表的长度 sqlist; /sqlist是数据类型的名称 /sqlist是一种新的，自定义的数据类型新的，自定义的数据类型 /这种类型就是顺序表类型顺序表类型 9 9 顺序表的类型定义 两种使用方法 sqlist L; L.vi L.len sqlist *sq; sq=(sqlist *)malloc(sizeof(sqlist); sq-vi sq-len #define MAXSIZE maxlen typedef int elemtype; typedef struct elemtype vMaxsize; int len; sqlist; 1010 元素序号元素序号 a a1 1 a a2 2 a an n 0 0 1 1 len-1len-1 1 1 2 2 lenlen 内存内存V V数组下标 数组下标 MaxsizeMaxsize-1-1 备用空间备用空间 顺序表的示意图 1111 顺序表的基本运算 #define maxsize 1024 /顺序表的最大长度 typedef int datatype; /定义表元素类型 typedef struct /定义顺序表类型 datatype datamaxsize; int len; sqlist; void main() sqlist *L; /定义指向顺序表的指针 L=(sqlist *)malloc(sizeof(sqlist); initlist(L); /构造一个空的顺序表 ;free(L); 初始化初始化: :构造空顺序表构造空顺序表 void void initlist(sqlistinitlist(sqlist *L) *L) L- L- lenlen=0; =0; 算法时间复杂度：算法时间复杂度：O(1)O(1) 1212 顺序表上的基本运算 插入算法 在线性表的第i个数据元素前，插入一个新数 据元素，使线性表的长度从n变成n+1 (a1, , ai-1, ai, , an) (a1, , ai-1, x, ai, , an) 1313 内存 a1 a2 ai ai+1 an 0 1 i-1 下标 len-1 i len 1 2 i 元素序号 i+1 len len+1 内存 a1 a2 ai ai+1 an 0 1 i-1 下标 len-1 i len 1 2 i 元素序号 i+1 len len+1 an-1 x 1414 顺序表的插入算法 判断线性表的存储空间是否已满，若已满，则 进行“溢出”处理 检查i值是否超出允许的范围(1ilen+1)，若超 出，则进行“超出”处理 如果上述条件都允许,则将最后一个元素到第i 个元素依次向后移动一个位置 将新的数据元素写到第i个位置上 线性表的长度增加1,插入成功 int insert(sqlist *L,int i,elemtype x)； 1515 插入算法的时间复杂度 插入算法的主要时间用于移动数据元素，该语句 循环执行的次数为n-i+1 当i=n+1时，移动次数为0 当i=1时,移动次数为n 算法的最坏情况时间复杂度：O(n) 算法的最好情况时间复杂度：O(1) 1616 插入算法的时间复杂度 假设在第i个元素之前插入一个元素的概率为Pi， 所需移动数据元素的平均次数为： 1717 顺序表上的基本运算 删除操作 将线性表的第i个数据元素删去，使长为n的 线性表变成长为n-1的线性表 (a1 ,.,ai-1 ,ai ,ai+1 ,.,an ) (a1 ,.,ai-1 ,ai+1 ,.,an ) 1818 内存 a1 a2 ai ai+1 an 0 1 i-1 下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai+1 下标 0 1 i-1 n-2 i n-1 1 2 i 元素序号 i+1 n-1 n an ai+2 1919 顺序表的删除算法 算法思路 判断i值是否超出允许的范围(1ilen），若 是，则进行“超出范围”处理； 否则，保存第i个元素的值； 将第i个元素后的所有元素依次向前移动一 个位置； 线性表长度减1，删除成功 intint delete(sqlistdelete(sqlist * *L,intL,int i,elemtypei,elemtype *y) *y) ； 2020 删除算法的时间复杂度 删除算法的主要时间用于移动数据元素，该循环 语句执行的次数为n-i 当i=1时，移动n-1 个 当i=n时，不需移动 算法的最坏情况时间复杂度：O(n) 算法的最好情况时间复杂度：O(1) 2121 删除算法的时间复杂度 设删除第i个元素的概率为qi，所需移动数据元素 的平均次数为： 2222 顺序表的基本运算 求线性表的长度 int lenth(sqlist *L) int len; len=L-len； return(len); /返回线性表的长度 2323 顺序表上的基本运算 查找 查找指定数据元素x在表中的位置序号，若 vi=x,则算法返回值为i+1，若不存在数据 元素x，则返回0 2424 顺序存储结构的优缺点 静态操作容易实现 根据定位公式容易确定表中元素的存储位置 元素随机存取 动态操作实现效率较低 插入和删除结点困难 由于表中的结点连续存放，在动态操作时，为 了保持元素的连续性，所以必须将某些结点向 后或向前依次移动 扩展不灵活，容易造成空间浪费 建表时，若估计不到表的最大长度，就难以确定 分配的空间，影响数据扩展 分配的空间过大，则会造成预留空间浪费 2525 作业 编写完整的源程序实现顺序表的插入,删除算法. P21,综合题5，6，7 2626 线性表的链式存储结构 链表 以链式结构存储的线性表 用一组在物理位置上任意的存储单元来存储线 性表的结点 存储单元可以是相邻的 也可以是不相邻的 相邻存储单元中的数据，不一定是相邻的结点 物理位置上的关系不能反映结点间的逻辑关系物理位置上的关系不能反映结点间的逻辑关系 2727 线性表的单链存储示意图 陈小洁 张吉祥1 林春英 李小林 李清 张桂林 7 15 54 40 NULL 2828 链式存储结构的特点 用一组任意位置的存储单元存储线性表的数据元素 结点间的逻辑关系借助结点中的指针实现 每个数据元素，除存储本身信息外，还需存储其直 接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 数据域 指针域 2929 单链表 链表中，每个结点只包含一个指针域 结点类型的C语言描述： typedef char elemtype; typedef struct node elemtype data； struct node *next; Lnode，* linklist; LnodeLnode *L; *L; 与与 linklistlinklist L; L; 等价等价 L可作为单链表的头指针，指向链表的第一个结点 若L=NULL，表示单链表为空表，长度为0 3030 带头结点的单链表 在单链表的第一个结点前添加一个辅助结点，称为 头结点或伪结点 头结点的数据域可以不存储任何信息，也可以存储 一些附加信息； 头结点的指针域存储链表首结点的地址链表首结点的地址 如果头结点的指针域为“空”，即L-next=NULL， 表示该链表为空表 3131 单链表的使用注意事项 linklist h,p; Lnode *h,*p; p=(Lnode *)malloc(sizeof(Lnode); 此时,P和对象之间的关系: datadatanextnext p p 结点结点 (*p)(*p) (*p)(*p)表示表示p p所指向的结点所指向的结点 (*p).data(*p).datap-datap-data： P P所所指向结点的数据域指向结点的数据域 (*p).next(*p).nextp-nextp-next： P P所所指向结点的指针域指向结点的指针域 typedef struct node elemtype data; struct node *next; Lnode,* linklist; 3232 头插法建立单链表 算法思路 1.建立一个头结点，使头结点的指针域为空 2.建立一个新结点P,作为待插入的新结点 3.给新结点P的数据域赋值 4.将新结点插入到头结点的后面，成为第一个 数据结点 5.是否继续？如果继续，返回2，否则跳到6 6.结束创建,创建成功 3333 typedef char elemtype; typedef struct node elemtype data； struct node *next; Lnode; #define LEN sizeof(Lnode) /定义结点长度 Lnode * creat() Lnode *p, *head; head=(Lnode *)malloc(LEN); /头结点 head-next=NULL; . 3434 while(1) /创建新链表 p=(Lnode *)malloc(LEN);/申请一个新结点 scanf(“%c”, /数据域赋值 p-next=head-next; /修改新结点的指针域 head-next=p; /将新结点设为第1个数据结点 printf(“是否继续?(y/n)”); if(getchar()=n)break; return(head); 3535 尾插法创建单链表的算法 算法思路 1.申请一个结点的空间，作为头结点 2.申请一个结点的空间，作为待插入的新结点 3.给新结点的数据域赋值，将新结点插入到链 表尾，使其成为新的尾结点,其指针域为NULL 4.是否继续？如果继续，返回2，否则跳到5 5.结束创建,创建成功 3636 typedef char elemtype; typedef struct node elemtype data； struct node *next; Lnode; #define LEN sizeof(Lnode)/定义结点长度 Lnode * creat() Lnode *p, *tail,*head; tail=head=(Lnode *)malloc(LEN); /头结点 head-next=NULL; . 3737 while(1) /创建新链表 p=(Lnode *)malloc(LEN);/申请一个新结点 scanf(“%c”, /数据域赋值 tail-next=p; /将新结点插入到链表尾 tail=p; /设置新的尾结点 tail-next=NULL; /置尾结点的指针域为空 printf(“是否继续?(y/n)”); if(getchar()=n)break; return(head); 3838 求单链表的长度的算法 求表中元素的个数 算法思想 计数器清0 令指针p=head-next 让指针P沿着链表的指针域向前移动,每移动 一步,计数器增1 当指针P 为空,表示已经到了链表尾 此时,计数器中就是结点个数 时间复杂度：O(n) 3939 单链表的插入算法 插入点 q q p p p-next=q-next; q-next=p; 插入数据 不需进行大量数据移动，只需找到插入点即可 4040 算法 在单链表的第i个结点后，插入值为item的结点 算法思想 寻找第i个结点,即插入点 如果找不到插入点,插入位置不合适,无法插 入,返回FALSE 如果找到插入点,则进行插入操作 申请新结点申请新结点 新节点数据域置为新节点数据域置为itemitem 插入新节点插入新节点 操作成功，返回操作成功，返回TRUE.TRUE. int insert(Lnode *h,int i,elemtype x); 4141 删除算法 删除数据：删除某个结点 算法思想 P P 结点结点i i结点结点i-1i-1 q q 4242 删除算法 算法思路： 将q指向p结点的直接后继； 改变指针链接，把q结点的直接后继作为 p结点的直接后继； 从单链表中删除q结点； 释放q结点空间。 4343 删除单链表上的第i个结点 算法思想 如果是空表,无法删除,返回FALSE 如果不是空表,则找第i-1个结点 如果该结点不存在如果该结点不存在, ,无法删除无法删除, ,返回返回FALSEFALSE 如果第如果第i-1i-1个结点存在个结点存在, ,则找第则找第i i个结点个结点 如果第如果第i i个结点不存在个结点不存在, ,无法删除无法删除, ,返回返回 FALSEFALSE 如果第如果第i i个节点存在个节点存在, ,则删除则删除, ,返回返回TRUETRUE int delete(Lnode *head，int i); 删除算法 4444 int delete(Lnode *head，int i) Lnode *p,*q; int j=1; p=head -next; if(p=NULL) /空表，无法删除 return 0; while(p /寻找第i-1个结点 if(jnext = =NULL) return 0; /第i个结点不存在 q=p-next; /q指向第i个结点 p-next=q-next; free(q);free(q); return 1; 算法的时间复杂度是算法的时间复杂度是O(nO(n) ) 4545 按值查找算法 查找单链表中是否存在数据域为x的结点。若 有该结点，则返回指向该结点的指针，否则返 回空 算法思路 从第一个结点开始扫描整个单链表，逐个 比较数据域值和x 找到该结点后返回指向该结点的指针 4646 读取线性表中指定位置的元素 读取单链表中的第i个元素。如果找到，则返回第i 个结点的存储地址，否则返回空 算法思路 (1)p从单链表的第一个结点出发，并定义j=1 (2)在单链表中移动指针p，同时累计j (3)通过j的累计查找j=i的结点 (4)重复(2)、(3)直到p为空或p指向第i个元素 Lnode *get(Lnode *h,int i); 4747 单链表特点 是一种动态结构，不需预先分配空间 指针占用额外存储空间 不能随机存取，而是顺序存取 适合做动态操作 带头结点的单链表很多时候可以使算法简化 4848 循环链表 单循环链表 单链表中最后一个结点的链域值不是NULL， 而是指向头结点，整个表形成一个环 特点 从表中任意结点出发均可找到表中其它的结点 操作与单链表基本一致,循环条件不同 带头结点的单链表：p-next=NULL 带头结点的单循环链表：p-next=head 4949 创建单循环链表 循环链表是对单向链表的一种改善。 单链表中尾结点的next=NULL，只需把尾结点的 next域设置为头结点的地址，就能够获得一个循 环链表。 int initclist(Lnode *head) head=( Lnode *) malloc (sizeof (Lnode); head-next=head; return 1; 单循环链表的操作一 5050 判断单循环链表是否为空 只需看头结点的next域是否等于头指针 int isempty(Lnode *head) if(head-next=head) return 1; else return 0; 本算法时间复杂度为O(1)。 单循环链表的操作二 5151 遍历单循环链表 从首元节点开始，逐个访问链表结点,直到链表尾 void view(Lnode *head) Lnode *p=head-next; while(p!=head) putchar(p-data); p=p-next; 算法时间复杂度为O(n) 单循环链表的操作三 5252 双向链表 每一个结点中有两个指针域 一个指向直接后继 另一个指向直接前趋 这样的链表称为双向链表 结点描述如下: typedef struct dulnode elemtype data; struct dulnode *next,*prior; dulnode; priorpriorelementelement nextnext 5353 双向循环链表 将双向链表中的头结点和尾结点链接起来，构成双 向循环链表 5454 双向循环链表 在双向环形链表中，指针p指向双向链表中的某 结点，则有如下关系 p-next-prior p p-prior-next p 双向链表的对称性 5555 在双向循环链表结点p之前插入结点s 改变指针链接的语句有 s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 双向循环链表的插入算法 5656 双向循环链表的插入算法 在双向循环链表的第i个结点之前插入值为x的 新结点。如果成功，返回1，否则，返回0。 算法思路 通过p的移动在双向链表中查找第i个元素 如果找到，则建立一个新结点s 将s和p以及p的前驱链接起来 使s的前驱是p原来的前驱 s的后继是p 5757 双向循环链表的删除算法 删除双向环形链表的结点p 改变指针链接的语句有 p-prior-next=p-next; p-next-prior=p-prior; 5858 双向循环链表的删除算法 删除双向环形链表的第i个结点p。如果成功，返 回1，否则，返回0。 算法思路 通过p的移动在双向链表中查找第i个元素 如果找到，改变指针链接 使p的前驱指向p的后继 p的后继结点的前驱指针指向p原来的前驱 释放p 5959 线性表顺序存储与链式存储的比较 从时间的角度 在按位置查找数据，或在查找元素的前趋和后继 等方面，顺序存储有着较大的优势。 在插入数据、删除数据时，链式存储有较大的优 势.因为在链表中只要修改指针即可做到；而在顺 序表中则平均要移动将近一半的数据元素 从空间的角度 顺序表的存储空间是静态分配的，在程序执行之 前必须规定其存储规模。 动态链表的存储空间是动态分配的，只要内存空 间有空闲，就不会产生溢出。 6060 线性表的顺序存储和链式存储在操作上的比