数据结构第七周 ：（稀疏矩阵快速转置 + 简单文本编辑器 + 三元组的矩阵加法 + 九宫格数独游戏 + 数组主元素 + 螺旋数字矩阵 + 蛇形矩阵）

稀疏矩阵快速转置

【问题描述】

稀疏矩阵的存储不宜用二维数组存储每个元素，那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组，由非零元素在该稀疏矩阵中的位置（行号和列号对）以及该元组的值构成。而矩阵转置就是将矩阵行和列上的元素对换。

请你实现一个快速的对稀疏矩阵进行转置的算法。
（注意：我看到部分同学提交的代码是简单转置+排序，请务必修改为快速转置算法哦。）

【输入形式】

输入的第一行是两个整数r和c（r<200, c<200, r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，用空格隔开，表示这个稀疏矩阵的各个元素。

【输出形式】

输出为读入的稀疏矩阵的转置矩阵。输出共有c行，每行有r个整数，每个整数后输出一个空格。请注意行尾输出换行。

【样例输入】

6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0

【样例输出】

0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0

【提示】

第二组测试数据行列较大，注意空间开大一点哦。

#include<iostream>
#define MAXSIZE 12510
using namespace std;

typedef struct //三元组元素定义
{
    int row,col;
    int data;
}Triple;

typedef struct //三元组结构体定义
{
    Triple data[MAXSIZE];
    int m;
    int n;
    int len;
}TSMatrix;

void InitMatrix(TSMatrix * matrix) //填充矩阵
{
    int i = 0;
    int j = 0;
    matrix->len  = 0;
    int num;
    for(i = 1; i <= matrix->m; i ++)
    {
        for(j = 1; j <= matrix->n ; j ++)
        {
            cin>>num;
            if(num == 0) continue;
            else
            {
                matrix->len ++;
                matrix->data[matrix->len].row = i;
                matrix->data[matrix->len].col = j;
                matrix->data[matrix->len].data = num;
            }
        }
    }
}

void TransposeMatrix(TSMatrix * matrix,TSMatrix *trans) //转置矩阵
{
    int cnum[MAXSIZE];
    int cpose[MAXSIZE];
    int i = 0;
    for(i = 1; i <= matrix->len; i ++)
    {
        cnum[matrix->data[i].col] ++;
    }
    for(i = 1; i <= matrix->m; i ++)
    {
        if(i == 1)
        {
            cpose[i] = 1;
        }
        else
        {
            cpose[i] = cpose[i - 1] + cnum[i - 1];
        }
    }
    trans->m = matrix->n;
    trans->n = matrix->m;
    trans->len = matrix->len;
    for(i = 1; i <= matrix->len; i ++) //转置元组
    {
        int col = matrix->data[i].col; //记录第一个元组列坐标
        int q = cpose[col]; //找到该列坐标换成行后是第几个非零元，也就是在转置元组中的位置
        trans->data[q].col = matrix->data[i].row;
        trans->data[q].row = matrix->data[i].col;
        trans->data[q].data = matrix->data[i].data;
        cpose[col] ++;
    }
}

void DisplayMatrix(TSMatrix * matrix) //输出矩阵
{
    int  i = 0;
    int j = 0;
    int k = 1;
    for(i = 1; i <= matrix->m; i ++)
    {
        for(j = 1; j <= matrix->n; j ++)
        {
            if(k <= matrix->len && i == matrix->data[k].row && j == matrix->data[k].col)
            {
                cout<<matrix->data[k].data<<" ";
                k ++;
            }
            else
            {
                cout<<0<<" ";
            }
        }
        cout<<endl;
    }
}
int main()
{
    int m,n;
    cin>>m>>n;
    TSMatrix matrix;
    TSMatrix trans;
    matrix.m = m;
    matrix.n = n;
    InitMatrix(&matrix);
    TransposeMatrix(&matrix,&trans);
    cout<<endl<<endl;
    DisplayMatrix(&trans);
    return 0;
}

简单文本编辑器

【问题描述】

