数据结构与算法第二章清华大学出版社赵玉兰VIP

第2章基本数据结构2.1线性表2.2数组2.3字符串数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第1页!2.1线性表——ADT线性表线性表（LinearList）例126个大写英文字母组成的字母表（A，B，C，…，Z）例2某个学生宿舍学生姓名（“wan”，“li”，“zhao”，“ye”，“hao”，“jia”）例3学生信息情况登记表姓名学号性别年龄班级家庭住址陈燕060001女21计06内蒙古刘伟060002男21计06北京王树林060003男22计06山东………………数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第2页!2.1线性表——ADT线性表定义由n(n0)个性质相同的数据元素a1,a2,…,an

组成的有限序列数据元素的个数n(n0)定义为表的长度，当n=0时称为空表常常将非空的线性表（n>0）记作：

L=(a1,a2,…,ai,…,an)注意：这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第3页!2.1线性表——ADT线性表线性表的逻辑特征有限性：线性表中数据元素的个数是有穷的相同性：线性表中数据元素的类型是同一的顺序性有且仅有一个开始结点a1，它没有前趋，而仅有一个后继a2

有且仅有一个终端结点an，它没有后继，而仅有一个前趋an-1其余的内部结点ai(2in-1)都有且仅有一个前趋ai-1

和一个后继ai+1

线性表的逻辑结构是一种典型的线性结构数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第4页!2.1线性表——ADT线性表LengthProcess：求线性表中元素个数

Output：返回线性表中元素个数GetElemInput：要取出的元素的位置

Process：取出指定位置上的元素

Output：返回取出的元素值LocateInput：要定位的元素

Process：为指定元素定位

