数据结构线性表.ppt

上传人:王** 文档编号:162998 上传时间:2023-03-02 格式:PPT 页数:35 大小:316KB
下载 相关 举报
数据结构线性表.ppt_第1页
第1页 / 共35页
数据结构线性表.ppt_第2页
第2页 / 共35页
数据结构线性表.ppt_第3页
第3页 / 共35页
数据结构线性表.ppt_第4页
第4页 / 共35页
数据结构线性表.ppt_第5页
第5页 / 共35页
数据结构线性表.ppt_第6页
第6页 / 共35页
数据结构线性表.ppt_第7页
第7页 / 共35页
数据结构线性表.ppt_第8页
第8页 / 共35页
数据结构线性表.ppt_第9页
第9页 / 共35页
数据结构线性表.ppt_第10页
第10页 / 共35页
亲,该文档总共35页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构线性表.ppt(35页珍藏版)》请在优知文库上搜索。

1、1数据结构数据结构 Data Structure2第二章第二章 线性表线性表 第二章第二章 线性表线性表 2.1 线性表的定义和运算 2.2 顺序表 2.3 链表 2.4 其它结构形式的链表 32.1 线性表的定义和运算 p 定义: 线性表L是由n个元素a1,a2,an组成的 有限 序列。 记作 L =(a1,a2,an) 其中n=0为表长;n=0时为L空表,记作L=()p特性: A、只有一个第一个元素和一个最后一个元素; B、除第一个元素外其他元素有且仅有一个直接前趋(前驱); C、除最后一个元素外其他元素有且仅有一个直接后继p元素ai的含义: 同一表中,元素类型相同。在不同的场合有不同的含

2、义 例:字母表(A,B,C,D,Z); 数字表(0,1,2,3,4,9); 每月天数(31,29,31,30,31,30,31,31,30,31,30,31);42.1 线性表的定义和运算 o 运算:运算: (1)初始化 initial_List(L)建立线性表的初始结构,即建空表 (2)求长度 List_length(L) 即求表中的元素个数(3)按序号取元素 get_element(L,i) 取出表中序号为i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值为x的元素,若存在则返回其地址;否则返回特殊值(5)插入 List_insert(L,i,x) 在表L的第i个位