参照Windows的记事本等类似的文本编辑器，使用串的技术设计一个功能简单的文本编辑器。

（1）要求从文件系统中打开文本文件（例如文件名为ok.txt，位于当前执行程序的目录下）；

（2） 文本文件中每行最多不超过80个字符，共N行（N>=1）;

（3）信息读取后，要求存储结构使用链表和串，建立以串为结点单元的单链表，每行对应单链表的每个串结点；

（4）实现信息显示功能，将字符串按行显示在屏幕上；

（5）可以进行字符串的查找，并显示找到的字符串的位置（行、列）；

（6）可以进行字符串的替换，注意替换后该行是否发生变化；

（7）可以指定插入位置后，进行字符串的插入，注意插入后该行是否发生变化；

（8）可以删除指定的字符串，注意删除后该行是否发生变化；

（9）可以将编辑后的内容存入文件 ；

（10）使用菜单模式，将各功能与数字序号结合，供用户选择；
【特别注意】可以自行添加设计其他功能，或以其他形式完成上述任务，不拘泥于上述功能，创意无限，精彩无限。

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
using namespace std;
// 待优化的地方，实现原记录的保存，做到可撤销操作


typedef struct node //串节点的定义
{
    char data[N];
    int paragraph;
    struct node * prior;
    struct node * next;
}DataNode;

DataNode * start = NULL;

//函数声明
void Open_file(); //打开并读入文件
void Menu(); //菜单
void Find(); //查找函数
void Delete(); //删除函数
void Insert(); //插入函数
void Sibsitute(); //替换函数
void Order(); //遍历
void Show(); //显示文章(暂时先写显示全部的，升级版写可以选择输出某一行）
void Save(); //保存文章

void Open_file() //打开并读入文件 （不足之处，不能识别回车，不能判断文章结束的位置）
{
    cout<<"请输入要打开文件名字（例如c:\\a.txt）：";
    char name[50];
    scanf("%s", &name);
    FILE * file; //文件指针
	while ((file = fopen(name, "r")) == NULL) //传参不能传string类，可以传char数组
	{
			cout<<"\n打开文件失败，请重新输入要打开文件名字（例如c:\\a.txt）：";
			cin>>name;
    }
    start = (DataNode *)malloc(sizeof(DataNode)); //建一个空的头结点
    DataNode * cur = start; //现指的节点
    DataNode * pre = NULL; //前驱节点
    char ch;
    int count = 0;

	while((ch = fgetc(file)) != EOF) //表示文件还未读完
    {
        count ++;
        DataNode * temp = (DataNode *)malloc(sizeof(DataNode));
        int i = 0;
        temp->data[i] = ch;
        i ++;
        while((ch = fgetc(file)) != '\n')
        {
            temp->data[i] = ch;
            i ++;
        }
        temp->data[i] = '\n'; //把文件内的换行读入
        temp->paragraph = count;
        cur->next = temp;
        cur->prior = pre;
        pre = cur;
        cur = temp;
    }
    pre->next = NULL; //最后一个回车结束占用一个节点
    cout<<"文件读入完毕"<<endl;
    cout<<"Press Enter key to back to main menu...";
    getchar();
    fclose(file);
}

void Menu() //菜单
{
    while(1)
    {
        system("cls");
        printf("\t\t\t\t ____________________________________________________\n");
        printf("\t\t\t\t|                 文章处理菜单                       |\n");
        printf("\t\t\t\t|                                                    |\n");
        printf("\t\t\t\t|---->  1、查找文章中的字符或者字符串                |\n");
        printf("\t\t\t\t|---->  2、删除文章中的字符或者字符串                |\n");
        printf("\t\t\t\t|---->  3、向文章中插入字符或者字符串                |\n");
        printf("\t\t\t\t|---->  4、替换文章中的字符或字符串                  |\n");
        printf("\t\t\t\t|---->  5、显示文章                                  |\n");
        printf("\t\t\t\t|---->  6、保存文章                                  |\n");
        printf("\t\t\t\t|---->  7、退出文本编辑器                            |\n");
        printf("\t\t\t\t|____________________________________________________|\n");
        printf("\t\t\t\t请输入你的选择:");
        int choice;
        cin>>choice;
        switch(choice)
        {
            case 1:Find();break;
            case 2:Delete();break;
            case 3:Insert();break;
            case 4:Sibsitute();break;
            case 5:Show();break;
            case 6:Save();break;
            case 7: exit(0);
        }
    }
}

