习题七参考答案.pdf

习题七 1 自己设计一个通信录条目的结构 并分别编写输入和输出一条通信录条目的函数 答 include include include typedef struct saddr char name char address char zip char phone ADDR ADDR inputAddr 输入一个通信录 char buffer 256 ADDR p printf 名字 立即回车表示输入结束 gets buffer if strlen buffer 0 return NULL p ADDR malloc sizeof ADDR p name char malloc strlen buffer 1 strcpy p name buffer printf 地址 gets buffer p address char malloc strlen buffer 1 strcpy p address buffer printf 邮编 gets buffer p zip char malloc strlen buffer 1 strcpy p zip buffer printf 电话号码 gets buffer p phone char malloc strlen buffer 1 strcpy p phone buffer return p void outputAddr ADDR ptr 显示一条通信录 if ptr NULL return printf n t 名字 s n ptr name printf t 地址 s n ptr address printf t 邮编 s n ptr zip printf t 电话 s n ptr phone void main outputAddr inputAddr 2 试定义一个表示学生信息的结构 要求包含学生的一些常见的固定信息和尽可能完全的 学习成绩信息 答 typedef struct student int number 学号 char name 20 姓名 设姓名少于 20 个字符 char sex 性别 struct int day 日 int month 月 int year 年 birthday 出生日期 char address 40 家庭地址 int totalPoints 已学总学分 int courseNum 已学课程数 StuType 3 试定义地址类型 要求该类型能考虑一般的地址格式 答 typedef struct addr char province 省 char city 市 char county 县 char village 乡 char zip 邮编 Addr 4 编写输入学生某门课程成绩的函数 利用该函数输入学生的全部成绩 再编写按某门成 绩或总成绩排序的函数 答 完整程序参见习题 5 的参考解 define M 100 define N 100 define UP 73 define DOWN 81 define Esc 27 struct gradeType int courseCode 课程代码 int grade 成绩 struct stuType 学生学习成绩信息 int number 学号 char name 20 姓名 int courseNum 已学课程数 gradeType grades N 课程成绩表 按课程代码为序存储 stuType students M 全班学生学习成绩信息 按学号为序存储 void inputGrade stuType spt int num code g j i char name 20 cout num name for i 0 i M i if spt i number 0 找到最后 spt i number num 插入一个新的学生 strcpy spt i name name spt i courseNum 0 break if num spt i number 找到 break else if num spt i number 需要插入 for j i 1 j i j 向后移一个位置 spt j spt j 1 spt i number num 插入 strcpy spt i name name spt i courseNum 0 break while 1 cout code if code 0 break cout g for j 0 j spt i courseNum j if code j k spt i grades k spt i grades k 1 spt i grades j grade g spt i grades j courseCode code spt i courseNum int sortByOneCourse stuType s int course int grades 2 从成绩表中取指定课程的成绩 无成绩以 0 分计算 从成绩表中取指定课程的成绩 无成绩以 0 分计算 排序结果存于数组 grades 2 中 由高分到低分排序 grades 0 存储该生在学生成绩表中的下标 grades 1 存储分数 int k for int i 0 i M i if s i number 0 break grades i 0 i for k 0 k s i courseNum k if course s i grades k courseCode break if course s i grades k courseCode grades i 1 s i grades k grade else 该生没有该门课程成绩 grades i 1 0 for int u 0 u u v if grades v 1 grades v 1 1 int t grades v 1 grades v 1 grades v 1 1 grades v 1 1 t t grades v 0 grades v 0 grades v 1 0 grades v 1 0 t return i 返回成绩表人数 int sortByTotalCourse stuType s int grades 2 从成绩表中取指定课程的成绩 无成绩以 0 分计算 int sum k for int i 0 i M i if s i number 0 break grades i 0 i for sum 0 k 0 k s i courseNum k sum s i grades k grade grades i 1 sum for int u 0 u u v if grades v 1 grades v 1 1 int t grades v 1 grades v 1 grades v 1 1 grades v 1 1 t t grades v 0 grades v 0 grades v 1 0 grades v 1 0 t return i 返回成绩表人数 5 利用前面的结果 编写一个小型的班级同学信息的管理系统 要求至少设有以下实用功 能 录入学生信息 求某一门课程的总分 平均分 按姓名或学号查找学生的信息并显 示 顺序浏览学生信息 按指定的若干门课程或按总分由高到低显示学生信息等 答 include include include include define M 100 define N 100 define UP 73 define DOWN 81 define Esc 27 struct gradeType int courseCode 课程代码 int grade 成绩 struct stuType 学生学习成绩信息 int number 学号 char name 20 姓名 int courseNum 已学课程数 gradeType grades N 课程成绩表 按课程代码为序存储 stuType students M 全班学生学习成绩信息 按学号为序存储 void inputGrade stuType spt int num code g j i char name 20 cout num name for i 0 i M i if spt i number 0 找到最后 spt i number num 插入一个新的学生 strcpy spt i name name spt i courseNum 0 break if num spt i number 找到 break else if num spt i number 需要插入 for j i 1 j i j 向后移一个位置 spt j spt j 1 spt i number num 插入 strcpy spt i name name spt i courseNum 0 break while 1 cout code if code 0 break cout g for j 0 j spt i courseNum j if code j k spt i grades k spt i grades k 1 spt i grades j grade g spt i grades j courseCode code spt i courseNum int sortByOneCourse stuType s int course int grades 2 从成绩表中取指定课程的成绩 无成绩以 0 分计算 int k for int i 0 i M i if s i number 0 break grades i 0 i for k 0 k s i courseNum k if course s i grades k courseCode break if course s i grades k courseCode grades i 1 s i grades k grade else 该生没有该门课程成绩 grades i 1 0 for int u 0 u u v if grades v 1 grades v 1 1 int t grades v 1 grades v 1 grades v 1 1 grades v 1 1 t t grades v 0 grades v 0 grades v 1 0 grades v 1 0 t return i 返回成绩表人数 int sortByTotalCourse stuType s int grades 2 从成绩表中取指定课程的成绩 无成绩以 0 分计算 int sum k for int i 0 i M i if s i number 0 break grades i 0 i for sum 0 k 0 k s i courseNum k sum s i grades k grade grades i 1 sum for int u 0 u u v if grades v 1 grades v 1 1 int t grades v 1 grades v 1 grades v 1 1 grades v 1 1 t t grades v 0 grades v 0 grades v 1 0 grades v 1 0 t return i 返回成绩表人数 int totalGrades stuType s int code int sum sum 0 for int i 0 i M i if s i number 0 break for int j 0 j s i courseNum j if s i grades j courseCode code sum s i grades j grade break return sum double aveGrades stuType s int code int sum sum 0 for int i 0 i M i if s i number 0 break for int j 0 j s i courseNum j if s i grades j courseCode code sum s i grades j grade break return double sum i void outputStu stuType spt cout 学号 number endl cout 姓名 name endl for int i 0 i courseNum i cout 课程代码 grades i courseCode t 成绩 grades i grade endl void searchByNum stuType s int num for int i 0 i M i if s i number 0 num s i number break if s i number num outputStu return cout 没有你要找的学生 n void searchByName stuType s char name for int i 0 i M i if s i number 0 break if strcmp s i name name 0 outputStu return cout 没有你要找的学生 n int sortTable M 2 void outputSortTabel int t 2 int n for int i 0 i n i cout t i 0 t t i 1 endl void show stuType s 浏览 char c int i 0 while 1 outputStu cout 0 cout tPgUp 向上 endl if s i 1 number 0 cout tPgDn 向下 endl cout tEsc 退出浏览 n 0 i break case DOWN if s i 1 number 0 i break int main int code num ans k i char name 20 int grades M 2 char menuName 录入学生信息 求某一门课程的总分 求某门课程的平均分 按学号查找学生信息 按姓名查找学生信息 顺序浏览学生信息 某门课程排序显示 总分排序显示 while 1 cout 请选择以下菜单命令 n for k 0 menuName k 0 0 k cout t k 1 menuName k endl cout ans if ansk break switch ans case 1 inputGrade students break case 2 cout code cout 该课程的总分是 totalGrades students code endl break case 3 cout code cout 该课程的平均分是 aveGrades students code endl break case 4 cout num searchByNum students num break case 5 cout name searchByName students name break case 6 show students break case 7 cout code k sortByOneCourse students code grades for i 0 i k i outputStu if i k 1 cout n 按任意键继续 n char c getch break case 8 k sortByTotalCourse students grades for i 0 i k i outputStu if i k 1 cout n 按任意键继续 n char c getch break return 0 6 一张扑克牌可用结构类型描述 一副扑克牌的 52 张牌则是一个结构数组 另引入表示 牌面值的字符串指针数组和表示牌花色的字符串指针数组 试编写洗牌函数和供四人玩 牌的发牌函数 两张牌的大小比较函数等 答 为了程序能完整地输出牌的花色和面值 另引入以下字符指针数组用于存储牌的花色名称 char suit 4 Spades Hearts Diamonds Clubs 以下字符指针数组用于存储牌的面值 char face 13 Ace Deuce Three Four Five Six Seven Eight Nine Ten Jack Queen King 令 52 张牌按位置顺序与整数 0 至 51 对应 首先按花色和按面值将牌顺序填入数组中 然后逐一考察这 52 张牌 并为每张牌随机产生一个 0 至 51 范围内的一个整数 并将当前正 在考察的牌与随机产生的整数对应的牌交换 直至每张牌都被考察后 洗牌结束 include include include 有关时间库函数 struct card int face int suit deck 52 char suit 4 Spades Hearts Diamonds Clubs char face 13 Ace Deuce Three Four Five Six Seven Eight Nine Ten Jack Queen King void fillDeck struct card d 初始化 int i for i 0 i 52 i d i suit i 13 d i face i 13 void shuffle struct card d 洗牌 int i j struct card t srand time NULL for i 0 i 52 i j rand 52 t d j d j d i d i t void dispense card d card d1 card d2 card d3 card d4 发牌 for int j 0 j 52 j switch j 4 case 0 d1 j 4 d j break case 1 d2 j 4 d j break case 2 d3 j 4 d j break case 3 d4 j 4 d j break void show struct card d int n 显示 int i for i 0 i n i printf 5s of 8s s face d i face suit d i suit i 0 card d1 13 d2 13 d3 13 d4 13 void main fillDeck deck shuffle deck show deck 52 printf n dispense deck d1 d2 d3 d4 show d1 13 printf n show d2 13 printf n show d3 13 printf n show d4 13 printf n 7 编写实现将两个已知的有序链表合并成一个有序链表的函数 答 include include struct intNode 整数链表表元类型 int value 存放整数 struct intNode next 存放后继表元的指针 struct intNode root 有序链表合并 intNode linkMager intNode h1 intNode h2 有序链表合并 intNode head t q p1 p2 p1 h1 p2 h2 head t NULL while p1 if p1 value value q value p1 value p1 p1 next else q value p2 value p2 p2 next if t NULL head t q else t next q t t next while p1 q struct intNode malloc sizeof struct intNode q value p1 value p1 p1 next if t NULL head t q else t next q t t next while p2 q struct intNode malloc sizeof struct intNode q value p2 value p2 p2 next if t NULL head t q else t next q t t next if t t next NULL return head void travelLink struct intNode h struct intNode p h while p NULL printf 4d p value 输出表元的值 p p next 准备访问下一个表元 printf n n 创建整数有序链表 intNode createLink struct intNode h 链表的头指针 p q1 q2 int x char c h NULL printf 输入整数序列 直至遇非整数字符结束 n while scanf d p value x q1 h q2 NULL while q1 p next q1 if q2 NULL h p else q2 next p do scanf c while c n return h void main intNode h1 createLink travelLink h1 intNode h2 createLink travelLink h2 intNode h linkMager h1 h2 travelLink h 8 编写三个链表复制函数 第一个是复制出相同链接顺序的链表 第二个是复制出链接顺 序相反的链表 第三个是复制出有序链表 答 struct intNode copyLink1 struct intNode h 复制出链接顺序相同的链表 struct intNode n t p n t NULL while h p struct intNode malloc sizeof struct intNode p value h value p next NULL if t NULL n t p else t t next p h h next return n struct intNode copyLink2 struct intNode h 复制出链接顺序相反的链表 struct intNode n p n NULL while h p struct intNode malloc sizeof struct intNode p value h value p next n n p h h next return n struct intNode copyLink3 struct intNode h 复制出自小到大有序链接的链表 struct intNode n u v p n NULL while h p struct intNode malloc sizeof struct intNode p value h value for u NULL v n v NULL u v v v next p next v if v n n p else u next p h h next return n 9 编写从 3 个有序整数链表中找出第 1 个共有整数的函数 答 int commonVal intNode h1 intNode h2 intNode h3 int xp do if h1 NULL h2 NULL h3 NULL return 0 if h1 value value h1 h1 next continue else if h1 value h2 value h2 h2 next continue if h3 value h2 value break if h3 value value h3 h3 next else h1 h1 next h2 h2 next while 1 xp h3 value return 1 10 令整数链表的表元包含两个指针成分 一个用于指出从小到大的链接顺序 另一个用于 输入的先后顺序 答 include include struct intNode2 int value struct intNode2 inOrder struct intNode2 sizeOrder struct intNode2 makeLink struct intNode2 h 链表的头指针 tail 链表末尾表元的指针 p u v int x h tail struct intNode2 malloc sizeof struct intNode2 h inOrder NULL h sizeOrder NULL printf Input data n while scanf d p value x p inOrder NULL tail tail inOrder p for u h v h sizeOrder v NULL p sizeOrder v u sizeOrder p return h void main struct intNode2 head p head makeLink printf 从大到小遍历 n for p head sizeOrder p p p sizeOrder printf 5d p value printf n printf 输入顺序遍历 n for p head inOrder p p p inOrder printf 5d p value printf n 11 编写从无序的整数链表中找出最小元 并将它从链表中删除的函数 答 include include struct intNode int value struct intNode next struct intNode makeLink struct intNode h 链表的头指针 tail 链表末尾表元的指针 p int n h tail NULL printf Input data n while scanf d p value n p next NULL if h NULL h tail p else tail tail next p return h struct intNode searchMin struct intNode h struct intNode pre 在链表中找最小值表元 struct intNode minp mpre p q for mpre NULL minp h q NULL p h p q p p p next if minp value p value mpre q minp p pre mpre return minp int deleMin struct intNode hpt struct intNode p q p searchMin hpt if p NULL return 0 if q NULL hpt p next else q next p next free p return 1 void travelLink struct intNode h struct intNode p h while p NULL printf 4d p value 输出表元的值 p p next 准备访问下一个表元 printf n n void main struct intNode head head makeLink while head travelLink head deleMin 12 n 级法雷 Forder 序列 Fn是将分母小于等于 n 的不可约真分数按递增次序排列 并让 分数 0 1 作为序列的第一个元素 分数 1 1 作为序列的最后一个元素 例如 F5为 0 1 1 5 1 4 1 3 2 5 1 2 3 5 2 3 3 4 4 5 1 1 要求编写程序 输入正整数 n 输出 n 级法雷 Forder 序列 Fn 另外要求程序用链表 存储法雷序列 答 include include typedef struct node int numerator int denominator struct node next Link Link fn int gcd int int void insert int int void main int i j n c Link p printf 输入法雷序列的级数 n n scanf d fn Link malloc sizeof struct node fn numerator 0 fn denominator 1 fn next Link malloc sizeof struct node fn next numerator 1 fn next denominator 1 fn next next NULL for i n i 1 i for j 1 j next printf d d p numerator p denominator if c c 1 10 0 printf n printf n int gcd int a int b int r while r a b a b b r return b void insert int j int i Link u v w v fn while v denominator j v numerator i u v v v next w Link malloc sizeof struct node w numerator j w denominator i w next v u next w 13 试编写按以下加密规则对指定的加密钥匙 key 和原文字符串的加密函数 设原文字符串 有 n 个字符 生成的密文字符串也是 n 个字符 将密文字符串的 n 个字符位置按顺时 针顺序连成一个环 加密时 从环的起始位置起顺时针方向计数 每当数到第 key 个字 符位置时 从原文字符串的第一个字符开始 依次将原文中的当前字符放入该密文字符 位置中 已填入字符的密文字符位置以后不再在环上计数 重复上述过程 直至原文的 n 个字符全部放入密文环中 由此产生的密文环上的字符序列即为原文的密文 答 如有 key 3 原文为 THIS IS AN DECODING SYSTEM 则密文为 AOTGNHEDI YS D IMIETSNC SS 而当 key 4 时 同样的原文 新的密文为 SSDTYD HTEGIASISCNM E ION include include include typedef struct node char ch struct node forward CODE char decode char int void main char old 256 int key num 0 printf n 请输入原文 n gets old do printf 请输入密匙 k 1 scanf d while key 1 printf 原文 s n 密文 s n n old decode old key char decode char old int key char newstr int len count i CODE loop p len strlen old loop CODE malloc len sizeof CODE for i 0 i len 1 i loop i forward loop i 1 顺序连接 loop len 1 forward loop 末位置的后继是首位置 构成环 for p loop len 1 i 0 i len i for count 1 count forward 前进 key 1 个位置 p forward ch old 为当前位置填字符 p forward p forward forward 当前位置从环上退出 newstr char malloc len 1 从环上取下字符 for i 0 i len i newstr i loop i ch newstr len 0 return newstr 14 用带辅助表元的有序整数链表表示整数集合 分别编写已知两个集合求集合和 S1 S1 S2 集合差 S1 S1 S2 集合交 S1 S1 S2 的函数 运算结果在链表 S1 设 S1 2 3 5 6 S2 3 4 6 8 则有 集合和 S1 S2 2 3 4 5 6 8 集 合差 S1 S2 2 5 集合交 S1 S2 3 6 答 include include include typedef struct node 集合元素类型 int ele struct node next EleNode 有序链表表示的集合初始化 void initSets EleNode S 集合初始化 设置空集合 S EleNode malloc sizeof EleNode S next NULL S ele 1 新元素加入到有序链表表示的集合 把新元素 a 加入到指定集合中 若集合已有此元素 则函数返回 0 否则函数返回 1 int insertEle int a EleNode S EleNode p S next q S s while p NULL if p NULL s EleNode malloc sizeof EleNode s ele a s next p q next s return 1 从有序链表表示的集合删除元素 从指定集合中删除成员 a 若集合不空且元素 a 在集合中 函数返回 1 否则返回 0 int deleteEle int a EleNode S EleNode p S next q S while p NULL if p NULL free p return 1 return 0 有序链表表示的集合的并操作 集合 S1 与 S2 的并 结果在 S1 中 void unionSet EleNode S1 EleNode S2 EleNode p S1 next q S2 next t S1 while p NULL p p next q q next else if p ele ele S1 的当前元素小 将它接在新链表上 t next p p p next else S2 的当前元素小 复制结点接在新链表上 t next EleNode malloc sizeof EleNode t next ele q ele q q next t t next if p NULL t next p S1 未扫视完 链接之 else S2 集合未扫视完 逐一复制到新的 S1 while q NULL t next EleNode malloc sizeof EleNode t next ele q ele t t next q q next t next NULL 链表收尾 有序链表表示的集合的交操作 集合 S1 与 S2 的交 结果在 S1 中 void intersectionSet EleNode S1 EleNode S2 EleNode p S1 next q S2 next t S1 while p NULL p p next q q next else if p ele ele S1 的当前元素小 删除该元素 t next p next free p p t next else S2 的当前元素小 q q next while p NULL t next p next free p p t next 有序链表表示的集合的差操作 集合 S1 与 S2 的差 结果在 S1 中 void differenceSet EleNode S1 EleNode S2 EleNode p S1 next q S2 next t S1 while p NULL free p p t next q q next else if p ele ele S1 的当前元素小 删除该元素 t t next p p next else S2 的当前元素小 继续向前检测 q q next void outputSet EleNode S 输出集合 EleNode p S next if p NULL printf 空集合 n return while p printf 4d p ele p p next printf n void main EleNode ss 20 int si 0 char menuName 创建一个集合 向集合插入一个元素 从集合删除一个元素 输出集合 求集合和 求集合差 求集合交 int ans k s1 s2 while 1 printf 请选择以下菜单命令 n for k 0 menuName k 0 0 k printf t d s n k 1 menuName k printf t 其他选择结束程序运行 n scanf d if ansk break switch ans case 1 initSets si break case 2 printf 指定集合号 d si scanf d printf 输入插入元素 scanf d insertEle s1 ss k break case 3 printf 指定集合号 d si scanf d printf 输入删除元素 scanf d deleteEle s1 ss k break case 4 printf 指定集合号 d si scanf d outputSet ss k break case 5 printf 指定集合号 1 d si scanf d printf 指定集合号 2 d d si s1 scanf d unionSet ss s1 ss s2 break case 6 printf 指定集合号 1 d si scanf d printf 指定集合号 2 d d si s1 scanf d differenceSet ss s1 ss s2 break case 7 printf 指定集合号 1 d si scanf d printf 指定集合号 2 d d si s1 scanf d intersectionSet ss s1 ss s2 break 15 用不带辅助表元的有序整数链表表示整数集合 分别编写已知两个集合求集合和 S S1 S2 集合差 S S1 S2 集合交 S S1 S2 的函数 运算结果产生一个新链表 答 include include include typedef struct node 集合元素类型 int ele struct node next EleNode 有序链表表示的集合初始化 void initSets EleNode s 集合初始化 设置空集合 s NULL 新元素加入到有序链表表示的集合 把新元素 a 加入到指定集合中 若集合已有此元素 则函数返回 0 否则函数返回 1 int insertEle int a EleNode s EleNode p s q NULL u while p NULL if p NULL u EleNode malloc sizeof EleNode u ele a u next p if q NULL s u else q next u return 1 从有序链表表示的集合删除元素 从指定集合中删除成员 a 若集合不空且元素 a 在集合中 函数返回 1 否则返回 0 int deleteEle int a EleNode s EleNode p s q NULL while p NULL if p NULL else q next p next free p return 1 return 0 有序链表表示的集合的并操作 集合 S1 与 S2 的并 结果在 S1 中 EleNode unionSet EleNode S1 EleNode S2 EleNode head NULL p