链表的常见操作

技术2022-05-20 48

链表是数据结构的重要内容，在计算机程序中应用广泛，同时也是各公司笔试题目的重点。

　　以下简单实现了链表的一些操作，包括创建、增加节点、删除节点、单链表逆置、合并有序链表等。

一、链表创建

　　链表主要有三种形式，包括单链表、双链表和循环链表。

　　单链表每个节点只包含一个后驱指针，双链表节点同时包含一个前驱指针和一个后驱指针，循环链表的尾节点的后驱指向头节点。

　　代码如下：

/* 单链表节点结构 */ 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;}

删除节点 / 删除节点 / Node DeleteNode(Node * head, char elem){ if (NULL == head || NULL == elem) return head; if (NULL == head -> next) return head; Node * prev, * current; prev = head; current = head -> next; while (current) { if (current -> elem == elem) /* 匹配节点元素 / { prev -> next = current -> next; / 前驱节点的后驱指向当前节点的下一个节点 / free(current); / 释放当前节点 / return head; } prev = current; current = current -> next; / 移动至下一个节点 / } return head;}

输出链表 / 输出链表 / void PrintList(Node head){ Node * current = head -> next; cout << " /n List are: " ; while (NULL != current) { if (NULL != current -> elem) cout << setw( 5 ) << current -> elem; 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 -> elem < curr2 -> elem) /* 链表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 ;}

七、总结　　以上实现了链表的一些常见操作，源文件LinkList.cpp全部代码如下：　 LinkList.cpp /* * 作者：达闻东 * 修改日期： 2010-04-28 17:10 * 描述：实现链表的常见操作 * */ #include < iostream > #include < iomanip > using namespace std; /* 单链表节点结构 */ 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;} /* ============================================================================= */ /* 输出链表 */ void PrintList(Node * head){ Node * current = head -> next; cout << " /n List are: " ; while (NULL != current) { if (NULL != current -> elem) cout << setw( 5 ) << current -> elem; current = current -> next; } cout << " /n " ;} /* ============================================================================= */ /* 插入节点 */ 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;} /* ============================================================================= */ /* 删除节点 */ Node * DeleteNode(Node * head, char elem){ if (NULL == head || NULL == elem) return head; if (NULL == head -> next) return head; Node * prev, * current; prev = head; current = head -> next; while (current) { if (current -> elem == elem) /* 匹配节点元素 */ { prev -> next = current -> next; /* 前驱节点的后驱指向当前节点的下一个节点 */ free(current); /* 释放当前节点 */ return head; } prev = current; current = current -> next; /* 移动至下一个节点 */ } return head;} /* ============================================================================= */ /* 单链表逆置 */ 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;} /* ============================================================================= */ /* 求中间节点 */ 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;} /* ============================================================================= */ /* 合并有序单链表 */ 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 -> elem < curr2 -> elem) /* 链表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;} /* ============================================================================= */ /* 创建双链表 */ 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;} /* ============================================================================= */ /* 输出双链表 */ void PrintDoubleList(DNode * head){ if (NULL == head) return ; DNode * p; p = head; cout << " /n DoubleList are: " ; while (p -> next) { p = p -> next; if (p -> elem) cout << setw( 5 ) << p -> elem; } cout << " /n DoubleList are: " ; while (p -> prev) { if (p -> elem) cout << setw( 5 ) << p -> elem; p = p -> prev; }} /* ============================================================================= */ /* 创建循环链表 */ 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;} /* ============================================================================= */ /* 判断链表是否有环(循环链表) */ 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 ;} int main(){ Node * head, * p; Node * head2, * head3; DNode * dHead; char ch; head = NULL; head2 = NULL; head3 = NULL; dHead = NULL; // head=(Node*) malloc ( sizeof( Node) ); // head->next = NULL; // 创建单链表 head = CreateList(head); PrintList(head); head2 = CreateList(head2); PrintList(head2); // 插入节点 cout << " /n input elem to insert: " ; cin >> ch; InsertNode(head,ch); PrintList(head); // 删除节点 cout << " /n input elem to delete: " ; cin >> ch; DeleteNode(head,ch); PrintList(head); // 单链表逆置 head = ReverseList(head); cout << " /n Reversed ! " ; PrintList(head); // 求中间节点 p = MiddleNode(head); cout << " /n Middle Node is: " ; cout << p -> elem << endl; // 合并有序单链表 MergeList(head,head2); cout << " /n Merged! " ; PrintList(head); // 创建双链表 dHead = DoubleList(dHead); PrintDoubleList(dHead); /* 创建循环链表并判断是否有环 */ head3 = CycleList(head3); cout << IsCycleList(head3); return 0 ;}

专利

最新回复(0)