void Find() //查找函数(暂时只能查找一段内的字符串，跨行尚不能实现）
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章内容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char des[N];
    cout<<"\n\t         请输入你所想要查找的字符串：";
    gets(des);
    int deslen = strlen(des);
    int ans = 0;
    char subs[N];
    bool found = false;
    cout<<"\n\t         该字符串出现在："<<endl;
    while(cur != NULL)
    {
        int i = 0;
		while (i <= (strlen(cur->data) - deslen))
		{
            int k = 0;
            int j = 0;
			for(j = i; j < i + deslen; j ++)
			{
				subs[k] = cur->data[j];
				k ++;
			}
			if (!strcmp(subs, des))
			{
				ans ++;
                printf("\n\t          \t%d:第%d段\t第%d行  第%d列\n", ans, cur->paragraph, 1 + i / 80, (i+1)%80); //取整和取余是模拟80一行输出模式
				found = true;
			}
			i ++;
		}
		cur = cur->next;
    }
	if(found) printf("\n\t         该字符串总共在文章中出现过%d次\n\n",ans);
	else printf("\n\t         \t\t文章中找不到该字符串\n\n");
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Delete() //删除函数 （暂时只能实现删除文章中字符串出现的所有位置，若要所删字符串跨行需分多次删除，尚待优化（根据需求可开发更多功能实现
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         原文章内容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char des[N];
    cout<<"\n\t         请输入你所想要删除的字符串：";
    gets(des);
    int deslen = strlen(des);
    char subs[N];
    bool found = false;
    while(cur != NULL)
    {
        int i = 0;
		while (i <= (strlen(cur->data) - deslen))
		{
            int k = 0;
            int j = 0;
			for(j = i; j < i + deslen; j ++)
			{
				subs[k] = cur->data[j];
				k ++;
			}
			if (!strcmp(subs, des)) //第i的位置为字符串起始位置
			{
			    int reslen = strlen(cur->data) - deslen - i;
			    found = true;
				if(reslen >= deslen) //要删除的字符串长度小于等于余下部分的字符串长度
                {
                    int pos = i;
                    for( ; pos < reslen + i; pos ++)
                    {
                        cur->data[pos] = cur->data[pos + deslen];
                    }
                }
                else
                {
                    int pos = i;
                    for( ; pos < reslen + i; pos ++)
                    {
                        cur->data[pos] = cur->data[pos + deslen];
                    }
                    int c = deslen - reslen;
                    while(c --)
                    {
                        cur->data[pos] = ' ';
                        pos ++;
                    }
                }
			}
			i ++;
		}
		cur = cur->next;
    }
	if(found) printf("\n\t         该字符串已在文章中彻底删除\n");
	else printf("\n\t         \t\t文章中找不到该字符串\n\n");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         删除后文章内容如下 :                                                           "<<endl;
     Order();
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Insert() //插入函数 （也只能一行内插入
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章内容如下 :                                                           "<<endl;
    Order();
    int para;
    int row;
    int col;
    cout<<"\n\t      请输入你插入的位置："<<endl;
    cout<<"\n\t      段落：";
    cin>>para;
    cout<<"\n\t      行：";
    cin>>row;
    cout<<"\n\t      列：";
    cin>>col;
    string neew;
    cout<<"\n\t      请输入你要插入的字符串:";
    cin>>neew;
    DataNode * cur = start->next;
    while(cur != NULL)
    {
        if(cur->paragraph == para)
            break;
        else
            cur = cur->next;
    }
    int pos = (row - 1) * 79 + col;
    int neewlen = neew.length();
    int reslen = strlen(cur->data) - pos ;
    int i = 0;
    int count = 0;
    for(i = strlen(cur->data) + neewlen - 1; ; i --)
    {
        cur->data[i] = cur->data[i - neewlen];
        count ++;
        if(count == reslen) break;
    }
    count = 0;
    for(i = pos; ; i ++)
    {
        cur->data[i] = neew[count];
        count ++;
        if(count == neewlen) break;
    }
    getchar();
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         插入后文章内容如下 :                                                           "<<endl;
     Order();
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Sibsitute() //替换函数 （行内替换
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         替换前文章内容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char old[N];
    cout<<"\n\t         请输入被替换的字符串：";
    gets(old); //两个gets（）连用不可，不解
    int oldlen = strlen(old);
    string neew;
    cout<<"\n\t         请输入替换后的字符串：";
    cin>>neew;
    int neewlen = neew.length();
    char subs[N];
    bool found = false;
    while(cur != NULL)
    {
        int i = 0;
		while (i <= (strlen(cur->data) - oldlen))
		{
            int k = 0;
            int j = 0;
			for(j = i; j < i + oldlen; j ++)
			{
				subs[k] = cur->data[j];
				k ++;
			}
			if (!strcmp(subs, old)) //第i的位置为字符串起始位置
			{
			    found = true;
                if(neewlen <= oldlen) // 要替换的字符串长度小于原来字符串的长度
                {
                    int m = 0;
                    int pos = i;
                    for(m = 0; m < neewlen; m ++)
                    {
                        cur->data[pos] = neew[m];
                        pos ++;
                    }
                    int movelen = oldlen - neewlen; //剩余部分移动距离
                    int restlen = strlen(cur->data) - pos;
                    int count = 0;
                    for(; ; pos ++)
                    {
                        cur->data[pos] = cur->data[pos + movelen];
                        count ++;
                        if(count == restlen) break;
                    }
                }
                else
                {
                    int movelen = neewlen - oldlen;
                    int alllen = strlen(cur->data);
                    int pos = alllen - 1 + movelen;
                    int count = 0;
                    for(; ; pos --)
                    {
                        cur->data[pos] = cur->data[pos - movelen];
                        count ++;
                        if(count == alllen) break;
                    }
                    pos = i;
                    count = 0;
                    for(; ;pos ++)
                    {
                        cur->data[pos] = neew[count];
                        count ++;
                        if(count == neewlen) break;
                    }
                }
			}
			i ++;
		}
		cur = cur->next;
    }
	if(found) printf("\n\t         该字符串已在文章中被替换\n");
	else printf("\n\t         \t\t文章中找不到要替换的字符串\n\n");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         替换后文章内容如下 :                                                           "<<endl;
     Order();
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
    getchar();
}

