《数据结构》复习重点.pdf

《《数据结构》复习重点.pdf》由会员分享，可在线阅读，更多相关《《数据结构》复习重点.pdf（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数 据 结 构 复 习 重 点 第 一 章 绪 论 要 求、目 标：了 解 数 据 逻 辑 结 构 的 分 类；掌 握 算 法 的 特 性 及 估 算 算 法 时 间 复 杂 度 的 方 法；熟 悉 数 据 结 构 的 基 本 基 本 概 念 和 术 语。一、基 本 概 念 和 术 语 1.数 据 结 构：是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 操 作 对 象 以 及 它 们 之 间 的 关 系 和 操 作 等 的 学 科。2.数 据：是 对 客 观 事 物 的 符 号 表 示，即 所 有 能 输 入 到 计 算 机 中 并 被 计 算 机 程

2、 序 处 理 的 符 号 的 总 称。3.数 据 项：数 据 的 不 可 分 割 的 最 小 单 位。4.数 据 元 素(数 据 结 点)：数 据 的 基 本 单 位，在 程 序 中 作 为 一 个 整 体 处 理，由 若 干 数 据 项 组 成。5.数 据 对 象：性 质 相 同 的 数 据 元 素 的 集 合，是 数 据 的 一 个 子 集 如：四 季 对 象 是 集 合：春，夏，秋，冬 自 然 数 对 象 是 集 合：0,1,2,3,字 母 字 符 对 象 是 集 合：，A,B,Z 6.数 据 结 构 的 分 类：线 性 结 构 和 非 线 性 结 构。7.数 据 结 构 的 形 式 化

3、 定 义：数 据 结 构 是 一 个 二 元 组，可 定 义 为 Data_Structure=(D,S)其 中：D 是 数 据 元 素 的 有 限 集 合，S 是 D 上 关 系 的 有 限 集 合 8.序 偶：两 个 元 素 间 的 前 后 关 系。a,b a是 b 的 前 驱 结 点，b 是 a 的 后 继 结 点 例：四 季 的 描 述 B=(D,R)D=春，夏，秋，冬 R=春，夏,夏，秋,秋，冬 9.物 理 结 构(存 储 结 构 或 映 像)：数 据 结 构 在 计 算 机 中 的 表 示。10.存 储 结 构 的 分 类：顺 序 存 储 结 构：利 用 元 素 的 相 对 位 置

4、 来 表 示 元 素 间 的 位 置 关 系，是 一 种 随 机 存 取 结 构，逻 辑 上 相 邻 的 数 据 物 理 上 也 紧 临，静 态 分 配 空 间；链 式 存 储 结 构：借 助 元 素 存 储 的 指 针 来 表 示 元 素 之 间 的 关 系，逻 辑 上 相 邻 的 数 据 物 理 上 不 一 定 紧 临，动 态 分 配 空 间。11.逻 辑 结 构 和 物 理 结 构 的 关 系：是 密 切 相 关 的 两 个 方 面，任 何 一 个 算 法 的 设 计 取 决 于 逻 辑 结 构，而 算 法 的 实 现 则 依 赖 于 采 用 的 存 储 结 构。12.数 据 类 型：是

5、 一 个 值 的 集 合 和 定 义 在 这 个 值 集 上 的 一 组 操 作 的 总 称，规 定 了 在 程 序 执 行 期 间 变 量 或 表 达 式 所 有 可 能 取 值 的 范 围，以 及 在 这 些 值 上 允 许 进 行 的 操 作。二、算 法 和 算 法 分 析 1.算 法：是 对 特 定 问 题 求 解 步 骤 的 一 种 描 述，它 是 指 令 的 有 限 序 列。2.算 法 的 特 性：有 穷 性：算 法 在 执 行 有 究 步 之 后 结 束，每 一 步 在 有 穷 时 间 内 完 成。确 定 性：每 一 条 指 令 必 须 有 确 切 的 含 义，不 应 产 生 二

