Data structure experiment 1 library information management based on linear table

Preparation before experiment

IDE selection

The IDE adopted is Visual_Studio_2019, SDL check needs to be turned off here


Other methods to solve scanf error

1. Add at the beginning of the program:

#define _CRT_SECURE_NO_DEPRECATE

2. Add at the beginning of the program:

#pragma warning(disable:4996)

About OVERFLOW
Generally, it needs to be at the front of the program:

#define OVERFLOW -2

However, note that in the IDE VS2019, OVERFLOW has a default value of 3, so the above operations are not required, otherwise an error will be reported; When running on other compilers, you need to add this sentence.
For portability, I delete OVERFLOW in the program and write -2 as the return value.

Pointer and structure in C language

Introduction to C language pointer
Introduction to c language structure and pointer.
typedef and struct
Understand various C language pointers, NULL pointers, zero pointers, wild pointers, and dangling pointers
What is the meaning of "dangling pointer" and "wild pointer" in C language?

int main(int argc, char* argv[])
//ARG in ARGc and ARGv refers to "parameter"
//(foreign languages: ARGuments, argument counter and argument vector)

Experimental purpose

1. master the sequential storage representation and chain storage representation of linear tables
2. master the basic operations of sequence list and linked list, including the algorithms of creation, search, insertion and deletion
3. make clear the characteristics and application occasions of the two different storage structures of the linear table, and their respective advantages and disadvantages

Experiment content

The book information table includes the following 10 common basic operations: creation, output, sorting and modification of the book information table Reverse order depositors, search for the most expensive books, search for favorite books, search for books in the best position, library of new books, ex warehouse of old books, and de duplication of books. The experiment requires that the above 10 operations be realized by using the sequence list and the linked list respectively. Therefore, the experiment content includes the following 20 questions in total. The first 10 require that the corresponding functions be realized based on the sequence list, and the last 10 require that the corresponding functions be realized based on the linked list.

1. creation and output of book information table based on sequential storage structure

Problem description

Define a sequence table containing book information (book number, book name, price), and read the corresponding book data to complete the creation of the book information table. Then, count the number of books in the book table, and output the information of each book line by line.

Input requirements

Enter line n+1, where the first n lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The last n+1 line is the input end flag: 0 00 (three zeros separated by spaces). The book number and title are of string type, and the price is of floating-point type.

Output requirements

There are n+1 lines in total. The first line is the number of books in the created book information table. The next N lines are the information of n books (book number, book name and price). Each book information occupies one line, and the book number, book name and price are separated by spaces. The price output shall be kept to two decimal places. sample input

9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00
0 0 0

sample output

6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00

code

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
//typedef Book Elemtype; Not here, but below
typedef int Status;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef struct {
	Book* elem;                //Base address of storage space
	int length;                //Current number of books in the book table
}SqList;                       //The sequential storage structure type of the library is SqList
typedef Book Elemtype;

//Book a[50];
//SqList c[50];
//SqList* L = c;
//SqList t;
//Initialization of sequence table
Status InitList(SqList* L) {
	//L->elem = (Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
	L->elem = new Book[MAXSIZE];
	//L->elem = (int*) malloc (sizeof (int) * maxsize)// No, Book*
	//L->elem = (int*) new int[maxsize]// No, the reason is the same as above
	//The return value of malloc is a pointer to the starting address of a section of available memory
	if (!L->elem)
		exit(-2);
	L->length = 0;
	return OK;
}
//The following is a self created linear table insert emmmmmm
/*
int main() {
	//SqList *L;
	InitList(L);
	for (L->length = 0; L->length < MAXSIZE; L->length++) {
		scanf("%s %s %f", &(L + L->length)->elem->no, &(L + L->length)->elem->name, &(L + L->length)->elem->price);
		if ((L + L->length)->elem->no == 0 && (L + L->length)->elem->name == 0 && (L + L->length)->elem->price == 0)
			break;
	}
	printf("%d\n", L->length);
	for (int i = 0; i < L->length; i++) {
		printf("%s %s %.2f\n", (L + i)->elem->name, (L + i)->elem->no, (L + i)->elem->price);
	}

}*/