void Order() //遍历文章
{
    int i = 0;
    //int count = 1;
    DataNode * cur = start;
    cur = cur->next;
    while(cur != NULL)
    {
        i = 0;
        while(cur->data[i] != '\n')
        {
            if(i == 0) cout<<"\n\t         第"<<cur->paragraph<<"段 :";
            cout<<cur->data[i];
            if(i % 79 == 0 && i != 0) cout<<"\n\t                "; //控制一行80个字符输出
            i ++;
        }
        cur = cur->next; //注意这句话出现在循环内的位置
    }
    printf("\n\t      _____________________________________________________________________________________________ \n");
}

void Show() //显示文章(暂时先写显示全部的，升级版写可以选择输出某一行）
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章内容如下 :                                                           "<<endl;    int i = 0;
    Order();
    cout<<"\n\t         已显示文章全部内容";
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Save() //保存文章
{
    system("cls");
	FILE *fp;
    DataNode *cur = start->next;
	int i=0;
    char name[20];
	printf("请输入保存地址(例如: c:\\a.txt):");
	scanf("%s",name);
		while ((fp=fopen(name,"w+"))==NULL)
		{
			printf("文件不存在，请重新输入文件名：");
			scanf("%s",name);
		}
	while(cur)
	{
        while(cur->data[i] != '\n')
		{
		    fprintf(fp,"%c",cur->data[i]);
            i++;
		}
		fprintf(fp,"%c",cur->data[i]);
		cur = cur->next;
		i = 0;
	}
        fclose(fp);
		printf("文件保存成功");
    cout<<"Press Enter key to back to main menu...";
    getchar();
    getchar();
}

