分享
分销 收藏 举报 申诉 / 220

类型数据结构C语言版.ppt

  • 上传人:快乐****生活
  • 文档编号:14599467
  • 上传时间:2026-10-18
  • 格式:PPT
  • 页数:220
  • 大小:3.04MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数据结构 语言版
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构C语言版,数据结构C语言版数据结构C语言版本书章节第1章 绪论,第2章 线性表,第3章 栈和队列,第4章 串和数组,第5章 树与二叉树第6章 图,第7章 查找,第8章 排序,第9章 综合应用实例,通过阅读文学作品,我们能提高文学鉴赏水平,培养文学情趣;,本书章节,第1章 绪论,第2章 线性表,第3章 栈和队列,第4章 串和数组,第5章 树与二叉树,第6章 图,第7章 查找,第8章 排序,第9章 综合应用实例,第1章 绪论,教学提示:,本章主要介绍数据结构课程中一些常用术语的含义,算法和算法描述,算法的时间复杂度和空间复杂度评价方法等内容。,教学目标:,1.掌握集合、线性结构、树和图等常用数据结构的概念;,2.掌握抽象数据类型的定义和应用,算法的特性和算法描述的方法;,3.掌握评价算法的一般规则,算法的时间复杂度和空间复杂度。,绪论,_从问题到程序,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门课程,是程序设计的基础,是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础,算法,+,数据结构,=,程序,计算机解决问题的一般过程,八皇后问题、汉诺塔问题、学生信息检索系统问题、迷宫问题、农夫过河问题等解决这类问题的关键不是数学分析和计算方法,而是设计出合适的数据结构,有效的解决问题,绪论,_从问题到程序,八,皇后,问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家,高斯,1850,年提出:在,8X8,格的,国际象棋,上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有,76,种方案。,后来有人用图论的方法解出,92,种,结果。计算机发明后,有多种方,法可以解决此问题,.,绪论,_从问题到程序,印度有个古老传说:在贝拿勒斯的圣庙里,一块黄铜板上插着三根宝石针。其中一根针上从下到上地穿着由大到小的,64,片金片,这就是所谓的汉诺塔。不管白天黑夜,总有一个僧侣在按照法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片从最初穿好的那根针上移到另外一根针上时,世界以及梵塔、庙宇和众生都将同归于尽。,f(64)=264-1=18446744073709551615,秒,584554049253.855,年,这表明移完这些金片需要,5845,亿年,以上,地球至今已,45,亿年,太阳系的预,期寿命是数百亿年。过,5845,亿年,太阳,系和银河系,以至地球上的一切生命真,的都要早灰飞烟灭。,绪论,_抽象数据类型,图书信息检索系统,教学编排问题,图书分类号,登录号,书 名,作 者,出版社,B259.1,3240,梁启超家书,张品兴,中国文联出版社,C52,5231,探寻语碎,李泽厚,上海文艺出版社,D035.5,6712,市政学,张永桃,高等教育出版社,C4,C程序设计,C1,C5,计算机图形学,C2,C3,C4,课程编号,课程名称,先修课程,C1,计算机导论,无,C2,数据结构,C1,C4,C3,汇编语言,C1,C1,C4,C3,C2,C5,绪论,_数据结构的基本概念,数据:能被计算机输入、存储、处理和输出的数字、字符等信息。,数据元素:数据的基本单位。,数据对象:性质相同的数据元素的集合。,数据结构:数据元素及其相互之间的联系。即数据的组织形式,数据元素之间的逻辑关系,也称逻辑结构,数据元素及其关系在计算机存储器内的表示,也称数据的存储结构,数据的运算,即对数据施加的操作,绪论,_数据结构的基本概念,逻辑结构:数据元素之间的逻辑关系,包括集合、性线结构、树型结构、图形结构。,绪论,_物理(存储)结构,物理结构:数据元素在计算机内的存储式,包括顺序、链接、索引、散列等。,26,43,79,11,66,b,c,d,e,a,22,47,60,1,5,9,10,22,15,19,42,44,47,34,51,60,52,54,第一子块,第二子块,第三子块,0,1,2,3,4,5,6,7,8,9,15,22,23,29,37,39,1,2,2,4,4,3,顺序存储,链式存储,散列存储,索引存储,结论,_算法和算法描述,算法:是对特定问题求解步骤的一种描述,有 5 种特性,有穷性 确定性 可行性 输入 输出,算法的特性,正确性 可读性 健壮性 高效率,算法的特性,查找 读取 插入 删除 更新,算法描述工具,自然语言算法描述 框图算法描述,伪语言算法描述 程序设计语言,结论,_算法和算法描述,算法效率的度量,执行算法所消耗的时间,执行算法所占用的存储空间,决定程序运行时间的条件,硬件的速度 实现算法的程序设计语言,编译程序所生成目标代码的质量,算法所采用的策略 问题的规模,结论,_算法评价,算法评价主要从时间和空间两方面入手,时间复杂度,:算法中基本操作重复执行的次数,且是估算的数量级,x=x+1,for(i=1;i=n;i+),for(i=1;i=n;i+),for(j=1;j=n;j+),O(1)O(log2n)O(n)O(nlog2n)O(n,2,)O(n,3,)O(2,n,),空间复杂度:算法执行过程中需要的空间。,存储程序本身所占用的空间,算法的输入/输出数据占用的空间,算法在运行过程中临时占用的辅助空间,结论,_习题,6.a,b,c 三个数求最大值,#include,int main(),int a,b,c;,int max;,printf(请输入三个数:);,scanf(%d%d%d,max=a;,if(max b)max=b;,if(max 0),x1=(x2+1)*2;/*第一天的桃子数是第2天桃子数加1后的2倍*/,x2=x1;,day-;,printf(the total is%dn,x1);,结论,_习题,6.,#include,int main(),int a,b,c;,int max;,printf(请输入三个数:);,scanf(%d%d%d,max=a;,if(max b)max=b;,if(max c)max=c;,printf(最大的数是:%dn,max);,return 0;,第2章 线性表和数组,教学提示:,本章主要介绍线性表的逻辑结构、物理结构;循环链表和双向链表;数组的存储等内容。,教学目标:,1.掌握线性表的顺序存储结构及相关操作和其时间复杂度;,2.握握线性表的链式存储结构及相关操作和其时间复杂度;,3.掌握循环链表和双向链表的存储结构及相关操作;,4.掌握数组的顺序存储结构;,5.掌握稀疏矩阵的顺序存储结构和链式存储结构.,第2章 线性表及数组,线性表的逻辑结构,线性表的顺序存储结构,线性表的链式存储结构,循环链表和双向链表,线性表的应用,数组的顺序存储,稀疏矩阵的,顺序存储,和,链接存储,习题,线性表及数组应用,_,线性表的逻辑结构,1,线性表的定义:是 相同数据类型的n 个元素组成的有限序列。,记作:,L=(a,1,a,2,a,3,a,i,a,n,),。例:学生登记表,线性表的长度:线性表中元素的个数。空表:长度为0。,直接前驱结点:对于a,i,来说,a,i-1,则是。,直接后继结点:对于a,i,来说,a,i+1,则是。,线性表的基本操作,Init_List(L):,建立一个空的线性表,L,;(表,L,不存在),Length_List(L):,求线性表,L,的长度;(表,L,已存在),Get_List(L,i ):,返回线性表,L,中的第,i,个元素值或地址;,Locate_List(L,x):返回L中x元素的序号或地址;,Insert _List(L,i,x):,在线性表,L,中第,i,个元素之前(或之后)插入一个新元素,x;,Delete_ List(L,i):,删除线性表,L,中的第,i,个元素;,线性表及数组应用,_,线性表的逻辑结构,2,操作举例:线性表,L=(26,43,79,11,66),i=2,j=4,x=60,作如下操作:,Length_List(L);5,Empty_List(L);False,Get_List(L,i);e=43,Insert_List(L,i,x);(26,60,43,79,11,66),Delete_List(L,j);,线性表及数组应用,_,线性表的逻辑结构,3,操作举例:,写出程序执行后的线性表,InitList(L);,Int a =48,26,57,34,62,79,for(i=1;i=6;i+)List_ Insert(L,1,a i-1);,for(i=1;i=6;i+),X=Get_List(L,i);,if(!X%2)ListDelete(L,i);,结果:,L=(79,62,34,57,26,48),长度为:,6,L=(79,57),长度为:,2,若余数不存在,即为,偶数,则删除,线性表及数组应用,_,线性表的顺序存储结构,1,顺序存储结构,基本操作,插入操作,删除操作,线性表及数组应用,_,线性表的顺序存储结构,2,线性表的顺序存储:是利用内存中一批地址连续的存储单元依次存储线,性表中的数据元素,特点:顺序存储 随机存储,每个元素占用的空间大小为,L,,则元素,A,i,的存放位置为:,loc(a,i,)=loc(a,1,)+,(i-1),d 1=i=n,线性表的结构,typedef struct,datatype data MAXSIZE,int last;,表长指针始终指向最后一个元素,SqList L;,线性表空间的获得,L=malloc(sizeof(SeqList),线性表数据:L.data0 L.datalast,表长:Last+1,A,i,+k,a,i,A,i,+2k,.,A,i,+(i-1)k,.,A,i,+(n-1)k,0,MAXSIZE-1,线性表的数据类型,L.data ,线性表及数组应用,_,线性表的顺序存储结构,3,线性表的存储结构:,初始化线性表,SeqList *Init_SeqList(),SeqList*L;,L=malloc(sizeof(SeqList);,Llast=-1;,return L;,26,43,79,11,66,当 前 长 度,总 长 度,基地址,Last,MAXSIZE-1,0,Main(),SeqList*L;,L=init_SeqList();,Last,是最后一个元素的数组下标,线性表及数组应用,_,线性表的顺序存储结构,4,清空线性表,Status ClearLIST_Sq(SqList&L),L.length=0;,return OK;,销毁线性表,Status DLIST_Sq(SqList&L),if(L.elem)free(L.elem);,return OK;,求线性表的长度,int ListLength_Sq(SqList L),return L.length;,线性表及数组应用,_,线性表的顺序存储结构,5,读取线性表第,i,个元素值,Status GetElem_Sq(SqList L,int i,ElemType&e),if (iL.length)return ERROR;,e=*(L.elem+(i-1)d);,return OK;,查找数据,int Location_Sqlist(SqList *L,ElemType x),int i=0;,while(iLlast)return -1;,else return i;返回的是数据下标,Last,是最后一个元素的数组下标,线性表及数组应用,_,线性表的顺序存储结构,6,顺序表的插入操作,插入前:,插入后,判断,i,是否越界,,1 i i-1;j-),Ldata j+1 =Ldata j;,Ldata i-1 =x;,Llast+;,return(1);,i,的区间:,1,至,Last+1,j,的区间:,0,至,Last,线性表及数组应用,_,线性表的顺序存储结构,8,顺序表的,删除,操作,删除前:,删除,后,判断,L,是否为空,为空则返回,ERROR;,判断,i,是否越界,,1 iL.last+1;,从第,i+1,个元素向后到最后一个元素为止,所有元素前移,一位,表长减 1.,3,8,14,26,33,41,55,67,80,3,8,14,26,33,41,55,67,80,21,线性表及数组应用,_,线性表的顺序存储结构,9,删除算法,int Delete_List(SqList *L,int i),if (Llast=-1),printf(“表空”);return 0;,If (i Llast+1),printf(“不存在第i个元素”);return 0;,for (j=i;j=Llast;j+),Ldata j-1 =Ldata j;,Llast-;,return(1);,线性表及数组应用,_,线性表的顺序存储结构,10,插入操作的时间分析,移动次数:,0+1+2+3+n =n(1+n)/2,E,is,=,p,i,(n-i+1)=(0+1+2+3+n)/(1+n)=n/2,删除,操作的时间分析,移动次数:,0+1+2+3+n-1 =n(n-1)/2,E,de,=,q,i,(n-i)=(0+1+2+3+n-1)/n=(n-1)/2,n+1,i=1,n+1,i=1,时间复杂度:,O(n),线性表及数组应用,_,线性表的顺序存储结构,11,顺序表(a,1,a,2,a,3,a,n,)重新排列,要求:a,1,前面的值均比a,1,小,a,1,后面的值都比a,1,大。,Void part(SeqList *L),int i,j;,datatype x,y;,x=L,data0;,for(i=1;i=,L,last;i+),if(,L,datai=0;j-),y=,L,dataj+1=y=,L,dataj;,L,data0=y;,时间复杂度:,O(n,2,),X,y,16,21,13,8,33,13,21,16,8,33,13,21,16,16,比较,i,下标元素,从 i-1,下标元素开始后移,线性表及数组应用,_,线性表的顺序存储结构,11,从线性表,LB,中依次取得每个数据元素,在,LA,中进行查找,若不存在,则将其插入,LA,void union_Sq(SqList&LA,SqList LB),for(i=1;i=LB.length;+i),e=*(LB.elem+i-1);从LB中依次取出每个元素,if(!LocateElem_Sq(LA,e,equal)判断是否在LA中,ListInsert_Sq(LA,LA.length+1,e);插入LA的表尾,时间复杂度:,O(m,n),线性表及数组应用,_,线性表的顺序存储结构,12,两个非递减有序表,LA,和,LB,将它们合并成一个新的非递减表,LC,void merge(SeqList A,SeqList B,SeqList *C),int i,j,k;,i=0;j=0;k=0;,while(i=A.last&j=B.last),if(A.dataiB.dataj),Cdatak+=A.datai+;,else,Cdatak+=B.dataj+;,while(i=A.last),Cdatak+=A.datai+;,while(i=B.last),Cdatak+=B.dataj+;,Clast=k-1;,时间复杂度:,O(m+n),A表内,的值送给,C表,K、j指针均后移一位,A表内,的值送给,C表,K、j指针均后移一位,26,43,79,99,12,33,68,70,12,26,33,43,68,70,79,99,线性表及数组应用,_,线性表的顺序存储结构,12,两个非递减有序表,LA,和,LB,将它们合并成一个新的非递减表,LC,void merge_Sq(SqList,SqList LB,SqList&LC),pc=LC.elem=(ElemType*)malloc(LC.listsize*LEN),if(!pc)exit(OVERFLOW);,pa=LA.elem;指向LA基地址,pb=LB.elem;指向LB基地址,pa_last=LA.elem+LA.length-1;指向LA尾地址,pb_last=LB.elem+LB.length-1;指向LB尾地址,while (pa=pa_last&pb=pb_last),if (*pa=*pb)*pc+=*pa+;,else *pc+=*pb+;,while (pa=pa_last)*pc+=*pa+;,while (pb=pb_last)*pc+=*pb+;,*pc=*pb,Pc+;pa+,构造,LC,存储空间,Pa,的值送给,Pc,PaPc指针均后移一位,时间复杂度:,O(m,+,n),线性表及数组应用,_,线性表的顺序存储结构,12,两个非递减有序表,LA,和,LB,将它们合并成一个新的非递减表,LC,int compare(A,B,m,n),int A,B;,int m,n;,int i=0,j,AS,BS,ms=0,ns=0;,while (Ai=Bi)i+;,for(j=i;jm;j+),ASj-i=Bj;ms+;,for(j=i;jn;j+),BSj-i=Bj;ns+;,if(ms=ns,else if(ms=0,else return 1;,时间复杂度:,O(m+n),x,y,y,z,x,x,y,y,z,y,x,z,y,x,z,x,A,B,AS,BS,组建AS表,组建BS表,线性表及数组应用,_,线性表的链式存储结构1,单链表的概念,单链表的查找,单链表的插入,单链表的删除,线性表及数组应用,_,线性表的链式存储结构,2,结点结构,表示方式,p,data,P,结点的元素,p next P,结点的后继指针,p next data P,结点的后继结点的元素值,p next next P,结点的后继结点的指针,一般情况下,等号左端为指针,等号右端为结点,data,next,数据域,指针域,线性表及数组应用,_,线性表的链式存储结构,2,a,1,a,2,a,n,空表,L,L,表头结点,存储地址,数据域,指针域,1,fox,43,7,pig,13,13,cat,1,19,bird,null,25,bat,37,31,dog,7,37,bee,19,43,hen,25,31,头指针L,线性表及数组应用,_,线性表的链式存储结构,2,线性表的链式存储是利用内存中一组任意的存储单元来存储线性表中的数据元素,typedef struct node,ElemType data;,/*,数据域,存放数据*/,struct node *next;,/*,指针域,存放下一个结点的地址*/,LNode*LinkList;,向内存申请一个,LNode,类型的单元,并用,P,指针指向它。,P=malloc(sizeof(LNode),向系统归还结点时,调用库函数,free(p),实现,线性表及数组应用,_,线性表的链式存储结构,9,头插入法建表,LinkList Create_LinkList(),ListList L=NULL,;,LNode *s;,int x;,scanf(“%d”,while (x!=flag),s=malloc(sizeof(LNode),s,data=x;,s next,=L;,L=s;,scanf(“%d”,return L;,时间复杂度:,O(n),s,L,x,初始化,插入,继续链表,键盘读入数据,s,x,s,s,x,线性表及数组应用,_,线性表的链式存储结构,9,尾插入法建表(增加一个尾指针,R,),LinkList Create_LinkList2(),ListList L=NULL,;,LNode *s,*R=NULL;,int x;scanf(“%d”,while (x!=flag),s=malloc(sizeof(LNode),s,data=x;,if (L=NULL)L=s;,else Rnext=s;,R=s;,scanf(“%d”,if (R!=NULL)Rnext,=NULL;,return L;,时间复杂度:,O(n),初始化,R,指向新的尾结点,s,L,x,s,s,x,x,R,R,插入第一个结点,插入其它结点,线性表及数组应用,_,线性表的链式存储结构,9,带头结点的建立单链表,LinkList Create_LinkList3(),ListList L=NULL,;,LNode *R=NULL;,int x;,L=malloc(sizeof(LNode);R=L;,scanf(“%d”,while (x!=flag),Rnext,=malloc(sizeof(LNode);,s,next,data=x;,R=Rnext,scanf(“%d”,Rnext,=NULL;,return L;,时间复杂度:,O(n),初始化,L,x,x,R,线性表及数组应用,_,线性表的链式存储结构,4,求表长,(,带表头,),int Length_LinkList1(LinkList L ),LNode *p=L;,int,j=0;,while(p next),p=,p,next;,j+;,return j;,时间复杂度:,O(n),p,j=1,j=2,j=i,L,a,1,a,2,a,i,a,n,j=0,线性表及数组应用,_,线性表的链式存储结构,4,求表长,(,不带头结点,),int Length_LinkList2(LinkList L ),LNode *p=L;,int,j;,if(P=NULL)return 0;/*空表*/,j=1;,while(p next),p=,p,next;j+;,return j;,时间复杂度:,O(n),p,j=2,j=3,j=i,L,a,1,a,2,a,i,a,n,j=1,线性表及数组应用,_,线性表的链式存储结构,4,查找单链表中第,i,个结点(按序号查找),ListNode *Get_LinkList(LinkList L,int i),ListNode *p=L;,int,j=0;,while(p,next!=NULL,&j i),p=,p,next;,j+;,if(i=j )return p;,else,return NULL;,时间复杂度:,O(n),p,j=1,j=2,j=i,L,a,1,a,2,a,i,a,n,j=0,线性表及数组应用,_,线性表的链式存储结构,5,查找单链表中元素值为 x,的,结点(按值查找),ListNode *Locate_LinkList(LinkList L,dataType x),ListNode *p;,*p=L,next;,while(p,!=NULL,&p data!=x)p=,p,next;,if(p data=x )return p;,else,return NULL;,时间复杂度:,O(n),L,a,1,a,2,x,a,n,p,线性表及数组应用,_,线性表的链式存储结构,6,在单链表中第,i,结点前插入一个元素,x,Void Insert_LinkList(LinkList L,int i,dataType x),ListNode *p,*s;,p=Get_LinkList(L,i-1);/*查找第 i-1个结点*/,if(p=NULL),Printf(“参数 i 错”),;return 0;/*第 i 个结点不存在*/,else ,s=malloc(sizeof(LNode);,sdata=x;,snext=p next;,p,next=s;return 1;,时间复杂度:,O(n),L,P,j=i-1,s,x,线性表及数组应用,_,线性表的链式存储结构,8,删除单链表中的第,i,个元素,Void Del_Linkst(L,int i),ListList p,s;,p=Get_LinkList(L,i-1);,if(p=NULL),printf(“第i-1个结点不存在”);return -1;,else if(p,next=NULL,),printf(“第i个结点不存在”);return 0;,else,s,=,p,next;,p,next,=s,next;,free(s);return 1;,时间复杂度:,O(n),p,s,L,j=i-1,free(r),j=i,线性表及数组应用,_,循环链表 和双向链表 1,循环链表的概念,循环链表的简单操作,双向链表的概念,双向循环链表的,插入,双向循环链表的,删除,线性表及数组应用,_,循环链表 和双向链表 2,循环链表就是将单链表中最后一个结点的指针域指向单链表的表头结点,这样就形成了一个环。,循环链表中可以设一尾指针而不设头指针,循环链表中可以设一尾指针而不设头指针,a,1,a,2,a,n,H,空表,H,a,1,a,2,a,n,R,线性表及数组应用,_,循环链表和双向链表 3,两个循环链表首尾相接,p=R1,next;,R1next=R2next next;,free(R2next);,R2next=p;,R1=R2;,a,1,a,2,a,n,R1,B,1,B,2,a,n,R2,a,1,a,2,a,n,B,1,B,2,B,n,p,free(R2next),R1,R2,线性表及数组应用,_,循环链表和双向链表 4,双向链表的每一个结点除了数据域外,还包含两个指针域,分别指向该结点的前驱结点和后继结点,双向链表中设一个头指针,typedef struct dLNode,dataType data;,struct dLNode *prior,*next;,dLNode,*DLinkList;,Prior data next,H,H,循环双链表,线性表及数组应用,_,循环链表和双向链表 5,在双向链表中的,p,结点前插入一个,s,结点,s=malloc(sizeof(Ldunode);,sdata=x;,sprior=pprior;,ppriornext=s;,snext=p;,pprior=s;,p,S,x,a,i-1,a,i,时间复杂度:,O(1),线性表及数组应用,_,循环链表和双向链表 6,在双向链表中删除,p,结点,p,priornext=,p,next,;,p,nextprior=,p,prior;,free(p);,p,a,i+1,a,i,a,i+2,free(p),时间复杂度:,O(1),线性表及数组应用,_,循环链表和双向链表 6,将单链表倒置,void reverse(Linklist H),LNode *p,*q;,p=Hnext;,Hnext=NULL;,while(p),q=p;p=pnext;,qnext=Hnext;,Hnext=q;,时间复杂度:,O(n),H,29,76,18,25,p,45,q,线性表及数组应用,_,循环链表和双向链表 6,删除单链表重复结点,void pur_LinkList(Linklist H),LNode *p,*q,*r;,p=Hnext;,if(p=NULL)return;,while(pnext),q=p;,while(qnext),if(qnextdata=pdata),r=qnext;qnext=rnext;free(r);,else q=qnext;,p=pnext;,时间复杂度:,O(n,2,),p,H,10,15,18,12,15,q,q,r,H,10,15,18,12,线性表及数组应用,_,循环链表和双向链表 6,将两个递增有序单链表链接成一个递减有序单链表,LinkList merge(LinkList A,LinkList B),LinkList C;LNode *p,*q,*s;,p=Anext;q=Bnext;,C=A;Cnext=NULL;,free(B);,while(p&q),if(pdataqdata),s=p;p=pnext;,else,s=q;q=qnext;,snext=Cnext;Cnext=s;,if(p=NULL)p=q;,while(p),s=p;p=pnext;snext=Cnext;Cnext=s;,时间复杂度:,O(m+n),p,A,10,15,20,25,23,B,12,22,28,32,C,q,s,q,q,p,s,线性表及数组应用,_,多项式相加问题 1,多项式的链表结构,三个核心算法,PolyList polycreate,:建立表示多项式的单链表,Print_Linkst,:输出多项式的单链表,AddPolyn,:把分别由,Pa,和,Pb,所指的两个多项式相加,qa,的指数值,小于,qb,的指数,值,qa,的指数值,等于,qb,的指数,值,qa,的指数值大,于,qb,的指数,值,线性表及数组应用,_,多项式相加问题 2,每个结点的结构,:,A(x)=5x,9,+8x,7,+3x,2,-12,B(x)=6x,12,+10 x,9,+3x,2,coef exp next,系数域 指数域 指针域,5 9,8 7,3 2,-,12 0,qa,Pa,6 12,10 9,-,3 2 ,qb,pb,线性表及数组应用,_,多项式相加问题 3,一元多项式链表的建立算法,PolyList polycreate(),polyNode,*head,*rear,*s;,int c,e;,head=(polyList)malloc(sizeof(PolyNode);,rear=head;,scanf(“%d,%d”,while(c!=0),s=(PloyList)malloc(sizeof(PolyNode);,A(x)=5x,9,+8x,7,+3x,2,-12,s,coef=c;sexp=e;,rearnext=s;rear=s,;,scanf(“%d,%d”,rear,next=NULL;,return(head);,5 9,8 7,3 2,-,12 0,rear,head,s,s,rear,线性表及数组应用,_,多项式相加问题 3,void AddPloy (PolyList ploya,PloyList ployb),polyNode,*p,*q,*tail,*s;int sum;,p=polya,next;q,=polyb,next;tail=,polya;,while(p!=NULL&q!=NULL),if (p,exp qexp,),tail,next=q;tail=q;q,=q,next;,else,sum=p,coef+qcoef;,if(sum!=0),pcoef=sum;tailnext=p;tail=,p,;,p,=p,next;q,=q,next;s=q;free(s);,else,s=p;p=pnext;free(s);,s=q;q=qnext;free(s);,if(p!=NULL)tailnext=p;,else,tailnext=q;,线性表及数组应用,_,多项式相加问题 4,7 0,11 1,9 8,5,17 ,p,polya,22 7,-,9 8,q,tail,Sum=8+11=19,8 1,polyb,s,free(s),Sum=9-9=0,s,Free(s),-,6 5,s,free(s),线性表及数组应用,_,多项式相加问题 8,6.1 从顺序表中删除自第i个元素开始的k个元素,若元素不足k个,则删除自第i元素开始的所有元素,Satus ListDelete_Sq(SqList&L,int i,ElemType&e),if (ListEmpty_Sq(L)return ERROR;,If (i L.length)return ERROR;,p=L.elem+i-1;指针 P 指向尾元素,q=L.elem+L.length 1;指针 q 指向第 i 个元素,e=*p;,if L.length i+1 k L.length=0;,for (;p=L.listsize),newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*LEN);,If(!Newbase)exit(OVERFLOW);,L.elem=newbase;,L.listsize+=LISTINCREMENT;,for (i=1,p=L.elem;i=L.length,*p=q;p-)*(p+1)=*p 元素后移,*q=e;,+L.length;,return OK;,i,:,为第一个元素序号,p,:,为第一个元素地址,线性表及数组应用,_,多项式相加问题 8,6.3 递减有序列,删除单链表中多余的值相同的元素1,#include,#include,#include,#define OK 1,#define Status int,typedef struct LNode,int data;,LNode*next;,LNoed,*LinkList;,Status CreateList_L(LinkList&L),int n,i;,LinkList p,q;,printf(input the length of the Listn);,scanf(%d,printf(input the datan);,L=(LinkList)malloc(sizeof(LNode);,q=L;,线性表及数组应用,_,多项式相加问题 8,6.3 递减有序列,删除单链表中多余的值相同的元素2,scanf(%d,/L-next=NULL;,for(i=2;inext=p;,/p-next=NULL;,q=p;,p-next=L;,return OK;,Status OutList_L(LinkList L),printf(the List isn);,LinkList p;,p=L;,线性表及数组应用,_,多项式相加问题 8,6.3 递减有序列,删除单链表中多余的值相同的元素3,do,printf(%4d,p-data);,p=p-next;,while(p!=L);,printf(n);,return OK;,Status ListDelete_L(LinkList&L),LinkList q,r,p,p1;,q=L;,do,p=q;,p1=p-next;,线性表及数组应用,_,多项式相加问题 8,6.3 递减有序列,删除单链表中多余的值相同的元素4,while(p1!=L),if(q-data=p1-data),r=p1;,p1=p-next=r-next;,free(r);,else,p1=p1-next;,p=p-next;,q=q-next;,while(q!=L);,return OK;,线性表及数组应用,_,多项式相加问题 8,6.3 递减有序列,删除单链表中多余的值相同的元素5,void main(),LinkList La;,CreateList_L(La);,OutList_L(La);,ListDelete_L(La);,OutList_L(La);,线性表及数组应用,_,多项式相加问题 8,6.6 两个递增有序线性表合并为新的有序线性表1,template,void joinsort(T*dst,T*src1,T*src2,int length1,int length2),int length=length1+length2;,dst=new Tlength;,T*src1end=src1+length1;,T*src2end=src2+length2;,while(src1!=src1end&src2!=src2end),if(*src1len+lb-lenelemielemj),lc-elemk=la-elemi;,i+;,k+;,else,lc-elemk=lb-ele
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:数据结构C语言版.ppt
    链接地址:https://www.zixin.com.cn/doc/14599467.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork