软件：Course Project 1 (optional)

[ghostbody]

Project1：

For a deep understand for c pointers and functions, we will take a project.

An introduction to List

In computer science, a list or sequence is an abstract data type that represents an ordered sequence of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream.[1]:§3.5 Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.

A singly linked list structure, implementing a list with 3 integer elements.
The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.

Many programming languages provide support for list data types, and have special syntax and semantics for lists and list operations. A list can often be constructed by writing the items in sequence, separated by commas, semicolons, or spaces, within a pair of delimiters such as parentheses '()', brackets '[]', braces '{}', or angle brackets '<>'. Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic "list" class, and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications. In some contexts, such as in Lisp programming, the term list may refer specifically to a linked list rather than an array.

In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.[2]

From wikipedia

Our course project is about List.
List is a data type that defined by programmers or the language. The best advantage of the list(linear list) is that it can store variable length of data. Usually, we use struct in c language with a member variable as a 'next' pointer points to the next element of the list. And we will have some functions for the list operations. These operations is the core of C programming language including the usage of pointers, various data types and also some basic knowledge of a computer.

Detail Introduction: link

Try your best to finish the hardest project.

Basic Knowledge(15 pts)

answer the questions in deep thinking part in your report

1. Memory distribution map for a runtime program (very important for your 4-year study)

From Professor Wan Hai's courseWare

This is an overview for a program when it's loaded into the memory of the computer. There are totally 4 area for it, Code area, Static area, Heap and stack.
Code area: This area is used to store program codes(instructions for cpu to execute)
Static area: This area is for the ralatively ‘static’ variables. Global variables, static local variables, static global variables are allocated in the static storage area.
Heap: This area is management by the operating system and it's shared by other programs. You can get dynamic memory allocations in this area. This is the area we need to use in list
Stack: The stack is a area of memory that allocated by the compile. All variables declared in stack.
Notice that stack and heap in operating system are totally different in data structure
For example:

#include <malloc.h>
int main() {
   int a;  // allocated in stack
   int * b = (int *)malloc(sizeof(int));  // allocated in heap
   free(b);
   return;
}

Notice that we have a operation before the program end. free(b). Because we use the memory in the heap which means that these memory should be managed by the programmer. Even though the memory will be free by a mordern operating system, we should prevent memory lost (memory leak).
For example:

int main() {
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area1
   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area2
   return;
}

The example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.

2. Malloc() to get memory from heap

The two examples above show how to get memory in heap. In fact, we it's a serial of functions.
C language with the memory of the functions are mainly calloc, alloca, malloc, free, realloc and so on.
<1> alloca is the application of the stack to the memory, so there is no need to release.
<2> malloc allocates memory is located in the heap, and there is no memory of the contents of the initial memory, so after the basic malloc, call the function memset to initialize this part of the memory space.
<3> calloc will initialize this part of the memory, set to 0
<4> realloc is the size of the memory of the malloc application.
<5> The heap needs to be released by the function free.

Notice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.

int main() {
   int * a = malloc(sizeof(int));

   // code using a

   free(a);
}

3. List operations

The operations about list are appending, deleting, modifying, querying.

we use this simple list again:

1. If delete the second node:

node* save = head->next;
head->next = head->next->next;
free(save);

2.If append a node at the end of the list

node* last = head;
while(last->next != NULL) {
    last = last->next;
}

last->next = (node*)malloc(sizeof(node));
last->next->data = data;
last->next->next = NULL;

1. Traversal
   node * temp = head;
   while(temp != NULL) {
   Traversal(temp);
   temp = temp->next;
   }

Deep Thinking

1. Why use a list instead of an array? What's the advantages of them and disadvantages for them respectively?
2.See the following function:

static void myFunction() { int a; }

(1) Which area in memory does the function store? And which dose the variable int a?
(2) What's the advantages of using static functions?

3. See the following program which is attempt to allocate a dynamic array.

#include <malloc.h>

int main() {
    char ** strs;
    int n ,m;
    int i;

    scanf("%d%d", &n, &m);

    strs = (char **)malloc(sizeof(char *) * n);

    for(i = 0; i < n; i++) {
        strs[i] = (char *)malloc(sizeof(char) * m);
    }


   // code for the 2d array
   // free operations omited
    return 0;
}

Can we create an 2D array in the heap using this way? Give your explanations and give another way that can allocated a dynamic 2D array

4.
(1)See the following program.

head->next = head->next->next;

