百度做网站和推广效果怎么样,创意响应式网站建设,银川网站seo,青海西宁制作网站企业功能受限的表结构
一、栈和队列介绍 栈和队列是两种重要的线性结构#xff0c;从数据结构角度#xff0c;他们都是线性表#xff0c;特殊点在于它们的操作被限制#xff0c;也就是所谓的功能受限#xff0c;统称功能受限的线性表 从数据类型角度#xff0c;它们也可以是…功能受限的表结构
一、栈和队列介绍 栈和队列是两种重要的线性结构从数据结构角度他们都是线性表特殊点在于它们的操作被限制也就是所谓的功能受限统称功能受限的线性表 从数据类型角度它们也可以是看成处理、管理数据的一种规则
二、栈结构 栈stack是限定在表尾进行数据的插入、删除等操作的线性表(只允许操作一个端口的数据) 表尾称为栈顶表头称为栈底 当没有元素的空表称为空栈当元素的数量到达栈的容量时称为满栈 添加数据到栈顶中的动作称为入栈、压栈把数据从栈顶中拿出的动作称为出栈、弹栈正因为这个数据的添加、删除的规则所以栈中元素满足先进后出简称FILO表、LIFO 栈结构可以具备的功能 创建 销毁 是否满栈 是否空栈 入栈 出栈 查看栈顶元素 查看元素数量 注意只有顺序栈才有需要判断栈是否满
1、栈结构的顺序实现
// 设计顺序栈结构
typedef struct ArrayStack
{TYPE* ptr; // 存储栈元素的内存首地址size_t cap; // 栈的容量size_t top; // 栈顶的位置
}ArrayStack;
2、栈结构常考笔试题 对一个栈的入栈、出栈序列进行正确性判断 入栈顺序 1 2 3 4 5 出栈顺序1 2 3 4 5 正确 1 2 4 3 5 正确 2 1 5 3 4错误 5 4 3 2 1 编程题实现一个函数判断序列B是否是序列A的出栈顺序 // 判断出栈顺序是否正确
bool is_pop(int* a,int* b,size_t len)
{// 创建一个栈ArrayStack* stack create_array_stack(len);// 按照a顺序入栈for(int i0,j0; ilen; i){ push_array_stack(stack,a[i]);// 按照b的顺序出栈一直出到无法出栈为止int val 0;// 栈非空且栈顶值等于b中要出栈的值 则出栈while(top_array_stack(stack,val) val b[j]){ pop_array_stack(stack);j;}}// 判断栈是否空如果空则是正确顺序bool flag false;if(empty_array_stack(stack))flag true;// 销毁栈destroy_array_stack(stack);return flag;
} 如何让两个长度相同的顺序栈实现空间利用率最大化 两个栈顶的增长方向设置成相对的
3、栈结构的链式实现
#define TYPE int
typedef struct ListNode
{TYPE data;struct ListNode* next;
}ListNode;
ListNode* create_list_node(TYPE data)
{ListNode* node malloc(sizeof(ListNode));node-data data;node-next NULL;return node;
}
// 链式栈结构
typedef struct ListStack
{ListNode* top; // 栈顶指针 指向栈顶节点size_t size; // 节点数量
}ListStack;
// 创建栈
ListStack* create_list_stack(void)
{ListStack* stack malloc(sizeof(ListStack));// 因为栈不允许随意操作插入、删除操作因此不需要头节点stack-top NULL;stack-size 0;return stack;
}
// 栈空
bool empty_list_stack(ListStack* stack)
{}
// 入栈
void push_list_stack(ListStack* stack,TYPE data)
{}
// 出栈
bool pop_list_stack(ListStack* stack)
{}
// 栈顶
TYPE top_list_stack(ListStack* stack)
{}
// 节点数
size_t size_list_stack(ListStack* stack)
{}
// 销毁
void destroy_list_stack(ListStack* stack)
{}
4、栈的应用 内存管理例如栈内存之所以叫栈内存因为它遵循栈的先进后出原则函数调用、函数参数的传参、定义先把数据入栈等结束时逆序出栈函数的调用、结束跳转也是遵循栈结构原则 特殊的算法算术表达式的转换(中缀表达式转后缀表达) 、进制转换、迷宫算法 三、队列结构
1、队列介绍 与栈结构相似的是也只允许在端口处进行添加、删除操作但是有两个端口一个负责添加数据称为入队 该端口称为队尾另一个端口只负责删除数据称为出队该端口称为队头属于一种先进先出结构称为FIFO
2、队列所具备的功能 创建队列 销毁队列 判断队空 判断队满 只有顺序存储时才有 入队 出队 查看队头元素 查看队尾元素 队列元素数量
3、队列的链式实现
#define TYPE int
typedef struct ListNode
{TYPE data;struct ListNode* next;
}ListNode;
ListNode* create_list_node(TYPE data)
{ListNode* node malloc(sizeof(ListNode));node-data data;node-next NULL;return node;
}
// 设计链式队列结构
typedef struct ListQueue
{ListNode* front; // 队头ListNode* rear; // 队尾size_t size; // 节点数量
}ListQueue;
// 创建
ListQueue* create_list_queue(void)
{ListQueue* queue malloc(sizeof(ListQueue));queue-front NULL;queue-rear NULL;queue-size 0;return queue;
}
// 队空
bool empty_list_queue(ListQueue* queue)
{return 0 queue-size;
}
// 入队
void push_list_queue(ListQueue* queue,TYPE data)
{ListNode* node create_list_node(data);if(empty_list_queue(queue)){queue-front node;}else{ queue-rear-next node;queue-rear node;}queue-size;
}
// 出队
bool pop_list_queue(ListQueue* queue)
{if(empty_list_queue(queue)) return false;ListNode* node queue-front;queue-front node-next;free(node);queue-size--;if(0 queue-size) queue-rear NULL;return true;
}
// 队头
TYPE front_list_queue(ListQueue* queue)
{return queue-front-data;
}
// 队尾
TYPE rear_list_queue(ListQueue* queue)
{return queue-rear-data;
}
// 数量
size_t size_list_queue(ListQueue* queue)
{return queue-size;
}
// 销毁
void destroy_list_queue(ListQueue* queue)
{while(pop_list_queue(queue));free(queue);
}
4、队列的顺序实现 顺序队列的队尾下标rear会随着入队而增大rear1队头下标front会随着出队增大front1因为是顺序结构就有随着入队和出队的进行可能超出有效的下标范围如果不进行处理那么队列无法重复使用。 为了避免这种情况当队尾、队头下标达到存储空间的末尾时要想办法让它们回到内存的开头位置相当于把内存想象成一个环形从而可以循环使用队列这样的队列称为循环队列 因此当队尾、队头下标增加时都要对队列的容量求余 rear (rear1)%cap front (front1)%cap
带计数器版本的循环队列 很直接地解决了元素数量的问题 可以直接解决队空、队满的判断矛盾问题 但是在队列结构中会多增加一个数据项并且每次入队、出队操作都要对其进行修改
typedef struct ArrayQueue
{TYPE* ptr; // 存储元素的内存首地址size_t cap; // 容量size_t cnt; // 元素个数 计数器int front; // 队头下标int rear; // 队尾下标
}ArrayQueue;
// 创建
ArrayQueue* create_array_queue(size_t cap)
{ArrayQueue* queue malloc(sizeof(ArrayQueue));queue-ptr malloc(sizeof(TYPE)*cap);queue-cap cap;queue-cnt 0;queue-front 0;qeueu-rear -1; // rear指向队尾元素return queue;
}
// 销毁
void destroy_array_queue(ArrayQueue* queue){}
// 队满
bool full_array_queue(ArrayQueue* queue){}
// 队空
bool empty_array_queue(ArrayQueue* queue){}
// 入队
bool push_array_queue(ArrayQueue* queue,TYPE data){}
// 出队
bool pop_array_queue(ArrayQueue* queue){}
// 队头
TYPE front_array_queue(ArrayQueue* queue){}
// 队尾
TYPE rear_array_queue(ArrayQueue* queue){}
// 数量
size_t size_array_queue(ArrayQueue* queue){}
不带计数器的版本
