第二部分 数据结构—— 用面向对象方法与C++描述.

Presentation on theme: "第二部分 数据结构—— 用面向对象方法与C++描述."— Presentation transcript:

1 第二部分 数据结构—— 用面向对象方法与C++描述

2 第7章 数据结构概述与线性表

3 本章主要内容 数据结构绪论 线性表的基本概念 抽象链表类 单链表

4 7.1 数据结构绪论 什么是数据结构 基本概念和术语 抽象数据类型 算法和算法分析

5 （一）数值计算的程序设计问题 1、结构静力分析计算 ─━ 线性代数方程组 2、全球天气预报 ─━ 环流模式方程 (球面坐标系)

6 （二）非数值计算的程序设计问题 1、求一组(n个)整数中的最大值 2、计算机对弈 算法？ 基本操作是“比较两个数的大小” 模型？
取决于整数值的范围 2、计算机对弈 对弈的规则和策略 算法? 模型? 棋盘及棋盘的格局

7 一、什么是数据结构 Algorithm + Data Structures = Programs （算法） （数据结构） （ 程序）
（算法） （数据结构） （ 程序） 程序设计: 算 法: 数据结构: 为计算机处理问题编制一组指令集 处理问题的策略 问题的数学模型 数据结构所研究的问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。

8 一、什么是数据结构 数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。
1968年，美国的 D.E.Knuth (唐.欧.克努特)教授开创了数据结构的最初体系，他的名著《计算机程序设计技巧》较为系统地阐述了数据的逻辑结构和存储结构及其操作。

9 二、基本概念和术语 数据(data)：客观对象的符号表示。
数据元素(data element)：数据的基本单位，在计算机程序中通常作为一个整体考虑和处理，通常具有完整确定的实际意义。（节点、顶点、记录） 数据项(data item)：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。（字段） 编号 姓名 性别 出生年月 职称 0001 刘建国 男 工程师 0002 黄 红 女 助工 0003 张 华 高工 …

10 二、基本概念和术语 数据结构(data structure)：具有相同特征的数据元素的集合，如果在这些数据元素之间存在一种或多种特定的关系，则称为一种数据结构。 数据结构：带有结构和操作的数据元素集合。 结构：数据元素之间的关系； 操作：对数据的加工处理 。 对每种数据结构，主要讨论如下两方面的问题： 1) 数据的逻辑结构，数据结构的基本操作 2) 数据的存储结构，数据结构基本操作的实现。

11 二、基本概念和术语 数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。 数据元素之间存在四种基本结构 集合（无关系） 线性结构（一对一）
树形结构（一对多） 图状结构（多对多）

12 二、基本概念和术语 线性结构 除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。 学生间 学号顺序关系
学号 姓名 专业 政治面貌 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员 学生间 学号顺序关系 是一种线性结构关系 001 003 002 004 006 005 008 007

13 二、基本概念和术语 树形结构 每一个元素只有一个直接前趋，有0个或多个直接后继。 J I A C B D H G F E 家族树（家谱）

14 二、基本概念和术语 图形结构 每一个元素可以有0个或多个直接前趋，有0个或多个直接后继。 工程进度图 V1 V0 V3 V4 V5 V6

15 二、基本概念和术语 数据结构的表示 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系。 二元组表示
二元组表示是用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。

16 二、基本概念和术语 例：学生基本情况表的二元组表示（D，S） D = { 001，002，003，004，005，006，007，008 }
S = { R } R = { <001,002>, <002,003>, <003,004>, <004,005>, <005,006>, <006,007>, <007,008> }

17 二、基本概念和术语 数据的存储结构：逻辑结构在计算机中的表示。 常见的存储结构
顺序存储结构 链式存储结构 散列结构 索引结构 注意：算法的设计取决于所选定的逻辑结构， 算法的实现则依赖于采用的存储结构。

