數(shù)據(jù)結(jié)構(gòu)第七周：（稀疏矩陣快速轉(zhuǎn)置 + 簡(jiǎn)單文本編輯器 + 三元組的矩陣加法 + 九宮格數(shù)獨(dú)游戲 + 數(shù)組主元素 + 螺旋數(shù)字矩陣 + 蛇形矩陣）

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)第七周：（稀疏矩陣快速轉(zhuǎn)置 + 簡(jiǎn)單文本編輯器 + 三元組的矩陣加法 + 九宮格數(shù)獨(dú)游戲 + 數(shù)組主元素 + 螺旋數(shù)字矩陣 + 蛇形矩陣）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

稀疏矩陣快速轉(zhuǎn)置

【問(wèn)題描述】

稀疏矩陣的存儲(chǔ)不宜用二維數(shù)組存儲(chǔ)每個(gè)元素，那樣的話會(huì)浪費(fèi)很多的存儲(chǔ)空間。所以可以使用一個(gè)一維數(shù)組存儲(chǔ)其中的非零元素。這個(gè)一維數(shù)組的元素類型是一個(gè)三元組，由非零元素在該稀疏矩陣中的位置（行號(hào)和列號(hào)對(duì)）以及該元組的值構(gòu)成。而矩陣轉(zhuǎn)置就是將矩陣行和列上的元素對(duì)換。

請(qǐng)你實(shí)現(xiàn)一個(gè)快速的對(duì)稀疏矩陣進(jìn)行轉(zhuǎn)置的算法。
（注意：我看到部分同學(xué)提交的代碼是簡(jiǎn)單轉(zhuǎn)置+排序，請(qǐng)務(wù)必修改為快速轉(zhuǎn)置算法哦。）

【輸入形式】

輸入的第一行是兩個(gè)整數(shù)r和c（r<200, c<200, r*c <= 12500），分別表示一個(gè)包含很多0的稀疏矩陣的行數(shù)和列數(shù)。接下來(lái)有r行，每行有c個(gè)整數(shù)，用空格隔開，表示這個(gè)稀疏矩陣的各個(gè)元素。

【輸出形式】

輸出為讀入的稀疏矩陣的轉(zhuǎn)置矩陣。輸出共有c行，每行有r個(gè)整數(shù)，每個(gè)整數(shù)后輸出一個(gè)空格。請(qǐng)注意行尾輸出換行。

【樣例輸入】

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

【提示】

第二組測(cè)試數(shù)據(jù)行列較大，注意空間開大一點(diǎn)哦。

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

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

typedef struct //三元組結(jié)構(gòu)體定義
{
    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) //轉(zhuǎn)置矩陣
{
    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 ++) //轉(zhuǎn)置元組
    {
        int col = matrix->data[i].col; //記錄第一個(gè)元組列坐標(biāo)
        int q = cpose[col]; //找到該列坐標(biāo)換成行后是第幾個(gè)非零元，也就是在轉(zhuǎn)置元組中的位置
        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;
}

簡(jiǎn)單文本編輯器

【問(wèn)題描述】

參照Windows的記事本等類似的文本編輯器，使用串的技術(shù)設(shè)計(jì)一個(gè)功能簡(jiǎn)單的文本編輯器。

（1）要求從文件系統(tǒng)中打開文本文件（例如文件名為ok.txt，位于當(dāng)前執(zhí)行程序的目錄下）；

（2）文本文件中每行最多不超過(guò)80個(gè)字符，共N行（N>=1）;

（3）信息讀取后，要求存儲(chǔ)結(jié)構(gòu)使用鏈表和串，建立以串為結(jié)點(diǎn)單元的單鏈表，每行對(duì)應(yīng)單鏈表的每個(gè)串結(jié)點(diǎn)；

（4）實(shí)現(xiàn)信息顯示功能，將字符串按行顯示在屏幕上；

（5）可以進(jìn)行字符串的查找，并顯示找到的字符串的位置（行、列）；

（6）可以進(jìn)行字符串的替換，注意替換后該行是否發(fā)生變化；

（7）可以指定插入位置后，進(jìn)行字符串的插入，注意插入后該行是否發(fā)生變化；

（8）可以刪除指定的字符串，注意刪除后該行是否發(fā)生變化；

（9）可以將編輯后的內(nèi)容存入文件；

（10）使用菜單模式，將各功能與數(shù)字序號(hào)結(jié)合，供用戶選擇；
【特別注意】可以自行添加設(shè)計(jì)其他功能，或以其他形式完成上述任務(wù)，不拘泥于上述功能，創(chuàng)意無(wú)限，精彩無(wú)限。

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
using namespace std;
// 待優(yōu)化的地方，實(shí)現(xiàn)原記錄的保存，做到可撤銷操作


typedef struct node //串節(jié)點(diǎn)的定義
{
    char data[N];
    int paragraph;
    struct node * prior;
    struct node * next;
}DataNode;

DataNode * start = NULL;

