教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net.

Presentation on theme: "教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net."— Presentation transcript:

1 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net
计算机软件技术基础 教 师：曾晓东 电 话： E_mail:

2 第三章 线性结构 3.1 线性表 3.2 栈和队列 3.3 数组 一、线性表概念与运算 二、线性表的顺序存储结构 三、线性表的链式存储结构
四、循环链表与双向链表 3.2 栈和队列 3.3 数组 计算机软件技术基础 数据结构——线性表

3 3.1 线性表 一、线性表的概念与运算 1、线性表概念
定义： n(n≥0)个同类元素构成的有限线性序列，表示为L=（a1,a2,…,an）。 n为线性表L的表长 线性表的结构特性 除第一个元素外，线性表中所有元素有唯一直接前驱 除最后一个元素外，线性表中所有元素有唯一直接后继 ai的直接前驱是ai-1，直接后继是ai+1 计算机软件技术基础 数据结构——线性表

4 一、线性表的概念与运算 2、线性表运算 1)初始化 initiate ( L) 建立一个空线性表
2)求表长 length (L) 求表的数据元素个数 3)取结点 get(L, i) 给定元素序号 i,取元素内容(或结点地址指针） 4)定位 locate(L, x) 给定元素内容x，取元素序号 i(或结点地址指针) 5)插入 insert(L , i, x) 给定结点序号i，在其前(或其后)插入结点 6)删除 delete(L, i) 给定结点序号，删除该结点(或其后结点) 7)遍历 getlist(L) 以某种顺序读取线性表L的所有元素一次 8)查找 search(L,x)查找数据元素x在线性表L中的序号或结点地址 9)排序 sort(L) 按关键字递增或递减的顺序对L的元素重新排列 计算机软件技术基础 数据结构——线性表

5 一、线性表的概念与运算 3、线性表的分类 按存储方式分类 顺序表 链表 按可进行的操作的不同分类 栈 队列 串 数组 计算机软件技术基础
数据结构——线性表

6 3.1 线性表 二、线性表的顺序存储结构 1、顺序表 用一组地址连续的存储单元存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构。 该结构用高级语言中的一维数组类型表示。数组中的分量下标即为元素在线性表中的序号。例如：可用一维数组A[n]来存储线性表： （a1, a2 ,...，an）。 这里需要声明：C语言中，数组下标从0开始。 计算机软件技术基础 数据结构——线性表

7 二、线性表的顺序存储结构 地址计算：设每个元素占L个单元，线性表在内存中的首地址为：Loc(a1)=b，则线性表中第i个元素的存储地址为：
Loc(ai)=Loc(ai-1)+L=Loc(a1)+(i-1)*L=b+(i-1)*L 特点：这种存储结构只要知道元素的序号，就很容易找到第i个数据元素，且无论序号i为何值，找到第i个元素所需时间相同。所以，这种存储结构亦称为随机存储结构。 计算机软件技术基础 数据结构——线性表

8 二、线性表的顺序存储结构 顺序表的类型定义 const int MAXSIZE 100; struct sequenlist {
elemtype data[MAXSIZE]; int length; } 顺序表类型的变量定义 sequenlist list,*L; 计算机软件技术基础 数据结构——线性表

9 二、线性表的顺序存储结构 2、顺序表有关操作 1) 顺序表初始化 ⑴操作: 建立一个长度为零的空表 ⑵接口： 入口和出口参数均为表头指针 L
⑴操作: 建立一个长度为零的空表 ⑵接口： 入口和出口参数均为表头指针 L ⑶算法描述：令表长度字段 list.length为零 ⑷函数实现： void setNull(sequenlist &L ) { L. length = 0; } L.length = 0; 计算机软件技术基础 数据结构——线性表

10 二、线性表的顺序存储结构 2) 顺序表的插入 ⑴ 操作: 从末尾至第i个结点将内容依次后挪 将新结点放入第i个结点位置 表长度加一
⑵ 接口： 入口参数: 表头指针 L，位置 i，新结点x 出口参数: 表头指针 L 函数值： 成功则返回1(用true表示), 失败则返回0(用false表示) 计算机软件技术基础 数据结构——线性表

