线性表顺序表稀疏矩阵字符串.ppt
《线性表顺序表稀疏矩阵字符串.ppt》由会员分享,可在线阅读,更多相关《线性表顺序表稀疏矩阵字符串.ppt(114页珍藏版)》请在三一文库上搜索。
1、线性表 顺序表 稀疏矩阵 字符串,第二章 数组,一、线性表,线性表 相同数据类型的元素的有限序列 叫线性表。 (a1, a2, ,an-1, an) a1为首元,an为末元, n叫线性表的长度 ai的后继是ai+1, i=1, ,n-1. an没有后继。 ai的前驱是ai-1, i=2, ,n. a1没有前驱。 ai可以是基本数据类型也可以是struct 类型。 没有数据的线性表叫空表。空表的长度n=0。,a1,a2,a3,a4,a5,a6,线性表是最简单的也是最基本的数据结构。,线性表可以用来构造字符串,集合,栈,队列,用来排序。 线性表可以顺序表示用一组地址连续的存储单元一次存储数据元素。
2、 线性表也可以用线性链表表示。,二、顺序表线性表的顺序表示,可以用通用数组定义通用线性表。 通用数组是可变长度的数组,也叫安全数组。,类模版 通用数据类型 /array.h 例. 通用数组 抽象数组类型 template class Array T *alist; /指针数据 表示一个数组 int size; /表示数组长度 public: Array(int s=50) /构造函数 Array(const Array /输出操作重载 ;,#include ,template class SeqList Arraylistitem; /list storage array int size;
3、public: SeqList(void); / constructor构造函数 / list access methods 线性表的访问操作 int ListSize(void) const; /取线性表的长 int ListEmpty(void)const; /问表是否空表 int Find (T /取线性表中元素,/ list modification methods线性表的修改操作,void Insert(const T,/ constructor. set size to 0,template SeqList:SeqList(void): listitem(size),size(0)
4、 ,/ return number of elements in list,template int SeqList:ListSize(void) const return size; ,/ tests for an empty list,template int SeqList:ListEmpty(void) const return size = 0; ,/ clears list by setting size to 0,template void SeqList:ClearList(void) size = 0; ,/ Take item as key and search the l
5、ist. /return True if item is in the list and,/ false otherwise. If found, assign the list / element to the reference parameter item. template int SeqList:Find(T / return False when list empty,while(isize &!(item=listitemi),i+; if (i size) item = listitemi; / assign list element to item return 1; / r
6、eturn True else return 0; / return false ,/ insert item at the rear of the list.,template void SeqList:Insert(const T / increment list size ,template /在第i位插入,void SeqList:Insert(const T,/shift the tail of the list /to the right one position,while (k = i) listitemk+1 = listitemk; k-; listitemi = item
7、; size+; / increament list size ,/search for item in the list /and delete it if found,template void SeqList:Delete(const T if (i size) / successful if i size ,/ shift the tail of the list /to the left one position,while (i size-1) listitemi = listitemi+1; i+; size-; / decreament size ,/delete elemen
8、t at front of list and return / its value. terminate the program with / an error message if the list is empty.,template T SeqList:DeleteFront(void) T frontItem; / list is empty if size = 0 if (size = 0) cerr “Attempt to delete the front / of an empty list!“ endl; exit(1); ,frontItem = listitem0; / g
9、et value from position 0. Delete(frontItem); / delete the first item and shift terms return frontItem; / return the original value ,/ return value at position pos in list. / if pos is not valid list position, / teminate program with an error message. template T SeqList:GetData(int pos) const / termi
10、nate program if pos out of range if (pos = size) cerr “pos is out of range!“ endl; exit(1); return listitempos; ,测试,#include “ iostream.h” #include “aseqlist.h” void main(void) SeqList a,b; int x; for(int i=0;ix; b.Insert(x+1); for(i=0;i20;i+) couta.GetData(i) ; coutendl;,for(i=0;i20;i+) coutb.GetDa
11、ta(i) ; coutendl; a.Insert(99,0); a.Insert(98,10); a.Insert(97,20); a.Insert(96,30); int k=a.ListSize( ); for(i=0;ik;i+) couta.GetData(i) ; coutendl; ,顺序表应用的例:,1. 用顺序表做插入,选择排序. 2. 合并两个已排序的线性表 3. 用顺序表做集合: 只插入不重复的元素 4. 求两个集合的交合并 5. 表示一个多项式 6. 求多项式的和差积商,微分,积分 7. 存储一个矩阵, 求矩阵的和,积,逆,顺序线性表复杂度分析,从已建立的顺序表中“取
12、表长” ,“取第i个元素”的复杂性是O(1), 2. 在表长n的顺序表第i位前插入一个元素,要把表尾n-i+1个元素后移一格。 假设每一位都插入一个数,从第1位到末尾第n+1位,总移动次数是: i=1i=n+1(n-i+1)=1+2+n=n*(n+1)/2 平均复杂度为O(n/2). 3. 删除第i位元素,要把表尾n-i个元素前移一格。假设每一位都删除一个数,从第1位到末尾第n位,总移动次数是: i=1i=n+1(n-i)=1+2+(n-1)=n*(n-1)/2 平均复杂度为O(n-1)/2).,一个阶数很高的矩阵中如果有许多相等的元素,或零元素,成为特殊矩阵。 对特殊矩阵可以进行压缩存储,三
13、、稀疏矩阵,特殊矩阵,对称矩阵 上(下)三角矩阵 对角矩阵 稀疏矩阵,对称矩阵,矩阵 A=(aij)n,n aij= aji , 0i,jn 每一对元素分配一个存储空间,可以 将n2个元素存储到n(n+1)/2个空间中,下三角矩阵,a11 a21a22 a31a32 a33 an1an2 an3 ann,1+2+3+ +n=n(n+1)/2 T sn(n+1)/2;,k=i(i-1)/2+j-1; ij; k=j(j-1)/2+i-1; ij. s12=aij=aji; i=4, j=3,s0=a11; s1=a21; sk=aij,对角矩阵,a11 a12 a21 a22 a23 an-1n
14、 ann-1 ann,sk=aij; k=3(i-1)+j; j=k%3; i=(k-j)/3,稀疏矩阵 Sparse Matrix,m*n阶矩阵 A=(aij)mn 中有t个非零元素, 如果 =t/(m*n)5%, 称A为稀疏矩阵,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,/smatrix.dat,6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,稀疏矩阵的存储,row col ele
15、m 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,template class Triple public: int row, col; T elem; SetVal(int r,int c,T d) elem=d;row=r;col=c; ;,稀疏矩阵元素的类TRiple,稀疏矩阵类的定义,#define MAXSIZE 500 template class SparseMatrix Triple dataMAXSIZE+1; int mu, nu, tu; /行数、列数、元素个数 public: SparseMatrix( )m
16、u=nu=tu=0; SparseMatrix(char*filename); SparseMatrix Transpose( ); SparseMatrix Add(SparseMatrix b); SparseMatrix Muliply(SparseMatrix b); void print( )const; ;,template SparseMatrix:SparseMatrix(char *filename) ifstream fin; int i,r,c; T d; fin.open(filename, ios:in | ios:nocreate); if (!fin) cerr
17、munutu; for (i = 1; i r cd; datai.SetVal(r,c,d); fin.close( ); ;,矩阵的转置 T=M,for(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol 时间复杂度O(mu*nu),M row col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,M row col elem 2 1 12 3 1 9 1 3 3 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7,M row col e
18、lem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,M row col elem 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14,稀疏矩阵的转置 T=M 算法5.1,template SparseMatrix SparseMatrix : Transpose( ) SparseMatrix temp; int i, j, k=1; temp.mu=nu; temp.nu=mu; temp.tu=tu; if(tu)for(i=1;i=nu;+i) for(j=1;j=t
19、u;+j) if(dataj.col=i) temp.datak.row=dataj.col; temp.datak.col=dataj.row; temp.datak.elem=dataj.elem; k+; return temp;,稀疏矩阵的转置的时间复杂度,O(nu*tu) 若tunu*mu O(nu*tu)=O(mu*nu*nu) 不是一个好算法! 应当改进!,快速转置 依次逐个对号入座,M row col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,M row col elem 2 1 12 3 1 9,先求
20、出M中每一列(即M中每一行)元素的个数numcol,确定M每行起始位置cpotcol。,快速转置,M row col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,快速转置算法5.2,template SparseMatrix SparseMatrix :Transpose( ) SparseMatrix temp; int i, j, k; int*num=new intnu+1; int* cpot=new intnu+1; cpot1=1; temp.mu=nu; temp.nu=mu;temp.tu=tu; if(
21、tu)for(i=1;i=nu;+i)numi=0; for(i=1;i=tu;+i)+numdatai.col; for(i=1;inu;+i)cpoti+1=cpoti+numi; for(i=1;i=tu;+i)j=datai.col;k=cpotj; temp.datak.row=j; temp.datak.col=datai.row; temp.datak.elem=datai.elem; +cpotj; return temp; ,时间复杂性O(nu+tu),稀疏矩阵的加法,template SparseMatrix SparseMatrix: Add(SparseMatrix b
22、 ) SparseMatrix temp; if(mu!=b.mu|nu!=b.nu) cerr“error ”end;return temp; temp.mu=mu; temp.nu=nu; int i=1, j=1, k=1; while(i=tu|j=b.tu) if(datai.rowb.dataj.row) | (datai.row=b.dataj.row) ,else if(datai.row=b.dataj.row) ,矩阵的乘法 Amp*Bpn,(aij)*(bij)=(1kpaik*bkj),2 0 0 -1 0 1 0 3 0 0 1 0,1 0 1 0 0 -1 0 0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 顺序 稀疏 矩阵 字符串
链接地址:https://www.31doc.com/p-3364461.html