//函數(shù)聲明
void Open_file(); //打開并讀入文件
void Menu(); //菜單
void Find(); //查找函數(shù)
void Delete(); //刪除函數(shù)
void Insert(); //插入函數(shù)
void Sibsitute(); //替換函數(shù)
void Order(); //遍歷
void Show(); //顯示文章(暫時(shí)先寫顯示全部的，升級(jí)版寫可以選擇輸出某一行）
void Save(); //保存文章

void Open_file() //打開并讀入文件 （不足之處，不能識(shí)別回車，不能判斷文章結(jié)束的位置）
{
    cout<<"請(qǐng)輸入要打開文件名字（例如c:\\a.txt）：";
    char name[50];
    scanf("%s", &name);
    FILE * file; //文件指針
	while ((file = fopen(name, "r")) == NULL) //傳參不能傳string類，可以傳char數(shù)組
	{
			cout<<"\n打開文件失敗，請(qǐng)重新輸入要打開文件名字（例如c:\\a.txt）：";
			cin>>name;
    }
    start = (DataNode *)malloc(sizeof(DataNode)); //建一個(gè)空的頭結(jié)點(diǎn)
    DataNode * cur = start; //現(xiàn)指的節(jié)點(diǎn)
    DataNode * pre = NULL; //前驅(qū)節(jié)點(diǎn)
    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'; //把文件內(nèi)的換行讀入
        temp->paragraph = count;
        cur->next = temp;
        cur->prior = pre;
        pre = cur;
        cur = temp;
    }
    pre->next = NULL; //最后一個(gè)回車結(jié)束占用一個(gè)節(jié)點(diǎn)
    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請(qǐng)輸入你的選擇:");
        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() //查找函數(shù)(暫時(shí)只能查找一段內(nèi)的字符串，跨行尚不能實(shí)現(xiàn)）
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章內(nèi)容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char des[N];
    cout<<"\n\t         請(qǐng)輸入你所想要查找的字符串：";
    gets(des);
    int deslen = strlen(des);
    int ans = 0;
    char subs[N];
    bool found = false;
    cout<<"\n\t         該字符串出現(xiàn)在："<<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列\(zhòng)n", ans, cur->paragraph, 1 + i / 80, (i+1)%80); //取整和取余是模擬80一行輸出模式
				found = true;
			}
			i ++;
		}
		cur = cur->next;
    }
	if(found) printf("\n\t         該字符串總共在文章中出現(xiàn)過(guò)%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() //刪除函數(shù) （暫時(shí)只能實(shí)現(xiàn)刪除文章中字符串出現(xiàn)的所有位置，若要所刪字符串跨行需分多次刪除，尚待優(yōu)化（根據(jù)需求可開發(fā)更多功能實(shí)現(xiàn)
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         原文章內(nèi)容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char des[N];
    cout<<"\n\t         請(qǐng)輸入你所想要?jiǎng)h除的字符串：";
    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) //要?jiǎng)h除的字符串長(zhǎng)度小于等于余下部分的字符串長(zhǎng)度
                {
                    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         刪除后文章內(nèi)容如下 :                                                           "<<endl;
     Order();
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Insert() //插入函數(shù) （也只能一行內(nèi)插入
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章內(nèi)容如下 :                                                           "<<endl;
    Order();
    int para;
    int row;
    int col;
    cout<<"\n\t      請(qǐng)輸入你插入的位置："<<endl;
    cout<<"\n\t      段落：";
    cin>>para;
    cout<<"\n\t      行：";
    cin>>row;
    cout<<"\n\t      列：";
    cin>>col;
    string neew;
    cout<<"\n\t      請(qǐng)輸入你要插入的字符串:";
    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         插入后文章內(nèi)容如下 :                                                           "<<endl;
     Order();
    cout<<"\n\t         Press Enter key to back to main menu...";
    getchar();
}

void Sibsitute() //替換函數(shù) （行內(nèi)替換
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         替換前文章內(nèi)容如下 :                                                           "<<endl;
    Order();
    DataNode * cur = start->next;
    char old[N];
    cout<<"\n\t         請(qǐng)輸入被替換的字符串：";
    gets(old); //兩個(gè)gets（）連用不可，不解
    int oldlen = strlen(old);
    string neew;
    cout<<"\n\t         請(qǐng)輸入替換后的字符串：";
    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) // 要替換的字符串長(zhǎng)度小于原來(lái)字符串的長(zhǎng)度
                {
                    int m = 0;
                    int pos = i;
                    for(m = 0; m < neewlen; m ++)
                    {
                        cur->data[pos] = neew[m];
                        pos ++;
                    }
                    int movelen = oldlen - neewlen; //剩余部分移動(dòng)距離
                    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         替換后文章內(nèi)容如下 :                                                           "<<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個(gè)字符輸出
            i ++;
        }
        cur = cur->next; //注意這句話出現(xiàn)在循環(huán)內(nèi)的位置
    }
    printf("\n\t      _____________________________________________________________________________________________ \n");
}

