线性表和链表的优缺点 线性表 - 链式存储结构- 单链表的运算（五）

线性表 - 链式存储结构- 单链表的运算（五）  

　　 插入运算

　　( )思想方法

　　插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到a i 与a i 之间

　　具体步骤

　　( )找到a i 存储位置p

　　( )生成一个数据域为x的新结点*s

　　( )令结点*p的指针域指向新结点

　　( )新结点的指针域指向结点a i

　　具体插入过程【 参见动画演示 】

　　( )具体算法实现

　　void InsertList(LinkList head DataType x int i)

　　{//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上

　　ListNode *p;

　　p=GetNode(head i );//寻找第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 head int i)

　　{//删除带头结点的单链表head上的第i个结点

　　ListNode *p *r;

　　p=GetNode(head i );//找到第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)

　　链表上实现的插入和删除运算 无须移动结点 仅需修改指针