//The following is the linear table insertion on the timetable, but I find that the first question seems to be useless
Status ListInsert(SqList* L, int i, Book e) {
	//If it is Elemtype / / PS, the original Elemtype is defined by int, but it is actually defined by Book
	//typedef Book Elemtype;
	//Or int e, l->elem[i-1] will report an error
	//Insert a new element e before the ith position in the sequence table L, and the legal range of i value is 1 ~ l->length+1
	if ((i < 1) || (i > L->length + 1)) return ERROR; //Illegal i value
	if (L->length == MAXSIZE) return ERROR;//Current storage space is full
	for (int j = L->length - 1; j >= i - 1; j--) {
		L->elem[j + 1] = L->elem[j];//Insert position and subsequent element move back
	}
	L->elem[i - 1] = e;//Put the new element e in position i
	++L->length;//Meter length +1
	return OK;
}

int main() {
	int i;
	SqList c[MAXSIZE];
	SqList* L = c;
	//Book e;
	InitList(L);
	Book b[MAXSIZE];
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &b[i].no, &b[i].name, &b[i].price);
		//if (strcmp(b[i].no, 0) && strcmp(b[i].name, 0) && (b[i].price == 0)) {break;}
		//if (b[i].no == '0' && b[i].name == 0 && b[i].price == 0)  break;
		if (!strcmp(b[i].no, "0") && !strcmp(b[i].name, "0") && b[i].price == 0.0) break;
		//Hey! strcmp(b[i].no, 0) is wrong because it can only execute one line
		//Hey! StrCmp (b[i].no,'0') cannot be compiled
	}
	printf("%d\n", i);
	for (int j = 0; j < i; j++) {
		printf("%s %s %.2f\n", b[j].no, b[j].name, b[j].price);
	}
	//ListInsert(L, i, e);
	return 0;
}

Problems encountered in the experiment ①

I have a lot to say. First, SqList * l;
Defining a pointer without assigning an initial value in this way will result in an error when running.
SqList c[MAXSIZE];
SqList L = c;*
It must be written in this way, otherwise, the runtime will flash back (no matter what version of compiler is used).

Obviously, only SqList *L;
In this sentence, whether in the global scope or in the main function, a null pointer or a wild pointer is defined, just as in VS, L is nullptr.

In the debug mode of vc, the uninitialized stack memory is filled with 0xcc, which corresponds to the Chinese character string in MBCS code; The uninitialized team memory is filled with 0xcd, which corresponds to the man string, and it is tuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntun; In the release mode, it is the random data in the memory directly.

Structure pointers can also be used as arguments to functions
What needs to be noted here is
Use structure variables to get member usage operator
Get member using struct pointer - > operator
If we do not use the structure variable declaration, but create the structure through malloc function, we will get the structure pointing to the address of the open space

My original idea was:
I originally defined a structure
typedef struct{
}SqList;
Then SqList *L;
I thought L was the pointer to the structure
I didn't expect this definition to be a null pointer

The structure pointer we usually refer to actually refers to the pointer to the structure type data.

Structure is our newly defined data type. Like int, char and float, these keywords only represent types and do not occupy memory space. Structure variables or structure data are actually created data. With memory space, we can create pointers to structure data, but not to the structure itself, The structure pointer refers to the pointer to the structure type data rather than the pointer to the structure

In addition to this method, we can also directly SqList L;
Then, by reference, avoid defining the pointer * L directly
The method of reference is as follows.
Quotation I

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef struct {
	Book* elem;                //Base address of storage space
	int length;                //Current number of books in the book table
}SqList;                       //The sequential storage structure type of the library is SqList
typedef Book Elemtype;
Status InitList(SqList* L) {
	//L->elem = (Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
	L->elem = new Book[MAXSIZE];
	//The return value of malloc is a pointer to the starting address of a section of available memory
	if (!L->elem)
		exit(-2);
	L->length = 0;
	return OK;
}

int main() {
	int i;
	SqList L;
	InitList(&L);
	Book b[MAXSIZE];
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &b[i].no, &b[i].name, &b[i].price);
		if (!strcmp(b[i].no, "0") && !strcmp(b[i].name, "0") && (b[i].price == 0)) break;
	}
	printf("%d\n", i );
	for (int j = 0; j < i; j++) {
		printf("%s %s %.2f\n", b[j].no, b[j].name, b[j].price);
	}
}

Method 1, which uses the reference symbol in the main function, is not mentioned in Hu fan's algorithm notes.

InitList(&L);
Status InitList(SqList* L){}

Quotation II

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef struct {
	Book* elem;                //Base address of storage space
	int length;                //Current number of books in the book table
}SqList;                       //The sequential storage structure type of the library is SqList
typedef Book Elemtype;
Status InitList(SqList& L) {
	//L->elem = (Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
	L.elem = new Book[MAXSIZE];
	//The return value of malloc is a pointer to the starting address of a section of available memory
	if (!L.elem)
		exit(-2);
	L.length = 0;
	return OK;
}

