|
链表的常见操作 链表是数据结构的重要内容在计算机程序中应用广泛同时也是各公司笔试题目的重点 以下简单实现了链表的一些操作包括创建增加节点删除节点单链表逆置合并有序链表等 一链表创建 链表主要有三种形式包括单链表双链表和循环链表 单链表每个节点只包含一个后驱指针双链表节点同时包含一个前驱指针和一个后驱指针循环链表的尾节点的后驱指向头节点 代码如下 /*单链表节点结构*/
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()
{
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()
{
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()
{
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)
cout<<setw()<<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的值怎样只遍历一次就可以求出中间节点 算法描述设立两个指针ppp每次移动个节点位置p每次移动个节点位置当p移动到尾节点时p指向中间节点 代码如下 求中间节点 /*求中间节点*/
Node* MiddleNode(Node*head)
{
if(NULL== head)
return head;
if(NULL== head>next)
return head>next; Node*p*p;
p=head;
p=head; while(p>next)
{
/*p节点移动个节点位置*/
p=p>next;
if(p>next)/*判断p后驱节点是否存在存在则再移动一次*/
p=p>next;
/*p节点移动个节点位置*/
p=p>next; }
return p; } 五合并有序单链表 问题描述合并个有序单链表合并后的链表也是排好序的 算法描述对链表A中的每一个节点元素查找其在链表B中的插入位置并在B中插入该元素 代码如下 合并有序单链表/*合并有序单链表*/
Node* MergeList(Node* hNode* h)
{
if(NULL== h|| NULL== h)
return h;
if(NULL== h>next )
return h;
if(NULL== h>next)
return h; Node* curr*curr*prev*temp;
prev=h;/*链表的前驱节点*/
curr=h>next;/*链表的当前节点*/
curr=h>next;/*链表的当前节点*/
temp=h;
while(curr)
{
while(curr&& curr>elem< curr>elem)/*链表指针移动至大或等于链表当前元素的位置*/
prev=currcurr=curr>next; /*在链表中插入链表的当前元素*/
temp=curr>next;/*暂存链表的下一个节点*/
prev>next=curr;
curr>next=curr; /*链表移动至新节点*/
curr=curr;
/*链表移动至下一个节点*/
curr=temp;
} return h; } 六判断链表是否有环 判断链表是否有环即是判断链表是否为循环链表算法较为简单一次遍历判断尾指针是否指向头指针即可 代码如下 /*判断链表是否有环(循环链表)*/
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;
} 七总结 以上实现了链表的一些常见操作源文件LinkListcpp全部代码如下 /*
* 作者 达闻东
* 修改日期 :
* 描述 实现链表的常见操作
*
*/
#include<iostream>
#include<iomanip>
using namespace std; /*单链表节点结构*/
typedefstruct NodeType
{
char elem;
NodeType*next;
}Node; /*双链表节点结构*/
typedefstruct 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()
{
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()<<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*headchar 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*p*p;
p=head;
p=head; while(p>next)
{
/*p节点移动个节点位置*/
p=p>next;
if(p>next)/*判断p后驱节点是否存在存在则再移动一次*/
p=p>next;
/*p节点移动个节点位置*/
p=p>next; }
return p; } /*=============================================================================*/ /*合并有序单链表*/
Node* MergeList(Node* hNode* h)
{
if(NULL== h|| NULL== h)
return h;
if(NULL== h>next )
return h;
if(NULL== h>next)
return h; Node* curr*curr*prev*temp;
prev=h;/*链表的前驱节点*/
curr=h>next;/*链表的当前节点*/
curr=h>next;/*链表的当前节点*/
temp=h;
while(curr)
{
while(curr&& curr>elem< curr>elem)/*链表指针移动至大或等于链表当前元素的位置*/
prev=currcurr=curr>next; /*在链表中插入链表的当前元素*/
temp=curr>next;/*暂存链表的下一个节点*/
prev>next=curr;
curr>next=curr; /*链表移动至新节点*/
curr=curr;
/*链表移动至下一个节点*/
curr=temp;
} return h; } /*=============================================================================*/ /*创建双链表*/
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()
{
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()<<p>elem; } cout<<&#;\n DoubleList are:&#;;
while(p>prev)
{
if(p>elem)
cout<<setw()<<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()
{
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* head*head;
DNode* dHead;
char ch;
head= NULL;
head=NULL;
head=NULL;
dHead=NULL; //head=(Node*) malloc ( sizeof( Node) );
//head>next = NULL; //创建单链表
head=CreateList(head);
PrintList(head); head=CreateList(head);
PrintList(head); //插入节点 cout<<&#;\n input elem to insert:&#;;
cin>>ch;
InsertNode(headch);
PrintList(head); //删除节点 cout<<&#;\n input elem to delete:&#;;
cin>>ch;
DeleteNode(headch);
PrintList(head); //单链表逆置 head=ReverseList(head);
cout<<&#;\n Reversed !&#;;
PrintList(head); //求中间节点 p=MiddleNode(head);
cout<<&#;\n Middle Node is:&#;;
cout<<p>elem<<endl; //合并有序单链表 MergeList(headhead);
cout<<&#;\n Merged!&#;;
PrintList(head); //创建双链表 dHead=DoubleList(dHead);
PrintDoubleList(dHead); /*创建循环链表并判断是否有环*/
head=CycleList(head);
cout<<IsCycleList(head);
return ;
} |
