高端医疗器械网站源码,网页设计规范字号选择相对正确的是,八亿wap建站,做网站推广有啥活动前面学习了两种最基本的数据结构 -- 顺序表和链表#xff0c;接下来就可以基于这两种数据结构来实现其他数据结构了。其实#xff0c;其他的数据结构的物理结构要么是数组#xff0c;要么就是链表#xff0c;所以学好顺序表和链表是学好其他数据结构的基础。接下里#xf… 前面学习了两种最基本的数据结构 -- 顺序表和链表接下来就可以基于这两种数据结构来实现其他数据结构了。其实其他的数据结构的物理结构要么是数组要么就是链表所以学好顺序表和链表是学好其他数据结构的基础。接下里我们就来看一个新的数据结构 -- 栈。 目录
1 栈的概念与特点
2 栈的结构
1 逻辑结构
2 物理结构 3 栈的基本操作的实现
1 初始化和销毁
2 入栈与出栈、
1 入栈
2 出栈
3 取栈顶元素、判空、获取有效元素个数
4 代码 重点一 栈的特点
1 栈的概念与特点 栈一种特殊的线性表其只允许在一端进行插入和删除数据。插入和删除数据的一端叫做栈顶另一端叫做栈底。 入栈压栈往栈中插入数据的操作叫做入栈。 出栈栈中删除数据的操作叫做出栈。 特点栈中的数据遵循LIFO原则(last in first out)也就是后进先出原则。 栈的特点特别重要一般使用栈都是因为其后进先出的特点下面来做一个题来理解一下其后进先出的特点
假设有一个栈数据入栈的先后顺序为 a b c d e 请在以下选项中选出错误的出栈顺序A. a b c d e B. c b d a eC. d b c a e D. e d c b a 该题的正确答案为 C因为如果 d 先出栈的话说明 abc 均以入栈如何要接着出栈的话应是 c 先出栈而不是 b 先出栈。 需要注意的一点就是出栈顺序并不是等数据全部入栈之后才能出栈。比如 A 选项就是入栈一个数据然后出栈一个数据。 重点二 栈的结构
2 栈的结构
1 逻辑结构 我们可以把栈想象成以下的一个结构
2 物理结构 栈的物理结构既可以选择用链式结构来实现也可以选择用数组也就是顺序表来实现。这里选择使用数组来实现因为栈后进先出的特性规定了其只能在尾部进行插入和删除数据而对于顺序表来说在尾部插入和删除数据又十分方便所以这里选择使用顺序表来实现栈。 既然是使用顺序表来实现栈所以栈的结构和顺序表十分相似只不过就是把 size 变为了 top用来表示栈的顶部元素的位置
//将int定义为栈里面的数据类型
typedef int STDataType;
//栈的结构
typedef struct Stack
{STDataType* arr;//栈中的存放数据的数组int capacity;//栈的容量大小int top;//栈顶
}ST;重点三 实现栈 3 栈的基本操作的实现 对于一个栈来说其主要操作只有入栈、出栈、取栈顶元素、初始化、销毁、判空、获取有效元素个数。
1 初始化和销毁 栈的初始化和销毁与顺序表可以说是一模一样这里就不做多余讲解可以去回顾一下顺序表也可以看下面代码理解一下。 2 入栈与出栈、
1 入栈 入栈的操作就相当于顺序表中的尾差其基本过程如图所示
可以看到就是顺序表的尾插操作只不过就是把 size 变成了 capacity 而已。
2 出栈 出栈就是顺序表的尾删所以只需要让 --top 就可以了。 3 取栈顶元素、判空、获取有效元素个数 这3个操作的实现都很简单。取栈顶元素就是返回 arr 数组中 top - 1 下标的数据但要注意栈要非空才能返回栈顶元素所以要先对栈是否为空断言判空就是判断 top 是否等于0获取有效元素个数就是返回 top 。 4 代码
Stack.h文件
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;int top;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);
Stack.c文件
#includeStack.h//初始化
void STInit(ST* ps)
{assert(ps);ps-arr NULL;ps-capacity ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-capacity ps-top 0;
}//入栈
void STPush(ST* ps, STDataType x)
{//相当于顺序表的尾插assert(ps);//如果数组满了。需要增容if (ps-capacity ps-top){int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail\n);exit(1);}ps-arr tmp;ps-capacity newCapacity;}//不要忘记让topps-arr[ps-top] x;
}
//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);//判断top是否为0就可以了return ps-top 0;
}
//出栈
void STPop(ST* ps)
{//相当于顺序表的尾删assert(!STEmpty(ps));--ps-top;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//栈不能为空assert(!STEmpty(ps));//只取栈顶元素不删除数据int pos ps-top - 1;return ps-arr[pos];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
test.c文件
#includeStack.h
void Test4()
{ST st;STInit(st);//测试入栈STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);for (int i 0; i st.top; i){printf(%d , st.arr[i]);}printf(\n);//测试出栈与取栈顶元素STPop(st);STPop(st);STPop(st);STPop(st);//STPop(st);/*int ret STTop(st);printf(%d , ret);printf(\n);for (int i 0; i st.top; i){printf(%d , st.arr[i]);}printf(\n);*/bool ret1 STEmpty(st);if (ret1){printf(栈为空\n);}else{printf(栈不为空\n);}int ret STSize(st);printf(%d , ret);STDestroy(st);
}
int main()
{Test4();return 0;
} 可以看到实现栈其实就是实现顺序表的部分接口学好顺序表和链表是实现其他数据结构的基础。所以一定要把基础学扎实才能越学越好。
