linkedlist.c

压缩包里面的都是精致的基本C语言小程序

#include <stdio.h>
#include "mystdlib.h"
#include "poly.h"
#include "error.h"
#include "commonInter.h"
#include "linkedList.h"


static int size (linkedList l);

linkedList newLinkedList ()
{
  linkedList l = checkedMalloc (sizeof (*l));
  l->data = NULL;
  l->next = NULL;
  return l;
}

linkedList newLinkedList2 (poly x, linkedList l)
{
  linkedList t = checkedMalloc (sizeof (*t));
  t->data = x;
  t->next = l;
  return t;
}

int linkedListIsEmpty (linkedList l)
{
  return (NULL==l->next);
}

poly linkedListHead (linkedList l)
{
  if (l->next)
    return l->next->data;
  else 
    return NULL;
}

linkedList linkedListTail (linkedList l)
{
  if (l->next)
    return l->next->next;
  else
    return NULL;
}

static int size (linkedList l)
{
  if (l==NULL)
    return 0;
  else 
    return size (l->next) + 1;
}

int linkedListSize (linkedList l)
{
  return size (l->next);
}

void linkedListInsert (linkedList l, poly x, int i)
{
  if (i<0 || i>linkedListSize (l))
    error ("index out of bound\n");

  linkedList p = l;
  int j = -1;
  while (p && j!=i-1)
  {
    p = p->next;
    j++;
  }
  linkedList temp = newLinkedList2 (x, p->next);
  p->next = temp;
  return;
}

void linkedListInsertHead (linkedList l, poly x)
{
  linkedListInsert (l, x, 0);
  return;
}

void linkedListInsertTail (linkedList l, poly x)
{
  linkedListInsert (l, x, linkedListSize (l));
  return;
}

poly linkedListDelete (linkedList l, int i)
{
  if (i<0 || i>= linkedListSize (l))
    error ("index out of bound\n");
  
  linkedList p = l;
  linkedList q;
  int j = -1;
  while (p && j!=i-1)
  {
    p = p->next;
    j++;
  }
  if (p->next)
  {
    q = p->next;
    p->next = p->next->next;
    return (q->data);
  }
  else;

  return NULL;
}

poly linkedListDeleteHead (linkedList l)
{
  return linkedListDelete (l, 0);
}

poly linkedListDeleteTail (linkedList l)
{
  return linkedListDelete (l, linkedListSize (l) -1);
}

void linkedListForeach (linkedList l, void (*f)(poly))
{
  linkedList p = l->next;
  
  while (p)
  {
    f (p->data);
    p = p->next;
  }
  return;
}

poly linkedListPeek (linkedList l, int (*f)(poly))
{
  linkedList p = l->next;
  
  while (p)
  {
    if ((f (p->data)))
      return p->data;
    else
      p = p->next;
  }
  return NULL;
}


void linkedListOutput (linkedList l)
{
  linkedList p = l->next;
  strOutput2 ("[");

  while (p)
  {
    strOutput (((commonInter)p->data)->vft->toString(p->data));
    strOutput2 (", ");
    p = p->next;
  }
  strOutput2 ("]");

  return;
}

void linkedListDeleteAll (linkedList l, int (*f)(poly))
{
  linkedList p = l->next;
  linkedList newList = newLinkedList ();
  linkedList temp;
  
  while (p)
  {
    if (f (p->data))
    {
      temp = p;
      p = p->next;
      checkedFree (temp);
    }
    else
    {
      temp = p;
      linkedListInsertTail (newList, p->data);
      p = p->next;
      checkedFree (temp);
    }
  }
  l->next = newList->next;
  return;
}

linkedList linkedListMap (linkedList l, poly (*map) (poly))
{
  linkedList temp = newLinkedList ();
  
  linkedList cursor = l->next;

  while (cursor)
  {
    poly newData = map (cursor->data);
    linkedListInsertTail (temp, newData);
    cursor = cursor->next;
  }
  return temp;
}

void linkedListDestroy (linkedList l)
{
  linkedList temp;
  
  while (l)
  {
    temp = l->next;
    checkedFree (l);
    l = temp;
  }
  //printf ("linked list destroyed!\n");
  
  return;  
}

linkedList linkedListReverse (linkedList l)
{
  linkedList temp = newLinkedList ();
  
  linkedList t = l->next;
  
  while (t)
  {
    linkedListInsertHead (temp, t->data);
    t = t->next;
  }
  
  return temp;
}

linkedList linkedListGetFirst (linkedList l)
{
  return l->next;
}

int linkedListEquals (linkedList l1, linkedList l2)
{
  return l1==l2;  
}