int main() {
	int i;
	SqList L;
	InitList(L);
	Book b[MAXSIZE];
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &b[i].no, &b[i].name, &b[i].price);
		if (!strcmp(b[i].no, "0") && !strcmp(b[i].name, "0") && (b[i].price == 0)) break;
	}
	printf("%d\n", i );
	for (int j = 0; j < i; j++) {
		printf("%s %s %.2f\n", b[j].no, b[j].name, b[j].price);
	}
}

The types of function reference models used in method 2 are as follows:

#include<stdio.h>
void change(int &x){
 x=1;
}
int main(){
 int a = 10;
 change(a);
 printf("%d\n",a);
 return 0;
}

Problems encountered in the experiment ②

About strcmp() function

if (!strcmp(b[i].no, "0") && !strcmp(b[i].name, "0") && (b[i].price == 0)) 
break;

First, here! And "0", I was wrong at first.
If yes! strcmp(b[i].no, 0) can only be broken by entering one line
If yes! strcmp(b[i].no, '0') can not pass the compilation
I missed it at first!, This indicates that you do not know enough about the final output of the strcmp function.

Compare two strings. Set these two strings as STR1 and STR2, and return zero if str1=str2; If str1>str2, a positive number is returned; If str1<str2, a negative number is returned.

Introduction to strcmp function
The strcmp function returns 0 if it is equal.

6. search for favorite books in book information table based on sequential storage structure

Problem description
Define a sequence table containing book information (book number, book name, price), and read the corresponding book data to complete the creation of the book information table. Then, according to the name of the specified favorite book, find the favorite book and output the information of the corresponding book.
Input requirements
Total n+m+2 lines. First, enter the n+1 line. The first line is the number of books n, and the next N lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The book number and title are of string type, and the price is of floating-point type. Then enter line m+1, where the first line is an integer m, representing m times of searching, and the last line m is the name of the favorite book to be searched each time.
Output requirements
If the search is successful:
A total of m(k+1) rows are output. For each search, the first row is the number of favorite books (there may be multiple books with the same book name), and the last K rows are the information of favorite books (book number, book name and price). Each book information occupies one row, and the book number, book name and price are separated by spaces. The price output shall be kept to two decimal places.
If the search fails:
Only output the following prompt: sorry, there is no your favorite!
sample input
6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00
2
data structure
Fundamentals of programming
sample output
Sorry, not your favorite!
1
9787302257646 fundamentals of program design 25.00

code

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef struct {
	Book* elem;                //Base address of storage space
	int length;                //Current number of books in the book table
}SqList;                       //The sequential storage structure type of the library is SqList
typedef Book Elemtype;
Status InitList(SqList* L) {
	L->elem = (Elemtype*)malloc(sizeof(Elemtype) * MAXSIZE);
	//The return value of malloc is a pointer to the starting address of a section of available memory
	if (!L->elem)
		exit(-2);
	L->length = 0;
	return OK;
}
int main() {
	int n;//Book Bibliography
	int i, j;
	Book b[MAXSIZE];
	scanf("%d", &n);
	SqList L;
	InitList(&L);
	for (i = 0; i < n; i++) {
		scanf("%s %s %f", &b[i].no, &b[i].name, &b[i].price);
	}
	int m;//Find m times
	scanf("%d", &m);
	Book b_1[MAXSIZE];
	for (int k = 0; k < m; k++) {
		scanf("%s", &b_1[k].name);
	}
	for (int k = 0; k < m; k++) {
		for (j = 0; j < i; j++) {
			//printf("1%s\n", b_1[k].name);
			//printf("2%s\n", b[j].name);
			//if (b_1[k].name == b[j].name) {
			if (!strcmp(b_1[k].name , b[j].name)) {
				printf("%d\n", j + 1);
				printf("%s %s %.2f\n", b[j].no, b[j].name, b[j].price);
				break;
			}
			if (j == i - 1 && b_1[k].name != b[j].name) {
				printf("Sorry, there is no your favorite here!\n");
			}
		}
	}
}

It is not very difficult to do it on the basis of experiment 1.1.

Problems encountered in the experiment

There is also a problem with the strcmp() function.
String comparison.

if (b_1[k].name == b[j].name) 
if (!strcmp(b_1[k].name , b[j].name)) 

The strings here are equal, and cannot be = =. Even if the strings are the same, they cannot return true; You need to use the strcmp() function to solve this problem.

8. warehousing of new books in book information table based on sequential storage structure

