一、鏈表創建
鏈表主要有三種形式，包括單鏈表、雙鏈表和循環鏈表。 單鏈表每個節點只包含一個后驅指針，雙鏈表節點同時包含一個前驅指針和一個后驅指針，循環鏈表的尾節點的后驅指向頭節點。 代碼如下：
/*單鏈表節點結構*/typedef struct NodeType{char elem;NodeType*next;}Node;/*雙鏈表節點結構*/typedef struct DNodeType{char elem;DNodeType*next;DNodeType*PRev;}DNode;/*創建鏈表*/Node* CreateList(Node*head){if(NULL== head)//分配頭節點空間head=(Node*)malloc(sizeof(Node)),head->next=NULL;Node*current=head ,*temp;char ch;while(1){cout<<”/n input elem:”;cin>>ch;if(‘#’ == ch)/*#結束輸入*/break;temp=(Node*) malloc (sizeof(Node) );temp->elem=ch;temp->next=NULL;current->next=temp;/*當前節點的后驅指向新節點*/current=temp;/*當前節點為鏈表尾節點*/}return head;}/*創建雙鏈表*/DNode* DoubleList(DNode*head){if(NULL== head)//分配頭節點空間head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL , head->next=NULL;DNode*current=head ,*temp;char ch;while(1){cout<<”/n input elem:”;cin>>ch;if(‘#’ == ch)/*#結束輸入*/break;temp=(DNode*) malloc (sizeof(DNode) );temp->elem=ch;temp->next=NULL;current->next=temp;/*當前節點的后驅指向新節點*/temp->prev=current;/*新節點的前驅指向當前節點*/current=temp;/*當前節點為鏈表尾節點*/}return head;}/*創建循環鏈表*/Node* CycleList(Node*head){if(NULL== head)/*分配頭節點空間*/head=(Node*)malloc(sizeof(Node)),head->next=NULL;Node*current=head ,*temp;char ch;while(1){cout<<”/n input elem:”;cin>>ch;if(‘#’ == ch)/*#結束輸入*/break;temp=(Node*) malloc (sizeof(Node) );temp->elem=ch;temp->next=NULL;current->next=temp;/*當前節點的后驅指向新節點*/current=temp;/*當前節點為鏈表尾節點*/}current->next=head;/*尾節點指向頭節點*/return head;}``二、鏈表操作包括單鏈表的增加節點、刪除節點、輸出鏈表等。/插入節點/
Node*InsertNode(Node*head ,char elem) { if( NULL== head|| NULL== elem ) return head;
Node*current=head->next;/當前節點/ Node*prev=head;/前驅節點/ Node*temp;/過渡節點/
while(current)/移動至尾節點/ { prev=current; current=current->next; }
temp=(Node*) malloc(sizeof(Node) ); temp->elem=elem; temp->next=NULL; prev->next=temp;/尾節點的后驅指向新節點/
return head;
}
/* 輸出鏈表 */ void PrintList(Node*head) { Node* current=head->next; cout<<”/n List are:”; while(NULL!= current) { if(NULL!= current->elem) coutelem; current=current->next; } cout<<”/n”; }
三、單鏈表逆置單鏈表逆置在各公司的筆試題中比較常見，以下是其中一種實現。算法描述：將鏈表中每一個節點插入到頭結點之后。單鏈表逆置/單鏈表逆置/ Node*ReverseList(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head; if(NULL== head->next->next) return head;
Node*curr=head->next;/當前節點/ head->next=NULL; Node*temp;
while(curr) { temp=curr->next;/暫存下一個節點/ /把當前節點插入到head節點后/ curr->next=head->next; head->next=curr;
curr=temp;/移動至下一個節點/ }
return head;
}
四、求單鏈表中間節點在筆試題中比較常見，通常題目描述是：給出一個單鏈表，不知道節點N的值，怎樣只遍歷一次就可以求出中間節點。算法描述：設立兩個指針p1,p2，p1每次移動1個節點位置，p2每次移動2個節點位置，當p2移動到尾節點時，p1指向中間節點。代碼如下：/求中間節點/ Node* MiddleNode(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head->next;
Node*p1,*p2; p1=head; p2=head;
while(p2->next) { /p2節點移動2個節點位置/ p2=p2->next; if(p2->next)/判斷p2后驅節點是否存在，存在則再移動一次/ p2=p2->next; /p1節點移動1個節點位置/ p1=p1->next; } return p1; }
五、合并有序單鏈表問題描述：合并2個有序單鏈表，合并后的鏈表也是排好序的。算法描述：對鏈表A中的每一個節點元素，查找其在鏈表B中的插入位置，并在B中插入該元素。代碼如下：/合并有序單鏈表/ Node* MergeList(Node* h1,Node* h2) { if(NULL== h1|| NULL== h2) return h1; if(NULL== h1->next ) return h2; if(NULL== h2->next) return h1;
Node* curr1,*curr2,*prev1,*temp; prev1=h1;/鏈表1的前驅節點/ curr1=h1->next;/鏈表1的當前節點/ curr2=h2->next;/鏈表2的當前節點/ temp=h2; while(curr2) { while(curr1&& curr1->elemelem)/鏈表1指針移動至大或等于鏈表2當前元素的位置/ prev1=curr1,curr1=curr1->next;
/在鏈表1中插入鏈表2的當前元素/ temp=curr2->next;/暫存鏈表2的下一個節點/ prev1->next=curr2; curr2->next=curr1;
/鏈表1移動至新節點/ curr1=curr2; /鏈表2移動至下一個節點/ curr2=temp; } return h1; }
六、判斷鏈表是否有環判斷鏈表是否有環即是判斷鏈表是否為循環鏈表，算法較為簡單，一次遍歷判斷尾指針是否指向頭指針即可。代碼如下：/判斷鏈表是否有環(循環鏈表)/ bool IsCycleList(Node*head) { if(NULL== head) return false; if(NULL== head->next) return false; Node*current=head->next; while(current) { if(head== current->next) return true; current=current->next; } return false; }
“`
新聞熱點
疑難解答
