Shulou(Shulou.com)06/01 Report--

With the end of the semester coming, the course of C language programming is coming to an end. After the first two times of teaching, we also have a deep understanding of the C language, and the content of learning is also constantly deepening. This time we learned the most widely used and most difficult knowledge in C language programming-the application of linked lists and pointers.

The application of pointers and linked lists is directly related to the last management system, and the management system without adding linked lists and pointers can not find them accurately. Data storage is also inconvenient. So pointers and linked lists can point directly to the data address you need, making the program more perfect. This time I made use of the pointer application to create a program to manage employee salary and other information.

§1 pointer variable to structural volume variable

A pointer variable pointing to a structure variable is defined in the same form as a general pointer variable, except that its pointing type is defined as a structure type. For example:

Struct person

{charname [20]

Char sex

Int age

Float height

}

Struct person * p

Then the pointer variable p, which can point to a structure variable of type struct person.

After you point a pointer variable to a structure variable, you can use the pointer variable to the structure to refer to the member, such as:

(* pointer variable name). Member name

The above forms are often written as follows:

Pointer variable name-> member name

Where-> is the pointing operator, which is made up of symbols "-" and ">". The priority of the pointing operator is the same as that of the member operator, which is also the highest level.

§2 pointer variables to the structure array

Pointer variables can point to arrays of basic types such as integers, characters, floats, and so on. Similarly, pointer variables can point to arrays of structure types.

Function: use pointer variables that point to an array of structures.

# include

Void main ()

{struct person

{char name [20]

Char sex

Int age

Float height

} per [3] = {{"Li Ping",'M', 20175}

{"Wang Ling",'F', 19162.5}

{"Zhao Hui",'M', 20178}}

Struct person * p

For (pname, p-> sex, p-> age, p-> height)

}

§3 the concept of linked lists

Linked list is the most basic form of dynamic data structure, and its size can be dynamically changed according to the needs to achieve the rational use of storage space.

The linked list has a "head pointer" variable that points to the first element of the linked list. Each element in the linked list is called a node, and the node contains two parts: one is the actual data information, and the other is the pointer to the next node. The last element of the linked list is set to "NULL" (empty address) to mark the end of the linked list.

A node can be described by a structure type. The structure contains several members that represent the data information of the node. In addition, there must be a member that is a pointer consistent with the node type to point to subsequent nodes. For example, the node of a linked list can be defined as the following structure type:

Struct node

{int data1

Float data2

Struct node * next

}

Where the member next is a pointer variable to the node, which points to the struct node structure type data where the next is located.

The library function of C system provides the function of dynamically applying and releasing memory storage unit.

(1) malloc function

The prototype of the malloc function is:

Void * malloc (unsigned int size)

The function is to allocate a contiguous space of size bytes in the dynamic storage area. The return value of the function is a pointer, and its value is the starting address of the allocated storage area. If there is not enough storage space allocated, a value of 0 (marked as NULL) is returned.

(2) calloc function

The prototype of the calloc function is:

Void * calloc (unsigned int n unsigned int size)

The function is to allocate n size bytes of contiguous space in the dynamic storage area and automatically set the storage space to an initial value of 0. The return value of the function is a pointer, and its value is the starting address of the allocated storage area. If the allocation is not successful, a value of 0 is returned.

(3) free function

The prototype of the free function is:

Void free (void * ptr)

The function is to free up the storage space pointed to by ptr. The value of ptr must be the address returned by the malloc or calloc function. This function has no return value.

§5 related operations of linked lists

First, establish a linked list

The establishment of a linked list is a process of gradually increasing the number of linked list nodes from scratch, that is, inputting node data and establishing the relationship between front and back links.

The following is the function creat () that builds the linked list:

Struct node * create ()

