单链表操作大集合代码,C代码库,德仔网

代码语言
代码分类
【C】单链表操作大集合
作者:弄月流影 / 发布于2013/8/20/ 760

	//单链表操作列表
	//1.创建链表
	//2.打印链表
	//3.排序链表
	//4.找出链表中倒数第m个元素
	//5.从一个未排序的链表中移除重复的项
	//6.链表反向输出,用栈实现
	//7.链表反向输出,用递归实现
	#include<iostream>
	#include<cstdlib>
	#include<stack>
	using namespace std;
	typedef struct node
	{
	 int data;
	 struct node *next;
	}node,*link;
	//创建链表
	void createLink(node **head)
	{
	 int n,num;
	 cout<<"input num of node:\n";
	 cin>>n;
	 cout<<"input the values of node:\n";
	 for(int i=0;i<n;i++)
	 {
	 cin>>num;
	 link pnode = new node;
	 pnode->data=num;
	 pnode->next=(*head);
	 (*head)=pnode;
	 }
	}
	//打印链表
	void printLink(link head)
	{
	 link pnode=head;
	 cout<<"print the link:\n";
	 while(pnode!=NULL)
	 {
	 cout<<pnode->data<<" ";
	 pnode=pnode->next;
	 }
	 cout<<endl;
	}
	//排序链表
	void sortLink(link *head)
	{
	 if((*head)==NULL)
	 return;
	 link p,q,r,s;
	 p=(*head)->next;//插入排序从第二个节点开始
	 (*head)->next=NULL;
	 while(p)
	 {
	 s=p->next;//保存下一个节点
	 if(p->data<(*head)->data)//比头结点还小，则成为新的头结点
	 {
	 p->next=(*head);
	 (*head)=p;
	 }
	 else
	 {
	 q=(*head);
	 r=(*head)->next;
	 while(r&&r->data<p->data)
	 {
	 q=r;
	 r=r->next;
	 }
	 p->next=q->next;
	 q->next=p;
	 }
	 p=s;
	 }
	}
	//找出链表中倒数第m个元素
	link findMToLastElement(link head,int m)
	{
	 //处理链表为空或者m输入错误
	 if(head==NULL||m<=0)
	 return NULL;
	 link p,q;
	 p=head;
	 for(int i=0;i<m;i++)
	 {
	 if(p->next)
	 p=p->next;
	 else
	 return NULL;//处理节点数小于m
	 }
	 q=head;
	 while(p)
	 {
	 p=p->next;
	 q=q->next;
	 }
	 return q;
	}
	//从一个未排序的链表中移除重复的项
	void removedulicate(link head)
	{
	 if(head==NULL)
	 return;
	 link p,q,r;
	 p=head;
	 while(p)
	 {
	 r=p;
	 q=p->next;
	 while(q)
	 {
	 if(q->data!=p->data)
	 {
	 r=q;
	 q=q->next;
	 }
	 else
	 {
	 r->next=q->next;
	 delete q;
	 q=r->next;
	 }
	 }
	 p=p->next;
	 }
	}
	//链表反向输出,用栈实现
	void printListReversed(link head)
	{
	 stack<link> stackList;
	 link p = head;
	 while(p)
	 {
	 stackList.push(p);
	 p=p->next;
	 }
	 cout<<"print the link reversed:\n";
	 while(!stackList.empty())
	 {
	 p=stackList.top();
	 stackList.pop();
	 cout<<p->data<<" ";
	 }
	 cout<<endl;
	}
	//链表反向输出,用递归实现
	void printListReversed2(link head)
	{
	 if(head)
	 {
	 if(head->next)
	 printListReversed2(head->next);
	 cout<<head->data<<" ";
	 }
	}
	int main()
	{
	 link head=NULL;
	 createLink(&head);//先输入总个数
	 printLink(head);
	 printListReversed(head);
	 cout<<"print the link reversed:\n";
	 printListReversed2(head);
	 cout<<endl;
	 cout<<"sort the link\n";
	 sortLink(&head);
	 printLink(head);
	 int m;
	 cin>>m;
	 link p = findMToLastElement(head,m);
	 if(p)
	 cout<<p->data<<endl;
	 else
	 cout<<"not fount"<<endl;
	 system("pause");
	 return 0;
	}
试试其它关键字
　单链表　
同语言下
可能有用的
弄月流影贡献的其它代码(1)
.单链表操作大集合