下载文档原格式
⽕车车厢重排问题2014-11-04主要数据结构：栈题⽬：⼀列⽕车要将n节车厢分别送往n个车站按1~n的次序编号，⽕车按照n,n-1,…1的编号次序经过车站。
假设车厢的编号就是其⽬的地车站的编号。
要求：给定⼀个任意的车厢排列次序。
重新排列车厢，使其按照从1到n的次序排列。
规定重排时，只能从⼊轨到缓冲铁轨，或者从缓冲铁轨到出轨。
总的思路：⾸先：将所需要重排的车厢编号从左到右依次输⼊数组carrage中；然后：对carrage中的元素进⾏从左往右逐个遍历，如果符合下⼀个输出，则直接将其输出，并且遍历所有的缓冲轨道，查找是否有符合下⼀个输出的车厢，有的话便将其输出，否则将其压⼊缓冲轨道未经优化的代码：1 #include <iostream>2 #include <stack>3using namespace std;45 stack<int> stack_final;678void Output(int& minH, int& minS, stack<int> H[], int k, int n) {9// put the car from the strack to the output line, and change the minH and minS10int index; // the index of the car11//delete the minist car number from the minS12 stack_final.push(H[minS].top());13 H[minS].pop();14 cout << "Move car " << minH << "from holding track " << minS << " to output line" << endl;15//serch all the track's top, find the new minH and minS16 minH = n+2;17for (int i= 0; i < k; i++) {18if (!H[i].empty() && (index = H[i].top()) < minH) {19 minH = index;20 minS = i;21 }22 }23 }2425bool Input(int c, int& minH, int& minS, stack<int> H[], int k, int n) {26// put the new car c into the track27// if there is no available track, then return false, else return true28// find the best track for the car c29// initial30int BestTrack = 0; //the best track now31int BestTop = n+1; //the best track's top car32int index; //the index for the car33// search the k track34for (int i= 0; i < k; i++) {35if (!H[i].empty()) {36 index = H[i].top();37if (c < index && index < BestTop) {38//the top car's number is the smallest39 BestTop = index;40 BestTrack = i;41 }42 } else { // the track is empty43if (!BestTrack) {44 BestTrack = i;45 }46 }47 }48if (!BestTrack) {49return false; //there is available track to use50 }51 H[BestTrack].push(c);52 cout << "Move car " << c << "from input to holding track " << BestTrack << endl;53//if it is essencial, then change the minH and minS54if (c < minH) {55 minH = c;56 minS = BestTrack;57 }58return true;59 }6061bool Railroad(int input[], int n, int k) {62//k63// if it resort succed, then return true, else return false64// create the stack according to the k65 stack<int> *H;66 H = new stack<int> [k];67int NowOut = 1; // the next number of car to putout68int minH = n+1; //the minist number car in the k69int minS; //the minist number's strack70// resort the car71for (int i = n-1; i >= 0; i--) {72int number = input[i];73if (number == NowOut) {74 cout << "Move car " << number << " from the input line to the output line\n";75 stack_final.push(number);76 NowOut++;77while (minH == NowOut) {78 Output (minH, minS, H, k, n);79 NowOut++;80 }81 } else {82int end = 0;83for (int j = i; j > 0; j--) {84if (input[j-1] < input[j]) {85 end = j;86break;87 }88 }89for (int j = end; j <= i; j++) {90if (!Input (input[j], minH, minS, H, k, n)) {91return false;92 }93 }94if (end) {95 i = end;96 }97 }98 }99return true;100 }101102int main() {103int n, *input;104 cin >> n;105 input = new int[n];106for (int i = 0; i < n; i++) {107 cin >> input[i];108 }109if (Railroad(input, n, n-1)) {110 cout << "resort succed!\n";111while (!stack_final.empty()) {112 cout << stack_final.top() << "";113 stack_final.pop();114 }115 } else {116 cout << "failed\n";117 }118 }View Code经过优化之后的代码：增加的条件：车厢可以从排在后⾯的缓冲轨道移到前⾯的缓冲轨道。
实验报告了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。
所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过转轨站完成。
在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。
假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。
②基本要求●设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；●设计并实现车厢重排算法；●分析算法的时间性能。
③思考●如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？二、数据结构设计迷宫问题和火车重排问题可以通过栈与队列实现的。
迷宫的进出和车厢的出入轨和缓冲轨主要是对栈与队列的判断和操作。
int empty( STLink top[],int n) /*判断是否为空*/{return (top[n]==NULL);}int push(STLink top[],int A,int m) /*入栈*/{STLink p;if(!(p=(STLink)malloc(LEN)))return 0;else{p->data=A;p->link=top[m];top[m]=p;return 1;}}int pop(STLink top[],int m) /*出栈*/{int A;STLink p;p=top[m];A=p->data;top[m]=top[m]->link;free(p);return A;}struct Node{ /定义队列int data;Node* next;};三、算法设计1.迷宫问题：进入格子后，需要判断此时格子位置周围障碍物的位置，对其进行压栈，判断，然后看是否满足条件，满足就进栈，不满足就弹出，然后输出不能通过建立迷宫：typedef struct LStack{Element elem;struct LStack *next;}*PLStack;int InitStack(PLStack &S){S=NULL;return 1;}int StackEmpty(PLStack S){if(S==NULL)return 1;elsereturn 0;}int Push(PLStack &S, Element e){PLStack p;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return 1;}（2）.输出路径2.火车车厢排序六、实验收获与思考通过本次实验，进一步增强了对栈和队列的理解，明白的栈的先进后出和队列先进先出的方式，对压栈和出入栈与队列有了深刻认识。
数据结构实验报告实验名称:实验二一一栈和队学生姓名:申宇飞班级：班内序03号：学号：日期2013年11月18日：1- 实验要求1.1实验目的：通过选择卞面五个题目之一进行实现，掌握如卞内容：>进一步掌握指针、模板类、异常处理的使用>掌握栈的操作的实现方法>掌握队列的操作的实现方法>学习使用栈解决实际问题的能力>学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。
要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试mainO函数测试线性表的正确性。
2.程序分析2.1存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。
第］页北京邮电大学信息与通信工程学院data next栈顶栈底关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1)Node<T> * s = new Node<T>;2)p->data = x;3)p->next = top;4)top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1)if(EmptyO)throw" F溢“；2)T x = top->data;3)Node<T> * p = top;4)top = top->next;5)elete p;三、链栈的取栈顶元素算法步骤：自然语言描述：1、判断栈是否为空第3页2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(EmptyO)tlu'ow H卜溢"；2)Node<T>*p=top;3)cout«p->data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p 伪代码描述：1)Node<T>*p = top;2)while(p !=NULL)3)cout« p->data ;4)p = p->next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1)while(top)2)strnct Node <T> * p = top;3)top = top->next;4)deletep; 时间复杂的：0(1)。
实验2用堆栈解决火车车厢重排问题的编程一、目的通过对本次实验，我们应：1、加深对线性表、堆栈的认识；2、加深接口、类、索引器的认识；3、掌握堆栈数据结构，并应用堆栈编程解决实际问题。
二、实验准备1、软件准备：C#.net。
2、参考数据（示例）：文件夹“…\实验2\示例”中的数据。
三、实验背景描述1、问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。
假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。
车厢的编号与它们的目的地相同。
为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。
当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。
我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。
图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。
开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。
在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。
图3.1b 给出了按所要求的次序重新排列后的结果。
图2.1根据上面的描述，编写程序实现下面的功能：编写一算法实现火车车箱的重排；编写程序模拟图2.1所示的具有9节车厢的火车入轨和出轨的过程。
程序主界面设计如图2.2所示。
图2.22、问题分析为了重排车厢，需从前至后依次检查入轨上的所有车厢。
如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。
如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。
缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。
当缓冲铁轨上的车厢编号不是按照从顶到底的递增次序排列时，重排任务将无法完成。
新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v>u,且v是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。
火车车厢重排问题栈c语言以下是一个用C语言实现火车车厢重排问题的代码：```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int val;struct Node* next;} Node;typedef struct {Node* top;} Stack;Stack* createStack() {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->top = NULL;return stack;}int isEmpty(Stack* stack) {return (stack->top == NULL);}void push(Stack* stack, int val) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = val;newNode->next = stack->top;stack->top = newNode;}int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}int val = stack->top->val;Node* temp = stack->top;stack->top = stack->top->next;free(temp);return val;}int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}return stack->top->val;}int canReorder(int numCars, int cars[]) { Stack* stationStack = createStack(); Stack* branchStack = createStack(); int nextCar = 1;for (int i = 0; i < numCars; i++) {// 如果当前车厢和需要出站的车厢一致，直接出站if (cars[i] == nextCar) {nextCar++;continue;}// 将从站台出来的车厢压入分支轨道while (!isEmpty(stationStack) && peek(stationStack) == nextCar) {push(branchStack, pop(stationStack));nextCar++;}// 当前车厢进站push(stationStack, cars[i]);}// 如果分支轨道中的车厢可以按顺序出站，则返回1，否则返回0while (!isEmpty(branchStack)) {if (pop(branchStack) != nextCar) {return 0;}nextCar++;}return 1;}int main() {int numCars;int cars[MAX_SIZE];printf("Enter the number of train cars: ");scanf("%d", &numCars);printf("Enter the train car numbers: ");for (int i = 0; i < numCars; i++) {scanf("%d", &cars[i]);}int result = canReorder(numCars, cars);if (result) {printf("Yes, it is possible to reorder the train cars.\n"); } else {printf("No, it is not possible to reorder the train cars.\n"); }return 0;}```输入示例：```Enter the number of train cars: 5Enter the train car numbers: 3 1 2 4 5```输出示例：```Yes, it is possible to reorder the train cars. ```。
计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级 10级计算机工程
02
试验地点 计算机大楼计工教研室
学生学号 1005080222 指导教师 蔡琼 学生姓名 肖宇博
试验时间
2012-4-21
试验项目 算法与数据结构
试验类别
基础性（） 设计性（） 综合性（√） 其它（ ） 试验目的及要求
（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。
成 绩 评 定 表
类 别 评 分 标 准 分值 得分 合 计
上机表现
积极出勤、遵守纪律 主动完成设计任务 30分
程序与报告
程序代码规范、功能正确 报告详实完整、体现收获
70分
goto label2;
}
else if(r!=0)
{
printf("重排前的序列为\n");
for(i=1;i<=k;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
printf("排列后的车厢号为：\n");
reset(q,w1,w2,k);
}
else
{
printf("我也不知道错哪了？'");
}
}
四、测试用例（尽量覆盖所有分支）
1.输入正确的序列后得到结果如图：
2.倒输这几个数如图：
3.顺序输这个序列
4.如果输入的车厢数有误的时候（为负数或零）
5.如果输入的序列不是连续自然数。
数据结构车厢调度第一篇：数据结构车厢调度#include #include#define STACK_INIT_SIZE 20 #define STACK_SIZEtypedef struct { int *base;int *top;int stacksize;} SqStack;bool InitStack(SqStack &S){ // 初始化栈S.base =(int *)malloc(STACK_INIT_SIZE*sizeof(SqStack));if(!S.base) exit(0);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return true;} // InitStackbool GetT op(SqStack S, int &e){ // if(S.top == S.base)return false;e = *(S.topS.base >= S.stacksize){S.base =(int *)realloc(S.base,(S.stacksize + STACK_SIZE)*sizeof(SqStack));if(!S.base)exit(0);S.top = S.base + S.stacksize;S.stacksize += STACK_SIZE;} *S.top++ = e;return true;} // Pushbool Pop(SqStack &S, int &e){ if(S.top == S.base)return false;e = *--S.top;return true;}/////////////////////////////////////////////////////////////////// ////////////////bool Judement(int *Array, int n){ int Count = 0;for(int i = 1;i <= 2*n;i++)if(Array[i] == 1)Count++;if(Count == n && Array[2*n] == 0)一个是出栈return true;elsereturn false;}void operation(SqStack S, int n){ // n代表获得数量，分别标记为1,2,3....n int *Array;int nCount = 0, e;Array =(int *)malloc((2 * n + 1)* sizeof(int));if(!Array)exit(0);// 将其初始化为1234..n的形式for(int i = 1;i <= 2*n;i++)if(i%2 == 1)Array[i] = 1;elseArray[i] = 0;while(1){if(Judement(Array, n)){nCount = 0;for(int i = 1;i <= 2*n;i++){if(Array[i] == 1)Push(S, ++nCount);// 必须保证最后//从1开始// 代表入栈// 代表出栈else{Pop(S, e);printf(“%d ”, e);}}printf(“n”);}Array[2*n] += 1;// 最后一个自增1，等于2时本为为0前一位加1for(int i = 2*n;i >= 1;i--){if(Array[i] == 2){Array[i-1] += 1;Array[i] = 0;}}nCount = 0;for(int i = 1;i <= n;i++){if(Array[i] == 1)nCount++;}if(nCount == n && Array[2*n] == 1)break;// 退出循环的条件为前n个为1同时最后一位也为1 } }void main(){ // 这个是在左边有1,2,3...n节车厢的情况，得出在右边所有的情况SqStack S;InitStack(S);int n;scanf_s(“%d”, &n);if(n <= 1){printf(“输入数字小于1”);return;} operation(S, n);第二篇：数据结构任务调度实验报告实验报告实验名称：表达式求值任务调度实验类型：综合性实验班级：学号：姓名：实验日期：2014.5.28表达式求值 1.问题描述表达式是数据运算的基本形式。
北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。
二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。
具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。
2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。
具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。
3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。
具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。
4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。
具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。
5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。
具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。
北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。
本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。
二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。
具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。
三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。
通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。
2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。
通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。
3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。
通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。
4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。
通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。
四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。
在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。
2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。
在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。
3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。
在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。
目录一、功能描述 (2)1、输入火车厢信息 (2)2、入轨 (2)3、出轨 (2)4、退出 (2)二、总体概要设计 (2)1、系统设计框图: (2)2、系统设计流程图 (3)三、详细设计 (3)1 功能一：输入火车厢信息 (3)1）概要设计： (3)2）算法描述： (3)3)算法分析 (4)2 功能二：入轨 (4)1）概要设计： (4)2）算法描述： (4)3)算法分析： (7)3 功能三：出轨 (8)1）概要设计 (8)2）算法描述： (8)3）算法分析: (11)4 功能四：退出 (11)四、效果及存在问题 (11)1、效果显示: (11)1）输入火车厢信息 (12)2）入轨 (12)3）出轨： (12)4）显示重排完成车厢排列 (13)2、存在问题 (13)五、心得及体会 (14)六、参考文献 (14)七、评分表（见尾页）.............................. 错误！未定义书签。
附录：源代码. (14)一、功能描述1、输入火车厢信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。
2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。
3、出轨给出每节火车厢出轨提示。
4、退出如果不需要操作就退出系统。
二、总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。
1、系统设计框图:2、系统设计流程图三、详细设计1 功能一：输入火车厢信息1）概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排列信息，并在屏幕上显示火车原始排列。
2）算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：int i,M,A[100],N=0;printf("\n\n");printf("************************************************************\n\n"); printf("===============您好,欢迎光临火车转轨系统！===============\n\n");printf("请输入您要进行转轨的火车车厢总长：");scanf("%d",&M);printf("\n请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢号\n\n");for(i=0;i<M;i++){scanf("%d",&A[i]);}printf("未转轨前的火车厢排列如下，请核对：\n");for(i=0;i<M;i++)printf("A[%d]=%d\n",i,A[i]);3)算法分析：此功能模块简单明了没有深度算法，在此不做分析。
数据结构实验报告实验名称：实验二——题目5学生姓名：班级：班内序号：学号：日期：2011年11月7日1．实验要求利用队列结构实现车厢重排问题。
车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。
给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。
转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。
开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。
缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。
2. 程序分析将每个轨道视为一个队列，每一个车厢视为一个结构体的结点，结点存储车厢编号以及下一节车厢的地址。
用尾插法建立队列，并根据队列队尾入队，队头出队的特点实现结点的出队以及入队。
由于车厢在重排过程中将会频繁进行入队以及出队的操作，如果采用顺序存储结构，则在结点出入队时是操作将会十分不方便，还会占用大量多余的空间和时间，故选用链式存储结构，可以直接调动结点，十分简洁。
重排过程比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面。
在把车厢c 移至缓冲轨是，车厢c应该移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择对位车厢编号最大的缓冲轨，否则选择一个空的缓冲轨。
这样，出轨的时候才可以按照从小到大的顺序重新编排。
2.1 存储结构2.2 关键算法分析1. 移动车厢算法（车厢要从a队列移至b队列）·自然语言描述（1）判断a队列是否为空，为空则输出“队列下溢”，提示出错。
（2） 否则，设置工作指针p 指向a 队列的队头元素，（3） 将b 的尾指针指向next 域指向p ；（4） b 队列的尾指针后移，指向p 指向的结点；（5） a 头结点指向p 后一个结点（6） p 的next 域置为空，完成一次车厢的移动（7） a 队列车厢数减1，b 队列车厢数加1·伪代码描述两个队列，车厢要从a 队列移至b 队列；（1）bus* p=a.front->next;（2）if(!p) cout<<"Underflow"<<endl;（3）b.rear->next=p;（4）b.rear=b.rear->next;（5）a.front->next=p->next;（6）p->next=NULL;（7）if(!(a.front->next))a.rear=a.front;（8）a.Number--;b.Number++;图示ab算法时间复杂度O(1)，空间复杂度S(1)。
一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。
二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。
假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。
为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。
所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过国转轨站完成。
在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。
假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。
(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：2222(a) 将369、247依次入缓冲轨(b) 将1移至出轨，234移至出轨(c) 将8入缓冲轨，5移至出轨(d) 将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：四、源程序代码#include<iostream>using namespace std;const MS=100;template <class T>struct QNode{T data;QNode<T> *next;};template <class T>class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template <class T>LiQueue<T>::LiQueue( ){QNode <T> *s;s=new QNode<T>;s->next=NULL;front=rear=s;}template <class T>LiQueue<T>::~LiQueue( ){QNode <T> *p;while(front){p=front;front=front->next;delete p;}}template <class T>void LiQueue<T>::EnQueue(T x){QNode<T> *s;s=new QNode<T>;s->data=x; //申请一个数据域为x的结点ss->next=NULL;rear->next=s; //将结点s插入到队尾rear=s;}template <class T>T LiQueue<T>::DeQueue(){QNode <T> *p; int x;if (rear==front) throw "下溢";p=front->next;x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为1delete p;return x;}template <class T>T LiQueue<T>::GetFront(){if (rear!=front)return front->next->data;}template <class T>T LiQueue<T>::GetRear(){if(rear!=front)return rear->data;}template <class T>bool LiQueue<T>::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout<<"请输入火车(货运列车）的车厢个数为："<<endl;cin>>n;cout<<"请输入转轨站的缓冲轨个数为："<<endl;cin>>k;}void Train::ChongPai(){int a[MS];LiQueue<int>*b;b=new LiQueue<int>[k+2];cout<<"请输入车厢入轨编号次序："<<endl;for(int i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<<endl;th=1;while(b[k].Empty()){int xx=b[k].DeQueue();if(xx==th){cout<<th<<"号车厢直接移至出轨"<<endl;b[k+1].EnQueue(th);th++;int j=0;while(b[j].Empty()){int x=b[j].GetFront();if(x==th){cout<<x<<"号车厢从"<<j+1<<"号缓冲轨出轨"<<endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{int j=0,u=5;while(b[j].Empty()&&j<k){if(xx<b[j].GetRear())j++;else{cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&j<k){cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);}if(j==k-1){cout<<"\n缓冲轨不够，重排车厢失败\n";return;}}}cout<<"车厢依次出轨的编号为：";while(b[k+1].Empty())cout<<b[k+1].DeQueue()<<" ";cout<<endl;}void main(){Train a;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。
实验报告（2）姓名：学号：班级：日期：一、实验目的：掌握特殊线性表栈和队列的有关运算，熟悉栈和队列的存储结构的基本特点。
二、实验原理：完成特殊单链表-----栈和队列的运算。
具体：1、利用栈完成1个字符串的逆置运算；2、在一个循环队列中入队2元素的运算。
三、实验内容及要求：1、编写一个算法程序实现在一个顺序栈中把一个字符串逆置的运算，要求使用入栈和出栈运算来完成。
2、编写一个算法程序实现在一个循环队列中入队2个元素，要求先建立一个循环队列，元素个数为4个，然后在循环队列的末尾加入2个元素。
要求：请同学把步骤、调试好的程序及存在的问题写在下面。
第一题:步骤:首先创建一个空栈 ,然后提示用户输入一个字符串,依次读取字符串的每个字符并入栈 ,再依次取栈顶元素并出栈 ,便可得到原字符串的逆置。
第一题实验程序代码：#include <stdio.h>#define Stack_Size 50//数组大小定义typedef char DataType;typedef struct{DataType elem[Stack_Size];int top;}SeqStack;//栈的结构定义SeqStack *InitStack();//栈的创建函数int StackEmpty(SeqStack *S);//判断栈是否为空int StackFull(SeqStack *S);//判断栈是否为满void Push(SeqStack *S,DataType x);//元素入栈DataType Pop(SeqStack *S);//元素出栈void playdata(SeqStack *S);//打印输出栈中的元素int main(){SeqStack *S;char x;S=InitStack();if(S==NULL)return 0;printf("请输入一个字符串，以回车键结束：\n");//打印提示语x=getchar();while(x!='\n'){Push(S,x);x=getchar();}if(!StackEmpty(S))//判断字符串是否为空{printf("该字符串的逆序是：\n");playdata(S);}elseprintf("该字符串为空！\n");system("pause");return 0;}SeqStack *InitStack()//栈的创建函数{SeqStack *S;S=(SeqStack*)malloc(sizeof(SeqStack));if(S==NULL)return NULL;else{S->top=-1;return S;}}int StackEmpty(SeqStack *S)//判断栈是否为空{return S->top==-1;}int StackFull(SeqStack *S)//判断栈是否为满{return S->top==Stack_Size-1;}void Push(SeqStack *S,DataType x)//元素入栈{S->elem[++S->top]=x;}DataType Pop(SeqStack *S)//元素出栈{return S->elem[S->top--];}void playdata(SeqStack *S)//打印输出栈中的元素{int i=0;for(i=S->top;i>=0;i--){printf("%c",S->elem[i]);}printf("\n");}第二题:步骤：首先创建一个循环队列，接着在循环队列中入队四个元素，接着提示用户输入2个元素，再入队，再将入队后的队列元素从队头到队尾打印出来，程序结束。
实验报告1．实验要求利用队列结构实现车厢重排问题。
车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。
给定任意次序的车厢，的车厢编号。
提示：一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。
比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。
2. 程序分析2.1 存储结构本程序采用单链表结构，具体为链队列结构，使用队列结构的先进先出原则可以较好地处理车厢重排问题。
链队列结构示意图如下：2.2 关键算法分析一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下：void TrainPermute():1. 初始化条件:计数器i=0,与非门aa=12. 判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)2.1将aa置空；2.2用for循环，依次取入入轨中的每一个车厢的编号进入合适的缓冲轨；2.2.1如果缓冲轨中尾指针比进入缓冲轨元素小，则进入该缓冲轨；计数器i+1;有合适缓冲轨，将aa变为真;跳出for循环并进入while循环；2.2.2如果缓冲轨中第一个元素为空，则进入缓冲轨成为第一个元素；计数器i+1;有合适缓冲轨，将aa变为真;跳出for循环并进入while循环；2.3 用aa判断是否有进入合适的缓冲轨2.3.1 aa=0即没有合适的缓冲轨，则输出无法排列；2.3.2 aa=1即有合适的缓冲轨，则2.3.2.1遍历缓冲轨，输出每个缓冲轨按顺序存储的车厢；2.3.2.2 按从小到大的顺序出轨for(引入输出轨计数器newOut=1;newOut<n; newOut+1;)newOut与每个队列的头元素比较若相等，则元素出队；输出显示；具体代码如下：void TrainPermute(int arr[],LinkQueue<int> a[],int n,int k){int i=0;bool aa=1;while((i<n)&&(aa)) //当入轨中有车厢时{for(int m=0;m<k;m++){if(a[m].GetRear()<arr[i]){a[m].EnQueue(arr[i]);i++;}if(a[m].front->next==NULL){a[m].EnQueue(arr[i]);aa=1;i++;break;}}}if(aa==0) //当无法将入轨中队头车厢移至合适缓冲轨中时，程序结束{cout<<"车厢无法重排,算法结束"<<endl;}else //当入轨中已经没有车厢时{for(int m=0;m<k;m++){cout<<"第"<<(m+1)<<"个缓冲轨的列车编号";a[m].Trans();cout<<endl;}cout<<"火车车厢出轨顺序为:"<<endl;for(int newOut=1;newOut<=n;newOut++){for(int j=0;j<k;j++) //扫描缓冲轨，将其队头元素依次由小到大输出{if(a[j].GetFront()==newOut){cout<<a[j].DeQueue()<<" ";}}}}}二、主函数伪代码如下：1. 输入n与k值，若输入值错误，则程序结束；2. 通过循环结构为数组array[]赋值，具体分析见代码；3. 输出入轨中火车车厢号码排列；4. 调用TrainPermute()函数；三、为array[]随机赋值的基本思想为：设置计数器count=0，设置数组ifmark[]来标记array[]赋值情况，依次将1至n等n个数随机赋给array[]，其中，若array[t]未被赋值，即ifmark[t]=0，则将值赋给array[t]，计数器加一；若array[t]已被赋值，即ifmark[t]=1，则重新开始循环。
一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。
二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。
假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。
为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。
所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过国转轨站完成。
在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。
假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。
(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：2222(a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨 (d) 将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：四、源程序代码#include<iostream>using namespace std;const MS=100;template <class T>struct QNode{T data;QNode<T> *next;};template <class T>class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template <class T>LiQueue<T>::LiQueue( ){QNode <T> *s;s=new QNode<T>;s->next=NULL;front=rear=s;}template <class T>LiQueue<T>::~LiQueue( ){QNode <T> *p;while(front){p=front;front=front->next;delete p;}}template <class T>void LiQueue<T>::EnQueue(T x){QNode<T> *s;s=new QNode<T>;s->data=x; //申请一个数据域为x的结点ss->next=NULL;rear->next=s; //将结点s插入到队尾 rear=s;}template <class T>T LiQueue<T>::DeQueue(){QNode <T> *p; int x;if (rear==front) throw "下溢";p=front->next;x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p;return x;}template <class T>T LiQueue<T>::GetFront(){if (rear!=front)return front->next->data;}template <class T>T LiQueue<T>::GetRear(){if(rear!=front)return rear->data;}template <class T>bool LiQueue<T>::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout<<"请输入火车(货运列车）的车厢个数为："<<endl;cin>>n;cout<<"请输入转轨站的缓冲轨个数为："<<endl;cin>>k;}void Train::ChongPai(){int a[MS];LiQueue<int>*b;b=new LiQueue<int>[k+2];cout<<"请输入车厢入轨编号次序："<<endl;for(int i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<<endl;th=1;while(b[k].Empty()){int xx=b[k].DeQueue();if(xx==th){cout<<th<<"号车厢直接移至出轨"<<endl;b[k+1].EnQueue(th);th++;int j=0;while(b[j].Empty()){int x=b[j].GetFront();if(x==th){cout<<x<<"号车厢从"<<j+1<<"号缓冲轨出轨"<<endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{int j=0,u=5;while(b[j].Empty()&&j<k){if(xx<b[j].GetRear())j++;else{cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&j<k){cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);}if(j==k-1){cout<<"\n缓冲轨不够，重排车厢失败\n";return;}}}cout<<"车厢依次出轨的编号为：";while(b[k+1].Empty())cout<<b[k+1].DeQueue()<<" ";cout<<endl;}void main(){Train a;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。
⽕车车厢重排问题问题描写叙述：⼀列货运⽕车从出发站出发时⽕车上⼀共同拥有n节车厢，编号各⾃是1到n。
运货的各节车厢是在⼊轨上时是随机的顺序，⽕车头在出轨处，如今要将各节车厢按编号从⼤到⼩挂到车头上。
当中在⼊轨与出轨之间有k条缓冲铁轨，将通过缓冲铁轨完毕本次的⽕车车厢的重排。
详细规则：⼀、车厢从⼊轨的前部（即右端）仅仅能够移动到⼀个缓冲铁轨的顶端或出轨的右端。
⼆、缓冲铁轨的顶端的车厢仅仅能够移动到出轨的最左端三、车厢不能从⼀个缓冲铁轨移动到还有⼀个缓冲铁轨或者再移动到⼊轨四、车厢移动到出轨的最左端（即⽕车头端）后不能再移动解决步骤：⼀、从⼊轨端開始移除最右边的车厢假设该车厢正好能够挂在出轨端则直接移到⼊轨端。
然后再在缓冲铁轨中查找是否有接到出轨上的车厢如有则移出如⽆则開始步骤四。
否则先在每条缓冲铁轨中查找。
⼆、假设能找到⼀条缓冲铁轨顶端的车厢编号正好⽐它⼤并且和它最接近则移动到该条缓冲铁轨上三、假设每⼀条有车厢的缓冲铁轨的顶端车厢编号都⽐它⼩，则再查找有没有空的缓冲铁轨假设有则移动到缓冲铁轨上，否则返回false。
四、继续開始从⼊轨端移除最右端的车厢⽽且開始反复步骤⼀。
应⽤的数据结构：因为对于每个缓冲铁轨来说都是LIFO后进先出的特点所以能够考虑採⽤栈的数据结构。
详细实现代码及结果例如以下：#include<iostream>#include<vector>#include<stack>#include<deque>#include<iterator>#include<algorithm>using namespace std;//辅函数：更新缓冲铁轨上的min_buf、min_travoid updata(vector<stack<int>> & tracks_buf,int & min_buf,int & min_tra){for (int i = 0;i<tracks_buf.size();i++){if(!tracks_buf[i].empty() && min_buf>tracks_buf[i].top()){min_buf = tracks_buf[i].top();min_tra = i;}}}//辅函数：将车厢移到缓冲铁轨上bool trans(int n,int d,vector<stack<int>> & tracks_buf,int & min_buf,int & min_tra){//先查找最优缓冲铁轨int min_gap = n+1;//d与个缓冲铁轨顶端上⼤于的车厢与d之间的最⼩间隔int prefer_track = -1;//最优铁轨for (int i = 0;i<tracks_buf.size();i++){if (!tracks_buf[i].empty() && tracks_buf[i].top()>d && (tracks_buf[i].top()-d)<min_gap){min_gap = tracks_buf[i].top()-d;prefer_track = i;}}if(-1!=prefer_track)//找到最优缓冲铁轨{tracks_buf[prefer_track].push(d);updata(tracks_buf,min_buf,min_tra);return true;}else{//再查找是否存在空铁轨for (int i = 0;i<tracks_buf.size();i++){if(tracks_buf[i].empty()){tracks_buf[i].push(d);updata(tracks_buf,min_buf,min_tra);return true;}}//否则返回false;return false;}}/* ⽕车车厢重排问题* datas：⽕车车厢在⼊轨上时的序列* n : ⽕车车厢的总节数* k ：缓冲铁轨的条数*///主要函数bool fun(vector<int> &datas,deque<int> & results,int n,int k){int min_buf = n+1;//缓冲铁轨上最⼩的车厢号int min_tra = 0;//最⼩的车厢所在的缓冲铁轨编号vector<stack<int>> tracks_buf(k);//缓冲铁轨数组int need = 1;//出轨处须要挂上的车厢号while (!datas.empty()){int d = datas.back();datas.pop_back();if (d==need)//符合要求直接移到出轨{results.push_front(need);need++;//再到缓冲铁轨中查找是否有下⼀个符合的车厢while(min_buf == need)//找到{results.push_front(need);need++;//移除缓冲铁轨tracks_buf[min_tra].pop();//更新min_buf、min_tramin_buf = n+2;min_tra = 0;updata(tracks_buf,min_buf,min_tra);}}else//不符合要求移到缓冲铁轨上{if(!trans(n,d,tracks_buf,min_buf,min_tra)){return false;}}}return true;}int main(){int array[] = {5,8,1,7,4,2,9,6,3};deque<int> results;vector<int> vec(array,array+sizeof(array)/sizeof(array[0]));int n = vec.size();int k = 3;//3条缓冲铁轨if (fun(vec,results,n,k)){cout<<k<<"条缓冲铁轨能够将依照";copy(vec.begin(),vec.end(),ostream_iterator<int>(cout));cout<<"此序列的"<<n<<"节车厢⼜⼀次排好挂到⽕车头上。
实验一线性表1 实验目的通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力2 实验内容2.1题目1根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。
2.2题目2利用线性表实现一个通讯录管理，通信录的数据格式如下：struct DataType{int ID; //编号char name[10]; //姓名char ch; //性别char phone[13]; //电话char addr[31]; //地址};要求：实现通讯录的建立、增加、删除、修改、查询等功能能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。
能够保存每次更新的数据（选作）能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）编写测试main()函数测试线性表的正确性2.3题目3利用线性表实现一个一元多项式Polynomialf(x) = a+ a1x + a2x2 + a3x3+ … + a n x n提示：Polynomial的结点结构如下：struct term{float coef; //系数int expn; //指数};可以使用链表实现，也可以使用顺序表实现。
要求：能够实现一元多项式的输入和输出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数（选作）能够进行一元多项式相乘（选作）编写测试main()函数测试线性表的正确性2.4题目4利用循环链表实现约瑟夫问题的求解。
