学步园

我把数据结构中常用的数据类型定义汇总了一下,可能有些地方会有疏漏, 欢迎指正.

先看下线性表,单链表,栈和队列

//total
#define OVERFLOW -2
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int status;

//线性表

#define List_Init_Size 100;
#define List_Increment 10;
typedef struct{
 ElemType *elem;
 int length;
 int listsize;
}SqList;

//Initiate
int init_sqlist(SqList &L){
 L.elem=(ElemType *)malloc(List_Init_Size*sizeof(ElemType));
 if (!L.elem) exit(OVERFLOW);
 L.length=0;
 L.listsize=List_Init_Size;
 return OK; 
}

//insert
int insert_elem(SqList &L,ElemType e,int i){
 int n;
 if (i<1||i>L.length-1) then return Error;
 if (L.length>=L.listsize) {
 L.elem=(ElemType *)realloc(L.elem,(listsize+List_Increment)*sizeof(ElemType));
 if (!L.elem) exit(OVERFLOW);
 L.listsize+=List_Increment;
 }
 /*
 q=&L.elem[i-1];
 for (p=&L.elem[L.length-1];p>=q;--p) *(p+1)=*p;
 *q=e;
 */
 for (n=L.length-1;n>=i-1;--n){
  L.elem[n+1]=L.elem[n];  
 }
 L.elem[i-1]=e;
 ++L.length;
 return OK
 };

//delete
int delete_elem(SqlList &L, ElemType &e, int i){
 ElemType p,q;
 if (i<0 || i>L.length-1) return Error;
 q=&L.elem[i-1];
 e=*q;
 for (p=q;p<L.elem[L.length-1];++p) *p=*(p+1);
 --L.length;
 return OK;
 
 } 
 
//Search
int find_elem(SqlList L,ElemType &e,int i){
 e=sq
 }

//单链表
typedef struct LNode{
 Elemtype data;
 struct LNode *next;
}LNode,*LinkList;

int init_linklist(LinkList &L){
 L=(LinkList)malloc(sizeof(LNode));
 L.next=NULL;
 return OK;
 };

status insert_node(LinkList &L, ElemType e, int i){
 int j;
 LNode *p,*q;
 j=1;
 //e=(LNode *)malloc(sizeof(LNode));
 p=L; 
 while (p && j<i){
  p=p->next;
  ++j;
 }
 if (!p||(i<1)) then return Error;
 q=(LinkList)malloc(sizeof(LNode));
 q->data=e;
 q->next=p->next;
 p->next=q;
 return OK;
}

Status delete_node(LinkList &L, int i,ElemType e){
 LNode *p,*q;
 int j; j=1;
 p=L;
 while (p&&j<i) {
  p=p->next;
  ++j;
  };
 if (!p||i<1) then return Error;
 q=p->next;
 p->next=q->next;
 e=q->next;
 free(q); 
 return OK;
 
 }
 
//栈
#define Stack_Init_Size 100

typedef struct{
 Elemtype *base;
 Elemtype *top;
 int stacksize;
}StackList;

int init_statcklist(StackList &S){
 S.base=(ElemType *)malloc(Stack_Init_Size*sizeof(ElemType));
 if (!L.base) exit(OVERFLOW);
 S.base=0;
 S.top=L.base;
 S.stacksize=Stack_Init_Size;
 return OK; //Don't forget
 }
status push(StackList &S, ElemType e){
 //S.top=S.top+1;
 if (S.top-S.base)>=S.stacksize then {
  S.base=(ElemType *)realloc(S.base,(s.stacksize+stackincrement)*sizeof(ElemType));
  if (!S.base) then exit (OVERFLOW);
  S.top=S.base+S.stacksize;
  S.stacksize+=staxkincrement;
 };
 *S.top=e;
 ++S.top;
 //or *S.top++=e; 
 return OK;
 }

Status pop(StackList &s, ElmeType &e){
 if (s.top=s.base) then return Error;
 s.top=s.top-1;
 e=*s.top;
 //e=*--s.top
 return OK;
 }

//队列
#define QLength 100;

typedef struct{
 Elemtype *base;
 int front;
 int rear;
}QList;

Status init_qlist(QList &Q){
 Q.base=(ElemType *)malloc(Maxsize*sizeof(ElemType));
 if (!Q.base) exit(OVERFLOW);
 Q.front=0;
 Q.rear=Q.front;
 return OK;
 }

Status enter_queue(QList &q, ElemType e){
 if (q.rear+1-q.front)%Maxsize=Maxsize then return Error;
 *q.base[q.rear]=e;
 q.rear=(q.rear+1)%Maxsize;
 return OK;
 }  
 
Status del_queue(QList &q, ElemType &e){
 if (q.front=q.rear) then return Error;
 e=*q.base[q.front];
 q.font=(q.font+1)%Maxsize;
 return OK;
 }