Output：若线性表中有给定元素，返回元素位置，否则返回-1数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第5页!2.1线性表——ADT线性表例4假设利用线性表LA和LB分别表示两个集合A和B（线性表中的数据元素即为集合中的成员），现求一个新的集合A∩B，并用LA表示结果集合。voidIntersection(ListLA,ListLB){inti=1;while(i<=

LA.size){x=LA.GetElem(i);//在LA中取一元素

k=LB.Locate(x);//在LB中搜索它

if(k==-1){//在LB中未找到，则在LA中删除它LA.Delete(i);LA.size--;}elsei++;}}//Intersection数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第6页!2.1线性表——线性表的顺序存储顺序表定义顺序存储的线性表把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里存储要点用一段地址连续的存储单元依次存储线性表中的数据元素a1a2…ai-1ai…an数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第7页!2.1线性表——线性表的顺序存储存储结构与逻辑结构的关系存储地址内存状态线性表中的位序LOC(a1)a11LOC(a1)+ma22…LOC(a1)+(i-1)maii…LOC(a1)+(n-1)mann空闲

顺序表存储结构示意图LOC(ai)=LOC(a1)+(i-1)×m基地址LOC(ai)=LOC(ai-1)+m一个数据元素所占存储量顺序表是一种随机存取的存储结构数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第8页!2.1线性表——线性表的顺序存储constintMaxListSize=100;classSeqList{DataTypedata[MaxListSize];intsize;//元素的个数

public:List(){size=0;}//构造一个空线性表

voidClear();//清空顺序表boolIsEmpty();//判断如果为空表，返回true，否则返回falseDataTypeGetElem(intk){returndata[k-1];}//返回第k个元素intLocate(DataTypee);//返回个与元素e匹配的元素位序DataTypePrior(DataTypee);//返回元素e的前驱DataTypeNext(DataTypee);//返回元素e的后继voidInsert(DataTypee,inti);//在表中第i个位置插入eDataTypeDelete(inti);//删除第i个元素，并返回其值}；//SeqList数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第9页!2.1线性表——线性表的顺序存储定位成功定位不成功e＝48e＝50数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第10页!2.1线性表——线性表的顺序存储在i=4处插入下标数据元素012

113

221

324

4

5

6

7

82528304277插入在顺序表中的第i个位置上插入eai和ai+1之间的逻辑关系发生了变化存储位置要反映这个变化数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第11页!2.1线性表——线性表的顺序存储插入算法的时间复杂度基本语句：移动元素最好情况：不移动（i=n），时间复杂度为O(1)最坏情况：移动n个元素（i=0），时间复杂度为O(n)平均情况：设插入每个数据元素的概率相等，则数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第12页!2.1线性表——线性表的顺序存储删除i=4处元素下标数据元素012

113

221

324

4

5

6

7

828304277数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第13页!2.1线性表——线性表的顺序存储顺序表的优点无需为表示数据元素之间的逻辑关系而增加额外存储空间。可方便地随机存取表中任一位置的元素。顺序表的缺点预先为数据元素分配空间。插入和删除时必须移动大量元素。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第14页!2.1线性表——线性表的链式存储单链表例6线性表（北京、天津、上海、宁夏、台湾）L北京天津

上海

宁夏

台湾

Ù

…………100上海140…………110天津100头指针…………126126北京110…………140宁夏230…………230台湾Null…………数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第15页!2.1线性表——线性表的链式存储为了操作（插入和删除）方便，增设一个头结点headhead

非空表 空表注意区分a1anheada2头指针头结点首结点表结点数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第16页!2.1线性表——线性表的链式存储voidCreate(intn);//创建长度为n的单链表

DataTypeGetElem(inti);//返回第i个元素值

Node*Locate(DataTypee);//返回个与e匹配的元素结点指针

boolIsEmpty(){return(head->next==NULL);}//判断是否为空链表DataTypePrior(DataTypee);//返回e的前驱结点元素DataTypeNext(DataTypee);//返回e的后继结点元素voidInsert(DataTypex,inti);//在第i个结点之前插入元素值为x的结点DatatypeDelete(inti);//删除第i个结点，并返回其元素值voidClear();//清空链表};//nextList数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第17页!2.1线性表——线性表的链式存储插入操作将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1

与ai

之间插入过程：1）定位；2）插入。pai-1headaixa1newnode

newnode→next=p→next; p→next=newnode;数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第18页!2.1线性表——线性表的链式存储删除操作将表的第i个结点，即ai

删去删除过程：1）定位；2）删除。pai-1headaia1ai+1q

q=p→next;p→next=q→next;deleteq;数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第19页!2.1线性表——线性表的链式存储建立单链表头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第20页!2.1线性表——线性表的链式存储尾插法建表该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。（1）创建头结点head，使尾结点r为NULL；（2）新建结点p，如果head->next=NULL，则head->next=p；r=p；（3）否则，r->next=p；r=p；重复（2），（3）

（4）如果r!=NULL；则r->next=NULL数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第21页!2.1线性表——线性表的链式存储双向链表（Doublenextedlist）每个结点中有两个指针域指向其直接前趋结点指向其直接后继结点每个结点结构数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第22页!2.1线性表——线性表的链式存储带头结点的双向链表类的定义classDNode{DataTypedata;DNode*prior;//指向前驱的指针

DNode*next;//指向后继的指针public:DNode(DataTyped=nulldata){data=d;prior=next=NULL;}friendclassDBList;};//DNode数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第23页!2.1线性表——线性表的链式存储定位定位成功head定位不成功head数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第24页!2.1线性表——线性表的链式存储删除操作（删除结点p）p->next->prior=p->prior;

aiai+1ai-1pp->prior->next=p->next;deletep;数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第25页!2.1线性表——线性表的链式存储循环链表是线性链表的变形表尾结点的next

指针不为NULL，而是指向了链表的头结点特点从表中任一结点出发，均可访问表中其他任一结点headhead数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第26页!2.1线性表——线性表的链式存储单链表的应用：一元多项式求和一元多项式在计算机中，可以用一个线性表来表示

P=(p0,p1,…,pn)但是对于下述多项式，该表示方法并不合适

P(x)=1+3x10000–2x20000数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第27页!2.1线性表——线性表的链式存储一元多项式的结构说明classTermType{//项的定义

floatcoef;intexpn;};classPNode{//结点的定义

TermTypeterm;PNode*next;public:PNode(floatc=0,inte=0){term.coef=c;term.expn=e;next=NULL;}}friendclassPolynList;};//PNode算法数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第28页!2.1线性表——线性表的链式存储求和过程演示A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8+10x20A(x)=A(x)+B(x)=7+11x+22x7+5x17+10x20hapa3170517^98hb227811020^-98pb11pa=NULL停止数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第29页!2.1线性表——线性表的链式存储例2非递减有序线性表的归并已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。如LA=（3,5,8,11）LB=（2,6,8,9,11,15,20）则LC=（2,3,5,6,8,8,9,11,11,15,20)数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第30页!2.1线性表——线性表的链式存储例3约瑟夫环问题n(n>0)个人围成一个圆圈，从第1个人开始顺时针报数，报到第m个人，令其出列。然后再从其下一个人开始重新报数，报到第m个人再令其出列，…，如此下去,直到圆圈中只剩一个人为止。例n=8m=3数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第31页!2.1线性表——顺序表和链表的比较根据应用选择顺序表和链表顺序表结点总数目大概可以估计表中结点比较稳定（插入、删除操作少）链表结点数目无法预知线性表中结点动态变化（插入、删除操作多）数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第32页!2.2数组——数组一维数组只有一个下标的数组特点连续存储（别名向量）除个元素外，其它每一个元素有且仅有一个直接前驱除最后一个元素外，其它每一个元素有且仅有一个直接后继数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第33页!2.2数组——数组二维数组A[n][m]

每个数据元素都有两个下标行下标列下标二维数组是一个数据元素值为一维数组的一维数组n=4m=6mn数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第34页!2.2数组——数组存储有次序问题约定的次序不同，则计算元素地址的公式也有所不同C和PASCAL中采用行优先顺序；FORTRAN中采用列优先顺序数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第35页!2.2数组——数组

以列序为主序

a00a01……..a0m-1

a10a11……..a1m-1

an-10an-11…an-1m-1

….

an-1m-1

……

a1m-1

a0m-1

……

an-11

……

a11

a01

an-10

……

a10

a00n*m-1(m-1)*n1*nn-1…10以列序为主序存储的地址公式为：LOC(aij)=LOC(a00)+(jn+i)l数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第36页!2.2数组——特殊矩阵矩阵在科学与工程计算问题中，矩阵是一种常用的数学对象在高级语言编制程序时，将一个矩阵描述为一个二维数组特殊矩阵具有许多相同值的元素或者零元素，并且这些元素在矩阵中的分步有一定规律的矩阵。压缩存储为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第37页!2.2数组——特殊矩阵在下三角（包括对角线）中，元素总数为：将这些元素存放在一维数组M[0..n(n+1)/2-1]中a00a10a11a20…an-1,0…an-1,n-1k=0123…n(n-1)/2…n(n+1)/2-1M[k]和矩阵中的元素aij之间存在着一一对应关系数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第38页!2.2数组——特殊矩阵可以用数组M[0..n(n+1)/2]存储，其中常量c存入最后一个单元下三角矩阵的元素aij

和M[k]之间的对应关系上三角矩阵中的元素aij

和M[k]之间的对应关系数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第39页!2.2数组——稀疏矩阵定义设矩阵A

中有s个非零元素，若s远远小于矩阵元素的总数（即s≦n×m），则称A为稀疏矩阵。行数n

=6，列数

m=7，非零元素个数t=8

数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第40页!2.2数组——稀疏矩阵classSPMatrix{//三元组表类

intrn,cn,en;//矩阵的行、列及非零元素的个数

SPNodedata[SMax];//三元组表

public:SPMatrix();SPMatrix(intm,intn,ints);//构造m行n列，元素个数为s的稀疏矩阵

SPMatrixTranspose();//求转置矩阵

SPMatrixAdd(SPMatrix&);//求矩阵的和

SPMatrixMultiply(SPMatrix&);//求矩阵的乘积

};//SPMatrix数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第41页!2.2数组——稀疏矩阵稀疏矩阵的转置转置

其时间复杂度为：

O(nm)用常规的二维数组表示时的转置算法for(i=0;i<n;i++)for(j=0;j<m;j++)T[j][i]=M[i][j];矩阵T（53）矩阵M（35）数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第42页!2.2数组——稀疏矩阵问题：若采用三元组顺序表存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？思路总行数rn和总列数cn互换；每个元素的行下标i和列下标j互换；按以行为主序的结构重新排列三元组内元素的顺序。上述（1）和（2）容易实现，难点在（3）。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第43页!2.2数组——稀疏矩阵SPMatrixTranspose(){SPMatrixT;T.rn=cn;T.cn=rn;T.en=en;if(en){q=0;for(col=0;col<cn;++col)for(p=0;p<en;++p)if(data[p].j==col){T.data[q].i=data[p].j;T.data[q].j=data[p].i;T.data[q].v=data[p].v;++q;}}returnT;}//Transpose数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第44页!2.2数组——稀疏矩阵时间复杂度分析主要时间消耗在查找data[p].j==col上，由两重循环完成：

for(col=0;col<cn;++col)循环次数＝cnfor(p=0;p<en;++p)

循环次数＝en

所以该算法的时间复杂度为O(cn×en)

----即稀疏矩阵的列数与非零元素个数的乘积。最恶劣情况：稀疏矩阵中全是非零元素，此时en=rn×cn，时间复杂度为

O(rn×cn2)

。

若M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是O(rn×cn

)

。结论：该算法仅适用于非零元素个数很少的情况。

数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第45页!2.2数组——稀疏矩阵设计思路如果能预知M矩阵每一列（即T的每一行）的非零元素个数，又能预知每一列个非零元素在T.data中的位置，则扫描M时便可以将每个元素准确定位。稀疏矩阵M中的列变量用col表示令num[col]：存放M中第col列中非零元素个数

cpot[col]：存放M中第col列的第一个非零元素在的T.data中的正确位置数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第46页!35186425

6

8

02-3051510121418209232435-74214ijvT76543210col01234num22211cpot02467p

6

5

8011202920-3241432244118501553-7ijvM76543210数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第47页!2.2数组——稀疏矩阵

cpot[0]=0;//求原矩阵中每一列个元素在转置矩阵中的位置

for(i=1;i<cn;i++)cpot[i]=cpot[i-1]+num[i-1];for(i=0;i<en;i++){//扫描原矩阵三元表进行转置j=data[i].j;k=cpot[j];//取到当前三元组在转置矩阵三元组表中的位置

T.data[k].i=data[i].j;T.data[k].j=data[i].i;T.data[k].v=data[i].v;cpot[j]++;}//fori}//ifreturnT;}//FastTranspose数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第48页!2.2数组——稀疏矩阵转置算法小结传统转置：O(rn×cn)采用压缩存储转置：O(cn×en)快速转置：O(cn＋en)

——牺牲空间效率换时间效率数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第49页!2.3字符串（String）串长：字符串中的字符个数（n≥0）。n=0时称为空串。空白串：由一个或多个空格符组成的串。子串：串S中任意个连续的字符序列叫S的子串；S叫主串。子串位置：子串的第0个字符在主串中的位置。字符位置：字符在串中的序号。串相等：串长度相等，且对应位置上字符相等。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第50页!2.3字符串（String）串的抽象数据类型定义ADTString{Data：零个或多个字符组成的字符序列OperationConstructorProcess：构造空串AssignInput：被复制的字符串

Process：串赋值

Output：复制成功，返回true；否则，返回false

数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第51页!2.3字符串（String）SubStringInput：子串的位置和长度Process：求子串Output：返回子串

IndexInput：子串以及开始匹配的位置Process：子串匹配Output：返回子串在开始位置之后的匹配位置ReplaceInput：子串T和子串VProcess：用子串V替换子串T}//Sting数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第52页!2.3字符串（String）char*strchr(char*str1,charch)再字符串str1中搜索字符ch并返回指向ch的指针intstrcspn(char*str1,charch)在字符串str1中搜索ch并返回其在str1中次出现的位置（从0开始计数）char*strpbrk(constchar*str1,constchar*str2)在字符串str1和str2中搜索首次共同出现的字符，返回该字符在str1中的地址char*strstr(constchar*str1,constchar*str2)在字符串str1中搜索和str2匹配的子字符串，返回该字符串个字符在str1中的地址数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第53页!2.3字符串（String）字符串的模式匹配（PatternMatching）在串T中查找与串pat相等的子串，并确定其次出现的位置，即如何实现Index(pat)函数。示例：目标

T＝’Beijing’，模式pat＝’jin’

匹配结果=3注：T称为目标，pat称为模式。若T中包含pat，则称“匹配成功”（返回位置）；否则称“匹配不成功”（返回-1）。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第54页!2.3字符串（String）穷举的模式匹配过程目标Tacabaabaabcabaabc第1趟模式patabaabcab第6趟patabaabcab第2趟patabaabcab第3趟patabaabcab第4趟patabaabcab第5趟patabaabcab×××××数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第55页!书面作业P552-1，2-4，2-5，2-10实验题实验1数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第56页!2.1线性表——ADT线性表抽象数据类型线性表的定义

ADTList{

Data

数据元素表size：数据元素的个数

OperationConstructorProcess：创建空表ClearProcess：清空线性表

IsEmptyProcess：判断线性表是否为空

Output：若线性表为空，返回true，否则返回false数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第57页!2.1线性表——ADT线性表InsertInput：被插入元素值及其位置Process：将给定元素插入指定位置Delete

Input：被删除元素的位置

Process：若线性表中有给定元素，则删除它PriorInput：要求前驱的元素

Process：求给定元素的直接前驱NextInput：要求后继的元素

Process：求给定元素的直接后继}//List数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第58页!2.1线性表——ADT线性表例5假设利用线性表LA和LB分别表示两个集合A和B（线性表中的数据元素即为集合中的成员），现求一个新的集合A∪B，并用LA表示结果集合。voidUnion(ListLA,ListLB){intn;for(inti=1;i<=LB.size;i++){x=LB.GetElem(i);//在LB中取一元素

k=LA.Locate(x);//在LA中搜索它

if(k==-1){//在LA中未找到，则在LA中插入它n=LA.size;LA.Insert(n,i);LA.size++;}}}//Intersection数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第59页!2.1线性表——线性表的顺序存储例：（34,23,67,82）34236782存储空间的起始地址——基地址用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度

4数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第60页!2.1线性表——线性表的顺序存储注意线性表的第i个元素ai

存储在数组下标为

i-1

的位置线性表的长度size与数组的长度MaxListSize是不同的size=n，大小可变MaxListSize是数组的长度，大小不变sizeMaxListSize表的长度空闲an…aiai-1…a2a1datan-1MaxListSize-1sizeMaxListSizei-1i-210下标如何实现顺序表的内存分配？顺序表一维数组数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第61页!2.1线性表——线性表的顺序存储基本操作在顺序表中的实现定位操作算法2.4定位intLocate(DataTypee){inti=0;while(i<size&&data[i]!=e)i++; if(i>=size)return-1; //没有找到

elsereturni; //找到此元素，返回其下标}//Locate注意序号和下标之间的关系！数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第62页!2.1线性表——线性表的顺序存储定位算法的时间复杂度基本操作：比较成功时最好情况：比较1次（i=0），时间复杂度为O(1)最坏情况：比较n次（i=n-1），时间复杂度为O(n)平均情况：设定位每个数据元素的概率相等，则不成功时：比较n次数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第63页!2.1线性表——线性表的顺序存储算法2.2插入voidInsert(DataTypee,inti){if(i<0||i>size||size==MaxListSize-1)exit;else{for(j=size;j>i;j--)data[j]=data[j-1]; data[i]=e;//插入成功size++;

}}//Insert什么时候不能插入？注意边界条件数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第64页!2.1线性表——线性表的顺序存储删除删除顺序表中第i个位置上的元素DataTypeDelete(inti){if(i<0||i>=size)returnnulldata;//被删除的元素下标错

else{size--;e=data[i]; for(intj=i;j<size;j++)data[j]=data[j+1];returne; } }//Delete数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第65页!2.1线性表——线性表的顺序存储删除算法的时间复杂度基本语句：移动元素最好情况：不移动（i=size-1），时间复杂度为O(1)最坏情况：移动n个元素（i=0），数据复杂度为O(n)平均情况：设删除每个数据元素的概率相等，则数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第66页!2.1线性表——线性表的链式存储链表线性表的链式存储结构逻辑上相邻的元素在物理位置上可能不相邻结点可以不连续存储表可扩充分为单链表双向链表循环链表数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第67页!2.1线性表——线性表的链式存储每个元素（表项）由结点（Node）构成每个结点只有一个指针域且最后一个结点的指针域为空整个单链表可由头指针唯一确定数据域指针域datanexta1a2an头指针空指针数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第68页!2.1线性表——线性表的链式存储单链表的存储结构的类定义

classNode{ DataTypedata; Node*next; public: Node(){next=NULL;} friendclassnextList; };//Node classLinkList{Node*head;intsize;public:LinkList(){head=newNode();size=0;}数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第69页!2.1线性表——线性表的链式存储取元素DataTypeGetElem(inti){ if(head->next==NULL)//空链表，返回空值

returnnulldata; else{

p=head;k=0;while(p&&k<i){p=p->next;k++;}if(!p||k==0)returnnulldata;//i超出链表元素的范围

elsereturnp->data; }}//GetElem数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第70页!2.1线性表——线性表的链式存储voidInsert(DataTypex,inti){//在第i个结点位置上插入元素值为x的结点

Node*p=head;intk=0;if(i<1||i>size)returnnulldata;//插入位置错误

while(p&&k<i-1){p=p->next;k++;}//找到插入位置

if(!p)exit;

Node*newnode=newNode();newnode->data=x;newnode->next=p->next;p->next=newnode;

size++;}//Insert数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第71页!2.1线性表——线性表的链式存储DataTypeDelete(inti){//删除第i个结点

Node*p=head;intk=0;if(i<1||i>size)//结点序号i超出链表结点范围，返回空值

returnnulldata;

while(p&&k<i-1)//找到被删除结点的前一个元素

{p=p->next;k++;}

if(p==NULL){cout<<“InvalidpositionforDeletion!\n”;returnnulldata;}

q=p->next;

p->next=q->next;e=q->data;deleteq;size--;returne;}//Delete数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第72页!2.1线性表——线性表的链式存储头插法建表voidCreate(intn){

