太原理工大学软件工程2017课设

1.1【问题描述】

体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号

小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再

插入队列。 例如，下面给出了一组移动的例子，例子中学生的人数为 8 人。

0）初始队列中学生的学号依次为 1, 2, 3, 4, 5, 6, 7, 8；

1）第一次调整，命令为“3 号同学向后移动 2”，表示 3 号同学出队，向后移动 2 名同学的距离，再插入到队列中，新队列中学生的学号依次为 1, 2, 4, 5, 3, 6, 7, 8；

2）第二次调整，命令为“8 号同学向前移动 3”，表示 8 号同学出队，向前移动 3 名同学的距离，再插入到队列中，新队列中学生的学号依次为 1, 2, 4, 5, 8, 3, 6, 7；

3）第三次调整，命令为“3 号同学向前移动 2”，表示 3 号同学出队，向前移动 2 名同学的距离，再插入到队列中，新队列中学生的学号依次为 1, 2, 4, 3, 5, 8, 6, 7。

小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？

请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移

动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动

到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于

对应同学前面的人数则该同学会移动到队列的最前面。

1.2【输入输出数据格式】

输入格式：

输入的第一行包含一个整数 n，表示学生的数量，学生的学号由 1 到 n 编号。第二行包含

一个整数 m，表示调整的次数。接下来 m 行，每行两个整数 p, q，如果 q 为正，表示学号为 p 的同学向后 移动 q，如果 q 为负，表示学号为 p 的同学向前移动-q。 1 ≤ n，m ≤ 1000

输出格式:

输出一行，包含 n 个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。  

#include <stdio.h>
#include <malloc.h>

/* 结构体：学生节点 */ 
typedef struct studentNode {
	// 学号
    int num;
    // 上一个同学： 如果是第一个同学则此属性为空 
    struct studentNode *before;
    // 下一个同学： 如果是最后一个同学则此属性为空 
    struct studentNode *next;
} student;

/* 创建链表（n：节点个数） */
student *creat(int n) {
	// 定义 头节点，普通节点，尾部节点
	student *head, *node, *end;
	// 初始化头结点（前一个节点和后一个节点都为空）
	head = (student*)malloc(sizeof(student));
	head->before = NULL;
	head->next = NULL; 
	// 初始化链表(此时end节点表示的是头结点) 
	end = head;
	for(int i = 1; i <= n; i++) {
		// 生成一个新的节点, 并接到end的后面 
		node = (student*)malloc(sizeof(student));
		// 当前节点接到上一个节点 
		node->before = end; 
		node->num = i;
		node->next = NULL;
		// 上一个节点接到当前节点 
		end->next = node;
		end = node;
	}
	// 返回头结点 
	return head;
}

/* 打印链表的num属性 */
void printStudent(student* head) {
	student *node = head;
	while(node->next != NULL) {
		printf("%d ", node->next->num);
		node = node->next;
	}
	printf("\n");
}

/* 交换两个节点的位置：b与b的前一位a交换位置 */
void change(student* a, student* b) {
	if(a == NULL || b == NULL) {
		printf("# 要移动的节点越界\n");
	}
	// x：a的前一位  y：b的后一位 
	student *x = a->before, *y = b->next;
	if(x != NULL) {
		x->next = b;
	}
	a->before = b;
	a->next = y;
	b->before = x;
	b->next = a;
	if(y != NULL) {
		y->before = a;
	}
}

/* 移动节点 */
void move(student* head, int id, int num) {

	// 找到要移动的节点 
	student *move = head->next;
	while(move != NULL && move->num != id) {
		move = move->next;
	}
	
	// 记录要插入哪个节点的前面或后面 
	student *node = move;
	// 记录移动的次数 
	int n = 0;
	if(num > 0) {
		// 向后移动 
		while(node->next != NULL && n != num) {
			change(move, move->next);
			node = node->next;
			n++;
		}
	} else if(num < 0) {
		// 向前移动 
		while(node->before != NULL && node->before != head && n != -num) {
			node = node->before;
			change(move->before, move);
			n++;
		}
	}
}

