线性表的逻辑结构.pptVIP

【算法2.11】将新结点s插入到第i个结点的位置上，即插入到ai-1与ai之间。算法思路：(1)查找第i-1个结点；若存在继续(2)，否则结束；(2)创建新结点；(3)将新结点插入，结束。…Hai-1xai×p①②s③④…时间复杂度为O(n)*intInsert_LinkList(LinkListH,inti,ElemTypex)

/*在单链表H的第i个位置上插入值为x的元素*/

{LNode*p,*s;

p=Get_LinkList(H,i-1);

if(p==NULL)

{printf(＂插入位置i错＂);returnERROR;}

else{

s=(LinkList)malloc(sizeof(LNode));

s-data=x;

s-next=p-next;

p-next=s；

returnOK;

}/*Insert_LinkList*/5.删除操作*【算法2.12】删除链表中第i个结点。算法思路：(1)查找第i-1个结点；若存在，则继续(2)，否则结束；(2)若存在第i个结点则继续(3)，否则结束；(3)删除第i个结点，结束。①q-next=p-next;②free(p);xpq①②…Hai-1ai+1p①②q③④…ai××释放到存储池intDel_LinkList(LinkListH，inti)/*删除单链表H上的第i个数据结点*/{LinkListp,q;p=Get_LinkList(H,i-1);if(p==NULL){printf(＂第i-1个结点不存在＂);returnERROR;}else{if(p-next==NULL){printf(＂第i个结点不存在＂);returnERROR;}else{q=p-next;/*q指向第i个结点*/p-next=q-next;free(q);returnOK;}}/*Del_LinkList*/时间复杂度为O(n)如果在链表中第i个结点后插入一个值为y的结点，如果i不存在，则把结点插在表尾。如何实现？如果在不带头结点的链表中第i（i=1）个结点前插入一个值为y的结点（在链表中值为x的结点前插入一个值为y的结点），如何实现？考虑的几个问题：从上面的讨论可以看出：单链表上插入、删除一个结点，必须知道其前驱结点。

单链表不具有按序号随机访问的特点，只能从头指针开始依次进行访问。

链表上实现的插入和删除运算，不用移动结点，仅需修改指针。(2)删除所有值为x的结点，并返回1值为x的结点个数。intDelete_Linkst2(LNode*H,Elemtypex){LNode*p,*q;q=H;count=0;while(q-next){p=q-next;if(!p-data==x){q-next=p-next;/*逐个判断结点值，为x则删除*/free(p);++count;}/*count+1*/elseq=p;}/*while*/returncount;}/*Delete_Linkst2*/80768090∧85Hpq例如x=80的情况。时间复杂度为O(n).考虑不带表头结点的情况，删除算法相对考虑的因素要多些。2.3.3循环链表*承德石油高专计算机系*2003-1-9单链表《数据结构》第二章线性表······a1a2an∧H······a2∧a1a2an∧H双向链表······a1a2anH循环链表*(rear-next)定义：循环链表是另一种形式的链表存储结构，实现方法是将表中最后一个结点的指针域指向单链表的表头结点，这样就