北京公司网站建设费用,wordpress 图册,深圳系统网站开发,扬州市市政建设处网站栈
栈的基本概念
定义 栈是只允许在一端进行插入或删除操作的线性表栈顶#xff1a;线性表允许进行插入删除的那一端栈底#xff1a;固定的#xff0c;不允许进行插入和删除的另一端空栈#xff1a;不含任何元素特点#xff1a;后进先出#xff08;LIFO#xff09; 基…栈
栈的基本概念
定义 栈是只允许在一端进行插入或删除操作的线性表栈顶线性表允许进行插入删除的那一端栈底固定的不允许进行插入和删除的另一端空栈不含任何元素特点后进先出LIFO 基本操作 InitStack(S)初始化一个空栈SStackEmpty(S)判断一个栈是否为空若栈S为空则返回true否则返回falsePush(S,x)进栈若栈S未满则将x加入使之成为新栈顶Pop(S,%x)出栈若栈S非空则用x返回栈顶元素GetTop(S,x)读栈顶元素若栈S非空则用x返回栈顶元素DestroyStack(S)销毁栈并释放栈S占用的存储空间 卡特兰数n个不同元素进栈出栈元素的不同排列的个数为 1 n 1 C 2 n n \frac{1}{n1}C^n_{2n} n11C2nn
栈的顺序存储结构
顺序栈的定义
#define MaxSize 10 //定义栈中元素的最大个数typedef struct{ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶元素
}SqStack;void testStack(){SqStack S; //声明一个顺序栈(分配空间)//连续的存储空间大小为 MaxSize*sizeof(ElemType)
}基本操作
#define MaxSize 10 //定义栈中元素的最大个数typedef struct{ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶元素
}SqStack;//初始化栈
void InitStack(SqStack S){S.top -1; //初始化栈顶指针
}//判栈空
bool StackEmpty(SqStack S){if(S.top -1) //栈空return true;else //栈不空return false;
}//新元素进栈
bool Push(SqStack S, ElemType x){if(S.top MaxSize - 1) //栈满return false;S.top S.top 1; //指针先加1S.data[S.top] x; //新元素入栈/*S.data[S.top] x;*/return true;
}//出栈
bool Pop(SqStack x, ElemType x){if(S.top -1) //栈空return false;x S.data[S.top]; //先出栈S.top S.top - 1; //栈顶指针减1return true;/*x S.data[S.top--];*///只是逻辑上的删除数据依然残留在内存里
}//读栈顶元素
bool GetTop(SqStack S, ElemType x){if(S.top -1)return false;x S.data[S.top]; //x记录栈顶元素return true;
}void testStack(){SqStack S; //声明一个顺序栈(分配空间)InitStack(S);//...
}栈满条件topMaxSize顺序栈的缺点栈的大小不可变共享栈 定义利用栈底位置相对不变的特性可以让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸
栈的链式存储结构
与链表类似入栈和出栈的操作都在链表的表头进行
队列
队列的概念
定义队列是只允许在一端进行插入入队在另一端删除出队的线性表队头允许删除的一端队尾允许插入的一端空队列不含任何元素的空表队列的特点先进先出FIFO队列的基本操作 InitQueue(Q): 初始化队列构造一个空队列QDestroyQueue(Q): 销毁队列并释放队列Q所占用的内存空间EnQueue(Q, x): 入队若队列Q未满将x加入使之成为新的队尾DeQueue(Q, x): 出队若队列Q非空删除队头元素并用x返回GetHead(Q,x): 读队头元素若队列Q非空则将队头元素赋值给xQueueEmpty(Q): 判队列空若队列Q为空则返回true否则返回false
队列的顺序存储结构
队列的顺序实现
# define MaxSize 10; //定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize]; //用静态数组存放队列元素int front, rear; //队头指针和队尾指针
}SqQueue;初始化操作
//初始化队列
void InitQueue(SqQueue Q){//初始化时队头、队尾指针指向0Q.rear Q.front 0;
}// 判断队列是否为空
bool QueueEmpty(SqQueue 0){if(Q.rear Q.front) //队空条件return true;else return false;
}入队操作
bool EnQueue(SqQueue Q, ElemType x){if((Q.rear1)%MaxSize Q.front) //队满return false; //队满报错Q.data[Q.rear] x; //将x插入队尾Q.rear (Q.rear 1) % MaxSize; //队尾指针加1取模return true;
}出队操作
//出队删除一个队头元素用x返回
bool DeQueue(SqQueue Q, ElemType x){if(Q.rear Q.front) //队空报错return false; x Q.data[Q.front];Q.front (Q.front 1) % MaxSize; //队头指针后移动return true;
}获得队头元素
bool GetHead(SqQueue Q, ElemType x){if(Q.rear Q.front) //队空报错return false; x Q.data[Q.front];return true;
}判断队列已满/已空 方案一牺牲一个存储单元实现代码同1 初始化时rearfront0;队空条件Q.rearQ.front;队满条件(Q.rear1)%MaxSize Q.front队列元素个数(rearMaxSize-front)%MaxSize; 方案二 实现 #define MaxSize 10; //定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize]; //用静态数组存放队列元素int front, rear; //队头指针和队尾指针int size;
}SqQueue;初始化时 rearfront0;
size0;插入成功size;删除成功size--;队满条件sizeMaxsize;队空条件size0; 方案三 实现 #define MaxSize 10; //定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize]; //用静态数组存放队列元素int front, rear; //队头指针和队尾指针int tag; //最近进行的是删除/插入
}SqQueue;初始化时 rearfront0;
tag0;插入成功tag1;删除成功tag0;队满条件rearfronttag1;队空条件rearfronttag0;
队列的链式存储结构
定义队列
typedef struct LinkNode{ //链式队列结点ElemType data;struct LinkNode *next;
}typedef struct{ //链式队列LinkNode *front, *rear; //队列的队头和队尾指针
}LinkQueue;初始化 带头结点 void InitQueue(LinkQueue Q){//初始化时front、rear都指向头结点Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode));Q.front - next NULL;
}//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.front Q.rear) //也可用 Q.front - next NULLreturn true;elsereturn false;
}不带头结点 void InitQueue(LinkQueue Q){//初始化时front、rear都指向NULLQ.front NULL;Q.rear NULL;
}//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.front NULL)return true;elsereturn false;
}入队 带头结点 //新元素入队 (表尾进行)
void EnQueue(LinkQueue Q, ElemType x){LinkNode *s (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点s-data x;s-next NULL; //s作为最后一个结点指针域指向NULLQ.rear-next s; //新结点插入到当前的rear之后Q.rear s; //表尾指针指向新的表尾
}不带头结点 //新元素入队
void EnQueue(LinkQueue Q, ElemType x){LinkNode *s (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点s-data x;s-next NULL;if(Q.frontNULL){ //在空队列中插入第一个元素Q.fronts; //修改队头队尾指针Q.rears;}else{Q.rear-nexts; //新结点插入到rear结点之后Q.rears; //修改rear指针}
}出队 带头结点 //队头元素出队
bool DeQueue(LinkQueue Q, ElemType x){if(Q.front Q.rear)return false; //空队LinkNode *p Q.front-next; //p指针指向即将删除的结点x p-data;Q.front-next p-next; //修改头结点的next指针if(Q.rear p) //此次是最后一个结点出队Q.rear Q.front; //修改rear指针free(p); //释放结点空间return true;
}不带头结点 //队头元素出队
bool DeQueue(LinkQueue Q, ElemType x){if(Q.front Q.rear)return false; //空队LinkNode *p Q.front; //p指针指向即将删除的结点x p-data;Q.front p-next; //修改头结点的next指针if(Q.rear p){ //此次是最后一个结点出队Q.rearNULL:Q.frontNULL;} free(p); //释放结点空间return true;
}双端队列
定义只允许从两端插入、两端删除的线性表 输入受限的双端队列允许一端插入两端删除的线性表输出受限的双端队列允许两端插入一端删除的线性表
栈和队列的应用
栈在括号匹配中的应用
#define MaxSize 10 typedef struct{char data[MaxSize];int top;
} SqStack;//初始化栈
InitStack(SqStack S)//判断栈是否为空
bool StackEmpty(SqStack S)//新元素入栈
bool Push(SqStack S, char x)//栈顶元素出栈用x返回
bool Pop(SqStack S, char x)bool bracketCheck(char str[], int length){SqStack S; //声明InitStack(S); //初始化栈for(int i0; ilength; i){if(str[i] ( || str[i] [ || str[i] {){Push(S, str[i]); //扫描到左括号入栈}else{if(StackEmpty(S)) //扫描到右括号且当前栈空return false; //匹配失败char topElem; //存储栈顶元素Pop(S, topElem); //栈顶元素出栈if(str[i] ) topElem ! ( )return false;if(str[i] ] topElem ! [ )return false;if(str[i] } topElem ! { )return false; }}StackEmpty(S); //栈空说明匹配成功
}栈在表达式值中的应用
中缀表达式 (需要界限符)
规则运算符在两个操作数中间例 a ba b - ca b - c*d
后缀表达式 (逆波兰表达式)
规则运算符在两个操作数后面例 a b ab c - / a bc- ab cd* - 中缀表达式转后缀表达式 确定中缀表达式中各个运算符的运算顺序选择下一个运算符按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数如果还有运算符没被处理继续步骤2 “左优先”原则: 只要左边的运算符能先计算就优先算左边的 (保证运算顺序唯一) 用栈实现中缀表达式转后缀表达式 初始化一个栈用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素直到末尾。可能遇到三种情况 遇到操作数: 直接加入后缀表达式遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式直到弹出 ‘(’ 为止。注意: ‘(’ 不加入后缀表达式遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈 按上述方法处理完所有字符后将栈中剩余运算符依次弹出并加入后缀表达式 后缀表达式的计算从左往右扫描每遇到一个运算符就让运算符前面最近的两个操作数执行对应的运算合体为一个操作数用栈实现后缀表达式的计算栈用来存放当前暂时不能确定运算次序的操作数 从左往后扫描下一个元素直到处理完所有元素若扫描到操作数则压入栈并回到步骤1;否则执行步骤3若扫描到运算符则弹出两个栈顶元素执行相应的运算运算结果压回栈顶回到步骤1 先出栈的是“右操作数” 前缀表达式 (波兰表达式)
规则运算符在两个操作数前面例 a b ab c ab *cd 中缀表达式转前缀表达式 确定中缀表达式中各个运算符的运算顺序选择下一个运算符按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数如果还有运算符没被处理就继续执行步骤2 “右优先”原则: 只要右边的运算符能先计算就优先算右边的; 用栈实现前缀表达式的计算 从右往左扫描下一个元素直到处理完所有元素若扫描到操作数则压入栈并回到步骤1否则执行步骤3若扫描到运算符则弹出两个栈顶元素执行相应运算运算结果压回栈顶回到步骤1 先出栈的是“左操作数” 4.中缀表达式的计算(用栈实现)两个算法的结合 中缀转后缀 后缀表达式的求值 1. 初始化两个栈操作数栈和运算符栈 2. 若扫描到操作数压入操作数栈 3. 若扫描到运算符或界限符则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符每当弹出一个运算符时就需要再弹出两个操作数栈的栈项元素并执行相应运算运算结果再压回操作数栈)
栈在递归中的应用
函数调用的特点最后被调用的函数最先执行结束(LIFO)函数调用时需要用一个栈存储 调用返回地址实参局部变量 递归调用时函数调用栈称为 “递归工作栈” 每进入一层递归就将递归调用所需信息压入栈顶每退出一层递归就从栈顶弹出相应信息缺点 太多层递归可能回导致栈溢出
数组和特殊矩阵
数组的定义
数组是由n(n1)个相同类型的数据元素构成的有限序列每个数据元素称为一个数组元素每个元素在n个线性关系中的序号称为该元素的下标下标的取值范围称为数组的维界
数组的存储结构
一维数组 各数组元素大小相同物理上连续存放数组下标默认从0开始数组元素 a[i] 的存放地址 L O C i ∗ s i z e o f ( E l e m T y p e ) LOC i * sizeof(ElemType) LOCi∗sizeof(ElemType) LOC为数组起始地址 二维数组 行优先/列优先存储优点实现随机存储M行N列的二维数组 b[M][N] 中b[i][j]的存储地址 行优先存储: L O C ( i × N j ) × s i z e o f ( E l e m T y p e ) LOC (i×N j) × sizeof(ElemType) LOC(i×Nj)×sizeof(ElemType)列优先存储 L O C ( j × M i ) × s i z e o f ( E l e m T y p e ) LOC (j×M i) × sizeof(ElemType) LOC(j×Mi)×sizeof(ElemType) 普通矩阵的存储使用二维数组存储 描述矩阵元素时行、列号通常从1开始 描述数组时通常下标从 0 开始 特殊矩阵的压缩存储
矩阵的压缩存储为多个相同的非零元素只分配一个存储空间对零元素不分配空间。
对称矩阵 若n 阶方阵中任意一个元素 a i , j a_{i,j} ai,j都有 a i , j a j , i a_{i,j}a_{j,i} ai,jaj,i则该矩阵为对称矩阵策略只存储主对角线下三角区按行优先原则将各元素存入一维数组中数组大小 n ( n 1 ) 2 \frac{n(n1)}{2} 2n(n1)元素下标对应关系k为 a i , j a_{i,j} ai,j在一维数组中的下标 k { i ( i − 1 ) 2 j − 1 , i ≥ j ( 下三角区和主对角线元素 ) j ( j − 1 ) 2 i − 1 , i j ( 上三角区元素 a i , j a j , i ) k \left\{ \begin{array}{l} \frac{i(i-1)}{2}j-1, \quad i \ge j \quad (下三角区和主对角线元素) \\ \frac{j(j-1)}{2}i-1, \quad ij \quad (上三角区元素a_{i,j}a_{j,i}) \ \end{array} \right. k{2i(i−1)j−1,i≥j(下三角区和主对角线元素)2j(j−1)i−1,ij(上三角区元素ai,jaj,i)
三角矩阵 以主对角线划分三角矩阵有上下三角两种。上下三角矩阵的下上三角不含主对角线中的元素均为常数。在大多数情况下三角矩阵常数为零策略按行优先原则将元素存入一维数组中同对称矩阵。并在最后一个位置存储常量元素下标对应关系k为 a i , j a_{i,j} ai,j在一维数组中的下标 k { i ( i − 1 ) 2 j − 1 , i ≥ j ( 下三角区和主对角线元素 ) n ( n 1 ) 2 , i j ( 上三角区元素 a i , j a j , i ) k \left\{ \begin{array}{l} \frac{i(i-1)}{2}j-1, \quad i \ge j \quad (下三角区和主对角线元素) \\ \frac{n(n1)}{2}, \quad ij \quad (上三角区元素a_{i,j}a_{j,i}) \ \end{array} \right. k{2i(i−1)j−1,i≥j(下三角区和主对角线元素)2n(n1),ij(上三角区元素ai,jaj,i) 3. 三对角矩阵带状矩阵 1. 当 ∣ i − j ∣ 1 |i-j|1 ∣i−j∣1时有 a i , j 0 ( 1 ≤ i , j ≤ n ) a_{i,j}0 (1 \leq i,j \leq n) ai,j0(1≤i,j≤n) 2. 策略按行优先(或列优先) 原则只存储带状部分 3. 元素下标对应关系k为 a i , j a_{i,j} ai,j在一维数组中的下标 k2ij-3
稀疏矩阵
非零元系远远少于矩阵元素的个数策略 顺序存储——三元组行,列,值 会失去随机存取的特性 十字链表法
