17_2_1.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <stdlib.h>
#define MAX_SIZE 200

struct Node
{
	int data;		// 单链表结点的数据
	Node *next;		// 指向下一个结点的指针
};

/*
@ CreateList
前置条件：	数组存在
输入：		数组和数组长度
功能：		创建一个单链表
输出：		单链表的头结点
后置条件：	单链表被创建
*/
Node *CreateList(int a[], int n)
{
	Node *p = new Node;
	Node *first = p;
	for (int i = 0; i < n; i++)
	{
		Node *q		= new Node;
		q->data		= a[i];
		p->next		= q;
		p			= p->next;
	}
	p->next = NULL;
	return first;
}

/*
@ PrintList
前置条件：	单链表存在
输入：		单链表的头结点
功能：		输出单链表的序列
输出：		单链表的序列
后置条件：	单链表不变
*/
void PrintList(Node *first)
{
	Node *p = first->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

void main()
{
	// 输入区
	cout << "请输入要排序的数字序列，输入#结束：" << endl;
	
	int a[MAX_SIZE];
	int i = 0;
	char c[8];
	while (c[0] != '#')
	{
		cin >> c;
		if (c[0] != '#')
			a[i] = atoi(c);
		i++;
	}
	int n = i - 1;
	
	/*
	// 这段语句用于生成一定范围的数据

	for (i = 0; i < 100; i++)
		a[i] = 100 - i;
	n = i;
	*/

	// Main Program
	Node *first	= CreateList(a, n);
	Node *pre	= first;
	Node *p		= first->next;
	Node *sEnd	= first->next;
	Node *q		= first->next->next;
	// 统计
	int cpr = 0;
	int run = 0;
	// end统计
	while (q)
	{
		while (p->data < q->data)
		{
			pre = p;
			p	= p->next;
			run++;
		}
		if (p != q)
		{
			Node *u		= q->next;
			pre->next	= q;
			q->next		= p;
			sEnd->next	= u;
			q			= u;
			run			+= 5;
		}
		else
		{
			q		= q->next;
			sEnd	= sEnd->next;
			run		+= 2;
		}
		pre		= first;
		p		= first->next;
		cpr++;
		run += 2;
	}
	cout << "排序后的结果为："	<< endl;
	PrintList(first);
	cout << "比较次数为："		<< cpr << endl;
	cout << "语句运行次数为："	<< run << endl;
}