外贸soho网站制作,北京活动策划公司排行,订阅号如何开通,永久免费开网店app个人主页#xff1a;点我进入主页 专栏分类#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞#xff0c;评论#xff0c;收藏。 一起努力#xff0c;一起奔赴大厂。 目录 1.前言
2.栈
2… 个人主页点我进入主页 专栏分类C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞评论收藏。 一起努力一起奔赴大厂。 目录 1.前言
2.栈
2.1栈的概念与性质
2.2栈的实现
3.队列
3.1队列的概念
3.2队列的实现
4.练习
4.1编程
4.2概念 1.前言 在前面我们写了关于链表和顺序表的内容我们很容易知道顺序表相当于数组链表是不连续的空间连在一起顺序表和链表是我们学习数据结构的一个重要的基础今天我们主要讲解的是两个重要的结构栈和队列这两个结构既可以使用顺序表实现也可以使用链表实现顺序表和链表哪一个更好呢这需要我们知道栈和队列是如何进行数据的存储的这与他们数据存储的性质有关接下来让我们看看栈与队列的具体实现吧。
2.栈
2.1栈的概念与性质 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶 栈满足数据的先进后出的原则例如我们让12345依次入栈我们出栈先出栈的是数字5。既然栈是先进后出我们用数组进行数据的存储还是用链表进行数据的存储呢先进后出也就是说我们呢访问需要栈知道栈顶的位置但是我们在数据入栈时链表相对来说比较困难所有我们在选择栈的存储时一半使用数组。 2.2栈的实现 在栈的操作中我们包括栈的初始化入栈出栈栈空增容取栈顶元素栈中元素个数遍历释放空间这几个操作。
void InItStack(Stack* s)
{assert(s);s-capacity 4;s-top -1;s-data (char*)malloc(sizeof(char) * s-capacity);
}
void CheckCapacity(Stack* s)
{assert(s);if (s-top 1 s-capacity)s-capacity 2;char* p (char*)realloc(s-data, sizeof(char) * s-capacity);if (p NULL){perror(realloc fail);return;}elses-data p;
}
void StackPush(Stack* s, char ch)
{assert(s);CheckCapacity(s);s-data[s-top] ch;
}
bool StackEmpty(Stack* s)
{assert(s);if (s-top -1)return true;return false;
}
char StackPop(Stack* s)
{assert(s);if (!StackEmpty(s)){s-top--;return s-data[s-top 1];}return 1;
}
void StackDestory(Stack* s)
{assert(s);free(s-data);
}
int StackSize(Stack* s)
{assert(s);return s-top 1;
}
int StackTopdata(Stack* s)
{assert(s);return s-data[s-top];
} 在函数实现时我们有几点需要注意首先我们需要将栈顶初始化为-1主要原因是如果我们初始化为0的话栈为空判断起来比较麻烦初始化为-1就很容易判断。还有就是当我们操作执行完后我们需要将空间进行释放。 3.队列
3.1队列的概念 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 3.2队列的实现 在队列的操作中我们包括对队列的初始化队列节点的创建出队入队取队顶元素对空遍历队列元素个数释放空间。
typedef struct QNode {int data;struct QNode* next;
}QNode;
typedef struct Queue {struct QNode* head;struct QNode* tail;
}Queue;
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-tail NULL;
}
QNode* QueueCreate(Queue* q, int x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}
void QueuePush(Queue* q, int x)
{QNode* newnode QueueCreate(q, x);if (q-head NULL){q-head newnode;q-tail newnode;}else{q-tail-next newnode;q-tail newnode;}
}
bool QueueEmpty(Queue* q)
{return q-head NULL;
}
int QueuePop(Queue* q)
{assert(q);if (!QueueEmpty(q)){int data q-head-data;if (q-head q-tail){free(q-head);q-head q-tail NULL;}else{QNode* cur q-head-next;free(q-head);q-head cur;}return data;}
}
int QueueSize(Queue* q)
{int count 0;QNode* cur q-head;while (cur){count;cur cur-next;}return count;
}
void QueueDestory(Queue* q)
{assert(q);if (!QueueEmpty(q)){QNode* cur q-head-next;QNode* prev q-head;while (prev){free(prev);prev cur;if (cur){cur cur-next;}}}
}
void QueuePrint(Queue* q)
{assert(q);QNode* cur q-head;while (cur){printf(%d , cur-data);cur cur-next;}
}
int top(Queue* q)
{assert(q);if (!QueueEmpty(q)){return q-head-data;}
} 在队列中我们需要注意几点我们在传参数时传的是一级指针我们在前面写链表时我们都是传的二级指针而且我们也是对头指针进行操作为什么会传一级指针呢这主要就是我们创建了两个结构体第一个结构体储存数据第二个结构体储存头尾指针我们传的时第二个结构体的地址传结构体当然是一级指针了为什么在前面我们使用了二级指针呢这主要是我们返回值是void类型我们知道函数在进行传参时会将传送的参数拷贝一份这一份也就是我们在函数中进行操作的数据我们对指针内容进行修改如果修改的不是头指针不会出现任何问题但是我们一旦修改头指针的位置那么就会出现错误。 4.练习 4.1编程 1. 括号匹配问题。OJ链接 2. 用队列实现栈。OJ链接 3. 用栈实现队列。OJ链接 4. 设计循环队列。OJ链接 4.2概念 1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出 栈的顺序是 。 A 12345ABCDE B EDCBA54321 C ABCDE12345 D 54321EDCBA 2.若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1 3.循环队列的存储空间为 Q(1:100) 初始状态为 frontrear100 。经过一系列正常的入队与退队操作 后 frontrear99 则循环队列中的元素个数为 A 1 B 2 C 99 D 0或者100 4.以下( )不是队列的基本运算 A 从队尾插入一个新元素 B 从队列中删除第i个元素 C 判断一个队列是否为空 D 读取队头元素的值 5.现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为(假设 队头不存放数据) A (rear - front N) % N 1 B (rear - front N) % N C ear - front) % (N 1) D (rear - front N) % (N - 1)
