Third Day Abstract Data Type ADT
Pre-definition: Abstract data Type Abstract Data Type is a data type (set of values and arithmetic combinations acting on it) only by interface access.
A Set of Data Values and Associated Operations That Are PRECISELY Specified Independent of Any Particular Implementation.
Mainly in this word Abstract. It allows this DATA TYPE to access data through an interface. Both the representation of the data and the operation of the implementation exist in the implementation, the user cannot see the implementation through the interface. Think about it, there is a little OO, it and the things like Class have such a common point (how can the package are one of the three important features of OO), according to my understanding, Class is an ADT, or it More advanced levels in the grammatical level.
The real ADT is more demanding, and our string is not counted. why? We can directly accept it and its address, no interfaces are in the middle. We can string str = "this is a string"; printf ("% c", str [1]); do not need to write a function instead of this operator: Printf ("% C", str.getchar (1)) Of course, we can customize a full ADT String.
Here below gives a familiar example: down the stack stack.
In fact, we said the stack of LIFO (Last In First Out), and the one of its corresponding we often calls its queue FIFO (First In First Out).
We assume that this abstract data type has several operations: initialization, stack, out of the stack, empty.
In Stack.h we define the following function: This code is written in stack.h
Void stack_init (int);
INT stack_empty ();
Void stack_push (item);
Item stack_pop ();
In the following, we can have many ways: you are fully defined or ready. Array, the list is also possible,
Give an array of implementations:
#include
#include "item.h"
#include "stack.h"
Static item * S;
Static int N;
Void StackInit (int MAXN)
{s = malloc (MAXN * SIZEOF (item)); n = 0;}
Int stackempty ()
{RETURN N == 0;}
Void StackPush (Item ITEM)
{S [N ] = item;}
Item stackpop ()
{Return S [- n];
Do I use other good? For example, the string? Is not good, the string is too narrow, the characters have been limited to it, not it is not good (not, just in efficiency and complexity).
It seems that an ADT is not complicated, defines the data and interfaces. The reality is that the logical relationship of this stack is not complicated, and ADT may be easy for very familiar things. In the face of a new problem, how we are fully designing it is a key.
Let's take a look at how to use this stack.
Inverse Poland This place has heard of the data structure. It is just a good time using a stack. Take a look at this suffix expression: 5 9 8 4 6 * * 7 *
We need to be humanized: The expression we are easy to understand is this: 5 * ((9 8) * (4 * 6) 7) This conversion process We need to use the stack to help us, read an inverse Polaum If the digital is pressed into the stack, if the operator, calculate the previous two POP POPs and the operator read, and then press the result into the stack. Is this a process, let's see how the code is implemented:
#include
#include
#include "item.h"
#include "stack.h"
Main (int Argc, char * argv [])
{char * a = argv [1]; int i, n = strlen (a);
Stackinit (n);
For (i = 0; i { IF (a [i] == ' ') StackPUSH (StackPop () stackpop ()); IF (a [i] == '*') StackPUSH (StackPop () * stackpop ()); IF ((A [i]> = '0') && (a [i] <= '9')) StackPush (0); While ((A [i]> = '0') && (a [i] <= '9'))) StackPUSH (10 * stackpop () (a [i ] - '0')); } Printf ("% d / n", stackPOP ()); } OK, it's seen for the sake of simplicity of subtraction and division, because these two calculations have no exchange rate, and write code may be complex, which is not conducive to us to understand the stack. Will use the ready-made ADT has not changed to hero, we also need to plan and achieve the ADT you want to get. Refer to the ADT that has been implemented above, we can draw the cat, and you will have a hand. Since we let's draw a FIFO. What is much trouble is, the stack is actually operating a memory address, it's here, ha, this is a room with only one door. The FIFO queue has front door and back door, the front door is behind. Two memory locations are required when achieving their data operations, which is slightly more complicated. How to do it yourself, then look at the code below. Void queinerinit (int); INT Queueempty (); Void queueput (item); Item queueget (); ----- #include #include "item.h" #include "queue.h" Typedef struct queuenode * link; Struct queuenode {item item; link next; Static Link Head, TAIL; LINK New (item item, link next) {link x = malloc (sizeof * x); X-> item = item; x-> next = next; Return X; } Void Queueinit (int MAXN) {head = null;} INT Queueempty () {Return Head == NULL;} QueuePut (item item) { IF (head == null) {head = (tail = new (item, head); return;} Tail-> Next = new (item, tail-> next); Tail = tail-> next; } Item queueget () {Item item = head-> item; LINK T = head-> next; Free (head); head = t; Return Item; }
