c/c++ 线性栈

c/c++ 链栈

链栈

下的代码实现了以下职能

函数 功能描述
push 压入
pop 弹出
show_list 打印
clear 释放所有内存空间
destroy 释放所有内存空间

nodestack.h

#ifndef __NODESTACK__
#define __NODESTACK__

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct Node{
  ElemType data;
  struct Node *next;
}Node;

typedef struct nodestack{
  int size;
  Node *base;
  Node *top;
}nodestack;

void init(nodestack*);
void push(nodestack*, ElemType);
void show_list(nodestack*);
void pop(nodestack*);
int length(nodestack*);
void clear(nodestack*);
void destroy(nodestack*);
#endif

nodestack.c

#include "nodestack.h"

Node* createNode(ElemType val){
  Node* n = (Node*)malloc(sizeof(Node));
  n->data = val;
  n->next = NULL;
  return n;
}
void init(nodestack* stack){
  stack->size = 0;
  stack->top = NULL;
  stack->base = NULL;
}
void push(nodestack* stack, ElemType x){
  Node* n = createNode(x);
  //当栈为空的时候
  if(stack->base == NULL){
    stack->top = stack->base = n;
    n->next = NULL;
    stack->size++;
    return;
  }
  n->next = stack->top;
  stack->top = n;
  stack->size++;
}
void show_list(nodestack* stack){
  Node* top = stack->top;
  while(top != NULL){
    printf("%d\n", top->data);
    top = top->next;
  }
}
void pop(nodestack* stack){
  if(stack->size == 0)return;

  Node* n = stack->top;
  stack->top = stack->top->next;
  free(n);
  stack->size--;
}
int length(nodestack* stack){
  return stack->size;
}
void clear(nodestack* stack){
  Node* top = stack->top;
  Node* tmp;
  while(top != NULL){
    tmp = top;
    top = top->next;
    free(tmp);
  }
  stack->top = stack->base = NULL;
  stack->size = 0;
}
void destroy(nodestack* stack){
  clear(stack);
}

nodestackmain.c

#include "nodestack.h"

int main(){
  nodestack list;
  init(&list);
  int select = 1;
  ElemType item;
  int index;
  while(select){
    printf("*****************************************\n");
    printf("*** [1]   push        [2]  pop        ***\n");
    printf("*** [3]   show_list   [4]  length     ***\n");
    printf("*** [5]   clear       [6]  destroy    ***\n");
    printf("*** [0]   quit                        ***\n");
    printf("*****************************************\n");
    printf("请选择:>");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("请输入要插入的数据>\n");
      scanf("%d",&item);
      push(&list, item);    
      show_list(&list);
      break;
    case 2:
      pop(&list);   
      show_list(&list);
      break;
    case 3:
      show_list(&list);
      break;
    case 4:
      printf("length is %d\n", length(&list));
      show_list(&list);
      break;
    case 5:
      clear(&list);
      show_list(&list);
      break;
    case 6:
      destroy(&list);
      break;
    default:
      printf("输入的选择错误,请重新选择\n");
      break;
    }
  }
  destroy(&list);
}

c/c++ 线性栈

线性栈

脚的代码实现了以下职能

函数 功能描述
push 压入
pop 弹出
show_list 打印
clear 移动top指针到栈底
destroy 释放所有内存空间

seqstack.h

#ifndef __SEQSTACK__
#define __SEQSTACK__

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>

#define SEQSTACK_INIT_SIZE 8
#define ADD_SIZE 1000

typedef int ElemType;

typedef struct seqstack{
  int size;
  ElemType *base;
  ElemType *top;
}seqstack;

void init(seqstack*);
void push(seqstack*, ElemType);
void show_list(seqstack*);
void pop(seqstack*);
int length(seqstack*);
void clear(seqstack*);
void destroy(seqstack*);
#endif

seqstack.c

#include "seqstack.h"

bool reInit(seqstack* seq){
  ElemType* new = (ElemType*)realloc(seq->base, ADD_SIZE *sizeof(ElemType));
  if(NULL == new)return true;
  if(seq->base != new){
    seq->base = new;
    seq->top = seq->base + seq->size + 1;
  }
  return false;
}
void init(seqstack* seq){
  ElemType* e = (ElemType*)malloc(sizeof(ElemType) * SEQSTACK_INIT_SIZE);
  seq->base = seq->top = e;
  seq->size = 0;
}
void push(seqstack* seq, ElemType x){
  if(seq->size >= SEQSTACK_INIT_SIZE && reInit(seq)){
    printf("stack is full\n");
    return;
  }
  //先赋值,后移动top的指向
  *((seq->top)++) = x;
  seq->size++;
}
void show_list(seqstack* seq){
  ElemType* e = seq->top;
  while(e-- != seq->base){
    printf("%d\n",*e);
  }
}
void pop(seqstack* seq){
  --seq->top;
  seq->size--;
}
int length(seqstack* seq){
  return seq->size;
}
void clear(seqstack* seq){
  seq->top = seq->base;
  seq->size = 0;
}
void destroy(seqstack* seq){
  free(seq->base);
}

seqstackmain.c

#include "seqstack.h"

int main(){
  seqstack list;
  init(&list);
  int select = 1;
  ElemType item;
  int index;
  while(select){
    printf("*****************************************\n");
    printf("*** [1]   push        [2]  pop        ***\n");
    printf("*** [3]   show_list   [4]  length     ***\n");
    printf("*** [5]   clear       [6]  destroy    ***\n");
    printf("*** [0]   quit                        ***\n");
    printf("*****************************************\n");
    printf("请选择:>");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("请输入要插入的数据>\n");
      scanf("%d",&item);
      push(&list, item);    
      show_list(&list);
      break;
    case 2:
      pop(&list);   
      show_list(&list);
      break;
    case 3:
      show_list(&list);
      break;
    case 4:
      printf("length is %d\n", length(&list));
      show_list(&list);
      break;
    case 5:
      clear(&list);
      show_list(&list);
      break;
    case 6:
      destroy(&list);
      break;
    default:
      printf("输入的选择错误,请重新选择\n");
      break;
    }
  }
  destroy(&list);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图