单链表的应用--判断单链表是否有序

单链表的应用--判断单链表是否有序

  判断单链表是否有序，利用前文写好的链表的框架，在链表类中补充IsOrdering方法。

对单链表排序

一、问题分析二、代码分析

1.链表类linkList2.链表方法IsOrdering 三、测试代码

1.主函数2.输出结果 四、源代码获取（免积分）

一、问题分析

  给你一个单链表，判断其是否为升序排列。（一般默认情况下，都是讨论升序排列。）

二、代码分析

  判断单链表是否有序只需要判断两个相邻的元素结点的值是否符合排序要求即可，一旦发现不符合排序要求的结点，返回0；如果直到比较结束都没有返回0，则最终返回1，说明链表是有序的。

1.链表类linkList

  在链表类中声明IsOrdering方法。

template 
class linkList{
	public:
		linkList();//构造函数 
		~linkList();//析构函数 
		void Insert(int i ,ElemType x);//插入函数 
		void PrintList();//打印所有元素  
		int Length();//获取链表长度
		ElemType Get(int i) ;//按位查找，返回第i个元素的值
		int Locate(ElemType x) ;//按值查找，返回x在单链表中的位置
		ElemType Delete(int i) ;//删除第i个元素 
		void DeleteNthFromEnd(int n) ;//删除倒数第n个元素
		int IsOrdering() ;
	private:
		Node* first; //头指针 
};

2.链表方法IsOrdering

  算法的伪代码如下：

1.p指向首元结点，flag=1；如果p不为空，则q=p->next;
2.当p和q都不为空则进入循环：
	2.1如果p->data大于q->data，则flag=0,break;
	2.2否则p和q分别后移
3.返回flag

  链表方法IsOrdering：

template 
int  linkList::IsOrdering()
{
	Node* p=first->next;
	Node* q;
	int flag=1;
	if(p!=NULL)
	{
		q=p->next;
	}
	
	while((p!=NULL)&&(q!=NULL))
	{
		if(p->data>q->data)
		{
			flag=0;
			break;
		}
		else
		{
			p=q;
			q=q->next;
		}
	}
	return flag;
}

三、测试代码 1.主函数

#include 
#include "linkList.h"
#include "linkList.cpp" 

using namespace std;

int  main() {
	linkList L;
	
	L.Insert(1,1);
	L.Insert(2,1);
	L.Insert(3,3);
	L.Insert(4,4);
	L.Insert(5,4);	
	L.Insert(6,5);	
	
	cout<<"原先链表数据:" < 
2.输出结果 
原先链表数据:
1 1 3 4 4 5
原先的链表是否有序？是
插入一个元素之后的链表元素:
1 1 8 3 4 4 5
插入一个元素之后的链表是否有序？否
 
四、源代码获取（免积分） 
判断单链表是否有序
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714409.html