/* 学生排队 */
int main(){
	
	// 学生数量 
	int stuNum = 0;
	printf("# 输入学生数量： \n");
	scanf("%d", &stuNum); 
	// 创建链表，返回头结点 
	student *head = creat(stuNum);
	
	// 移动几个学生 
	int changeNum = 0;
	printf("# 请输入要移动几个学生： \n");
	scanf("%d", &changeNum); 
	// 学号、向后移动几位
	int id = 0, num = 0; 
	// 移动
	for(int i = 0; i < changeNum; i++) {
		printf("# 请输入哪个学生向后移动几位：(负数为向前移动) \n");
		scanf("%d %d", &id, &num);
		/* 找出要移动的学生当前位置 */
		int n = 1; 
		student *m = head->next;
		while(m != NULL && m->num != id) {
			m = m->next;
			n++;
		}
		/* 判断是否越界 */ 
		if((n + num) <= stuNum && (n + num) > 0) {
			// 没有越界 : 移动并打印当前站位 
			move(head, id, num);
			printStudent(head);
		} else {
			// 越界 
			printf("移动位数越界\n");
		}
	}
	return 0;
}

3.1【问题描述】

假设有如下的英文文本文档：（文件名是：Happiness.txt）

What Is Happiness

Most of us probably don’t believe we need a formal definition of happiness; we know it

when we feel it, and we often use the term to describe a range of positive emotions,

including joy, pride, contentment, and gratitude.

But to understand the causes and effects of happiness, researchers first need to define

it. Many of them use the term interchangeably with “subjective well-being,” which they

measure by simply asking people to report how satisfied they feel with their own lives and

how much positive and negative emotion they’re experiencing. In her 2007 book The How

of Happiness, positive psychology researcher Sonja Lyubomirsky elaborates, describing

happiness as “the experience of joy, contentment, or positive well being, combined with a

sense that one’s life is good, meaningful, and worthwhile.”

That definition resonates with us here at Greater Good: It captures the fleeting positive

emotions that come with happiness, along with a deeper sense of meaning and purpose in

life and suggests how these emotions and sense of meaning reinforce one another.

设计 C 或 C++程序，统计在这样的英文文本文件中，出现了多少个单词（不区分大小写），每个单词出现了几次。连续的英文字符都认为是单词(不包括数字)，单词之间用空格或标点符号分隔。

3.2【设计需求及分析】

要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。

线性表的顺序存储结构如下：（必须使用如下定义的存储结构，否则无效）

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量

#define LISTINCREMENT 10 //线性表存储空间的分配增量

typedef struct{

char word[21] //存储单词，不超过 20 个字符

int count; //单词出现的次数

} ElemType;

typedef struct{

ElemType *elem; //存储空间基址

int length; //当前长度

int listsize; //当前分配的存储容量

} SqList;

3.3【功能设计】

3.3.1 实现顺序表的基本操作（必须使用下面给定的函数名和参数表，否则无效）

⑴顺序表的初始化：InitList(SqList &L)

⑵顺序表上查找指定的单词：LocateElem(SqList &L,char *s)

若找到，单词的出现次数增 1，返回 0，否则返回该单词的插入位置。

⑶在顺序表上插入新的单词：InsertList(SqList &L,int i，char *s)

要求按字典顺序有序。新单词的出现次数为 1.

⑷输出顺序表上存储的单词统计信息：PrintList(SqList &L)

输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100    //线性表存储空间的初始分配量 
#define LISTINCREMENT 10      //线性表存储空间的分配增量 

typedef struct{ 
    char word[21];            //存储单词，不超过 20 个字符 
    int count;                //单词出现的次数 
} ElemType; 

typedef struct{ 
    ElemType *elem;           //存储空间基址 
    int length;               //当前长度 
	int listsize;             //当前分配的存储容量 
} SqList; 