3、置上插入值为x的元素( 1=i=n+1)(6)删除 List_delete(L,i)删除表L中序号为i的元素1=ilistlen=0; int List_length(seqlist L) return L.listlen ; void get_element(seqlist L,int i, elementtype &x) if( i L.listlen) error(“超出范围”); else x = L.datai-1; int List_locate(seqlist L,elementtype x) int i; for (i=0; ilistlen=maxlen)error(“ove

4、rflow”); else if(iL-listlen+1) error(“position error”); else for(j=L-listlen-1;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-listlen+; a1 a2 a3 ai an 0 1 2 i-1 n-1 maxlen-1x条件:顺序表不满; 序号正确,在1, n+1中操作:ai an后移; 填入x; listlen +82.2 顺序表void List_delete(seqlist *L,int i) int j; if (L-listlenL-listlen|i=0) er

5、ror(“删除位置出错”); else for (j=i;jlistlen-1;j+) L-dataj-1=L-dataj; L-listlen-; 92.2 顺序表o 算法分析:插入时 在i=1,2,n+1,元素移动的次数分别为n,n-1,0。 在等概率的情况下,平均移动(n+1)n/2(n+1)=n/2次删除时 在i=1,2,n,元素移动的次数分别为n,n-1,0。 在等概率的情况下,平均移动(n-1)n/2n=(n-1)/2次结论:n较大时,大量移动元素,耗时解决:考虑不移动元素102.3 链表基本结构以链接形式连接元素次序。a1a2a3a4 L=(a1,a2,a3,a4)结点包括 元素

6、和地址。datanext112.3 链表存储实现(静态链表)1、静态链表用数组C3A2B0D5F-1E4data next012345L=(A,B,C,D,E,F)head122.3 链表存储实现(动态链表)2、动态链表用指针和动态变量实现(1)结点结构datanext(2)类型定义 typedef struct elementtype data; node *next; node; 引用:node *head;132.3 链表图例a1a2a3a4 Head*HeadHead-next首元素首元素142.3 链表讨论(插入操作)p 插入(一般位置):假设被插入位置的前一个结点的指针P已找到,插

7、入由S指向的结点:Pa1a2a3a4 headxS S-next=P-next P-next=S注意注意:两个操作不能交换p 如果是作为第一个结点插入,过程如下:S-next=head head=Sa1a2a3 a4 headxS152.3 链表讨论 (引入头结点)为保持插入操作一致,引入头结点头结点。注意:头结点与首元素的区别。a1a2a3 xheadSPS-next=P-next P-next=S162.3 链表讨论(删除操作)p 删除(一般位置):假设被删除的前一个结点的指针P已找到,插入由S指向的结点:Pa1a2a3a5 heada4 P-next=P-next-nextp 如果是删除

8、第一个结点,过程如下:head=head-nexta1a2a3a5 heada4 p 讨论结果:引入头结点P-next=P-next-nexta1a2a4 heada3 P172.3 链表运算的实现(有头结点) 1、初始化单链表(建空表)Lint initial_List(node *L) L=(node*)malloc(sizeof(node);if(!L) printf(“初始化链表错误n”);elseL - next = NULL;182.3 链表求表长(1)2、求单链表表长a1a2a3 LPlen=0int List_length(node *L)P=L-next; len=0; wh

9、ile(P!=NULL) P=P-next; len+; return(len);192.3 链表求表长(2)2、求单链表表长a1a2a3 Lint List_length(node *L)P=L;len=0; while(P-next!=NULL) P=P-next; len+; return(len);Plen=0202.3 链表按序号取值3、按序号取值返回指向结点的指针,否则返回NULLa1a2a3 LPj=0212.3 链表按值查询 4、按值查询 返回元素结点指针,否则返回NULL;a1a2a3 LPnode *locate(node *L,elementtype x) P=L-nex

10、t; while(P!=NULL&P-data!=x) P=P-next; if(P-data=x) return(P); else return NULL; 222.3 链表 插入5、插入ai-1aixSP分析:A、搜索位置;B、装入x;C、插入x;P=get(L,i-1);if(P=NULL) error(“序号错”);else S = (node *)malloc(sizeof(node); S-data=x; S-next=P-next; P-next=S; void insert(node *L,elementtype x,int i)232.3 链表 删除6、删除Pai-1aiai

11、+1 分析:A、搜索位置;B、删除结点;C、释放结点;P=get(L,i-1);if(P=NULL) error(“序号错”);else u=P-next; P-next=P-next-next; free(u); void delete(node *L,int i)242.3 链表单链表的应用(头结点)o链表的遍历:访问链表每个结点一次且仅一次。基本算法如下:void print(node *L) P=L-next; while(P!=NULL) visit(P-data); P=P-next; a1a2a3 LP252.3 链表单链表的应用(头结点) 设计算法,判断带头结点单链表L是否递增

12、?若递增,则返回true,否则返回false。分析:(1)链表空,返回true;(2)只有一个结点,返回true;(3)每个元素都小于其直接后继,返回true;否则,返回false;262.3 链表单链表的应用(头结点)由分析得如下流程图:P=L-next;P=P-next;P!=NULLP-next!=NULLP-datanext-dataYYY返回true返回trueNN返回fasleNbool Judge(node *L) P=L-next; if(P=NULL) return(true); while(P-next!=NULL) if(P-datanext-data) P=P-next

13、; else return(false); return(true); 272.3 链表构造链表o 构造链表构造链表n 基本方法:从键盘输入数据,每读入一个元素,产生结点装入,插入链表中,重复上述操作X是结束是结束0非0Scanf(“%d” ,x);s = (node*)malloc(sizeof(node);s - data = x;s - next = head -next;head - next =s ;n 讨论:产生结点:s=(node *)malloc(sizeof(node);s-data=x;插入链表:插入位置如何确定, 有 表头/表尾 两个位置可选 头插法 尾插法重复上述操作:

14、 何时结束?282.3 链表头插法头插法运算实现:头插法运算实现:void create_List(node *L)L= (node *)malloc(sizeof(node); L-next=NULL;scanf(“%d”,& x);while( x != End_of_Num ) u = (node *)malloc(sizeof(node); u-data=x; u-next=L-next; L-next=u; printf(“%dn”,x);a1a2an UxL292.3 链表尾插法尾插法运算实现:尾插法运算实现:void create_List(node * L)L=(node *)

15、malloc(sizeof(node);R=L; /尾指针尾指针scanf(“%d”,&x);while(x!=End_of_Numo) u=(node *)malloc(sizeof(node); u-data=x; R-next=u; R=u; printf(“%dn”,x);R-next=NULL;a1a2an x sLR302.3 链表练习题1)链表A,B,设计算法求CAB,并分析其时间复杂度2)递增链表A,B,设计算法求CAB,并分析其时间复杂度312.4 其他结构形式的链表o 单循环链表单循环链表(优点:可在表中反复搜索 )初始化操作为: head = (node *)malloc

16、(sizeof(node); head - next = head;求长度: p = head - next; n = 0; while ( p != head ) p = p - next; n + ;应用:约瑟夫环问题(利用循环队列,不带头结点的循环链表都可) (用户输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,直至全部输出。写出C程序。作业)a1a2an headhead322.4 其他结构形式的链表o带尾指针的单循环链表(带尾指针的单循环链表(优点:表尾操作方便 ) 应用:将A、B两链表首尾相连 实现部分语句为:实现部分语句为: u = A - next; A - next = B - next - next; free( B - next); B - next = u; A = B; a1a2an reara1a2an a1a2an BA332.4 其他结构形式的链表p 双链表(双链表(优点:求前驱后继都方便) 带头结点 或者 不带头结点 typedef struct elementtype data; dnode * prior, * next; dnode;

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 高等教育 > 微积分

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!