int main()
{
	cout<<"\n\n\n\n\n\n\n\n\n\t\t\t\tWelcom to use our TXT edition system!\n";
	cout<<"\n\n\t\t\t\t     Press Enter key to continue...";
	getchar();
    system("cls");
    Open_file(); //打开文件
    getchar();
    system("cls");
    Menu(); //显示菜单
    return 0;
}

三元组的矩阵加法

【问题描述】

以三元组表存储的稀疏矩阵A、B非零元个数分别为m和n。试编写程序，完成A+B。

【输入形式】

第一排为分别为A、B元素的个数，以下各排分别输入对应的三元组，头m组为A中的元素，接下来为B的元素，同一个矩阵的元素按照行递增排列，第一行规定为1，同一行的元素按照列递增排列，第一列规定为1

【输出形式】

为相应的三元组，以回车分开，如果结果全部为0，则输出 -1 -1 -1

【样例输入】

2 1

1 2 3

1 3 4

1 3 3

【样例输出】

1 2 3

1 3 7

#include<iostream>
#define MAXSIZE 1000
using namespace std;
typedef struct
{
    int row;
    int col;
    int data;
}Triple;
typedef struct
{
    Triple s[MAXSIZE];
}TSMatrix;
int main()
{
    int is0 = 1;
    int n1,n2;
    cin>>n1>>n2;
    TSMatrix m1,m2,m3;
    int len1 = 0;
    int len2 = 0;
    int  len3 = 0;
    while(n1 --) //输入第一个三元组
    {
        int row,col,data;
        cin>>row>>col>>data;
        m1.s[len1].row = row;
        m1.s[len1].col = col;
        m1.s[len1].data = data;
        //cout<<m1.s[len1].row<<" "<<m1.s[len1].col<<" "<<m1.s[len1].data<<endl;
        len1 ++;
    }
    while(n2 --)//输入第二个三元组
    {
        int row,col,data;
        cin>>row>>col>>data;
        m2.s[len2].row = row;
        m2.s[len2].col = col;
        m2.s[len2].data = data;
        //cout<<m2.s[len2].row<<" "<<m2.s[len2].col<<" "<<m2.s[len2].data<<endl;
        len2 ++;
    }
    int i = 0;//当前处理元素位置
    int j = 0;
    while(i < len1 && j < len2)
    {
        //cout<<m1.s[i].row<<" "<<m1.s[i].col<<" "<<m1.s[i].data<<endl;
        //cout<<m2.s[j].row<<" "<<m2.s[j].col<<" "<<m2.s[j].data<<endl;
        if(m1.s[i].row < m2.s[j].row)//如果行小直接放
        {
            m3.s[len3].row = m1.s[i].row;
            m3.s[len3].col = m1.s[i].col;
            m3.s[len3].data = m1.s[i].data;
            if(m3.s[len3].data != 0) is0 = 0;
            len3 ++;
            i ++;
            continue;
        }
        else if(m1.s[i].row == m2.s[j].row)
        {
            if(m1.s[i].col < m2.s[j].col)
            {
                m3.s[len3].row = m1.s[i].row;
                m3.s[len3].col = m1.s[i].col;
                m3.s[len3].data = m1.s[i].data;
                if(m3.s[len3].data != 0) is0 = 0;
                len3 ++;
                i ++;
                continue;
            }
            else if(m1.s[i].col == m2.s[j].col)
            {
                int r = m1.s[i].data + m2.s[j].data;
                if(r == 0)
                {
                    i ++;
                    j ++;
                    continue;
                }
                else
                {
                    m3.s[len3].row = m1.s[i].row;
                    m3.s[len3].col = m1.s[i].col;
                    m3.s[len3].data = m1.s[i].data + m2.s[j].data;
                    //cout<<m3.s[len3].row<<" "<<m3.s[len3].col<<" "<<m3.s[len3].data<<endl;
                    if(m3.s[len3].data != 0) is0 = 0;
                    len3 ++;
                    i ++;
                    j ++;
                    continue;
                }
            }
            else if(m1.s[i].col > m2.s[j].col)
            {
                m3.s[len3].row = m2.s[j].row;
                m3.s[len3].col = m2.s[j].col;
                m3.s[len3].data = m2.s[j].data;
                if(m3.s[len3].data != 0) is0 = 0;
                len3 ++;
                j ++;
                continue;
            }
        }
        else if(m1.s[i].row > m2.s[j].row)
        {
            m3.s[len3].row = m2.s[j].row;
            m3.s[len3].col = m2.s[j].col;
            m3.s[len3].data = m2.s[j].data;
            if(m3.s[len3].data != 0) is0 = 0;
            len3 ++;
            j ++;
            continue;
        }
    }
    if(i != len1)
    {
        while(i != len1)
        {
            m3.s[len3].row = m1.s[i].row;
            m3.s[len3].col = m1.s[i].col;
            m3.s[len3].data = m1.s[i].data;
            if(m3.s[len3].data != 0) is0 = 0;
            i ++;
            len3 ++;
        }
    }
    if(j != len2)
    {
        while(j != len2)
        {
            m3.s[len3].row = m2.s[j].row;
            m3.s[len3].col = m2.s[j].col;
            m3.s[len3].data = m2.s[j].data;
            if(m3.s[len3].data != 0) is0 = 0;
            len3 ++;
            j ++;
        }
    }
    int k = 0;
    if(is0) cout<<-1<<" "<<-1<<" "<<-1<<endl;
    while(k != len3)
    {
        cout<<m3.s[k].row<<" "<<m3.s[k].col<<" "<<m3.s[k].data<<endl;
        k ++;
    }
    return 0;
}

