数据结构C语言描述(耿国华)第二章

22.05.2020.1，数据结构课件，西北大学计算机系列，本演示可能包括观众讨论和特定反应。 PowerPoint可以跟踪演示期间的即席反应。 在幻灯片放映中，如果需要右键单击并选择“会议记录”，然后选择“即席反应”选项卡，则输入即席反应并单击“确定”取消选中此框时，将在演示结束时自动创建包含您自己意见的即席反应幻灯片。22.05.2020、2、第2章线性表、2.1线性表的概念和运算2.2线性表的顺序存储2.3线性表的链存储2.4元多项式的表示和加法运算、22.05.2020、3、2.1线性表的概念和运算、2.1.1线性表的逻辑结构2.1.2线性表的抽象数据类型定义、22.05.2020、4线性表的定义，线性表(LinearList )是由n(n0 )个相同类型的数据元素a1、a2、an构成的有限阵列，记载为(a1、a2、ai-1、ai、ai 1、an )。 数据元素之间有一对一的关系。 也就是说，每个数据元素最多有一个直接前体和一个直接后体。 线性表的逻辑结构图包括、22.05.2020、5、线性表的特征、同一性：线性表由相同数据元素构成，每个ai必须属于相同的数据对象。 具有贫困性：线性表由有限的数据要素构成，表的长度是表中的数据要素的数量。 规则性：线性表的相邻数据要素之间存在顺序偶数关系。22.05.2020、6、6、6,2.1.2线性表的抽象数据类型定义、抽象数据类型定义： ADTLinearList数据元素： D=ai|aiD0、I=1、2、nn0、D0是某个数据对象关系： S=|ai、ai 1D0、I=1、2 操作结果：将l初始化为空表。 (2)DestroyList(L )操作的前提：线形表l已经存在。 操作结果：放弃l。 (3)ClearList(L )操作的前提：线形表l已经存在。 操作结果：使表l为空表。 ADTLinearList，22.05.2020，7，2.2线性表的顺序存储结构2.2.2线性表的顺序存储结构上的基本运算，22.05.2020，8，顺序存储结构的定义， 线性表的顺序存储指示线性表内的逻辑结构上相邻的数据元素被存储在相邻物理存储单元中，即数据元素的物理存储的相邻关系，反映该数据元素之间的逻辑相邻关系，该线性表的顺序存储是指在一系列地址连续的存储单元中顺序存储该线性表中的各元素。 采用顺序记忆结构的线性表通常称为顺序表。 如果线性表的各要素占据k个单元，第一个要素的地址为loc(a1)，则第k个要素的地址为loc(ai)=loc(a1) (i-1)k，22.05.2020，9，依次存储结构图，22.05.2020，10，依次存储结构的c语言定义，# define /*线性表占用的数组空间*/intlast； /*记录路线表中最后一个元素在阵列elem内的位置(下标值)。 请注意，空表格是-1*/SeqList区分元素的序号和数组的后缀。 例如，a1的序号为1，对应数组的后缀为0。22.05.2020、11、2.2.2线性表顺序存储结构的基本运算、线性表的基本运算：检索操作插入操作删除操作顺序表合并算法线性表的顺序存储结构的优缺点分析、22.05.2020、12、检索操作、线性表这2种基本检索运算按顺序为GetData(L，I ) :请求在线性表l中搜索第I个数据元素，结果是L.elemi-1或L-elemi-1。 按内容搜索Locate(L，e):会在线性表l中搜索等于给定值e的数据元素，并且如果在表l中找到等于e的元素，则返回该元素在表中的编号。如果找不到，则返回空序列号，如-1。线性表搜索算法包括：22.05.2020、13、线性表搜索运算、intlocate (数组列表l、ElemTypee)i=0； /*i是扫描计数器，初始值为0，从第一个元素开始*/while(ilast 2)/*首先确定插入位置是否合法*/printf (插入位置I的值不正确 ) return (error ) if (l-last=maxsize-1 ) printf (表已满，无法插入 ) return(ERROR) for(k=L-last； k=i-1； 位置*/L-elemk 1=L-elemk；插入元素L-elemi-1=e； /*c语言中数组第I个元素的下标是i-1*/L-last； return(OK) 算法演示(将算法演示程序连接到此处)。 22.05.2020.17.删除操作和线性表删除操作是删除该表中的第I个元素(1in )，并使长度为n的线性表(e1，ei-1、ei、ei 1，en )具有长度为n-1的线性表(e1，ei-1、ei 1，en )。 实现算法构思模式算法、删除算法模式22.05.2020.18，以及删除线性表(4、9、15、21、28、30、30、42、51、62 )中的第五元素。22.05.2020、19、删除算法、intDelList(SeqList*L、inti、ElemType*e)/*从顺序表l中删除第I个数据元素，使用指针参数e删除其值*/intk； if(iL-last 1)printf (删除位置不正确！ ； return (错误) * e=l-elem I-1 ； /*将删除的要素存储在e指定的变量中*/for(k=i； ilast； k )L-elemk-1=L-elemk； 将后面的元素依次向前移动*/L-last-； 已知的是，return(OK) 、22.05.2020、20，一种组合算法包括两个次序表LA和LB，每一个元素均以非降序次序排列，创建一种算法，将它们组合为一个次序表LC，并要求LC也以非降序次序排列。 算法思想：将表LC作为一个空的表，为了使LC也不是降序，假设两个指针I、j分别指向表LA和LB的要素，如果是LA.elemiLB.elemj，则现在将LB.elemj插入到表LC中如果lb.elemj，则现在首先将LA.elemi插入表LC中，假定其中一个算法被扫描之后保留在未扫描的表中，这样的算法实现了这里的连接算法的演示，顺序为22.05.2020、21 j=0； k=0； while(ilast )，22.05.2020，22，顺序记忆体结构的优点与缺点：1.无需增加额外的记忆体空间来表示节点之间的逻辑关系2 .可轻松随机存取表格中的任何元素。 缺点：1.插入或删除的运算不方便，除表末尾的位置外，在表的其他位置进行插入或删除需要移动很多节点，其效率低2 .顺序表需要占用连续的存储区域，所以存储分配只能预先静态分配。 因此，如果表长度的变化较大，则很难确定适当的存储大小。22.05.2020、23、2.3线性表的链接存储、采用链接存储结构的线性表称为链接表。 现在我们从两个角度讨论链接表：1.从实现的角度来看，链接表分为动态链接表和静态链接表2 .从链接方式的角度来看，链接表分为单链接表、循环链接表和双链接表。22.05.2020、24、2.3.1链接表2.3.2链接表中的基本运算2.3.4链接表2.3.4双向链接表*2.3.5静态链接表2.3.6顺序表与链接表的比较、链接表、22.05.2020、25、2.3.1链接表、节点(节点) 链接列表：链接列表中的每个节点只有一个指针域，为了准确表示节点之间的逻辑关系，必须记住路线表中每个数据元素的值以及表示其后续节点的数据元素的值。 此链接列表称为链接列表。 在链接列表中，存储节点值的数据域和指针字段用于存储紧接在数据元素之后的地址(或位置)。 头指针：指向链表头节点的指针。22.05.2020、26、单链路表示的示例图、22.05.2020、27、开头节点的单链路表示的图像，为了便于操作，也可以在单链路表示的第一节点之前加入开头节点。开头节点的空链表开头节点的链表、22.05.2020、28、链表的存储结构描述、typedefstructNode/*节点类型定义*/ElemTypedata； 结构节点*下一步； Node、*LinkList； /*LinkList是结构指针类型*/、22.05.2020、29、2.3.2链接表上的基本运算，线性表的基本运算：链接表删除算法的应用实例，用于创建链接表并查找和操作链接表：求出链接表的长度22.05.2020.30、创建链接表、插件方法或表算法的描述：从空表重复读取数据，生成新节点，将读取的数据存储到新节点的数据字段中，以及将新节点存储到当前链接表的报头节点中、22.05.2020、31、插件构建表算法、linklistcreatefromhead () link list l； 节点* s； intflag=1； /*初始值为1，输入“$”后flag为0，表的创建结束*/l=(link list ) malloc (sizeof (node ) )； /*为头节点分配存储空间*/L-next=NULL； while(flag)c=getchar ()； if(c！=$) *为读取的字符分配存储空间*/s=(Node*)malloc(sizeof(Node ) ) : s-data=c； s-next=L-next； L-next=s； elseflag=0； ，22.05.2020，32，尾插法建立表，C1，s，r，l，22.05.2020，33，尾插法建立表算法，LinklistCreateFromTail()/*链接表末尾*/LinkListL 节点* r、*s； intflag=1； L=(Node*)malloc(sizeof(Node ) )； /*为头节点分配存储空间*/L-next=NULL； r=L； /*r指针始终动态指向链接表的当前末尾*/while(flag)/*标志，初始值为1。 如果输入 $ ，则flag为0，表的创建结束*/c=getchar () : if(c！=$) s=(node * ) malloc (sizeof (node )； s-data=c； r-next=s； r=selseflag=0； r-next=NULL； 用 、 22.05.2020、34、链路表搜索、序列号搜索算法进行描述：若要将开头节点的链路表大小设为n、查找表中的第I个节点，请从链路表头指针l从开头节点(L-next )到链路域用指针p指向当前扫描的节点，初始值指向开头节点(pL-next )，用j制作寄存器，合计当前扫描的节点数(初始值为0 )，在j=i的情况下，实现指向指针p指向的节点的算法，算法的演示。 通过、22.05.2020、35、编号检索算法实现，/*在开头节点的链接列表l中检索第I个节点，如果找到(1in )，则返回该节点的存储位置，否则为NULL*/Node*Get(LinkListL，inti ) 1 p=L； j=0； 从第一个节点开始扫描*/while(p-next！=NULL)p=L-next； 从表的第一个节点开始*/while(p！=null ) if (p -数据！=key)p=p-next； elsebreak； /*找到节点key并退出循环*/returnp；22.05.2020、38、链路表插入操作、算法描述：要在开头节点的链路表l的第I个数据元素之前插入数据元素e，首先在链路表中找到第i-1个节点，用指针pre指示，然后申请新节点并用指针pre指示必须将该数据区域的值设为e，将第i-1个节点的指针朝向s进行修正，使s节点的指针区域朝向第I个节点。s，a1，s，pre，l，22.05.2020，39，单链接表插入操作算法的实现，voidInsList(LinkListL，inti，ElemTypee)/*开头节点的单链接表l中的*/Node*pre、*s； pre=L； intk=0； while！=NULL，22.05.2020，40，链接表删除，算法描述：为了从开头节点的链接表l删除第I个节点，首先通过计数方式找到第i-1个节点，将p指向第i-1个节点，删除第I个节点，释放节点空间。22.05.2020、41、单链接表删除算法的实现、voidDelList(LinkListL、inti、ElemType*e)/*从开头节点的单链接表l中删除第I个要素，并将其值与变量*e中*/Node*p、*r； p=L； intk=0； while(p-next！=NULL/*释放被删除节点占用的内存空间*/，22.05.2020，42，求出链接表的长度，算法用“数”节点的方法求出链接表的长度，用指针p依次指向各节点，从第一个元素到“数”从“数”到最后一个节点intListLength(LinkListL)/*L是起始节点的链接列表*/Node*p；