算数提高课件ds 2 2线性表

1第二章线性表

算法与数据结构张路

2

内容提要线性表的概念（逻辑结构）线性表的顺序表示和实现（顺序表）线性表的链式表示和实现（链表）线性表的应用3

顺序表示的优缺点优点:不需要附加空间；随机存取任一元素.缺点一开始就要分配足够大的一片连续的内存空间，很难估计所需空间的大小。更新操作代价大,插入与删除运算要移动大量的元素，效率较低。改进：使用链接存储结构（不要求逻辑相邻物理也相邻，通过指针表达逻辑关系），克服顺序存储的不足，但失去了随机存取的优点。4

线性表的链式表示和实现基本思想:用附加的指针来表示结点之间的线性关系单链表循环链表双向链表5

线性表的链式表示数据域指针域存储地址数据域指针域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531头指针H6

线性链表的逻辑状态（不带头结点）LiZhaoQianSunZhouWuZhengWang^Ha1an^a2...H头结点

带头结点的线性链表

线性链表的图示

（数据元素的逻辑顺序，不是存储位置）数据域可以存储任何附加信息指针域存储指向第一个节点7

链表的定义运算的实现数据域可以有多个信息。数据说明structNode; /*单链表结点类型*/typedefstructNode*PNode; /*结点指针类型*/structNode /*单链表结点结构*/{DataTypeinfo; PNodelink;};typedefstructNode*PLinkList;

/*单链表指针类型*/

PLinkListpllist;

/*指向单链表*/8

对于线性表(A,B,C,D,E,F),假定p指向结点C，则:p->link指向C的后继Dp->link->link指向?无头结点整个单链表：pllist第一个结点：pllist空表判断：pllist==NULL带头结点整个单链表：pllist头结点：pllist第一个结点：pllist->link，plist≠NULL空表判断：plist->link==NULL，plist≠NULLCPDECE^D

plistCE^D

plist9

单链表基本运算及其实现

创建空的单链表

Plinklist

createNull_link(void)插入结点

insert_link(PLinkListplist,inti,DataTypex)

删除结点

delete_link(PLinkListplist,DataTypex)定位运算

locate_link(PlinkListplist,DataTypex)求存储地址运算

find_link(PLinkListplist,inti)判空运算

isNull_link(PLinkListplist)10

单链表基本运算的实现-1函数名：createNulllist_link

功能:建立带有头节点的空链表程序：PLinkListcreateNulllist_link(void){ PLinkListpllist;pllist=(PLinkList)malloc(sizeof(structNode));if(pllist!=NULL)pllist->link=NULL;return(pllist);}

pllist

11

单链表基本运算的实现-2函数名：insert_link功能:在pllist带头结点的单链表中下标为i(第i+1个)的结点前插入一个值为ｘ的元素，并返回插入成功与否的标志。程序：intinsert_link(PLinkListpllist,inti,DataTypex)abxqpq->link=p->link;p->link=q;注：顺序不能反abp单链表12

intinsert_link(PLinkListpllist,inti,DataTypex){PNodep,q;p=pllist;intj=0;while(p!=NULL&&j<i)/*查找i的前驱*/{p=p->link;j++;}if(j!=i)/*查找失败*/{printf(“i=%disnotreasonable.\n”,i);return0;}q=(PNode)malloc(sizeof(structNode));/*申请新节点*/if(q==NULL)/*申请失败*/{printf("Outofspace!!!\n");return0;}else/*插入链表中*/{ q->info=x;q->link=p->link;p->link=q; return1;}}13

pabcp->link=p->link->link;单链表基本运算的实现-3函数名：delete_link功能:在pllist带头结点的单链表中删除第一个元素值为ｘ的元素，并返回删除成功与否的标志。程序：intdelete_link(PLinkListpllist,DataTypex)abp单链表14

intdelete_link(PLinkListpllist,DataTypex)/*在pllist带头结点的单链表中删除第一个元素值为ｘ的元素*/{PNodep,q;p=pllist; /*在pllist带头结点的单链表中找元素为x的结点的前驱*/while(p->link!=NULL&&p->link->info!=x) p=p->link;if(p->link==NULL)/*没找到元素为x的结点*/ {printf(”Notexist!\n”);return(0);}else/*删除该结点*/{q=p->link;p->link=q->link;free(q);return(1);}}15

pabx单链表基本运算的实现-4函数名：locate_link功能:在pllist带头结点的单链表中定位第一个元素值为ｘ的元素，并返回该元素的标志。程序：PNodelocate_link(PLinkListplist,DataTypex)ec……16

PNode*locate_link(PlinkListplist,DataTypex)/*在pllist带头结点的单链表中定位第一个元素值为ｘ的元素*/{PNodep,q;p=pllist; /*在pllist带头结点的单链表中找元素为x的结点的前驱*/while(p->link!=NULL&&p->link->info!=x) p=p->link;

/*返回元素为x的结点的位置*/return(p->link);}17

单链表运算的时间复杂度由于“插入/删除运算”首先需要定位，而定位必须从头结点开始顺链一个一个结点进行比较，因此其“基本的操作”为比较运算。比较运算的执行次数与结点的位置有关最好情况时为1次（第一个结点），最坏为n次（所有结点皆比较一次）时间复杂度为O(n)平均情况下需要查找n/2个元素时间复杂度为O(n)插入与删除元素时所花费时间只是申请结点和修改指针的时间，时间复杂度为O(1)18

