NO2 线性表下载_PPT模板_50

is_964693

暂无简介

NO2 线性表nullnull第2章线性表null逻辑结构：线性结构存储结构：顺序存储链式存储顺序表 (Sequential List)顺序表 (Sequential List)顺序表的定义和特点定义 n（  0）个表项的有限序列（a1, a2, …, an） ai是表项，n是表长度。特点顺序存取遍历逐项访问从前向后从后向前从两端向中间顺序表(SeqList)类的定义顺序表(SeqList)类的定义template class Seq...

nullnull第2章线性

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

null逻辑结构：线性结构存储结构：顺序存储链式存储顺序表 (Sequential List)顺序表 (Sequential List)顺序表的定义和特点定义 n（  0）个表项的有限序列（a1, a2, …, an） ai是表项，n是表长度。特点顺序存取遍历逐项访问从前向后从后向前从两端向中间顺序表(SeqList)类的定义顺序表(SeqList)类的定义template class SeqList { Type *data; //顺序表存储数组 int MaxSize; //最大允许长度 int last; //当前最后元素下标 public: SeqList ( int MaxSize = defaultSize ); ~SeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } int Find ( Type & x ) const;null int Insert ( Type & x, int i ); int Remove ( Type & x ); int Next ( Type & x ) ; int Prior ( Type & x ) ; int IsEmpty ( ) { return last ==-1; } int IsFull ( ) { return last == MaxSize-1; } Type Get ( int i ) { return i < 0 || i > last？NULL : data[i]; } } 顺序表部分公共操作的实现顺序表部分公共操作的实现 template SeqList :: SeqList ( int sz ) { //构造函数 if ( sz > 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; if ( data == NULL ) { MaxSize = 0; last = -1; return; } } }nulltemplate int SeqList::Find ( Type & x ) const { //搜索函数：在表中从前向后顺序查找 x int i = 0; while ( i <= last && data[i] != x ) i++; if ( i > last ) return -1; else return i; }顺序搜索图示顺序搜索图示 x = 48 x = 50null搜索成功若搜索概率相等，则搜索不成功数据比较 n 次null表项的插入nulltemplate int SeqList::Insert ( Type & x, int i ){ //在表中第 i 个位置插入新元素 x if ( i < 0 || i > last+1 || last == MaxSize-1 ) return 0; //插入不成功 else { last++; for ( int j = last; j > i; j-- ) data[j] = data[j -1]; data[i] = x; return 1; //插入成功 } }null表项的删除null template int SeqList::Remove ( Type & x ) { //在表中删除已有元素 x int i = Find (x); //在表中搜索 x if ( i >= 0 ) { last-- ; for ( int j = i; j <= last; j++ ) data[j] = data[j+1]; return 1; //成功删除 } return 0; //表中没有 x }null顺序表的应用：集合的“并”运算 template void Union ( SeqList & LA, SeqList & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); for ( int i = 0; i < m; i++ ) { Type x = LB.Get(i); //在LB中取一元素 int k = LA.Find (x); //在LA中搜索它 if ( k == -1 ) //若未找到插入它 { LA.Insert (n, x); n++; } } }null template void Intersection ( SeqList & LA, SeqList & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); int i = 0; while ( i < n ) { Type x = LA.Get (i); //在LA中取一元素 int k = LB.Find (x); //在LB中搜索它 if ( k == -1 ) { LA.Remove (i); n--; } else i++; //未找到在LA中删除它 } }顺序表的应用：集合的“交”运算多项式 (Polynomial)多项式 (Polynomial)n阶多项式 Pn(x) 有 n+1 项。系数 a0, a1, a2, …, an 指数 0, 1, 2, …, n。按升幂排列多项式(Polynomial)的抽象数据类型class Polynomial { public: Polynomial ( ); //构造函数 float Coef ( int e); int LeadExp ( ); //返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); //求值 }多项式(Polynomial)的抽象数据类型创建power类，计算x的幂 #include class power { double x; int e; double mul; public: power (double val, int exp); //构造函数 double get_power ( ) { return mul; } //取幂值 };创建power类，计算x的幂null power::power (double val, int exp) { //按val值计算乘幂 x = val; e = exp; mul = 1.0; if ( exp == 0 ) return; for ( ; exp>0; exp--) mul = mul * x; } main ( ) { power pwr ( 1.5, 2 ); cout << pwr.get_power ( ) << “\n”; }多项式的存储表示多项式的存储表示第一种： private: (静态数 int degree; 组表示) float coef [maxDegree+1]; Pn(x)可以表示为： pl.degree = n pl.coef[i] = ai, 0  i  nnull第二种：private: (动态数 int degree; 组表示) float * coef; Polynomial::Polynomial (int sz) { degree = sz; coef = new float [degree + 1]; } 以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如 P101(x) = 3 + 5x50 - 14x101, 不经济。null第三种： class Polynomial; class term { //多项式的项定义 friend Polynomial; private: float coef; //系数 int exp; //指数 };nullclass Polynomial { //多项式定义 public: …… private: static term termArray[MaxTerms]; //项数组 static int free; //当前空闲位置指针 // term Polynomial::termArray[MaxTerms]; // int Polynomial::free = 0; int start, finish; //多项式始末位置 } null A(x) = 2.0x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 两个多项式存放在termArray中两个多项式的相加两个多项式的相加结果多项式另存扫描两个相加多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。nullPolynomial Polynomial::operator+(Polynomial B) { Polynomial C; int a = start; int b = B.start; C.start = free; float c; while ( a <= finish && b <= B.finish ) Switch ( compare ( termArray[a].exp, termArray[b].exp) ) { //比较对应项指数 case ‘=’ : //指数相等 c = termArray[a].coef + //系数相加 termArray[b].coef; if ( c ) NewTerm ( c, termArray[a].exp ); a++; b++; break; null case ‘>’ : //b指数小, 建立新项 NewTerm ( termArray[b].coef, termArray[b].exp ); b++; break; case '<': //a指数小, 建立新项 NewTerm ( termArray[a].coef, termArray[a].exp ); a++; } for ( ; a <= finish; a++ ) //a未检测完时 NewTerm ( termArray[a].coef, termArray[a].exp ); null for ( ; b <= B.finish; b++ ) //b未检测完时 NewTerm ( termArray[b].coef, termArray[b].exp ); C.finish = free-1; return C; }null在多项式中加入新的项 void Polynomial::NewTerm ( float c, int e ) { //把一个新的项加到多项式C(x)中 if ( free >= maxTerms ) { cout << "Too many terms in polynomials” << endl; return; } termArray[free].coef = c; termArray[free].exp = e; free++; } null 链表是用链接（拉链）存储的N（N>=0）个表项的序列。适用于经常要进行插入，删除以及存储空间不定的情形。链表又分为单链表，循环链表以及双向链表。单链表链表null循环链表双向链表1 单链表1 单链表 (Singly Linked List)1) 单链表的结构：null2) 单链表的类定义在类定义中要使用两个类来协同表示单链表： ListNode类（结点类） List类（链表类） Class List ; //List类的前视声明 Class ListNode { friend class List ; //声明List类为友元类 private : int data ; //这里假设数据域为整型 ListNode * link ; };nullClass List { public : ------- private : ListNode * first , * last ; //指向链表表头的指针与表尾指针 }; 3) 单链表的插入与删除 (1)单链表的插入要求在单链表(a0,a1,a2,-----an-1) ai前插入一个新元素x ,这里i=0,1,2----,n 分析：第一种情况：ai是第一个结点的数据(a0)null如果 First: NewNode = new ListNode(x,Null) NewNode link=First; First=NewNode; null第二种情况：ai的i=1,2,----,n-1 找到含ai-1的结点，由p指向 NewNodelink=plink; plink=NewNode; 第三种情况：ai的i为n，即在最后一个结点的后面插入一个元素 null null(2）单链表的删除：删除第i个结点（i=0,1,2----,n-1) 第一种情况：删除第一个结点a0 第二种情况：删除除a0与an-1结点以外的结点，找到ai-1 结点，让p指向它，再进行删除。第三种情况：删除尾结点，与第二种情况相同，多一个动作，重置Last指针。不管那一种情况，一定要找到(i-1)位置，让p指向它。First a0 a1ai-1ai+1an-1ai an-2 Last null4) 带表头结点的单链表从上面插入与删除算法可以看到在第一个结点前面插入一个元素，或删除一个结点都要与一般情况区分开来处理，为了统一处理，可在表中增加一个表头结点，即nullnull三种情况统一为：NewNodelink=plink; if (plink= =Null) last=NewNode; Plink=NewNode; *删除：统一为： q=Plink; Plink=qlink; Delete q; if (Plink= =Null ) last=P :null5) 静态链表（用数组来实现链表）null link域：伪指针，指向下一个元素在数组中的下标，而不是真正的地址为什么称静态：因为数组表示，运行过程中存储空间大小不会变化。与真指针的区别： P=A[P].link , A[P].data P=Plink Pdata 2.循环链表（Circular List）2.循环链表（Circular List）null带表头结点的循环链表null1) 循环链表的类定义用复合类：即定义循环链表结点类CircListNode与循环链表类 CircList *结点类：私有数据同单链表结点类 *循环链表类：私有数据比单链表类多了一个当前指针nullEnum Boolean {False,True} template class CircList; template class CircListNode { friend class CircList; public: CircListNode(Type d=0,CircListNode *next=NULL): data(d),link(next){} private: Type data; CircListNode *link; } template class CircList { public: CircList ( Type value ) ; //构造函数null ~CircList( ); //析构函数 int Length( ) const; //计算循环链表长度 Boolean IsEmpty( ) {return firstlink= =first;} //判表空否 Boolean Find (const Type & value); //在循环链表中寻找其值等于value的结点 Type getData( ) const; //返回当前结点中存放的值 void Firster( ) {current=first;} //将当前指针置于头结点 Boolean First( ); //将当前指针指向链表的第一个结点null Boolean Next( ); //将当前指针指到当前结点的后继结点 Boolean Prior( ); //将当前指针指到当前结点的前驱结点 void Insert(const Type &value); //插入新结点 void Remove ( ); //删除当前结点 private: CircListNode *first,*current,*last; //头指针，当前指针，尾指针 }; null2) 用循环链表求解约瑟夫问题约瑟夫问题：实际上是一个游戏。

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

中以旅行社从n个旅客中选出一名旅客，为他提供免费环球旅行服务。 n=8，m=3（报数）从1号开始报数出列顺序为：3，6，1，5，2， 8，4。最后一个编号7的旅客将赢得环球旅游。null# include # include "CircList.h" Template < class Type > viod CircList < Type > :: Josephus( int n , int m ) { Firster(); for (int i=0;i clist; //定义循环链表clist并初始化 int n,m; //n是总人数,m是报数值 cout << “Enter the Number of Contestants?”; cin >> n >> m; for ( int i=1;i<=n;i++ ) clist.insert(i); //建立数据域为1,2,--- 的循环链表 clist.Josephus(n,m); //解决约瑟夫问题，打印胜利者编号 } 以上是用抽象数据类型来实现的. null回收一个循环链表 ListNode * p = L->link; L->link = Avail; Avail = p; 3 多项式及其相加3 多项式及其相加nullnull存放非零指数的系数与指数，因此每个结点有三个域组成。书中使用单链表的模板类来实现多项式的链表表示，每个 ListNode代表多项式中的一项：元素：nulldata的类型为Type，以后可实例化为int，float等。在这里为了表示多项式，把Type实例化为Term，而Term用Struct定义： coef（系数）和exp（指数） Struct Term { int coef; int exp; Void Init(int c , int e) { coef=c; exp=e;} } Class Polynomial { friend Polynomial operator + ( const polynomial & ,const polynomial &);null private: Listpoly; } 2) 多项式加法 A(X)+B(X)==》A(X)null 具体实现时，并不要再重新申请结点，完全利用原来两个链表的结点。方法：设4个流动指针： ListNode*pa, *pb, *pc, *p (指AH) (指BH) (指向结果) (工作流动指针,为释放结点用) 1)初始化：pc , pa , pb ,并把BH的表头结点删除了； 2)当pa和pb都有项时null pc永远指向相加时结果链表的最后一个结点。 a)指数相等( paexp= =pbexp ) 对应系数相加：pacofe=pacofe + pbcofe ; p= pb ; pb前进 ; 删除p所指结点; if (系数相加结果为0){p=pa; pa前进; 删除p所指结点} else { pclink=pa; pc=pa; pa前进} b)指数不等 paexp< pbexp //pb要插入结果链表 {pclink=pb ; pc=pb ; pb前进} c)指数不等 paexp> pbexp //pa要插入结果链表 {pclink=pa ; pc=pa ; pa前进} 3)当两链表中有一链表为空，则将另一链表链入结果链表就可以 null if (pb空了){ pclink=pa;} else pclink=pb; 算法分析：设两个多项式的长度分别是m和n，则总的比较次数为O(m+n)4 双向链表（Doubly Linked List)4 双向链表（Doubly Linked List)null 对于单链表或循环链表插入或删除都要知道两个指针(一前一后)，对双链表而言，只要知道一个。 p=plLinkrLink=prLinklLink;双链表部分成员函数的实现 null 插入 (Insert) 把含给定值Value的新结点插入到当前指针(current)所指结点的后面。非空表分析：*空表结点需要申请形成null currentrLink = new DblNode (value, current, currentrLink ); current = currentrLink ; currentrLinklLink = current ; 先假设插入的结点为p所指向的结点PlLink = current ; prLink = currentrLink ; currentrLink = p ; current = currentrLink ; currentrLinklLink = current ;null 删除 (删除current所指向的结点) currentrLinklLink = currentlLink ; currentlLinkrLink = currentrLink ;

本文档为【NO2 线性表】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

NO2 线性表

热门搜索

历史搜索