九宫格数独游戏

【问题描述】
数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9X9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。要求使用合适的数据结构和算法，求解出所有剩余空格的数字。

【输入形式】
输入为9X9的二维数组，每个数字均为0-9之间的数字，其中0表示该位置的数字为未知。

【输出形式】
输出为9X9的二维数组，每个数字均为1-9之间的数字，满足

【样例输入】

0 0 3 5 0 0 0 0 2
0 0 8 6 0 0 0 0 0
0 7 0 0 0 0 1 0 0
0 1 0 0 0 0 6 0 0
0 5 0 0 1 0 0 7 0
0 0 6 9 0 0 0 3 0
0 0 9 0 0 0 0 5 0
0 0 0 0 0 9 7 0 0
6 0 0 0 0 8 9 0 0

【样例输出】

1 6 3 5 4 7 8 9 2
5 9 8 6 2 1 3 4 7
2 7 4 8 9 3 1 6 5
3 1 7 4 8 5 6 2 9
9 5 2 3 1 6 4 7 8
8 4 6 9 7 2 5 3 1
7 8 9 1 6 4 2 5 3
4 3 1 2 5 9 7 8 6
6 2 5 7 3 8 9 1 4

【评分标准】
深搜或者其他算法均可

#include<iostream>
using namespace std;
#define N 10
typedef struct
{
    int row;
    int col;
    int data;
}elem;
void Creat(int sodu[N][N])
{
    int i, j;
    for(i = 1; i < N; i ++)
    {
        for(j = 1; j < N; j ++)
        {
            cin>>sodu[i][j];
        }
    }
}

