数据结构 |
您所在的位置：网站首页 › 栈顶指针为0时,栈内元素有 › 数据结构 |
数据结构
|
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶,而不是栈底。 1.2 特性它的特殊之处在于限制了这个线性表的插入和删除的位置，它仅限于插入和删除数据元素的操作在栈顶，另一端为栈底。 1.3 操作栈的插入操作，叫做进栈，也成压栈。 栈的删除操作，叫做出栈，也有的叫做弹栈，退栈。 1.4 应用实例 建筑房子时砌砖。一个一个砌上去，一个一个取下来。访问浏览器。在点击页面加载，或者后退返回。 2、栈的存储 2.1 顺序存储顺序栈是一个预设的足够长度的一维数组和一个记录栈顶位置的变量。 2.2 栈操作 空栈：top=-1；入栈：top-1，栈顶指针指针移动至栈顶；出栈：top+1，栈顶指针移动至原栈顶的下一个元素；满栈：top=栈长度-1。 2.3 基本操作main.c #include #include #include #include "stackList.h" int main() { SeqStack* Stack = Init_SeqStack(); int i1 = 3, i2 = 6, i3 = 9, i4=10; Push_SeqStack(Stack, &i1); Push_SeqStack(Stack, &i2); Push_SeqStack(Stack, &i3); Push_SeqStack(Stack, &i4); Display(Stack); Pop_SeqStack(Stack); Display(Stack); int data = *(int *)Get_SeqStack(Stack); printf("栈顶元素为：%d", data); return 0; }stackList.c #include "stackList.h" /* 功能：初始化栈 */ SeqStack* Init_SeqStack() { SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack*)*MAXLEN); if (stack == NULL) return NULL; memset(stack, 0, sizeof(SeqStack*)*MAXLEN); stack->size = -1; return stack; } /* 功能：判断栈空 返回值： · NULL：该栈不存在； · 0：为空栈； · 1：不为空。 */ int Judge_SeqStackNull(SeqStack* Stack) { if (Stack == NULL) return NULL; if (Stack->size == -1) return 0; return 1; } /* 功能：判断栈满 返回值： · NULL：该栈不存在； · 0：为满栈； · 1：栈不为满栈。 */ int Judge_SeqStackFull(SeqStack* Stack) { if (Stack == NULL) return NULL; if (Stack->size == MAXLEN - 1) return 1; return 0; } /* 功能：进栈 */ void Push_SeqStack(SeqStack* Stack, void* data) { if (Judge_SeqStackFull(Stack)) { printf("满栈，不能进栈！"); return; } Stack->size++; Stack->data[Stack->size] = data; } /* 功能：出栈 */ void Pop_SeqStack(SeqStack* Stack) { if (Stack == NULL) return; if (!Judge_SeqStackNull(Stack)) { printf("空栈，不能出栈！"); return; } Stack->data[Stack->size] = NULL; Stack->size--; } /* 功能：去栈顶 */ void* Get_SeqStack(SeqStack* Stack) { if (Stack == NULL) return NULL; if (Stack->size == -1) return NULL; void* x = Stack->data[Stack->size]; return x; } void Display(SeqStack* Stack) { int i; for (i = 0; i size+1; i++) { printf("%5d", *(int *)Stack->data[i]); } printf("\n"); } void Destroy_SeqStack(SeqStack *Stack) { if (Stack != NULL) { free(Stack); } }stack.h #pragma once #include #include #include #ifdef __cplusplus extern "C" { #endif #define MAXLEN 1024 typedef struct SeqStack { void* data[MAXLEN]; // 存储数据 int size; // 存储数据个数 }; // 初始化栈 SeqStack* Init_SeqStack(); // 判断栈空 int Judge_SeqStackNull(SeqStack*); // 判断栈满 int Judge_SeqStackFull(SeqStack*); // 进栈 void Push_SeqStack(SeqStack*, void*); // 出栈 void Pop_SeqStack(SeqStack*); // 取栈顶 void* Get_SeqStack(SeqStack*); // 打印栈 void Display(SeqStack*); // 销毁释放内存 void Destroy_SeqStack(SeqStack*); #ifdef __cplusplus } #endif运行结果 main.c #include #include #include "StackLink.h" int main() { StackLink* stack = Init_StackLink(); stack = Push_StackLink(stack, 1); stack = Push_StackLink(stack, 2); stack = Push_StackLink(stack, 3); printf("栈内元素为：\n"); Display(stack); int top = Get_Top(stack); printf("栈顶元素为：%d", top); Distory(stack); return 0; }StackLink.c #include "StackLink.h" StackLink* Init_StackLink() { StackLink* stack; stack = NULL; return stack; } // 判断栈空 int Judge_isNull(StackLink* stack) { if (stack == NULL) return 1; return 0; } // 进栈 StackLink* Push_StackLink(StackLink* stack, int data) { StackLink* temp = (StackLink*)malloc(sizeof(StackLink*)); temp->data = data; temp->next = stack; stack = temp; return stack; } // 出栈 StackLink* Pop_StackLink(StackLink* stack) { if (Judge_isNull(stack)) return NULL; stack = stack->next; return stack; } //取栈顶 int Get_Top(StackLink* stack) { if (Judge_isNull(stack)) return NULL; int x = stack->data; return x; } //显示函数 void Display(StackLink* stack) { if (Judge_isNull(stack)) return ; while (stack != NULL) { printf("%5d", stack->data); stack = stack->next; } printf("\n"); } // 链表销毁 void Distory(StackLink* stack) { if (stack != NULL) { free(stack); } }StackLink.h #pragma once #include #include typedef struct LinkNode { int data; struct LinkNode* next; }StackLink; #ifdef __cplusplus extern "C" { #endif // __cplusplus // 初始化 StackLink* Init_StackLink(); // 判断栈空 int Judge_isNull(StackLink*); // 进栈 StackLink* Push_StackLink(StackLink*, int data); // 出栈 StackLink* Pop_StackLink(StackLink*); //取栈顶 int Get_Top(StackLink*); //显示函数 void Display(StackLink*); // 链表销毁 void Distory(StackLink*); #ifdef __cplusplus } #endif // __cplusplus运行结果 1. 对于栈操作数据的原则是 A. 先进先出 B.后进先出 C.后进先出 D.不分顺序 2. 有6个元素按6,5,4,3,2,1的顺序进栈, 问下列()不是合法的出栈序列? A.543612 B.453126 C.346521 D.234156 3.插入和删除只能在一端进行的线性表，称为() A.队列 B.循环队列 C.栈 D.循环栈 4.输入序列为ABC，可变为CBA时，经过的栈操作为() A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop 5.没有编号为1,2,3,4 的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为() A.1234 B.1243 C.1324 D.1423 6.如果以链表作为栈的存储结构，则出栈操作时()。 A.必须判别栈是否满 B.必须判别栈是否空 C.必须判别栈元素类型 D.队栈可不做任何判别 7.顺序栈存储空间的实现使用( )存 储栈元素。 A.链表 B.数组 C.循环链表 D.变量 8.在C语言中，一个顺序栈一旦被声明，其占用空间的大小()。 A.已固定 B.不固定 C.可以改变 D.动态变化 9.从一个栈顶指针为top的链栈中删除一一个结点时， 用x保存被删除的结点，应执行下列( )命令。 A. x=top;top=top->next; B. top-top->next;x-top->data; C. x-top->data; D. x=top->data;top=top- >next; 10.4个元素按A,B,C,D顺序进S栈，执行两次Pop(S,x)运算后，栈顶元素的值是() A. A B. B C. C D. D 11.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列( ) 命令。 A. HS->next= S; B. S->next=HS->next;HS->next=S; C. S->next= HS- next;HS=S; D. S->next=HS;HS=HS~>next; 12.向顺序栈中压入元素时( )。 A.先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素 C.谁先谁后无关紧要 D.同时进行 13. 一个栈的入栈次序ABCDE,则栈的不可能的输出序列是()。 A. EDCBA B. DECBA C. DCEAB D. ABCDE 14.设有一个顺序栈s,元素A.B.C,D,EF依次进栈，如果6个元素出栈的顺序是B,D,C,F.E,A,则栈的容量至少应是() A.3 B.4 C.5 D.6 二、填空题1.对于栈只能在____下位置插入和删除元素； 2.在顺序栈中，当栈项指针top=-1时，表示____； 3.在有n个元素的栈中，进栈操作的时间复杂度为____； 4.在栈中，出栈操作的时间复杂度为:____； 5.在一个链栈中，若栈顶指针等于NULL，则表示____； 6.向一个栈顶指针为top的链栈插入一一个新结点*p时，应执行____和____操作； 7.已知顺序栈S，在对s进行进栈操作之前首先要判断____； 8.已知顺序栈S，在对S进行出栈操作之前首先要判断____； 9. 4个元素按A,B,C,D顺序进S栈，执行两次Pop (S, X)运算后，x的值是____；
几种术语 入队：在队尾插入操作；出队：在队头删除操作；空队：没有任何元素。 2、存储方式 2.1 顺序存储队列中的顺序存储使用的较少。存在一个缺陷【假溢出】：在每次出队的时候front指针都会像前移动，导致前面被取出数据的空间造成假溢出的现象。 在队列中，入队 - rear、出队 - front。 2.2 循环队列main.c #include #include #include "QueuList.h" int main() { SeqQueue* Queue = Init_SeqQueue(); Entry_SeqQueue(Queue, 1); Entry_SeqQueue(Queue, 4); Entry_SeqQueue(Queue, 5); Entry_SeqQueue(Queue, 7); Entry_SeqQueue(Queue, 9); Display(Queue); Delete_SeqQueue(Queue); Display(Queue); //Destroy(Queue); return 0; }CirqueueList.c #include "QueuList.h" // 初始化 SeqQueue* Init_SeqQueue() { SeqQueue* Queue = (SeqQueue*)malloc(sizeof(SeqQueue*)*MAXLEN); Queue->front = Queue->rear = 0; return Queue; } // 判断是否为空 int Judge_isNull(SeqQueue* Queue) { if (Queue == NULL || Queue->front == Queue->rear) { return 1; } return 0; } // 入队 void Entry_SeqQueue(SeqQueue* Queue, int data) { if (Queue == NULL || data == NULL) { return; } // 队是否满 if (Queue->front == (Queue->rear + 1) % MAXLEN) { printf("队满..."); return; } Queue->rear = Queue->rear + 1; Queue->data[Queue->rear] = data; } // 出队 void Delete_SeqQueue(SeqQueue* Queue) { if (Judge_isNull(Queue)) { printf("队空..."); return; } Queue->front = Queue->front + 1; int x = Queue->data[Queue->front]; } // 取队头 int Get_Head(SeqQueue* Queue) { if (Judge_isNull(Queue)) { printf("对空..."); return NULL; } int x = Queue->data[Queue->front + 1]; // 取出数据 return x; } // 显示 void Display(SeqQueue* Queue) { int temp = Queue->front; // 用来暂存front指向，保证在循环中指向不被改变 if (Judge_isNull(Queue)) { return; } while (temp != Queue->rear) { printf("%5d", Queue->data[temp+1]); temp++; } printf("\n"); } // 释放内存 void Destroy(SeqQueue* Queue) { if (Queue != NULL) { free(Queue); Queue = NULL; } }CirQueueList.h #pragma once #include #include /* 循环队列中的几种情况： 空队：rear = front = 0 满队：(rear+1)%MAXLEN = front */ #define MAXLEN 100 typedef struct { int data[MAXLEN]; int front; int rear; }SeqQueue; #ifdef __cplusplus extern "C" { #endif // __cplusplus // 初始化 SeqQueue* Init_SeqQueue(); // 判断是否为空 int Judge_isNull(SeqQueue*); // 入队 void Entry_SeqQueue(SeqQueue*, int); // 出队 void Delete_SeqQueue(SeqQueue*); // 取队头 int Get_Head(SeqQueue*); // 显示 void Display(SeqQueue*); // 释放内存 void Destroy(SeqQueue*); #ifdef __cplusplus } #endif // __cplusplus运行结果 main.c #include #include #include "QueueLink.h" int main() { QueueLink* queue = Init_QueueLink(); Entry_QueueLink(queue, 3); Entry_QueueLink(queue, 4); Entry_QueueLink(queue, 1); Entry_QueueLink(queue, 7); printf("入队后\n:"); Display(queue); int x = Get_Head(queue); printf("队头为：%d\n", x); Delete_QueueLink(queue); printf("出队后\n:"); Display(queue); //Distory(queue); return 0; }QueueLink.c #include "QueueLink.h" // 初始化 QueueLink* Init_QueueLink() { // 创建头结点 QueueLinkQ* head; QueueLink* queue; head = (QueueLinkQ*)malloc(sizeof(QueueLinkQ*)); queue = (QueueLink*)malloc(sizeof(QueueLink*)); queue->front = head; queue->rear = head; return queue; } // 判断对空 int Judge_isNull(QueueLink *queue) { if (queue->front == queue->rear) { return 1; } return 0; } // 出队 void Delete_QueueLink(QueueLink* queue) { if (Judge_isNull(queue)) { return; } /* * 注意队头是指向队头的前一个结点 * 头结点 != 队头；头结点为队头的前一个结点 */ QueueLinkQ* q; // 用来保存原来的头结点 q = queue->front->next; // 取出对头结点 int x = q->data; queue->front->next = q->next; // 将头结点的下一个结点指向对头的下一个结点 } // 入队 void Entry_QueueLink(QueueLink*queue, int data) { QueueLinkQ* q = (QueueLinkQ*)malloc(sizeof(QueueLinkQ*)); q->data = data; q->next = NULL; queue->rear->next = q; queue->rear = q; // 此时不是赋值，而是将队尾指针移动到队尾 } // 取对头 int Get_Head(QueueLink* queue) { int x = queue->front->next->data; return x; } // 显示 void Display(QueueLink* queue) { if (queue == NULL) return; QueueLinkQ *temp = queue->front->next; while (temp != NULL) { printf("%5d", temp->data); temp = temp->next; } printf("\n"); } // 释放空间 void Distory(QueueLink* queue) { if (queue != NULL) { free(queue); queue = NULL; } }QueueLink.h #pragma once #include #include // 用来生成新节点 typedef struct QueueNode { int data; struct QueueNode* next; }QueueLinkQ; // 链表 typedef struct { QueueLinkQ* front; QueueLinkQ* rear; }QueueLink; #ifdef __cplusplus extern "C" { #endif // __cplusplus // 初始化 QueueLink* Init_QueueLink(); // 判断对空 int Judge_isNull(QueueLink, int); // 出队 void Delete_QueueLink(QueueLink*); // 入队 void Entry_QueueLink(QueueLink*, int); // 取对头 int Get_Head(QueueLink*); // 显示 void Display(QueueLink*); // 释放空间 void Distory(QueueLink*); #ifdef __cplusplus } #endif // __cplusplus运行结果 在系统中，多个进程满足运行条件，即可用队列来管理。若需要运行该进程，则插入队列。等待运行。 3.2 队列的数据管理应用可设定一个队列缓冲区用来缓冲数据，将数据切块添加到该缓冲区，可保证数据的次序。 3.3 队列的优先级任务队列的优先级，可根据权值大小来定。通过权值来确定谁先入队，从而进行操作。 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |