数据结构------栈和队列
?栈顺序栈 栈在使用时，所需最大空间的大小很难估计，在初始化设空栈时，不应该限定栈的最大容量。 做法为：先为栈分配一个基本容量，使用过程中，当栈的空间不够使用时再逐段扩大。 STACK_INIT_SIZE? 储存空间初始分配量 STACKINCREAMENT? 存储空间分配增量 #include #include /*堆栈的基本操作*/ struct Stack{ int data; struct Stack * next; }; typedef struct Stack * link; typedef struct Stack Snode; /*初始化栈*/ link init(){ link p; p = (link)malloc(sizeof(Snode)); p = NULL; return p; } /*入栈*/ link push(link Head,int x){ link p; p = (link)malloc(sizeof(Snode)); if (p == NULL){ printf("分配内存失败n"); return Head; } p->data = x; p->next = Head; return p; } /*出栈*/ link pop(link Head){ link p; p = Head; if (p == NULL){ printf("栈为空n"); } else{ p = p->next; free(Head); } return p; } /*取栈顶元素*/ int gettop(link Head){ if (Head == NULL){ printf("栈为空n"); return -1; } else{ return Head->data; } } /*判断栈是否为空*/ int empty(link Head){ if (Head == NULL){ return 1; } else return 0; } /*显示栈元素*/ void display(link Head){ link p; p = Head; if (p == NULL){ printf("栈为空n"); } else{ do{ printf("%d",p->data); p = p->next; } while (p != NULL); } } /*释放栈*/ link setnull(link Head){ link p; p = Head; while (p != NULL){ p = p->next; free(Head); Head = p; } return Head; } int main(){ int i,x; link head1; head1 = init(); int n = 0; //link q = (link)malloc(sizeof(Snode)); scanf("%d",&n); for (i = 0; i < n; i++){ scanf("%d",&x); head1 = push(head1,x); } head1 = pop(head1); printf("栈顶元素为:%dn",gettop(head1)); if (empty(head1) == 1){ printf("栈为空n"); } else printf("栈不为空n"); display(head1); display(setnull(head1)); return 0; } 队列#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; typedef int QElemType; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; //队列的链表结构 typedef struct{ QueuePtr front;//队头 QueuePtr rear;//对尾 }LinkQueue; Status visit(QElemType e){ printf("%d ",e); return OK; } //初始化空的队列 Status InitQueue(LinkQueue *Q){ Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q->front) exit(OVERFLOW); Q->front->next =NULL; return OK; } //销毁队列 Status DestroyQueue(LinkQueue *Q){ while(Q->front){ Q->rear=Q->front->next;//从队头开始销毁 free(Q->front); Q->front = Q->rear; } return OK; } //清空队列，队头指针还在 Status ClearQueue(LinkQueue *Q){ QueuePtr p,q; Q->rear =Q->front;//跟初始状态相同，Q->rear指向头结点 p=Q->front->next;//开始销毁队头元素，队头，对尾依然保留 Q->front->next =NULL; while(p){ q=p; p=p->next; free(q); } return OK; } //队列是否空 Status QueueEmpty(LinkQueue Q){ if(Q.front == Q.rear) return TRUE; else return FALSE; } //取队列长度 int QueueLength(LinkQueue Q){ int i=0; QueuePtr p = Q.front; while(Q.rear != p){ i++; p = p->next; } return i; } //获取队头元素 Status GetHead(LinkQueue Q,QElemType *e){ QueuePtr p; if(Q.front == Q.rear)//队空 return ERROR; p=Q.front->next; *e = p->data; return OK; } //对尾插入元素 Status EnQueue(LinkQueue *Q,QElemType e){ QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if(!s) exit(OVERFLOW); s->data = e; s->next =NULL; Q->rear->next =s;//原来对尾的next指向新的元素 Q->rear =s;//将新元素变为对尾 return OK; } //队头元素出队 Status DeQueue(LinkQueue *Q,QElemType *e){ QueuePtr p; if(Q->front == Q->rear) return ERROR; p=Q->front->next;//ｐ指向队头元素 *e = p->data; Q->front->next = p->next;//头结点的后继指向队头的下一个元素 if(Q->rear == p){//队头等于对尾了 Q->rear = Q->front;//对尾指向头结点 } free(p); return OK; } //遍历元素 Status QueueTraverse(LinkQueue Q){ QueuePtr p; p=Q.front->next; while(p){ visit(p->data); p=p->next; } printf("n"); return OK; } int main(){ int i; QElemType d; LinkQueue q; i=InitQueue(&q); //入队１０个元素 for(int index=0;index EnQueue(&q,index); } QueueTraverse(q); DestroyQueue(&q); printf("队列已经销毁,q.front=%p q.rear=%pn",q.front,q.rear); return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |