# "Data Structure" second assignment

Originally published in Hibiki33's Blog , reproduced please indicate the source.
The code is for reference only, and the result of the duplicate check is at your own risk.

## 1. Gomoku risk judgment

[Problem Description]

It is known that two people respectively hold white chess and black chess to play backgammon on a go board. If the chess pieces of the same color are connected to form 5 chess pieces on the same horizontal row, vertical row or oblique line, the person who holds the colored chess pieces wins. Write a program to read the state of playing chess at a certain moment, and judge whether someone is about to win, that is: chess pieces of the same color are connected to form 4 chess pieces on the same horizontal row, column or diagonal line, and the two ends of the 4 chess pieces At least one end is empty.
The size of the input board is 19×19, the number 0 is used to indicate an empty position (that is, there is no chess piece), the number 1 is used to indicate that a white chess piece is placed in this position, and the number 2 is used to indicate that a black chess piece is placed in this position. Assume that the number of pieces connected by pieces of the same color on the same horizontal row, column or oblique line will not exceed 4, and the number of pieces connected by one person at most is 4.

[Input form]

Enter the number 0, 1 or 2 from the console to indicate the state of the chessboard; enter 19 numbers in each line, each number is separated by a space, and there is no space after the last number in each line; a total of 19 lines are input to indicate the state of the chessboard number.

[Output format]

If someone is about to win, first output the color of the chess pieces of the person who is about to win (1 means a white chess piece, 2 means a black chess piece), then output the English colon:, and finally output the starting position of a line connecting 4 chess pieces (horizontal lines on the board from the top Going down and counting from left to right in columns, the number of rows and columns of the smallest chess piece on the board is used as the starting position of the connection line. If it is on the same row, the position of the chess piece with the smallest number of columns As the starting position, a comma is used as a separator between two numbers).
If no one wins, output the English string: No.
No matter what the output is, there must be a carriage return and line feed at the end.

[Input example 1]

```0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 1 1 2 0 0 0 0 0 0 0
0 0 0 0 0 2 1 1 1 1 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 2 2 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 1 0 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```

[Output sample 1]

1:9,8

[Input example 2]

```0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```

[Output sample 2]

No

[Example description]

In the input example 1, the person holding the white piece (represented by the number 1) is about to win, and the starting position of connecting 4 pieces and one end is empty is in the 9th row and 8th column, so the output is 1:9,8 .
In the input example 2, there are no chess pieces of the same color connected into 4, so no one is about to win, and No is output directly.

This question requires judging the state of the backgammon board, and the submitted program file name is chess.c.

Traverse 8 / 2 = 4 directions for each point, just be careful not to cross the boundary. Here I wrapped a circle of -1 outside the chessboard, which is convenient for judging the 0s on both sides of 4 consecutive pieces.

The test points on the evaluation machine for this question are particularly weak. Even if the code submitted is correct, it is likely to have bug s. It is recommended to test more by yourself.

```#include <stdio.h>
#include <stdlib.h>

int grid[25][25];

int quat_equal(int a, int b, int c, int d)
{
if (a == b && a == c && a == d)
{
return 1;
}
return 0;
}

int main()
{
for (int i = 1; i <= 19; i++)
{
for (int j = 1; j <= 19; j++)
{
scanf("%d", &grid[i][j]);
}
}
for (int i = 0; i <= 20; i++)
{
grid[20][i] = grid[i][20] = -1;
grid[0][i] = grid[i][0] = -1;
}
for (int i = 1; i <= 19; i++)
{
for (int j = 1; j <= 19; j++)
{
if (grid[i][j])
{
if (j <= 16)
{
if (quat_equal(grid[i][j], grid[i][j + 1], grid[i][j + 2], grid[i][j + 3]))
{
if (!grid[i][j - 1] || !grid[i][j + 4]) {
printf("%d:%d,%d", grid[i][j], i, j);
return 0;
}
}
}
if (i <= 16)
{
if (quat_equal(grid[i][j], grid[i + 1][j], grid[i + 2][j], grid[i + 3][j]))
{
if (!grid[i - 1][j] || !grid[i + 4][j]) {
printf("%d:%d,%d", grid[i][j], i, j);
return 0;
}
}
}
if (i <= 16 && j <= 16)
{
if (quat_equal(grid[i][j], grid[i + 1][j + 1], grid[i + 2][j + 2], grid[i + 3][j + 3]))
{
if (!grid[i - 1][j - 1] || !grid[i + 4][j + 4]) {
printf("%d:%d,%d", grid[i][j], i, j);
return 0;
}
}
}
if (j >= 4) {
if (quat_equal(grid[i][j], grid[i + 1][j - 1], grid[i + 2][j - 2], grid[i + 3][j - 3]))
{
if (!grid[i - 1][j + 1] || !grid[i + 4][j - 4]) {
printf("%d:%d,%d", grid[i][j], i, j);
return 0;
}
}
}
}
}
}

printf("No");

return 0;
}
```

## 2. String replacement (new)

[Problem Description]

Write a program to replace a string in a specified file with another string. Requirements: (1) If there are multiple strings to be replaced, all of them must be replaced; (2) The specified string to be replaced is case-insensitive.

[Input form]

The given file name is filein.txt. Input two lines of strings from the console (without spaces and with carriage return and line feed characters at the end of the line), which represent the replaced string and the replacement string respectively.

[Output format]

Output the replaced result to the file fileout.txt.

[Sample input]

Enter a two-line string from the console:

in

out

The content of the file filein.txt is:

#include <stdio.h>

void main()

{

FILE * IN;

if((IN=fopen("in.txt","r"))==NULL)

{

​ printf("Can't open in.txt!");

​ return;

}

fclose(IN);

}

[Sample output]

The content of the file fileout.txt should be:

#outclude <stdio.h>

void maout()

{

FILE * out;

if((out=fopen("out.txt","r"))==NULL)

{

​ prouttf("Can't open out.txt!");

​ return;

}

fclose(out);

}

[Example description]

The input string to be replaced is in, and the replacement string is out, that is, all in strings (including iN, In, and IN strings) in the file filein.txt are replaced with out strings, and the output is saved to the file fileout. txt.

This question requires to get the content of the replaced file, and there are 5 test points in total. Upload the C language file named replace.c.

Read line by line from a file for output. There are many places that can be optimized, such as KMP and so on.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int is_matching(char *str, char *sub_str)
{
int len = strlen(sub_str);
for (int i = 0; i < len; i++)
{
if (tolower(*(str + i)) != tolower(*(sub_str + i)))
{
return 0;
}
}
return 1;
}

int main()
{
FILE *in = fopen("filein.txt", "r");
FILE *out = fopen("fileout.txt", "w");

char in_str[100];
char out_str[100];
gets(in_str);
gets(out_str);

char line[200];
while (fgets(line, 200, in) != NULL)
{
int line_len = strlen(line);
for (int i = 0; i < line_len; i++)
{
if (tolower(line[i]) == tolower(in_str[0]) && is_matching(line + i, in_str))
{
fputs(out_str, out);
i += strlen(in_str) - 1;
}
else
{
fputc(line[i], out);
}
}
}

fclose(in);
fclose(out);

return 0;
}
```

## 3. Encrypted files

[Problem description] There is an encryption method: it uses a string of letters (can contain repeated letters, the number of letters does not exceed 50) as a key. Assuming that the key word string is feather, first remove the repeated letters in the key word to obtain the word string feathr, and then append other letters in the alphabet to the back of featherr in reverse order:

feathrzyxwvusqponmlkjigdcb

The correspondence between encrypted letters is as follows:

abcdefghijklmnopqrstuvwxyz
feathrzyxwvusqponmlkjigdcb

Among them, the first row is the original English letter, and the second row corresponds to the encrypted letter. Other characters are not encrypted. Write a program to encrypt a file with this cipher. Assume that the file name to be encrypted is encrypt.txt and the encrypted file name is output.txt, and assume that the letters in the input file are all lowercase letters, and the input key is also all lowercase letters.

[Input form] Input the key string from the standard input, and read the content to be encrypted from the file encrypt.txt.
[Output format] The encrypted result is output to the file output.txt.
[Sample input]
feather
And the content in the file encrypt.txt, for example, the content in the encrypted file encrypt.txt is:
c language is wonderful.
[Sample output] The contents of the output.txt file after encryption are:
a ufqzjfzh xl gpqthmrju.
[Example description] First remove the repeated letters of the given key words, and then encrypt the contents of the encrypt.txt file according to the above encryption correspondence table to obtain the encrypted file, in which only the English letters are encrypted and swapped, And assume that the English letters in encrypt.txt are all lowercase letters.

[Scoring criteria] This question requires the file to be encrypted, and there are 5 test points in total. Submit program named encrypt.c

Pay attention to line breaks when generating keys.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int main()
{
FILE *encrypt = fopen("encrypt.txt", "r");
FILE *output = fopen("output.txt", "w");

char key[55];
fgets(key, 50, stdin);

char corresponds[30];
int cor_p = 0;
int hash_tab[30];
memset(hash_tab, 0, sizeof(int) * 26);
for (int i = 0; key[i] != '\0' && key[i] != '\n'; i++)
{
if (!hash_tab[key[i] - 'a'])
{
corresponds[cor_p++] = key[i];
hash_tab[key[i] - 'a'] = 1;
}
}
for (int i = 25; i >= 0; i--)
{
if (!hash_tab[i])
{
corresponds[cor_p++] = i + 'a';
}
}

char line[100];
while (fgets(line, 100, encrypt) != NULL)
{
for (int i = 0; line[i] != 0; i++)
{
if (isalpha(line[i]))
{
line[i] = corresponds[line[i] - 'a'];
}
}
fputs(line, output);
}

fclose(encrypt);
fclose(output);

return 0;
}
```

## 4. Organize the address book

[Problem Description]

Read a set of phone numbers (composed of names and mobile numbers), delete repeated items (items with the same name and phone number are duplicates, and only keep the first occurrence), and check for the same phone number Items with different numbers are sorted as follows: the item that appears for the first time is not processed, the first repeated name is followed by the English underline character _ and the number 1, the second repeated name is followed by the English underline character _ and the number 2, and so on. The maximum number of entries with the same name in the directory does not exceed 10. Finally, the sorted telephone directory is sorted according to the names from small to large, and the sorted telephone directory is output.

[Input form]

First read the number of phone numbers from the standard input, and then enter the name and phone number in separate lines. The name is composed of no more than 20 English lowercase letters, and the phone number is composed of 11 numeric characters. The name and phone number are separated by a space. No more than 100 items of names and phone numbers can be entered.

[Output format]

Output the final sorting results line by line in ascending order of names, first output the name and then output the phone number, separated by a space.

[Sample input]

15

liping 13512345678

zhaohong 13838929457

qiansan 13900223399

zhouhao 18578294857

anhai 13573948758

liping 13512345678

zhaohong 13588339922

liping 13833220099

boliang 15033778877

zhaohong 13838922222

tianyang 18987283746

sunnan 13599882764

zhaohong 13099228475

liushifeng 13874763899

caibiao 13923567890

[Sample output]

anhai 13573948758

boliang 15033778877

caibiao 13923567890

liping 13512345678

liping_1 13833220099

liushifeng 13874763899

qiansan 13900223399

sunnan 13599882764

tianyang 18987283746

zhaohong 13838929457

zhaohong_1 13588339922

zhaohong_2 13838922222

zhaohong_3 13099228475

zhouhao 18578294857

[Example description]

15 names and phone numbers were entered. The first item and the sixth item are exactly the same, both are "liping 13512345678", the sixth item is deleted, and the first item is retained;

If the name of the eighth item and the first item are the same, but the phone number is different, the name of the eighth item will be sorted as liping_1; similarly, the names of the second, seventh, tenth, and thirteenth items are all the same, and the last three The names of the items are organized as: zhaohong_1, zhaohong_2 and zhaohong_3.

Finally, the sorted phone book is sorted by name from small to large, and the sorting results are output by branch.

This question requires programming to sort and sort the address book, and the submitted program file name is sort.c.

A relatively simple sorting question. Note that you don’t need to line up the phone numbers, otherwise you will look like me for a long time and don’t know where the problem is ().

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

struct people
{
char name[30];
char tel[20];
} tel_dir[100];

int cmp(const void *a, const void *b)
{
struct people *aa = (struct people *)a;
struct people *bb = (struct people *)b;
return strcmp(aa -> name, bb -> name);
}

int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s %s", tel_dir[i].name, tel_dir[i].tel);
}
qsort(tel_dir, n, sizeof(tel_dir[0]), cmp);

int same_name_cnt = 1;
printf("%s %s\n", tel_dir[0].name, tel_dir[0].tel);
for (int i = 1; i < n; i++)
{
if (strcmp(tel_dir[i].name, tel_dir[i - 1].name) == 0)
{
if (strcmp(tel_dir[i].tel, tel_dir[i - 1].tel) == 0)
{
continue;
}
else
{
printf("%s_%d", tel_dir[i].name, same_name_cnt++);
printf(" %s\n", tel_dir[i].tel);
}
}
else
{
printf("%s %s\n", tel_dir[i].name, tel_dir[i].tel);
same_name_cnt = 1;
}
}

return 0;
}
```

## 5. Small library management system

[Problem Description]
Xiao Ming especially likes to buy and read books. Due to the large number of books and the messy arrangement, it is very troublesome to find them. After Xiao Ming took the data structure and programming class this semester, he decided to change this situation: use C to develop a small library management system. The book information contained in the system includes: title, author, publisher, publication date, etc. First of all, the library management system arranges the existing books (original library, stored in a text file) according to the lexicographical order of the titles (according to the ASCII code value of each character in the title from small to large) The sequenced book information files generate an ordered file, that is, the new library) for easy search. The management system can perform the following operations on book entries in the new library:
1. Enter. Add new books to the library (that is, read a piece of book information from the input and insert it into the relevant position of the sorted book file)
2. Find. Find related book information in the library according to the title or keyword information in the title. If there are multiple books, output them in lexicographical order.
3. Delete. Enter the book title or keyword information in the title, find and delete related books from the library, and update the library.
[Input form]
The original book information (original library) is saved in books.txt in the current directory.
User operations are read from the console, first input the operation function serial number (1 represents input operation, 2 represents search operation, 3 represents delete operation, 0 represents save the updated book information in the library and exit the program), and then enter in the next line Corresponding operation information (you need to enter a piece of book information after the input operation, and you only need to enter the book title or part of the information in the book title after the search and delete operations). Multiple operations can be performed during program execution until the program is exited (input operation 0).
Require:
1. The format of the book information in the original file is the same as that of the entered book information. Each piece of book information is on one line, including the title (no more than 50 characters), author (no more than 20 characters), and publisher (no more than 20 characters). 30 characters) and publication date (not to exceed 10 characters), consisting only of English letters and underscores, separated by a space. The total number of book information will not exceed 500.
2. The underscore character participates in the sorting.
3. Books will not have the same name.
[Output format]
Enter and delete operations, the system will update the book information, but will not display any information in the console window.
After the search operation is performed, the searched book information will be output on the console according to the dictionary order of the book title. The title occupies 50 characters, the author occupies 20 characters, the publisher occupies 30 characters, and the publication date occupies 10 characters. Character width, all left-aligned output.
The final book information sorted by dictionary is stored in ordered.txt in the current directory, each book information occupies one line, and the format is the same as that of the search output book information.
[Sample input]
Suppose the original book information saved in books.txt is:
The_C_programming_language Kernighan Prentice_Hall 1988
Programming_in_C Yin_Bao_Lin China_Machine_Press 2013
ANSI_and_ISO_Standard_c Plauger Microsoft_Press 1992
Data_structures_and_program_design_in_C Robert_Kruse Pearson_Education 1997
Computer_network_architectures Anton_Meijer Computer_Science_Press 1983
C_programming_guidelines Thomas_Plum Prentice_Hall 1984
Data_structures_using_C Tenenbaum Prentice_Hall 1990
Computer_networks_and_internets Douglas_E_Come Electronic_Industry 2017
The user console input information is:
1
2
structure
1
2
rogram
3
rogramming
0
[Sample output]
After the user enters "2 structure", the console outputs:

```Data_structures_and_Algorithm_Analysis_in_C       Mark_Allen_Weiss    Addison_Wesley                1997
Data_structures_and_program_design_in_C           Robert_Kruse        Pearson_Education             1997
Data_structures_using_C                           Tenenbaum           Prentice_Hall                 1990
```

After the user enters "2 rogram", the console outputs:

```C_programming_guidelines                          Thomas_Plum         Prentice_Hall                 1984
Data_structures_and_program_design_in_C           Robert_Kruse        Pearson_Education             1997
Programming_in_C                                  Yin_Bao_Lin         China_Machine_Press           2013
The_C_programming_language                        Kernighan           Prentice_Hall                 1988
```

The content of the ordered.txt file is:

```ANSI_and_ISO_Standard_c                            Plauger              Microsoft_Press                1992
Computer_network_architectures                     Anton_Meijer         Computer_Science_Press         1983
Computer_networks_and_internets                    Douglas_E_Come       Electronic_Industry            2017
Data_structures_and_program_design_in_C            Robert_Kruse         Pearson_Education              1997
Data_structures_using_C                            Tenenbaum            Prentice_Hall                  1990
```

[Example description]
First read 10 pieces of book information in books.txt, and sort them lexicographically according to the title; the user performs five operations, and then exits: the first operation is to insert a piece of book information, and there are 11 pieces of book information at this time, Sorted lexicographically by title:

```ANSI_and_ISO_Standard_c Plauger Microsoft_Press 1992
C_programming_guidelines Thomas_Plum Prentice_Hall 1984
Computer_network_architectures Anton_Meijer Computer_Science_Press 1983
Computer_networks_and_internets Douglas_E_Come Electronic_Industry 2017
Data_structures_and_program_design_in_C Robert_Kruse Pearson_Education 1997
Data_structures_using_C Tenenbaum Prentice_Hall 1990
Programming_in_C Yin_Bao_Lin China_Machine_Press 2013
The_C_programming_language Kernighan Prentice_Hall 1988
```

The second operation is to search for books whose title contains structure, and 4 book information is output to the screen according to the format requirements; the third operation inserts another book information, and there are 12 book information at this time; the fourth operation searches for books For books whose title contains rogramming, 6 book information is output to the screen according to the format requirements; the fifth operation is to delete the book information whose title contains rogramming, there are four book information to be deleted, and there are eight book information left; before exiting the program, the The remaining eight pieces of book information are stored in the ordered.txt file according to the format requirements.

The program requires writing a library management system. The submitter file is called books.c.

Just write as required. The way I delete the operation here is to overwrite the title of the book with the largest dictionary order, and then sort it.

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

#define LOGI 1
#define SEAR 2
#define DELE 3
#define EXIT 0

struct book
{
char name[50];
char author[20];
char publisher[30];
char publish_data[10];
} lib[500];

int cmp(const void *a, const void *b)
{
return strcmp(((struct book *)a)->name, ((struct book *)b)->name);
}

int main()
{
FILE *books = fopen("books.txt", "r");
FILE *ordered = fopen("ordered.txt", "w");

int n = 0;
while (~fscanf(books, "%s %s %s %s", lib[n].name, lib[n].author, lib[n].publisher, lib[n].publish_data))
{
n++;
}
qsort(lib, n, sizeof(lib[0]), cmp);

int order;
scanf("%d", &order);
while (order != EXIT)
{
switch (order)
{
case LOGI:
scanf("%s %s %s %s", lib[n].name, lib[n].author, lib[n].publisher, lib[n].publish_data);
qsort(lib, ++n, sizeof(lib[0]), cmp);
break;
case SEAR:;
char sea_target[50];
scanf("%s", sea_target);
for (int i = 0; i < n; i++)
{
if (strstr(lib[i].name, sea_target) != NULL)
{
printf("%-50s%-20s%-30s%-10s\n", lib[i].name, lib[i].author, lib[i].publisher, lib[i].publish_data);
}
}
break;
case DELE:;
char del_target[50];
int del_cnt = 0;
scanf("%s", del_target);
for (int i = 0; i < n; i++)
{
if (strstr(lib[i].name, del_target) != NULL)
{
memset(lib[i].name, 126, sizeof(lib[i].name));
del_cnt++;
}
}
qsort(lib, n, sizeof(lib[0]), cmp);
n -= del_cnt;
break;
default:
break;
}
scanf("%d", &order);
}

for (int i = 0; i < n; i++)
{
fprintf(ordered, "%-50s%-20s%-30s%-10s\n", lib[i].name, lib[i].author, lib[i].publisher, lib[i].publish_data);
}

fclose(books);
fclose(ordered);

return 0;
}
```

Posted by JohnResig on Thu, 09 Mar 2023 22:48:02 +1030