head=newNode();//创建头结点

head->next=NULL;for(i=n;i>0;i--){p=newNode();if(p==NULL)exit;cin>>p->data;p->next=head->next;head->next=p;}size=n;}数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第73页!2.1线性表——线性表的链式存储尾插法建表voidCreate(intn){

head=newNode();

head->next=NULL;r=head;for(i=n;i>0;i--){p=newNode();if(p==NULL)exit;cin>>p->data;r–>next=p;r=p;}size=n;}数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第74页!2.1线性表——线性表的链式存储带头结点的双向链表heada1a2an^^……head^^结点指针的指向p==p->prior->next==p->next->prior空表非空表p->priorp->nextp数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第75页!2.1线性表——线性表的链式存储classDBList{DNode*head;intsize;public:DBList(){head=newDNode();size=0;}//构造函数，创建空链表

voidCreate(intn);//创建长度为n的双链表

DataTypeGetElem(inti);//取得第i个元素Dnode*Locate(DataTypee);//返回个与e匹配的结点指针boolIsEmpty();//判断是否为空链表voidInsert(DataTypee,inti);//在第i个结点前插入值为e的结点DataTypeDelete(inti);//删除第i个结点，并返回其元素值voidClear();//清空链表};//DBList数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第76页!2.1线性表——线性表的链式存储插入操作（在结点p

之前插入结点s）s->prior=p->prior; p->prior->next=s;s->next=p;p->prior=s;考虑：哪些语句可以交换位置？哪些不能交换？esabps=newDNode(e); 数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第77页!2.1线性表——线性表的链式存储注意与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针。数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第78页!2.1线性表——线性表的链式存储循环链表基本操作的实现基本操作与单链表类似在循环链表中遍历的终止条件是什么？

终止

p->next==NULL;或p==NULL;

终止应该是p->next==

head;

或

p==

head;

开始

p=head->next;或p=head;

数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第79页!2.1线性表——线性表的链式存储一般情况下，一元稀疏多项式可写成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指数为ei

项的非零系数，

0≤e1<e2<…<em=n可以下列线性表表示

((p1

,e1

),(p2

,e2),┄,(pm,em))例如

P999(x)=7x3-2x12-8x999可表示为

((7,3),(-2,12),(-8,999))数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第80页!2.1线性表——线性表的链式存储classPolynList{//多项式链表定义

PNode*head;intlen;public:PolynList();//构造空的多项式链表

voidCreate(intm);//创建m项多项式

voidAddPolyn(PolynList&);//多项式相加

voidPrintPolyn();//显示多项式

voidSubreactPolyn(PolynList&);//多项式相减

voidMultiplyPolyn(PolynList&);//多项式相乘};//PolynList数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第81页!2.1线性表——线性表的链式存储算法voidAddPolyn(polynList&ah,polynList&bh){pc=ah;pa=ah.head;pb=bh.head;while(pa&&pb){a=pa->term.expn;b=pb->term.expn;//指数

if(a<b){//多项式ah中当前结点的指数值小

pc->next=pa;pc=pa;pa=pa->next;//pa指针后移}elseif(a>b){//多项式bh中当前结点的指数值小

pc->next=pb;pc=pb;pb=pb->next;//pb指针后移

}elseif(pa.coef+pb.coef<0.0001){//两者的指数值相等且系数之和为0，删除两个结点

p=pa;pa=pa->next;deletep;p=pb;pb=pb->next;deletep;}else{//将pb结点的系数加入pa结点

pa->coef=pa.coef+pb.coef;pc->next=pa;pc=pa;pa=pa->next;p=pb;pb=pb->next;deletep;}}//whileif(pa)pc->next=pa;elsepc->next=pb;returnah;}数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第82页!2.1线性表——线性表的链式存储归并算法voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La.head->next;pb=Lb.head->next;Lc=La;pc=Lc.head;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;deleteLb.head;}//endMergeList数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第83页!2.1线性表——顺序表和链表的比较顺序表没有附加存储空间开销随机取得任一元素预先申请固定长度的数组插入、删除需要移动元素，运算时间代价O(n)链表插入、删除运算时间代价O(1)，但找第

i

个元素个元素时间代价O(n)在运行时动态为表中新的元素分配存储空间顺序取得某一元素每个元素都有附加存储空间开销数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第84页!2.2数组——数组数组的定义是由一组具有相同类型的数据元素构成的有限序列，且存储在一块地址连续的内存单元中数据元素可以是简单类型，也可以是构造类型数据元素在数组中的相对位置由其下标确定数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第85页!2.2数组——数组存储数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第86页!2.2数组——数组二维数组中的元素

aij可以看成属于两个向量：即第i

行的向量Ai

和第j

列的向量Bja00没有前驱结点，称之为开始结点；

an-1,m-1没有后继结点，称之为终端结点aij（1i

n-2,1j

m-2）有两个前驱结点ai,j-1,ai-1,j

两个后继结点ai,j+1,ai+1,j第0行的元素a0j(j=1,…,m-1)只有一个前驱a0,j-1

第0列的元素ai0(i=1,…,n-1)只有一个前驱ai-1,0

第n-1行的元素an-1,j(j=0,…,m-2)只有一个后继an-1,j+1

第m-1列的元素ai,m-1(i=0,…,n-2)只有一个后继ai+1,m-1数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第87页!2.2数组——数组

a00a01……..a0m-1

a10a11……..a1m-1

an-10an-11…an-1m-1

….

以行序为主序

an-1m-1

……

an-11

an-10

……

a1m-1……

a11

a10

a0m-1

……

a01

a00n*m-1(n-1)*m1*mm-1…10以行序为主序存储的地址公式为：LOC(aij

)=LOC(a00)+(im+j

)l数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第88页!2.2数组——数组n维数组各维元素个数为b1,b2,b3,…,bn下标为（j1,j2,j3,…,jn）的数组元素的存储地址数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第89页!2.2数组——特殊矩阵对称矩阵的压缩存储若一个n

阶方阵A中的元素满足下述关系：aij=aji(0<=i,j<=n-1)，则A为对称矩阵

a00

a10

a11

a20

a21

a22………………..

an-1,0

an-1,1

an-1,2…an-1,n-1以行序为主序存储其下三角

1

5137

5

0

800

18

9

26

302

5

1

7061

3

对称矩阵数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第90页!2.2数组——特殊矩阵三角矩阵的压缩存储以主对角线划分，三角矩阵有两种上三角矩阵：其主对角线下方元素均为常数下三角矩阵：其主对角线上方元素均为常数大多数情况下，三角矩阵中的常数为零

a00

a01…a0,n-1

ca11…a1,n-1…..cc…an-1,n-1

上三角矩阵

a00c…c

a10

a11…c…..

an-1,0

an-1,1…an-1,n-1

下三角矩阵数据结构与算法第二章清华大学出版社赵玉兰共109页，您现在浏览的是第91页!2.2数组——特殊矩阵对角矩阵（或带宽矩阵）的压缩存储

a00

a01

a10a11

a12

a21

a22

a23…………

an-2n-3

an-2n-2

an-2n-1