【正文】 newnode。 p→ link = newnode。 } return 1。 } Linked List:Inserting a new node(6) Data Structure Software College Northeastern University when we insert a new node： （ 1） insert before the i?th element， which pointer should we get first？ （ 2） illegal inserting position is ? How can we judge inserting position is illegal？ （ 3） We should change two links when inserting ， Is there an order？ Linked List:Inserting a new node Data Structure Software College Northeastern University Case 1: delete the first Case 2: delete the other node Delete the i’th element According the pointer to i?th element ,Can we acplish the operation？ Linked List:Deleting a new node(1) Data Structure Software College Northeastern University int List::Remove ( int i ) { //Delete the i’th element Node *p = first, *q。 int k = 0。 while ( p != NULL amp。amp。 k i1 ) { p = p→ link。 k++。 } //locate the i1’th element if (i0 || p == NULL || p→ link == NULL ) { cout “無(wú)效的刪除位置 !\n”。 return 0。 } if ( i == 0 ) { //delete the first q = first。 //q point the deleted node p = first = first→ link。 //Update first } Linked List:Deleting a new node(2) Data Structure Software College Northeastern University else { q = p→ link。 p→ link = q→ link。 } if ( q == last ) last = p。 //if necessary update last k = q→ data。 delete q。 //free the node pointed by q return k。 } Linked List:Deleting a new node(3) Data Structure Software College Northeastern University Linked List with header ?A node linking to the first node is called Header, the header cell only contains references to the first. Nonempty list empty list 0 an a1 first last first 0 last Data Structure Software College Northeastern University Inserting in a linked list with header newnode→ link = p→ link。 if ( p→ link == NULL ) last = newnode。 p→ link = newnode。 Data Structure Software College Northeastern University q = p→ link。 p→ link = q→ link。 delete q。 if ( p→ link == NULL ) last = p。 Deleting in a linked list with header Data Structure Software College Northeastern University Template of linked list(1) template class Type class List。 template class Type class ListNode { friend class ListType。 Type data。 //結(jié)點(diǎn)數(shù)據(jù) ListNodeType *link。 //結(jié)點(diǎn)鏈接指針 public: ListNode ( )。 //鏈表結(jié)點(diǎn)構(gòu)造函數(shù) ListNode ( const Typeamp。 item )。 ListNodeType *NextNode ( ) { return link。 } //給出當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)地址 Data Structure Software College Northeastern University void InsertAfter ( ListNodeType *p )。 //在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn) p ListNodeType *RemoveAfter ( )。 //摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn) }。 template class Type class List { ListNodeType *first, *last。 public: ListNodeType *GetNode ( const Typeamp。 item, ListNodeType *next )。 //創(chuàng)建數(shù)據(jù)為 item，指針為 next的新結(jié)點(diǎn) Template of linked list(2) Data Structure Software College Northeastern University List ( const Type amp。 value ) { last =first = new ListNodeType( value )。 } //構(gòu)造函數(shù) ~List ( )。 //析構(gòu)函數(shù) void MakeEmpty ( )。 //鏈表置空 int Length ( ) const。 //求鏈表長(zhǎng)度 ListNodeType *Find ( Type value )。 ListNodeType *Find ( int i )。 int Insert ( Type value, int i )。 Type *Remove ( int i )。 Type *Get ( int i )。 }。 Template of linked list(3) Data Structure Software College Northeastern University template class Type ListNodeType :: ListNode ( ) : link (NULL) { } template class Type ListNodeType:: ListNode( const Typeamp。 item ) : data (item), link (NULL) { } template class Type void ListNodeType:: InsertAfter ( ListNodeType *p ) { p→ link = link。 link = p。 } Implementation of linked list(1) Data Structure Software College Northeastern University template class Type ListNodeType *ListNodeType::RemoveAfter ( ) { //摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn) ListNodeType *tempptr = link。 if ( link == NULL ) return NULL。 //沒(méi)有下一結(jié)點(diǎn)則返回空指針 link = tempptr→ link。 //重新鏈接 return tempptr。 //返回下一結(jié)點(diǎn)地址 } Implementation of linked list(2) Data Structure Software College Northeastern University template class Type ListNodeType*ListType::GetNode ( const Type amp。 item, ListNodeType *next = NULL ) { ListNodeType *newnode = new ListNodeType ( item )。 newnode → link = next。 return newnode。 } template class Type ListType :: ~List ( ){ //析構(gòu)函數(shù) (鏈表的公共操作 ) MakeEmpty ( )。 delete first。 //鏈表置空，再刪去表頭結(jié)點(diǎn) } Implementation of linked list(3) Data Structure Software College Northeastern University template class Type void ListType :: MakeEmpty ( ) { //刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn) ListNodeType *q。 while ( first→ link != NULL ) { q = first→ link。 first→ link = q→ link。 //將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q。 //釋放它 } last = first。 //修改表尾指針 } Implementation of linked list(4) Data Structure Software College Northeastern University template class Type int ListType::Length ( ) const { //求單鏈表的長(zhǎng)度 ListNodeType *p = first→ link。 //檢測(cè)指針 p指示第一個(gè)結(jié)點(diǎn) int count = 0。 while ( p != NULL ) { //逐個(gè)結(jié)點(diǎn)檢測(cè) p = p→ link。 count++。 } return count。 } Implementation of linked list(5) Data Structure Software College Northeastern University template class Type ListNodeType*List Type:: Find ( Type value ) { //在鏈表中從