18 二、基本概念和术语 顺序存储结构： 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系（一维数组描述）。
顺序存储结构： 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系（一维数组描述）。 存储地址 存储内容 元素1 L０ 元素2 L０+m …….. 元素i L０+(i-1)*m …….. 元素n L０+(n-1)*m Loc(元素i) = L０ +（i-1) * m

19 二、基本概念和术语 链式存储结构：借助指示元素存储地址的指针 来表示数据元素之间的逻辑关 系（指针类型描述）。 h 1345 元素1
链式存储结构：借助指示元素存储地址的指针 来表示数据元素之间的逻辑关 系（指针类型描述）。 1345 h 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3

20 三、抽象数据类型 1、数据类型：是一个值的集合和定义在此集合上的一组操作的总称。
在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 整型 int 浮点型 float 实型（ C++语言） 双精度型 double 字符型 char 逻辑型 bool （ C++语言）

21 三、抽象数据类型 2、抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数据类型可用（D，S，P）三元组表示。其中：
S 是 D 上的关系集； P 是对 D 的基本操作集。

22 三、抽象数据类型 3、抽象数据类型 有两个重要特征:
1）数据抽象： 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 2）数据封装：

23 四、算法与算法分析 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有穷性、确定性、可行性、有输入和有输出。 有穷性：算法必须在有限步内结束。 确定性：算法的操作清晰无二义性。 可行性：算法的操作必须能够实现。 有输入：有0个或多个输入。 有输出：有1个或多个输出。

24 四、算法与算法分析 评价算法的标准 正确性，可读性，可维护性，健壮性，效率。 算法效率的度量 算法的时间复杂度：算法的时间效率
算法的空间复杂度：算法的空间效率

25 小 结 什么是数据结构 基本概念和术语 抽象数据类型 算法和算法分析

26 数据的运算：检索、排序、插入、删除、修改等
小 结 数据结构的三个方面： 线性表 栈 线性结构 队 数据的逻辑结构 树形结构 非线性结构 图形结构 顺序存储结构 数据的存储结构 链式存储结构 数据的运算：检索、排序、插入、删除、修改等

27 7.2 线性表的基本概念 线性表的逻辑结构 线性表的顺序存储表示 线性表的链式存储表示

28 线性表是n(>=0)个数据元素a1, a2 , … , an-1 , an的有序集合。
线性表的逻辑结构 线性表是n(>=0)个数据元素a1, a2 , … , an-1 , an的有序集合。 元素ai在表中的位置仅取决于元素本身的序号i。当1 < i < n时，ai的直接前驱为ai-1，ai的直接后继为ai+1。 除第一个元素a1与最后一个元素an外，其他每个元素ai有且仅有一个直接前驱和一个直接后继；第一个元素a1仅有一个直接后继，最后一个元素an仅有一个直接前驱。

29 可见，线性表的数据元素之间存在一对一的关系，属于线性结构。
线性表的逻辑结构 可见，线性表的数据元素之间存在一对一的关系，属于线性结构。   一个线性表可以用一个标识符来命名。例如： L = ( a1, a2, a3 , … , an-1 , an ) 注意：同一线性表中的元素必定具有相同的特性，都属于同一数据类型。

30 线性表中的数据元素在不同情况下可能有不同的具体含义。
线性表的逻辑结构 线性表中的数据元素在不同情况下可能有不同的具体含义。 如 L1＝ ( 1.2，-2.3，56，0，45.7 ) L2＝ ( ’a’，’d’，’c’，’g’，’j’，’l’ )   在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成。

31 线性表的逻辑结构 例如：学生名册： 黎 明 男 王 烟 18 女 曲 柳 17 女 何旦 旦 19 男 李 美 16 女

32 在计算机内部可以采用两种不同方法来表示一个线性表，它们分别是顺序表表示法和链表表示法。
线性表的顺序存储方式 在计算机内部可以采用两种不同方法来表示一个线性表，它们分别是顺序表表示法和链表表示法。 顺序表示法的定义； 元素的地址表示； 顺序表示法的优、缺点。

