Abstraction - Creates barrier between representation & usage of
ListADTEncapsulation - Ensures maintaining in-variants of
ListADT. An invariant is a fact about a data structure that is always true (assuming the code is bug-free), no matter what functions are called by user.
Con questa comprensione, di seguito è riportato il codice utente,
/***** main.c *****/
#include"list.h"
int main(void){
List *arrayList = createList((List *)NULL, CREATE_NEW_LIST);
if (arrayList == (List *)0){
fprintf(stderr, "Unable to create list \n");
exit(1); //Nothing else to do without arrayList
}
// Objects should only be on heap
int *object1 = malloc(sizeof(int));
*object1 = 777;
insertItem(arrayList, object1);
int *object2 = malloc(sizeof(int));
*object2 = 888;
insertItem(arrayList, object2);
/*
List *linkedList = createList((List *)NULL, CREATE_NEW_LIST);
if (linkedList == (List *)0){
fprintf(stderr, "Unable to create list \n");
exit(1); //Nothing else to do without linked list
}
// Objects should only be on heap
int *object1 = malloc(sizeof(int));
*object1 = 777;
insertItem(arrayList, object1);
int *object2 = malloc(sizeof(int));
*object2 = 888;
insertItem(arrayList, object2);
*/
}
sotto è List ADT,
/************ list.h ************/
/*
List is an ordered collection of homogenuous type elements(unique or duplicate).
List is not designed to have collection of heterogenuous type elements
All elements in a List are related.
List is mutable
Each element has a position.
If an element is deleted, then still the remaining elements sit in new order.
Array implementation of List
Linked implementation of List
*/
#include<stddef.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
/*********************** Usage - start ****************/
typedef enum{false, true}bool;
typedef enum {CREATE_NEW_LIST, DOUBLE_THE_LIST, HALF_THE_LIST}Op;
#if defined(ARRAY)
/* To ensure Encapsultation(i.e., maintain invariants of array) */
typedef struct List List;
#elif defined(LINKED_LIST)
/* To ensure Encapsultation(i.e., maintain invariants of linked list) */
/* User will not get access to list node */
typedef struct List List;
#else
#error "Wrong list implementation macro name !!!"
#endif
void insertItem(List *, void *newItem);
void deleteItem(List *, int listIndex);
List* createList(List *, Op opType);
/*********************** Usage - end ****************/
Di seguito è l'implementazione dell'array,
/***************** arrayImple.c **************/
#if defined(ARRAY)
#include"list.h"
/************ Representation - start ************/
typedef struct List{
void **array;
/* Following members for Housekeeping - Array enhancement*/
int lastItemPosition;
int size;
}List;
#define INITIAL_LIST_SIZE 50
/********************* Representation - end ************/
/************* Usage - start ***************/
List *createList(List *list, Op opType){
if(opType == CREATE_NEW_LIST){
list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
/* Is it safe to initialise zero to array of pointers? */
list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *));
list->lastItemPosition = -1;
list->size = INITIAL_LIST_SIZE;
}else if(opType == DOUBLE_THE_LIST){
list->array = realloc(list->array, 2*(list->size)*sizeof(void *));
list->lastItemPosition = list->lastItemPosition;;
list->size = 2*(list->size);
}else if(opType == HALF_THE_LIST){
list->array = realloc(list->array, ((list->size)/2)*sizeof(void *));
list->lastItemPosition = list->lastItemPosition;
list->size = (list->size)/2;
}
return list;
}
void insertItem(List *arrayList, void *newItem){
/* House keeping - Enhance the array */
if(arrayList->lastItemPosition + 1 == arrayList->size){
arrayList = createList(arrayList, DOUBLE_THE_LIST);
}
/* Insert new element - O(1) operation */
arrayList->array[++(arrayList->lastItemPosition)] = newItem;
return;
}
void deleteItem(List *arrayList, int listIndex){
void * element = arrayList->array[listIndex];
free(element);
/* Delete operation - O(n) operation */
for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
arrayList->array[accumulator] = arrayList->array[++accumulator];
}
arrayList->lastItemPosition--;
/* House keeping - Half the list */
if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
arrayList = createList(arrayList, HALF_THE_LIST);
}
}
return;
}
/******************** Usage - end *******************/
#endif
Di seguito è riportata l'implementazione dell'elenco collegato,
/**********linkedListImpl.c ***********/
#if defined(LINKED_LIST)
#include"list.h"
/***************** Representation - start ******************/
typedef struct DListNode{
void *item;
struct DListNode *next;
struct DListNode *prev;
}DListNode;
/*
Reason to introduce 'List' type:
Problem 1:
Say, user code has 'x' and 'y' pointing to the same shopping list that is built using 'Node' type.
Some part of user code update list with new item using 'x'
'y' is not in sync with this updation
Node *x = someCreatedList;
Node *y = x;
Node *z = malloc(sizeof(Node));
z->next = x;
x = z; //y misses that reference.
Solution:
Maintain a List type, whose job is to point to head(first node) of the list.
User code will go via reference of List type
Problem 2:
It make sense to have references of 'Node' type pointing to NULL
Applying operation[insertItem()] on NULL pointer will cause runtime errors
Solution:
Run operations over List type because it does not make sense to have reference of SList type pointing to NULL.
To solve problem1 & problem2, here is 'List' type
*/
typedef struct List{ /* Circular linked list(prev, next) */
DListNode *head;
int size; /*size attribute is not part of list definition, but quick way to help user code */
}List;
#define SENTINEL_NODE_DATA_ITEM (void *)0
/*
The following invariants apply to the 'linkedList' with a sentinel.
(1) For any linkedList d, d.head != null. (There’s always a sentinel.)
(2) For any DListNode x, x.next != null.
(3) For any DListNode x, x.prev != null.
(4) For any DListNode x, if x.next == y, then y.prev == x.
(5) For any DListNode x, if x.prev == y, then y.next == x.
(6) A 'linkedList'’s "size" variable is the number of DListNodes, NOT
COUNTING the sentinel (denoted by "head"), that can be accessed from the
sentinel by a sequence of "next" references.
*/
/************ Representation - end *************/
/********** Helper function - start ***********/
DListNode* createNode(void * value){
DListNode *newNode= malloc(sizeof(DListNode));
newNode->next = newNode;
newNode->prev = newNode;
newNode->item = value;
return newNode;
}
/******** Helper function - end ********/
/******** Usage - start **********/
List *createList(List *list, Op opType ){
List *listPointer = (List *)malloc(sizeof(List));
if(opType == CREATE_NEW_LIST){
/*
Amidst performing insert/delete operations on 'List',
To reduce the number of special checks, we designate one node as 'SENTINEL'
After using sentinel, there will be no NULL assignments/check in code.
*/
DListNode *sentinel = createNode(SENTINEL_NODE_DATA_ITEM);
listPointer->head = sentinel;
listPointer->head->next = listPointer->head;
listPointer->head->prev = listPointer->head;
listPointer->size = 0;
return listPointer;
}else{
fprintf(stderr, "Invalid flag passed to createList() \n");
return (List *)0;
}
}
/* O(1) operation - insert() operation */
void insertItem(List *linkedList, void *newItem){
DListNode *newNode = createNode(newItem);
if(linkedList->size == 0){
linkedList->head->next = linkedList->head->prev = newNode;
}else{
/* Link with current last node in the linked list*/
newNode->prev = linkedList->head->prev;
linkedList->head->prev->next = newNode;
/* Link with Sentinel node */
newNode->next = linkedList->head;
linkedList->head->prev = newNode;
}
return;
}
/* O(n) - delete() operation*/
void deleteItem(List *linkedList, int listIndex){
int accumulator = 0;
DListNode *nodeToDelete = linkedList->head->next;
if(listIndex < linkedList->size){
while(accumulator++ < listIndex){
nodeToDelete = nodeToDelete->next;
}
nodeToDelete->prev->next = nodeToDelete->next;
nodeToDelete->next->prev = nodeToDelete-> prev;
free(nodeToDelete);
}else{
fprintf(stderr, "deleteItem() - Invalid Index");
}
return;
}
/********** Usage - end *************/
#endif
Procedura di compilazione:
gcc -DLINKED_LIST main.c linkedListImpl.c
o
gcc -DARRAY main.c arrayImpl.c
1)
List garantisce l'incapsulamento?
2)
List è una buona astrazione? In caso di perdite, ti preghiamo di chiarire
Nota: motivazione - Per comprendere l'astrazione e l'amp; Incapsulamento, usando C