Today, I told a question, and this question is the problem that the same color beads I have said in two-way linked lists. So it can be seen again that our programmer's test is inseparable from the list and pointer. The pointer is of course the most important, because the linked list is the pointer, must be familiar with the pointer. Let's see you:
Read the following programs and C code, write the words of __ (n) __written in the corresponding column of the answer sheet. [Program Description] A bead having different colors numbered No. 0 to N-1 (the color of the bead color is represented by the n-granulus color by the alphabetic color, indicated by the input character string. In the ring, the two-piece beads are broken, and the continuously colored beads are removed from the breakpoint, and the other side of the breakpoint will take the resection of the colored beads in the counterclockwise direction. The sum is the number of grains of the beads for the breakpoint. Moving breakpoints, the number of beads that can be taken is endless. This program finds that the number of beads and breakpoints that can be taken away. The string is stored in a two-way linked list. For example, the string of 10-capped colors called 0-9 is "aaabbbadcc", the corresponding linked list is: Figure 20 days Figure 2 If there is a breakpoint between the 2nd and No. 3 beads, take 6 capsules Beads, and the number of beads taken away.
[Program] #include Node * building (char * s) / * Generate two-way circular list * / {node * p = null, * q; while (* s) {q = (node *) malloc (sizeof (node)); Q -> ch = * S ; if (p = null) P = q -> fpt = q -> bt = q; Else {P -> BPT -> fpt = q; q -> fpt = p; q -> bpt = __ ( 1) __; __ (2) __;}} return (})} This also illustrates that the BPT refers to a node, and the FPT is a node. Ok, continue to see the program if (p = null) p = q -> fpt = q -> bt = q; this is easy to determine that the first is the first tie point when it is specifically used to handle the new list, initialize the knot Point q, make two front and rear pointers point to yourself. P -> BPT -> fpt = q; q -> fpt = p; q -> bpt = p-> bpt; p-> bpt = q; here is given first, because this question is really difficult, so directly Talk about how he established a two-way loop linked list, as for I can understand it really hard to guarantee. Here I am here to emphasize that I am a beginner, but I will do my best to learn with you. One sentence is finished, P-> btp-> fpt = Q; and Q-BPT = P-> BPT; these two sentences are the skills of establishing a two-way loop linked list, so we have to understand these two sentences. P-> btp-> fpt = q; Demolition this sentence to each other, p-> BTP is the node pointed to by the front pointer representing the two-way linked list, pay attention to the bidirectional linked list The front pointer is always the end of the final node, so on this basis, add-> ftp, p-> btp-> fpt, you can get the node points to the last node. , Then link the newly established node Q, P-> btp-> fpt = q; it is a link to a new node. Q-> ftp = p; there is nothing special here, just directly, the pointer points to the head knot, so that the head node and the tail joint phase chain. Continue to see the third line Q -> BPT = P-> BPT; here there is also a new knot point pointer to the tail joint point of the old bidirectional linked list. (This is also the same characteristic, the node pointed to by the head knot "is the fourth sentence is to point the first pointer to the newly inserted new node (ie the new two-way linked point" to point to the newly inserted nodes (ie the new two-way linked point "to point to the newly inserted nodes (ie the new two-way linked point" to point to the newly inserted nodes (ie the new two-way linked point "to point to the newly inserted nodes (ie the new two-way linked point) to point the header node pointer (ie the new two-way linked point" ), Then constitute the two-way linked list again. I hope everyone can understand what I wrote. If it is really not Taiming, please contact me with E-mail, I will try my best, because we all work hard for the test. I believe our efforts will not be quaint, work hard ~! Struggle ~~~!