33 顺序表示法用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构称为线性表的顺序存储结构，并称此时的线性表为顺序表。
顺序表示法的定义 顺序表示法用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构称为线性表的顺序存储结构，并称此时的线性表为顺序表。

34 线性表的顺序表示 顺序映象 —— 以 x 和 y 存储位置之间的某种关系来表示x 和 y的逻辑关系<x, y>。 最简单的一种顺序映象方法是： 令 y 和 x 的存储位置相邻。

35 用一组地址连续的存储单元 依次存放线性表中的数据元素 a1 a2 … ai-1 ai … an 线性表的起始地址 称作线性表的基地址

36 以“存储位置相邻”表示有序对<ai-1，ai> 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量↑
所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址

37 线性表的顺序存储结构示意图 逻辑地址 数据元素 存储地址 k0 Loc(k0) 1 k1 Loc(k0)+c … i ki
k0 Loc(k0) 1 k1 Loc(k0)+c … i ki Loc(k0)+i*c n-1 kn-1 Loc(k0)+(n-1)*c

38 元素的地址表示 假设线性表的每个元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i+1个数据元素ai+1的存储位置与第i个数据元素ai的存储位置之间满足如下关系： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a0)+i*C LOC(a0)为线性表的首地址或基地址。

39 以元素在计算机内存中的“物理位置相邻” 来表示线性表中数据元素之间的逻辑关系， 只要确定了首地址，线性表中任意数据元 素都可以随机存取。

40 2）逻辑位置相邻的数据元素，其物理位置也相邻。可随机存取，所以称为随机存取结构。
顺序表示法的优缺点 优点： 1）存储密度大、空间利用率高； 2）逻辑位置相邻的数据元素，其物理位置也相邻。可随机存取，所以称为随机存取结构。 缺点： 1）插入和删除时要移动大量的元素； 2）长度较大的线性表须按所需的最大存储空间来分配。

41 线性表的链式存储表示 链式存储表示的定义 链式存储表示的实现 链式存储表示的特点

42 用一组地址任意的存储单元存放线性表中的数据元素
线性表的链式表示 用一组地址任意的存储单元存放线性表中的数据元素 以元素(数据元素的映象) + 指针(指示后继元素存储位置) 组成结点 (表示数据元素 或 数据元素的映象) 以“结点的序列”表示线性表  称作链表

43 结点：数据元素的存储映象，由数据域和指针域构成
a1 a2 a3 a4 a5 a6 an ^ …… 设ai的存储位置为p，则ai+1的地址q是：q = p ->link;

44 链式存储方式 链表：是用一组地址任意的存储单元存放线性表的各个数据元素，通过保存直接后继的存储位置来表示元素之间的逻辑关系；
 链式存储结构不要求逻辑上相邻的数据元素在物 理位置上也相邻； 链表：是用一组地址任意的存储单元存放线性表的各个数据元素，通过保存直接后继的存储位置来表示元素之间的逻辑关系； 所有的数据元素都分别保存在具有相同数据结构的结点中,结点是链表的基本存储单位,结点与数据元素一一对应； 每个结点在链表中使用一块连续的存储空间,而相邻结点之间不必使用连续的存储空间。

45 链式存储表示的特点 逻辑上相邻的元素对应的存储位置是通过指针反映的，不要求物理上相邻。进行插入、删除运算时，只需修改被插入位置指针域。
一般不需要预先分配存储空间，当有元素插入时，可临时分配一个空的结点空间，填上信息，插入到线性链表中；当某个结点不再使用时，应将其占用的存储空间释放。 不足之处：每个结点设有一个指针域，存储空间的开销较大；不能实现随机存取。

46 抽象链表类 线性链表的实现 抽象链表类的定义 抽象链表类中典型成员函数的实现

47 数据元素的存储结构－－结点 结点 (表示 数据元素的映象) = 元素 + 指针(指示后继元素的存储位置) 7.3.1 链式存储的实现 结点
ai 数据域 data 指针域 next 如果结点中只包含一个指针域，称为单链表

