数据结构复习笔记

1、第一章 概 论1. 数据：信息的载体 , 能被计算机识别、存储和加工处理。2. 数据元素： 数据的基本单位， 可由若干个数据项组成， 数据项是具有独立含义的最小标识 单位。3. 数据结构：数据之间的相互关系，即数据的组织形式。它包括： 1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/ 排序。4. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。5. 数据类

2、型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6. 抽象数据类型： 抽象数据的组织和与之相关的操作。 优点： 将数据和操作封装在一起实现 了信息隐藏。7. 抽象数据类型 ADT是在概念层上描述问题；类：是在实现层上描述问题；在应用层上 操作对象（类的实例）解决问题。8. 数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个 直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9. 数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2) 链接存储，结点间的逻辑关系

3、由附加指针字段表示。3) 索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4) 散列存储，按结点的关键字直接计算出存储地址。10. 评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间(辅助 存储空间)；易于理解、编码、调试。11. 算法的时间复杂度 T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为0(n)。时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n人2)、立方阶0(n3)、k次方阶0(门你)、指数阶0(2An)。13.算法的空间复杂度 S(n)：是该算法的

4、空间耗费，是求解问题规模n的函数。12. 算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。13. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。线性表1.线性表：是由n(n > 0)个数据元素组成的有限序列。3顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C; K i < n5顺序表上的基本运算public in terface List /返回线性表的大小，即数据元素的个数。public int getSize();/如果线性表为空返回true，

5、否则返回false 。public boolea n isEmpty();/判断线性表是否包含数据元素epublic boolea n contain s(Object e);/将数据元素e插入到线性表中i号位置 public void in sert(i nt i, Object e) throws OutOfB oun daryExcepti on;/删除线性表中序号为i的元素，并返回之 public Object remove(i nt i) throws OutOfB oun daryExcepti on;/删除线性表中第一个与e相同的元素public boolea n remove(

6、Object e);/返回线性表中序号为i的数据元素public Object get(i nt i) throws OutOfB oun daryExcepti on;在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)O(n)。在顺序表上删除要移动表的(n +1)/2结点，算法的平均时间复杂度为public class ListArray impleme nts List for (in t i=0; i<size; i+)private final int LEN = 8;/private Strategy strategy; /private int size; /

7、private Object eleme nts; /构造方法数组的默认大小数据元素比较策略线性表中数据元素的个数数据元素数组public ListArray (Strategy strategy)size = 0;eleme nts = new ObjectLEN;/返回线性表的大小，即数据元素的个数。public int getSize() return size;/如果线性表为空返回true，否则返回falsepublic boolea n isEmpty() retur n size=0;/判断线性表是否包含数据元素public boolea n contain s(Object e)

