DataStucture :Sqlist

Sqlist.c

#include <stdio.h>
#include <stdlib.b>
#define INITSIZE 100
#define INCREMENT 10
#define TRUE 1
#define FALSE 0
#define ElemType int //根据需要改变ElemType指代的类型

/*...ADT Sequence List...*/

/*数据集的定义 类比数组 Array[N]*/
typedef struct Sqlist{
  ElemType *base;//指向基元素的指针
  int listsize;//分配的空间
  int len;//list长度
}Sqlist;

/*Attribution 定义*/
//...Sqlist初始化  类比声明 int a[10]
void InitList(Sqlist *l){
  l->listsize=INITSIZE;
  l->len=0;
  l->base=(ElemType *)malloc(listsize*sizeof(ElemType));
}

//...destroy a sqlist
void DestroyList(Sqlist *l){
  if (l!=NULL){
    l->base=NULL;
    l->len=0;
    l->listsize=0;
  }
}

//...clear a sqlist
void ClearList(Sqlist *l){
  if (l->len!=0)
    l->len=0;
}

//...if empty return 1(TRUE)
int IsEmpty(Sqlist *l){
  return (l->len==0)?True:FALSE;
}

//...get the length of sqlist
int ListLen(Sqlist *l){
  if (l!=NULL)
    return l->len;
}

//...get elem of sqlist
ElemType GetElem(Sqlist *l,int p){
  if (!IsEmpty(l) && p>=0 && p<l->len){
    return l->base[p];//类比 address a+i, elem *(a+i)/a[i]
  }
}

//...insert an elem into sqlist
void Insert(Sqlist *l,int p,ElemType e){
  if(l==NULL)
    InitList(l);
  if (l->len==l->listsize){//存储空间不足 扩大分配空间
    l->listsize+=INCREMENT;
    l->base=(ElemType *)realloc(l->base,(listsize)*sizeof(ElemType));
    if(l==NULL)//if realloc fails return
      return ;
  }
  if (p>len) //如果插入位置超出len，则将元素插入到list 末尾
    p=len;
  ElemType *insert=l->base+p;
  ElemType *iter;
  for (iter=l->base+l->len-1;iter>=insert;iter--)
    *(iter+1)=*(iter);
  *insert=e;
  l->len++;
}

//...print elem of list
void PrintList(Sqlist *l){
  if (l!=NULL){
    ElemType *iter=l->base;
    int i=0;
    while(i<l->len){
      printf("%d ",*(iter+i));
      i++;
    }
  }
}

/*基于sequence list 的算法*/
Sqlist* MergeList(Sqlist *a,Sqlist*b){ // a b are already sorted
  ElemType *pa=a->base,*pb=b->base;//遍历指针
  int la=a->len,lb=b->len;
  ElemType *End_a=a->base+la,*End_b=b->base+lb;//list尾指针

  Sqlist c;//...initialize c
  c.initsize=c.len=la+lb;
  c.base=malloc(initsize*sizeof(ElemType));
  ElemType *pc=c->base;

  while(pa<=End_a && pb<=End_b){
    if (*pa<*pb)
      *pc++ = *pa++;
    else
      *pc++ = *pb++;
  }
  while (pa<=End_a)
    *pc++ = *pa++;
  while (pb<=End_b)
    *pc++ = *pb++;
  return &c;
}

Sqlist * MergeSort(Sqlist *A){//结合MergeList展示 divide and conquer 与 recursive
  if (A->len==1)
    return A;
  else{
    int mid=A->len/2;
    Sqlist a,b;
    a.len=a.initsize=mid;
    a.base=A->base;
    b.len=b.initsize=A->len-mid;
    b.base=A->base+mid;
    return MergeList(MergeSort(&a),Mergesort(&b));
  }
}
int main(){
  /*test*/
  return 0;
}

Arrays are the simplest way to group data; it's no accident that most languages provide efficient and convenient indexed arrays and represent strings as arrays of characters. Arrays are easy to use, provide O( 1) access to any item, work well with binary search and quicksort, and have little space overhead. For fixed-size data sets, which can even be constructed at compile time, or for guaranteed small collections of data, arrays are unbeatable. But maintaining a changing set of values in an array can be expensive, so if the number of elements is unpredictable and potentially large, it may be better to use another data structure.