第二章 线性表数据结构电子教案殷人昆 王 宏1第二章 线性表n线性表n顺序表 n单链表n多项式n循环链表n双向链表2线性表 (Linear List)n线性表的定义v线性表是 n (0) 个数据元素的有限序列 ，记作（a1, a2, , an）ai 是表中数据元素，n 是表长度。v原则上讲，线性表中表元素的数据类型 可以不相同。但采用的存储表示可能会 对其有限制。v为简单起见，假定各元素类型相同。 3 线性表的特点v除第一个元素外，其他每一个元素有一 个且仅有一个直接前驱。v除最后一个元素外，其他每一个元素有 一个且仅有一个直接后继。v直接前驱和直接后继描述了结点之间的 逻辑关系（即邻接关系）。 a1a2a3a4a5a64抽象数据类型线性表的定义如下： ADT List 数据集合： D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。 数据关系： R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。 5操作集合：结构初始化操作 结构销毁操作引用型操作加工型操作 ADT List6InitList( /template class LinearList public:LinearList();/构造函数LinearList();/析构函数virtual int Size() const = 0;/求表最大体积virtual int Length() const = 0; /求表长度virtual int Search(T x) const = 0; /搜索virtual int Locate(int i) const = 0; /定位virtual T getData(int i) const = 0; /取值virtual void setData(int i, T x) = 0; /赋值 23virtual bool Insert(int i, T x) = 0; /插入virtual bool Remove(int i, T / 删除virtual bool IsEmpty() const = 0; /判表 空 virtual bool IsFull() const = 0; /判表满virtual void Sort() = 0； /排序virtual void input() = 0； /输入virtual void output() = 0； /输出virtual LinearList /复制 ;因为LinearList是抽象类，所以只能返回引用类型线性表的存储表示有两种：顺序存储方式和 链表存储方式。 24顺序表 (Sequential List) 顺序表的定义v将线性表中的元素相继存放在一个连续 的存储空间中。 v可利用一维数组描述存储结构 顺序表的特点v所有元素的逻辑先后顺序与其物理存放 顺序一致 25 34 57 16 48 09 0 1 2 3 4 5 data25顺序表的静态存储和动态存储#define maxSize 100 typedef int T; typedef struct T datamaxSize; /顺序表的静态存储表示int n; SeqList;typedef int T; typedef struct T *data; /顺序表的动态存储表示int maxSize, n; SeqList;26结点的变体（异质数据）结点的变体（异质数据）n若想在线性表中存放不同类型的数据，可采 用等价定义union：typedef union int val; /按data.val引用char ch; /按data.ch引用float dir; /按data.dir引用union data *link; /按data.link引用 data; /整体上是同一类型data 25 s 3.3 62 74 t 1.0 6 27顺序表(SeqList)类的定义#include /定义在 “seqList.h”中 #include #include “LinearList.h“ const int defaultSize = 100; typedef int T;/template class SeqList: public LinearList protected:T *data; /存放数组int maxSize; /最大可容纳表项的项数int n; /当前已存表项数void reSize(int newSize);/改变数组空间 大小28public:SeqList(int sz = defaultSize); /构造函数SeqList(SeqList /复制构造函数SeqList() delete data; /析构函数int Size() const return maxSize; /求表最大容量int Length() const return n; /计算表长度int Search(T x) const;/搜索x在表中位置，函数返回表项序号int Locate(int i) const; /定位第 i 个表项，函数返回表项序号bool Insert(int i, T x);/插入bool Remove(int i, T/删除T getData(int i) const ; /取值 void setData(int i, T x); /赋值 ; 应用29顺序表的构造函数#include /操作“exit”存放在此 #include “seqList.h” /操作实现放在 “seqList.cpp” typedef int T; /template SeqList:SeqList(int sz) if (sz 0) maxSize = sz; n = 0;data = new TmaxSize; /创建表存储数组if (data = NULL) /动态分配失败 cerr SeqList:SeqList ( SeqList n = L.Length();data = new TmaxSize;/创建存储数组if (data = NULL)/动态分配失败cerr , 表的长度增加3621 18 30 75 42 56 8721 18 30 75例如： item=66; Insert ( i,x)n1jjji87564266for(j = n ; j =i ; j -)dataj=dataj-1;datai-1=x;/在i（下标为i-1）插入xn+;/数据元素个数n加1 j37表项的插入算法/template bool SeqList:Insert (int i, T x) /将新元素x插入到表中第i (1in+1) 个表项位 /置。函数返回插入成功的信息if (n = maxSize) return false; /表满if (i n+1) return false; /参数i不合理for (int j = n; j = i; j-) /依次后移dataj = dataj-1; datai-1 = x; /插入(第 i 表项在datai -1处)n+; return true; /插入成功 ; 38插入算法的性能分析n在表中第 i 个位置插入，从datai-1 到 data n-1 成块后移，移动n-1-(i-1)+1 = n-i+1项。n考虑所有插入位置，相等插入概率时，从 1 到 n+1，平均移动元素个数为:39线性表操作bool SeqList:Remove (int i,T/要删除的元素 for(int j = i ; j bool SeqList:Remove (int i,T /表空if (i n) return false; /参数i不合理x = datai-1; for (int j = i; j link = first ; first = newnode;（插入前插入前） （插入后插入后）firstnewnodenewnode first58( (插入前插入前) () (插入后插入后) )u 第二种情况：在链表中间插入newnode-link = current-link;current-link = newnode；newnode currentnewnodecurrent59uu 第三种情况：在链表末尾插入newnode-link = current-link;current-link = newnode；( (插入前插入前) () (插入后插入后) )newnodenewnode currentcurrent60单链表的插入算法bool List:Insert(int i, int x) /将新元素 x 插入到第 i 个结点之后。i 从1开始， /i = 0 表示插入到首元结点之前。if (first = NULL | i = 0) /空表或首元结 点前LinkNode *newNode = new LinkNode(x);/建立一个新结点newNode-link = first; first = newNode;/新结点成为首元结点 else /否则，寻找插入位置LinkNode *current = first; int k = 1; 61while (k link; k+; if (current = NULL current-link = newNode; return true; ;62n删除u第一种情况: 删除表中第一个元素u第二种情况: 删除表中或表尾元素在单链表中删除含a ai i的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后q = p-link; /删中间/尾结点 p-link = q-link;63单链表的删除算法bool List:Remove (int i, int/暂存删除结点指针 if (i link; else LinkNode *current = first; k = 1; /找i-1号结 点while (k link; k+; if