《复习-第2章-2剖析》由会员分享，可在线阅读，更多相关《复习-第2章-2剖析（47页珍藏版）》请在金锄头文库上搜索。
1、线性表是一种最简单的线性结构,线形表基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,顺序表,typedef struct ElemType *elem; int length; int listsize; SqList; / 俗称 顺序表,头结点,头指针,头指针,空指针,线性表为空表时， 头结点的指针域为空,Typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList; LinkList L； / L 为的头指针,单链表,带头结点的单链表,typedef struct
2、LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position; typedef struct / 链表类型 Link head; / 指向头结点的指针 Link tail; / 指向最后一个结点的指针 int len; / 链表长度 Link current; / 指向当前被访问的结点 /初始位置指向头结点 LinkList;,初始化操作：构造一个空的线性表,Status InitList(LinkList ,销毁操作： 销毁线性表,void DestroyList(LinkList ,置空操作： 清空线性表的元素,void
3、ClearList(LinkList ,在当前位置之后插入数据元素,Status InsertAfter(LinkList ,在表中查找数据元素，让当前指针指向该结点,Status LocateElem(LinkList ,线性表就地逆转,void ListReverse(LinkList ,class LinkList public: Link head, tail, current; int lenth; LinkList(); LinkList(); Status LocatePos(int i ); Status InsertAfter(ElemType e); Status Loca
4、teElem(LinkList ,用C+的类实现单链表,LinkList :LinkList() head = new LNode; if(!head) exit(-1); head-next = 0; tail = head; current = head; lenth = 0; LinkList :LinkList() Link p; while(head) p = head-next; delete head; head = p; ,用C+的类实现单链表,int main() LinkList L; /从文本文件“a.txt”中读入数据到单链表L L.LocatePos(0); /改变当
5、前指针指向表的头结点 while(1) if (fscanf(fp, “%d“, ,用C+的类实现单链表,双向循环链表,空表,非空表,a1 a2 . an,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,长整数,/ 结点类型 typedef struct DuLNode int data; DuLNode *next; DuLNode *prior; DuLNode, *DuLi
6、nk; / 长整数类型，带头结点的双向循环链表 typedef DuLink LongInt;,初始化,/构造一个长整数 Status Init(LongInt ,销毁和清空,void Destroy(LongInt ,插入、删除、显示,/在表头插入数据元素e void InsertHead(LongInt &L, int e)； /在表尾插入数据元素e void InsertTail(LongInt &L, int e)； /从链表头删除 void DeleteHead(LongInt &L)； /显示长整数 void Show(LongInt L)；,创建,/利用输入字符串创建长整数 /如
7、 “ -123456 “ 变成 “-“, “12“, “3456“，再存储 bool Create(LongInt ,创建,int len = 0; /计算连续 数字字符 的个数 while(*p) if(*p = 0 ,创建,int i = len % 4; / i 表示每4个数字一组的分割 int t = 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; return true; ,长整数的加法,/a, b 两个
8、长整数相加，结果存放到 c 中 void Add(LongInt a, LongInt b, LongInt &c) /置空长整数c /从低位开始相加 /调整相加后的结果 ,长整数的加法,/变量定义 DuLink pa, pb, pc; /指向a, b, c结点的指针 int sign_a, sign_b; /长整数a, b 的符号标志 int sign; /相加结果 c 符号标志 int sum; /结点相加中间变量 /置空长整数c Clear(c); /从低位开始相加 pa = a-prior; pb = b-prior; sign_a = a-data; sign_b = b-data;
9、,长整数的加法,/从低位开始相加 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) int m = c-next-data; if(m = 0) D
10、eleteHead(c); else sign = m 0 ? 1 : -1; c-data = sign; break; /调整进位和借位 /除去前面的0 ,长整数的加法,/调整进位和借位 pc = c-prior; int f = 0; /进位标志 while(pc != c) sum = (pc-data + f) * sign; if(sum data = sum + 10000; else if(sum = 10000) f = sign; pc-data = sum - 10000; else f = 0;pc-data = sum; pc = pc-prior; if(f !=
11、0) /判断调整结果是否有最高位的进位 InsertHead(c, 1);,长整数的加法,/去掉调整后结果中高位的0 while(!IsEmpty(c) int m = c-next-data; if(m = 0) DeleteHead(c); else break; ,长整数的减法,/a, b 两个长整数相减，结果存放到 c 中 void Sub(LongInt a, LongInt b, LongInt ,用C+类class实现长整数-结点类型,typedef struct DuLNode int data; DuLNode *next; DuLNode *prior; DuLNode,
12、*DuLink;,class实现长整数-长整数类型,class LongInt public: DuLink L; LongInt(); /构造一个长整数 LongInt ( const LongInt /显示长整数,class实现长整数-长整数类型,class LongInt /利用输入字符串创建长整数 /如 “ -123456 “ 变成 “-“, “12“, “3456“， /再存储到长整数数据类型中 bool Create (char *exp); LongInt,class实现长整数-拷贝构造函数,LongInt: LongInt (const LongInt ,拷贝构造函数,在C+中
13、，下面三种对象需要调用拷贝构造函数： 一个对象作为函数参数，以值传递的方式传入函数体； 一个对象作为函数返回值，以值传递的方式从函数返回； 一个对象用于给另外一个对象进行初始化； 隐式的拷贝构造函数： 如果在类中没有显式的声明一个拷贝构造函数，那么，编译器会自动生成一个来进行对象之间成员的位拷贝（Bitwise Copy） 包含动态分配成员的类除提供拷贝构造函数外，还应该考虑重载“=“赋值操作符号,class实现长整数 重载=,LongInt ,class实现长整数 重载+,LongInt LongInt: operator+ ( const LongInt ,class实现长整数 重载+,/
14、处理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.IsEm
15、pty() int m = 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; int f = 0; while(pc != c.L) sum = (pc-data + f) * sign; if(sum data = sum + 10000; else if(sum = 10000) f = sign; pc-data = sum 10000; else f = 0; pc-data = sum; pc = pc-prior; ,class实现长整数 重载+,/判断调整结果是否有最高位的进位，如果有则添加节点 if(f != 0
