复习-第2章-3-第3章-1.ppt

双向循环链表 空表 非空表 a1a2 an typedefstructDuLNode ElemTypedata 数据域structDuLNode prior 指向前驱的指针域structDuLNode next 指向后继的指针域 DuLNode DuLinkList 长整数 结点类型typedefstructDuLNode intdata DuLNode next DuLNode prior DuLNode DuLink 长整数类型 带头结点的双向循环链表typedefDuLinkLongInt 初始化 构造一个长整数StatusInit LongInt 销毁和清空 voidDestroy LongInt 插入 删除 显示 在表头插入数据元素evoidInsertHead LongInt L inte 在表尾插入数据元素evoidInsertTail LongInt L inte 从链表头删除voidDeleteHead LongInt L 显示长整数voidShow LongIntL 创建 利用输入字符串创建长整数 如 123456 变成 12 3456 再存储boolCreate LongInt 创建 intlen 0 计算连续数字字符的个数while p if p 0 创建 inti len 4 i表示每4个数字一组的分割intt 0 while p 存储其他节点 if p 9 break t p 0 i if i 0 i 4 if i 0 InsertTail L t t 0 t 10 returntrue 长整数的加法 a b两个长整数相加 结果存放到c中voidAdd LongInta LongIntb LongInt c 置空长整数c 从低位开始相加 调整相加后的结果 长整数的加法 变量定义DuLinkpa pb pc 指向a b c结点的指针intsign a sign b 长整数a b的符号标志intsign 相加结果c符号标志intsum 结点相加中间变量 置空长整数cClear c 从低位开始相加pa a prior pb b prior sign a a data sign b b data 长整数的加法 从低位开始相加while pa a 长整数的加法 将多出来的位加到c中while pa a a的位数比b多 处理a的剩余位 InsertHead c sign a pa data pa pa prior while pb b b的位数比a多 处理b的剩余位 InsertHead c sign b pb data pb pb prior 长整数的加法 调整相加后的结果c 除去前面的0 判断结果c的符号while IsEmpty c intm c next data if m 0 DeleteHead c else sign m 0 1 1 c data sign break 调整进位和借位 除去前面的0 长整数的加法 调整进位和借位pc c prior intf 0 进位标志while pc c sum pc data f sign if sumdata sum 10000 elseif sum 10000 f sign pc data sum 10000 else f 0 pc data sum pc pc prior if f 0 判断调整结果是否有最高位的进位InsertHead c 1 长整数的加法 去掉调整后结果中高位的0while IsEmpty c intm c next data if m 0 DeleteHead c elsebreak 长整数的减法 a b两个长整数相减 结果存放到c中voidSub LongInta LongIntb LongInt 用C 类class实现长整数 结点类型 typedefstructDuLNode intdata DuLNode next DuLNode prior DuLNode DuLink class实现长整数 长整数类型 classLongInt public DuLinkL LongInt 构造一个长整数LongInt constLongInt 显示长整数 class实现长整数 长整数类型 classLongInt 利用输入字符串创建长整数 如 123456 变成 12 3456 再存储到长整数数据类型中boolCreate char exp LongInt class实现长整数 拷贝构造函数 LongInt LongInt constLongInt 拷贝构造函数 在C 中 下面三种对象需要调用拷贝构造函数 一个对象作为函数参数 以值传递的方式传入函数体 一个对象作为函数返回值 以值传递的方式从函数返回 一个对象用于给另外一个对象进行初始化 隐式的拷贝构造函数 如果在类中没有显式的声明一个拷贝构造函数 那么 编译器会自动生成一个来进行对象之间成员的位拷贝 BitwiseCopy 包含动态分配成员的类除提供拷贝构造函数外 还应该考虑重载 赋值操作符号 class实现长整数 重载 LongInt class实现长整数 重载 LongIntLongInt operator constLongInt class实现长整数 重载 处理a b中相同位阶的数while pa a L class实现长整数 重载 while pa a L a的位数比b多 处理a的剩余位 sum pa data sign a c InsertHead sum pa pa prior while pb L b的位数比a多 处理b的剩余位 sum pb data sign b c InsertHead sum pb pb prior class实现长整数 重载 调整相加后的结果c 去掉计算结果中高位的0 并计算结果的符号sign 正负 while c IsEmpty intm c L next data if m 0 c DeleteHead else sign m 0 1 1 c L data sign break class实现长整数 重载 调整各个节点 使之与符号位相符pc c L prior intf 0 while pc c L sum pc data f sign if sumdata sum 10000 elseif sum 10000 f sign pc data sum 10000 else f 0 pc data sum pc pc prior class实现长整数 重载 判断调整结果是否有最高位的进位 如果有则添加节点if f 0 c InsertHead 1 while c IsEmpty 去掉调整后结果中高位的0 intm c L next data if m 0 c DeleteHead elsebreak returnc 通常称 栈和队列是限定插入和删除只能在表的 端点 进行的线性表 3 2 1 栈的操作 InitStack S DestroyStack S ClearStack S StackEmpty s StackLength S GetTop S e Push S e Pop S e 栈的基本操作 一个栈的输入序列为123 n 若输出序列的第一个元素是n 输出第i 1 i n 个元素是 a 不确定b n i 1c id n i一个栈的进栈序列为 a b c d e