6、 义 性，相 同 的 输 入 只 能 得 出 相 同 的 输 出。可 行 性：一 个 算 法 可 以 通 过 已 经 实 现 的 基 本 运 算 执 行 有 限 次 来 实 现。输 入 性：个 算 法 有 零 个 或 多 个 输 入。输 出 性：一 个 算 法 有 一 个 或 多 个 输 出。3.算 法 分 析 考 虑 的 方 面：正 确 性 可 读 性 健 壮 性 效 率 与 低 存 储 量 需 求 4.语 句 频 度：一 条 语 句 被 执 行 的 次 数 5.渐 近 时 间 复 杂 度：所 有 语 句 频 度 之 和，主 要 考 虑 嵌 套 最 深 语 句 的 频 度，若 频 度 为 多

7、 项 式 取 指 数 最 高 的 一 项 去 掉 系 数 即 为 渐 近 时 间 复 杂 度。T(n)=O(f(n)-f(n)为 时 间 复 杂 度 值 例：+x;s=O;0(1)(2)for(i=l;i=n;i+)+x;s+=x 0(n)(3)for(j=l;j=n;j+)-0(1?)for(k=l;k=n;k+)+x;s+=x;(4)for(j=l;jn;j+)y=y+l;频 度：n-1for(k=0;k=(2*n);j+)x+;频 度：(n-l)*(2n+l)-时 间 复 杂 度 为 0面)6.算 法 分 析 的 两 个 主 要 方 面：空 间 复 杂 度 和 时 间 复 杂 度。第 一

8、 章 复 习 题 一、填 空 1、数 据 结 构 被 形 式 地 定 义 为(D,S),其 中 D 是 数 据 元 素 的 有 限 集 合,S 是 D 上 关 系 的 有 限 集 合。2、数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 数 据 元 素 以 及 它 们 之 间 的 关 系 和 运 算 等 的 学 科。3、在 数 据 结 构 中，逻 辑 上 可 以 把 数 据 结 构 分 成 线 性 结 构 和 非 线 性 结 构。,立 选 牧 洋 1、算 法 必 须 具 备 的 五 个 特 性 是(B)。A.输 入 性、输 出 性、可 执

9、行 性、可 移 植 性 和 可 扩 充 性 B.输 入 性、输 出 性、可 行 性、确 定 性 和 有 穷 性 C.输 入 性、输 出 性、确 定 性、有 穷 性 和 稳 定 性 D.输 入 性、输 出 性、可 行 性、稳 定 性 和 安 全 性 2、算 法 分 析 的 两 个 主 要 方 面 是(A)oA.空 间 复 杂 度 和 时 间 复 杂 度 B.正 确 性 和 可 读 性 C.简 单 性 和 文 档 性 D.数 据 复 杂 性 和 程 序 复 杂 性 三、计 算，求 下 列 算 法 的 渐 近 时 间 复 杂 度 及 带 语 句 的 频 度 1.void s o rt(in t*x,

10、int n)int i,j,k,t;fo r(i=l,i=n-l;i+)k=i;for(j=i+l;j xk)k=j;if(k!=i)t=xi;xi=xk;xk=t;解：语 句 频 度 为：(-1)+(n-2)+1=渐 近 时 间 复 杂 度：0(n2)2.sum(int n);int sum=O,i,j;for(i=l;i=n;i+)p=l；for(j=l;j=i;j+)P*二 j；sum+=p;return sum;解：语 句 频 度 为：1+2+3+=险 土。2渐 近 时 间 复 杂 度：0(/)3.sum(int n)int i,sum=0;for(i=l;i=n;i+)sum+=i;

11、printf(%dn,sum);解：语 句 频 度 为：n渐 近 时 间 复 杂 度：0(n)第 二 章 线 性 表 要 求、目 标：了 解 线 性 表 的 基 本 概 念；掌 握 顺 序 存 储 和 链 式 存 储 结 构 的 描 述 方 法；掌 握 循 环 单 链 表、双 链 表 的 特 点 一、线 性 表 概 述 1.线 性 表：具 有 相 同 类 型 的 n 个 数 据 元 素 的 有 限 序 列，可 表 示 为 0,a2,a0)2.线 性 表 长 度：数 据 元 素 个 数 n。3.空 线 性 表：长 度 为 零 的 线 性 表。4.关 键 字/犍：能 惟 一 标 识 元 素 的 字

