c语言数据结构 第二章.ppt

插入操作 a b p … … 插入元素e e s s-next p-next=s s-next=p-next 注意： ①插入元素时应使一指针指向插入位置的前一结点； ②语句s-next=p-next； p-next=s；不能颠倒顺序。 插入操作 在不带头结点的单链表中插入 ai an ^ … … ai-1 a1 L 插入位置 e p s 插入位置的合法范围 1)查找插入位置： 表首或空表（无前驱结点）： 其他位置（有前驱结点）：若题中明确在第i个元素前插入，则需通过计数，找到第i-1个结点；若未明确插入位置，则需进行元素值的比较，找到插入位置前一结点。 ①无前驱结点 ②有前驱结点 插入操作 在不带头结点的单链表中插入 2)插入新结点： 在表首插入：s-next=L; L=s; 其他位置插入： s-next=p-next； p-next=s; ai an ^ … L … ai-1 a1 e p s s-next=p-next p-next=s 插入位置的合法范围 ①无前驱结点 ②有前驱结点 插入位置 e s 插入操作 在带头结点的单链表中插入 ai an ^ … ai-1 … a1 L 插入位置 e p s s-next=p-next p-next=s 插入位置的合法范围 查找插入位置：通过计数或进行元素值的比较找到插入位置前一结点。 插入新结点：s-next=p-next； p-next=s； 在表首或空表中插入也可直接写成：s-next=L-next; L-next=s; e s 插入操作 status ListInsert_L( LinkList L, int i, ElemType e){ //在带头结点的单链表L中第i个位置之前插入元素e，1≤ i≤表长+1 p=L;j=0; while(pji-1) {p=p-next; j++;} //顺指针找第i-1个结点 if(!p||ji-1) return ERROR; //i小于1或i大于表长加1 s=(LinkList) malloc(sizeof(LNode)); //生成新结点 s-data=e; s-next=p-next; //插入L中 p-next=s; return OK; } //ListInsert_L 插入操作 基本操作：指针后移 当1≤i ≤表长+1时，指针后移i-1次，否则，后移n+1次 时间复杂度：O(n) 删除操作 删除位置 注意： ①删除元素时应使一指针指向其前驱结点； ②执行语句p-next=q-next； free(q)； ai p ai-1 … … ai+1 e ai q p-next=q-next free(q) (q=p-next) 删除操作 在不带头结点的单链表中删除 ai … ai-1 a1 L 删除位置 p 删除位置的合法范围 1)查找删除位置： 空表(L=NULL)或表首(无前驱结点)：空表出错 其他位置（有前驱结点）：若题中明确删除第i个元素，则需通过计数，找到其前驱结点；若未明确删除位置，则需进行元素值的比较，找到删除位置前一结点。 ① ② an ^ … ai+1 q 删除操作 在不带头结点的单链表中删除 ai ai-1 L … a1 删除位置 p 删除位置的合法范围 2)删除结点： 表首（无前驱结点）：q=L-next; free(L); L=q; 其他位置（有前驱结点）：p-next=q-next; free(q); ① ② an ^ … ai+1 e q ai p-next=q-next; free(q); q q=L-next; free(L); L=q; 删除操作 在带头结点的单链表中删除 ai … ai-1 a1 L 删除位置 p 删除位置的合法范围 1)查找删除位置： 通过计数，或元素值的比较，找到删除位置前一结点。 2)删除结点：p-next=q-next; free(q); 若已知删除首元结点，也可写为： q=L-next; L-next=q-next; free(q); an ^ … ai+1 q e ai p-next=q-next; free(q); 第 2 章 线性表 教学目标：掌握线性表的基本特征，熟练掌握线性表在顺序和链式物理结构上基本操作的实现，了解两种实现方式的优缺点。 教学重点：线性表的链式实现 教学难点：线性表的链式实现 教学时数：6 线性结构：一个数据元素的有序（次序）序列。 基本特点： 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个之外，集合中的每个数据元素均只有一个前驱 除最后一个之外，集合中的每个数据元素均只有一个后继 线性结构：包括：线