void Fill(int sodu[N][N])
{
    bool row[N][N];
    bool col[N][N];
    bool square[N][N];
    elem num[80];
    int i, j;
    int pre = 0;

    for(i = 1; i < N; i ++) //三个数组初始化为真
    {
        for(j = 1; j < N; j ++)
        {
            row[i][j] = true;
            col[i][j] = true;
            square[i][j] = true;
        }
    }

    for(i = 1; i < N; i ++) //填row数组
    {
        for(j = 1; j < N; j ++)
        {
            if(sodu[i][j] == 0) continue;
            else
            {
                int num = sodu[i][j];
                row[i][num] = false;
            }
        }
    }

    for(j = 1; j < N; j ++) //填col数组
    {
        for(i = 1; i < N; i ++)
        {
            if(sodu[i][j] == 0) continue;
            else
            {
                int num = sodu[i][j];
                col[j][num] = false;
            }
        }
    }

    for(i = 1; i < N; i ++) //填square数组
    {
        for(j = 1; j < N; j ++)
        {
            if(sodu[i][j] == 0) continue;
            else
            {
                int num = sodu[i][j];
                int m = (i - 1)/3 + 1;
                int n = (j - 1)/3 + 1;
                int r = 0;
                r = (m - 1) * 3 + n; //第几个九宫格
                square[r][num] = false;
            }
        }
    }

    for(i = 1; i < N; i ++) //填数独
    {
        for(j = 1; j < N; j ++)
        {
            if(sodu[i][j] != 0) continue;
            else
            {
                int k = 1;
                cycle1:int r = ((i - 1)/3) * 3 + (j - 1) / 3 + 1;
                //cout<<r;
                while(!row[i][k] || !col[j][k] || !square[r][k])
                {
                    k ++;
                    if(k == 10) break;
                }
                if(k == 10)
                {
                    while(k == 10)
                    {
                        pre --;
                        i = num[pre].row;
                        j = num[pre].col;
                        k = num[pre].data;
                        sodu[i][j] = 0;
                        r = ((i - 1)/3) * 3 + (j - 1) / 3 + 1;
                        //cout<<r<<" ";
                        row[i][k] = true;
                        col[j][k] = true;
                        square[r][k] = true;
                        //cout<<"回退到"<<i<<" "<<j<<" "<<k<<endl;
                        k ++;
                    }
                    goto cycle1;
                }
                else
                {
                    num[pre].row = i;
                    num[pre].col = j;
                    num[pre].data = k;
                    row[i][k] = false;
                    col[j][k] = false;
                    square[r][k] = false;
                    pre ++;
                    sodu[i][j] = k;
                    //cout<<"放入"<<i<<" "<<j<<" "<<sodu[i][j]<<endl;
                }
            }
        }
    }
}

void Display(int sodu[N][N])
{
    int i, j;
    for(i = 1; i < N; i ++)
    {
        for(j = 1; j < N; j++)
        {
            cout<<sodu[i][j]<<" ";
        }
        cout<<endl;
    }
}

int main()
{
    int sodu[N][N];
    Creat(sodu); //数组名即为地址
    Fill(sodu);
    Display(sodu);
    return 0;
}

数组主元素

【问题描述】这是一道2013年考研真题，已知一个整数序列A长度为N，其中若存在a，且a的个数大于N/2，则称a为A的主元素

例如：3 5 5 3 5 7 5 5，其主元素为5

又如：3 5 5 3 5 1 5 7，其中没有主元素。

假设元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出主元素。若存在主元素则输出该元素否则输出

要求时间复杂度为O(N)，请注意穷举法时间复杂度是O(N^2)，排序再遍历查找的时间复杂度是O(N*logN+N)

【输入形式】

一个整数数组，以0作为结束输入

【输出形式】

主元素，若没有则输出-1

【样例输入】

3 5 5 3 5 7 5 5 0

【样例输出】

5

