线性表作业01
第一题
题目
用结构体数组表示学生表，并实现表的建立学生表、添加一个学生数据、插入一个学生数据、、删除一个学生数据、显示全部学生数据和结束程序的功能。
参考信息如下：
学生结构体：
struct student {
int no;//学号
string name; //姓名
char sex; //性别 M 代表男，W代表女
int age;// 年龄
｝
功能控制：
-----------功能菜单-----------
1—建立学生表
2—添加一个学生
3—插入一个学生
4—删除一个学生
5—显示全部学生表数据
6—按学号查找学生数据
0—退出
请选择功能：(1/2/3/4/5/6//0)
各功能要求如下：
(1)能够输入一些学生数据，当输入学号为-9999时结束。
(2)在表最后添加 一个学生数据
(3)插入时指定插入位置，假设输入位置一定正确
(4)删除学生时，请输入要删除的学生学号，然后把对应的学生数据删除
(5)显示全部学生数据
(6)输入学号显示相应学生数据
(7)退出，结束程序运行
源程序清单：
#include<iostream>
using namespace std;
int MAX_NUM = 2; //动态数组的初始最大个数
struct student {
int no;//学号
string name; //姓名
char sex; //性别 M 代表男，W代表女
int age;// 年龄
};
void printMenu() {
cout << "======功能菜单======\n";
cout << " 1---建立学生表\n";
cout << " 2---添加一个学生\n";
cout << " 3---插入一个学生\n";
cout << " 4---删除一个学生\n";
cout << " 5---显示全部学生表数据\n";
cout << " 6---按学号查找学生数据\n";
cout << " 0---退出\n";
cout << "请选择功能：(1/2/3/4/5/6/0)\n";
}
//用于判断输入的性别是否符合要求
bool sexIsRight(char c) {
return c == 'M' || c == 'W' || c == 'm' || c == 'w';
}
//根据学号找到某学生的位置，返回位置数。
int findStudentPos(student s[], const int sNUM, int no) {
for (int i = 0; i < sNUM; i++) {
if (s[i].no == no) {
return i;
}
}
return -1; //找不到就返回-1
}
//5. 打印所有学生信息
void printStudentArray(const student s[],const int n) {
for (int i = 0; i < n; i++) {
cout << "学号：" << s[i].no << endl;
cout << "姓名：" << s[i].name << endl;
cout << "性别：" << s[i].sex << endl;
cout << "年龄：" << s[i].age << endl;
cout << "----------------------------------------\n";
}
}
//输入学生信息，假设输入的学号不会重复
bool enterStudentInfo(student &t) {
cout << "请输入学号： " << endl;
cin >> t.no;
if (t.no == -9999) {
return false;
}
cout << "请输入姓名： " << endl;
cin >> t.name;
cout << "请输入性别（M 代表男，W代表女）： " << endl;
cin >> t.sex;
while (!sexIsRight(t.sex)) { //不对就一直输入
cout << "请重新输入性别（M 代表男，W代表女）！： " << endl;
cin >> t.sex;
}
cout << "请输入年龄： " << endl;
cin >> t.age;
cout << "\n";
return true;
}
//扩展动态数组的大小
student* extendArray(student s[], const int n) {
MAX_NUM = MAX_NUM * 1.5 + 2; //更新全局变量
student* sArr = new student[MAX_NUM];
for (int i = 0; i < n; i++) {
sArr[i].no = s[i].no;
sArr[i].name = s[i].name;
sArr[i].sex = s[i].sex;
sArr[i].age = s[i].age;
}
delete[] s;
return sArr;
}
//1. 创建学生列表
student* createStudentArray(student s[], int& sNum) {
enterStudentInfo(s[sNum]); //建立一个学生
sNum++; //学生数量加一
while (enterStudentInfo(s[sNum])) {
sNum++;
if (sNum >= MAX_NUM) {
s = extendArray(s, sNum);
}
}
return s;
}
//2. 添加一个学生
student* appendStudent(student s[], int& sNUM) {
if (sNUM >= MAX_NUM) {
extendArray(s, sNUM);
}
if (enterStudentInfo(s[sNUM])) { //输入学生信息
sNUM++; //学生人数+1
}
return s;
}
//3. 在某位置插入一个学生
student* insertStudent(student s[], int& sNUM) {
int pos;
cout << "你想插在哪？\n";
cin >> pos;
//if (pos >= sNUM) { //位置大于等于人数时，直接相当于append
// s = appendStudent(s, sNUM);
// return s;
//}
//else if (pos < 0) { //位置小于0
// cout << "该位置无效！\n";
// return s;
//}
student tem_s; //临时储存学生信息，防止输入为-9999
if (enterStudentInfo(tem_s)) { //确实要插入
sNUM++;
if (sNUM >= MAX_NUM) { //防止人数已经达到上限
extendArray(s, sNUM);
}
for (int i = sNUM - 1; i > pos; i--) { //要么重载=，要么就这样赋值，不能直接s[i] = s[i - 1]
s[i].no = s[i - 1].no;
s[i].name = s[i - 1].name;
s[i].age = s[i - 1].age;
s[i].sex = s[i - 1].sex;
}
s[pos].no = tem_s.no;
s[pos].name = tem_s.name;
s[pos].age = tem_s.age;
s[pos].sex = tem_s.sex;
}
return s;
}
//4. 删除学生
student* deleteStudent(student s[], int& sNUM) {
int no, pos;
cout << "请输入要删除的学生的学号：";
cin >> no;
pos = findStudentPos(s, sNUM, no);
if (pos == -1) //pos为-1的话，表明上面函数没有找到相应的学号
cout << "查无此人\n";
else {
for (int i = pos; i < sNUM; i++) {
s[i].no = s[i + 1].no;
s[i].name = s[i + 1].name;
s[i].age = s[i + 1].age;
s[i].sex = s[i + 1].sex;
}
sNUM--; //人数-1
cout << "删除成功！\n";
}
return s;
}
//6. 查找学生，显示他的信息
void findStudent(student s[], int& sNUM) {
int no, pos;
cout << "请输入要查找的学生的学号：";
cin >> no;
pos = findStudentPos(s, sNUM, no);
if (pos == -1) { ////pos为-1的话，表明上面函数没有找到相应的学号
cout << "查无此人\n";
}
else {
cout << "学号：" << s[pos].no << endl;
cout << "姓名：" << s[pos].name << endl;
cout << "性别：" << s[pos].sex << endl;
cout << "年龄：" << s[pos].age << endl;
cout << "----------------------------------------\n";
}
}
int main() {
student* studentArr = new student[MAX_NUM]; //使用动态分配内存
int n; //用于选择操作
int studentNumber = 0;
while (true) {
printMenu();
cin >> n;
switch (n) {
case 1:
studentArr = createStudentArray(studentArr, studentNumber); //不给自己赋值就会导致溢出！
system("pause");
system("cls");
break; //break不能掉
case 2:
studentArr = appendStudent(studentArr, studentNumber);
system("pause");
system("cls");
break;
case 3:
studentArr = insertStudent(studentArr, studentNumber);
system("pause");
system("cls");
break;
case 4:
studentArr = deleteStudent(studentArr, studentNumber);
system("pause");
system("cls");
break;
case 5:
printStudentArray(studentArr, studentNumber);
system("pause");
system("cls");
break;
case 6:
findStudent(studentArr, studentNumber);
system("pause");
system("cls");
break;
case 0:
cout << "Bye~\n";
delete[] studentArr;
return 0;
default:
break;
}
}
if(studentArr != NULL) //防止未删除空间
delete[] studentArr;
return 0;
}
程序运行结果截屏
（此处省略）
第二题
题干
用数组表示多项式，并实现二个整数多项式的加法、减法要求每个多项式存放在各个表中，如C(x)存放运算结果。
A(x)放在a_poly[MAXSIZE]中, B(x)放在不b_poly[MAXSIZE]中C(x)放在c_poly[MAXSIZE]中
注意： 编写输入、输出和相加、相减的程序 （在程序中尽量不用全局变量、输入输出格式自定，尽量做到简单、方便、有效，能说明问题）在主程序中要提示进行何种运算，然后进行相应运算，输出运算结果。
源程序清单：
#include<iostream>
#include<ctime>
#include<Windows.h>
constexpr auto MAXSIZE = 10;;
using namespace std;
//说明：数组的序号为多项式的次数，数组每一项储存的数为该项的系数。
//即：a[0] 表示 系数为a[0]、次数为0 的项
//创建随机多项式
int* createRandPoly() {
int* a = new int[MAXSIZE];
srand((unsigned)time(NULL));
for (int i = 0; i < MAXSIZE; i++) { //i为次数
a[i] = rand() % 20 - 10; //系数范围：-10~9
}
return a;
}
//手动输入系数
int* createPoly(int ap[]) {
if(ap != NULL) delete[] ap;
int coef, exp;
int* a = new int[MAXSIZE];
for (int i = 0; i < MAXSIZE; i++) { //首先初始化，全部设置为0，防止有没输入的项导致
a[i] = 0;
}
cout << "请输入系数（为-9999时停止，是覆盖式输入）：";
cin >> coef;
while (coef != -9999) {
cout << "请输入次数：";
cin >> exp;
while (exp >= MAXSIZE) {
cout << "允许的次数范围为：0~" << MAXSIZE - 1 << "，请重新输入！\n";
cout << "请输入次数：";
cin >> exp;
}
a[exp] = coef;
cout << "请输入系数（为-9999时停止）：";
cin >> coef;
}
return a;
}
//相加
int* addPoly(int a[], int b[]) {
int* c = new int[MAXSIZE];
for (int i = 0; i < MAXSIZE; i++) {
c[i] = a[i] + b[i];
}
return c;
}
//相减
int* subPoly(int a[], int b[]) {
int* c = new int[MAXSIZE];
for (int i = 0; i < MAXSIZE; i++) {
c[i] = a[i] - b[i];
}
return c;
}
//输出多项式
void outputPoly(int a[]) {
bool isFirst = true;
for (int i = MAXSIZE - 1; i > 0; i--) {
if (a[i] == 0) continue;
else if (a[i] > 0) {
if (isFirst) { //如果是多项式的第一项
cout << a[i] << "x^" << i;
isFirst = false;
}
else {
cout << " + " << a[i] << "x^" << i;
}
}
else {
if (isFirst) { //如果是多项式的第一项
cout << "-"<< -a[i] << "x^" << i; //由于负号和数字在一起不便于观察，便和正项统一格式
isFirst = false;
}
else {
cout << " - " << -a[i] << "x^" << i;
}
}
}
if (a[0] > 0) { //常数部分
cout << " + " << a[0];
}
else if (a[0] < 0) {
cout << " - " << -a[0];
}
cout << "\n\n";
}
int main() {
int* a_poly = NULL, * b_poly = NULL;
int* c_poly = NULL;
int a, b;
cout << "对于多项式a，你选择：\n";
cout << "1. 手动创建\n";
cout << "2. 随机创建(default)\n";
cin >> a;
if (a == 1) {
cout << "请输入多项式a（最高次数为：" << MAXSIZE - 1 << "次）：\n";
a_poly = createPoly(a_poly);
}
else { //默认随机
a_poly = createRandPoly(); //随机创建多项式
}
cout << "\n多项式a：\n";
outputPoly(a_poly);
Sleep(1000); //停顿一秒，防止随机数一样
cout << "对于多项式b，你选择：\n";
cout << "1. 手动创建\n";
cout << "2. 随机创建(default)\n";
cin >> b;
if (b == 1) {
cout << "请输入多项式b（最高次数为：" << MAXSIZE - 1 << "次）：\n";
b_poly = createPoly(b_poly);
}
else {
b_poly = createRandPoly(); //随机创建多项式
}
cout << "\n多项式b：\n";
outputPoly(b_poly);
cout << "\n相加的和为：\n";
c_poly = addPoly(a_poly, b_poly); //c_poly为相加的结果
outputPoly(c_poly);
cout << "\n相减（a - b）的和为：\n";
c_poly = subPoly(a_poly, b_poly); //c_poly为相减的结果
outputPoly(c_poly);
delete a_poly;
delete b_poly;
delete c_poly;
return 0;
}
程序运行结果截屏
（此处省略）
第三题
题目
求4*4矩阵的主对角线数据之和并输出4*4矩阵及求和结果。（用数组完成）
源程序清单：
#include<iostream>
using namespace std;;
void createRandMatrix(int a[][4]) {
srand((unsigned int)time(NULL));
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
a[i][j] = rand() % 20 - 10; //范围：-10~9
}
}
}
void printMatrix(const int a[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << a[i][j] << "\t";
}
cout << "\n";
}
}
int main() {
int a[4][4];
createRandMatrix(a);
cout << "矩阵：\n";
printMatrix(a);
cout << "主对角线和的结果：" << a[0][0] + a[1][1] + a[2][2] + a[3][3] << endl;
return 0;
}
程序运行结果截屏
（此处省略）
第四题
题目
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序。
结点结构：
struct node {
int data;
node *link
};
源程序清单：
#include <iostream>
using namespace std;
constexpr auto N = 20; //数组长度
struct node {
int data;
node* link;
};
node* createSortedLink()
{
srand((unsigned int)time(NULL)); //随机数种子
node* head = NULL, * p, * q;
int n = rand() % 20 - 10; //n为有序链表的起点
if (N == 0) return NULL;
head = new node;
p = head;
p->data = n;
p->link = NULL;
for (int i = 1; i < N; i++) {
q = new node;
q->data = n + i * 1.5; //要有点间隔
q->link = NULL;
p->link = q;
p = q;
}
return head;
}
node* insertLink(node *head) {
int num;
cout << "请输入你想插入的数值（= -9999时退出）：";
cin >> num;
if (num == -9999) return head;
int max; //记录最大值
node* m = head; //作为变量寻找尾结点
while (m->link != NULL) {
m = m->link;
}
max = m->data; //由于我设置的链表顺序为升序，所以找到最后一个结点的值就行
node* p = new node; //p是新结点
p->data = num;
if (num < head->data) { //插在头部
p->link = head;
head = p;
}
else if (num >= max) { //如果大于等于最大值，插在最后面
p->link = NULL;
m->link = p;
}
else { //在中间
m = head; //此时尾结点已经没有用了，以免重新创建其他变量
while (m->link != NULL && m->link->data < p->data) { //找到要插入的位置，这种情况下，至少有2个结点
m = m->link;
}
p->link = m->link;
m->link = p;
}
return head;
}
void out_link(node* head)
{
while (head != NULL)
{
cout << head->data << " --> ";
head = head->link;
}
cout << endl;
}
int main()
{
node* head;
head = createSortedLink();
out_link(head);
head = insertLink(head);
cout << "插入后：\n";
out_link(head);
return 0;
}
程序运行结果截屏
（此处省略）
第五题
题目
删除整型数链表中所有奇数结点
源程序清单：
#include <iostream>
using namespace std;
constexpr auto N = 20; //数组长度
struct node {
int data;
node* link;
};
node* createRandLink()
{
srand((unsigned int)time(NULL));
node* head = NULL, * p, * q;
int n = rand() % 20 - 10; //n为有序链表的起点
if (N == 0) return NULL;
head = new node;
p = head;
p->data = n;
p->link = NULL;
for (int i = 1; i < N; i++) {
q = new node;
q->data = rand()%40 - 20; //随机数
//q->data = (rand() % 10 - 5) * 2; //全是偶数
//q->data = (rand() % 10 - 5) * 2 + 1; //全是奇数
q->link = NULL;
p->link = q;
p = q;
}
return head;
}
bool isOdd(int n) { //判断是否为奇数
return n % 2 == 1 || n % 2 == -1;
}
node* deleteOddNode(node* head) {
if (head == NULL) { //链表为空时
return head;
}
node* q = head;
node* p = head; //作用：指向要删除的结点的前面
while (1) {
if (isOdd(q->data)) { //删除的是头结点
if (q->link == NULL) {//只剩头结点，且头结点为奇
delete q;
return NULL;
}
head = q->link; //由于前面已经保存head结点，所以直接接上去，再删除
delete(q);
q = head; //再接上去
}
else { //删除的是中间结点，此时头结点已经为偶数，或者已经被删完并退出
while (!isOdd(q->data) && q->link != NULL) { //为了找到下一个匹配的结点
p = q;
q = q->link;
}
if (isOdd(q->data)) { //找到奇数
p->link = q->link; //接上去
delete(q); //删除该结点
q = p;
}
else { //是因为到尾了才停下来的
return head;
}
}
}
}
void out_link(node* head)
{
if (head == NULL) cout << "链表为空\n";
while (head != NULL)
{
cout << head->data << " --> ";
head = head->link;
}
cout << endl;
}
int main()
{
node* head;
head = createRandLink();
cout << "原链表：\n";
out_link(head);
head = deleteOddNode(head);
cout << "删除后的链表：\n";
out_link(head);
return 0;
}
程序运行结果截屏
（此处省略）
第六题
题目
编写程序实现链表的逆转。node *reverse(node *head)
源程序清单：
#include <iostream>
using namespace std;
struct node {
int data;
node* link;
};
node* create_link()
{
int n;
node* head = NULL, * p, * q;
p = head;
cin >> n;
while (n != -9999)
{
if (head == NULL) {
head = new node;
head->data = n;
head->link = NULL;
p = head; //p只需要指向head即可
cin >> n; //还是需要一个cin，不然第一个就会创建两次
}
else {
q = new node; //用q创建，然后p再指
q->data = n;
q->link = NULL;
p->link = q;
p = q;
cin >> n;
}
p->link = NULL;
}
return(head);
}
void out_link(node* head)
{
while (head != NULL)
{
cout << head->data << "-->";
head = head->link;
}
cout << endl;
}
node* reverse_link(node* head) {
if (head == NULL || head->link == NULL) return head; //空表或者只有一个结点相当于不需要反转
node* p = head->link;
node* q = p->link;
head->link = NULL;
while (q != NULL) {
p->link = head; //将“中间”结点指向上一个结点
head = p; //以下三句相当于把这三个指针整体向后移动一个
p = q;
q = p->link; //p->link还是q->link都一样，用p->link为了方便理解
}
p->link = head; //最后一个结点还没有连到倒数第二个上面
return p;
}
int main()
{
node* head;
head = create_link();
cout << "原链表：\n";
out_link(head);
cout << "\n";
head = reverse_link(head);
cout << "反转后：\n";
out_link(head);
return 0;
}
程序运行结果截屏
（此处省略）
第七题
题目
用单向带头结点的循环链表表示多项式并实现多项式的加法和减法。要求在一个函数中同时实现加法和减法：头结点中指数部分用-1表示，可以用作结束标志
结点结构：
struct node{
int coef, exp;
node *link;
};
参与运算的二个多项式，A(x) 用头指针 *ah，B(x) 用头指针 *bh，加法的结果用头指针 *ch ，减法的结果用头指针 *dh 。
源程序清单：
#include<iostream>
using namespace std;
struct node {
int coef, exp;
node* link;
};
node* createPoly(node *head, int num)
{
if (head == NULL) {
head = new node;
head->coef = 0;
head->exp = -1;
head->link = head;
}
node* p = head, * q; //p指向最后一个结点，q指向新的结点
int n;
cout << "请输入次数为："<< num << "的系数（输入-9999提前停止）：";
cin >> n;
while (n != -9999) {
q = new node;
q->coef = n;
q->exp = num;
q->link = head; //创建新结点q并对其赋值
p->link = q;
p = q; //将新结点接上
num--; //它的位置至关重要
if (num < 0) break;
cout << "请输入次数为：" << num << "的系数（输入-9999提前停止）：";
cin >> n;
}
return head;
}
void outputPoly(node* head) { //输出多项式
bool isFirst = true;
if(head->exp == -1) head = head->link;
while(head->exp != -1) { //执行完后，head为要输出的最后一个结点
if (head->coef == 0) {
head = head->link;
continue;
}
else if (head->coef > 0 && head->exp != 0) {
if (isFirst) { //如果是多项式的第一项
cout << head->coef << "x^" << head->exp;
isFirst = false;
}
else {
cout << " + " << head->coef << "x^" << head->exp;
}
}
else if(head->coef < 0 && head->exp != 0) {
if (isFirst) { //如果是多项式的第一项
cout << "-"<< -head->coef << "x^" << head->exp; //由于负号和数字在一起不便于观察，便和正项统一格式
isFirst = false;
}
else {
cout << " - " << -head->coef << "x^" << head->exp;
}
}
else if (head->exp == 0) { //应该可以直接else，不过保险起见，还是else if
if (head->coef > 0) {
if (isFirst) {
cout << head->coef;
}
else
cout << " + " << head->coef;
}
else if (head->coef < 0) {
if(isFirst)
cout << -head->coef;
else
cout << " - " << -head->coef;
}
}
head = head->link;
}
cout << "\n\n";
}
void insertPoly(node*& c,int coef, int exp) {
node* a = c;
while (a->link->exp != -1) {
a = a->link;
}
node* p = new node;
p->coef = coef; p->exp = exp; p->link = c;
a->link = p;
}
void addAndSubPoly(node*a, node*b, node*& c, node*& d) { //使用指针引用
if (a->exp = -1) a = a->link; //防止传进来为头结点，然后无限循环
if (b->exp = -1) b = b->link;
while (a->exp != -1 && b->exp != -1) { //a、b
if (a->exp == b->exp) { //次数匹配
insertPoly(c, a->coef + b->coef, a->exp);
insertPoly(d, a->coef - b->coef, a->exp);
a = a->link; b = b->link; //下移
}
else if (a->exp > b->exp) {
insertPoly(c, a->coef, a->exp);
insertPoly(d, a->coef, a->exp);
b = b->link;
}
else { //a->exp < b->exp
insertPoly(c, b->coef, b->exp);
insertPoly(d, b->coef, b->exp);
a = a->link; //下移
}
}
while (a->exp != -1) //b到了底
{
insertPoly(c, a->coef, a->exp);
insertPoly(d, a->coef, a->exp);
a = a->link;
}
while (b->exp != -1) //a到了底
{
insertPoly(c, b->coef, b->exp);
insertPoly(d, b->coef, b->exp);
b = b->link;
}
}
int main() {
node* ah = NULL, *bh = NULL;
ah = createPoly(ah, 3);
cout << "多项式a：\n";
outputPoly(ah);
bh = createPoly(bh, 3);
cout << "\n多项式b：\n";
outputPoly(bh);
node* ch, * dh; //创建并初始化两个结果链表
ch = new node; dh = new node;
ch->link = ch; dh->link = dh;
ch->exp = -1; dh->exp = -1;
ch->coef = dh->coef = 0;
addAndSubPoly(ah, bh, ch, dh);
cout << "\na + b：\n";
outputPoly(ch);
cout << "\na - b：\n";
outputPoly(dh);
return 0;
}
程序运行结果截屏
（此处省略）
