I participated in the 14th day of the Challenge in August. For details, see:August is more challenging
1. Structure pointer variables as function parameters
The ANSI C standard allows structural variables to be used as function parameters for overall transmission. However, this kind of transfer will pass all the members one by one, especially when the members are arrays, which will make the time and space of the transfer cost very much, and seriously reduce the efficiency of the program. Therefore, the best approach is to use Pointers, which are passed as function arguments. In this case, only the address is passed from the argument to the parameter, thus reducing the time and space overhead.
Calculate the average grade and number of failing students in a group. Programming with structure pointer variables as function parameters.
struct stu
{
int num;
char *name;
char sex;
floatscore; }boy[5] = {{101."Li ping".'M'.45},
{102."Zhang ping".'M'.62.5},
{103."He fang".'F'.92.5},
{104."Cheng ling".'F'.87},
{105."Wang ming".'M'.58}};main()
{
struct stu *ps;
void ave(struct stu *ps);
ps=boy;
ave(ps);
}
void ave(struct stu *ps)
{
int c=0,i;
float ave,s=0;
for(i=0; i<5; i++,ps++) { s+=ps->score;if(ps->score<60) c+=1;
}
printf("s=%f\n",s);
ave=s/5;
printf("average=%f\ncount=%d\n",ave,c);
}
Copy the codeThis program defines the function ave, its parameter is the structure pointer variable ps. Boy is defined as an array of external structures and is therefore valid throughout the source program. The struct pointer variable ps is defined in the main function and is given the first address of boy so that ps points to the boy array. We then call the function ave with ps as the argument. Calculate the average score and count the number of failed students in the function AVE and output the results. Compared with example 7.4 program, because this program adopts pointer variables for operation and processing, it is faster and more efficient. .
2. Dynamic storage allocation — linked lists
In the array chapter, we saw that the length of an array is predefined and fixed throughout the program. Dynamic array types are not allowed in C. For example: int n; scanf(“%d”,&n); int a[n]; It is an error to dynamically specify the size of an array by using a variable to indicate length. In real programming, however, it often happens that the amount of memory required depends on the actual data entered and cannot be determined in advance. For this kind of problem, the array method is difficult to solve. To solve this problem, THE C language provides some memory management functions, which can dynamically allocate memory space as needed or reclaim unused space for use, providing a means for efficient utilization of memory resources. There are three commonly used memory management functions:
2.1 Allocate memory space malloc
Malloc (size) function: allocates a contiguous area of “size” bytes in the dynamic storage area of memory. The return value of the function is the first address of the range. The type specifier indicates what data type to use the field for. (Type specifier *) casts the return value to a pointer to that type. “Size” is an unsigned number. For example: PC =(char *) malloc (100); The function allocates 100 bytes of memory and casts it to a character array type. The function returns a pointer to the character array and assigns the pointer to the pointer variable PC.
2.2 Allocate memory space function calloc
Calloc is also used to allocate memory space.
Call form: (type specifier *)calloc(n,size)
Function: Allocate n contiguous regions of size bytes in the memory dynamic storage area. The return value of the function is the first address of the range. (Type specifier *) used to cast the type.
The calloc function differs from the malloc function only in that it can allocate n blocks at a time.
For example: ps=(struet stu*) calloc(2,sizeof (struct stu)); Sizeof (struct stu) is the length of stu. Allocate 2 contiguous blocks of the length of stU, cast to stU, and assign their first address to the pointer variable ps.
2.3 Free memory Space Function free
Free (void* PTR);
PTR is a pointer variable of any type. It points to the first address of the region to be freed. The freed region should be the region allocated by the malloc or calloc function.
3. The linked list
3.1 Assign an area and input a student’s data.
main()
{
struct stu
{
int num;
char *name;
char sex;
float score;
} *ps;
ps=(struct stu*)malloc(sizeof(struct stu));
ps->num=102;
ps->name="Zhang ping";
ps->sex='M';
ps->score=62.5;
printf("Number=%d\nName=%s\n",ps->num,ps->name);
printf("Sex=%c\nScore=%f\n",ps->sex,ps->score);
free(ps);
}
Copy the codeIn this case, the structure STu is defined, and the pointer variable ps of type STU is defined. Then a large stU memory area is allocated, and the first address is given to PS, so that PS points to the area. Ps as a pointer variable pointing to the structure to assign values to each member, and printf output the value of each member. Finally, use the free function to free the memory space pointed by ps. The whole program includes three steps of applying for memory space, using memory space and releasing memory space, realizing the dynamic allocation of storage space. The linked list concept in example 7.9 uses the dynamic allocation method to allocate memory space for a structure. Each allocation of space can be used to store a student’s data, we can call a node. The number of students is the number of blocks of memory that should be allocated, that is, the number of nodes to be built. Of course you can do the same with an array of structures, but if you don’t know exactly how many students there are in advance, you can’t determine the size of the array. And when a student fails a grade or drops out of school, the space taken up by the element cannot be released from the array. Dynamic storage can be used to solve these problems. If there is a student, a node is assigned, and there is no need to determine the exact number of students in advance. If a student drops out, the node can be deleted and the storage space occupied by the node can be released. This saves valuable memory resources. Arrays, on the other hand, must occupy a contiguously large area of memory. When using dynamic allocation, each node can be discontinuous (within the node is continuous). The connection between nodes can be realized using Pointers. The node structure defines a member item that holds the first address of the next node. The member that holds the address is often called the pointer field. We can store the first address of the second node in the pointer domain of the first node, and store the first address of the third node in the pointer domain of the second node, and so on until the last node. The pointer field of the last node can be assigned to 0 because no subsequent nodes are connected.
Such a connection is called a “linked list” in the data structure.
The 0th node is called the head node, it holds the first node’s first address, it has no data, it’s just a pointer variable. Each node below is divided into two fields. One is the data field, which stores all kinds of actual data, such as student number NUM, name, sex and score. The other field is the pointer field, which holds the first address of the next node. Each node in the list is of the same type of structure.
For example, a node containing student numbers and grades should have the following structure:
struct stu
{ int num;
int score;
struct stu *next;
}
Copy the codeThe first two member items make up the data field, and the second member item next makes up the pointer field, which is a pointer variable to a structure of type STU.
3.3 Basic Operations of linked Lists
Basic operations of the linked list The main operations of the list are as follows:
1.Establish a linked list;2.Structure search and output;3.Insert a node;4.Delete a node;Copy the codeExamples illustrate these operations.
Create a three-node linked list to store student data. For simplicity, let’s assume that there are only two items in the student data structure: student number and age.
3.4 Can write a linked list of the function CREAT
The procedure is as follows:
#define NULL 0
#define TYPE struct stu
#define LEN sizeof (struct stu)
struct stu
{
int num;
int age;
struct stu *next;
};
TYPE *creat(int n)
{
struct stu *head, *pf, *pb;
int i;
for(i=0; i<n; i++) { pb=(TYPE*)malloc(LEN);
printf("input Number and Age\n");
scanf("%d%d",&pb->num,&pb->age);
if(i==0)
pf=head=pb;
else pf->next=pb;
pb->next=NULL;
pf=pb;
}
return(head);
}
Copy the codeThe three symbolic constants are defined by macros outside the function. The main purpose of using TYPE for struct stu and LEN for sizeof(struct stu) is to reduce writing and make reading easier in the following programs: The structure STU is defined as an external type that can be used by various functions in the program.
The creat function is used to create a list of n nodes. It is a pointer function that returns a pointer to the stU structure. Three pointer variables to stU structures are defined in the creat function. Head is the head pointer and PF is the pointer variable pointing to the previous node of two adjacent nodes. Pb is the pointer variable of the latter node. In the for statement, the malloc function is used to establish the space with the same length as stu as a node, and the first address is given to pb. And then input the node data. If the current node is the first node (I ==0), then the pb value (the node pointer) is assigned to head and pf. If it is not the first node, then the pb value is assigned to the pointer domain member next of the node to which PF refers. Pb refers to the node as the current last node, and its pointer field is NULL. The PB value is then assigned to PF to prepare for the next loop. The parameter n of creat, which represents the number of nodes in the list, is used as the number of loops for the statement.
Write a function to find the node by student number in a linked list.
TYPE * search (TYPE *head,int n)
{
TYPE *p;
int i;
p=head;
while(p->num! =n && p->next! =NULL)
p=p->next; /* Move the node back */
if (p->num==n) return (p);
if(p->num! =n&& p->next==NULL)
printf ("Node %d has not been found! \n",n
}
Copy the codeThe symbolic constant TYPE used in this function is the same as the macro definition in example 7.10, which is equal to structstu. The function takes two parameters. Head is a pointer to a list, and n is the student number to look for. If num is not equal to n and the pointer field is not NULL(not the last node), then move one node back and continue the loop. Returns a pointer to the node if it is found. If the node is not found at the end of the loop, the “not found” message is displayed.
3.5 Deleting a Node from the Linked List
Writes a function that removes a node from a linked list. There are two ways to delete a node:
-
The node to be deleted is the first node. In this case, just make the head point to the second node. The head = pb – > next.
-
The deleted node is not the first node, in which case the node before the deleted node points to the node after the deleted node. The pf – > next = pb – > next.
Function programming is as follows:
TYPE * delete(TYPE * head,int num)
{
TYPE *pf,*pb;
if(head==NULL) /* If the table is empty, a message */ is displayed
{ printf("\nempty list! \n");
gotoend; } pb=head;while(pb->num! =num && pb->next! =NULL)
/* If the node is not to be deleted, and it is not the last node, the loop continues */{pf=pb; pb=pb->next; }/*pf points to the current node, pb points to the next node */
if(pb->num==num)
{if(pb==head) head=pb->next;
/* If the node is the first node to be deleted, make head point to the second node; otherwise, make pf point to the next node */
else pf->next=pb->next;
free(pb);
printf("The node is deleted\n"); }else
printf("The node not been foud! \n");
end:
return head;
}
Copy the codeThe function takes two parameters. Head is a pointer to the first node in the list, and num deletes the student number of the node. First, judge whether the list is empty. If the list is empty, there can be no deleted nodes. If not null, the pb pointer points to the first node in the list. We go into the while statement and look for the deleted nodes one by one. If so, make head point to the second node (i.e. delete the first node from the chain); otherwise, make the previous node of the deleted node (pf) point to the next node of the deleted node (pointer field of the deleted node). If no node to delete is found at the end of the loop, a “last found” prompt is output. Finally, return the head value.
3.6 Insert a node at a specified position in the list
Write a function to insert a node at a specified position in the list. The insertion of a node at a specified position in a linked list requires that the list itself has been sorted according to some law. For example, in the student data list, the student number order is required to insert a node. Set the pointer to the inserted node to PI. It can be inserted in three different situations.
-
The original table is empty, so just make the head point to the inserted node.
-
The inserted node has the smallest value and should be inserted before the first node. In this case, the head points to the inserted node, and the pointer field of the inserted node points to the original first node. Namely: PI – > next = pb; head=pi;
-
In this case, the pointer field of the node before the insertion point to the inserted node, and the pointer field of the inserted node points to the node after the insertion point. To: PI – > next = pb; Pf – > next = PI;
-
Insert at the end of the table. In this case, the original end node pointer field points to the inserted node, and the inserted node pointer field is set to NULL. That is:
pb->next=pi;
pi->next=NULL; TYPE *insert(TYPE * head,TYPE *pi)
{
TYPE *pf,*pb;
pb=head;
if(head==NULL) /* Insert null table */
(head=pi;
pi->next=NULL; }else
{
while((pi->num>pb->num)&&(pb->next! =NULL))
{pf=pb;
pb=pb->next; }/* Find the insert position */
if(pi->num<=pb->num)
{if(head==pb)head=pi;/* Insert */ before the first node
else pf->next=pi;/* Insert */ in other positions
pi->next=pb; }
else
{pb->next=pi;
pi->next=NULL; }/* Insert */ at the end of the table
}
returnhead; }Copy the codeThis function takes two pointer variables, head to the list and PI to the inserted node. The function first determines whether the list is empty, which makes the head point to the inserted node. If the table is not empty, the while statement is used to loop through the insertion position. If so, make the head point to the inserted node. The pointer field of the inserted node points to the original first node. Otherwise, insert the node at another position. This function returns a pointer to the head of a linked list. When you insert before the first node, the new node becomes the first node in the list, so the value of head has changed, so you need to return the pointer to the calling function.
Put together the functions that create lists, delete nodes, and insert nodes, create a function that outputs all nodes, and then call them using main. In this example, the print function is used to print the data field values of each node in the list. The initial value of the head parameter points to the first node in the list. In a while statement, after the node value is printed, the head value is changed to point to the next node. If we keep the head pointer, we should set another pointer variable, assign the head value to it, and use it instead of head. In the main function, n is the number of established nodes and num is the data field value of the node to be deleted. Head is the head pointer to the linked list, and pnum is the pointer to the node to be inserted.
The meanings of the lines in main are:
In the sixth line, enter the number of nodes in the linked list. In line 7, call creat to create the list and return the head pointer to head. In line 8, call the print function to output the list. In the tenth line, enter the student number of the node to be deleted. Line 11deleteFunction to remove a node; In line 12, call the print function to output the list. The malloc function on line 14 allocates a node's memory space and assigns its address to pnum. In line 15, enter the data field value of the node to be inserted. Insert (pnum) insert (pnum); On line 17, call print again to print the list.Copy the code#define NULL 0
#define TYPE struct stu
#define LEN sizeof(struct stu)
struct stu
{
int num;
int age;
struct stu *next;
};
TYPE * creat(int n)
{
struct stu *head, *pf, *pb;
int i;
for(i=0; i<n; i++) { pb=(TYPE *)malloc(LEN);
printf("input Number and Age\n");
scanf("%d%d",&pb->num,&pb->age);
if(i==0)
pf=head=pb;
else pf->next=pb;
pb->next=NULL;
pf=pb;
}
return(head);
}
TYPE * delete(TYPE * head,int num)
{
TYPE *pf,*pb;
if(head==NULL)
{ printf("\nempty list! \n");
gotoend; } pb=head;while(pb->num! =num && pb->next! =NULL) {pf=pb; pb=pb->next; }if(pb->num==num)
{ if(pb==head) head=pb->next;
else pf->next=pb->next;
printf("The node is deleted\n"); }
else
free(pb);
printf("The node not been found! \n");
end:
return head;
}
TYPE * insert(TYPE * head,TYPE * pi)
{
TYPE *pb ,*pf;
pb=head;
if(head==NULL)
{ head=pi;
pi->next=NULL; }
else
{
while((pi->num>pb->num)&&(pb->next! =NULL))
{ pf=pb;
pb=pb->next; }
if(pi->num<=pb->num)
{ if(head==pb) head=pi;
else pf->next=pi;
pi->next=pb; }
else
{ pb->next=pi;
pi->next=NULL; }}return head;
}
void print(TYPE * head)
{
printf("Number\t\tAge\n");
while(head! =NULL)
{
printf("%d\t\t%d\n",head->num,head->age); head=head->next; }}main()
{
TYPE * head,*pnum;
int n,num;
printf("input number of node: ");
scanf("%d",&n);
head=creat(n);
print(head);
printf("Input the deleted number: ");
scanf("%d",&num);
head=delete(head,num);
print(head);
printf("Input the inserted number and age: ");
pnum=(TYPE *)malloc(LEN);
scanf("%d%d",&pnum->num,&pnum->age);
head=insert(head,pnum);
print(head);
}
Copy the codeFrom the running result, the linked list of three nodes is first established and its value is output. Then delete node 103, leaving node 105,108; Then input the data of node no. 106. After insertion, the nodes in the linked list are 105,106,108. Federation “federation” is also a construct type of data structure. A variety of different data types can be defined within a union, and any type of data defined by the union can be loaded into a variable that is specified as the type of the union. This is not possible with any of the previous data types. For example, variables defined as integers can only be loaded with integer data, and variables defined as real can only be assigned with real data.
There are many examples of this in practical problems. For example, fill in the following form among teachers and students in a school: Surname, first name, age, Occupation Unit The “occupation” category can be divided into “teacher” and “student”. For “unit”, students should fill in the class number, teachers should fill in a department a teaching and research office. Classes can be expressed as integer quantities, while teaching and research sections can only be expressed as characters. To fill the variable “unit” with both types of data, you must define “unit” as a union of the two types: integer and character array.
“Union” and “structure” have some similarities. But there is a fundamental difference. In a structure, each member has its own memory space. The total length of a structure variable is the sum of the length of each member. In a union, members share a memory space, and the length of a union variable is equal to the length of the longest member. It should be noted that the so-called sharing here does not mean loading multiple members into a union variable at the same time, but that the union variable can be assigned to any member value, but only one value at a time, the new value to flush out the old value. As in the “unit” variable described earlier, if defined as a union that can be loaded into “class” or “teaching and Research section,” it is allowed to assign integer values (class) or strings (teaching and research section). You can either give it an integer value or a string, not both. Definition of union Types and Description of Union Variables A union type must be defined before a variable can be specified as that union type.
4. Consortium – Definition of Commons
The general form of defining a union type is:
unionThe joint name {Members of the table};Copy the codeA member table contains several members. The general form of a member is as follows: Type specifier Member Name The name of a member must comply with the requirements of the identifier. Such as:
union perdata
{
int class;
char office[10];
};
Copy the codeDefines a union type named perdata that contains two members, one of which is an integer and the member name is class. The other is an array of characters named Office. After the union definition, the union variable can be described. The variable that is described as the perdata type can be stored as the integer class or the character array Office.
5. Commonwealth – Description of shared body variables
The description of the union variable is the same as that of the structure variable, and there are also three forms. That is, first define, then explain; Definitions are both descriptive and direct. The following uses the perdata type as an example:
union perdata
{
int class;
char officae[10];
};
union perdata a.b; /* Note that a and b are of perdata type */
Copy the codeOr it can also be stated as:
union perdata
{ int class;
char office[10]; }a,b; Or directly stated as:union
{ int class;
char office[10]; }a,b
Copy the codeThe variables A and B are of type perdata. The length of variables a and b should be equal to the longest member of perdata, that is, equal to the length of the office array, a total of 10 bytes. As you can see from the figure, the variables A and b use only two bytes when they are assigned an integer value, but 10 bytes when they are assigned a character array.
6. Assignment and use of union variables
Assignments to union variables can only be made to members of the variables. Members of a union variable are represented as: the union variable name. For example, after a is specified as a variable of type perdata, a.classa. Office does not allow assignment or other operations to be performed using only the union variable name. Initializing assignments to union variables are also disallowed; assignments can only be done in a program. Again, a union variable can only be assigned one member value at a time. In other words, the value of a joint variable is the value of one of the members of the joint variable.
There is a common table for teachers and students. Teacher data has four items: name, age, occupation and teaching and research section. Students have name, age, occupation and class.
The program inputs personnel data and outputs them in a table.
main()
{
struct
{
char name[10];
int age;
char job;
union
{
int class;
char office[10];
} depa;
}body[2];
int n,i;
for(i=0; i<2; i++) {printf("input name,age,job and department\n");
scanf("%s %d %c",body[i].name,&body[i].age,&body[i].job);
if(body[i].job=='s')
scanf("%d",&body[i].depa.class);
else
scanf("%s",body[i].depa.office);
}
printf("name\tage job class/office\n");
for(i=0; i<2; i++) {if(body[i].job=='s')
printf("%s\t%3d %3c %d\n",body[i].name,body[i].age
,body[i].job,body[i].depa.class);
else
printf("%s\t%3d %3c %s\n",body[i].name,body[i].age, body[i].job,body[i].depa.office); }}Copy the codeThis example program uses an array of four structures, body, to store staff data. The member item DEPa is a union type, which is composed of two members, one is an integer class, the other is a character array office. In the first for statement of the program, enter the data of the personnel, first enter the first three members of the structure name,age and job, and then identify the job member item, such as “s”, enter depA ·class (assign class number to students), otherwise enter DEPA · Office (assign group name to teachers).
When using scanf statements, it is important to note that the “&” operator cannot be added before an array member, whether a structure member or a union member. For example, the body[I].name in line 18 is an array type, and the body[I].depa. Office in line 22 is an array type, so you cannot add the “&” operator between the two items. The second for statement in the program prints the values of each member item:
7. Chapter summary
-
Structure and union are two kinds of constructing type data and are important means for users to define new data types. Structure and union have a lot in common. They both consist of members. Members can have different data types. Members are represented the same way. Can be used as a variable description in three ways.
-
In a structure, each member occupies its own memory space and they exist simultaneously. The total length of a structure variable is equal to the sum of the lengths of all its members. In a union, all members cannot occupy its memory space at the same time. They cannot exist at the same time. The length of the union variable is equal to the length of the longest member.
-
“.” Is the member operator, which can represent member items. Members can also be represented by the “->” operator.
-
A structure variable can be used as a function argument, and a function can return a pointer variable to a structure. A union variable cannot be used as a function argument, and a function cannot return a pointer variable to the union. But you can use Pointers to union variables, or you can use an associative array.
-
Structure definitions allow nesting, and unions can be used as members in structures to form nesting of structures and unions.
-
Linked list is an important data structure, which facilitates dynamic storage allocation. This chapter is a one-way linked list, can also be composed of two-way linked list, circular linked list, etc.