《数据结构与算法 教学课件 ppt 作者 王曙燕 chapter2 线性表》由会员分享，可在线阅读，更多相关《数据结构与算法 教学课件 ppt 作者 王曙燕 chapter2 线性表（49页珍藏版）》请在金锄头文库上搜索。
1、1,第 2 章 线性表,2.2 线性表的概念及运算,2.3 线性表的顺序存储,2.4 线性表的链式存储,2.5 顺序表和链表的比较,2.1 应用实例,2.6 实例分析与实现,第 2 章 线性表,2.1 应用实例,应用实例一：约瑟夫环（Josephus）问题 约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的。问题描述为： 编号为1，2，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个
2、人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。,第 2 章 线性表,2.1 应用实例,应用实例二：一元多项式运算器 要实现一元多项式运算器，首先要设计表示一元多项式P=p0+p1X+p2X2 +pnXn的合适的数据结构，并支持多项式的下列运算。 （1）建立多项式。 （2）输出多项式。 （3）+，两个多项式相加，建立并输出和多项式。 （4），两个多项式相减，建立并输出差多项式。 （5）*,多项式乘法。 （6）( ),求多项式的值。 （7）derivative(), 求多项式导数。,4,第 2 章 线性表,2.2 线性表的概念及运算,定义：线性表(Linear
3、List)是由n (n0)个类型相同的数 据元素a1,a2,，an组成的有限序列，记做（a1,a2,， ai-1，ai，ai+1， ，an）。,数据元素之间是一对一的关系，即每个数 据元素最多有一个直接前驱和一个直接后继。,逻辑结构图：,5,第 2 章 线性表,2.2 线性表的概念及运算,特点：, 同一性：,线性表由同类数据元素组成， 每一个ai必须属于同一数据对象。, 有穷性：,线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。, 有序性：,线性表中相邻数据元素之间存在 着序偶关系。,6,第 2 章 线性表,2.3 线性表的顺序存储,定义:,采用顺序存储结构的线性表通常称为顺序表。
4、,假设线性表中每个元素占k个单元，第一个元素 的地址为loc(a1)，则第k个元素的地址为：,loc(ai) =loc(a1)+(i-1)k,7,第 2 章 线性表,2.3 线性表的顺序存储,数 据 结 构 与 算 法,8,第 2 章 线性表,2.3 线性表的顺序存储,C语言定义,#define maxsize 线性表可能达到的最大长度 typedef struct ElemType elemmaxsize； int length； SeqList；,/表长,9,第 2 章 线性表,2.3 线性表的顺序存储,基本运算, 查找操作, 插入操作, 删除操作,10,数 据 结 构,第 2 章 线性表
5、,2.3 线性表的顺序存储, 查找操作,按序号查找GetData(L,i)：,要求查找线性表L中第i个数据元素，其结果是L.elemi 。,按内容查找Locate（L,x）:,要求查找线性表L中与给定值x相等的数据元素，其结果 是：若在表L中找到与x相等的元素，则返回该元素在表 中的序号；若找不到，则返回一个“空序号”，如-1。,11,第 2 章 线性表,2.3 线性表的顺序存储,按内容查找Locate（L,x）:,int Locate(SeqList L，ElemType x) int i=1 ; while (i=L.length) ,int Opt_Locate(SeqList L，El
6、emType x) int i; L.elem0=x; /*标识边界*/ i=L.length; while (L.elemi!=x) i-; return(i); ,12,第 2 章 线性表,2.2 线性表的顺序存储, 插入操作,是指在表的第i (1in+1)个位置，插入一个新元素e， 使长度为n的线性表 (e1，ei-1，ei，en) 变成 长度为n+1的线性表（e1，,ei-1，x，ei，en）。,例如：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元 素之前插入一个元素“21”。则需要将第9个位置到 第4个位置的元素依次后移一个位置，然后将“21” 插入到第4
7、个位置。 (4,9,15, 21 28,30,30,42,51,62),#define OK 1 #define ERROR 0 int InsList(SeqList *L,int i,ElemType x) int k; if( (iL-length+1) ) printf(“插入位置i值不合法”)； return(ERROR); if(L-length=maxsize-1) printf(“表已满无法插入”)； return(ERROR); for(k=L-length;k=i;k-) L-elemk+1=L-elemk; L-elemi=x; L-length+; return(OK)
8、; ,时间复杂度： O(n),数 据 结 构 与 算 法,13,第 2 章 线性表,2.3 线性表的顺序存储, 删除操作,是指将表的第i(1in)个元素删去，使长度为n的 线性表 (e1，,ei-1，ei，ei+1，en)，变成长 度为n-1的线性表(e1，,ei-1， ei+1，en)。,int DelList(SeqList *L,int i,ElemType *e) int k; if(iL-length) printf(“删除位置不合法！”)； return(ERROR)； *e= L-elemi; for(k=i;klength-1;k+) L-elemk= L-elemk+1; L
9、-length-; return(OK); ,时间复杂度： O(n),14,第 2 章 线性表,2.2 线性表的顺序存储,例2-1 ：有两个顺序表LA和LB，其元素均为非递减 有序排列，编写一个算法，将它们合并成 一个顺序表LC，要求LC也是非递减有序排列。,算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj ，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素
10、放到表LC中。,void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=1; j=1; k=1; while(ilength ,15,第 2 章 线性表,2.3 线性表的顺序存储,优点：,可方便地随机存取表中的任一元素。,缺点：, 插入或删除运算不方便，除表尾的位置外，在表的其 它位置上进行插入或删除操作都必须移动大量的结点， 其效率较低；,无须为表示结点间的逻辑关系而增加额外的存储空间；, 由于顺序表要求占用连续的存储空间，存储分配只能预 先进行静态分配。因此当表长变化较大时，难以确定合 适的存储规模。,返回,16,第 2 章 线性表,2.4
11、线性表的链式存储,定义:,采用链式存储结构的线性表称为链表 。,动态链表,静态链表,单链表,双链表,循环链表,实现角度,链接方式,17,第 2 章 线性表,2.4 线性表的链式存储,单链表,：链表中的每个结点只有一个指针域,结点（Node）：,单链表包括两个域,数据域：,指针域：,用来存储结点的数据值,用来存储数据元素的直 接后继的地址（或位置）,头指针 ：,指向链表头结点的指针。,18,第 2 章 线性表,2.4 线性表的链式存储,单链表,H,19,第 2 章 线性表,2.4 线性表的链式存储,单链表,头结点,带头结点的空单链表,带头结点的单链表,20,数 据 结 构,第 2 章 线性表,2
12、.4 线性表的链式存储,单链表,存储结构描述,typedef struct Node ElemType data； struct Node *next； LNode, *LinkList；,21,第 2 章 线性表,2.4 线性表的链式存储,单链表,的基本运算,建立单链表 单链表查找 单链表插入 单链表删除 求单链表的长度,22,第 2 章 线性表,2.4 线性表的链式存储, 建立单链表,头插法建表,s指向新申请的结点 s-data=A;,插入第一个结点：,插入某一个结点：,s-next=H-next;,H-next=s;,顺序可以 颠倒吗？,23,第 2 章 线性表,2.3 线性表的链式存储
13、, 建立单链表,头插法建表,算法,Linklist CreateFromHead( ) LinkList L; LNode *s; int x; int flag=1; L=(Linklist)malloc(sizeof(LNode)； L-next=NULL; scanf(“%d”, ,24,第 2 章 线性表,2.4 线性表的链式存储, 建立单链表,尾插法建表,s指向新申请的结点 s-data=A;,插入第一个结点：,插入某一个结点：,r-next=s;,r=s;,顺序可以 颠倒吗？,25,第 2 章 线性表,2.4 线性表的链式存储, 建立单链表,尾插法建表,算法,Linklist Cr
14、eateFromTail() LinkList L; LNode *r, *s; int x; L=(LNode * )malloc(sizeof(LNode); L-next=NULL; r=L; scanf(“%d”, ,26,第 2 章 线性表,2.4 线性表的链式存储,单链表按序号查找,按序号查找,设带头结点的单链表的长度为n，要查找表中第i个结点， 则需要从单链表的头指针L出发，从第一个结点（L-next） 开始顺着链域扫描。 用指针p指向当前扫描到的结点,初值指向第一个结点 （p=L-next），用j做记数器，累计当前扫描过的结点数 （初值为0），当j = i 时，指针p所指的结点
15、就是要找的 第i个结点 。,Node *Get(LinkList L, int i) LNode *p； p=L； j=0； while (p-next!=NULL)&(jnext； j+； if（i= =j） return p； else return NULL； ,27,第 2 章 线性表,2.4 线性表的链式存储,按值查找,指在单链表中查找是否有结点值等于e的结点，若有的 话，则返回首次找到的其值为e的结点的存储位置，否则返 回NULL。 查找过程从单链表的头指针指向的第一个结点出发， 顺着链逐个将结点的值和给定值e作比较。,Node *Locate( LinkList L,ElemType key) LNode *p; p=L-next; while (p!=NULL) if (p-data!=key) p=p-next; else break; return p; ,单链表按内容查找,28,第 2 章 线性表,2.4 线性表的链式存储,单链表插入,要在带头结点的单链表L中第i个数据元素之前插入一个 数据元素e，需要首先在单链表中找到第i-1个结点并由指针 pre指示，然后申请一个新的结点并由指针s指示，其数据域 的值为e，并修改
