diff options
Diffstat (limited to 'c/dataStructure')
62 files changed, 4063 insertions, 0 deletions
diff --git a/c/dataStructure/408/fibo_1.c b/c/dataStructure/408/fibo_1.c new file mode 100755 index 0000000..26cb3b2 --- /dev/null +++ b/c/dataStructure/408/fibo_1.c @@ -0,0 +1,29 @@ +#include<stdio.h> + +int fibo(int n) +{ + int res, a = 0, b = 1; + + for (int i = 1; i <= n; i++) + { + if (i <= 1) + res = 1; + else + { + res = a + b; + a = b; + b = res; + } + } + + return res; +} + +int main(void) +{ + for (int i = 1; i <= 10; i++) + printf("%3d",fibo(i)); + putchar('\n'); + + return 0; +} diff --git a/c/dataStructure/408/graph/Makefile b/c/dataStructure/408/graph/Makefile new file mode 100755 index 0000000..d3565e8 --- /dev/null +++ b/c/dataStructure/408/graph/Makefile @@ -0,0 +1,18 @@ +CC = gcc +FLGS = -Wall -Werror -g +SRCS = *.c queue/queue.c +OPT = graph + +all: link run clean + +link: + $(CC) $(SRCS) $(FLGS) -o $(OPT) + +run: + ./$(OPT) + +gdb: link + gdb ./$(OPT) + +clean: + rm $(OPT) diff --git a/c/dataStructure/408/graph/dgraph.c b/c/dataStructure/408/graph/dgraph.c new file mode 100755 index 0000000..499fc0d --- /dev/null +++ b/c/dataStructure/408/graph/dgraph.c @@ -0,0 +1,164 @@ +#include "graph.h" + +/* Thdse functions can use for both direct or undirect graph, + * only be affected by argument 'directed' we give + */ + +void retreat(char * str) +{ + fprintf(stderr,"%s\n",str); + exit(EXIT_FAILURE); +} + +void initializeGraph(graph * g, bool directed) +{ + int i; /* counter */ + + g->nvertices = 0; + g->nedges = 0; + g->directed = directed; + + for (i = 1; i <= MAXV; i++) + g->degree[i] = 0; + + for (i = 1; i <= MAXV; i++) + g->edges[i] = NULL; +} + +/* x, y is a pair of vertices */ +void insertEdge(graph * g, int x, int y, bool directed) +{ + edgeNode * p; /* temporary pointer */ + + p = (edgeNode *) malloc (sizeof(edgeNode)); + if (!p) + retreat("Error allocate memory p"); + + p->weight = 0; + p->y = y; + + p->next = g->edges[x]; /* insert at head */ + g->edges[x] = p; + + g->degree[x]++; + + if (!directed) + insertEdge(g,y,x,true); /* add another one for undirected */ + else + g->nedges++; +} + +void readGraph(graph * g, bool directed) +{ + int i; /* counter */ + int m; /* number of edges */ + int x, y; /* vertices in edge (x, y) / <x, y> */ + + printf("Enter number of vertices and edges: "); + scanf ("%d%d", &(g->nvertices), &m); /* read number of vertices and edges */ + + printf("Enter two vertices consist one edge: "); + for (i = 1; i <= m; i++) + { + scanf("%d %d", &x, &y); /* readindex and vertex */ + insertEdge(g,x,y,directed); /* this is the one to make a graph */ + } +} + +void printGraph(graph * g) +{ + int i; /* counter */ + edgeNode * p; /* temporary pointer */ + + for (i = 1; i <= g->nvertices; i++) + { + printf("%d: ",i); + p = g->edges[i]; + while (p) + { + printf(" %d", p->y); + p = p->next; + } + putchar('\n'); + } +} + +void purgeGraph(graph * g) +{ + int i; /* counter */ + edgeNode * p, * q; /* temporary pointer */ + + for (i = 1; i < g->nvertices; i++) + { + p = g->edges[i]; + while (p) + { + q = p; + p = p->next; + free(q); + } + } +} + +void initializeSearch(graph * g) +{ + int i; + +// time = 0; + + for (i = 0; i <= g->nvertices; i++) + { + g->processed[i] = false; + g->discovered[i] = false; + g->parent[i] = -1; + } +} + +void processVertexEarly(int v) +{ + printf("processed vertex %d\n",v); +} +void processVertexLate(int v) +{ +} +void processEdge(int v, int y) +{ + printf("Process edge (%d,%d)\n",v,y); +} + +void bfs(graph * g, int start) +{ + queue q; /* queue of vertices to visit */ + int v; /* current vertex */ + int y; /* successor vertex */ + edgeNode * p; /* temporary pointer */ + + initializeSearch(g); + + initQueue(&q); + enQueue(&q,start); + g->discovered[start] = true; + + while (!emptyQueue(&q)) + { + v = deQueue(&q); + processVertexEarly(v); + g->processed[v] = true; + p = g->edges[v]; + + while (p) + { + y = p->y; + if (!g->processed[y] || g->directed) + processEdge(v,y); + if (!g->discovered[y]) + { + enQueue(&q,y); + g->discovered[y] = true; + g->parent[y] = v; + } + p = p->next; + } + processVertexLate(v); + } +} diff --git a/c/dataStructure/408/graph/graph.h b/c/dataStructure/408/graph/graph.h new file mode 100755 index 0000000..98b18bb --- /dev/null +++ b/c/dataStructure/408/graph/graph.h @@ -0,0 +1,45 @@ +#ifndef _GRAPH_H +#define _GRAPH_H + +/* + * We can use this header for both + * directed graph or undirected graph + * by toggle boolean flag 'directed' + * in graph structure. + */ + +#include<stdio.h> +#include<stdbool.h> +#include<stdlib.h> +#include "queue/queue.h" + +#define MAXV 5 /* maximum number of vertices */ + +typedef struct edgenode { + int y; /* adjacency info */ + int weight; /* edge weight if any */ + struct edgenode * next; /* next edge in list */ +} edgeNode; + +/* graph nodes start by 1 */ +typedef struct { + edgeNode * edges[MAXV + 1]; /* adjacency info */ + int degree[MAXV + 1]; /* outdegree of each vertex */ + int nvertices; /* number of vertices in graph */ + int nedges; /* number of edges in graph */ + bool directed; /* is the graph directed? */ + bool discovered[MAXV + 1]; + bool processed[MAXV + 1]; + int parent[MAXV + 1]; +} graph; + +void retreat (char * str); +void initializeGraph(graph * g, bool directed); +void readGraph (graph * g, bool directed); +void insertEdge (graph * g, int x, int y, bool directed); +void printGraph (graph * g); +void purgeGraph (graph * g); +void initializeSearch(graph * g); +void bfs(graph * g, int start); + +#endif diff --git a/c/dataStructure/408/graph/main.c b/c/dataStructure/408/graph/main.c new file mode 100755 index 0000000..6219969 --- /dev/null +++ b/c/dataStructure/408/graph/main.c @@ -0,0 +1,17 @@ +#include "graph.h" + +int main(void) +{ + graph gh; + bool directed = true; + initializeGraph(&gh,directed); + + readGraph(&gh,directed); + + printGraph(&gh); + bfs(&gh, 1); + + purgeGraph(&gh); + + return 0; +} diff --git a/c/dataStructure/408/graph/queue/qtest.c b/c/dataStructure/408/graph/queue/qtest.c new file mode 100755 index 0000000..61e01f2 --- /dev/null +++ b/c/dataStructure/408/graph/queue/qtest.c @@ -0,0 +1,21 @@ +#include "queue.h" + +int main(void) +{ + queue q; + + initQueue(&q); + enQueue(&q,10); + enQueue(&q,12); + printQueue(&q); + printf("deQueue1: %d\n",deQueue(&q)); + printf("deQueue2: %d\n",deQueue(&q)); + enQueue(&q,14); + printHead(&q); + printQueue(&q); + purgeQueue(&q); + if(emptyQueue(&q)) + puts("Empty Queue"); + + return 0; +} diff --git a/c/dataStructure/408/graph/queue/queue.c b/c/dataStructure/408/graph/queue/queue.c new file mode 100755 index 0000000..673c595 --- /dev/null +++ b/c/dataStructure/408/graph/queue/queue.c @@ -0,0 +1,78 @@ +#include "queue.h" + +void initQueue(Queue q) +{ + q->qhead = NULL; + q->qtail = NULL; +} + +void enQueue(Queue q, int y) +{ + elem * tmp = (elem*)malloc(sizeof(elem)); + + if (!tmp) + retreat("fail to enQueue"); + tmp->y = y; + tmp->next = NULL; + + if (!q->qtail) + { + q->qtail = tmp; + q->qhead = tmp; + } + else + { + q->qtail->next = tmp; + q->qtail = tmp; + } +} + +int deQueue(Queue q) +{ + bool flag = false; + if (!q->qhead) + retreat("Empty queue"); + if (q->qhead == q->qtail) + flag = true; + elem * tmp = q->qhead; + int p = tmp->y; + q->qhead = tmp->next; + free(tmp); + if (flag) + q->qtail = q->qhead; + return p; +} + +bool emptyQueue(Queue q) +{ + if (q->qhead) + return false; + return true; +} + +void purgeQueue(Queue q) +{ + elem * tmp; + while (q->qhead) + { + tmp = q->qhead; + q->qhead = tmp->next; + free(tmp); + } +} + +void printHead(Queue q) +{ + printf("Queue head is %d\n", q->qhead->y); +} + +void printQueue(Queue q) +{ + elem * tmp = q->qhead; + while (tmp) + { + printf("%d ",tmp->y); + tmp = tmp->next; + } + printf("\n"); +} diff --git a/c/dataStructure/408/graph/queue/queue.h b/c/dataStructure/408/graph/queue/queue.h new file mode 100755 index 0000000..145e598 --- /dev/null +++ b/c/dataStructure/408/graph/queue/queue.h @@ -0,0 +1,26 @@ +#ifndef _QUEUE_H +#define _QUEUE_H + +#include "../graph.h" + +typedef struct elem { + int y; + struct elem * next; +} elem; + +typedef struct queue { + elem * qhead; + elem * qtail; +} queue; + +typedef queue * Queue; + +void initQueue(Queue q); +void enQueue(Queue q, int y); +int deQueue(Queue q); +void purgeQueue(Queue q); +bool emptyQueue(Queue q); +void printHead(Queue q); +void printQueue(Queue q); + +#endif diff --git a/c/dataStructure/408/list/Makefile b/c/dataStructure/408/list/Makefile new file mode 100755 index 0000000..0b76bbc --- /dev/null +++ b/c/dataStructure/408/list/Makefile @@ -0,0 +1,24 @@ +CC = gcc + +FLGS = -Wall -Werror -g + +SSRCS = main.c sqlist.c +LSRCS = main.c lklist.c + +OPT = ./list + +ALL: link run clean + +link: + $(CC) $(LSRCS) $(FLGS) -o $(OPT) +list: + $(CC) $(SSRCS) $(FLGS) -o $(OPT) + +run: + $(OPT) + +gdb: $(OPT) + gdb $(OPT) + +clean: + rm $(OPT) diff --git a/c/dataStructure/408/list/list.h b/c/dataStructure/408/list/list.h new file mode 100755 index 0000000..811c62d --- /dev/null +++ b/c/dataStructure/408/list/list.h @@ -0,0 +1,69 @@ +/* + * In order to use one header file for both + * sequence list and linked list, I used linked list style + * this may cause inconvenient when inplementing sequence list + */ + +#ifndef _LIST_H +#define _LIST_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +#define MAX 50 + +typedef struct seq { + int * data; + int length; + int maxSize; +} Seq; +typedef Seq * sqList; + +typedef struct link { + int elem; + struct link * next; +} Link; +typedef Link * linkList; + +typedef struct list { + sqList sql; + linkList lin; +} List; + +/* initialize list + * exit with code EXIT_FAILURE if initialize fail, + * otherwise nothing return */ +void initList(List * L); + +/* return number of current elements + * if list does not exist, return -1 */ +int lengthList(List * L); + +/* find location of the element + * if element exists, return location + * else return false */ +bool locateElem(List * L, int * i, int e); + +/* find element at given location + * if location is bigger/smaller than length/0 + * return false + * else return location */ +bool getElem(List * L, int i, int * e); + +/* insert element at given location + * if location is bigger than length, insert at last + * if location is 0 or negative, return false */ +bool insertElem(List * L, int i, int e); + +/* if location is bigger than length, + * or is smaller than 1, + * return false */ +bool deleteElem(List * L, int i, int * e); +void printList (List * L); + +/* check if list exist and have no element */ +bool emptyList (List * L); +void deleteList(List * L); + +#endif diff --git a/c/dataStructure/408/list/lklist.c b/c/dataStructure/408/list/lklist.c new file mode 100755 index 0000000..c2112b1 --- /dev/null +++ b/c/dataStructure/408/list/lklist.c @@ -0,0 +1,174 @@ +#include "list.h" + +/* Fundamental */ +void initList(List * L) +{ + L->lin = NULL; +} + +int lengthList(List * L) +{ + linkList tmp = L->lin; + int i = 0; + while (tmp) + { + i++; + tmp = tmp->next; + } + + return i; +} + +bool locateElem(List * L, int * i, int e) +{ + linkList tmp = L->lin; + *i = 1; + while (tmp) + { + if (tmp->elem != e) + { + (*i)++; + tmp = tmp->next; + } + else + return true; + } + return false; +} + +bool getElem(List * L, int i, int * e) +{ + linkList tmp = L->lin; + + for (int j = 1; j < i; j++) + if(tmp->next) + tmp = tmp->next; + else + { + fprintf(stderr,"Location is out of range\n"); + return false; + } + *e = tmp->elem; + return true; +} + +bool insertElem(List * L, int i, int e) +{ + if (i <= 0) + { + fprintf(stderr,"Invalid location!\n"); + return false; + } + linkList scan = L->lin; + linkList new = (Link *) malloc (sizeof(Link)); + + new->elem = e; + new->next = NULL; + + if (!L->lin) + { + L->lin = new; + return true; + } + else + { + if (i == 1) + { + new->next = scan; + L->lin = new; + } + else + { + int j = 2; + while (j++ < i && scan->next) + scan = scan->next; + if (!scan->next && --j < i) + printf("Location is beyond the list length, Append element\n"); + new->next = scan->next; + scan->next = new; + } + } + return true; +} + +bool deleteElem(List * L, int i, int * e) +{ + linkList tmp = L->lin; + if (i == 1) + { + *e = tmp->elem; + L->lin = L->lin->next; + free(tmp); + return true; + } + int j = 2; // we need the one before the one needs delete + while (j++ < i && tmp->next) + tmp = tmp->next; + if (!tmp->next) + { + fprintf(stderr,"location out of range\n"); + return false; + } + + *e = tmp->next->elem; + if (tmp->next) + { + linkList t = tmp->next; + tmp->next = t->next; + free(t); + } + else + free(tmp); + return true; +} + +void printList(List * L) +{ + linkList tmp = L->lin; + + while (tmp) + { + printf("%d ",tmp->elem); + tmp = tmp->next; + } + putchar('\n'); +} + +void deleteList(List * L) +{ + linkList tmp = L->lin; + linkList del; + while (tmp) + { + del = tmp->next; + free(tmp); + tmp = del; + } +} + +/* Homework */ +void deleteX(linkList * L, int e) +{ + linkList tmp = *L; + + if (!tmp->next) + return; + else + { + if (tmp->elem == e) + { + (*L) = (*L)->next; + free(tmp); + deleteX(&(*L)->next,e); + } + else if (tmp->next->elem == e) + { + linkList p = tmp->next; + tmp->next = p->next; + free(p); + deleteX(&tmp,e); + } + else + deleteX(&tmp->next,e); + } +} diff --git a/c/dataStructure/408/list/main.c b/c/dataStructure/408/list/main.c new file mode 100755 index 0000000..34e4030 --- /dev/null +++ b/c/dataStructure/408/list/main.c @@ -0,0 +1,41 @@ +#include "list.h" + +int deleteMin(List * L); +void reverse(List * L); +//void deleteX(List * L, int e); +void deleteX(linkList * L, int e); +void loopLeftN(List * L, int n); +int main(void) +{ + List U; + initList(&U); + + for (int i = 1; i <= 10; i++) + insertElem(&U,i,i*2); + int p; + printList(&U); +// loopLeftN(&U,3); +// printList(&U); + getElem(&U,8,&p); + printf("%d\n",p); + locateElem(&U,&p,10); + printf("%d\n",p); + deleteElem(&U,3,&p); + printf("%d\n",p); + insertElem(&U,7,p); + insertElem(&U,7,p); + insertElem(&U,7,p); + insertElem(&U,7,p); + insertElem(&U,7,p); + printList(&U); + deleteX(&U.lin,p); + deleteX(&U.lin,2); + deleteX(&U.lin,20); + printList(&U); +// reverse(&U); +// printList(&U); + + deleteList(&U); + + return 0; +} diff --git a/c/dataStructure/408/list/sqlist.c b/c/dataStructure/408/list/sqlist.c new file mode 100755 index 0000000..05893b4 --- /dev/null +++ b/c/dataStructure/408/list/sqlist.c @@ -0,0 +1,201 @@ +#include "list.h" + +/* Fundamental */ +void initList(List * L) +{ + + // create new list + L->sql = (Seq *) calloc (1,sizeof(Seq)); + if (!L->sql) + { + fprintf(stderr,"create list fail\n"); + exit(EXIT_FAILURE); + } + + sqList tmp = L->sql; + // allocate memory + tmp->data = (int *) calloc (MAX, sizeof(int)); + if (!tmp->data) + { + fprintf(stderr,"allocate memory fail\n"); + exit(EXIT_FAILURE); + } + + tmp->length = 0; + tmp->maxSize = MAX; +} + +int lengthList(List * L) +{ + return L->sql->length; +} + +bool locateElem(List * L, int * i, int e) +{ + sqList tmp = L->sql; + for (int j = 0; j < tmp->length; j++) + if (tmp->data[j] == e) + { + *i = j + 1; + return true; + } + return false; +} + +bool getElem(List * L, int i, int * e) +{ + sqList tmp = L->sql; + if (i < 1 || i > tmp->length) + { + fprintf(stderr,"Out of range\n"); + return false; + } + *e = tmp->data[i-1]; + + return true; +} + +bool insertElem(List * L, int i, int e) +{ + sqList tmp = L->sql; + if (i < 1 || i > tmp->length+1) + { + fprintf(stderr, "Out of range\n"); + return false; + } + if (tmp->length == tmp->maxSize) + { + fprintf(stderr, "List full\n"); + return false; + } + for (int j = tmp->length; j >= i; j--) + tmp->data[j] = tmp->data[j-1]; + tmp->data[i-1] = e; + tmp->length++; + + return true; +} + +bool deleteElem(List * L, int i, int * e) +{ + sqList tmp = L->sql; + if (i < 1 || i > tmp->length) + { + fprintf(stderr,"Out of range\n"); + return false; + } + *e = tmp->data[i-1]; + + for (int j = i; j < tmp->length; j++) + tmp->data[j-1] = tmp->data[j]; + tmp->length--; + return true; +} + +void printList(List * L) +{ + sqList tmp = L->sql; + for (int i = 0; i < tmp->length; i++) + printf("%d ",tmp->data[i]); + putchar('\n'); +} + +bool emptyList(List * L) +{ + sqList tmp = L->sql; + if (tmp->length == 0) + return true; + return false; +} + +void deleteList(List * L) +{ + free(L->sql->data); + free(L->sql); +} + +/* homework */ +// 1 +int deleteMin(List * L) +{ + sqList tmp = L->sql; + + if (tmp->length == 0) + { + fprintf(stderr,"list is empty\n"); + exit(1); + } + int min = tmp->data[0], index = 0; + + for (int i = 1; i < tmp->length; i++) + if (min > tmp->data[i]) + { + min = tmp->data[i]; + index = i; + } + tmp->length--; + for (int i = index; i < tmp->length; i++) + tmp->data[i] = tmp->data[i+1]; + return min; +} + +// 2 +void reverse(List * L) +{ + sqList tmp = L->sql; + for (int i = 0; i < tmp->length/2; i++) + { + int t = tmp->data[i]; + tmp->data[i] = tmp->data[tmp->length-1-i]; + tmp->data[tmp->length-1-i] = t; + } +} + +// 3 +void deleteX(List * L, int e) +{ + sqList tmp = L->sql; + int n = 0, index = -1, i; + + for (i = 0; i < tmp->length; i++) + { + if (tmp->data[i] == e) + n++; + if (tmp->data[i] == e && index == -1) + index = i; // get first element's index + } + + for (i = index; i + n < tmp->length; i++) + tmp->data[i] = tmp->data[i+n]; + tmp->length -= n; +} + +// 10 +// helper +void rev(sqList q, int low, int high) +{ + for (int i = low; i < (low+high)/2; i++) + { + int n = i - low; + int tmp = q->data[i]; + q->data[i] = q->data[high-1-n]; + q->data[high-1-n] = tmp; + } +} + +// question answer +void loopLeftN(List * L, int n){ + sqList tmp = L->sql; + rev(tmp,0,n); + rev(tmp,n,tmp->length); + rev(tmp,0,tmp->length); +} +// extra +void loopRightN(List * L, int n) +{ + sqList tmp = L->sql; + n = tmp->length - n; + rev(tmp,0,n); + rev(tmp,n,tmp->length); + rev(tmp,0,tmp->length); +} diff --git a/c/dataStructure/408/tree/Makefile b/c/dataStructure/408/tree/Makefile new file mode 100755 index 0000000..85ea9c1 --- /dev/null +++ b/c/dataStructure/408/tree/Makefile @@ -0,0 +1,17 @@ +CC = gcc +SRC = *.c +FLGS = -Wall -Werror -g +OPT = ./tree + +ALL: link run clean + +link: + @$(CC) $(SRC) $(FLGS) -o $(OPT) +run: + $(OPT) + +gdb: link + gdb $(OPT) + +clean: + @rm $(OPT) diff --git a/c/dataStructure/408/tree/main.c b/c/dataStructure/408/tree/main.c new file mode 100755 index 0000000..c879362 --- /dev/null +++ b/c/dataStructure/408/tree/main.c @@ -0,0 +1,26 @@ +#include "tree.h" + +int main(void) +{ + Tree tree; + + initTree(&tree); + + printf("the size of tree now is %d\n",tree.size); + + insertTree(&tree,3); + insertTree(&tree,4); + insertTree(&tree,2); + insertTree(&tree,1); + + printTree(tree.root); + putchar('\n'); + + printf("the size of tree now is %d\n",tree.size); + + freeTree(&tree); + + printf("the size of tree now is %d\n",tree.size); + + return 0; +} diff --git a/c/dataStructure/408/tree/tree b/c/dataStructure/408/tree/tree Binary files differnew file mode 100755 index 0000000..1e50b63 --- /dev/null +++ b/c/dataStructure/408/tree/tree diff --git a/c/dataStructure/408/tree/tree.c b/c/dataStructure/408/tree/tree.c new file mode 100755 index 0000000..26dc81e --- /dev/null +++ b/c/dataStructure/408/tree/tree.c @@ -0,0 +1,83 @@ +#include "tree.h" + +void initTree(Tree * T) +{ + T->root = NULL; + T->size = 0; +} + +// insertTree helper +static Node * createNode(int e) +{ + Node * tmp = (Node *) malloc (sizeof(Node)); + if (!tmp) + { + fprintf(stderr,"Node creation failed!\n"); + exit(EXIT_FAILURE); + } + + tmp->data = e; + tmp->lchild = NULL; + tmp->rchild = NULL; + + return tmp; +} + +static void insertNode(Node * root, Node * new) +{ + if (root->data > new->data) + { + if (!root->lchild) + root->lchild = new; + else + insertNode(root->lchild,new); + } + else if (root->data < new->data) + { + if (!root->rchild) + root->rchild = new; + else + insertNode(root->lchild,new); + } + else + fprintf(stderr,"Binary tree can't hold two identical element.\n"); +} + +bool insertTree(Tree * T, int e) +{ + Node * tmp = createNode(e); + + if (T->size == 0) + T->root = tmp; + else + insertNode(T->root,tmp); + T->size++; + + return true; +} + +void printTree(Node * root) +{ + if (root->lchild) + printTree(root->lchild); + if (root->rchild) + printTree(root->rchild); + printf("%d ",root->data); +} + +// freeTree helper +void freeNode(Node * root) +{ + Node * tmp = root; + if (tmp->lchild) + freeNode(tmp->lchild); + if (tmp->rchild) + freeNode(tmp->rchild); + free(tmp); +} + +void freeTree(Tree * T) +{ + freeNode(T->root); + T->size = 0; +} diff --git a/c/dataStructure/408/tree/tree.h b/c/dataStructure/408/tree/tree.h new file mode 100755 index 0000000..659d7ef --- /dev/null +++ b/c/dataStructure/408/tree/tree.h @@ -0,0 +1,23 @@ +#ifndef _TREE_H +#define _TREE_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +typedef struct node { + int data; + struct node * lchild, * rchild; +} Node; + +typedef struct { + Node * root; + int size; +} Tree; + +void initTree(Tree * T); +bool insertTree(Tree * T, int e); +void printTree(Node * root); +void freeTree(Tree * T); + +#endif diff --git a/c/dataStructure/baseConversion.c b/c/dataStructure/baseConversion.c new file mode 100755 index 0000000..8f7bd46 --- /dev/null +++ b/c/dataStructure/baseConversion.c @@ -0,0 +1,71 @@ +// default base is decimal to binary +// run program with flag to start with different base + +#include<stdio.h> +#include<stdlib.h> + +typedef struct stack { + int * base; + int top; + int size; +} Stack; + +void getSpace(Stack * s) +{ + if (s->size == 0) + { + s->size = 1; + s->base = (int *) calloc (s->size,sizeof(int)); + } + else + { + s->size += 1; + s->base = (int *) realloc (s->base, sizeof(int) * s->size); + } +} + +void conversion(Stack * s, int from, int to) +{ + while (from != 0) + { + if (s->size <= s->top) + getSpace(s); + s->base[s->top++] = from % to; + from /= to; + } +} + +void print(Stack * s, int from) +{ + printf("origin\t\tbinary\n"); + printf("%d\t\t",from); + while (s->top != 0) + printf("%d",s->base[--s->top]); + s->top = 0; + putchar('\n'); +} + +int getNumber(void) +{ + int tmp; + + if (scanf("%d", &tmp) != 1) + exit(EXIT_SUCCESS); + return tmp; +} + +int main(void) +{ + Stack storage = {NULL, 0, 0}; + + int from = getNumber(); + int to = 2; + + conversion(&storage,from,to); + + print(&storage,from); + + free(storage.base); + + return 0; +} diff --git a/c/dataStructure/sorting/bubbleSort.c b/c/dataStructure/sorting/bubbleSort.c new file mode 100755 index 0000000..521a781 --- /dev/null +++ b/c/dataStructure/sorting/bubbleSort.c @@ -0,0 +1,47 @@ +#include<stdio.h> +#include<stdlib.h> +#include<time.h> + +#define SIZE 10 + +void swap(int * a, int * b) +{ + int tmp = *a; + *a = *b; + *b = tmp; +} + +void generateRandom(int * arr, int n) +{ + time_t sr; + srand(sr); + + for (int i = 0; i < n; i++) + arr[i] = rand() % 100; +} + +void bubbleSort(int * arr, int n) +{ + for (int i = 0; i < n; i++) + for (int j = 0; j < n - 1 - i; j++) + if (arr[j] > arr[j+1]) + swap(&arr[j],&arr[j+1]); +} + +int main(void) +{ + int arr[SIZE]; + generateRandom(arr,SIZE); + + for (int i = 0; i < SIZE; i++) + printf("%3d",arr[i]); + putchar('\n'); + + bubbleSort(arr,SIZE); + + for (int i = 0; i < SIZE; i++) + printf("%3d",arr[i]); + putchar('\n'); + + return 0; +} diff --git a/c/dataStructure/sorting/insertSort.c b/c/dataStructure/sorting/insertSort.c new file mode 100755 index 0000000..741f295 --- /dev/null +++ b/c/dataStructure/sorting/insertSort.c @@ -0,0 +1,60 @@ +#include<stdio.h> +#include<stdlib.h> +#include<time.h> + +#define SIZE 10 + +void swap(int * a, int * b) +{ + int tmp = *a; + *a = *b; + *b = tmp; +} + +void generateRandom(int * arr, int n) +{ + time_t sr; + srand(*&sr); + + for(int i = 0; i < n; i++) + arr[i] = rand() % 100; +} + +void print(int * arr, int n) +{ + for(int i = 0; i < n; i++) + printf("%3d",*(arr+i)); + putchar('\n'); +} + +void insertSort(int * arr, int n) +{ + int key, i, j; + + for (i = 1; i < n; i++) + { + key = arr[i]; + j = i - 1; + + while (j >= 0 && key < arr[j]) + { + arr[j+1] = arr[j]; + j--; + } + arr[j+1] = key; + } +} + +int main(void) +{ + int arr[SIZE]; + generateRandom(arr,SIZE); + + print(arr,SIZE); + + insertSort(arr,SIZE); + + print(arr,SIZE); + + return 0; +} diff --git a/c/dataStructure/sorting/mergeSort.c b/c/dataStructure/sorting/mergeSort.c new file mode 100755 index 0000000..826df71 --- /dev/null +++ b/c/dataStructure/sorting/mergeSort.c @@ -0,0 +1,57 @@ +#include<stdio.h> + +#define N 10 + +void merge(int * A, int low, int mid, int high) +{ + int m, n; + m = mid - low + 1; + n = high - mid; + int a1[m],a2[n]; + + for (int i = 0; i < m; i++) + a1[i] = A[low + i]; + for (int j = 0; j < n; j++) + a2[j] = A[mid + 1 + j]; + + //compare two subsets, put lower one in sorted array + int i = 0, j = 0, k = low; + + while (i < m && j < n) + { + if (a1[i] <= a2[j]) + A[k++] = a1[i++]; + else + A[k++] = a2[j++]; + } + + //Insert remains + while (i < m) + A[k++] = a1[i++]; + while (j < n) + A[k++] = a2[j++]; +} + +void mergeSort(int * A, int low, int high) +{ + if (low < high) + { + int mid = low + (high - low) / 2; + mergeSort(A,low,mid); + mergeSort(A,mid+1,high); + merge(A,low,mid,high); + } +} + +int main(void) +{ + int A[N] = {12,63,58,95,41,35,65,0,38,44}; + + mergeSort(A,0,N - 1); + + for (int i = 0; i < N; i++) + printf("%3d",A[i]); + + putchar('\n'); + return 0; +} diff --git a/c/dataStructure/sorting/quickSort.c b/c/dataStructure/sorting/quickSort.c new file mode 100755 index 0000000..2904b48 --- /dev/null +++ b/c/dataStructure/sorting/quickSort.c @@ -0,0 +1,63 @@ +#include<stdio.h> +#include<stdlib.h> +#include<time.h> + +#define SIZE 10 + +void swap(int * a, int * b) +{ + int tmp = *a; + *a = *b; + *b = tmp; +} + +void generateRandom(int * arr, int n) +{ + time_t sr; + srand(sr); + + for(int i = 0; i < n; i++) + arr[i] = rand() % 100; +} + +int partition(int * arr, int low, int high) +{ + int i,j; + for (i = low, j = low; i < high; i++) + if (arr[i] < arr[high]) + { + swap(&arr[i],&arr[j]); + j++; + } + swap(&arr[high],&arr[j]); + + return j; +} + +void quickSort(int * arr, int low, int high) +{ + if (low < high) + { + int pivot = partition(arr,low,high); + quickSort(arr,low, pivot - 1); // sort left + quickSort(arr,pivot + 1, high); + } +} + +int main(void) +{ + int arr[SIZE]; + generateRandom(arr,SIZE); + + for(int i = 0; i < SIZE; i++) + printf("%3d",*(arr+i)); + putchar('\n'); + + quickSort(arr,0,SIZE - 1); + + for (int i = 0; i < SIZE; i++) + printf("%3d",arr[i]); + putchar('\n'); + + return 0; +} diff --git a/c/dataStructure/sorting/selectionSort.c b/c/dataStructure/sorting/selectionSort.c new file mode 100755 index 0000000..0bfb671 --- /dev/null +++ b/c/dataStructure/sorting/selectionSort.c @@ -0,0 +1,86 @@ +#include<stdio.h> +#include<time.h> +#include<stdlib.h> + +void swap(int * a, int * b) +{ + int tmp; + tmp = *a; + *a = *b; + *b = tmp; +} + +int * selectionSort(int * arr, size_t n) +{ + int tmp = 0; + for (int i = 0; i < (int)n - 1; i++) + { + int position = i; + for (int j = i + 1; j < (int)n; j++) + if ( arr[position] > arr[j]) + position = j; + if (position != i) + swap(&arr[position], &arr[j]); + } + + return arr; +} + +void heapify(int * arr, size_t n, int i) +{ + int smallest = i; + int left = 2 * i + 1; + int right = 2 * i + 2; + + if (left < n && arr[left] > arr[smallest]) + smallest = left; + if (right < n && arr[right] > arr[smallest]) + smallest = right; + + if (smallest != i) + { + swap(&arr[i], &arr[smallest]); + heapify(arr,n,smallest); + } +} + +int * heapSort(int * arr, size_t n) +{ + for (int i = n/2 - 1; i >= 0; i--) + heapify(arr,n,i); + + for (int i = n - 1; i >= 0; i--) + { + swap(&arr[i],&arr[0]); + heapify(arr,i,0); + } + + return arr; +} + +int main(void) +{ + int sarr[] = {12,63,58,95,41,35,65,0,38,44}; + int harr[] = {12,63,58,95,41,35,65,0,38,44}; + size_t size = sizeof(sarr)/sizeof(int); + + + printf("Before sort:\n"); + for (int i = 0; i < (int)size; i++) + printf("%3d",sarr[i]); + putchar('\n'); + + selectionSort(sarr,size); + printf("After selection sort:\n"); + for (int i = 0; i < (int)size; i++) + printf("%3d",sarr[i]); + putchar('\n'); + + heapSort(harr,size); + printf("After heap sort:\n"); + for (int i = 0; i < (int)size; i++) + printf("%3d",harr[i]); + putchar('\n'); + + return 0; +} diff --git a/c/dataStructure/string/main.c b/c/dataStructure/string/main.c new file mode 100755 index 0000000..e0b57d9 --- /dev/null +++ b/c/dataStructure/string/main.c @@ -0,0 +1,15 @@ +#include "string.h" + +int main(void) +{ + sstring st; + char * ch = "This is a test string!"; + + StrAssign(&st,ch); + + printf("ch: %s\nsp: %s\n",ch,st.s); + + free(st.s); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/string/string.c b/c/dataStructure/string/string.c new file mode 100755 index 0000000..5b48917 --- /dev/null +++ b/c/dataStructure/string/string.c @@ -0,0 +1,66 @@ +#include "string.h" + +void StrAssign(sstring * st, const char * ch) +{ + size_t size = strlen(ch); + + st->s = (char *) malloc (sizeof(char) * (size+1)); + + if (!st->s) + { + fprintf(stderr,"Failed to malloc!\n"); + exit(EXIT_FAILURE); + } + + strncpy(st->s,ch,size+1); + st->length = size; +} + +void StrCopy(sstring * st, const sstring * sp) +{ + if (!sp->s) + { + fprintf(stderr,"Empty string!\n"); + exit(EXIT_FAILURE); + } + + StrAssign(st,sp->s); +} + +bool StrEmpty(sstring * st) +{ + if (!st->s) + return false; + return true; +} + +int StrCompare(const sstring * st, const sstring * sp) +{ + int count = 0, i; + if (!st->s || !sp->s) + { + fprintf(stderr,"Empty string!\n"); + exit(EXIT_FAILURE); + } + + for (i = 0; st->s[i] && sp->s[i]; i++) + { + if (st->s[i] > sp->s[i]) + count++; + else if (st->s[i] < sp->s[i]) + count--; + } + + if (st->s[i]) + { + i++; + count++; + } + else if (sp->[i]) + { + i++; + count--; + } + + return count; +}
\ No newline at end of file diff --git a/c/dataStructure/string/string.h b/c/dataStructure/string/string.h new file mode 100755 index 0000000..000f299 --- /dev/null +++ b/c/dataStructure/string/string.h @@ -0,0 +1,19 @@ +#ifndef _STRING_H +#define _STRING_H + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <stdbool.h> + +typedef struct string { + char * s; + int length; +}sstring; + +void StrAssign(sstring * st, const char * ch); +void StrCopy (sstring * st, const sstring * sp); +bool StrEmpty (sstring * st); +int StrCompare(const sstring * st, const sstring * sp); + +#endif
\ No newline at end of file diff --git a/c/dataStructure/tree/1.c b/c/dataStructure/tree/1.c new file mode 100755 index 0000000..3b2364a --- /dev/null +++ b/c/dataStructure/tree/1.c @@ -0,0 +1,268 @@ +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> +#define MAXSIZE 10 +typedef int elemtype; +typedef struct node { + elemtype e; + struct node * left; + struct node * right; +} Node; + +typedef Node * LLP; + +typedef struct tree { + Node * root; + int size; +} Tree; + +typedef struct pair { + Node * parent; + Node * child; +} Pair; + +typedef int ElemType; + +typedef struct data { + ElemType * elem; + int length; +} Elem; + +typedef struct stack { + LLP data; + struct stack * next; +} S; +typedef S * Stack; + +void InitS(Stack * s) +{ + *s = NULL; +} + +void Push(LLP e, Stack * s) +{ + Stack new = (Stack ) calloc (1,sizeof(S)); + if (!new) + { + fprintf(stderr,"failed to allocate memory for stack!\n"); + exit(1); + } + new->data = e; + new->next = *s; + *s = new; +} + +void Pop(LLP * e, Stack * s) +{ + Stack p = *s; + *e = (*s)->data; + *s = (*s)->next; + free(p); +} + +void DestroyS(Stack * s) +{ + Stack p; + + if (*s) + { + p = *s; + *s = (*s)->next; + free(p); + } +} + +bool EmptyS(Stack * s) +{ + if (!*s) + return true; + return false; +} + +void InitList(Elem * L) +{ + L->elem = (ElemType *) malloc (sizeof(ElemType) * MAXSIZE); + + if (!(L->elem)) + { + fprintf(stderr,"Initialization Failed\nPlease run as debug mode\n"); + exit(EXIT_FAILURE); + } + + L->length = 0; +} + +void AddElem(Elem * L, Node * nd) //recursive +{ + Stack p; + InitS(&p); + + Node * n = nd; + + while (n || !EmptyS(&p)) + { + if (n) + { + Push(n,&p); + n = n->left; + } + else + { + Pop(&n,&p); + L->elem[L->length++] = n->e; + n = n->right; + } + } + DestroyS(&p); +} + +void DestroyList(Elem * L) +{ + if (L->elem) + free(L->elem); + else + printf("Sequence list is not exist!\n"); +} + +int binarySearch(int e, Elem * L) +{ + int l = 0, r = L->length; + int n; + + while (l < r) + { + n = (l+r)/2-1; + if (L->elem[n] == e) + return n; + else if (L->elem[n] < e) + l = n+1; + else + r = n; + } + return -1; +} + +void InitTree(Tree * tr) +{ + tr->root = NULL; + tr->size = 0; +} + +static bool ToLeft(const elemtype e, const elemtype tree_e) +{ + return e < tree_e; +} + +static bool ToRight(const elemtype e, const elemtype tree_e) +{ + return e > tree_e; +} + +static Pair SeekItem(const elemtype e, Tree * ptr) +{ + Pair look = {NULL,ptr->root}; + + while (look.child) + { + if (ToLeft(e,look.child->e)) + { + look.parent = look.child; + look.child = look.child->left; + } + else if (ToRight(e,look.child->e)) + { + look.parent = look.child; + look.child = look.child->right; + } + else + break; + } + + return look; +} + +static bool AddNode(Node * new, Node * nd) +{ + if (ToLeft(new->e,nd->e)) + { + if (nd->left == NULL) + nd->left = new; + else + AddNode(new,nd->left); + } + else if (ToRight(new->e,nd->e)) + { + if (nd->right == NULL) + nd->right = new; + else + AddNode(new,nd->right); + } + else return false; + return true; +} + +void MidPrint(const Node * nd) //recursive +{ + if (nd->left) + MidPrint(nd->left); + printf(" %d", nd->e); + if (nd->right) + MidPrint(nd->right); +} + +bool AddItem(const elemtype e, Tree * ptr) +{ + Node * new; + + if (SeekItem(e, ptr).child) + return false; + + new = (Node *) calloc (1,sizeof(Node)); + if (!new) + return false; + + new->e = e; + + if (!ptr->root) + ptr->root = new; + else + AddNode(new, ptr->root); + return true; +} + +bool ReleaseTree(Node * nd) +{ + Node * tmp = nd; + if (tmp->right) + ReleaseTree(tmp->right); + if (tmp->left) + ReleaseTree(tmp->left); + free(tmp); + return true; +} + +int main(void) +{ + int num; + Tree btree; + Elem list; + int position; + InitTree(&btree); + InitList(&list); + + for (int i = 0; i < 10; i++) + { + scanf("%d", &num); + AddItem(num,&btree); + } + + MidPrint(btree.root); //recursive + AddElem(&list, btree.root); + putchar('\n'); + printf("%d\n",binarySearch(21,&list)); + + ReleaseTree(btree.root); + DestroyList(&list); + + return 0; +} diff --git a/c/dataStructure/tree/btree.c b/c/dataStructure/tree/btree.c new file mode 100755 index 0000000..c40db30 --- /dev/null +++ b/c/dataStructure/tree/btree.c @@ -0,0 +1,166 @@ +#include "btree.h" + +void InitTree(Tree * ptree) +{ + ptree->root = NULL; + ptree->size = 0; +} + +bool EmptyTree(const Tree * ptree) +{ + return !ptree->root?true:false; +} + +int CountItem(const Tree * ptree) +{ + return ptree->size; +} + +typedef struct pair { + Node * parent; + Node * child; +} Pair; + + +static bool ToLeft(ElemType e1, ElemType e2) +{ + return e1 < e2; +} +static bool ToRight(ElemType e1, ElemType e2) +{ + return e1 > e2; +} +static bool AddNode(Node * new, Node * root) +{ + if (ToLeft(new->e, root->e)) + { + if (root->left == NULL) + root->left = new; + else + AddNode(new,root->left); + } + else if (ToRight(new->e,root->e)) + { + if (root->right == NULL) + root->right = new; + else + AddNode(new,root->right); + } + else + return false; + return true; +} + +static Pair SeekNode(Node * root, const ElemType e) +{ + Pair look; + look.parent = NULL; + look.child = root; + + if (look.child == NULL) + return look; + + while (look.child != NULL) + { + if (ToLeft(e, look.child->e)) + { + look.parent = look.child; + look.child = look.child->left; + } + else if (ToRight(e,look.child->e)) + { + look.parent = look.child; + look.child = look.child->right; + } + else + break; + } + + return look; +} + +bool AddItem(const ElemType e, Tree * ptree) +{ + Node * new = (Node *) calloc (1,sizeof(Node)); + if (!new) + return false; + if(SeekNode(ptree->root,e).child) + return false; + + new->e = e; + + ptree->size++; + + if (!ptree->root) + ptree->root = new; + else + AddNode(new,ptree->root); + + return true; +} + +static void DeleteNode(Node ** ptr) +{ + Node * tmp; + + if ((*ptr)->left == NULL) + { + tmp = *ptr; + *ptr = (*ptr)->right; + free(tmp); + } + else if ((*ptr)->right == NULL) + { + tmp = *ptr; + *ptr = (*ptr)->left; + free(tmp); + } + else + { + for (tmp = (*ptr)->left;tmp->right != NULL; tmp = tmp->right) + continue; + tmp->right = (*ptr)->right; + tmp = *ptr; + *ptr = (*ptr)->left; + free(tmp); + } +} + +bool DeleteItem(const ElemType e, Tree * ptree) +{ + Pair look; + + look = SeekNode(ptree->root, e); + if (look.child == NULL) + return false; + + if (look.parent == NULL) + DeleteNode(&ptree->root); + else if (look.parent->left == look.child) + DeleteNode(&look.parent->left); + else + DeleteNode(&look.parent->right); + ptree->size--; + + return true; +} + +bool ResTree(Node * root) +{ + Node * pnode = root; + if (pnode->right) + ResTree(pnode->right); + if (pnode->left) + ResTree(pnode->left); + free(pnode); + return true; +} + +void PrintTree(const Node * root) +{ + printf("%c",root->e); + if (root->left) + PrintTree(root->left); + if (root->right) + PrintTree(root->right); +} diff --git a/c/dataStructure/tree/btree.h b/c/dataStructure/tree/btree.h new file mode 100755 index 0000000..3acf818 --- /dev/null +++ b/c/dataStructure/tree/btree.h @@ -0,0 +1,28 @@ +#ifndef _BTREE_H +#define _BTREE_H + +#include<stdio.h> +#include<stdbool.h> +#include<stdlib.h> + +typedef char ElemType; +typedef struct node { + ElemType e; + struct node * left; + struct node * right; +} Node; + +typedef struct tree { + Node * root; + int size; +} Tree; + +void InitTree (Tree * ptree); +bool EmptyTree (const Tree * ptree); +int CountItem (const Tree * ptree); +bool AddItem (const ElemType e, Tree * ptree); +bool DeleteItem(const ElemType e, Tree * ptree); +bool ResTree (Node * pnode); +void PrintTree (const Node * root); + +#endif diff --git a/c/dataStructure/tree/main.c b/c/dataStructure/tree/main.c new file mode 100755 index 0000000..846c9e1 --- /dev/null +++ b/c/dataStructure/tree/main.c @@ -0,0 +1,30 @@ +#include "btree.h" + +int main(void) +{ + Tree btree; + + ElemType e; + InitTree(&btree); + + int size = 10; + char a[] = {'a','b','c','d','e','A','B','C','D','E'}; + + if (EmptyTree(&btree)) + printf("It's empty\n"); + + for (int i = 0; i < size; i++) + AddItem(a[i],&btree); + + printf("Tree content: %d\n", CountItem(&btree)); + + PrintTree(btree.root); + putchar('\n'); + DeleteItem('c',&btree); + PrintTree(btree.root); + putchar('\n'); + + ResTree(btree.root); + + return 0; +} diff --git a/c/dataStructure/栈和队列/栈/链栈/ack.c b/c/dataStructure/栈和队列/栈/链栈/ack.c new file mode 100755 index 0000000..9d12544 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/ack.c @@ -0,0 +1,20 @@ +#include "stack.h" + +int ack (int m, int n) +{ + if (m == 0) + return n+1; + else if (n == 0) + return ack(m-1,1); + else + return ack(m-1,ack(m,n-1)); +} + +int main(void) +{ + int m = 2, n = 1; + + printf("%d\n",ack(m,n)); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/conversion.c b/c/dataStructure/栈和队列/栈/链栈/conversion.c new file mode 100755 index 0000000..ebc2161 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/conversion.c @@ -0,0 +1,29 @@ +#include "stack.h" + +int main(void) +{ + Stack s; + + int number, ans; + + InitStack(&s); + + printf("Please enter a number: "); + scanf("%d", &number); + + while (number) + { + Push(&s, number%2); + number /= 2; + } + + while (!StackIsEmpty(&s)) + { + printf("%d",GetTop(&s)); + Pop(&s, &ans); + } + + putchar('\n'); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/main.c b/c/dataStructure/栈和队列/栈/链栈/main.c new file mode 100755 index 0000000..f211ae4 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/main.c @@ -0,0 +1,21 @@ +#include "stack.h" + +int main(void) { + Stack s; + int p; + + InitStack(&s); + + for (int i = 0; i < 3; i++) + Push(&s, i); + + for (int i = 0; i < 3; i++) { + printf("Get top: %d\n",GetTop(&s)); + Pop(&s,&p); + printf("Pop: %d\n",p); + } + + DestroyStack(&s); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/p_match.c b/c/dataStructure/栈和队列/栈/链栈/p_match.c new file mode 100755 index 0000000..44efecd --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/p_match.c @@ -0,0 +1,41 @@ +#include "stack.h" + +int main(void) +{ + ElemType ch; + Stack s; + ElemType pop, top; + bool flag = true; + + InitStack(&s); + + while ((ch = getchar()) != '\n' && flag) + { + switch (ch) + { + case '(': Push(&s,ch); + break; + case '[': Push(&s,ch); + break; + case ')': if (StackIsEmpty(&s) || (top = GetTop(&s)) != '(') + flag = false; + else if (top == '(') + Pop(&s,&pop); + break; + case ']': if (StackIsEmpty(&s) || (top = GetTop(&s)) != '[') + flag = false; + else if (top == '[') + Pop(&s,&pop); + break; + } + } + + if (StackIsEmpty(&s) && flag) + printf("Matching successful!\n\n"); + else + { + fprintf(stderr,"Matching failed!\n\n"); + DestroyStack(&s); + } + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/palindrome.c b/c/dataStructure/栈和队列/栈/链栈/palindrome.c new file mode 100755 index 0000000..c8a9a7f --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/palindrome.c @@ -0,0 +1,64 @@ +#include<ctype.h> +#include "stack.h" + +int main(void) +{ + ElemType ch,a1,a2; + Stack s,p; + int size = 0; + bool flag = false; + + InitStack(&s); + InitStack(&p); + + while ((ch = getchar()) != '\n') + { + Push(&s,tolower(ch)); + size++; + } + + if (size == 0) + return 0; + if (size % 2 == 0) + flag = true; + size /= 2; + + if (!flag) + size++; + + for (int i = 0; i < size; i++) + { + if (flag) + { + Pop(&s,&ch); + Push(&p,ch); + } + else + { + if (i == size - 1) + ch = GetTop(&s); + else + Pop(&s,&ch); + Push(&p,ch); + } + } + + while (s) + { + Pop(&s,&a1); + Pop(&p,&a2); + if (a1 != a2) + break; + } + + if (s) + { + printf("Not palindrome word!\n"); + DestroyStack(&s); + DestroyStack(&p); + } + else + printf("Is palindrome word!\n"); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/stack.c b/c/dataStructure/栈和队列/栈/链栈/stack.c new file mode 100755 index 0000000..e47dd81 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/stack.c @@ -0,0 +1,56 @@ +#include "stack.h" + +bool InitStack(Stack * s) { + *s = NULL; + return true; +} + +bool DestroyStack(Stack * s) { + Stack p; + + while (*s) { + p = *s; + *s = (*s)->next; + free (p); + } + return true; +} + +bool Push(Stack * s, ElemType n) { + Stack p = (stack *) malloc (sizeof(stack)); + if (!p) { + fprintf(stderr,"No enough memory\n"); + return false; + } + p->data = n; + p->next = *s; + + *s = p; + + return true; +} + +bool Pop(Stack * s, ElemType * n) { + if (!*s) { + fprintf(stderr,"No element in stack!\n"); + return false; + } + *n = (*s)->data; + Stack p = *s; + *s = (*s)->next; + free(p); + + return true; +} + +ElemType GetTop(Stack * s) { + if (*s) + return (*s)->data; + return -1; +} + +bool StackIsEmpty (Stack * s) { + if (!*s) + return true; + return false; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/链栈/stack.h b/c/dataStructure/栈和队列/栈/链栈/stack.h new file mode 100755 index 0000000..33e9ffe --- /dev/null +++ b/c/dataStructure/栈和队列/栈/链栈/stack.h @@ -0,0 +1,25 @@ +#ifndef _STACK_H +#define _STACK_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> +#include"tree.h" + +typedef Node * ElemType; + +typedef struct stack{ + ElemType data; + struct stack * next; +} stack; + +typedef stack * Stack; + +bool InitStack(Stack * s); +bool DestroyStack(Stack * s); +bool Push(Stack * s, ElemType n); +bool Pop(Stack * s, ElemType * n); +ElemType GetTop(Stack * s); +bool StackIsEmpty (Stack * s); + +#endif diff --git a/c/dataStructure/栈和队列/栈/顺序栈/main.c b/c/dataStructure/栈和队列/栈/顺序栈/main.c new file mode 100755 index 0000000..93fcad8 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/顺序栈/main.c @@ -0,0 +1,21 @@ +#include "stack.h" + +int main(void) { + int p; + Stack s; + + InitStack(&s); + + for (int i = 0; i < 8; i++) + Push(&s,i); + + for (int i = 0; i < 8; i++) { + printf("Get top: %d\n",GetTop(&s)); + Pop(&s,&p); + printf("Pop: %d\n",p); + } + + DestroyStack(&s); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/顺序栈/stack.c b/c/dataStructure/栈和队列/栈/顺序栈/stack.c new file mode 100755 index 0000000..b124e59 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/顺序栈/stack.c @@ -0,0 +1,50 @@ +#include "stack.h" + +bool InitStack(Stack * s) { + s->base = (int *) malloc (sizeof(int) * MAXIMUM); + + if (!s->base) { + fprintf(stderr,"Create stack error!\n"); + return false; + } + s->top = s->base; + s->size = MAXIMUM; + + return true; +} + +bool DestroyStack(Stack * s) { + if (!s->base){ + fprintf(stderr,"Stack not initialize!\n"); + return false; + } + free(s->base); + + return true; +} + +bool Push(Stack * s, int n) { + if (s->top - s->base == s->size) { + fprintf(stderr,"Stack is full!\n"); + return false; + } + *s->top++ = n; // *s->top = n; *s->top++; + + return true; +} + +bool Pop(Stack * s, int * n) { + if (s->top == s->base) { + fprintf(stderr,"Empty stack!\n"); + return false; + } + *n = *--s->top; // --s->top; *n = *s->top; + + return true; +} + +int GetTop(Stack * s) { + if (s->top != s->base) + return *(s->top - 1); + return -1; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/栈/顺序栈/stack.h b/c/dataStructure/栈和队列/栈/顺序栈/stack.h new file mode 100755 index 0000000..2d63452 --- /dev/null +++ b/c/dataStructure/栈和队列/栈/顺序栈/stack.h @@ -0,0 +1,23 @@ +#ifndef _STACK_H +#define _STACK_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +#define MAXIMUM 5 +#define RESIZE 1 + +typedef struct stack { + int * base; + int * top; + int size; +} Stack; + +bool InitStack(Stack * s); +bool DestroyStack(Stack * s); +bool Push(Stack * s, int n); +bool Pop(Stack * s, int * n); +int GetTop(Stack * s); + +#endif
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/队列/循环队列/main.c b/c/dataStructure/栈和队列/队列/循环队列/main.c new file mode 100755 index 0000000..e69de29 --- /dev/null +++ b/c/dataStructure/栈和队列/队列/循环队列/main.c diff --git a/c/dataStructure/栈和队列/队列/循环队列/queue.c b/c/dataStructure/栈和队列/队列/循环队列/queue.c new file mode 100755 index 0000000..2c7f781 --- /dev/null +++ b/c/dataStructure/栈和队列/队列/循环队列/queue.c @@ -0,0 +1,53 @@ +#include "queue.h" + +bool InitQueue(Queue * q) +{ + q->base = (int *) malloc (sizeof(int) * MAXSIZE); + if (!q->base) + { + fprintf(stderr,"Failed to allocate memory!\n"); + return false; + } + + q->front = q->rear = 0; +} + +bool EnQueue(Queue * q, int e) +{ + if ((q->rear + 1)%MAXSIZE == q->front) + { + fprintf(stderr,"Queue is full!\n"); + return false; + } + + q->base[q->rear] = e; + q->rear = (q->rear + 1) % MAXSIZE; + + return true; +} + +bool DeQueue(Queue * q, int * e) +{ + if (q->front == q->rear) + { + fprintf(stderr,"Queue is empty"); + return false; + } + + *e = q->base[q->front]; + q->front = (q->front + 1) % MAXSIZE; + + return true; +} + +int LengthQueue(Queue * q) +{ + return (q->rear - q->front + MAXSIZE) % MAXSIZE; +} + +int GetHead(Queue * q) +{ + if (q->front != q->rear) + return q->base[q->front]; + return -1; +}
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/队列/循环队列/queue.h b/c/dataStructure/栈和队列/队列/循环队列/queue.h new file mode 100755 index 0000000..11806b5 --- /dev/null +++ b/c/dataStructure/栈和队列/队列/循环队列/queue.h @@ -0,0 +1,17 @@ +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +#define MAXSIZE 5 + +typedef struct queue { + int * base; + int front; + int rear; +} Queue; + +bool InitQueue (Queue * q); +bool EnQueue (Queue * q, int e); +bool DeQueue (Queue * q, int * e); +int LengthQueue (Queue * q); +int GetHead (Queue * q);
\ No newline at end of file diff --git a/c/dataStructure/栈和队列/队列/链队列/main.c b/c/dataStructure/栈和队列/队列/链队列/main.c new file mode 100755 index 0000000..db5ae9a --- /dev/null +++ b/c/dataStructure/栈和队列/队列/链队列/main.c @@ -0,0 +1,28 @@ +#include "queue.h" + +int main(void) +{ + ElemType e; + pqueue head, tail; + InitQueue(&head); + InitQueue(&tail); + + while ((e = getchar()) != '\n') + { + EnQueue(&tail, &e); + if (EmptyQueue(&head)) + head = tail; + } + + PrintQueue(&head); + ElemType retval; + + DeQueue(&head, &retval); + printf("'%c' quit queue\n",retval); + + PrintQueue(&head); + + RsQueue(&head); + + return 0; +} diff --git a/c/dataStructure/栈和队列/队列/链队列/queue.c b/c/dataStructure/栈和队列/队列/链队列/queue.c new file mode 100755 index 0000000..94361d1 --- /dev/null +++ b/c/dataStructure/栈和队列/队列/链队列/queue.c @@ -0,0 +1,75 @@ +#include "queue.h" + +void InitQueue(pqueue * q) +{ + *q = NULL; +} + +bool EmptyQueue(pqueue * qhead) +{ + if (!*qhead) + return true; + return false; +} + +bool EnQueue(pqueue * qtail, ElemType * e) +{ + pqueue new = (pqueue) malloc (sizeof(Queue)); + if (!new) + return false; + new->data = *e; + new->next = NULL; + + if (!*qtail) + *qtail = new; + else + { + (*qtail)->next = new; + *qtail = new; + } + + return true; +} + +bool DeQueue(pqueue * qhead, ElemType * e) +{ + pqueue tmp = *qhead; + if (!*qhead) + return false; + *e = tmp->data; + *qhead = (*qhead)->next; + free(tmp); + + return true; +} + +bool RsQueue (pqueue * qhead) +{ + if (EmptyQueue(qhead)) + return false; + pqueue tmp = *qhead; + + while (!*qhead) + { + tmp = (*qhead)->next; + free(*qhead); + *qhead = tmp; + } + + return true; +} + +bool PrintQueue (pqueue * qhead) +{ + if (EmptyQueue(qhead)) + return false; + pqueue tmp = *qhead; + + while (tmp) + { + printf("%c", tmp->data); + tmp = tmp->next; + } + putchar('\n'); + return true; +} diff --git a/c/dataStructure/栈和队列/队列/链队列/queue.h b/c/dataStructure/栈和队列/队列/链队列/queue.h new file mode 100755 index 0000000..e444632 --- /dev/null +++ b/c/dataStructure/栈和队列/队列/链队列/queue.h @@ -0,0 +1,23 @@ +#ifndef _QUEUE_H +#define _QUEUE_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +typedef char ElemType; + +typedef struct queue { + ElemType data; + struct queue * next; +} Queue; +typedef Queue * pqueue; + +void InitQueue (pqueue * q); +bool EnQueue (pqueue * qtail, ElemType * e); +bool DeQueue (pqueue * qhead, ElemType * e); +bool RsQueue (pqueue * qhead); +bool EmptyQueue (pqueue * qhead); +bool PrintQueue (pqueue * qhead); + +#endif diff --git a/c/dataStructure/树/btree.c b/c/dataStructure/树/btree.c new file mode 100755 index 0000000..f41c404 --- /dev/null +++ b/c/dataStructure/树/btree.c @@ -0,0 +1,91 @@ +#include "btree.h" + +void InitTree(Tree * ptree) +{ + ptree->root = NULL; + ptree->size = 0; +} + +bool EmptyTree(const Tree * ptree) +{ + return !ptree->root?true:false; +} + +int CountItem(const Tree * ptree) +{ + return ptree->size; +} + + +static bool ToLeft(ElemType e1, ElemType e2) +{ + return e1 < e2; +} +static bool ToRight(ElemType e1, ElemType e2) +{ + return e1 > e2; +} +static bool AddNode(Node * new, Node * root) +{ + if (ToLeft(new->e, root->e)) + { + if (root->left == NULL) + root->left = new; + else + AddNode(new,root->left); + } + else if (ToRight(new->e,root->e)) + { + if (root->right == NULL) + root->right = new; + else + AddNode(new,root->right); + } + else + return false; + return true; +} + +bool AddItem(const ElemType e, Tree * ptree) +{ + Node * new = (Node *) calloc (1,sizeof(Node)); + if (!new) + return false; + new->e = e; + + ptree->size++; + + if (!ptree->root) + ptree->root = new; + else + AddNode(new,ptree->root); + + return true; +} + +bool ResTree(Node * root) +{ + Node * pnode = root; + if (pnode->right) + { + ResTree(pnode->right); + free(pnode); + } + else if (pnode->left) + { + ResTree(pnode->left); + free(pnode); + } + else + free(pnode); + return true; +} + +void PrintTree(const Node * root) +{ + printf("%c",root->e); + if (root->left) + PrintTree(root->left); + if (root->right) + PrintTree(root->right); +} diff --git a/c/dataStructure/树/btree.h b/c/dataStructure/树/btree.h new file mode 100755 index 0000000..d950745 --- /dev/null +++ b/c/dataStructure/树/btree.h @@ -0,0 +1,27 @@ +#ifndef _BTREE_H +#define _BTREE_H + +#include<stdio.h> +#include<stdbool.h> +#include<stdlib.h> + +typedef char ElemType; +typedef struct node { + ElemType e; + struct node * left; + struct node * right; +} Node; + +typedef struct tree { + Node * root; + int size; +} Tree; + +void InitTree (Tree * ptree); +bool EmptyTree (const Tree * ptree); +int CountItem (const Tree * ptree); +bool AddItem (const ElemType e, Tree * ptree); +bool ResTree (Node * pnode); +void PrintTree (const Node * root); + +#endif diff --git a/c/dataStructure/树/main.c b/c/dataStructure/树/main.c new file mode 100755 index 0000000..7def53f --- /dev/null +++ b/c/dataStructure/树/main.c @@ -0,0 +1,27 @@ +#include "btree.h" + +int main(void) +{ + Tree btree; + + ElemType e; + InitTree(&btree); + + int size = 10; + char a[] = {'A','a','B','b','C','c','D','d','E','e'}; + + if (EmptyTree(&btree)) + printf("It's empty\n"); + + for (int i = 0; i < size; i++) + AddItem(a[i],&btree); + + printf("Tree content: %d\n", CountItem(&btree)); + + PrintTree(btree.root); + putchar('\n'); + + ResTree(btree.root); + + return 0; +} diff --git a/c/dataStructure/线性表/线性链表/blist/bhlist.c b/c/dataStructure/线性表/线性链表/blist/bhlist.c new file mode 100755 index 0000000..1c0dbc8 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/blist/bhlist.c @@ -0,0 +1,76 @@ +// Implement +#include "bhlist.h" + +void InitList (Blist * L) +{ + *L = NULL; +} + +bool AddElem(Blist * L, int e) +{ + Blist scan = *L; + BNode * new = (BNode *) malloc (sizeof(BNode)); + + if (!new) + { + fprintf(stderr,"Memory error!\n"); + return false; + } + + new->data = e; + new->next = NULL; + + if (!scan) + { + new->prior = NULL; + *L = new; + } + + else + { + while (scan->next) + scan = scan->next; + new->prior = scan; + scan->next = new; + } + + return true; +} + +void DestroyList (Blist * L) +{ + Blist t1 = *L; + Blist t2; + + while (t1) + { + t2 = t1->next; + free(t1); + t1 = t2; + } +} + +void TraverseList(Blist * L) +{ + Blist tmp = *L; + Blist ta,tb; + + while (tmp) + { + printf("Element is %d\n",tmp->data); + tb = tmp->prior; + ta = tmp->next; + if (tb) + printf("It's prior element is %d, ",tb->data); + else + printf("No element before it, "); + + if (ta) + printf("and it's next element is %d!\n",ta->data); + else + printf("No element after it!\n"); + + tmp = tmp->next; + } + puts("Traverse DONE!"); +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/blist/bhlist.h b/c/dataStructure/线性表/线性链表/blist/bhlist.h new file mode 100755 index 0000000..659750a --- /dev/null +++ b/c/dataStructure/线性表/线性链表/blist/bhlist.h @@ -0,0 +1,23 @@ +#ifndef _BHLIST_H +#define _BHLIST_H + +#include<stdio.h> +#include<stdbool.h> +#include<stdlib.h> + +typedef struct bnode { + int data; + struct bnode * prior; + struct bnode * next; +} BNode; + +typedef BNode * Blist; + +void InitList (Blist * L); +bool AddElem (Blist * L, int e); +bool InsertElem (Blist * L, int e, int i); +bool DeleteElem (Blist * L, int e, int i); +void DestroyList (Blist * L); +void TraverseList (Blist * L); + +#endif
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/blist/main.c b/c/dataStructure/线性表/线性链表/blist/main.c new file mode 100755 index 0000000..09b4247 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/blist/main.c @@ -0,0 +1,24 @@ +// Driver +#include "bhlist.h" + +int main(void) +{ + Blist number; + + int num; + + InitList(&number); + + printf("Please enter number(q to quit): "); + while (scanf("%d", &num) == 1) + AddElem(&number,num); + + printf("Add element done! Now shows them!\n"); + printf("%d\n",number->data); + + TraverseList(&number); + + DestroyList(&number); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/hlist.c b/c/dataStructure/线性表/线性链表/hlist.c new file mode 100755 index 0000000..fc4cf8a --- /dev/null +++ b/c/dataStructure/线性表/线性链表/hlist.c @@ -0,0 +1,198 @@ +#include "list.h" + +void InitList (List * L) +{ + *L = (LNode *) malloc (sizeof(LNode)); + + if (!*L) + { + fprintf(stderr,"Initialization Failed\n"); + exit(EXIT_FAILURE); + } + + (*L)->next = NULL; + + printf("Initialization Successful!\n"); +} + +void DestroyList (List * L) +{ + // reserve head pointer + List T = *L; + List tmp; + + if (!T->next) + printf("No element in list!\n"); + else + { + while (T->next) + { + tmp = T->next->next; + free(T->next); + T->next = tmp; + } + + if (!T->next) + printf("Destroyed list!\n"); + else + printf("Error during destroy list"); + } +} + +bool AddElem (List * L, ElemType e) +{ + List new = *L; + + while (new->next) + new = new->next; + + new->next = (LNode *) malloc (sizeof(LNode)); + + if (!new) + return false; + new = new->next; + new->data = e; + new->next = NULL; + + return true; +} + +int ListLength (List * L) +{ + int count = 0; + + List tmp = *L; + + while (tmp->next) + { + tmp = tmp->next; + count++; + } + + return count; +} + +ElemType GetElem (List * L, int i) +{ + List tmp = *L; + + for (int j = 1; j < i; j++) + tmp = tmp->next; + return tmp->next->data; +} + +int LocateElem (List * L, ElemType e) +{ + int i = 1; + List tmp = *L; + + while (tmp->next && tmp->next->data != e) + { + tmp = tmp->next; + i++; + } + + if (!tmp->next) + return 0; + + return i; +} + +ElemType PriorElem(List * L, ElemType e) +{ + List tmp = *L; + while (tmp->next->data != e) + tmp = tmp->next; + + return tmp->data; +} + +ElemType NextElem(List * L, ElemType e) +{ + List tmp = *L; + while (tmp->next->data != e) + tmp = tmp->next; + + tmp = tmp->next->next; + + return tmp->data; +} + +bool InsertElem (List * L, ElemType e, int i) +{ + List scan = *L; + List new; + int tmp = 1; + + new = (LNode *) malloc (sizeof(LNode)); + + if (!new) + return false; + + while (scan->next && tmp < i) + { + scan = scan->next; + tmp++; + } + + + if (!scan->next) + printf("Reached list end. Element appended on.\n"); + + new->data = e; + new->next = scan->next; + scan->next = new; + + return true; +} + +bool DeleteElem (List * L, int i) +{ + List tmp1 = *L; + List tmp2 = tmp1->next; + + for (int j = 1; j < i; j++) + { + tmp1 = tmp1->next; + tmp2 = tmp2->next; + } + + if (!tmp2) + return false; + + tmp1->next = tmp2->next; + free(tmp2); + + return true; +} + +void TraverseList (List * L) +{ + int i = 1; + List tmp = (*L)->next; + + if (!tmp) + printf("No element could be traversed!\n"); + else + { + puts("Traverse list:"); + while (tmp) + { + printf("Node %d:\t%d\n",i++,tmp->data); + tmp = tmp->next; + } + puts("Traverse done!\n"); + } +} + +void OperateMenu (void) +{ + puts("List Operation Menu\n"); + puts("\e[34ma. Add element b. Initialize list"); + puts("c. List status d. Get element from specific position"); + puts("e. Search element f. Find prior element"); + puts("g. Find next element h. Insert an element"); + puts("i. Delete an element j. Traverse list"); + puts("k. Show Menu l. Destroy list"); + puts("q. Quit"); +} diff --git a/c/dataStructure/线性表/线性链表/hmain.c b/c/dataStructure/线性表/线性链表/hmain.c new file mode 100755 index 0000000..20aaa92 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/hmain.c @@ -0,0 +1,207 @@ +#include "list.h" + +static void eatline(void) +{ + while (getchar() != '\n') + continue; +} + +static char get_answer(void) +{ + printf("\e[39m\nPlease enter choice > "); + return tolower(getchar()); +} + +static bool CheckList(bool flag) +{ + if (!flag) + { + printf("List does not exist! Please initialize it!\n"); + return false; + } + return true; +} + +int main(void) +{ + List L; + char ans; + ElemType e; + int pos; + bool flag = false; + + printf("\e[1;1H\e[2J"); + + OperateMenu(); + + while ((ans = get_answer()) != 'q') + { + if (strchr("abcdefghijklq",ans) == NULL) + { + fprintf(stderr,"Please enter choice labeled above!\n"); + if (ans != '\n') + eatline(); + continue; + } + + eatline(); + + if (ans == 'k') // Show menu + { + putchar('\n'); + OperateMenu(); + continue; + } + + if (ans == 'b') // Initialize list + { + InitList(&L); + flag = true; + continue; + } + + if (CheckList(flag) == false) // Check initialization + continue; + + else if (ans == 'l') // Destroy list + DestroyList(&L); + + else if (ans == 'a') // Add element + { + printf("Please enter an number: "); + scanf("%d", &e); + eatline(); + if (AddElem(&L, e)) + printf("Element adding successful!\n"); + else + printf("Element adding failed, please run debug mode!\n"); + } + + else if (ans == 'c') // Show list length + printf("List contains %d element!\n",ListLength(&L)); + + else if (ans == 'd') // Get element by position + { + printf("Enter position you want to get: "); + scanf("%d",&pos); + eatline(); + int i = ListLength(&L); + + if (pos > i || pos <= 0) + { + printf("Position error, List now has %i elements!\n", i); + continue; + } + + printf("Position %d: %d",pos,GetElem(&L,pos)); + } + + else if (ans == 'e') // Get position by element + { + printf("Enter element value: "); + scanf("%d", &e); + eatline(); + + if ((pos = LocateElem(&L,e)) == 0) + { + printf("Element %d is not in this list!\n",e); + continue; + } + + printf("Element position: %d\n",pos); + } + + else if (ans == 'f') // Get prior element + { + printf("Enter element: "); + scanf("%d", &e); + eatline(); + + if ((pos = LocateElem(&L,e)) == 0) + { + printf("Element %d is not in this list!\n",e); + continue; + } + + else if (pos == 1) + { + printf("First element, no prior element!\n"); + continue; + } + + printf("Prior element of element %d is %d\n", + e,PriorElem(&L,e)); + } + + else if (ans == 'g') // Get next element + { + printf("Enter element: "); + scanf("%d", &e); + eatline(); + + if ((pos = LocateElem(&L,e)) == 0) + { + printf("Element %d is not in this list!\n",e); + continue; + } + + else if(pos == ListLength(&L)) + { + printf("Last element, no next element!\n"); + continue; + } + + printf("Next element of element %d is %d\n", + e,NextElem(&L,e)); + } + + else if (ans == 'h') // Insert an element + { + printf("Enter position you want to put: "); + scanf("%d", &pos); + printf("Enter element you want to add: "); + scanf("%d", &e); + eatline(); + + if (!InsertElem(&L,e,pos)) + { + printf("Insert error!\n"); + continue; + } + printf("Insert successful!\n"); + } + + else if (ans == 'i') // Delete an element + { + int i = ListLength(&L); + printf("Enter position you want to delete: "); + scanf("%d", &pos); + eatline(); + + if (pos <= 0) + { + printf("position should be greater than 0!\n"); + continue; + } + + else if (pos > i || !DeleteElem(&L,pos)) + { + printf("Position error, %d elements in list\n", + i); + puts("Delete failed"); + continue; + } + puts("Delete successful!"); + } + + else if (ans == 'j') + TraverseList(&L); + } + + if (flag) + free(L); + + puts("Thanks for using this utility!\n"); + + return 0; +} diff --git a/c/dataStructure/线性表/线性链表/list.h b/c/dataStructure/线性表/线性链表/list.h new file mode 100755 index 0000000..1b0e8b0 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/list.h @@ -0,0 +1,33 @@ +#ifndef _LIST_H +#define _LIST_H + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> +#include<ctype.h> +#include<string.h> + +typedef int ElemType; + +typedef struct list { + ElemType data; + struct list * next; +}LNode; + +typedef LNode * List; + +void InitList (List * L); +void DestroyList (List * L); +bool AddElem (List * L, ElemType e); // Add an element, length +1 +bool ListEmpty (List * L); +int ListLength (List * L); +ElemType GetElem (List * L, int i); // Get ith element +int LocateElem (List * L, ElemType e); // return element e's position, if not found, return 0 +ElemType PriorElem (List * L, ElemType e); // return precedent element of e +ElemType NextElem (List * L, ElemType e); // return element after e +bool InsertElem (List * L, ElemType e, int i); // insert Elem at i +bool DeleteElem (List * L, int i); // delete ith element +void TraverseList (List * L); // traverse all list +void OperateMenu (void); // show Menu to user + +#endif
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/nhdriver.c b/c/dataStructure/线性表/线性链表/nhdriver.c new file mode 100755 index 0000000..86ef056 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/nhdriver.c @@ -0,0 +1,34 @@ +/* Test driver -- Linked list without head pointer */ + +#include "list.h" + +int main(void) +{ + List number; + + InitList(&number); + + for (int i = 0; i < 10; i++) + AddElem(&number,i+1); + + TraverseList(&number); + printf("%d numbers in list", ListLength(&number)); + + putchar('\n'); + + InsertElem(&number,7,12); + TraverseList(&number); + + putchar('\n'); + + DeleteElem(&number, 1); + TraverseList(&number); + + putchar('\n'); + + DestroyList(&number); + + TraverseList(&number); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/nhlist.c b/c/dataStructure/线性表/线性链表/nhlist.c new file mode 100755 index 0000000..d37248d --- /dev/null +++ b/c/dataStructure/线性表/线性链表/nhlist.c @@ -0,0 +1,181 @@ +/* Function declaration -- Linked list without head pointer */ + +#include "list.h" + +void InitList(List * L) +{ + *L = NULL; +} + +void DestroyList(List * L) +{ + List tmp; + + while (*L) + { + tmp = (*L)->next; + free(*L); + *L = tmp; + } +} + +bool AddElem(List * L, ElemType e) +{ + List scan = *L; + + List new = (LNode *) malloc (sizeof(LNode)); + + if (!new) + { + fprintf(stderr,"Failed Adding element\n"); + return false; + } + + new->data = e; + new->next = NULL; + + if (!*L) + *L = new; + else + { + while (scan->next) + scan = scan->next; + scan->next = new; + } + + return true; +} + +bool ListEmpty (List * L) +{ + if (!*L) + return true; + return false; +} + +int ListLength (List * L) +{ + List tmp = *L; + int count = 0; + while (tmp) + { + tmp = tmp->next; + count++; + } + + return count; +} + +ElemType GetElem (List * L, int i) +{ + int n = ListLength(L); + if (i > n) + { + fprintf(stderr,"Position error, Please restricted between 0 and %d",n); + return EOF; + } + List tmp = *L; + + for (int j = 0; j < i; j++) + tmp = tmp->next; + + if (tmp) + return tmp->data; + return 0; +} + +void TraverseList (List * L) +{ + List tmp = *L; + + while (tmp) + { + printf("%7d",tmp->data); + tmp = tmp->next; + } + putchar('\n'); +} + +bool InsertElem (List * L, ElemType e, int i) +{ + bool flag = false; + List tmp = *L; + List new = (LNode *) malloc (sizeof(LNode)); + + int n = ListLength(&tmp); + + if (!new) + { + fprintf(stderr,"Failed to create new node!\n"); + return flag; + } + + new->data = e; + + if (i < 1) + fprintf(stderr,"Invalid position!\n"); + + else if (i == 1) + { + new->next = tmp; + *L = new; + flag = true; + } + + else + { + for (int j = 2; j < i; j++) + if (tmp->next) + tmp = tmp->next; + else + break; + + if (i > n) + printf("List length is %d, append element to last!\n",n); + + new->next = tmp->next; + tmp->next = new; + flag = true; + } + return flag; +} + +bool DeleteElem (List * L, int i) +{ + List t1 = *L; + List t2; + bool flag = false; + int n = ListLength(&t1); + + if (i < 1) + fprintf(stderr, "Position error!\n"); + + else if (i == 1) + { + t2 = t1; + *L = t1->next; + free(t2); + flag = true; + } + + else if (i <= n) + { + for (int j = 2; j < i; j++) + if (t1->next) + t1 = t1->next; + else + break; + + if (t1->next) + { + t2 = t1->next; + t1->next = t2->next; + free(t2); + flag = true; + } + } + + else + printf("No element at position %d\n",i); + return flag; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/线性链表/operation.c b/c/dataStructure/线性表/线性链表/operation.c new file mode 100755 index 0000000..c0dc934 --- /dev/null +++ b/c/dataStructure/线性表/线性链表/operation.c @@ -0,0 +1,334 @@ +/* Operation based on pointer with head */ +#include "list.h" + +void append(List * A, List * B); // Append B's elements to A +List ordered_merge(List * A, List * B); // Merge B's elements to A orderedly +void overlap(List * A, List * B); +void ANotB(List * A, List * B); +void split(List * A, List * B, List * C); +void reverse(List * A); + +// Driver +int main(void) +{ + // This comment is use for test reverse function + ///* + List a; + InitList(&a); + + int d1[] = {1,2,3,4,5,6,7,8,9,10}; + + for (int i = 0; i < sizeof(d1)/sizeof(int); i++) + AddElem(&a,*(d1+i)); + + TraverseList(&a); + + reverse(&a); + + TraverseList(&a); + + DestroyList(&a); + + return 0; + //*/ + + // This comment is use for test split function + /* + ElemType d1[] = {-3,9,-5,1,3,6,-13,0,0,-44,42,123,453,12,42,-312,-1324}; + + InitList(&a); + for (int i = 0; i < sizeof(d1)/sizeof(int); i++) + AddElem(&a,d1[i]); + + TraverseList(&a); + + split(&a,&b,&c); + TraverseList(&b); + TraverseList(&c); + + DestroyList(&b); + DestroyList(&c); + + free(a); + + return 0; + */ + + // This comment is use for test function takes 2 arguments + /* + ElemType d1[] = {11,22,33,44,99}; + ElemType d2[] = {44,55,66,77,88}; + + // Initialize list + InitList(&a); + InitList(&b); + + for (int i = 0; i < sizeof(d1)/sizeof(int); i++) + AddElem(&a,d1[i]); + + for (int i = 0; i < sizeof(d2)/sizeof(int); i++) + AddElem(&b,d2[i]); + + TraverseList(&a); + TraverseList(&b); + + + // Check initialization + overlap(&a,&b); + + TraverseList(&a); + + // Release list + DestroyList(&a); + free(a); + + return 0; + */ +} + +// ------------------------------------------ list with head ----------------------------------------- +void append(List * A, List * B) +{ + // Create a new pointer to point A; + List C = *A; + + // Get next pointer until hits NULL pointer + while (C->next) + C = C->next; + + // Attach last NULL pointer to first element of B + C->next = (*B)->next; + + // Release B's head + free(*B); + + // Now A has both A and B's elements +} + +List ordered_merge(List * A, List * B) +{ + List T1, T2; + // For convenience, T1 is smallest one + if ((*A)->next->data <= (*B)->next->data) + { + T1 = *A; + T2 = *B; + } + else + { + T1 = *B; + T2 = *A; + } + + // To keep T1 still + List T4 = T1; + + // Store next pointer of bigger one + List T3; + + /* Both start from Head pointer. So T->next is the real data + * we manipulate. Assume T->next is P + * + * If P1->data <= P2->data: + * We use P3 to store P2->next, + * attach P2->next with P4, + * and attach P2 to P4. + * This process will still P1 and move P2 to next + * as long as condition remains true. + * + * Else, if P1->data > P2->data + * Then we move P1 to next to compare with P2 */ + while (T4->next && T2->next) + { + if (T4->next->data >= T2->next->data) + { + T3 = T2->next->next; + T2->next->next = T4->next; + T4->next = T2->next; + T2->next = T3; + } + else + T4 = T4->next; + } + + /* Due to every elements are ordered. + * so if smaller one runs out, + * we only need to append bigger one to it. + * + * If bigger one runs out, We won't do anything. */ + if (!T4->next) + { + T4->next = T2->next; + T2->next = NULL; + + } + + // Clear empty list + if (!(*A)->next) + free(*A); + else + free(*B); + + return T1; +} + +void overlap (List * A, List * B) +{ + /* If A > B, release B, moving B to next + If B > A, release A, moving A to next + If A = B, release B, moving A&B to next */ + List a = *A, b = *B, c; + + while (a->next && b->next) + { + if (a->next->data > b->next->data) + { + c = b->next->next; + free(b->next); + b->next = c; + } + else if (a->next->data < b->next->data) + { + c = a->next->next; + free(a->next); + a->next = c; + } + else + { + a = a->next; + c = b->next->next; + free(b->next); + b->next = c; + } + } + + if (a->next) + { + c = a->next->next; + free(a->next); + a->next = c; + } + else if (b->next) + { + c = b->next->next; + free(b->next); + b->next = c; + } + free(b); +} + +// Get elements appear only in A +void ANotB (List * A, List * B) +{ + /* If A > B, then release B, moving to next + * If A < B, moving A till A == B or A > B + * If A = B, Release B, moving both A and B + */ + List t1 = *A, t2 = *B; + List tmp; + + while (t1->next && t2->next) + { + if (t1->next->data > t2->next->data) + { + tmp = t2->next->next; + free(t2->next); + t2->next = tmp; + } + + else if (t1->next->data == t2->next->data) + { + tmp = t2->next->next; + free(t2->next); + t2->next = tmp; + + tmp = t1->next->next; + free(t1->next); + t1->next = tmp; + } + else + t1 = t1->next; + } + + while (t2) + { + tmp = t2->next; + free(t2); + t2 = tmp; + } +} + +void split(List * A, List * B, List * C) +{ + /* if A < 0 + * if !B + * B get A node + * else + * bp get A node + * else A > 0 + * same as B + * else A == 0 + * release A node, move A to A->next + */ + List b, c, tmp, bp, cp, op; + tmp = (*A)->next; + *B = NULL; + *C = NULL; + + while (tmp) + if (tmp->data < 0) + if (!*B) + { + *B = tmp; + tmp = tmp->next; + (*B)->next = NULL; + bp = *B; + } + else + { + bp->next = tmp; + tmp = tmp->next; + b = bp->next; + b->next = NULL; + bp = bp->next; + } + else if (tmp->data > 0) + if (!*C) + { + *C = tmp; + tmp = tmp->next; + (*C)->next = NULL; + cp = *C; + } + else + { + cp->next = tmp; + tmp = tmp->next; + c = cp->next; + c->next = NULL; + cp = cp->next; + } + else + { + op = tmp; + tmp = tmp->next; + free(op); + } +} +// ------------------------------------------ list with head ----------------------------------------- + +// this function will take list without head +void reverse(List * A) +{ + List prior = NULL, current; + + while (*A) + { + current = *A; + *A = (*A)->next; + current->next = prior; + prior = current; + } + + *A = current; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/顺序表/main.c b/c/dataStructure/线性表/顺序表/main.c new file mode 100755 index 0000000..66e4031 --- /dev/null +++ b/c/dataStructure/线性表/顺序表/main.c @@ -0,0 +1,47 @@ +#include "sequence.h" + +int main(void) +{ + Elem number; + + InitList(&number); + + if (ListEmpty(&number)) + printf("List now is empty\n"); + + printf("So the length of list would be %d\n",ListLength(&number)); + + for (int i = 0; i < 10; i++) + AddElem(&number, i*i-i*3); + + ElemType n; + if ((n = GetElem(&number,3) != -1)) + printf("Element at position 3 is %d\n", n); + + if ((n = GetElem(&number,7)) != -1) + printf("Element at position 7 is %d\n", n); + + if ((n = LocateElem(&number,-2)) != 0) + printf("Number -2 is at %dth\n",n); + else + printf("Element not found\n"); + + for (int i = 0; i < number.length; i++) + printf("Element %d: %d\n", i+1, number.elem[i]); + putchar('\n'); + + ListInsert(&number,3,7); + + for (int i = 0; i < number.length; i++) + printf("Element %d: %d\n", i+1, number.elem[i]); + putchar('\n'); + + ListDelete(&number,6); + + for (int i = 0; i < number.length; i++) + printf("Element %d: %d\n", i+1, number.elem[i]); + + DestroyList(&number); + + return 0; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/顺序表/sequence.c b/c/dataStructure/线性表/顺序表/sequence.c new file mode 100755 index 0000000..8a26488 --- /dev/null +++ b/c/dataStructure/线性表/顺序表/sequence.c @@ -0,0 +1,151 @@ +#include "sequence.h" + +void InitList(Elem * L) +{ + L->elem = (ElemType *) malloc (sizeof(ElemType) * MAXSIZE); + + if (!(L->elem)) + { + fprintf(stderr,"Initialization Failed\nPlease run as debug mode\n"); + exit(EXIT_FAILURE); + } + + L->length = 0; + + puts("Initialization Successful!"); + printf("You now have %d storage sequence list!\n",MAXSIZE); +} + +void DestroyList(Elem * L) +{ + if (L->elem) + free(L->elem); + else + printf("Sequence list is not exist!\n"); +} + +void AddElem (Elem * L, ElemType e) +{ + if (L->length >= MAXSIZE) + { + printf("No memory for more data\n" + "You could try to release some unused item.\n"); + puts("Add failed"); + } + + else + { + int i = 0; + + while (i < L->length) + i++; + + *(L->elem + i) = e; + L->length++; + } +} + +bool ListEmpty (Elem * L) +{ + return L->length = 0 ? true:false; +} + +ElemType ListLength (Elem * L) +{ + return L->length; +} + +ElemType GetElem (Elem * L, int i) +{ + if (i > L->length) + { + fprintf(stderr,"%d is out of index\n" + "Please keep index between 0 and %d\n", + i, L->length); + return -1; + } + return *(L->elem + i - 1); +} + +ElemType LocateElem (Elem * L, ElemType e) +{ + for (int i = 0; i < L->length; i++) + { + if (e == *(L->elem + i)) + return i + 1; + } + + return 0; +} + +ElemType PriorELem (Elem * L, ElemType e) +{ + ElemType i = 0; + + while (e != *(L->elem + i) && (i < L->length)) + i++; + if (i == 0) + { + printf("The value is at first, so no element before it\n"); + free(L->elem); + exit(EXIT_FAILURE); + } + else if (i >= L->length) + { + printf("The element is not found.\n"); + free(L->elem); + exit(EXIT_FAILURE); + } + return *(L->elem + i - 1); +} + +ElemType NextElem (Elem * L, ElemType e) +{ + ElemType i = 0; + + while (e != *(L->elem + i) && (i < L->length - 1)) + i++; + if (i == L->length - 1) + { + printf("Not found this element in list.\n"); + free(L->elem); + exit(EXIT_FAILURE); + } + return *(L->elem + i); +} + +bool ListInsert (Elem * L, ElemType e, int i) +{ + if (i < 1 || i >= L->length) + { + fprintf(stderr,"Index should be between 0 and %d\n", + L->length); + return false; + } + + for (int n = L->length; n > i - 1; n--) + L->elem[n] = L->elem[n - 1]; + L->elem[i-1] = e; + L->length++; + + return true; +} + +bool ListDelete (Elem * L, int i) +{ + if (i < 1 || i >= L->length) + { + fprintf(stderr,"Index should be between 0 and %d\n", + L->length); + return false; + } + + printf("Element %d has been deleted\n", L->elem[i-1]); + + for (int n = i; n < L->length; n++) + { + L->elem[n-1] = L->elem[n]; + } + L->length--; + return true; +}
\ No newline at end of file diff --git a/c/dataStructure/线性表/顺序表/sequence.h b/c/dataStructure/线性表/顺序表/sequence.h new file mode 100755 index 0000000..6a48d67 --- /dev/null +++ b/c/dataStructure/线性表/顺序表/sequence.h @@ -0,0 +1,32 @@ +#ifndef SEQUENCE_H_ +#define SEQUENCE_H_ + +#define MAXSIZE 100 + +#include<stdio.h> +#include<stdlib.h> +#include<stdbool.h> + +typedef int ElemType; + +typedef struct data { + ElemType * elem; + int length; +} Elem; + +void InitList (Elem * L); +void DestroyList (Elem * L); +void ClearList (Elem * L); +void AddElem (Elem * L, ElemType e); // Add an element, length +1 +bool ListEmpty (Elem * L); +ElemType ListLength (Elem * L); +ElemType GetElem (Elem * L, int i); // Get ith element +ElemType LocateElem (Elem * L, ElemType e); // return element e's position, if not found, return 0 +ElemType PriorElem (Elem * L, ElemType e); // return precedent element of e +ElemType NextElem (Elem * L, ElemType e); // return element after e +bool ListInsert (Elem * L, ElemType e, int i); // insert Elem at i +bool ListDelete (Elem * L, int i); // delete ith element +void TraverseList (Elem * L); // traverse all list +char OperateMenu (void); // show Menu to user + +#endif
\ No newline at end of file |