《《数据结构a》第02章》由会员分享，可在线阅读，更多相关《《数据结构a》第02章（71页珍藏版）》请在金锄头文库上搜索。
1、 数据结构数据结构 Data Structures in C+Data Structures in C+第第2 2章章 线性表线性表2.1 线性表ADT 2.2 线性表的顺序表示 2.3 线性表的链接表示 2.4 多项式的算术运算2.1 2.1 线性表线性表ADTADT 线性表的定义线性表的定义线性表是n(0)个元素a0,a1,an-1 的线性 序列，记为: (a0,a1,an-1)。其中n是线性 表中元素的个数，称为线性表的长度线性表的长度； n=0时称为空表空表。ai是表中下标为i的元素（i=0,1,n-1） ，称ai是ai+1的直接前驱元素，ai+1是ai的 直接后继元素。 线性表是动态
2、数据结构动态数据结构，它的表长可以 改变。线性表线性表ADT ADT ADT LinearList 数据：数据：0个或多个元素的线性序列（a0,a1,.,an-1），其最 大允许长度为MaxListSize。 运算：运算：Create()Create()： 创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返 回false。Length()： 返回表中元素个数。Find(i,x)Find(i,x)：在x中返回表中下标为i的元素ai。若不 存在，则返回false，否则返回true。 Search(x)：若x不在表中，则返回-1，否则返回x
3、在表中的下标。 Insert(i,x)Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在 第一个元素a0前。若插入成功，则返回true，否 则返回false。 Delete(i)Delete(i)：删除元素ai。若删除成功，则返回true ，否则返回false。 Update(i,x)：将元素ai的值修改为x。若修改成功 ，则返回true，否则返回false。 Output(out)：把表送至输出流 / 插入x x 到表：（a0,a1,.,an-1）线性表类线性表类 template class LinearList LinearList public: virtual boo
4、l Find(int i,T virtual bool Insert(int i,T x)=0;virtual bool Delete(int i)=0; protected:int n;int n; /线性表的长度 ;2.2 2.2 线性表的顺序表示线性表的顺序表示2.2.1 2.2.1 顺序存储结构顺序存储结构 顺序存储表示顺序存储表示是用一组地址连续的存储单元依次存储线性 表中元素。 顺序表顺序表顺序表示的线性表称为顺序表a0 a1 ai an-1 0 1 i n-1 maxLength-1地址计算公式地址计算公式若已知顺序表中每个元素占k个存储单元，第 一个元素a0在计算机内存中的首地
5、址是 loc(a0)，则表中任意一个元素ai在内存中的 存储地址loc(ai)为 loc(aloc(ai i)=loc(a)=loc(a0 0)+i*k)+i*k随机存取结构随机存取结构只要给定loc(a0)和k，就可以确定线性表中 任意一个元素的存储地址，换句话说，顺序 表是一种随机存取结构。2.2.2 2.2.2 顺序表类顺序表类 顺序表类顺序表类 template class SeqList:public LinearListLinearList public: /公有函数SeqList(int mSize);SeqList() delete elements; bool Find(in
6、t i,T int Search(T x) const; bool Insert(int i,T x);bool Delete(int i);SingleListLinearListSeqList private:/private:/私有数据私有数据int maxLength; /顺序表的最大长度T *elements;/动态一维数组的指针 ;动态存储分配动态存储分配 构造函数，构建一个空构造函数，构建一个空线性线性表表 template SeqList:SeqList(int mSize) maxLength=mSize;elements=new TmaxLength; n=0; 析构函数，
7、撤消一个顺序表析构函数，撤消一个顺序表 template SeqList: SeqList() delete elements; 2.2.3 2.2.3 线性表运算实现线性表运算实现 搜索运算搜索运算Find(i,x):Find(i,x): 查找下标为i的元素ai。在x中返回表中下标为i的元素ai (即表中 第i+1个元素)。如果不存在，则返回false，否则返回true。x=elementsi; 渐近时间复杂度：O(1) a0 a1 ai an-1 0 1 i n-1 maxLength-1template bool SeqList:Find(int i,Tj-) elementsj+1=e
8、lementsj;elementsj+1=elementsj; elementsi+1=x;n+; return true; 删除运算删除运算Delete(i)Delete(i)： 删除元素ai。删除运算的平均时间复杂度删除运算的平均时间复杂度 分析: 设顺序表长度为n,则删除元素ai（i=0,n-1）,要 移动n-i-1元素。若删除表中每个元素的概率是相等 的，即Qi=1/n， 21)-n(n1.2)-(n1)-(n01-ni .,1n,0i=+=-=次，移动次，移动template bool SeqList:Delete(int i) / /删除元素删除元素a ai i if (!n) /
9、下溢出检查coutn-1) cout r(4 4);r.Insert(-1,x); r.Insert(-1,x); r.Output(cout); 线性表的顺序存储表示的优缺点线性表的顺序存储表示的优缺点 优点：随机存取；存储空间利用率高。 缺点：插入、删除效率低；必须按事先估计的最大元素个数分配连 续的存储空间，难以临时扩大。2.3 2.3 线性表的链接表示线性表的链接表示2.3.1 2.3.1 单链表单链表 链接存储表示链接存储表示 单链表的结点结构单链表的结点结构单链表结构单链表结构element linka0a1a2an-1first 非空单链表first空单链表 = NULL指针变量
10、的存储 单元 红色为结点的指 针域 注意事项注意事项 头指针first是指向单链表的头结点的指针 最后一个结点的指针域为，地址值为0 逻辑上相邻的元素在物理上不一定相邻 不能出现“断链”现象结点类结点类 #include “linearlist.h“ template class SingleList；/超前声明 template class Node private:T element;Node *link;friend class SingleListSingleList; ;element link单链表类单链表类 template class SingleList:public Lin
11、earListLinearList public:SingleList() first=NULL; n=0; SingleList();bool Find(int i,Tint Search(T x) const;bool Insert(int i,T x);bool Delete(int i);. private:Node* first;Node* first; ;顺序表类SeqList、单链表类SingleList是抽象线性 表类LinearList类的派生类。SingleListLinearListSeqListNodefriend构造函数SingleList() first=NULL;
12、 n=0; 析构函数析构函数template SingleList: SingleList() Node *p;while (first) p=first-link;delete first;first=p; 搜索运算搜索运算必须从头指针开始沿链逐个计数查找，称为顺顺 序查找序查找搜索运算的平均、最坏的渐近时间复杂度：搜索运算的平均、最坏的渐近时间复杂度： O(n)O(n)template bool SingleList:Find(int i,T for (int j=0; jlink;x=p-element; return true; 插入运算插入运算 修改两个指针域的值修改两个指针域的值插
13、入渐近时间复杂度：插入渐近时间复杂度：O(1)O(1)q-link=p-link; q-link=p-link;p-link=q p-link=q； 插入运算步骤插入运算步骤：生成数据域为x的新结点，q指向新结点;从first开始找第i+1个结点，p指向该结点；将q插入p之后。表长加1。template bool SingleList:Insert(int i,T x) if (in1) cout * q=new Node;q-element=x; Node *p=first;/ 找ai元素所在的结点pfor (int j=0; jlink;if(i1) q-link=p-link;/新结点q
14、插在p之后p-link=q;else q-link=first; /新结点q插在头结点之前 first=q;n+; return true; / 删除结点p是指删除指针变量p所指示的结点*p。单链表的删除单链表的删除只需修改一个指针只需修改一个指针“ “q-link=p-linkq-link=p-link” ”，但还需使，但还需使 用用“ “delete pdelete p；” ”语句回收结点占用的空间。语句回收结点占用的空间。 单链表的步骤单链表的步骤从first开始找第i+1个结点，p指向该结点，q 指向p之前驱结点;从单链表中删除p；释放p之空间；表长减1。template bool S
15、ingleList:Delete(int i) if ( !n ) coutn-1 ) cout *p=first, *q=first;for (int j=0; jlink;if (i=0) first=first-link;/ 删除头结点else p=q-link; q-link=p-link;delete p; n-;return true; 单链表运算的优缺点单链表运算的优缺点优点优点 单链表插入和删除只需修改一两个指针，无需移动 元素。如已知前驱结点，插入删除运算的时间为 O(1)可以动态分配结点空间，线性表的长度只受内存大 小限制。 缺点缺点查找运算费时，只能顺序查找，不能随机查找2.3.2 带表头结点的单链表请区分“表头结点”和“头结点” template HeaderList: HeaderList() Node *firs
