int List: Insert( int x, int 1)& ∥/在链表第i个结点处插入新元素x ListNodesp- first for(k=0;k<1-1;k++)∥找第i1个结点 if(p==NULL) break else p=p->link; if (p== NULL & first!= NULL)( cout<<“元效的插入位置!n; return 0; ListNode *newnode 创建新结点 new ListNode(x, nUll);
int List :: Insert ( int x, int i ) { //在链表第i 个结点处插入新元素x ListNode * p = first; for ( k = 0; k < i -1; k++ ) //找第 i-1个结点 if ( p == NULL ) break; else p = p->link; if ( p == NULL && first != NULL ) { cout << “无效的插入位置!\n”; return 0; } ListNode *newnode = //创建新结点 new ListNode(x, NULL);
if(frst==NULL‖i==0){/插在表前 newnode->link= first; if( first- NULL )last=newnode, first= newnode eise ∥/插在表中或末尾 newnode->link=p->link if (p->link=- NULL)last=newnode; p->link=newnode, return 1
if ( first == NULL || i == 0 ) { //插在表前 newnode->link = first; if ( first == NULL ) last = newnode; first = newnode; } else { //插在表中或末尾 newnode->link = p->link; if ( p->link == NULL ) last = newnode; p ->link = newnode; } return 1; }
删除 ◆第一种情况:删除表中第一个元素 ◆第二种情况:删除表中或表尾元素 -a4 删除前 p 删除后 在单链表中删除含a的结点
◼ 删除 ◆ 第一种情况: 删除表中第一个元素 ◆ 第二种情况: 删除表中或表尾元素 在单链表中删除含ai的结点 ai-1 ai-1 ai ai ai+1 ai+1 p q 删除前 删除后
int List Remove(int 1)t ∥/在链表中删除第i个结点 istNode* p,g: if(i==0) 删除表中第1个结点 &q= first; p= first- first->link;) else p=frst;intk=0;/找第i1个结点 while(p= null &&k<1-1 ip=p->link; k++;) if(p== null p->link ==NULL cout<<“无效的删除位置!n”; return0;
int List :: Remove ( int i ) { //在链表中删除第i 个结点 ListNode *p, *q; if ( i == 0 ) //删除表中第 1 个结点 { q = first; p = first = first->link; } else { p = first; int k = 0; //找第 i-1个结点 while ( p != NULL && k < i-1 ) { p = p->link; k++; } if ( p == NULL || p->link == NULL ) { cout << “无效的删除位置!\n”; return 0; }
eise 删除表中或表尾元素 q=p->link;∥重新链接 p->link=q->link; if(q=last)last=p;∥)能修改last ypex=q->dat,你q delete q; / return x. /回第i个结点的值
else { //删除表中或表尾元素 q = p->link; //重新链接 p->link = q->link; } if ( q == last ) last = p; //可能修改last Type x = q->data; delete q; //删除q return x; //返回第i 个结点的值 }