数据结构第二章C.ppt

第二章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双链表 2.4 顺序表和链表的比较 例3、学生健康情况登记表如下： 三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如下 ： 具体算法如下： void INSERT (linklist *head，datetype x，int i) { listnode *p，*s; p=GET(head，i-1); if(p==NULL) error(〝position error〞); s=malloc(sizeof(linklist)); s–data=x; s–next=p–next; p–next=s; } s=malloc(sizeof(linklist)); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return OK; } ∧ an ai a1 a2 P ai-1 L s=malloc(sizeof(linklist )); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return OK; } ∧ an ai a1 a2 ai-1 P L S s=malloc(sizeof(linklist )); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return OK; } ∧ an ai a1 a2 ai-1 P L S x s=malloc(sizeof(linklist )); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return OK; } ∧ an ai a1 a2 ai-1 x P L S s-next=p-next s=malloc(sizeof(linklist )); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return OK; } ∧ an ai a1 a2 ai-1 L S x s-next=p-next P p-next=s 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令p–next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。具体算法如下： void DELETER(linklist *head， int i) { linklist *p， *r; p=GET(head，i-1); if(p= =NULL || p–next= =NULL) return ERROR; r=p–next; p–next=r–next; free( r ) ; } 设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即p–next!=NULL）时，才能确定被删结点存在。 显然此算法的时间复杂度也是O(n)。 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。 ai-1 a1 ai ai+1 L p if(p-next !=NULL) { q=p-next ; / * q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(