2.1 线性表的概念 (逻辑结构及其基本操作)2.2 线性表的存储结构
(顺序表与链表)2.3 线性表的操作算法顺序表的操作算法、链表的操作算法2.4 线性表的应用2.1. 线性表的概念
（逻辑结构及其基本操作）1.定义： 线性表L是n(n>=0)个相同类型数据元素a1, …，an-1 , an构成的有限序列。
表示成:L= (a1, …，an-1 , an ) 形式化定义：Linearlist = (D, R)其中：D0为某个数据对象
的集合n为线性表长度例如：26英文字母表(A,B,C,……,X,Y,Z)、一个班级的学生成绩报表等 表长--线性表中元素的个数直接
前驱--线性表中ai-1领先于ai，则ai-1是ai的直接前驱元素直接后继--线性表中ai领先于ai+1，则ai+1是ai的直接后
继元素2. 线性表的主要操作1、建立一个空的线性表 ??2、求线性表中元素个数 ??3、判断线性表L是否为空 ??4、取线性表L
中第i个元素 ??5、在线性表中插入某元素 ??6、在线性表中删除某元素 ??7、求线性表中某元素的前驱元素 ??8、求线性表中某
元素的后继元素 ??9、在线性表中查找某元素 ??10、两个线性表进行合并 2.2 线性表的存储结构 有两种存储结构：
顺序存储—顺序表(数组) 链式存储－链表1.线性表的顺序存储结构--顺序表 设线性表的基地址为：LOC(a1),ai的存
储地址为： LOC(ai) = LOC(a0)＋ik 1<=i<=na0a1aian-1……a0a1aia
n-1……01n-1Loc(a0)Loc(a0)+kiLoc(a0)+ikLoc(a0)+(n-1)k顺序表的类定义:由于线性
表的数据元素类型可以是任意的，所以可采用C++模板机制。 template clas
s SeqList{ T data[MaxSize]; //用于存放数据元素的数组 int length;
//顺序表中元素的个数public: SeqList( );
//无参构造函数 SeqList(T a[ ], int n); //有参构造函数 int ListL
ength(); //求线性表的长度 T Get(int pos); //按位查找
，取顺序表的第pos个元素 int Locate(T item); //按值查找，求顺序表中值为item的元素序号
void PrintSeqList(); //遍历顺序表，按序号依次输出各元素 void Insert(int
i, T item); //在顺序表中第i个位置插入值为item的元素 T Delete(int i);
//删除顺序表的第i个元素};2. 线性表的链式存储----链表单链表循环链表双向链表单链表 (思考:头节点的作用)hh
不带头节点的链表带头节点的链表单链表结点的定义： template struct Node {
T data; Node next; };?节点的申请 p＝new Node;节
点的释放 delete p;单链表在C++中的类模板 template class LinkList{
Node head; //单链表的头指针public: LinkList( );
//建立带头结点的空链表 LinkList(T a[ ], int n); //建立有n个
元素的单链表 ~LinkList(); //析构函数 int ListLength()
; //求单链表的长度 T Get(int pos); //按位查找 int L
ocate(T item); //按值查找 void PrintLinkList( ); //遍历单
链表 void Insert(int i, T item); //在第i个位置插入 T Delete(int i)
; //删除第i个结点};循环链表 双向链表 (双向循环链表) 2.3 线性表的操作算法 顺序
表的操作算法 链表的操作算法 1. 顺序表的操作算法 (1)无参构造函数 template t MaxSize> SeqList:: SeqList( ) { length=0; }
（2）有参构造函数 数组?顺序表template SeqList axSize>:: SeqList(T a[ ], int n){ if (n>MaxSize) {cerr<< "参数非法
";exit(1);} for (i=0; i ;}（3）求顺序表的长度 template int SeqList >::ListLength(){ return length; }（4）按位查找 template t MaxSize> T SeqList::Get(int pos){ if (pos<1 || p
os>length) {cerr<< "查找位置非法"; exit(1);} else return data[p
os-1];}（5）按值查找 template int SeqList ze>::Locate(T item){ for (int i=0; i ta[i]==item) return i+1 ; return 0; }（6）遍历（打印）顺序表
template void SeqList::PrintSeq
List(){ for (int i=0;i mplate void SeqList::Insert(int
i, T item){ if (length>=MaxSize) {cerr<< "上溢"; exit(1);} if (
i<1 || i>length+1) {cerr<< "插入位置非法"; exit(1);} for (j=len
gth; j>=i-1; j--) data[j+1]=data[j]; data[i-1]=item;
length++;}时间复杂性分析（8） 删除 template T SeqList , MaxSize>::Delete(int i){ if (length==0) {cerr<<"下溢"; exit(
1);} if (i<1 || i>length) {cerr<<"删除位置非法"; exit(1);} x=
data[i-1]; for (j=i; j gth--; return x;}时间复杂性分析补充: 两个有序顺序表合并例:A=(3,5,8,9,20,25)B=(2,6,9,
12,16,22,30,45)算法:1、 插入 O( n)2、删除 O(n)3、按序号检索 O(1
)4、按数据检索 O( n)顺序表算法复杂性分析 2. 链表的操作算法 (9
)单链表的无参构造函数 template LinkList:: LinkLis
t( ) { head=new Node; head->next=NULL; }?? (10)单链表的有
参构造函数 template LinkList:: LinkList(T a[ ], int n){
head=new Node; //生成头结点 r=head; for (i=0;
i; s->data=a[i]; r->next=s; r=s;
} r->next=NULL; } (11) 求单链表
长度template int LinkList::ListLength( ){ num=0;
p = head->next; while (p) { p = p->next; num++;
} return num;} (12) 单链表的按位查找 template T LinkL
ist::Get(int pos) { p=head->next; j=1; while (p
&& jnext; j++; } if (!p) {cerr<<"查找位置非
法"; exit(1);} else return p->data;}(13) 单链表的按值查找 template ss T> int LinkList::Locate(T item){ p=head->next; j=1; while (
p&&p->data!=item) { p=p->next; j++; } if (p) return j; e
lse return 0;}(14) 遍历单链表 template void LinkList:
:PrintLinkList( ){ p=head->next; while (p) { cout<data; p
=p->next; }}(15) 单链表的插入 template void LinkList::Ins
ert(int i, T item){ p=head ; j=0; while (p && j 结点的位置 { p=p->next; j++; } if (!p) {cerr<<"插入位置非法"; exit(1
);} else { s=new Node; s->data=item; s->nex
t=p->next; p->next=s; }}(16) 单链表的删除 template T Link
List::Delete(int i){ p=head ; j=0; while (p && j 第i-1个结点 { p=p->next; j++; } if (!p || !p->next) {cerr
<<"删除位置非法"; exit(1);} else { q=p->next; x=q->data; p->next
=q->next; delete q; return x; }}(17) 单链表的析构函数 template lass T>LinkList:: ~LinkList( ){ p=head; while (p) { q=p; p=
p->next; delete q; } head=NULL;}(18) 逆置单链表 template voi
d LinkList::Invert(){ p=head->next; head->next=NULL; while (p
!=NULL) { q=p; p=p->next; q->next=head->next; head->
next=q; }}(19) 合并有序单链表 void Merge(LinkList &L1, LinkList &L2)
//声明为LinkList的友元 { p1=L1.head->next; p2=L2.head->next;
p3=L1.head; while ((p1!=NULL)&&(p2!=NULL)) { //p3指向结果有序单链
表的表尾 if ((p1->data)<(p2->data)) { p3->next=p1; p1=p1->next;
p3=p3->next; } else { p3->next=p2; p2=p2->next;
p3=p3->next; } } if (p1!=NULL) p3->next=p1; if (p2!=N
ULL) p3->next=p2; delete L2.head; L2.head=NULL;}双向链表的操作 插
入操作 删除操作 2.4 线性表的应用1. 求集合的并集2. 一元多项式相加1. 求集合的并集template ,int MaxSize> //定义类模板SeqSetclass SeqSet{public: SeqSet( );
//无参构造函数 SeqSet(T a[], int n); //有参构造函数
void Union(SeqSet &set); //求并集 void Print(); /
/输出集合各元素private: T data[MaxSize]; //存放数据元素的数组 int leng
th; //集合的长度 int Locate(T item); void Insert(int
i, T item);};template void SeqSet >::Union(SeqSet &set){ int i; for (i=0;i ate(set.data[i])==0) Insert(length,set.data[i]);}2. 一元多项式相加一元多项
式单链表的结点结构struct PolyNode { float coef; //系数域 int exp; //指数域 PolyNode next; //指针域 };具体实现算法见教材P31-32 2.5 顺序表和单链表的比较（1）顺序表 优点: 随机存取; 存储空间利用率高 缺点: 插入、删除需移动元素 （2）链表： 优点: 插入、删除不需移动元素 缺点: 不能随机存取; 存储空间利用率不高 循环链表的操作与单链表的差别： 循环链表的操作与单链表基本一致，差别仅在于:算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。 本 章 小 结线性表的存储结构分为顺序存储和链式存储，分别称为顺序表和链表。本章学习要点如下：（1）线性表的基本概念。（2）顺序表的定义及操作算法。（3）链表的定义及操作算法。 |
|