// 顺序表的初始化：
void InitList(SqList &L) {
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(L.elem == NULL)  printf("# ******* InitList Field *****\n");
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	printf("# ******* InitList Finished : %d *****\n", L.listsize);
}

// 在顺序表上插入新的单词：要求按字典顺序有序。新单词的出现次数为 1. 
void InsertList(SqList &L, int i, char *s) {
	// 扩充表长 
	if(sizeof(ElemType) + L.length >= L.listsize || i >= L.listsize) {
		L.listsize = L.listsize + LISTINCREMENT;
		ElemType *newList;
		newList = (ElemType*)realloc(L.elem, L.listsize * sizeof(ElemType));
		L.elem = newList;
		printf("# ******* Extend SqList : %d *****\n", L.listsize);
	}
	// 插入新单词 
	for(int j = L.length; j > i; j--) {
		L.elem[j] = L.elem[j-1];
	}
	strcpy(L.elem[i].word, s);
	printf("# Insert Word ---> %s \n", s);
	L.elem[i].count = 1;
	L.length++;
}

// 顺序表上查找指定的单词：若找到，单词的出现次数增 1，返回 0，否则返回该单词的插入位置。
int LocateElem(SqList &L, char *s) {
	for(int i = 0; i < L.length - 1; i++) {
		if(strcmp(s, L.elem[i].word) == 0) {
			// 找到了
			L.elem[i].count++;
			return -1; 
		} else if(strcmp(s, L.elem[i].word) < 0) {
			return i;
		}
	}
	return L.length;
}

// 输出顺序表上存储的单词统计信息：输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。 
void PrintList(SqList &L) {
	printf("\n"); 
	printf("# 开始打印文件\n");
	for(int i = 0; i < L.length; i++) {
		printf("# %s --> %d\n", L.elem[i].word, L.elem[i].count);
	}
	printf("# 文件打印完成\n");
}
  

int main() {
	int j = 0, mark = 0;
	SqList L;
	InitList(L);
	char word[21], ch;
	char fileName[50] = "D://img//Happiness.txt";
	
	FILE *fp;
	if(NULL == (fp = fopen(fileName, "r"))) {
		printf("# 文件打开失败");
		exit(0);
	}
	ch = fgetc(fp);
	while(ch != EOF) {
		if(ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z') {
			ch = ch >= 'A' && ch <= 'Z' ? ch+32 : ch;
			word[j++] = ch;
			mark = 1;
		} else {
			if(mark == 1) {
				word[j] = '\0';
				mark = 0;
				j = 0;
				int i = LocateElem(L, word);
				if(i != -1) {
					InsertList(L, i, word);
				}
			}
		}
		ch = fgetc(fp);
	}
	fclose(fp); 
	
	PrintList(L);
	return 0;
} 

4.1【问题描述】

用分数形式表示的有理数类如下：

class Rational {

private:

int x,y; //成员变量 x 和 y，分别存放分子和分母

public:

Rational(int a=1,int b=1); //具有默认参数的构造函数，默认值为 1

Rational Add(Rational &r); //求两个分数的和

Rational Sub(Rational &r); //求两个分数的差

Rational Mul(Rational &r); //求两个分数的积

Rational Div(Rational &r); //求两个分数的商

Rational operator+(Rational &r); //重载“+”运算符，求两个分数的和

Rational operator-(Rational &r); //重载“-”运算符，求两个分数的差

Rational operator*(Rational &r); //重载“*”运算符，求两个分数的积

Rational operator/(Rational &r); //重载“/”运算符，求两个分数的商

int Divisor(int a,int b); //求最大公约数

friend ostream& operator<<(ostream &output,Rational &r); //以 x/y 的形式输出分数

};

4.2【基本要求】

1.成员变量 x 和 y，分别存放分子和分母, 要求分数以最简形式存放。例如：分数 2/4 应简化为 1/2。

2.定义成员函数 Add、Sub、Mul 和 Div，求两个分数的和差积商。计算结果仍以最简形式存放。