8、 if ( e = = eleme ntsi) retur n true;return false;/将数据元素e插入到线性表中i号位置public void in sert(i nt i, Object e) throws OutOfB oun daryExcepti on if (i<0|i>size)throw new OutOfBou ndaryExceptio n(”错误，指定的插入序号越界。");if (size >= eleme nts.le ngth)expa ndSpace();for (int j=size; j>i; j-)eleme n

9、tsj = eleme ntsj-1;eleme ntsi = e;size+;return;private void expa ndSpace()Object a = new Objectelements.length*2;for (in t i=0; i<eleme nts.le ngth; i+)ai = eleme ntsi;eleme nts = a;/删除线性表中序号为i的元素，并返回之public Object remove(i nt i) throws OutOfB oun daryExcepti on if (i<0|i>=size)throw new Ou

10、tOfBou ndaryExceptio n(”错误，指定的删除序号越界。");Object obj = eleme ntsi;for (int j=i; j<size-1; j+) eleme ntsj = eleme ntsj+1;eleme nts-size = n ull;return obj;/替换线性表中序号为i的数据元素为e，返回原数据元素public Object replace。nt i, Object e) throws OutOfB oun daryExcepti on if (i<0|i>=size)throw new OutOfBou nd

11、aryExceptio n(”错误，指定的序号越界。 ”)；Object obj = eleme ntsi;eleme ntsi = e;return obj;/返回线性表中序号为i的数据元素public Object get(i nt i) throws OutOfB oun daryExcepti on if (i<0|i>=size)throw new OutOfBou ndaryExceptio n(”错误，指定的序号越界。 ”)；return eleme ntsi;/删除线性表中第一个与e相同的元素public boolea n remove(Object e) int

12、i = in dexOf(e);if (i<0) retur n false;remove(i);return true;6. 单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。（1）建立单链表。时间复杂度为 O（n）。加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统(2 )查找运算。时间复杂度为 0(n)。public class SLNode impleme nts Node private Object eleme nt;private SLNode n ext;pu

13、blic SLNode(Object ele, SLNode next) this.eleme nt = ele;this .next = n ext;public SLNode getNext()return n ext;public void setNext(SLNode n ext)this .next = n ext; public Object getData() return eleme nt;public void setData(Object obj) eleme nt = obj;public class ListSL in ked impleme nts List priv

14、ate SLNode head; /单链表首结点引用private int size;/线性表中数据兀素的个数public ListSLi nked () head = new SLNode();size = 0;/辅助方法：获取数据兀素e所在结点的前驱结点private SLNode getPreNode(Object e)SLNode p = head;while (p.getNext()!=null)if (p.getNext().getData()=e)return p;else p = p.getNext();return n ull;II辅助方法：获取序号为0<=i<s

15、ize的元素所在结点的前驱结点private SLNode getPreNode(int i)SLNode p = head;for (; i>0; i-)p = p.getNext();return p;II获取序号为0<=i<size的元素所在结点private SLNode getNode(int i)SLNode p = head.getNext();for (; i>0; i-)p = p.getNext();return p;II返回线性表的大小，即数据元素的个数。public int getSize() return size;II如果线性表为空返回tru

16、e，否则返回false 。public boolea n isEmpty() retur n size=0;II判断线性表是否包含数据元素epublic boolea n contain s(Object e) SLNode p = head.getNext();while (p!=null)if (p.getData()=e) return true;else p = p.getNext(); return false;/将数据元素e插入到线性表中i号位置public void in sert(i nt i, Object e) throws OutOfB oun daryExcepti o

17、n if (i<0|i>size)throw new OutOfBou ndaryExceptio n(”错误，指定的插入序号越界。");SLNode p = getPreNode(i);SLNode q = new SLNode(e,p.getNext();p.setNext(q);size+;return;/删除线性表中序号为i的元素，并返回之public Object remove(i nt i) throws OutOfB oun daryExcepti on if (i<0|i>=size)throw new OutOfBou ndaryExcept

18、io n(”错误，指定的删除序号越界。");SLNode p = getPreNode(i);Object obj = p.getNext().getData();p.setNext(p.getNext().getNext();size-;return obj;/删除线性表中第一个与e相同的元素public boolea n remove(Object e) SLNode p = getPreNode(e);if (p!=null)p.setNext(p.getNext().getNext();size-;return true;return false;/替换线性表中序号为i的数据

19、元素为e，返回原数据元素public Object replace(i nt i, Object e) throws OutOfB oun daryExcepti on if (i<0|i>=size)throw new OutOfBou ndaryExceptio n(”错误，指定的序号越界。”)；SLNode p = getNode(i);Object obj = p.getData();p.setData(e);return obj;/返回线性表中序号为i的数据元素public Object get(i nt i) throws OutOfB oun daryExcepti

20、on if (i<0|i>=size)throw new OutOfBou ndaryExceptio n(”错误，指定的序号越界。”)；SLNode p = getNode(i);return p.getData();7. 循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表 的处理灵活方便。8. 空循环链表仅由一个自成循环的头结点表示。9. 很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方 便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是0(1),查找尾结点的时间是0(n);用尾指针表示

21、的单循环链表查找开始结点和尾结点的时间都是0(1)。10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。public class DLNode impleme nts Node private Object eleme nt;private DLNode pre;private DLNode n ext;public DLNode(Object ele, DLNode pre, DLNode n ext)this.eleme nt = ele;this.pre = pre;this .next = n ext;public DLNode ge

22、tNext()return n ext;public void setNext(DLNode n ext)this .next = n ext;public DLNode getPre()return pre;public void setPre(DLNode pre)this.pre = pre;public Object getData() return eleme nt;public void setData(Object obj) eleme nt = obj;public class Lin kedListDLNode impleme nts Lin kedList private

23、int size; /private DLNode head;/ private DLNode tail;/ public LinkedListDLNode() size = 0;head = new DLNode(); tail = new DLNode(); head.setNext(tail); tail.setPre(head);规模头结点，哑元结点尾结点，哑元结点构建只有头尾结点的链表/辅助方法，判断结点 p是否合法，如合法转换为DLNodeprotected DLNode checkPositi on(N ode p) throws In validNodeExcepti on i

24、f (p=n ull)throw new InvalidNodeException(" if (p=head)throw new InvalidNodeException(" if (p=tail)throw new InvalidNodeException("DLNode n ode = (DLNode)p;retur n no de;错误：p为空。”)；错误：p指向头节点，非法。");错误：p指向尾结点，非法。");/查询链接表当前的规模public int getSize() return size;/判断链接表是否为空 public b

25、oolea n isEmpty() return size=O;/返回第一个结点 public Node first() throws OutOfB oun daryExceptio nif (isEmpty()throw new OutOfBou ndaryExceptio n(”错误：链接表为空。”)；return head.getNext();/返回最后一结点public Node last() throws OutOfB oun daryExcepti onif (isEmpty()throw new OutOfBou ndaryExceptio n(”错误：链接表为空。”)；retu

26、rn tail.getPre();/返回p之后的结点public Node getNext(Node p)throws InvalidNodeException,OutOfBoundaryException DLNode node = checkPositi on( p);node = no de.getNext();if (no de=tail)throw new OutOfBou ndaryExceptio n(”错误：已经是链接表尾端。");retur n no de;/返回p之前的结点public Node getPre(Node p) throws In validNode

27、Excepti on, OutOfB oun daryExcepti on DLNode node = checkPositi on( p);node = no de.getPre();if (no de=head)throw new OutOfBou ndaryExceptio n(”错误：已经是链接表前端。");retur n node;/将e作为第一个元素插入链接表 public Node in sertFirst(Object e) DLNode n ode = new DLNode(e,head,head.getNext();head.getNext().setPre (n

28、o de);head.setNext (no de);size+;retur n no de;/将e作为最后一个元素插入列表,并返回e所在结点public Node in sertLast(Object e) DLNode node = new DLNode(e,tail.getPre(),tail);tail.getPre().setNext (n ode);tail.setPre (no de);size+;retur n no de;/删除给定位置处的元素，并返回之public Object remove(Node p) throws In validNodeExcepti on DLN

29、ode node = checkPositi on( p);Object obj = no de.getData();no de.getPre().setNext (no de.getNext();no de.getNext().setPre (no de.getPre();size-;return obj;/删除首元素，并返回之public Object removeFirst() throws OutOfBo un daryExcepti on retur n remove(head.getNext();/删除末元素，并返回之public Object removeLast() throw

30、s OutOfB oun daryExcepti onreturn remove(tail.getPre();/将处于给定位置的元素替换为新元素，并返回被替换的元素public Object replace(Node p, Object e) throws In validNodeExcepti on DLNode node = checkPositi on( p);Object obj = no de.getData();no de.setData(e);return obj;11. 顺序表和链表的比较1) 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存

31、储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。2) 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。12. 存储密度=(结点数据本身所占的存储量)/ (整个结点结构所占的存储总量)存储密度：顺序表 =1,链表1。第栈和队列LIFO表)。插1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表(入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。2. 栈的基本运算有：1) ini tstac

32、k(s),构造一个空栈;2) stackempty(s),判栈空；3) stackfull(s),判栈满；4) push(s,x),进栈；5) pop (s),退栈；6) stacktop(s)，取栈顶元素。3. 顺序栈：栈的顺序存储结构称顺序栈。4. 当栈满时，做进栈运算必定产生空间溢出， 称“上溢”。 当栈空时，做退栈运算必定产 生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。5. 在顺序栈上的基本运算：public interface Stack / 返回堆栈的大小public int getSize();/ 判断堆栈是否为空public boolean

33、isEmpty();/ 数据元素 e 入栈public void push(Object e);/ 栈顶元素出栈public Object pop() throws StackEmptyException;/ 取栈顶元素public Object peek() throws StackEmptyException;public class StackArray implements Stack private final int LEN = 8; / 数组的默认大小private Object elements; / 数据元素数组private int top;/ 栈顶指针public Sta

34、ckArray() top = -1;elements = new ObjectLEN;/ 返回堆栈的大小public int getSize() return top+1;/ 判断堆栈是否为空public boolean isEmpty() return top<0;/ 数据元素 e 入栈public void push(Object e) if (getSize()>=elements.length) expandSpace();elements+top = e;private void expandSpace()Object a = new Objectelements.le

35、ngth*2;for (int i=0; i<elements.length; i+)ai = elementsi;elements = a;/ 栈顶元素出栈public Object pop() throws StackEmptyException if (getSize()<1)throw new StackEmptyException(" 错误，堆栈为空。 ");Object obj = elementstop;elementstop- = null;return obj;/ 取栈顶元素public Object peek() throws StackEm

36、ptyException if (getSize()<1)throw new StackEmptyException(" 错误，堆栈为空。 ");return elementstop;6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。7. 链栈上的基本运算： public class StackSLinked implements Stack private SLNode top; /链表首结点引用private int size;/ 栈的大小public StackSLinked() top = null;size = 0;/ 返回堆栈的大小public

37、int getSize() return size;/ 判断堆栈是否为空public boolean isEmpty() return size=0;/ 数据元素 e 入栈public void push(Object e) SLNode q = new SLNode(e,top);top = q;size+;/ 栈顶元素出栈public Object pop() throws StackEmptyException if (size<1)throw new StackEmptyException(" 错误，堆栈为空。 ");Object obj = top.getD

38、ata();top = top.getNext();size-;return obj;/ 取栈顶元素public Object peek() throws StackEmptyException if (size<1)throw new StackEmptyException(" 错误，堆栈为空。 ");return top.getData();8. 队列是一种运算受限的线性表， 允许删除的一端称队首， 允许插入的一端称队尾。 队列又 称为先进先出线性表， FIFO 表。9. 队列的基本运算：1) initqueue(q), 置空队；2) queueempty(q),

39、 判队空；3) queuefull(q), 判队满；4) enqueue(q,x), 入队；5) dequeue(q), 出队；6) queuefront(q), 返回队头元素。10. 顺序队列： 队列的顺序存储结构称顺序队列。 设置 front 和 rear 指针表示队头和队尾元 素在向量空间的位置。11. 顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元 素的空间无法利用，队尾指针超过向量空间的上界而不能入队。12. 为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称 循环队列。 i=(i+1)%queuesize13. 循环队列的边界