Why it's a wrong operation for deleting a element in the list?
(2)Write a simple pseudo code program to insert '88' before the last element and then insert '76' before the head. Notice that what you know is the head element address of the list. Think about the difference between instering at the head and not at the head.

5. How to use an array to create a list know as a static list in logic?
For example:

node a[100];
head = a[0];
a[0]->next = 2;   // an array index

6. (optional) Think about that can we use an int_64 (long long) to create a list using the high 32 bits to store an int data and use the low 32 bits to store the next address pointer? If so, write a program to test. If not, wirte a program to explain your reasons.

Grading List

Deep thinking for part 1 (15pts)

Option 1 Generic list (115 pts)

Option 2 Json Parser (105 pts)

[ghostbody]

Option 1 Generic list (115 pts)

Knowledge points:

1. Data pointers.
2. Functions and function pointers.
3. Generic programming.

Generic Programming:

In the simplest definition, generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by ML in 1973,[1][2] permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication. Such software entities are known as generics in Ada, Delphi, Eiffel, Java, C#, F#, Objective-C, Swift, and Visual Basic .NET; parametric polymorphism in ML, Scala and Haskell (the Haskell community also uses the term "generic" for a related but somewhat different concept); templates in C++ and D; and parameterized types in the influential 1994 book Design Patterns. The authors of Design Patterns note that this technique, especially when combined with delegation, is very powerful but that "[dynamic], highly parameterized software is harder to understand than more static software."[3]

A simple example:

int max(int a, int b);
double max(double a, double b);
char max(char a, char b);

We need three function to achieve our goal, can we use just one?

function max(type a, type b) //????

Generic List:

For a list in c language, its type is set to be int, double, char or struct. The question is that, can we achieve just one list that can be used for various type in c language?
The answer is "Yes".
Now, your job is going to do it. Notice that this job can be very challenge but a lot to learn for you and if you can finish this, your c language programming skill is said to be passed.

void for various type of data

Type void * can point to various data types, this can help us to solve this problem.

The function prototype and some data definition is provided for you:

Glist.h

/*
 * list.h
 *
 *  Created on: Oct 22, 2015
 *      Author: Jiaqi Ye
 */


#ifndef BOOLEAN
#define BOOLEAN
typedef enum {true = 1, false = 0} bool;
#endif

#ifndef LIST_H_
#define LIST_H_
struct node {
    void * data;
    struct node* next;
};

struct list {
    // the head node of the list
    struct node * head;
    // the data size of each element in the list
    int data_size;
    // the size of the list
    int length;
};

#ifndef NODE_SIZE
#define NODE_SIZE sizeof(struct node)
#endif // NODE_SIZE
#ifndef LIST_SIZE
#define LIST_SIZE sizeof(struct list)
#endif // LIST_SIZE

// Poniter for struct node
typedef struct node* Iterator;

// Pointer for struct list
typedef struct list* List;


/*
    InitList
    @function: Initialize a list with the given data size
    @param: List * list indicates the list pointer's pointer
            int datasize indicates the datasize for each element in the list
    @return: if the operation is success return true, else retuen false
*/
bool InitList(List *list, int data_size);

/*
    Append
    @function: set a new node to the end of the list
    @param: List * list indicates the list pointer's pointer
            void * data indicates the generic data
            bool(*assign)(void *, void *) indicates a function pointer to provide assign rule for the data
    @return: if the operation is success return true, else retuen false
*/
bool Append(List list, void * data, bool(*assign)(void *, void *));

/*
    Append
    @function: set a new node after the index of the list
    @param: List * list indicates the list pointer's pointer
            int index indicates the index to be inserted data
            void * data indicates the generic data
            bool(*assign)(void *, void *) indicates a function pointer to provide assign rule for the data
    @return: if the operation is success return true, else retuen false
*/
bool AppendAt(List list, int index, void * data, bool(*assign)(void *, void *));

/*
    Remove
    @function: remove a node of the list
    @param: List * list indicates the list pointer's pointer
            void * data indicates the generic data to be deleted
            bool(*equal)(const void*, const void *) is a function poniter indicates the rule of "equal"
    @return: if the operation is success return true, else retuen false
*/
bool Remove(List list, void *data, bool(*equal)(const void*, const void *));

/*
    RemoveAt
    @function: remove a node of the list using index
    @param: List * list indicates the list pointer's pointer
            int index indicates the index of element to be deleted
    @return: if the operation is success return true, else retuen false
*/
bool RemoveAt(List list, int index);