void Show() //顯示文章(暫時(shí)先寫顯示全部的，升級(jí)版寫可以選擇輸出某一行）
{
    getchar();
    system("cls");
    printf("\n\t      _____________________________________________________________________________________________\n");
     cout<<"\n\t         文章內(nèi)容如下 :                                                           "<<endl;    int i = 0;
    Order();
    cout<<"\n\t         已顯示文章全部?jī)?nèi)容";
    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("請(qǐng)輸入保存地址(例如: c:\\a.txt):");
	scanf("%s",name);
		while ((fp=fopen(name,"w+"))==NULL)
		{
			printf("文件不存在，請(qǐng)重新輸入文件名：");
			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;
}

三元組的矩陣加法

【問(wèn)題描述】

以三元組表存儲(chǔ)的稀疏矩陣A、B非零元個(gè)數(shù)分別為m和n。試編寫程序，完成A+B。

【輸入形式】

第一排為分別為A、B元素的個(gè)數(shù)，以下各排分別輸入對(duì)應(yīng)的三元組，頭m組為A中的元素，接下來(lái)為B的元素，同一個(gè)矩陣的元素按照行遞增排列，第一行規(guī)定為1，同一行的元素按照列遞增排列，第一列規(guī)定為1

【輸出形式】

為相應(yīng)的三元組，以回車分開，如果結(jié)果全部為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 --) //輸入第一個(gè)三元組
    {
        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 --)//輸入第二個(gè)三元組
    {
        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;//當(dāng)前處理元素位置
    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;
}

九宮格數(shù)獨(dú)游戲

【問(wèn)題描述】
數(shù)獨(dú)是一種運(yùn)用紙、筆進(jìn)行演算的邏輯游戲。玩家需要根據(jù)9X9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個(gè)粗線宮內(nèi)的數(shù)字均含1-9，不重復(fù)。要求使用合適的數(shù)據(jù)結(jié)構(gòu)和算法，求解出所有剩余空格的數(shù)字。

【輸入形式】
輸入為9X9的二維數(shù)組，每個(gè)數(shù)字均為0-9之間的數(shù)字，其中0表示該位置的數(shù)字為未知。

【輸出形式】
輸出為9X9的二維數(shù)組，每個(gè)數(shù)字均為1-9之間的數(shù)字，滿足

【樣例輸入】

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

【評(píng)分標(biāo)準(zhǔn)】
深搜或者其他算法均可

#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 ++) //三個(gè)數(shù)組初始化為真
    {
        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數(shù)組
    {
        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數(shù)組
    {
        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數(shù)組
    {
        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; //第幾個(gè)九宮格
                square[r][num] = false;
            }
        }
    }

    for(i = 1; i < N; i ++) //填數(shù)獨(dú)
    {
        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); //數(shù)組名即為地址
    Fill(sodu);
    Display(sodu);
    return 0;
}

數(shù)組主元素

【問(wèn)題描述】這是一道2013年考研真題，已知一個(gè)整數(shù)序列A長(zhǎng)度為N，其中若存在a，且a的個(gè)數(shù)大于N/2，則稱a為A的主元素

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

又如：3 5 5 3 5 1 5 7，其中沒(méi)有主元素。

假設(shè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出主元素。若存在主元素則輸出該元素否則輸出

要求時(shí)間復(fù)雜度為O(N)，請(qǐng)注意窮舉法時(shí)間復(fù)雜度是O(N^2)，排序再遍歷查找的時(shí)間復(fù)雜度是O(N*logN+N)

【輸入形式】

一個(gè)整數(shù)數(shù)組，以0作為結(jié)束輸入

【輸出形式】

主元素，若沒(méi)有則輸出-1

【樣例輸入】

3 5 5 3 5 7 5 5 0

【樣例輸出】

【樣例說(shuō)明】長(zhǎng)度為8，共有5個(gè)‘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;
}

螺旋數(shù)字矩陣

【問(wèn)題描述】編寫一個(gè)程序，對(duì)任意輸入的正整數(shù)n(n不大于10)，產(chǎn)生并顯示n階螺旋式數(shù)字方陣。如n=3 要顯示的方陣為

1 2 3

8 9 4

7 6 5

【輸入形式】輸入一個(gè)數(shù)n
【輸出形式】產(chǎn)生n階螺旋數(shù)字矩陣，數(shù)字以空格隔開
【樣例輸入】3
【樣例輸出】

1 2 3

8 9 4

7 6 5

【樣例說(shuō)明】注意輸出的數(shù)字以空格隔開

#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;
}

蛇形矩陣

【問(wèn)題描述】蛇形矩陣是由1開始的自然數(shù)依次排列成的，按對(duì)角線方向依次遞增

例如n=5時(shí)：

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文章來(lái)源地址http://www.zghlxwxcb.cn/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;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)第七周：（稀疏矩陣快速轉(zhuǎn)置 + 簡(jiǎn)單文本編輯器 + 三元組的矩陣加法 + 九宮格數(shù)獨(dú)游戲 + 數(shù)組主元素 + 螺旋數(shù)字矩陣 + 蛇形矩陣）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！