40、条件处理：由于无法用front=rear 来判断队列的“空”和“满”。解决的方法有：1) 另设一个布尔变量以区别队列的空和满；2) 少用一个元素，在入队前测试 rear 在循环意义下加 1 是否等于 front ；3) 使用一个记数器记录元素总数。14. 循环队列的基本运算：public interface Queue / 返回队列的大小public int getSize();/ 判断队列是否为空public boolean isEmpty();/ 数据元素 e 入队public void enqueue(Object e);/ 队首元素出队public Object dequeue() t

41、hrows QueueEmptyException;/ 取队首元素public Object peek() throws QueueEmptyException;public class QueueArray implements Queue private static final int CAP = 7;/队列默认大小private Object elements; / 数据元素数组private int capacity; / 数组的大小 elements.lengthprivate int front; / 队首指针 , 指向队首private int rear; / 队尾指针 , 指

42、向队尾后一个位置 public QueueArray() this(CAP);public QueueArray(int cap)capacity = cap + 1;elements = new Objectcapacity;front = rear = 0;/ 返回队列的大小public int getSize() return (rear -front+ capacity)%capacity;public boolean isEmpty() / 判断队列是否为空return front=rear;/ 数据元素 e 入队public void enqueue(Object e) if (g

43、etSize()=capacity-1) expandSpace();elementsrear = e;rear = (rear+1)%capacity;private void expandSpace()Object a = new Objectelements.length*2;int i = front;int j = 0;while (i!=rear)/ 将从 front 开始到 rear 前一个存储单元的元素复制到新数组aj+ = elementsi;i = (i+1)%capacity;elements = a;capacity = elements.length;front =