/*
    RemoveAt
    @function:  update nodes of the list
    @param: List * list indicates the list pointer's pointer
            void * newData indicates the new data for the list
            filter is a function indicates the rule for which elements should be updated
            assign is a function indicates the rule to assign
    @return: if the operation is success return true, else retuen false
*/
bool Update(List list, void *newData, bool(*filter)(const void*, const void *), bool(*assign)(void *, void *));

/*
    Query
    @function: query some elements that fit a condition
    @param: List * list indicates the list pointer's pointer
            filter is a function indicates the rule for which elements should be updated
            assign is a function indicates the rule to assign
    @return: A list with result
*/
List Query(List list, bool(*filter)(const void *), bool(*assign)(void *, void *));

/*
    traversal
    @function: traversal with an operation rule
    @param: List * list indicates the list pointer's pointer
            filter is a function indicates the rule for which elements should be updated
            operation is a function to apply actions on the elements
    @return: A list with result
*/
bool traversal(const List list, bool(*filter)(const void *), bool(*operation)(const void *));

/*
    DeleteList
    @function: deconstuct the list deleting all the elements
    @param: a list
*/
bool DeleteList(List *list);


#endif /* LIST_H_ */

When you are doing the project, you probably use the following function:

static bool newNode(Iterator * it, int data_size, void * data, bool(*assign)(void *, void *)) {
    (*it) = (Iterator)malloc(sizeof(NODE_SIZE));
    if((*it) == NULL) {
        return false;
    }
    (*it)->data = NULL;
    (*it)->next = NULL;
    (*it)->data = malloc(data_size);
    if((*it)->data == NULL) {
        return false;
    }

    assign((*it)->data, data);

    return true;
}

And here is a script for you to test your logic:

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

static bool asign(void * a, void * b) {
    int * tempa = (int *)a;
    int * tempb = (int *)b;
    *tempa = *tempb;
    return true;
}

static bool filter(const void * a) {
    if(a != NULL) {
        return true;
    }
    return false;
}

static bool filter_1(const void * a, const void * b) {
    if(a != NULL) {
        if (*((int *)a) >= 4) {
            return true;
        }
    }
    return false;
}

static bool filter_odd(const void * a) {
    if(a != NULL) {
        if ((*((int *)a) & 1) != 0) {
        return true;
        }
    }
    return false;
}

static bool operation(const void * a) {
    if(a != NULL) {
        printf("%d->", *((int *)a));
        return true;
    }
    return false;
}

static bool equal(const void * a, const void * b) {
    if(a == NULL || b == NULL) {
        return false;
    }

    return *((int*)a) == *((int*)b);
}

int main() {
    printf("Hello world!\n");

    List li = NULL;

    int a;

    InitList(&li, sizeof(int));
    for(a = 1; a < 10; a++)
        Append(li, (void *)&a, asign);
    for(a = 9; a >= 1; a--)
        Remove(li, &a, equal);
    for(a = 1; a < 10; a++)
        Append(li, (void *)&a, asign);

    traversal(li, filter, operation);
    printf("NULL\n");

    traversal(li, filter_odd, operation);
    printf("NULL\n");

    List li2 = NULL;

    li2 = Query(li, filter_odd, asign);

    a = 0;
    Update(li, (void *)&a, filter_1, asign);
    traversal(li, filter, operation);
    printf("NULL\n");

    traversal(li2, filter, operation);
    printf("NULL\n");

    DeleteList(&li2);
    DeleteList(&li);

    return 0;
}

[ghostbody]

Option 2 Json Parser (105 pts)

Knowledge points:

1. Pointers and functions.
2. Strings parsing.
3. Json format.

Json

JSON, (canonically pronounced /ˈdʒeɪsən/ jay-sən;[1] sometimes JavaScript Object Notation), is an open standard format that uses human-readable text to transmit data objects consisting of attribute–value pairs. It is the primary data format used for asynchronous browser/server communication (AJAJ), largely replacing XML (used by AJAX).

Although originally derived from the JavaScript scripting language, JSON is a language-independent data format. Code for parsing and generating JSON data is readily available in many programming languages.

The JSON format was originally specified by Douglas Crockford. It is currently described by two competing standards, RFC 7159 and ECMA-404. The ECMA standard is minimal, describing only the allowed grammar syntax, whereas the RFC also provides some semantic and security considerations.[2] The official Internet media type for JSON is application/json. The JSON filename extension is .json.

From wikipedia

The test in SOJ and YOJ are in json format, here is an example:

  {
    "input": "yi qian liu bai er shi wu wan ling liu shi si\n",
    "output": "sixteen million two hundred and fifty thousand sixty-four\n",
    "score": 40
  }