Problem description
First, define a sequence table containing book information (book number, book name, price), and read in the corresponding book data to complete the creation of the book information table. Then, according to the specified location and information of the new book to be warehoused, insert the new book into the specified location in the book table. Finally, output the information of all the books after the new books are put into storage.
Input requirements
Total n+3 lines. First, enter the n+1 line. The first line is the number of books n, and the next N lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The book number and title are of string type, and the price is of floating-point type. Then enter line n+2, the content is only an integer, representing the position serial number of the new book to be warehoused. Finally, enter line n+3. The content is the information of the new book. The book number, title and price are separated by spaces.
Output requirements
If the insertion is successful:
Output the information (book number, book name and price) of all books after the new book is put into storage, totaling n+1 lines. Each line is the information of a book, and the book number, book name and price are separated by spaces. The price output shall be kept to two decimal places.
If insertion fails:
Only the following prompt is output: sorry, the storage location is illegal!
sample input
6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00
2
9787302265436 computer introduction experiment guide 18.00
sample output
9787302257646 fundamentals of program design 25.00
9787302265436 computer introduction experiment guide 18.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00

code

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef struct {
	Book* elem;                //Base address of storage space
	int length;                //Current number of books in the book table
}SqList;                       //The sequential storage structure type of the library is SqList
typedef Book Elemtype;
//Initialization of sequence table
Status InitList(SqList* L) {
	L->elem = (Elemtype*)malloc(sizeof(Elemtype) * MAXSIZE);
	//The return value of malloc is a pointer to the starting address of a section of available memory
	if (!L->elem)
		exit(-2);
	L->length = 0;
	return OK;
}
//Insertion of sequence table
Status ListInsert(SqList& L, int i, Elemtype e) {
	//Insert a new element e before the ith position in the sequence table L, and the legal range of I value is 1<=i<=l.length+1
	if ((i < 1) || (i > L.length + 1)) return ERROR;//Illegal i value
	if (L.length == MAXSIZE) return ERROR;//Current storage space is full
	for (int j = L.length - 1; j >= i - 1; j--) {
		L.elem[j + 1] = L.elem[j];//Insert position and subsequent elements to the right
	}
	L.elem[i - 1] = e;//Put the new element e in position i
	++L.length;//Meter length plus 1
	return OK;
}
int main() {
	int n;//Book Bibliography
	int i;
	Book b[MAXSIZE];
	scanf("%d", &n);
	SqList L;
	InitList(&L);
	for (i = 0; i < n; i++) {
		scanf("%s %s %f", &b[i].no, &b[i].name, &b[i].price);
	}
	L.length = n;
	int m;//Insert location
	scanf("%d", &m);//Enter line n+2
	Book in_b;
	//Inserted content
	//scanf("%s %s %f", &in_b.no, &in_b.name, &in_b.price);
	scanf("%s %s %f", in_b.no, in_b.name, &in_b.price);
	/*
	scanf("%s", &in_b.no);
	scanf("%s", &in_b.name);
	scanf("%f", &in_b.price);
	*/
	L.elem = b;
	ListInsert(L, m, in_b);
	//ListInsert(L, m, b[m]); 
	for (int k = 0; k < n + 1; k++)
	{
		printf("%s %s %.2f\n", b[k].no, b[k].name, b[k].price);
	}
}

Problems encountered in the experiment ①

It is still the relationship between pointers, references and functions
How to use ListInsert is a key function module.

ListInsert(L, m, in_b);

Here's a blow. The single-step debugging of VS2019 is really convenient. When I first wrote it, I missed two places.
One is:

L.elem = b;

The other is:

L.length = n;

It can be seen that I am defining SqList L; After that, I hardly used it. During the process, I found that the contents of the L array were garbled, and L.length was not assigned. It was still in the state of initialization =0.

Problems encountered in the experiment ②

Relationships among pointers, references, and functions
To another key point.
At first I wrote:

ListInsert(L, m, b[m]);

I am writing l.elem = B; 50. Length = n; The operation was changed again and found feasible. Therefore, the pointer at the beginning of L has been initialized, and the length has no assignment problem.
The following wording is also feasible:

Book p = *(b + m);
ListInsert(L, m, p); 

The following is working correctly:

ListInsert(L, m, in_b);

Problems encountered in the experiment ③

