Related Blog Items

• C++ Tutorial Part 2 - Advanced
• C++ Basics - Tutorial
• C++ Advanced Tutorial - Lesson 11
• C++ Advanced Tutorial - Lesson 8
• C++ Advanced Tutorial - Lesson 3

Please refer Lesson 4..

5. DATA STRUCTURES
5.1 Data Structure
5.2 Linked List
5.3 Tree
5.4 Struct
5.5 Bitwise Operators
5.6 Example: Display a Number in Binary Form
5.7 Bit Field
5.8 Character Handling Library
5.9 String Conversion Methods
5.10 String Handling Library “string.h”
5.11 Error Message Method

5. DATA STRUCTURES

5.1 Data Structure

A collection of the same type of objects is called a data structure.

5.2 Linked List

If you want to maintain a collection of the same objects, you may first think of an array of that type of objects. But as we already know, the size of the array have to be decided before compiling. Then we may think of using dynamic memory allocation to create the array, so that we can decide the memory size at run time:

Test * array = new Test [size];

But still there is limitation: once the array is created, you can not vary the size, unless you delete the whole array and create a new one. You can’t expand or shrink the list dynamically.

In order to put a group of objects into a flexible data structure, you can use wrapper objects to wrap around the original objects, with some additional pointers pointing to each other. Through these pointers, all the wrapper objects can be linked together. Such a pointer-linked collection is called “linked list”.

The disadvantages of linked list is that you can not directly access one node with subscript like array. You have to find the first one, go through the list through the pointers, until you reach the one you want. The other thing to remember is: nodes in linked list are created dynamically. They are not as fast as automatic objects.

If in a data structure each of the nodes is only connected to one node downstream and one node upstream, such a structure is called a “linear linked list”.

There are “open-loop” lists, each has a start node and end node. The pointer of the end node is always set to 0 to mark the end. There are also “close-loop” lists, whose start node and end node are connected together forming a circular loop of nodes.

There are Singly-linked lists whose nodes only contain one pointer pointing to the downstream node. You can’t traverse upstream. There are also doubly-linked lists whose nodes each contains a pointer to both the upstream and downstream node. You can traverse on both directions.

Using pointers to link objects you can create lists as queues, which only removes a node from the front and adds a node to the back, or stacks, which only adds and removes nodes to and from the front, or any other types.

5.3 Tree

A tree is a structure whose nodes each connected to one upstream node and many down-stream nodes. A binary tree is a structure which is connected to one upstream and two downstream nodes. A tree has a root node.

5.4 Struct

A structure is a simplified class with all public members:

struct Card 
{
  char * face;
  char * suit;
};

Structure members are not necessarily stored in consecutive bytes of memory. If the word length of the computer is 2 bytes, and one data member is only one-byte long, there will be a one-byte hole between this member and the next member. Because the value stored in the hole is undefined, a structure can not be compared.

A structure is initialized the same way as an array:

Card c1 = {"Three", "Hearts"};

If the initialization list contains not enough initializers, the rest will be initialized to 0.

5.5 Bitwise Operators

Up to now data is regarded as a whole number without considering its bit status. Internally a number is represented by binary bits. C++ provides the following bitwise operators:

1)&: bitwise AND. One bit is 1 if the corresponding bits of the both operands are both 1.
2)|: bitwise inclusive OR. One bit is 1 if one of both corresponding bits of the two operands is/are 1.
3)^: bitwise exclusive OR. One bit is 1 if the corresponding bits of the two operands are different: one is 1 and one is 0
4)<<: left shift. Shifts the bits of the first operand left by the number of bits specified by the second operand; fill from right with 0. For example, 0001 << 2 will be 0100. Result will be undefined if the second operand is negative.
5)>>: right shift. Shifts the bits of the first operand right by the number of bits specified by the second operand; The way of filling the left is machine-dependent, some use 0 and some use the sign bit.
6)~: complement. All 0 bits are 1 and all 1 bits are 0. For example, ~0101 will be 1010.
7)Assignment operators: &=, |=, ^=, <<=, >>=. For example: a &= b means a = a & b, a >>= b means a = a >> b.

5.6 Example: Display a Number in Binary Form

void BinaryDisplay1(unsigned value)
{
  mask = 1 << 15;   // 1000000000000000
 
  for (int c = 1; c <= 16; c++)
  {
    // 1000000000000000 is regarded as true
    cout << (value & mask ? '1': '0'); 
 
    if(c % 8 == 0)
      cout << ' '; 
  }
 
  cout << endl; 
}

5.7 Bit Field

C++ provides the ability to specify the number of bits in which an unsigned or int member of a class or a structure (or a union) is stored. Such a member is called a bit filed member:

struct Card 
{
  unsigned face : 4;
  unsigned suit : 2;
  unsigned color: 1;
};

Therefore, three members are stored in one byte. The number of bits of one member is decided by the maximum number it will represent. For example, the number of faces of cards is 13, less than 16, so member “face” can be defined with four bits.

Bit field members are accessed the same way as normal members. But they can not have addresses, and “&” can not be used, because there is no unique address of each part of one word.

Unnamed bit field with a width is used as padding, nothing can be stored in these padding bits:

structure Example 
{
  unsigned a : 13;
  unsigned   : 3;
  unsigned b : 4;
};

