c语言数据结构 第二章
插入操作 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(p&&jnext; j++;} //顺指针找第i-1个结点 if(!p||j>i-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 线性结构：一个数据元素的有序(次序)序列。 基本特点： 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个之外，集合