initialize

1 files changed, 201 insertions, 0 deletions

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);
+}