Assume that we have 4 types of the data, int32, bool(true or false), array, object(nested json), we can have a compelete example:

{
    "nested_obj": {"num": 50097, "str": "GBRDCMJQGAYDAMJRGEYDCMJQGAYDC==="}, 
    "sparse_978": "GBRDCMBQGA======", 
    "dyn2": 100097,
    "dyn1": 100097, 
    "nested_arr": ["many"], 
    "str2": "GBRDCMJQGAYDAMJRGEYDCMJQGAYDC===", 
    "str1": "GBRDCMJQGAYDAMJRGEYDAMBQGAYDAMI=", 
    "thousandth": 97, 
    "sparse_979":  "GBRDCMBQGA======", 
    "num": 100097, 
    "bool": true, 
    "sparse_973": "GBRDCMBQGA======", 
    "sparse_972": "GBRDCMBQGA======", 
    "sparse_971": "GBRDCMBQGA======", 
    "sparse_970": "GBRDCMBQGA======",
    "sparse_977": "GBRDCMBQGA======", 
    "sparse_976": "GBRDCMBQGA======", 
    "sparse_975": "GBRDCMBQGA======", 
    "sparse_974": "GBRDCMBQGA======"
}

Now our job is to parse the object above into "keys" and "values", exclude the nested objects'.
For example above, we should parse:
keys: nested_obj, sparse_978, dyn2 .....
values: {"num": 50097, "str": "GBRDCMJQGAYDAMJRGEYDCMJQGAYDC==="}, "GBRDCMBQGA======" .....

Why Parse Json

Because Json is string and we need to know what it's exactly expressing unless we parse it in to pair (key, value). For example for a string:

{ "input": "yi qian liu bai er shi wu wan ling liu shi si\n","output": "sixteen million two hundred and fifty thousand sixty-four\n","score": 40}

We do not know that what's the input or output or score in the string unless we parse it.

Limits:

1. We just parse json in one line with space which means that we do not pares pretty json.
2. There will be only one layer nesting for nested json objects.
3. The json string will be correct.

Design Logic:

Json stores data format as a string array. We define the structure, including the start pointer, end pointer, JSON data type (used to determine the read of the string as the key or value) and data type (used to judge the value of the type, including: int, bool, string, array, nested and other types). Using pointers to read JSON key or value, start pointer and the end pointer representing its starting position in the string array and end position, first read for the key and the second read the value, and so on (as shown in the figure). Judgment value of the first character in a text string, if the character is digital, the value of data type is int; if the character "t" or "F", the string bool type; if the quotation marks "," ", the string is the string; if the symbol" [", the string is an array type; if the symbol" {", the string as the nested; otherwise for unknown type.

We have the following function prototype:

#ifndef JSONPARSER
#define JSONPARSER
#ifndef BOOLEAN
#define BOOLEAN
typedef enum {true = 1, false = 0} bool;
#endif
// 0 for json attributes(keys) and 1 for value
typedef enum {atr = 0, value = 1} json_type;
// 5 data type
typedef enum {int32 = 0, bool8 = 1, stringn = 2, array1 = 3, object1 = 4, unknown = 5} data_type;
// list define
typedef struct json_parser {
  // Json element start position
  unsigned int start;
  // Json element end position
  unsigned int end;
  // key or value
  json_type type;
  // data type
  data_type dtype;
  // next parser element
  struct json_parser * next;
} json_parser;

/*
   ParseJson
   @function: parse a Json string into parser elements
   @param: char * JsonStr indicates the Json string
   @return: A list of json parser elements and the length of the list
*/
extern json_parser * ParseJson(char * JsonStr, int * len);

/*
    DeleteJson
    @function: delete the list of json parser elements
    @param: a list of json parser elements
*/
extern void DeleteJson(json_parser * head);
#endif

Simple test

#include <stdio.h>
#include "Json.h"

static void print(unsigned int start, unsigned int end, char * s) {
  int i;
  for(i = start; i <= end; i++) {
    printf("%c", s[i]);
  }
}

int main() {
  char Json[10000];
  fgets(Json, 10000, stdin);
  int len;
  //puts(Json);

  json_parser * Parser;
  Parser = ParseJson(Json, &len);

  json_parser * positioner = Parser;
  while(positioner!=NULL) {
    print(positioner->start,positioner->end, Json);
    printf(" %d", positioner->dtype);
    positioner = positioner->next;
    printf("\n");
  }
  return 0;
}

Requirement:
You can not use any library for json parser in the internet

[kobebry80]

nice