12、 段。5.相 邻 元 素 关 系：a i为 a z 前 驱 元 素，4”为 后 继 元 素，存 在 序 偶 关 系。为 无 前 驱 元 素，a.无 后 继 元 素。例：字 母 表：(A,B,C,Z)学 生 成 绩 表：(790631,790632,，790645)每 个 元 素 为 一 条 记 录，由 若 干 数 据 项 组 成，线 性 表 中 可 只 写 关 键 字。二、线 性 表 的 顺 序 存 储 1.顺 序 存 储：线 性 表 的 各 个 元 素 依 次 存 储 在 一 组 地 址 连 续 的 存 储 单 元 里。2.元 素 位 置 确 定：LOC(ai)=LOC(ai)+(i-l)*

13、L 其 中 a I为 线 性 表 第 一 个 元 素 的 存 储 位 置，L 为 每 个 元 素 所 占 字 节 数。例：已 知 a i的 地 址 为 1 0 0 0,每 个 元 素 占 2 字 节，求 as的 地 址 LOC(a5)=1000+(5-1)*2=10083.顺 序 表 的 特 点(1)是 一 种 随 机 存 取 的 存 储 结 构(2)逻 辑 上 相 邻 的 元 素 物 理 位 置 必 定 紧 邻(3)存 储 空 间 是 静 态 分 配 的(4)适 用 于 事 先 能 确 定 线 性 表 的 大 小，存 取 速 度 快(5)插 入 和 删 除 操 作 时 需 移 动 大 量 的

14、 元 素，4.插 入 或 删 除 元 素 时 移 动 次 数(1)向 含 有 n 个 元 素 的 线 性 表 第 i 个 位 置 插 入 元 素，需 移 动 n-i+1次 元 素，平 均 移 动 巴 次 2(2)删 除 含 有 n 个 元 素 的 线 性 表 第 i 个 位 置 的 元 素，需 移 动 n-i次 元 素，平 均 移 动 0 次 25.存 储 结 构 的 描 述#define list_max 100typedef structint datalist_max;int len;sqlist;6.顺 序 结 构 线 性 表 的 运 算(1)线 性 表 的 初 始 化 void In

15、itList(sqlist*L)L.len=0;(2)求 线 性 表 的 长 度 int ListLen(sqlist*L)return L.len;(3)在 线 性 表 中 查 询 某 个 个 结 点，返 回 结 点 在 线 性 表 中 的 位 置 int search(int x;sqlist*L;int n)int i;for(i=0;in;i+)if(x=L.datai)break;if(i=n)retum(0);retum(i+l);(4)在 顺 序 线 性 表 中 第 I 个 位 置 前 插 入 一 新 元 素 int insert_sq(sqlist*L;int i;int e)

16、int p;if(iL.len)return 1;if(L.lenlist_max-1)return 2;for(p=L.len;pi;p-)L.datap=L.datap-1;L.datai=e;L.len+;return 0;(5)在 顺 序 线 性 表 中 删 除 第 i个 元 素 int delete_sq(sqlist*L,int i)int p;if(iL.len)return 1;for(p=i+l;pL.Ien;p+)L.datap-1=L.datap;L.len-;return 0;(6)合 并 两 个 递 增 有 序 的 顺 序 线 性 表，合 并 后 仍 为 递 增 有

17、序 int mergelist(sqlist*LA,sqlist*LB,sqlist*LC)int I=0,j=0,k=0;while(ILA.len&jLB.len)if(LA.dataILB.dataj)LC.datak+=LA.dataI+;else if(LA.dataI=LB.dataj)LC.da皿 k+=LA.dataI+;LC.data k+=LB.datafj+;elseLC.data k+=LB.data j+;while(ILa.len)LC.dat a k+=L A.data I+;while(jLB.len)LC.data k+=LB.dataj+;return k;