【样例说明】长度为8，共有5个‘5’

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int a[1000];
    int num;
    int i = 0;
    stack <int> s;
    while(1)
    {
        cin>>num;
        a[i++] = num;
        if(num == 0) break;
        else{
            if(s.empty())
            {
                s.push(num);
            }
            else
            {
                if(num == s.top())
                {
                    s.push(num);
                }
                else
                {
                    s.pop();
                    continue;
                }
            }
        }
    }
    if(s.empty())
    {
        cout<<-1;
    }
    else
    {
        int count = 0;
        for(i = 0; a[i] != 0; i ++)
        {
            if(a[i] == s.top())
                count ++;
        }
        if(count > (i /2.0))
            cout<<s.top();
        else
            cout<<-1;
    }
    return 0;
}

螺旋数字矩阵

【问题描述】 编写一个程序，对任意输入的正整数n(n不大于10)，产生并显示n阶螺旋式数字方阵。如n=3 要显示的方阵为

1 2 3

8 9 4

7 6 5

【输入形式】输入一个数n
【输出形式】产生n阶螺旋数字矩阵，数字以空格隔开
【样例输入】3
【样例输出】

1 2 3

8 9 4

7 6 5

【样例说明】注意输出的数字以空格隔开

#include<iostream>
using namespace std;
int main()
{
    int n = 0;
    cin>>n;
    int a[n][n];
    int count = 0;
    int i = 0;
    int j = 0;
    for(i = 0; i < n; i ++)
    {
        for(j = 0; j < n; j ++)
        {
            a[i][j] = 0;
        }
    }
    /*for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j ++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }*/
    i = j = 0;
    while(1)
    {
        for( ; j < n && a[i][j] == 0; j ++) //右
        {
            a[i][j] = ++ count;
            //cout<<a[i][j];
        }
        j --;
        i ++;
        for( ; i < n && a[i][j] == 0; i ++) //下
        {
            a[i][j] = ++ count;
            //cout<<a[i][j];
        }
        i --;
        j --;
        for( ; j >= 0 && a[i][j] == 0; j --) //左
        {
            a[i][j] = ++ count;
        }
        j ++;
        i --;
        for( ; i >= 0 && a[i][j] == 0; i --) //上
        {
            a[i][j] = ++ count;
        }
        i ++;
        j ++;
        if(count == n * n)
            break;
    }
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j ++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

蛇形矩阵

【问题描述】蛇形矩阵是由1开始的自然数依次排列成的，按对角线方向依次递增

例如n=5时：

1 2 6 7 15
3 5 8 14 16
4 9 13 17 22
10 12 18 21 23
11 19 20 24 25

【输入形式】n

【输出形式】蛇形矩阵

【样例输入】5

【样例输出】

1 2 6 7 15

3 5 8 14 16

4 9 13 17 22

10 12 18 21 23

11 19 20 24 25文章来源地址https://www.toymoban.com/news/detail-420734.html

#include<iostream>
using namespace std;
int main()
{
    int n = 0;
    cin>>n;
    if(n == 1)
    {
        cout<<1;
        return 0;
    }
    int a[n][n];
    int count = 0;
    int i = 0;
    int j = 0;
    for(i = 0; i < n; i ++)
    {
        for(j = 0; j < n; j ++)
        {
            a[i][j] = 0;
        }
    }
    i = j = 0;
    a[i][j] = ++ count;
    while(1)
    {
        j ++; //右或下
        if(j < n) a[i][j] = ++ count;
        else
        {
            j --;
            i ++;
            a[i][j] = ++ count;
        }

        i ++;
        j --;
        for( ; i < n && j >= 0; i ++, j --) //左下
        {
            a[i][j] = ++ count;
        }
        j ++; i --;

        i ++; //下或右
        if(i < n) a[i][j] = ++ count;
        else
        {
            i --;
            j ++;
            a[i][j] = ++ count;
        }

        i --;
        j ++;
        for( ; i >= 0 && j < n; i --, j ++)
        {
            a[i][j] = ++ count;
        }
        i ++; j --;
        if(count == n * n)
            break;
    }
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j ++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

到了这里，关于数据结构第七周 ：（稀疏矩阵快速转置 + 简单文本编辑器 + 三元组的矩阵加法 + 九宫格数独游戏 + 数组主元素 + 螺旋数字矩阵 + 蛇形矩阵）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！