44、0;rear = j; / 设置新的队首、队尾指针public Object dequeue() throws QueueEmptyException if (isEmpty()throw new QueueEmptyException(" 错误：队列为空 "); Object obj = elementsfront; elementsfront = null;front = (front+1)%capacity;return obj;/ 取队首元素public Object peek() throws QueueEmptyException if (isEmpty()th

45、row new QueueEmptyException(" 错误：队列为空 ");return elementsfront;15. 链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16. 链队列的基本运算：public class QueueSLinked implements Queue private SLNode front;private SLNode rear;private int size;public QueueSLinked() front = new SLNode();rear = front;size = 0;/ 返回队列的

46、大小public int getSize() return size;/ 判断队列是否为空public boolean isEmpty() return size=0;/ 数据元素 e 入队public void enqueue(Object e) SLNode p = new SLNode(e,null);rear.setNext(p);rear = p;size+;/ 队首元素出队public Object dequeue() throws QueueEmptyException if (size<1)throw new QueueEmptyException(" 错误：队

47、列为空 ");SLNode p = front.getNext();front.setNext(p.getNext();size-;if (size<1) rear = front; /如果队列为空 ,rear 指向头结点return p.getData();/ 取队首元素public Object peek() throws QueueEmptyException if (size<1)throw new QueueEmptyException(" 错误：队列为空 ");return front.getNext().getData();第 四 章 串

48、1. 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2. 空串：长度为零的串称空串； 空白串：由一个或多个空格组成的串称空白串； 子串：串中任意个连续字符组成的子序列称该串的子串；主串： 包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3. 空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变；4. 串的基本运算1) int strlen(char2) char *strcpy(char3) char *strcat(char4) int strcmp(char5) char *strchr(char

49、*s); 求串长。* to,char* from); 串复制。* to,char* from); 串联接。*s1,char *s2); 串比较。*s,char c); 字符定位。5. 串的存储结构：(1) 串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：1) 静态存储分配的顺序串： 直接用定长的字符数组定义，以“0”表示串值终结。#define maxstrsize 256typedef char seqstringmaxstrsize; seqstring s;不设终结符，用串长表示。Typedef structChar chmaxstrsize;Int length;seqst