18、三、线 性 表 的 链 式 存 储(-)线 性 链 表 1.特 点 1)逻 辑 上 相 邻 的 元 素，物 理 上 不 一 定 紧 邻 2)插 入 和 删 除 操 作 时，不 需 移 动 大 量 元 素，只 需 修 改 有 限 的 指 针 变 量 3)动 态 分 配 和 释 放 存 储 单 元，避 免 了 空 间 浪 费 4)不 具 备 随 机 存 取 的 优 点，查 找 结 点 需 从 表 头 开 始，结 点 的 存 储 利 用 率 较 低 5)适 用 于 经 常 进 行 插 入、删 除 操 作 或 事 先 不 能 确 定 结 点 的 最 大 数 量 2.线 性 链 表：具 有 链 式 存

19、储 结 构 的 线 性 表 3.单 链 表：每 个 结 点 只 包 含 一 个 指 针 域 4.结 点 结 构：data next5.结 点 类 型 typedef struct nodeint data;struct node*next;NODE;6.头 指 针：指 向 链 表 的 头 结 点 或 第 一 个 结 点 的 位 置 7.头 结 点：在 链 表 第 一 个 结 点 之 前 附 设 的 结 点，其 数 据 域 可 不 存 任 何 信 息 或 存 表 长，指 针 域 保 存 第 一 个 结 点 的 地 址 8.设 置 头 结 点 的 作 用：插 入 或 删 除 首 元 素 时 不 必