In the process of summarizing, the error of running is suddenly check ed. In my example, the content of line 2 is inserted, but it backfires.
Oh, no!
I found that ListInsert(L, m, in_b); The result of writing is right, and the other two are wrong.
At first, I guessed that the problem should be the size of M. it is estimated that 1 should be subtracted before the other two methods use m to cause errors in the third parameter.
But it is not. The biggest problem with these two methods (using b[m] and P) is that the inserted statement is not input at all, and in_b is to directly define a variable of type Book, then input the statement into the structural variable, and then insert the statement. Both b[m] and p=* (b+m) mean the same thing. They only rotate in the array entered for the first time, and do not enter the inserted content at all!
Correct operation results:

Bad run result:

The biggest reason for the error is that it is written in this way. As a result, the inserted content does not enter the ListInsert function.

11. creation and output of book information table based on chain storage structure

Problem description
Define a linked list containing book information (book number, book name, price), and read in the corresponding book data to complete the creation of the book information table. Then, count the number of books in the book table, and output the information of each book line by line.
Input requirements
Enter line n+1, where the first n lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The last n+1 line is the input end flag: 00 00 (three zeros separated by spaces). The book number and title are of string type, and the price is of floating-point type.
Output requirements
There are n+1 lines in total. The first line is the number of books in the created book information table. The next N lines are the information of n books (book number, book name and price). Each book information occupies one line, and the book number, book name and price are separated by spaces. The price output shall be kept to two decimal places.
sample input
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00
0 0 0
sample output
6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00

code

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
int i;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode {
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L) {
	//L = (LNode*)malloc(sizeof(LNode))// Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L = new LNode;
	L->next = NULL;
	return OK;
}

//Post insertion is the order of topics
void CreateList_H(LinkList& L) {
	//Enter the values of n elements in the positive sequence to establish a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;  //First, create an empty linked list of leading nodes
	LinkList r = L;           //Tail pointer r points to the head node
	for (i = 0; i < MAXSIZE; i++) {
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		if (!(strcmp(p->data.no, "0")) && !(strcmp(p->data.name, "0")) && p->data.price == 0) {
			break;
		}
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

int main() {
	int  j;
	LNode* L;
	InitList(L);
	CreateList_H(L);
	for (j = 0; j < i; j++) {
		L = L->next;
		printf("%s %s %.2f\n", L->data.no, L->data.name, L->data.price);
		
	}
}

Error example: the following code is not wrong, but simply creates a linked list, using properties and pointers similar to arrays.

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode {
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));//Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L->next = NULL;
	return OK;
}
int main() {
	int i, j;
	LNode* L = NULL;
	InitList(L);
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &(L + i)->data.no, &(L + i)->data.name, &(L + i)->data.price);
		if (!(strcmp((L + i)->data.no, "0")) && !(strcmp((L + i)->data.name, "0")) && (L + i)->data.price == 0) {
			break;
		}
	}
	for (j = 0; j < i; j++) {
		printf("%s %s %.2f\n", (L + j)->data.no, (L + j)->data.name, (L + j)->data.price);
	}
}

Problems encountered in the experiment ①

It is easy to write, but there is a problem. Both input and output are in the form of L + i, which is similar to the array feature used in the main function. L = L - > next; Can you try to use this kind of?
As shown in the following figure, an error occurred during operation.

Error code at run time:

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode {
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));//Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L->next = NULL;
	return OK;
}
int main() {
	int i, j;
	LNode* L = NULL;
	InitList(L);
	LinkList p = L;
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &L->data.no, &L->data.name, &L->data.price);
		if (!(strcmp(L->data.no, "0")) && !(strcmp(L->data.name, "0")) && L->data.price == 0) {
			break;
		}
		L = L->next;
	}
	for (j = 0; j < i; j++) {
		printf("%s %s %.2f\n", p->data.no, p->data.name, p->data.price);
		p = p->next;
	}
}

First, there are serious problems with the above code.

