|
插入运算 ()思想方法 插入运算是将值为x的新结点插入到表的第i个结点的位置上即插入到a i 与a i 之间 具体步骤 ()找到a i 存储位置p ()生成一个数据域为x的新结点*s ()令结点*p的指针域指向新结点 ()新结点的指针域指向结点a i 具体插入过程【 参见动画演示 】 ()具体算法实现 void InsertList(LinkList headDataType xint i) {//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上 ListNode *p; p=GetNode(headi);//寻找第i个结点 if (p==NULL)//i<或i>n+时插入位置i有错 Error(position error); s=(ListNode *)malloc(sizeof(ListNode)); s>data=x;s>next=p>next;p>next=s; } ()算法分析 算法的时间主要耗费在查找操作GetNode上故时间复杂度亦为O(n) 删除运算 ()思想方法 删除运算是将表的第i个结点删去 具体步骤 ()找到a i 的存储位置p(因为在单链表中结点a i 的存储地址是在其直接前趋结点a i 的指针域next中) ()令p>next指向a i 的直接后继结点(即把a i 从链上摘下) ()释放结点a i 的空间将其归还给存储池 具体操作过程【 参见动画演示 】 ()具体算法实现 void DeleteList(LinkList headint i) {//删除带头结点的单链表head上的第i个结点 ListNode *p*r; p=GetNode(headi);//找到第i个结点 if (p==NULL||p>next==NULL)//i<或i>n时删除位置错 Error(position error);//退出程序运行 r=p>next;//使r指向被删除的结点a i p>next=r>next;//将a i 从链上摘下 free(r);//释放结点a i 的空间给存储池 } 注意 设单链表的长度为n则删去第i个结点仅当≤i≤n时是合法的 当i=n+时虽然被删结点不存在但其前趋结点却存在它是终端结点因此被删结点的直接前趋*p存在并不意味着被删结点 就一定存在仅当*p存在(即p!=NULL)且*p不是终端结点(即p>next!=NULL)时才能确定被删结点存在 ()算法分析 算法的时间复杂度也是O(n) 链表上实现的插入和删除运算无须移动结点仅需修改指针 |
