数据算法与结构.ppt

上传人:夺命阿水 文档编号:229766 上传时间:2023-03-02 格式:PPT 页数:41 大小:1.06MB
返回 下载 相关 举报
数据算法与结构.ppt_第1页
第1页 / 共41页
数据算法与结构.ppt_第2页
第2页 / 共41页
数据算法与结构.ppt_第3页
第3页 / 共41页
数据算法与结构.ppt_第4页
第4页 / 共41页
数据算法与结构.ppt_第5页
第5页 / 共41页
点击查看更多>>
资源描述

《数据算法与结构.ppt》由会员分享,可在线阅读,更多相关《数据算法与结构.ppt(41页珍藏版)》请在课桌文档上搜索。

1、2.3 线性表的链式存储结构,特点:用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai,除存储本身信息外,还需存储其直接后继的信息结点数据域:元素本身信息指针域:指示直接后继的存储位置,例 线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,线性链表,定义结点中只含一个指针域的链表叫,也叫单链表实现,typedef struct node datatype data;struct node*link;JD;,JD*h,*p;,(*p)表示p所指向的结点

2、(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域,生成一个JD型新结点:p=(JD*)malloc(sizeof(JD);系统回收p结点:free(p),h,a1,a2,an,h,空表,头结点,.,线性链表,头结点:在单链表第一个结点前附设一个结点叫。是整个线性链表的第一个结点,它的数据域可以放数据元素,也可以放线性表的长度等附加信息,也可以不存储任何信息头结点指针域为空表示线性表为空。,线性链表,头指针:指向链表中的第一个结点;首元结点:线性表的第一个元素结点,单链表的基本运算,查找:查找单链表中是否存在结点X,若有则返回指向X结点的指

3、针;否则返回NULL算法描述算法评价,JD*dlbcz(JD*h,int x)JD*p;p=h;while(p!=NULL,单链表的基本运算,插入:在线性表两个数据元素a和b间插入x,已知p指向a算法描述算法评价,s-link=p-link;,p-link=s;,/数据元素的查找,x为要查找的元素,void dlbcr(JD*p,int x)JD*s;s=(JD*)malloc(sizeof(JD);s-data=x;s-link=p-link;p-link=s;,单链表的基本运算,删除:单链表中删除b,设p指向a算法描述算法评价,p-link=p-link-link;,void dlbsc(

4、JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);,算法评价,Ch2_3.c,单链表的基本运算,动态建立单链表算法:设线性表n个元素已存放在数组a中,建立一个单链表,h为头指针算法描述,JD*dlbjl(int a,int n)JD*s,*h,*p;int i;h=(JD*)malloc(sizeof(JD);h-data=0;h-link=NULL;for(i=n;i0;i-)s=(JD*)malloc(sizeof(JD);s-data=ai-1;s-link=h-link;h-link=s;return(h);,单链表,单链

5、表特点它是一种动态结构,整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取,查找速度慢为什么引入头结点在一些针对链表的算法中,(如查入,删除、及建表)对其中第一个结点和其余结点的操作,因结构方面的原因而存在差异,从而使算法的设计不方便,加入头结点,使得线性表中第一个元素对应的首元结点变成了链表中的第二个结点,使所有元素结点具有相同的结构,方便算法和程序设计。,循环链表(circular linked list),循环链表是表中最后一个结点的指针指向头结点,使链表构成环状特点:从表中任一结点出发均可找到表中其他结点,提高查找效率操作与单链表基本一致,循环条件不同单链表p或

6、p-link=NULL循环链表p或p-link=H,双向链表(double linked list),单链表具有单向性的缺点,在查找某节点的直接前趋的时间复杂度将达到O(n)。结点定义,typedef struct node datatype element;struct node*prior,*next;JD;,p-prior-next=p=p-next-proir;,b,c,void del_dulist(JD*p)p-prior-next=p-next;p-next-prior=p-prior;free(p);,算法描述,算法评价:T(n)=O(1),p-prior-next=p-nex

7、t;,p-next-prior=p-prior;,P,a,删除,void ins_dulist(JD*p,int x)JD*s;s=(JD*)malloc(sizeof(JD);s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;,算法描述,算法评价:T(n)=O(1),插入,2.4 线性表的应用举例,一元多项式的表示及相加一元多项式的表示:,可用线性表P表示,但对S(x)这样的多项式浪费空间,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构,也可以用单链表,单链表的结点定义,一元多项式相加,typedef

8、struct node int coef,exp;struct node*next;JD;,设p,q分别指向A,B中某一结点,p,q初值是第一结点,运算规则,Ch2_7.c,算法描述,void add_poly(JD*pa,JD*pb)JD*p,*q,*u,*pre;int x;p=pa-next;q=pb-next;pre=pa;while(p!=NULL),p=pre-next;u=q;q=q-next;free(u);else u=q-next;q-next=p;pre-next=q;pre=q;q=u;if(q!=NULL)pre-next=q;free(pb);,重点:线性表的顺序存

9、储;线性表的链式存储;顺序表的插入、删除 单链表的插入、删除难点:双向链表的系列操作 线性表的应用。,练习,填空题线性表是一种典型的 结构。采用 存储结构的线性表叫顺序表,N-i+1,插入或删除的元素位置,顺序表逻辑上相邻的元素的物理位置 紧邻,单链表中逻辑上相邻的元素的物理位置 紧邻。,必定,不一定,单链表中除首元结点外,任一结点的存储位置由 指示。,其前驱结点的指针域,N-i,在长度为n的顺序表中第i个元素前插入一个元素,需要移动 个元素,若删除第I个元素,需移动 个元素,移动元素的个数取决于。,数据,顺序,练习,选择题以下关于线性表的说法不正确的是()A、线性表中的数据元素可以是数字、字

10、符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表:表中各结点都没有直接前趋和直接后继。,练习,线性表的顺序存储结构是一种()的存储结构。A、随机存取 B、顺序存取 C、索引存取D、散列存取,练习,在顺序表中,只要知道(),就可在相同时间内求出任一结点的存储地址。A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小,练习,4、在等概率情况下,顺序表的插入操作要移动()结点。A、全部 B、一半 C、三分之一 D、四分之一,练习,5、在()运算中,使用顺序表比链表好。A、插入 B、删除 C、根据序号查找

11、 D、根据元素值查找,作业:,S,P,R,(1)Q=P-next;,(2)R-data=P-data;,(3)R-data=P-next-data;,(4)P-next-next-next-data=P-data;,(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-next;,(6)T=P;while(T-next!=NULL)T-data=(T-data)*2;T=T-next;,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-next=P;P-next=S;,P,10,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-next=P;P-next=S;,P,10,L,2,4,3,7,5,8,6,S,R,(8)T=L;T-next=P-next;free(P);,3 6,5 4,1 11,

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

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号