单链表与顺序表的比较存储顺序表为静态结构，而链表为动态结构。单链表的存储密度比顺序表低；在许多情况下链式的分配比顺序分配有效；修改在单链表里进行插入、删除运算比在顺序表里容易得多；顺序表通过数据元素移动完成，而链表通过修改指针完成。定位对于顺序表，可通过简单的定位公式随机访问任一个元素;而在单链表中，需要顺着链逐个进行查找。因此，顺序表为随机存取结构，而链表不是。19

（1）有利于基本运算的实现频繁访问：顺序表（随机存取）；频繁插入、删除：链表（2）有利于数据的特性顺序表：难于事先估计数据元素个数，过大浪费空间，过小易产生溢出；链表：动态申请，但存储密度比顺序表低；（3）有利于软件环境（程序设计语言）程序设计语言是否支持动态分配？Fortran、Basic等不支持动态分配，此时只能选择顺序表。

单链表与顺序表的选择20

单链表存在的问题单链表的表长是一个隐含的值（后继为空）在单链表最后插入一个元素时，需要遍历整个链表在链表中，元素的位序概念淡化，结点的概念强化改进链表的设置21

线性表的链式表示扩充单链表循环链表双向链表22

无头结点：循环条件：p->link==pclist表空条件：pclist==NULL带头结点：循环条件：p->link==pclist表空条件：pclist->link==NULLpclist…infoa1an头结点建立：将最后一个结点的指针项指向第一个结点（或头结点），构成一个循环链。循环链表的优点：

从任何一个结点出发，可以访问表中任何一个结点元素。循环链表23

上面循环链表的缺点：

如果要访问最后一个结点，仍要访问表中所有的结点。改进：

修改pclist指向最后一个结点，方便某些操作(如两个链表合并等）。pclist…a1a2an最后结点：pclist第一个结点：pclist->link循环条件：p==pclist空表判断：pclist==NULL思考问题1：如何将一个单循环链表（无头结点，且pclist指向第一个结点）倒置？

(a1,a2,…,an)=>(an,an-1,…,a1)24

palist…a0an-1pblist…b0bn-1…a0an-1pmlist…b0bn-1思考问题2：将仅设尾指针的两个循环链表合并25

线性表的链式表示和实现单链表循环链表双向链表26

链表的另一种定义structNode; /*单链表结点类型*/typedefstructNode*PNode; /*结点指针类型*/structNode /*单链表结点结构*/{ DataTypeinfo; PNodelink;};structLinkList /*单链表类型定义*/{ PNodehead; /*指向单链表中的第一个结点*/};typedefstructLinkList*PLinkList; /*单链表类型的指针类型*/PLinkListplist;27

无头结点整个单链表：plist第一个结点：plist->headplist≠NULL空表判断：plist->head=NULL，plist≠NULL带头结点整个单链表：plist头结点：plist->headplist≠NULL第一个结点：plist->head->linkplist->head≠NULL空表判断：plist->head->link=NULL，plist->head≠NULLCE^D

plist

headCE^D

plist

head28

单链表缺点：找后继容易，找前驱必须从头开始查找。双向链表：既可以找前驱，也可以找后继。不带头结点 空表判断：pdlist->head=NULL

最后结点判断：p->rlink=NULL

第一个结点：pdlist->head

最后结点：pdlist->rear结点结构：infollinkrlinkpdlist^k1k2kn……^headrearP->rlink->llink=p->llink->rlink=p

双向链表29

双向链表特点：既可以找前驱，也可以找后继。数据说明：structDoubleNode /*双链表结点结构*/{DataTypeinfo;structDoubleNode*llink,*rlink;};typedefstructDoubleNode*PDoubleNode;/*结点指针类型*/llinkrlinkinfo双向链表定义30

structDoubleList /*双链表类型*/{PDoubleNodehead;/*指向第一个结点*/PDoubleNoderear;/*指向最后一个结点*/};typedefstructDoubleList*PDoubleList; PDoubleListpdList;/*pdlist指向双链表*/pdListpdList->rear….….pdList->head31

删除双向链表的结点ABCp(p->llink)->rlink=p->rlinkp->rlink->llink=p->llink双向链表结点删除图示free(p)32

往双向链表中p前插入结点(1)q->llink=p->llink;(2)p->llink->rlink=q;(3)q->rlink=p;(4)p->llink=q;ABCqp双向链表结点插入的图示p指向结点后插入新结点s:q->llink=p;(3)p->rlink->llink=q;q->rlink=p->rlink;(4)p->rlink=q;(1)(2)(4)(3)ABCpq(1)(4)(3)(2)q=(PDoubleNode)malloc(sizeof(structDoubleNode)33

双向循环链表PDoubleListpdList;/*pdlist指向双链表*/空表判断：pdlist->rlink==NULL最后结点判断：p->rlink==pdlist或

p==pdlist->llink第一个结点：pdlist->rlink最后结点：pdlist->llinkpdlistk0k1kn-1……34

内容提要线性表的概念（逻辑结构）线性表的顺序表示和实现（顺序表）线性表的链式表示和实现（链表）线性表的应用35

线性表的应用——链表部分问题Josephus问题一元多项式表示和运算36

循环链表方式实现步骤：建立循环链表；出列算法；找循环单链表中的第s个结点放在指针变量p中，从p所指结点开始计数寻找第m个结点，输出该结点的元素值；删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行②，直到所有结点被删除为止；主程序时间复杂度分析：创建链表，求第s个结点，求n个第m个应出列的元素O(n)+O(s)+O(m*n))37

线性表的应用——链表部分问题Josephus问题一元多项式表示和运算38

一元多项式：Pn(x)=p0+p1x+p2x2+…+pnxn线性表表示：P=(p0,p1,p2,…,pn)顺序表表示：只存系数（第i个元素存xi的系数）