11 二、线性表的顺序存储结构 (3) 算法描述 计算机软件技术基础 数据结构——线性表

12 二、线性表的顺序存储结构 (4) 函数实现 const int true = 1; const int false = 0;
int insert(sequenlist &L,int i,elemtype x){ int j; if(i<1||i>L.length+1) return(false); for(j=L.length-1;j>=i;j--） L.data[j+1] = L.data[j]; L.data[i] = x; L.length ++ ; return(true); } 计算机软件技术基础 数据结构——线性表

13 二、线性表的顺序存储结构 计算机软件技术基础 数据结构——线性表

14 二、线性表的顺序存储结构 (5) 时间复杂度分析 计算机软件技术基础 数据结构——线性表

15 二、线性表的顺序存储结构 3）顺序表的删除 ⑴ 操作: 从第i个结点至末尾将内容依次前挪 表长度减一 ⑵ 接口：
入口参数：表头指针 L，位置 i 出口参数: 表头指针 L 函数值： 成功则返回 1 (用true表示), 失败则返回 0 (用false表示) 计算机软件技术基础 数据结构——线性表

16 二、线性表的顺序存储结构 (3)算法描述 计算机软件技术基础 数据结构——线性表

17 二、线性表的顺序存储结构 (4)函数实现 int delete(sequenlist &L,int i){ int j;
if(i<1||i>L.length) return(false); for(j=i+1;j<L.length;j++） L.data[j－1]=L.data[j]; L.length--; return (true); } 计算机软件技术基础 数据结构——线性表

18 二、线性表的顺序存储结构 计算机软件技术基础 数据结构——线性表

19 二、线性表的顺序存储结构 (5) 时间复杂度分析 计算机软件技术基础 数据结构——线性表

20 二、线性表的顺序存储结构 4) 顺序表的特点 按序号访问结点，存取时间与位置无关，快 可进行效率较高的折半查找操作
插入和删除结点要挪动大量元素，时间长短与位置有关 要求存放元素的存储单元连续； 有时会造成空间浪费或溢出。 适用范围 一旦建立，则插入、删除操作较少，经常进行查询操作的线性表 计算机软件技术基础 数据结构——线性表

21 3.1 线性表 三、线性表的链式存储结构 1、线性链表 特点： 存储单元可以不连续，每个结点加上指针字段，指向其下一个结点地址
1)特点及分类 特点： 存储单元可以不连续，每个结点加上指针字段，指向其下一个结点地址 链式存储，动态分配结点单元 分类：单向链表，双向链表，循环链表 计算机软件技术基础 数据结构——线性表

22 三、线性表的链式存储结构 data next 2)结点构成及类型定义 数据域 指针域 head ^ head ^ 结点构成
两部分：数据域，指针域 类型及变量定义: struct link{ struct elemtype data; struct link * next;} typedef link * NODE; 指示链表中第一个结点的指针称为头指针（head），最后一个结点没有后继结点，它的指针域为空(记为NULL或∧)。 data next 数据域 指针域 head ^ （空表） head ^ 计算机软件技术基础 数据结构——线性表

23 三、线性表的链式存储结构 2、线性链表的基本操作 1）线性链表的初始化 （1）操作 给头节点分配一个空间 头结点指针域赋值为空（NULL）
（2）接口 入口参数为空， 出口参数用return返回头节点的地址 （3）算法描述 动态分配一个新结点，用h指向之 返回h的值 计算机软件技术基础 数据结构——线性表

24 三、线性表的链式存储结构 h （4）函数实现 link * initiat(void){ link * h; h = new link;
h->next = NULL; return (h); } h head 空 NULL 计算机软件技术基础 数据结构——线性表