50、ring; 以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2) 动态存储分配的顺序串：简单定义： typedefchar* string;复杂定义： typedefstructchar *ch;int length;hstring;(2) 串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义： typedef struct nodechar data;struct node *next;linkstrnode;typedef linkstrnode *linkstring; linkstring s;将结点数据域存放的字符个数定义为结点的大小。结点大小不为

51、1 的链串类型定义： #definenodesize80typedef struct nodechar datanodesize;struct node * next;linkstrnode;6. 串运算的实现 (1)顺序串上的子串定位运算。1)子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。2)朴素的串匹配算法。时间复杂度为0(nA2)。比较的字符总次数为(n-m+1) mInt naivestrmatch(seqstring t,seqstring p)int i,j,k;int m=p.length;int n=t.length; for(i=0;i<=n-m;i

52、+)j=0;k=i;while(j<m&&t.chk=p.chj)j+;k+; if(j=m)return i;return 1;(2)链串上的子串定位运算。时间复杂度为0(nA2) 。比较的字符总次数为( n-m+1) m。Linkstrnode * lilnkstrmatch(linkstringT, linkstring P)linkstrnode *shift, *t,*p;shift=T;t=shift;p=P;while(t&&p)if(t->data=p->data)t=t->next; p=p->next;elses

53、hift=shift->next;t=shift;p=P;if(p=NULL)return shift;elsereturn NULL;第 五 章 多 维 数 组 和 广 义 表1. 多维数组：一般用顺序存储的方式表示数组。2. 常用方式有： 1)行优先顺序，将数组元素按行向量排列；2)列优先顺序，将数组元素按列向量排列。3. 计算地址的函数： LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d4. 矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。( 1) 对称矩阵：在一个 n 阶的方阵 A 中，元素满足 Aij=Aji 0&

54、lt;=i,j<=n-1; 称为对称矩 阵。元素的总数为： n(n+1)/2;设： I=i 或 j 中大的一个数； J=i 或 j 中小的一个数；则： k=I*(I+1)/2+J;地址计算： LOC(Aij)=LOC(sak)=LOC(sa0)+k*d= LOC(sa0)+ (I*(I+1)/2+J )*d(2)三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素 均为常数C；下三角的主对角线上元素均为常数C。元素总数为： (n(n+1)/2)+1; 以行优先顺序存放的 Aij 与 SAk 的关系： 上三角阵： k=i*(2n-i+1)/2+j-i;下三角阵： k=i*(i+1)/2+j;(3) 对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为 零。 |i-j|>(k-1)/2以行优先顺序存放的 Aij 与 SAk 的关系： k=2i+j;5.