《链表的常见操作》由会员分享，可在线阅读，更多相关《链表的常见操作（33页珍藏版）》请在金锄头文库上搜索。
1、http:/ struct NodeTypechar elem;NodeType *next;Node;/*双链表节点结构*/typedef struct DNodeTypechar elem;DNodeType *next;DNodeType *prev;DNode;田日创建单链表/*创建链表*/Node * CreateList(Node *head)if (NULL = head)/分配头节点空间head=(Node*)mallocsizeof(Node),head-next=NULL;Node *current=head , *temp;char ch;while (1)coutch;
2、if(# = ch)/*# 结束输入*/break;temp=(Node *) malloc sizeof(Node);temp-elem=ch;temp-next=NULL;current-next=temp;/*当前节点的后驱指向新节点*/ head;田日创建双链表/*创建双链表*/DNode * DoubleList(DNode *head)if (NULL = head)/分配头节点空间head=(DNode*)mallocsizeof(DNode) , head-prev=NULL , head-next=NULL;DNode *current=head ,*temp;char ch
3、;while (1)coutch;if(# = ch)/*# 结束输入*/break;temp=(DNode) malloc ( sizeof(DNode);temp-elem=ch;temp-next=NULL;田日创建循环链表/*创建循环链表*/Node* CycleList(Node *head)if (NULL = head)/*分配头节点空间*/head=(Node*)mallocsizeof(Node),head-next=NULL;Node *current=head , *temp;char ch;while (1)coutch;if(# = ch)/*# 结束输入*/brea
4、k;temp=(Node *) malloc sizeof(Node);temp-elem=ch;temp-next=NULL;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;/*前驱节点*/*
5、过渡节点*/prev=current;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;prev
6、-next=current-next; /*前驱节点的后驱指向当 前节点的下一个节点*/free(current);/*释放当前节点*/return head;prev=current;current=current-next;/* 移动至下一个节点*/return head;田日输出链表/*输出链表*/void PrintList(Node *head)Node * current=head-next;coutn List are:;while(NULL != current)coutsetW(elem;、单链表逆置单链表逆置在各公司的笔试题中比较常见，以下是其中一种实现。算法描述：将链表中
7、每一个节点插入到头结点之后。J3mT+j+J+-4 4 执毎歩骤代码如下：田日单链表逆置/*单链表逆置*/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节点后*/ cur
8、r-next=head-next;head-next=curr;curr=temp;/*移动至下一个节点*/return head;四、求单链表中间节点在笔试题中比较常见，通常题目描述是：给出一个单链表，不知道节点N的值，怎样只遍历一次就可 以求出中间节点。算法描述：设立两个指针p1,p2，pl每次移动1个节点位置，p2每次移动2个节点位置，当p2移 动到尾节点时， p1 指向中间节点。代码如下：田日求中间节点/*求中间节点*/Node * MiddleNode(Node *head) if(NULL = head)return head;if (NULL = head-next)return
9、 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,
10、Node * h2)if (NULL = hl | NULL = h2)return hi;if(NULL = h1-next )return h2;if(NULL = h2-next)return hi;Node * curr1,*curr2,*prev1,*temp;prev1=h1;/*链表1的前驱节点*/curr1=h1-next; /*链表1的当前节点*/ curr2=h2-next;/*链表2的当前节点*/temp=h2;while (curr2)while (curr1 & curr1-elem elem) /*链表 1 扌旨针移动至大或等于链表2当前元素的位置*/ prev1=
11、curr1,curr1=curr1-next;/*在链表1中插入链表2的当前元素*/ temp=curr2-next/*暂存链表2的下一个节点*/ prev1-next=curr2;curr2-next=curr1;/*链表1移动至新节点*/curr1=curr2;/*链表2移动至下一个节点*/c六、判断链表是否有环判断链表是否有环即是判断链表是否为循环链表，算法较为简单，一次遍历判断尾指针是否指向头指针即可。代码如下：田日判断链表是否有环/*判断链表是否有环(循环链表)*/bool IsCycleList(Node *head)if (NULL= head)return false;if(N
12、ULL = 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#includeusing namespace std;/*单链表节点结构*/typedef struct NodeTypechar elem;NodeType *next;Node;/*双链表节点结构*/typedef struct DNodeTypechar elem;DNodeType *next;DNodeType *prev;DNode;/*=*/*创建链表*/Node * CreateList(Node *head)if (NULL = head)/分配头节点空间head=(Node*)mallocsizeof(Node