25 三、线性表的链式存储结构 2)单链表的建立 算法：先建立一个空链表，然后不断插入新结点 按插入位置有三种方法： 每次插入结点在链首
每次插入结点在链尾 按数据域值大小排序 我们介绍第2种方法。 计算机软件技术基础 数据结构——线性表

26 三、线性表的链式存储结构 每次插在链尾的单链表建立方法 ⑴ 操作:
①输入数据 x（为简化起见，我们假设结点的数据域仅为一个简单变量data） ②若 x=结束标志，结束 ③找到链尾 ④在链尾结点后插入一个新结点，返回 ① ⑵ 接口： 入口/出口参数：表头指针 h 计算机软件技术基础 数据结构——线性表

27 三、线性表的链式存储结构 （3）算法描述 计算机软件技术基础 数据结构——线性表

28 三、线性表的链式存储结构 (4)函数实现 void rcreate(link * h){ link *p=h,*x;
x=pread(); /*pread()动态分配一个结点空间, 并且给结点的数据域赋值*/ while(x->data != －1){ while(p->next != NULL) p = p->next ; // 将指针移动表尾 p->next=x; x->next=NULL; p = p－>next ; x=pread(); // 继续处理下一个结点 } 计算机软件技术基础 数据结构——线性表

29 三、线性表的链式存储结构 3) 线性链表的插入 在链表L中q结点后插入结点s要涉及两个指针的修改：
新结点s的指针域指向原结点q的后继结点p： s－>next = q－>next 原结点q的指针域指向新结点s： q－>next = s 计算机软件技术基础 数据结构——线性表

30 三、线性表的链式存储结构 算法一：在线性表的第i个结点前插入新结点 ⑴ 操作: ①在链表L中找到第 i－1 个结点 ②动态分配一个新结点
⑵ 接口： . 入口参数：表头指针h，序号 i ，数据变量x . 出口参数: 表头指针h 计算机软件技术基础 数据结构——线性表

31 三、线性表的链式存储结构 ⑶算法描述 计算机软件技术基础 数据结构——线性表

32 三、线性表的链式存储结构 （4）函数实现 link * insert(link * h,int i,elemtype x) {
link * p=h,*t ; int j=0; while(p != NULL && j<i-1) { //查找第i-1个结点 p = p->next ; j++; } if(j != i-1 ) return(NULL); //表长小于i-1，插入失败 t = new link; t->data = x ; t->next = p->next ; p->next = t; return(h); } 计算机软件技术基础 数据结构——线性表

33 三、线性表的链式存储结构 (5)算法分析 本算法的主要运算为单链表指针的后移，共需移动i次
与前面对顺序表的分析类似，可得此算法的时间复杂度为O(n) 但此算法不需移动数据元素，故在数据元素较大时，此算法为优 计算机软件技术基础 数据结构——线性表

34 三、线性表的链式存储结构 算法二：在线性链表中的p结点后面插入一个值为x的新结点 ⑴ 操作: ① 动态分配一个新结点
③ 新结点指针域指向原后继结点 ④ 原结点指针域指向新结点 ⑵ 接口： 入口参数：链表头结点head，结点指针p ，数据变量x 出口参数: 链表头结点head 计算机软件技术基础 数据结构——线性表

35 三、线性表的链式存储结构 （3）算法描述 计算机软件技术基础 数据结构——线性表

36 三、线性表的链式存储结构 （4）函数描述 link * insert(link * head,link * p,datatype x){
link *s; if(head==NULL){ // 如果表有空，则对其初始化 initiat(head); p=head; } s = new link; s->data = x; s->next = p->next; p->next = s; return(head); } 计算机软件技术基础 数据结构——线性表

37 三、线性表的链式存储结构 4)线性链表的删除 只涉及一个指针的修改： i结点前驱的指针域指向i结点后继结点：
pi-1－>next = pi－>next 释放i结点 p q ┄ head ^ a 计算机软件技术基础 数据结构——线性表

38 三、线性表的链式存储结构 ⑴ 操作: ①在链表L中找到第 i－1 个结点 ②i结点指针域赋给i-1结点的指针域 ③释放i结点 ⑵ 接口：
入口参数：表头指针 h，序号 i 出口参数: 无 计算机软件技术基础 数据结构——线性表

39 三、线性表的链式存储结构 (3)算法描述 计算机软件技术基础 数据结构——线性表

40 三、线性表的链式存储结构 (4)函数实现 void delete(link * h ,int i){
link * p=h,*s ; int j=0; while(p != NULL && j < i－1) { p = p->next ; j++; }// 查找第i-1个结点 if(j != i-1) return; // 表长小于i-1，删除失败 s = p->next; // 第i个结点 if(s==NULL) return; // 表长小于i，删除失败 p->next = s->next; delete(s); // 释放i结点 } 计算机软件技术基础 数据结构——线性表

41 三、线性表的链式存储结构 5)线性链表的特点 优点： 内存利用好， 插入删除方便，效率较高 缺点： 元素访问不方便
不能进行效率较高的折半查找 适用范围 变动较大（删除、插入频繁）的线性表 计算机软件技术基础 数据结构——线性表

42 3.1 线性表 四、循环链表与双向链表 1、循环链表 特点：
表中最后一个结点的指针域不为空，而是指向表头，整个链表形成一个环。与一般链表不同之处在于只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始。 head 非空表 head 空表 计算机软件技术基础 数据结构——线性表

43 四、循环链表与双向链表 表尾元素的next指针不为NULL 判断表是否为空的方法是判断头结点的next指针是否指向头结点
好处：从链表中任何一个节点都可以找到其它的节点。 计算机软件技术基础 数据结构——线性表

44 四、循环链表与双向链表 2)采用尾指针的循环链表 rear->next->next 非空表 rear … 空表
计算机软件技术基础 数据结构——线性表

45 四、循环链表与双向链表 3)两个循环链表的链接 ra p ① ② 存储池 ③ ④ rb 计算机软件技术基础 数据结构——线性表

46 四、循环链表与双向链表 两循环链表的链接 link *CONNECT(link *ra,link *rb) { link *p;
/*1*/ p＝ra->next; // 获取ra的头结点 /*2*/ ra->next＝rb->next->next;// 将rb链入ra中 /*3*/ delete (rb->next); // 释放rb的头结点 /*4*/ rb->next＝p;// rb的尾结点的后继为ra的头结点 return(rb); // 返回链表的尾指针 } 计算机软件技术基础 数据结构——线性表

47 四、循环链表与双向链表 head head 2、双向链表 头结点 特点
表中每个结点有两个指针域：一个指向直接后继，一个指向直接前驱，那么从表中任一结点都可以随意向前或向后查找。但在作插入、删除运算时，需同时修改两个方向上的指针。 (1)带头结点的双向循环链表（空表） head 头结点 (2)带头结点的双向循环链表（非空表） head 计算机软件技术基础 数据结构——线性表

48 四、循环链表与双向链表 prior data next dulink *pl ； 2)初始化 (1)结点构成 数据域 data
(1) 结点结构 (2)类型及变量定义: struct dulink{ elemtype data ； // 数据域 dulink *prior, *next; // 前趋和后继指针 }; dulink *pl ； 计算机软件技术基础 数据结构——线性表

49 四、循环链表与双向链表 3)双向链表逻辑结构 i结点后继结点为 p->next；前趋结点为 p->prior
h. prior a 1 next 。 i next n ^ p . i结点后继结点为 p->next；前趋结点为 p->prior 满足关系： (p->next)->prior = p (p->prior)->next = p 4)操作 对仅需涉及一个方向指针的操作与单链表相同，如： 求表长 LENGTH(L)、取元素 GET(L,i)、定位LOCATE(L, x) 在插入、删除时不同，需同时修改两个方向上的指针 计算机软件技术基础 数据结构——线性表

50 四、循环链表与双向链表 (1) 双向链表的后插操作 将数据x插入到以head为表头指针的双向链表中的p结点的后面
void duinsert(dulink *head, dulink * p,elemtype x){ dulink *s; s＝new dulink; s->data＝x; s->next＝p->next; s->prior＝p; p->next->prior＝s; p->next＝s; } p s a b x 计算机软件技术基础 数据结构——线性表

51 四、循环链表与双向链表 (2)双向链表的删除操作 删除以head为头结点的双向链表中的结点p
void dudelete(dulink *head,dulink *p){ p->prior->next = p->next; p->next->prior = p->prior; delete(p); } a b c p 计算机软件技术基础 数据结构——线性表

52 3.1 线性表 五、应用实例——一元多项式相加  问题描述 一个一元多项式可以表示为：
其中每一项由系数Pi及x的指数i组成。若多项式按升幂排列，则它由n+1个系数唯一确定，因此可以用一个线性表P表示： 其指数i隐藏在系数Pi的序号内。 计算机软件技术基础 数据结构——线性表

53 五、应用实例  问题分析 1）存储结构：多项式相加时，常要合并同类项，由此就要改变多项式的系数和指数，而且在实际问题中，时常会出现多项式的次数很高但又存在大量零系数的项，因此宜采用链式存储结构。 2）结点结构：每一个非零项构成链表中的一个结点，结点由两个数据域和一个指针域构成，如下图： coef exp next pi 计算机软件技术基础 数据结构——线性表

54 五、应用实例 3）链表结构：采用带头结点的线性链表表示多项式A(x)、B(x)，相加后结果在线性链表C(x)中。
4）运算过程：设指针ha、hb分别为多项式链表A(x)、B(x)的头指针，指针p、q的初始位置分别指向A(x)、B(x)中的第一项。 过程为：比较p、q所指结点中的指数项。 若：p->exp<q->exp，那么p所指的结点为C(x)中的一项，令p指针后移一个结点； 计算机软件技术基础 数据结构——线性表

55 五、应用实例 若：p->exp>q->exp，则q所指的结点为C(x)中的一项，将q结点插入p结点之前，并令q指针后移一个结点； 若：p->exp==q->exp，则将两个结点中的系数相加，当和不为零时，修改p结点中的系数，释放q结点；否则，删去p结点，同时释放p、q结点。 这种方法实际上是将B(x)加到A(x)中，最后形成C(x)，因此C(x)中的结点不需要重新生成。  算法描述（一元多项式加法） 计算机软件技术基础 数据结构——线性表

56 EXPNODE. AddPoly(EXPNODE. ha,EXPNODE
EXPNODE *AddPoly(EXPNODE *ha,EXPNODE *hb) { p=ha->next; q=hb->next; pre=ha; hc=ha; while (p!=NULL && q!=NULL) { if (p->exp<q->exp){ pre=p; p=p->next; }else if (p->exp>q->exp){ u=q->next; q->next=p; pre->next=q; pre=q; q=u; }else{ double x=p->coef+q->coef; if (fabs(x)<=1e-6){ p->coef=x; pre=p; } else{ pre->next=p->next; delete(p); } p=pre->next; u=q; q=q->next; delete(u); } } if (q!=NULL) pre->next=q; delete(hb); return(hc); } 五、应用实例 计算机软件技术基础 数据结构——线性表

57 3.1 线性表 六、顺序表和链表的比较  线性表的长度是否固定
顺序表的存储空间是静态分配的，执行期间上下界固定，适用于表长固定的场合；链表的存储空间是在执行过程中动态分配的，适用于表长不固定的场合。  线性表的主要操作是什么 顺序表是连续存放的，适用于频繁查找操作的表。链表适用于经常进行插入和删除的表。  采用的算法语言：链表要求指针类型变量。 计算机软件技术基础 数据结构——线性表

58 3.1 线性表 七、小结 1、理解线性表的基本概念 2、掌握顺序和链式存储结构 3、熟悉线性表的基本操作（会读/写算法）
4、了解循环链表、双向链表的概念 计算机软件技术基础 数据结构——线性表