【大学资料】数据结构 chapter02_线性表

1、第二章 线性表,线性表是最简单和最常用的一种数据结构。 本章讨论线性表的定义、顺序存储结构和链式存储结构。 重点是线性表两种不同存储结构下的操作及其相应的算法。,第二章 线性表,2.1 线性表的概念及其抽象数据类型 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用一元多项式的表示及相加 2.5 顺序表与链表的综合比较（自学） 2.6 总结与提高（复习作业）,2.1 线性表的概念及其抽象数据类型,线性表的逻辑结构 线性表的定义 线性表的特点 线性表的抽象数据类型定义,线性表的逻辑结构,线性表的定义 线性表是由n（n=0）个类型相同的数据元素组成的有限序列，记做 (a1,a

2、2,ai-1,ai,ai+1,an) 第一个元素a1无直接前驱 最后一个元素an无直接后继 每个数据元素ai只有一个直接前驱和一个直接后继 数据元素之间具有一对一的关系 线性表的特点,线性表的逻辑结构,线性表的定义 线性表的特点 同一性：线性表由同类数据元素组成 有穷性：线性表由有限个数据元素组成 表长度：表中数据元素的个数 有序性：线性表中相邻数据元素之间存在序偶关系,线性表的抽象数据类型定义,ADT List 数据元素：D=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象 结构关系：R=|ai,ai+1D0,i=1,2,n-1 基本操作： (1)InitList(L) 操作前提：