The problem is that there is no process to create a linked list by directly entering values here. P = P - > next; This sentence is the root of the mistake. There is no pre insertion and post insertion, or the feature of the linked list is not used at all, and there is no process of creating the linked list.
P = P - > next; Before p - > next = null; However, P - > next - > next has no value at all, which is directly a running error.
The modified code adopts the post interpolation method.

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
int i;
typedef struct {
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode {
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L) {
	//L = (LNode*)malloc(sizeof(LNode))// Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L = new LNode;
	L->next = NULL;
	return OK;
}

//Value of single linked list
/*
Status GetElem(LinkList L, int i, Elemtype& e) {
	//In the single linked list L of the leading node, the value of the element is obtained according to the sequence number i, and e is used to return the value of the ith data element in L
	LNode* p = L->next;  //Initialization, p points to the initial node
	int j = 1;   //Initial value of counter j is set to 1
	while (p && j < i)//Scan the chain domain backward until p is empty or p points to the ith element
	{
		p = p->next;//p Point to the next node
		++j;  //Counter j increases by 1 accordingly
	}
	if (!p || j > i) return ERROR;  //i Illegal value i>n or i<=0
	e = p->data;   //Take the data field of the ith node
	return OK;
}
*/

//The following is purely self created. Instead of using the properties of a single linked list, it uses the properties of an array
/*
int main() {
	int i, j;
	LNode* L = NULL;
	InitList(L);
	for (i = 0; i < MAXSIZE; i++) {
		scanf("%s %s %f", &(L + i)->data.no, &(L + i)->data.name, &(L + i)->data.price);
		if (!(strcmp((L + i)->data.no, "0")) && !(strcmp((L + i)->data.name, "0")) && (L + i)->data.price == 0) {
			break;
		}
	}
	for (j = 0; j < i; j++) {
		printf("%s %s %.2f\n", (L + j)->data.no, (L + j)->data.name, (L + j)->data.price);
	}
}*/

//Forward interpolation, wrong sequence
/*
void CreateList_H(LinkList& L) {
	//Enter the values of n elements in reverse order to create a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;
	for (i = 0; i < MAXSIZE; i++) {
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		p->next = L->next;
		L->next = p;
		if (!(strcmp(p->data.no, "0")) && !(strcmp(p->data.name, "0")) && p->data.price == 0) {
			break;
		}
	}
	L->next = NULL;
}*/

//Post insertion is the order of topics
void CreateList_H(LinkList& L) {
	//Enter the values of n elements in the positive sequence to establish a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;  //First, create an empty linked list of leading nodes
	LinkList r = L;           //Tail pointer r points to the head node
	for (i = 0; i < MAXSIZE; i++) {
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		if (!(strcmp(p->data.no, "0")) && !(strcmp(p->data.name, "0")) && p->data.price == 0) {
			break;
		}
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

int main() {
	int  j;
	LNode* L;
	InitList(L);
	CreateList_H(L);
	for (j = 0; j < i; j++) {
		L = L->next;
		printf("%s %s %.2f\n", L->data.no, L->data.name, L->data.price);
		
	}
}

Problems encountered in the experiment ②

About null pointers.

How to change the null pointer error in programming (C language)?
char *str=null;strcpy(str,"hello world");
Do not know the length of the string to be stored in advance
Best answer
On November 22, 2008, answer char * str= (char *) malloc (11 * sizeof (char)); Strcpy (STR, "hello world");
Open mirror waterstop grade 7
2008-11-22 answer: you can dynamically allocate memory and set the capacity a little larger.
North, what level 2 are you in
2008-11-22 answer with memcpy() do not worry about overflow
Near d è local level 5
On November 22, 2008, answer char *str=null; It indicates that STR is a null pointer and has no real address. You must apply for an address before using it. Whether you use strcpy or memcpy, you must apply for an address if you want to store characters. You can apply for an address with malloc, etc.
Harmony level 4
2008-12-05 answer with dynamic storage allocation

Problems encountered in the experiment ③

The difference between forward interpolation and backward interpolation.

Forward interpolation

void CreateList_H(LinkList& L) {
	//Enter the values of n elements in reverse order to create a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;
	for (i = 0; i < MAXSIZE; i++) {
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		p->next = L->next;
		L->next = p;
		if (!(strcmp(p->data.no, "0")) && !(strcmp(p->data.name, "0")) && p->data.price == 0) {
			break;
		}
	}
	L->next = NULL;
}

Forward interpolation requires the values of the elements to be entered in reverse order.

Backward interpolation

//Post insertion is the order of topics
void CreateList_H(LinkList& L) {
	//Enter the values of n elements in the positive sequence to establish a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;  //First, create an empty linked list of leading nodes
	LinkList r = L;           //Tail pointer r points to the head node
	for (i = 0; i < MAXSIZE; i++) {
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		if (!(strcmp(p->data.no, "0")) && !(strcmp(p->data.name, "0")) && p->data.price == 0) {
			break;
		}
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

The post interpolation method is a positive sequence input, which meets the requirements of the topic.

15. search for the most expensive books in the book information table based on the chain storage structure

Problem description
Define a linked list containing book information (book number, book name, price), and read in the corresponding book data to complete the creation of the book information table. Then, find the book with the highest price and output the information of the corresponding book.
Input requirements
Enter a total of n+1 lines. The first line is the number of books n, and the next N lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The book number and title are of string type, and the price is of floating-point type.
Output requirements
A total of m+1 lines are output, of which the first line is the number of the most expensive books (there may be multiple books with the highest price), and the last m line is the information of the most expensive books (book number, title and price). Each book information occupies one line, and the book number, title and price are separated by spaces. The price output shall be kept to two decimal places.
sample input
6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811230710 C\
sample output
2
978730221972 MCU technology and application 32.00
9787811230710 C\

code

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
int i;
typedef struct
{
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode
{
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L)
{
	//L = (LNode*)malloc(sizeof(LNode))// Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L = new LNode;
	L->next = NULL;
	return OK;
}
LinkList r_;
LinkList r_1;

//Post insertion is the order of topics
void CreateList_H(LinkList& L, int n)
{
	//Enter the values of n elements in the positive sequence to establish a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;  //First, create an empty linked list of leading nodes
	LinkList r = L;           //Tail pointer r points to the head node
	for (i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		p->next = NULL;
		r->next = p;
		r = p;
	}
}
//sort exchange data field, taking the maximum value
LinkList GetElem_max(LinkList& L)
{//The linked list has i nodes in total

	LNode* p = L->next;  //Initialization, p points to the initial node
	Book temp;
	for (int j = 0; j < i - 1; j++)
	{
		for (int k = 0; k < i - 1 - j; k++)
		{
			if (p->data.price > p->next->data.price)
			{//Only data fields need to be exchanged
				temp = p->next->data;
				p->next->data = p->data;
				p->data = temp;
			}
			p = p->next;
			if (j == 0)
			{
				r_ = p;
			}
		}
		p = L->next;
		r_1 = p;
	}
	LinkList e = p;
	return e;
}
int main()
{
	int n;//Book Bibliography
	int count_ = 1;
	scanf("%d", &n);
	LNode* L;
	InitList(L);
	CreateList_H(L, n);
	LinkList m = GetElem_max(L);
	LinkList r_3 = r_1;
	for (int i_2 = 0; i_2 < i - 1; i_2++)
	{
		if (r_1->data.price == r_->data.price)
		{
			count_++;
		}
		r_1 = r_1->next;
	}
	printf("%d\n", count_);
	for (int i_3 = 0; i_3 < i - count_; i_3++)
	{
		r_3 = r_3->next;
	}
	for (int i_4 = 0; i_4 < count_; i_4++)
	{
		printf("%s %s %.2f\n", r_3->data.no, r_3->data.name, r_3->data.price);
		while (r_3 != r_)
		{
			r_3 = r_3->next;
		}
	}
}

Problems encountered in the experiment ①

The first important point to note is that you can't use only one layer of bubble sorting, because it doesn't just output the leftmost maximum value, it has to output all prices as the maximum value, that is, you can't rule out the case that there are more than one maximum value.
The method adopted here is to sort by bubble, and then set two additional pointers, one pointing to the head node and the other pointing to the node with the maximum value at the tail, and then traverse the linked list. When the price corresponding to the data field of the node moving to the next direction is equal to the maximum, count is added automatically (count starts from 1), and the accumulated count value can be obtained, and then the position of the node in the linked list at the time of the first equality is recorded, Use a for loop to output the following one by one.

Problems encountered in the experiment ②

The second thing to note is that the bubble sort cycle here does not need to be as complex as the exchange node, but only needs to exchange the data field corresponding to the node.

if (p->data.price > p->next->data.price)
			{//Only data fields need to be exchanged
				temp = p->next->data;
				p->next->data = p->data;
				p->data = temp;
			}

19. ex warehouse of old books based on linked storage structure of book information table

Problem description
Define a linked list containing book information (book number, book name, price), and read in the corresponding book data to complete the creation of the book information table. Then, delete the old book from the book table according to the specified location of the old book to be issued. Finally, output the information of all the books after the book is out of the warehouse.
Input requirements
Total n+2 lines. First, enter the n+1 line. The first line is the number of books n, and the next N lines are the information of n books (book number, book name and price). Each book information occupies one line. The book number, book name and price are separated by spaces, and there is no space after the price. The book number and title are of string type, and the price is of floating-point type. Then enter line n+2, the content is only an integer, representing the position serial number of the old book to be deleted.
Output requirements
If the deletion is successful:
Output the information (book number, book name and price) of all the books after the old books are out of the warehouse, totaling n-1 lines. Each line is the information of a book, and the book number, book name and price are separated by spaces. The price output shall be kept to two decimal places.
If deletion fails:
Only the following prompt is output: sorry, the outbound location is illegal!
sample input
6
9787302257646 fundamentals of program design 25.00
9787302164340 fundamentals of program design (version 2) 20.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00
2
sample output
9787302257646 fundamentals of program design 25.00
978730221972 MCU technology and application 32.00
9787302203513 single chip microcomputer principle and application technology 26.00
9787810827430 industrial computer control technology - principle and application 29.00
9787811234923 assembly language programming tutorial 21.00

code

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
int i;
typedef struct
{
	char no[20];               //Book ISBN
	char name[50];             //Book name
	float price;               //Book price
}Book;
typedef Book Elemtype;

//————————————Storage structure of single linked list————————————
typedef struct LNode
{
	Elemtype data;//Data field of node
	struct LNode* next;//Pointer field of node
}LNode, * LinkList;//LinkList is the pointer type to the structure LNode
//Construct an empty single linked list
Status InitList(LinkList& L)
{
	//L = (LNode*)malloc(sizeof(LNode))// Generate a new node as the head node, and point to the head node with the head pointer L
	//L = (LinkList)malloc(sizeof(LNode))// This kind of writing is also OK
	L = new LNode;
	L->next = NULL;
	return OK;
}
//Create single linked list
void CreateList_H(LinkList& L, int n)
{
	//Enter the values of n elements in the positive sequence to establish a single linked list L with header nodes
	L = new LNode;
	L->next = NULL;  //First, create an empty linked list of leading nodes
	LinkList r = L;           //Tail pointer r points to the head node
	for (i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		scanf("%s %s %f", &p->data.no, &p->data.name, &p->data.price);
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

//Deleting a single linked list
Status ListDelete(LinkList& L, int i)
{//Delete the ith element in the single linked list of the leading node
	LinkList p = L;
	int j = 0;
	LinkList q;
	while ((p->next) && (j < i - 1))  //Find the i-1 node, and p points to it
	{
		p = p->next;
		++j;
	}
	//If (! (p->next) | (J > I - 1)) return error// When i>n or i<1, the deletion position is unreasonable
	if (!(p->next) || (j > i - 1))
	{
		printf("Sorry, the outbound location is illegal!");
		return ERROR;
	}
	q = p->next;     //Temporarily save the address of the deleted node for release
	p->next = q->next;  //Change the pointer field of the pre deletion node
	delete q;  //Free up space for deleting nodes
	return OK;
}
/*
There is a difference between the loop condition in the deletion algorithm (p->next&&j<i-1) and the loop condition in the insertion algorithm (p&& (j<i-1)).
Because there are n+1 legal insertion positions in the insert operation, and only n legal deletion positions in the delete operation,
If you use the same loop condition as the insert operation, the null pointer will be referenced and the delete operation will fail.
Null pointer will fail!!!
*/

int main()
{
	int n;//Book Bibliography
	scanf("%d", &n);
	LNode* L;
	InitList(L);
	CreateList_H(L, n);
	int m;
	scanf("%d", &m);
	ListDelete(L, m);
	for (int m_1 = 0; m_1 < i - m + 1; m_1++)
	{
		printf("%s %s %.2f\n", L->next->data.no, L->next->data.name, L->next->data.price);
		L = L->next;
	}
}

Problems encountered in the experiment ①

There is a difference between the loop condition in the deletion algorithm (p->next&&j<i-1) and the loop condition in the insertion algorithm (p&& (j<i-1)).
Because there are n+1 legal insertion positions in the insert operation, and only n legal deletion positions in the delete operation,
If you use the same loop condition as the insert operation, the null pointer will be referenced and the delete operation will fail.
Null pointer will fail!!!

This is a sentence in YanWeiMin's data structure book. The null pointer is quoted, which makes the operation fail. I stepped on the pit many times before. When quoting the null pointer, the code will not report an error, but the operation will make an error / exit without output, and the step-by-step debugging (step by step) will get stuck at a certain step. But as far as the deletion algorithm itself is concerned, this experiment is relatively simple.

Problems encountered in the experiment ②

How many times does the loop need to be cycled? If the number of cycles is wrong, it will not report an error. However, during operation, there will be no output exit, single-step debugging will get stuck, or output "tuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntuntun" and other random codes.

Personal summary

It's been several days since I decided to write it. I've filled in the freshman pit.
I feel that the application of C language has made full progress, but the code specification and other aspects have not been taken into account. I look forward to the next transformation.

Tags: C C++ data structure linked list pointer

Posted by subasi on Tue, 31 May 2022 11:05:55 +0530