{struct node * head, * tail, * p

Int x

Head=tail=NULL

Printf ("\ nPlease enter an integer:")

Scanf (& d, & x)

While (Xerox 0)

{p = (struct node *) malloc (sizeof (struct node))

P-> data=x

P-> next=NULL

If (head= = NULL)

Head=tail=p

Else

{tail- > next=p

Tail=p

}

Printf ("Please enter an integer:")

Scanf (& d, & x)

}

Return (head)

}

Second, insert nodes in the linked list

The operation of inserting a node has the following situations:

(1) A linked list is an empty linked list, and the inserted node is the first node of the linked list.

(2) the linked list is not empty, and the node is inserted before the first node of the linked list, so that the inserted node becomes the first node of the linked list.

(3) the linked list is not empty, and the node is inserted at the end of the linked list, so that the inserted node becomes the last node of the linked list.

(4) the linked list is not empty, and the node is inserted after a node in the middle of the linked list.

The following function insert (struct node * head, int value) is used to insert data value in the head linked list of known header nodes in the order from smallest to largest.

Struct node * insert (struct node * head, intvalue)

{

Struct node * new, * p, * Q

New= (struct node *) malloc (sizeof (struct node))

New- > data=value

P=head

If (head= = NULL) / * linked list is empty linked list * /

{head=new

New- > next=NULL

}

Else

{while ((p-> next! = NULL) & & (p-> datanext;})

If (p-> data > = value)

{if (head= = p) / * linked list is not empty, inserted in front of the first node * /

{new- > next=head

Head=new

}

Else / * the linked list is not empty, insert it in the middle of the linked list * /

{Q-> next=new

New- > next=p

}

}

Else / * the linked list is not empty, inserted at the end of the linked list * /

{p-> next=new

New- > next=NULL

}

}

Return (head)

}

Delete nodes in the linked list

Deleting a node from the linked list refers to separating the node from the linked list, that is, changing the link relationship of the linked list. There are two ways to deal with the node deleted from the linked list: one is to call the function free () to release the storage space occupied by the node and delete it from memory; the other is to insert the node into other linked lists to wait for processing.

The following function delete (struct node * head, int value) is used to find a data value in the head linked list of known header nodes and delete it from the linked list.

Struct node * delete (struct node * head, intvalue)

{struct node * p, * Q

P=head

If (head= = NULL) / * linked list is empty linked list * /

{printf ("this is an empty linked list!\ n"); return (head);}

While ((p-> next! = NULL) & & (p-> data deleted value)) / * find the location of the deleted node * /

{qroomp; pairp-> next;}

If (value= = p-> data)

{if (head= = p) head=p- > next; / * Delete the first node of the linked list * /

Else Q-> next=p- > next; / * Delete linked list node * /

Free (p)

}

Else

Printf ("this linked list does not have data% d!\ n", value); / * there is no such node in the linked list * /

Return (head)

}

source code

# include

# include

# include

# include

# define N 3

Typedef struct node

{

Char name [20]

Struct node * link

} stud

Stud * creat (int n) / * function to create a single linked list * /