3、L为未初始化的线性表 操作结果：将L初始化为空表 (2)DestroyList(L) 操作前提：线性表L已经存在 操作结果：将L销毁 (3)ClearList(L) 操作前提：线性表L已经存在 操作结果：将L置为空表,线性表的抽象数据类型定义,数据元素：D=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象 结构关系：R=|ai,ai+1D0,i=1,2,n-1 基本操作： (4)EmptyList(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回TRUE，否则返回FALSE (5)ListLength(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回0，否

4、则返回表中数据元素的个数 (6)Locate(L,e) 操作前提：线性表L已经存在，e为合法数据元素值 操作结果：如果L中存在数据元素e，则将“当前指针”指向数据元素e所在位置并返回TRUE，否则返回FALSE,线性表的抽象数据类型定义,数据元素：D=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象 结构关系：R=|ai,ai+1D0,i=1,2,n-1 基本操作： (7)GetData(L,i) 操作前提：线性表L已经存在，且i值合法 操作结果：返回线性表L中第i个数据元素的值 (8)InsList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：在表

5、中第i个位置之前插入新的数据元素e，L的长度加1 (9)DelList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1,2.2 线性表的顺序存储,线性表的顺序存储结构 顺序表的定义 地址映像的计算公式 线性表顺序存储的表示 线性表顺序存储结构上的基本操作 查找操作 插入操作 删除操作,线性表的顺序存储结构,顺序表的定义演示 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个数据元素，采用顺序存储结构存放的线性表通常称为顺序表。 顺序表归纳为：关系线性化、结点顺序存 地址映像的计算公式 线性表顺序

6、存储的表示,一组连续的存储单元存放线性表的数据元素,线性表的顺序存储结构,顺序表的定义演示 地址映像的计算公式 假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素地址loc(ai)的计算公式： loc(ai)=loc(a1)+(i-1)*k 线性表顺序存储的表示,线性表的顺序存储结构,顺序表的定义演示 地址映像的计算公式 线性表顺序存储的表示说明 #define MaxSize 100 /*此处的宏定义变量表示线性表的最大长度*/ typedef struct list DataType dataMaxSize; /*存放线性表的数组*/ int las

7、t; /*线性表最后一个元素的下标，空表为-1*/ SeqList;,思考：last和len有怎样的关系？,线性表的顺序存储结构,#define MaxSize 100 typedef struct DataType dataMaxSize; int last; SeqList; #define MaxSize 100 typedef struct DataType dataMaxSize; int len; SeqList;,(1)结点类型DataType由线性表中的元素类型确定。 (2)数组下标从0开始计数，即data0存放线性表的第一个元素a1。 (3)len=last+1,对顺序表的另

8、一种定义,线性表顺序存储结构上的基本操作,建立一个顺序存储的线性表算法描述 算法实现：将线性表的每个元素依次存储到数组中,a1,a2,ai,an,线性表顺序存储结构上的基本操作,void create(SeqList *L) int i; scanf(%d, ,main() static SeqList *L; int i; clrscr(); create(L); for(i=0;i=(*L).last;i+) printf(%d ,(*L).datai); ,线性表顺序存储结构上的基本操作,查找操作 按序号查找：GetData(L,i)算法描述 查找线性表L中的第i个数据元素。 算法思想：

9、测试i是否合法，如果合法，输出第i个数据元素的值；如果非法，则输出-1。 按内容查找：Locate(L,e)算法描述 在线性表L中查找与给定值e相等的数据元素。 算法实现：从第一个元素开始，依次将表中每个元素与e比较，如果相等，则查找成功，返回该元素在表中的序号；如果e与表中的所有元素都不相等，则查找失败，返回值为-1。,线性表顺序存储结构上的基本操作,DataType getdata(SeqList *L,int i) DataType e; if(i=0) 算法的时间复杂度：O(1),线性表顺序存储结构上的基本操作,int locate(SeqList *L,DataType e) int

10、 loc=-1,i; for(i=0;i=(*L).last;i+) if(e=(*L).datai) loc=i; break; return loc; 算法的时间复杂度：O(n),线性表顺序存储结构上的基本操作,插入操作 在表的第i个位置之前插入一个新元素e，使长度为n的线性表变成长度为n+1的线性表。 算法思想 原表插入位置之后的所有元素依次后移一位 空出插入位置，在该位置插入新结点 线性表表长加1 动画演示 算法描述 算法分析,线性表顺序存储结构上的基本操作,e,ai,an-1,an,e,线性表顺序存储结构上的基本操作,#define OK 1 #define ERROR 0 int

11、inslist(SeqList *L, int i, DataType e) int j; if(i(*L).last) printf(insert position is illegal.n); return ERROR; if(*L).last=MaxSize-1) printf(array is full.n); return ERROR; ,/*插入位置之后的所有元素依次后移一位*/ for(j=(*L).last;j=i;j-) (*L).dataj+1=(*L).dataj; /*将元素e插入位置i之前*/ (*L).datai=e; /*线性表表长加1*/ (*L).last+;

12、 return OK; ,线性表顺序存储结构上的基本操作,算法分析 在表尾插入元素，原有元素不需要移动，直接插入即可 在表头插入元素，所有元素（n个）依次后移一位，然后插入新元素 结论：元素的移动次数和插入位置有关 设Eins为平均移动次数，Pi为在第i个位置之前插入元素的概率，等概率(Pi=1/(n+1)情况下：,线性表顺序存储结构上的基本操作,删除操作 将表的第i个元素删除，使长度为n的线性表变成长度为n-1的线性表。 算法思想 将第i个位置的元素赋值给指定变量 原表删除位置之后的所有元素依次前移一位 线性表表长减1 动画演示 算法描述 算法分析,线性表顺序存储结构上的基本操作,*e,ai

13、+1,an-1,an,线性表顺序存储结构上的基本操作,#define OK 1 #define ERROR 0 int dellist(SeqList *L, int i, DataType *e) int j; if(i(*L).last) printf(delete position is illegal.n); return ERROR; if(*L).last=-1) printf(array is empty.n); return ERROR; ,/*将删除位置上的元素传递给指针变量e*/ *e=(*L).datai-1; /*删除位置之后的所有元素依次前移一位*/ for(j=i;

14、j=(*L).last;j+) (*L).dataj-1=(*L).dataj; /*线性表表长减1*/ (*L).last-; return OK; ,线性表顺序存储结构上的基本操作,算法分析 在表尾删除元素，原有元素不需要移动，直接删除最后一个元素即可 在表头删除元素，所有剩余元素（n-1个）依次前移一位 结论：元素的移动次数和删除位置有关 设Edel为平均移动次数，Qi为删除第i个元素的概率，等概率(Qi=1/n)情况下：,2.3 线性表的链式存储,单链表 单链表的定义 单链表的结构 单链表上的基本运算 初始化单链表 建立单链表：头插法、尾插法 查找单链表：按序号查找、按值查找 求单链表

15、长度操作 单链表插入操作 单链表删除操作 循环链表 双向链表,单链表,单链表的定义 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。 单链表的结构 单链表的存储结构描述,单链表,单链表的定义存储结构描述 单链表的结构 结点：表示线性表中的一个数据元素ai 存储数据元素ai的本身信息，数据域 存储一个指示其直接后继的信息（即直接后继的存储地址），指针域,数据域,指针域,头指针,尾结点,头结点,问题：空链表的结构如何表示？,单链表,单链表的定义 单链表的结构 单链表的存储结构描述例题 typedef struct LinkNode

16、 DataType data; struct LinkNode *next; Node,*LinkList;,头指针Head,链表中结点的物理顺序和逻辑顺序不一定一致。,例：线性表bat，cat，eat，fat，hat，jat，lat，mat的单链表示意图如下。,有关指针的几个基本操作的含义,Node s; s为结点类型的变量 Node *p,*q; LinkList H; p、q、H均为指向结点类型的指针变量 p指向某个结点且该结点非空 p-data表示p所指结点的数据域 p-next表示p所指结点中的指针域,请注意区分结点变量和指向结点的指针变量,有关指针的几个基本操作的含义,q=p; q

17、=p-next; p=p-next;,单链表上的基本运算,初始化单链表 void initlist(LinkList *L) /*L是指向单链表的头指针*/ /*malloc是动态分配函数，为头结点分配存储空间*/ *L=(LinkList)malloc(sizeof(Node); (*L)-next=NULL; ,L,单链表上的基本运算,建立单链表：头插法建表 算法思想：从一个空表开始，每次读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。 动画演示 算法描述,初始化的空表,s,s指向新申请的结点 s-data=a1,插入

18、第一个结点,s,s,s-next=H-next; H-next=s;,单链表上的基本运算,LinkList CreateFromHead(LinkList H) Node *s; DataType e; int flag=1; H=(LinkList)malloc(sizeof(Node);/*初始化空表*/ H-next=NULL; while(flag)/*用flag标志建表是否结束*/ scanf(%d, ,单链表上的基本运算,建立单链表：尾插法建表 算法思想：从一个空表开始，每次读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前单链表的表尾。 动画演示 算法

19、描述,初始化的空表,s,s指向新申请的结点 s-data=a1,插入第一个结点,s,在当前单链表表尾插入第二个结点,s,在当前单链表表尾插入第三个结点,r始终指向单链表的表尾 r-next=s; r=s;,单链表上的基本运算,LinkList CreateFromTail(LinkList H) Node *s,*r;DataType e;int flag=1; H=(LinkList)malloc(sizeof(Node); H-next=NULL; r=H; while(flag) scanf(%d, ,单链表上的基本运算,查找：按序号查找 算法思想：从单链表的头指针指向的头结点出发，逐个

20、结点向下搜索，直至所说到第i个结点为止顺序访问。 动画演示 算法描述,单链表上的基本运算,Node *Get(LinkList H, int i) int j=0; Node *p=H; while(p-next!=NULL) ,单链表上的基本运算,查找：按值查找 算法思想：从单链表的头指针指向的头结点出发，逐个将结点值和给定值e作比较，返回查找结果。 动画演示 算法描述,p-data=e,单链表上的基本运算,Node *Locate(LinkList H, DataType key) Node *p; p=H-next; while(p!=NULL) if(p-data!=key) p=p-

21、next; else break; return p; ,单链表上的基本运算,求单链表长度操作 算法思想：从结点“头”开始“数(p=L-next)”，用指针p依次指向各个结点，并附设计数器j计数，一直“数”到最后一个结点(p-next=NULL)，从而得到单链表的长度。 动画演示 算法描述,p=L-next; j=0;,p=p-next; j+;,单链表上的基本运算,int ListLength(LinkList L) Node *p=L-next; int j=0; while(p!=NULL) p=p-next; j+; return j; ,单链表上的基本运算,单链表插入操作 算法思想：

22、 查找：在单链表中找到第i-1个结点并由指针pre指示 申请：申请新结点s，将其数据域的值置为e 插入链表：通过修改指针域将新结点s插入单链表L 动画演示 算法描述,寻找第i-1个结点并由指针pre指示,申请新的结点S,插入s结点,与ai连接 s-next=pre-next;,ai-1与ai断开连接，插入s pre-next=s;,单链表上的基本运算,int InsList(LinkList L, int i, DataType e) Node *pre,*s; int k; pre=L;k=0; /*从头开始，查找第i-1个结点*/ while(pre!=NULL ,单链表上的基本运算,单链

23、表删除操作 算法思想： 查找：通过计数方式找到第i-1个结点并由指针pre指示 删除第i个结点并释放结点空间 动画演示 算法描述,寻找第i-1个结点并由指针pre指示,删除第i个结点并释放结点空间,r=pre-next; pre-next=pre-next-next; free(r);,删除结点i并释放结点空间,单链表上的基本运算,int DelList(LinkList L, int i, DataType *e) Node *pre,*r; int k; pre=L;k=0; while(pre-next!=NULL ,循环链表,循环链表的定义 循环链表（Circular Linked L

24、ist）是一个首尾相接的链表。将单链表最后一个结点的指针域由NULL改为指向头结点，就得到了单链形式的循环链表，称为循环单链表。 循环链表的结构,循环链表,循环链表的定义 循环链表的结构,rear-next=NULL; rear-next=L;,L,双向链表,双向链表的定义 单链表的每个结点里再增加一个指向其前驱的指针域prior，这样形成的链表中就有两条方向不同的链，称为双向链表（Double Linked List）。 双向链表的结点结构 双向链表的结点定义 双向链表的结构 双向链表上的基本运算,双向链表,双向链表的定义 双向链表的结点结构 双向链表的结点定义 双向链表的结构 双向链表上的

25、基本运算,双向链表,双向链表的定义 双向链表的结点结构 双向链表的结点定义 typedef struct node DataType data; struct node *prior; struct node *next; DoubleNode,*DoubleList; 双向链表的结构 双向链表上的基本运算,双向链表,双向链表的定义 双向链表的结点结构 双向链表的结点定义 双向链表的结构 双向链表上的基本运算,双向链表上的基本运算,双向链表的插入操作 算法思想：在双向链表的第i个结点之前插入一个结点，需要修改相关结点的前驱指针域和后继指针域。 动画演示 算法描述,s-next=p; p-pri

26、or=s;,指针p指向第i个结点 指针s指向需要插入的结点,s-prior=p-prior; p-prior-next=s;,双向链表上的基本运算,int InsDoubleList(DoubleList L, int i, DataType e) DoubleNode *s,*p; int k=0; p=L; while(p!=NULL ,s=(DoubleNode *)malloc(sizeof(DoubleNode); if(s) s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return TRUE; re

27、turn FALSE; ,双向链表上的基本运算,双向链表的删除操作 算法思想：删除双向链表的第i个结点，同样需要修改相关结点的前驱指针域和后继指针域。 动画演示 算法描述,指针p指向第i个结点（删除结点） 分析： 结点ai-1如何用指针p表示？ 结点ai+1如何用指针p表示？,结点ai-1：p-prior 结点ai+1：p-next,p-prior-next=p-next; p-next-prior=p-prior;,双向链表上的基本运算,int DelDoubleList(DoubleList L, int i, DataType *e) DoubleNode *s,*p; int k=0;

28、 p=L; while(p!=NULL ,2.4 线性表的应用一元多项式的表示及相加,一元多项式的表示 一元多项式的存储 一元多项式的相加运算,一元多项式的表示,一元多项式可按升幂的方式写成： ei为第i项的指数 pi是指数ei的项的系数 1=e1=e2=en,问题1：假设Qm(x)是一个一元多项式，如何用一个线性表Q表示？,问题2：若假设mn，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)，如何用线性表R表示？,一元多项式的存储,一元多项式的顺序存储表示 一元多项式的链式存储表示 一元多项式链式存储的结点结构 建立一元多项式链式存储算法,一元多项式的存储,一元多项式的顺序存储表示

29、方法1：只存储该一元多项式各项的系数，每个系数对应的指数项隐含在存储系数的顺序表的下标中。 演示1 方法2：只存储一元多项式的非零项，此时每个非零项需要存储：非零项系数和非零项指数。 演示2,一元多项式的顺序存储表示,Pn(x)=1+2x+3x2+5x3+2x5 适合于存储表示非零系数多的多项式 Pn(x)=1+5x1000+7x2000 特点：存在大量的零系数项,一元多项式的顺序存储表示,Pn(x)=1+5x1000+7x2000 适合于存储表示非零项系数少的多项式,pi：非零项系数 ei：非零项指数,一元多项式的链式存储表示,一元多项式链式存储的结点结构 在链式存储中，对一元多项式只存非零项，则该多项式中每一非零项由两部分构成：指数项和系数项。 一元多项式链式存储的结点定义 建立一元多项式链式存储算法,一元多项式的链式存储表示,一元多项式链式存储的结点结构 一元多项式链式存储的结点定义 typedef struct polynode int coef;/*系数域*/ int exp;/*指数域*/ struct ploynode *next;/*指针域*/ PolyNode,*PolyList; 建立一元多项式链式存储算法,一元