48 链表结点与组成 链表是动态数据结构，通过指针（链）将结点链接在一起。结点包括两部分：数据信息和链接结点的指针；结点分为表头结点和表结点；
指向链表表头结点的指针(表头指针，也称为头指针)； 表头结点(链表的第一个结点)，一般不存放数据元素的信息； 表结点（数据结点，也称为结点，保存数据信息）。

49 表头指针：存放线性链表中第一个结点的存储地址； 空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针；
线性链表的相关术语 表头指针：存放线性链表中第一个结点的存储地址； 空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针； 表头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。 带表头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表。

50 链表的图示 NULL 表头指针 表头结点 数据结点

51 链表结点类的定义 template <class type> class ListNode{ public:
ListNode( ) {next = Null;}//无参数，构造一个空结点 ListNode(const type &item, ListNode<type> *next1=NULL) //带参数，构造一个非空结点 { data=item; next=next1;} //包含数据域和指针域 type data; //结点的数据域 ListNode <type> *next; //结点的指针域 }; data next

52 链表的常用操作 求链表的长度； 寻找第i个数据元素； 根据关键字值求数据元素在链表中的位置； 插入数据元素； 修改数据元素的值；
获取表头指针； 求链表的长度； 寻找第i个数据元素； 根据关键字值求数据元素在链表中的位置； 插入数据元素； 修改数据元素的值； 删除数据元素。

53 线性链表有3种：单链表、循环链表与双向链表；
抽象链表类的定义 线性链表有3种：单链表、循环链表与双向链表； 抽象出上述三种线性链表的相同点（结点、指针和相同操作），建立一个抽象链表，再由此抽象链表类派生出新的链表类（单链表和循环链表）； 采用类模板机制； 增加表头结点，统一空表和非空表的操作。

54 抽象链表类定义 template<class type> //抽象类链表的定义 class ablist {public:
ListNode<type>*GetHead( ) //获得表头结点指针 { return head; } //取出链表中的第i个元素 type Get(int i); //将链表中第i个结点元素值设置为x Bool Set(type x, int i); //寻找数据元素值为value的结点地址 ListNode<type>*Find1(type value); //寻找链表中第i个结点元素的地址 ListNode<type>*Find(int i);

55 protected: //链表的数据成员：头指针和表长
void MakeEmpt( ); //将链表置为空表 //取得结点n的下一个结点位置 virtual ListNode<type> *GetNext (ListNode<type>&n)=0; //纯虚函数，将新元素value插入到第i个位置 virtual int Insert(type value, int i)=0; //纯虚函数，将新元素value插入到链表表头处 virtual int Insert(type value)=0; //纯虚函数，将链表中第i个结点删去 virtual int Remove(int i)=0; //纯虚函数，将元素值为value的结点删去 virtual int Remove(type value)=0; protected: //链表的数据成员：头指针和表长 ListNode<type> *head; int length; };

56 设置函数：将第i个结点数据元素值设为x。
抽象链表成员函数的实现 设置函数：将第i个结点数据元素值设为x。 template<class type> bool ablist<type>::Set(type x, int i) { ListNode<type> *p = Find(i); //寻找第i个结点位置 if(p==NULL||p==head) //i值不合法或为空表，返回false return false; else p->data=x; //修改第i个结点的数据元素值 return ture; }

57 取值函数：返回第i个结点的数据元素值。 template<class type> type ablist<type>::Get(int i) { //寻找指向第i个结点位置的指针 ListNode<type> *p=Find(i); assert (p && p!=head); //断言：p不空也不为表头 return p->data; //返回第i个结点的数据元素值 }

58 清空链表：用q指向第一个结点，当链表不空时，循链逐个删除，仅保留表头结点。
template<class type> void ablist<type>::MakeEmpty() { ListNode<type> *q=head->next; int i=1; //链表不空，所以至少有一个结点 while(i++ <= length) //当链表不空时，删去表中所有结点 { head->next=q->next; delete q; //循链逐个删除，仅保留表头结点 q=head->next; } length=0;

59 搜索数据元素值为value的结点 template<class type>
ListNode<type>*ablist<type>::Find1(type value) { ListNode<type> *p=head->next; int i=1; //循环条件包含空链表的情况 while (i++ <= length && p->data!=value) p=p->next; //循链找数据元素值value的结点 return p; }

60 定位函数：返回链表中第i个元素结点的地址
template<class type> ListNode<type>*ablist<type>::Find(int i) { if(i<0 || i>length) return NULL; if(i==0) return head; //i=0时返回表头结点的地址 ListNode<type>*p=head->next; //让检测指针p指向表 中第1个结点 int j=1; while(p!=NULL && j<i) //循链扫描，至第i个结点地址 { p=p->next; j++; } return p; //返回第i个结点地址

61 单链表 单链表的定义 单链表类 单链表常用成员函数的实现 单链表举例：一元多项式加法

62 7.4.1 单链表的定义 线性表的n个数据元素对应的n个结点通过链接方式链接成一个链表，每个结点由数据域和指针域组成。
单链表的定义 线性表的n个数据元素对应的n个结点通过链接方式链接成一个链表，每个结点由数据域和指针域组成。 每个结点中只有一个指针域的链表，就称为单链表。 ai-1 ai a2 a1 ai+1 n an head

63 带头结点的单向链表 L L 怎样判断带头结点的单向链表是否为空表？ 如果：L->next == NULL 成立，则 L 为空表。
ai-1 ai a2 a1 ai+1 n an L n L 空表 怎样判断带头结点的单向链表是否为空表？ 如果：L->next == NULL 成立，则 L 为空表。 反之： 如果：L->next != NULL 成立，则 L 不是空表。

64 不带头结点的单向链表 L L 怎样判断不带头结点的单向链表是否为空表？ 如果：L == NULL 成立，则 L 为空表。 反之：
ai-1 ai a2 a1 ai+1 n an L NULL L 空表：L=NULL 怎样判断不带头结点的单向链表是否为空表？ 如果：L == NULL 成立，则 L 为空表。 反之： 如果：L != NULL 成立，则 L 不是空表。

65 结点之间的基本关系 p q r s 则下列关系成立： p->next == q r->next == s == q->
a2 a2 a4 a5 则下列关系成立： p->next == q r->next == s == q-> next->next == p-> next->next->next 通过当前结点 p 要访问下一个结点，则指向下一个结点的指针为： p->next 通过当前结点 p 要访问下一个结点的下一个： p->next->next

66 7.4.2 单链表类的定义 { MakeEmpty( ); delete head; } //将链表置空 从抽象链表类派生：
单链表类的定义 从抽象链表类派生： class List：public ablist <type> { public： List（） //构造函数，建立一个空链表 { head = new ListNode <type>；length = 0；} //构造函数，用于通过一个现有链表建立新链表 List（List <type> & l） { Copy（l）；} ~List（） //析构函数 { MakeEmpty( ); delete head; } //将链表置空

67 //将新元素插入在链表中第i个位置 bool Insert(type value, int i); type Remove(int i); //将链表中第i个结点删去 type Remove1(type value); //删去表中值为value的结点 //取得结点n的下一个结点位置 ListNode<type> *GetNext(ListNode<type> & n); List <type> & Copy(List <type> & l); //拷贝函数 //重载赋值运算符, 同类型链表赋值 List <type> & operator =(List <type> & l); //重载输出运算符 friend ostream & operator <<(ostream &, List <type> &); }; //class List

68 单链表常用成员函数实现 在第i个位置插入一个新结点 删除链表指定位置i处的结点 删除数据元素为value的结点 拷贝链表 取得结点n的下一个位置 重载赋值运算符* 重载输出运算符*

69 在单链表第i个位置插入一个新结点 基本原理: 寻找插入点的前一个位置i-1; 若为空表，应将表尾指针指向新结点; 从内存中申请一个新的空结点，将数据信息置于新结点的数据域内; 修改指针插入新结点。

70 在单链表第i个位置插入一个新结点 L L 主要步骤 p 指向第i-1个元素结点 q 指向新结点 e 修改指针插入新结点 p ×
ai-1 ai a1 ai+1 n an L p × q->next=p->next; e q p->next=q; ai-1 ai a1 ai+1 n an L p e q

71 template<class type>
bool List<type>::Insert(type value，int i) { ListNode<type> *p=Find(i-1); //定位插入点的前一位置 if(p==NULL) return false; //i值不合理，返回false //创建新元素结点 ListNode<type> *q= new ListNode<type> (value,q->next); assert(q); q->next=p->next; //链接后面指针 p->next=q; //链接前面指针 length++; return true; }

72 基本原理 删除指定位置i处的结点 利用Find(i-1)函数找到第i-1个元素结点； 保留被删结点的数据值，重新拉链(摘链)；
若被删结点为表尾结点时，修改表尾指针; 最后应释放被删结点的内存空间; 将链表长度减1。

73 删除指定位置i处的结点 L L 主要步骤 p 指向第 i-1 个元素结点，q指向被删除结点 修改指针删除第 i 个元素结点 回收被删除结点
ai-1 ai a1 ai+1 n an L p × q q = p->next; ai-1 a1 ai+1 n an L p p->next=q->next;

74 template<class type>
type List<type>::Remove(int i) { //p定位于第i-1个元素结点 ListNode<type> *p=Find(i-1), *q; assert(p && p->next); //p不为空且不为最后一个元素地址 q=p->next; //q指向将被删除的元素 p->next=q->next; //重新链接（摘链） type value=q->data; //保留被删除结点的数据值 delete q; //释放被删结点的空间 length--; return value; }

75 删除元素值为value的结点 基本原理 循链寻找数据值为value的前一结点； 若已至表尾，且其值不为value，返回NULL；
否则，重新拉链，将此结点断开（摘链）； 若被删结点为表尾结点时，应修改表尾指针； 回收被删结点的内存空间，将链表长度减1。

76 template<class type>
type List<type>::Remove1(type value) { ListNode<type> *q，*p=head; //循链寻找数据值为value的前一结点 while(p->next!=NULL && p->next->data!=value) p=p->next; assert(p->next); //p不是表尾，继续 q=p->next; //q指向将删除的元素 p->next=q->next; //重新接链，删除此结点 delete q; length--; return value; }

77 7.4.4 线性表的应用实例 一元多项式的表示及相加 可用线性表P表示 但对S(x)多项式浪费空间 一般 其中
用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表

78 7.4.4 线性表的应用实例 单链表的结点定义 next coef exp -1 A 7 0 3 1 9 2 5 17 ^ -1 B 8 1
^ -1 B 22 7 ^ -1 C 9 2 22 7 ^

79 7.4.4 线性表的应用实例 运算规则 假设：p,q分别指向A,B中某一结点，p,q初值是第一结点，结果放入A链中。
-1 A ^ 假设：p,q分别指向A,B中某一结点，p,q初值是第一结点，结果放入A链中。 运算规则 -1 B 22 7 ^ p->exp < q->exp: p结点是和多项式中的一项 　　　　　　 p后移，q不动 比较 p->exp与 q->exp p->exp > q->exp: q结点是和多项式中的一项 　　　　　　 将q插在p之前，q后移，p不动 =0：从A表中删去p, 释放p,q，p,q后移 p->exp = q->exp: 系数相加 0：修改p系数域, 释放q，p,q后移 若q==NULL，结束 直到p或q为NULL 若p==NULL，将B中剩余部分连到A上

80 第7章 总结 1、数据结构研究的主要内容包括：数据的逻辑结构、物理结构（存储结构）以及在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理。 2、线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 3、熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。