Unnamed bit field with 0 width is used to align the next bit field with next word:

structure Example 
{
  unsigned a : 13;
  unsigned   : 0;
  unsigned b : 4;
};

Although bit fields save space, it consumes more machine time, because extra codes have to be generated to deal with them. This is one of the many examples of space-time trade off that occur in computer science.

5.8 Character Handling Library

Characters are often manipulated as integers. Header file of the character handling library is .

int isdigit(int c): returns true if c is a digit — ‘0′ to ‘9′.
int isxdigit(int c): returns true if c is a hex digit — ‘0′, ‘1′,…, ‘E’, ‘F’.
int isalpha(int c): returns true if c is a letter.
int isalnum(int c): returns true if c is a letter or a digit.
int islower(int c): returns true if c is a lower case
int isupper(int c): returns true if c is a upper case
int tolower(int c): if c is upper case then return c in lower case, otherwise return c unchanged
int toupper(int c): if c is lower case then return c in upper case, otherwise return c unchanged.
int isspace(int c): returns true if c is a whitespace character: newline(’\n’), space, form feed(’\f’), carriage return(’\r’), horizontal tab(’\t’), or vertical tab(’\v’).
int iscntrl(int c): returns true if c is a control character.
int ispunct(int c): returns true if c is a printing character other than a space, a digit or a letter.
int isprint(int c): returns true if c is a printing character including space.
int isgraph(int c): returns true if c is a printing character other than space.

5.9 String Conversion Methods

String conversion methods are in .

double atof(const char *): converts a numbered string to double. E.g.: if ptr = “23.85″, double 23.85 will be returned.
int atoi(const char *): converts a numbered string to integer. E.g.: if ptr = “2593″, integer 2593 will be returned.
long atol(const char *): converts a numbered string to long integer.

double strtod(const char *, char **): converts the double portion of string ptr1 to double, and locate the second pointer at the first remaining character in the first string. E.g.: if ptr1 = “1234.2ABCD”, double 1234.2 will be returned and second pointer will be “ABCD”.

long strtol(const char * ptr1, char ** ptr2, int base): converts the long int portion of string ptr1 to long integer, and locate pointer ptr2 at the first remaining character in ptr1. The long integer can be in any base: if base = 0, then it can be decimal, octal or hexadecimal; if base = 8, it is octal; if base = 10, it is decimal; if base = 16, it is hexadecimal. But the base can be any value from 2 to 36, limited only by the number of Latin letters A-Z. Using NULL for the second argument will cause the remaining portion be ignored.

unsigned long strtoul(const char * ptr1, char ** ptr2, int base): only difference with method strtol is the integer is unsigned.

5.10 String Handling Library “string.h”

=>Searching character in string

char * strchr(const char * s, int c): locate the first c in string s, or return NULL if not found.
size_t strcspn(const char * s1, const char * s2): return the length of the initial segment of s1 which consists of characters not included in s2.
size_t strspn(const char * s1, const char * s2): return the length of the initial segment of string s1 which consists only characters in s2.
char * strpbrk(const char * s1, const char * s2): locate the first occurrence in s1 of any character contained in s2 or NULL if not found.
char * strrchr(const char * s, int c): locate the last occurrence of c in s or NULL if not found.
char * strstr(const char * s1, const char * s2): locate the first occurrence in s1 of s2 or NULL if not found.

=>Memory manipulating methods

The basic unit of memory is byte, and a byte can be regarded as a character. The following methods manipulate memory buffers in characters. The pointer parameters in these methods are declared “void *”. Because pointers of any type can be directly assigned to a pointer of type “void *”, therefore methods can receive pointers of any type.

void * memcpy(void * s1, const void * s2, size_t n)
Copies n characters from buffer s2 to s1, and return a pointer to the resulting buffer.

void * memmove(void * s1, const void * s2, size_t n)
The same as memcpy, but the characters are first copied from s2 into a temporary location, then copied to s1. This allows to copy part of one object and overlap with itself:

int main()
{
   char x[] = "123 456 789";
   cout << (char *)memmove(x, x+4, 3);
}

then x will become “456 456 789″.

int  memcmp(const void * s1, const void s2, size_t n)
//Compares the first n characters of object s1 and s2, 
//and returns 0, <0, or >0.

void *  memchr(const void * s, int c, size_t n)
//Locates the first occurrence of c in the first n 
//characters of object s, or return 0 if not found.

void *  memset(void * s, int c, size_t n)
//Set the first n characters of object s to character c, 
//and return a pointer to the result

int main()
{
   char x[] = "AAAA";
   cout << (char *)memset(x, 'B', 2);
}

result will be “BBAA”.

5.11 Error Message Method

char * strerror(int code);

Error messages have their codes. This method maps the error code into a full text string in a system dependent way, and returns a pointer to that mapped message.

Popularity: 24%

You need to log on to convert this article into PDF

Related Blog Items

• C++ Tutorial Part 2 - Advanced
• C++ Basics - Tutorial
• C++ Advanced Tutorial - Lesson 11
• C++ Advanced Tutorial - Lesson 8
• C++ Advanced Tutorial - Lesson 3

This entry was written by Silan Liu and posted on December 7, 2007 at 8:58 pm and filed under Tutorials. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Trackbacks are closed, but you can post a comment.