20、 对 头 指 针 进 行 修 改 9.第 一 个 结 点：第 一 个 实 际 存 储 数 据 的 结 点 10.单 链 表 的 结 构 1）不 带 头 结 点 11.建 立 带 头 结 点 的 单 链 表,在 表 尾 插 入，以-1结 束 NODE*creat()NODE*h,*p,*r;int x;h=r=(NODE*)malloc(sizeof(NODE);scanf(d,&x);while(x!=-l)p=(NODE*)malloc(sizeof(NODE);p-data=x;r-next=p;r=p；scanf(%d,&x);r-next=NULL;retum(h);12.建 立 带

21、头 结 点 的 单 链 表,在 表 头 插 入，以-1结 束 NODE*creat()NODE*h,*p;int x;h=(NODE*)malloc(sizeof(NODE);h-next=NULL;scanf(%d”,&x);while(x!=-l)p=(NODE*)malloc(sizeof(NODE);p-data=x;p-next=h-next;h-next=p;scanf(d”,&x);retum(h);13.在 单 链 表 第 I 个 结 点 前 插 入 一 个 元 素 int insert_L(NODE*h,int I,int x)NODE*p=h,*s;int j=0;s=(N

22、ODE*)malloc(sizeof(NODE);s-data=x;while(p!=NULL&jnext;j+;if(!plljI-l)return 1;s-next=p-next;p-next=s;return 0;14.删 除 单 链 表 中 第 I 个 结 点 int delete_L(NODE*h,int I,int*e)NODE*p=h,*q;int j=0;while(p-next&jnext;j+;if(!(p-next)lljI-l)retum 1;q=p-next;*e=q-data;p-next=q-next;free(q);return 0;15.查 找 与 给 定 值

23、 相 同 的 第 一 个 结 点 NODE*locatenode(NODE*h,int key)NODE*p=h-next;while(p&p-data!=key)p=pnext;return p;16.合 并 两 个 递 减 有 序 的 链 表，合 并 后 仍 为 递 减 有 序 NODE*merge_L(NODE*ha,NODE*hb)NODE*p=ha-next,*q=hb-next,*r,*s;s=(NODE*)malloc(sizeof(NODE);s-next=NULL;r=s;while(p!=NULL&q!=NULL)if(p-dataq-data)r-next=p;r=p;p

24、=p-next;elser-next=q;r=q;q=q-next;if(p=NULL)r-next=q;else r-next=p;return s;(-)循 环 链 表1.定 义：最 后 一 个 结 点 的 指 针 域 指 向 链 表 的 头 结 点 或 第 一 个 结 点。2.优 点：解 决 了 无 法 从 指 定 结 点 到 达 该 结 点 的 前 驱 结 点 的 问 题。3.结 构：4.判 别 是 否 为 空 1）带 头 结 点：当 h-next=h时 为 空 2）不 带 头 结 点：当 h=NULL时 为 空 5.删 除 第 一 个 结 点 1）带 头 结 点：h-next=h-n

25、ext-next2）不 带 头 结 点：h=h-next6.建 立 循 环 链 表 将 尾 结 点 r-next=NULL;改 为 r-next=h;（三）双 向 链 表 1.特 点：两 个 指 针 域，可 用 于 表 示 树 型 结 构，一 个 指 向 前 驱，一 个 指 向 后 继 2.结 点 类 型：typedef struct dnodeint data;struct dnode*prior,*next;DNODE;3.结 构：h4.建 立 双 链 表（以 0 结 束）DNODE*creatd()DNODE*h,*p,*q;int x;h=p=(*DNODE)malloc(sizeof

26、(DNODE);scanf(%d,&x);while(x!=0)q=(*DNODE)malloc(sizeof(DNODE);q-data=x;p-next=q;q-prior=p;p=q；scanf(%d,&x);p-next=NULL;h-prior=NULL;return h;5.在 双 链 表 的 第 I 个 结 点 之 后 后 插 入 一 新 结 点 void insertd(DNOD*h,int I,int x)DNODE*s,*p;intj;s=(DNODE*)malloc(sizeof(DNODE);s-data=x;if(I=0)s-next=*h;*h-prior=s;*h

27、=s;*h-prior=NULL;elsep=*h;j=l;while(p!=NULL&jnext;if(p!=NULL)if(p-next=NULL)p-next=s;s-prior=p;s-next=NULL;elses-next=p-next;p-next-prior=s;s-prior=p;p-next=s;elseprintf(Nofoundn);6.删 除 双 链 表 中 值 为 x 的 结 点 void delete(DNODE*h,int x)DNODE*p;if(*h=NULL)printf(overflowrT);if(*h-data=x)p=*h;*h=*h-next;*

28、h-prior=NULL;free(p);elsep=*h-next;while(p!=NULL&p-data!=x)p=pnext;if(p!=NULL)if(p-next=NULL)p-prior-next=NULL;free(p);elsep-prior-next=p-next;p-next-prior=p-prior;free(p);elseprintf(Nofoundn);第 二 章 复 习 题 一、填 空 1.在 线 性 结 构 中 元 素 之 间 存 在 一 对 一 关 系,第 一 个 结 点 皿 前 驱 结 点，其 余 每 个 结 点 有 且 只 有 一 个 前 驱 结 点；最

29、 后 一 个 结 点 没 有 后 继 结 点,其 余 每 个 结 点 有 且 只 有 个 后 继 结 点。2.线 性 结 构 的 顺 序 存 储 结 构 是 一 种 随 机 存 取 的 存 储 结 构,逻 辑 上 相 邻 的 元 素 物 理 位 置 上 必 紧 临；其 链 式 存 储 结 构 是 一 种 现 在 在 的 存 储 结 构，逻 辑 上 相 邻 的 元 素 物 理 存 储 位 置 不 关 连 续。*2琏 2E-徉 Z.1.在 一 个 单 链 表 中，若 P 所 指 结 点 不 是 最 后 结 点，在 P 之 后 插 入 S所 指 结 点,则 执 行（B）。A.s-next=p;p-n

30、ext=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;2.在 一 个 单 链 表 中，若 删 除 p所 指 结 点 的 后 续 结 点，则 执 行（A）oA.p-next=p-next-next;B.p-next=p-next;C.p=p-next;p-next=p-next-next;D.p=p-next-next;3.在 一 个 单 链 表 中，已 知 q 所 指 结 点 是 p 所 指 结 点 的 前 驱 结 点，若 在 q 和 p 之 间 插 入 s结 点，则 执 行（C）。A.s-next=p-n

31、ext;p-next=s;B.p-next=s-next;s-next=p;C.s-next=p;q-next=s;D.p-next=s;s-next=q;4.非 空 的 循 环 单 链 表 头 指 针 为 front,p 指 向 尾 结 点，则 应 满 足（C）。A.p-next=NULL;B.p二 二 NULL;C.p-next=front;D.p=front;5.带 头 结 点 的 单 链 表 头 指 针 front为 空 的 判 定 条 件 是（B）。A.front=NULL B.front-next=NULLC.front-next=front D.front!=NULL6.不 带

32、头 结 点 的 单 链 表 头 指 针 front为 空 的 判 定 条 件 是（A）。A.front=NULL B.front-next=NULLC.front一 next二 二 front D.front!=NULL7.在 循 环 双 链 表 的 p 所 指 结 点 之 后 插 入 s所 指 结 点 的 操 作 是（D）0A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p

33、-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;8.在 双 链 表 的 p 所 指 结 点 之 前 插 入 s所 指 结 点 的 操 作 是（A）0A.s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;B.s-next=p;s-prior=p-prior;p-prior=s;p-prior-next=s;C.p-prior=s;s-next=p;p-prior-next=s;s-prior=p-prior;D.s-prior=p;s-next=p-next;p-ne

34、xt-prior=s;p-next=s;9.删 除 双 链 表 中 p 所 指 结 点 的 操 作 是(C)oA.p-prior=p-prior-prior;p-prior-next=p;free(p);B.p-next=p-next-next;p-next-prior=p;free(p);C.p-prior-next=p-next;p-next-prior=p-prior;free(p);D.p-next-prior=p-prior;p-prior-next=p;free(p)三、编 程 1.含 n 个 元 素 的 顺 序 表 X 按 升 序 排 列，删 除 线 性 表 中 值 介 于 a

35、与 b 之 间 的 元 素。void del(int x,int*n,int a,int b)int i=0,k;while(ia&xib)for(k=i;k*n;k+)xk=xk+l;(*n)一;else i+;2.含 n 个 元 素 的 顺 序 表 A 按 升 序 排 列，删 除 线 性 表 中 多 余 的 值 相 同 的 元 素。int del(int a,int n)int i=0,j;while(i=nl)if(ai!=ai+l)i+;else for(j=i;jn;j+)aj=aj+l;n-;return n;3.含 n 个 元 素 的 顺 序 表 A 中 元 素 按 升 序 排

36、列，插 入 一 个 元 素 x 后，使 A 中 元 素仍 有 序。int insert(int a,int n,int x)int i,j;if(x=an-l)an=x;else i=0;while(x=aii+;for(j=n-l;j=i;j)aj+l=aj;ai=x;n+;return n;4.求 单 链 表 的 长 度 int count(NODE*h)int n=0;NODE*p;p=h;if(h=NULL)n=0;elsewhile(p!=NULL)n+;p=p-next;return n;第 三 章 栈 和 队 列 要 求、目 标：熟 悉 栈 和 队 列 特 点、数 据 结 构 的

37、 定 义 掌 握 在 栈 上 的 各 种 操 作、使 用 数 组 和 链 表 实 现 栈 掌 握 用 数 组 和 链 表 实 现 队 列 掌 握 循 环 队 列 的 相 关 操 作 一、栈（-）概 述 1.堆 栈：只 允 许 在 表 的 一 端 进 行 插 入 和 删 除 操 作 的 线 性 表。2.栈 顶：允 许 进 行 添 加 或 删 除 元 素 的 一 端 3.栈 底：不 允 许 进 行 添 加 或 删 除 元 素 的 一 端 4.空 栈：没 有 元 素 的 栈 5.入 栈（进 栈/压 栈）（pus/l）：栈 的 插 入 运 算 6.出 栈（退 栈/弹 出）（pop）：栈 的 删 除 运

38、 算 7.栈 的 特 点：后 进 先 出（LIFO）is入 在 栈 中 插 入 和 删 除 的 示 例（-）栈 的 顺 序 存 储 结 构 1.栈 类 型 的 定 义 define STACKMAX 100int top;int stackSTACKMAX;2.栈 的 初 始 化 top值 为 下 一 个 进 栈 元 素 在 数 组 中 的 下 标 值，入 栈 操 作 是 先 压 栈 再 移 动 栈 顶 指 针，出 栈 操 作 是 先 移 动 栈 顶 指 针 再 取 出 元 素 1）栈 空:top=02）栈 满：top=STACKMAX3.进 栈 与 出 栈 顺 序 若 进 栈 序 列 为 a

39、、b、c,则 全 部 可 能 出 栈 的 序 列 为（，一，表 示 进，一，表 示 出）：af a-b c c 即 abc a f b f b c c-a 即 bca a a*b c f c-b-即 acb a f b f b-a-c c 即 bac a f b-*c*c-b-a 即 cba4.判 定 栈 是 否 为 空 int empty()if(top=0)return 1;else return 0;5.压 栈 的 实 现 int top=0;int push(int x)if(top=STACKMAX)rerurn 1;stack top+=x;return 0;6.出 栈 的 实 现

40、 int pop(int*p)if(top=0)rreturn 1;*p=stack topi;return 0;7,读 栈 顶 元 素 void readtop(int*p)if(top=0)printfCNo elementn)；else*p=stack top;top+;(三)栈 的 链 式 存 储 结 构 1.链 栈：用 线 性 链 表 表 示 的 栈 2.栈 顶 指 针：链 栈 的 表 头 指 针 3.栈 的 变 化 1)栈 空：top=NULL2)非 空：to p指 向 链 表 的 第 一 个 结 点，栈 底 结 点 的 指 针 域 为 空 无 栈 满 情 况 4.结 点 类 型

41、typedef struct snodeint data;struct snode*next;SNODE;5.进 栈 的 实 现 SNODE*top=NULL;void push_L(int x)SNODE*p;p=(SNODE*)malloc(sizeof(SNODE);p-data=x;p-next=top;top=p；6.判 链 栈 是 否 为 空 int empty_L(SNODE*top)if(top=NULL)return 1;else return 0;7.出 栈 的 实 现 int pop_L(SNODE*top,int*p)SNODE*q;if(top=NULL)return

42、 1;*p=top-data;q=top;top=top-next;free(q);return 0;8.求 链 栈 中 结 点 的 个 数 int count_L(SNODE*top)SNODE*p;int n=0;p=top;while(p!=NULL)n+;p=pnext;return n;(四)栈 的 应 用 1.数 数 制 转 换(十 进 制 一 八 进 制)void convert()int x,n,m;top=0;scanf(u%d,&n);while(n)m=push(n%8);if(m)printf(overflown);else n/=8;while(!empty()m=p

43、op(&x);if(m)printfCNo elementn);else printf(%d”,x);2.表 达 式 求 值 1)算 术 表 达 式 的 中 缀 表 示：运 算 符 放 在 两 个 操 作 数 中 间 的 算 术 表 达 式 例：a+b*c+d/e*f2)中 缀 表 示 在 计 算 机 处 理 中 的 的 问 题 受 括 号、优 先 级 和 结 合 律 的 限 制，不 一 定 按 运 算 符 出 现 的 先 后 顺 序 执 行，完 成 运 算 需 对 表 达 式 进 行 多 遍 扫 描，浪 费 时 间。3)算 术 表 达 式 的 后 缀 表 示(逆 波 兰 表 示 法)例：a+

44、b-ab+a*b-ab*4)中 缀 表 达 式 到 后 缀 表 达 式 的 转 换 规 则 找 出 最 先 运 算 的 运 算 符，将 其 移 至 两 个 操 作 数 的 后 面，若 有 括 号 则 删 掉 把 得 到 的 后 缀 表 达 式 作 为 一 个 整 体 放 在 原 表 达 式 中 找 下 一 个 要 运 算 的 运 算 符，重 复 上 述 转 换 直 到 所 有 运 算 符 处 理 完 毕 例：a+b*c-d/（e*f）f a+b*c-d/ef*f a+bc*-def*/f abc*+-def*/f abc*+def*/-5.后 缀 表 达 式 的 求 值 从 左 一 右 扫 描

45、，遇 到 运 算 符 将 该 运 算 符 前 面 两 个 数 取 出 运 算，结 果 带 回 后 缀 表 达 式 参 与 后 面 的 运 算，直 到 扫 描 到 最 后 一 个 运 算 符 并 计 算 得 最 终 结 果 例：345/6*+2-3 0.8 6*+2-3 4.8+2-7.8 2-5.86.运 用 栈 完 成 后 缀 表 达 式 求 值 运 用 栈 保 存 操 作 数 和 结 果，从 左 一 右 扫 描，若 为 操 作 数 则 将 其 入 栈，若 为 运 算 符 则 弹 出 两 个 数 进 行 运 算，并 将 结 果 入 栈,直 到 扫 描 到 表 达 式 的 最 后 一 个 字

46、符,栈 顶 的 值 为 最 终 的 结 果。7.运 用 栈 完 成 中 缀 表 达 式 到 后 缀 表 达 式 的 转 换 运 用 栈 保 存 运 算 符、取 中 缀 表 达 式 中 的 一 字 符，若 为 数 字 则 输 出；若 为（则 入 栈；若 为 运 算 符 当 其 优 先 级 高 于 栈 顶 运 算 符 的 栈 中 优 先 级 时 则 入 栈，否 则 栈 顶 运 算 符 出 栈 并 输 出；若 为）则 依 次 退 出 栈 中 运 算 符 并 输 出 直 到（，将（退 栈 但 不 输 出；若 为 0则 依 次 退 栈 并 输 出 二、队 列（-）概 述 1.队 列：只 允 许 在 表

47、的 一 端 进 行 插 入 操 作 而 在 另 一 端 进 行 删 除 操 作 的 线 性 表 2.队 尾：允 许 进 行 插 入 操 作 的 一 端 3.队 首：允 许 进 行 删 除 操 作 的 一 端 4.特 点：先 进 先 出（FIFO）（二）队 列 的 顺 序 存 储 结 构 1.顺 序 队 列 的 类 型#define Q U E U E M A X 100char queuefQUEUEMAX;int front,rear;2.顺 序 队 列 的 变 化front指 向 队 首 元 素 的 前 一 个 位 置，rear指 向 队 尾 元 素 的 位 置，入 队 操 作 是 先 移

48、 动 队 尾 指 针，再 插 入 元 素；出 队 操 作 是 先 移 动 队 首 指 针，再 取 出 元 素 1)空：front=rear=-l2)非 空：rearfront3)满：rear=QUEUEMAX-13.判 别 队 列 是 否 为 空 int empty()if(front=rear)return 1;else return 0;4.初 始 化 队 列 void init()int front=-1,rear=-1;5.入 队 的 实 现 int ins_queue(char x)if(rear=QUEUEMAX-1)return 1;queue+rear=x;return 0;6

49、.出 队 的 实 现 int del_queue(char*p)if(front=rear)return 1;*p=queue+front;return 0;7.假 溢 出 1)假 满：当 rear=QUEUEMAX-1时，数 组 前 端 有 空 闲 单 元，出 现 假 满 2)解 决 方 案：一 个 元 素 出 队 时，将 所 有 元 素 依 次 向 队 首 方 向 移 动 一 个 位 置，修 改 头 尾 指 针，使 空 闲 单 元 留 在 后 面，此 方 案 花 费 时 间 较 多 出 队 时 队 列 不 移 动，当 出 现 假 溢 出 时，将 所 有 元 素 依 次 向 队 首 方 向

50、移 动，此 方 案 也 要 花 费 较 多 时 间 把 队 列 看 作 是 个 首 尾 衍 接 的 循 环 队 列，这 是 最 有 效 的 解 决 方 案（三）循 环 队 列 1.特 点：空 闲 单 元 单 元 总 是 在 尾 指 针 后 面，fro n t指 向 队 首 前 一 个 位 置 2.循 环 队 列 的 变 化 队 列 的 队 首 队 列 的 队 首 队 列 的 队 尾 ARRAYM AX-1C IR C U L A R M A X=1 6C IR C U LA R M A X-1队 列 的 队 尾 I)仝 队：front=rear2)队 满：front=rear3.问 题：当 队