{

Stud * pjime / hjorn / s

Int i

If ((h = (stud *) malloc (sizeof (stud) = = NULL)

{

Printf ("memory space cannot be allocated!")

Exit (0)

}

H-> name [0] ='\ 0'

H-> link=NULL

Pairh

For (iS0th ilinksand)

Printf ("Please enter the name of the% d person:", iTun1)

Scanf ("% s", s-> name)

S-> link=NULL

Pairs

}

Return (h)

}

Stud * search (stud * hmaine char * x) / * find function * /

{

Stud * p

Char * y

Pairh-> link

While (paired null)

{

Yroomp-> name

If (strcmp (yperimex) = = 0)

Return (p)

Else pendant-> link

}

If (p==NULL)

Printf ("data not found!")

}

Stud * search3 (stud * hmenchar * x)

/ * another lookup function that returns the pointer to the direct precursor node of the previous lookup function

H is the header pointer and x is the pointer to the name to be found

In fact, the algorithm of this function is the same as the above search algorithm, except that there is an extra pointer s, and s always points to the direct precursor of the node pointed to by the pointer p.

The result returns s, which is the previous node of the node to be found * /

{

Stud * pjime

Char * y

Pairh-> link

Sphinch

While (paired null)

{

Yroomp-> name

If (strcmp (yperimex) = = 0)

Return (s)

Else

{

Pairp-> link

Swatches-> link

}

}

If (p==NULL)

Printf ("data not found!")

}

Void insert (stud * p) / * insert function, insert * / after pointer p

{

Char stuname [20]

Stud * s; / * pointer s is the * / that holds the address of the new node.

If ((s = (stud *) malloc (sizeof (stud) = = NULL)

{

Printf ("memory space cannot be allocated!")

Exit (0)

}

Printf ("Please enter the name of the person you want to insert:")

Scanf ("% s", stuname)

Strcpy (s-> name,stuname); / * copy the array elements pointed to by the pointer stuname to the data field of the new node * /

S-> link=p- > link; / * point the link domain of the new node to the successor node of the original p node * /

The link domain of the p-> link=s; / * p node points to the new node * /

}

Void del (stud * x stud * y) / * delete function, where y is the pointer of the node to be deleted and x is the pointer of the previous node of the node to be deleted * /

{

Stud * s

Swiny

X-> link=y- > link

Free (s)

}

Void print (stud * h)

{

Stud * p

Pairh-> link

Printf ("data information is:\ n")

While (paired null)

{

Printf ("% s\ n", & * (p-> name))

Pairp-> link

}

}

Void quit ()

{

Exit (0)

}

Void menu (void)

{

System ("cls")

Printf ("\ t\ t\ t single linked list C language implementation example\ n")

Printf ("\ t\ t |-|\ n")

Printf ("\ t\ t | |\ n")

Printf ("\ t\ t | [1] create a new table |\ n")

Printf ("\ t\ t | [2] search data |\ n")

Printf ("\ t\ t | [3] insert data |\ n")

Printf ("\ t\ t | [4] Delete data |\ n")

Printf ("\ t\ t | [5] print data |\ n")

Printf ("\ t\ t | [6] exit |\ n")

Printf ("\ t\ t | |\ n")

Printf ("\ t\ t | if you have not created a new table, create it first! |\ n")

Printf ("\ t\ t | |\ n")

Printf ("\ t\ t |-|\ n")

Printf ("\ t\ t Please enter your options (1-6):")

}

Main ()

{

Int choose

Stud * head,*searchpoint,*forepoint

Char fullname [20]

While (1)

{

Menu ()

Scanf ("d", & choose)

Switch (choose)

{

Case 1:

Head=creat (N)

Break

Case 2:

Printf ("enter the name of the person you are looking for:")

Scanf ("% s", fullname)

Searchpoint=search (head,fullname)

Printf ("the name of the person you are looking for is:% s", * & searchpoint- > name)

Printf ("\ nPress enter to return to the main menu.")

Getchar (); getchar ()

Break

Case 3: printf ("enter who you want to insert after:")

Scanf ("% s", fullname)

Searchpoint=search (head,fullname)

Printf ("the name of the person you are looking for is:% s", * & searchpoint- > name)

Insert (searchpoint)

Print (head)

Printf ("\ nPress enter to return to the main menu.")

Getchar (); getchar ()

Break

Case 4:

Print (head)

Printf ("\ nenter the name of the person you want to delete:")

Scanf ("% s", fullname)

Searchpoint=search (head,fullname)

Forepoint=search3 (head,fullname)

Del (forepoint,searchpoint)

Break

Case 5:

Print (head)

Printf ("\ nPress enter to return to the main menu.")

Getchar (); getchar ()

Break

Case 6:quit ()

Break

Default:

Printf ("you typed illegal characters! press enter to return to the main menu.")

System ("cls")

Menu ()

Getchar ()

}

}

}

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.