3.重载运算符“+、-、*、/”，求两个分数的和差积商。计算结果仍以最简形式存放。

4.定义友元函数，重载“<<”运算符，以 x/y 的形式输出分数。例如，有如下的主函数：

int main(){

Rational a(5,15),b(1,-2),c;

cout<<"a="<<a<<endl;

cout<<"b="<<b<<endl;

c=a.Add(b); //c=a+b;

cout<<"a+b="<<c<<endl;

c=a.Sub(b); //c=a-b;

cout<<"a-b="<<c<<endl;

c=a.Mul(b); //c=a*b;

cout<<"a*b="<<c<<endl;

c=a.Div(b); //c=a/b;

cout<<"a/b="<<c<<endl;

}

#include <iostream>
using namespace std;

/* Rational类 */
class Rational{
	private:
		//成员变量 x 和 y，分别存放分子和分母
		int x, y; 
	public:
		Rational(int a=1,int b=1);  //具有默认参数的构造函数，默认值为 1
		Rational Add(Rational &r); //求两个分数的和
		Rational Sub(Rational &r);  //求两个分数的差
		Rational Mul(Rational &r); //求两个分数的积
		Rational Div(Rational &r); //求两个分数的商
		Rational operator+(Rational &r); //重载“+”运算符，求两个分数的和
		Rational operator-(Rational &r); //重载“-”运算符，求两个分数的差
		Rational operator*(Rational &r); //重载“*”运算符，求两个分数的积
		Rational operator/(Rational &r); //重载“/”运算符，求两个分数的商
		int Divisor(int a,int b); //求最大公约数
		friend ostream& operator<<(ostream &output,Rational &r); //以 x/y 的形式输出分数
};

//具有默认参数的构造函数，默认值为 1
Rational::Rational(int a, int b) {
	int max = Divisor(a, b);
	x = a / max;
	y = b / max;
}  

//求两个分数的和
Rational Rational::Add(Rational &r) {
	int zi = x * r.y + r.x * y;
	int mu = y * r.y;
	return Rational(zi, mu);
}

//求两个分数的差
Rational Rational::Sub(Rational &r) {
	int zi = x * r.y - r.x * y;
	int mu = y * r.y;
	return Rational(zi, mu);
} 

//求两个分数的积
Rational Rational::Mul(Rational &r) {
	int zi = x * r.x;
	int mu = y * r.y;
	return Rational(zi, mu);
}

//求两个分数的商
Rational Rational::Div(Rational &r) {
	int zi = x * r.y;
	int mu = y * r.x;
	return Rational(zi, mu);
} 

//重载“+”运算符，求两个分数的和
Rational Rational::operator+(Rational &r) {
	return this->Add(r);
} 
 
//重载“-”运算符，求两个分数的差
Rational Rational::operator-(Rational &r) {
	return this->Sub(r);
} 

//重载“*”运算符，求两个分数的积
Rational Rational::operator*(Rational &r) {
	return this->Mul(r);
} 
 
//重载“/”运算符，求两个分数的商
Rational Rational::operator/(Rational &r) {
	return this->Div(r);
} 

//求最大公约数
int Rational::Divisor(int a,int b) {
	return b==0 ? a : Divisor(b,a%b);
}

// 重载输出运算符 
ostream& operator<<(ostream &output,Rational &r) {
	output<<r.x<<"/"<<r.y;
}

int main(){
	Rational a(5,15),b(1,-2),c;
	cout<<"a="<<a<<endl;
	cout<<"b="<<b<<endl;
	c=a.Add(b); //c=a+b;
	cout<<"a+b="<<c<<endl;
	c=a.Sub(b); //c=a-b;
	cout<<"a-b="<<c<<endl;
	c=a.Mul(b); //c=a*b;
	cout<<"a*b="<<c<<endl;
	c=a.Div(b); //c=a/b;
	cout<<"a/b="<<c<<endl;
}