1、 Department of Computer Science&Technology,Nanjing University fall 2008DATA STRUCTURES1第第2章章 线性表线性表n线性表线性表n顺序表顺序表 n单链表单链表n循环链表循环链表n双向链表双向链表n多项式多项式 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESn线性表的定义线性表的定义p线性表是线性表是 n(0)个数据元素的有限序列个数据元素的有限序列 （a1,a2,an）ai 是表中数据元素，是表中数
2、据元素，n 是表长度。是表长度。p原则上讲，线性表中表元素的数据类型可以不原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。相同。但采用的存储表示可能会对其有限制。p为简单起见，假定各元素类型相同。为简单起见，假定各元素类型相同。2.1 线性表线性表(Linear List)Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES直接前驱和直接后继描述了结点之间的逻辑关系直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）（即邻接关系）a1a2a3a4a5a
3、6n线性表的特点线性表的特点p除第一个元素外，其他每一个元素有一个且除第一个元素外，其他每一个元素有一个且仅有一个仅有一个直接前驱直接前驱。p除最后一个元素外，其他每一个元素有一个除最后一个元素外，其他每一个元素有一个且仅有一个且仅有一个直接后继直接后继。Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES线性表的抽象基类(ADT)template class LinearList public:LinearList();/构造函数构造函数 LinearList();/析构函数析构函数
4、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 E*getData(int i)const=0;/取值取值 virtual void setData(int i,E x)=0;/赋值赋值 Department of Computer Science&Technology,Nanjing University fallDAT
5、A STRUCTURES virtual bool Insert(int i,E x)=0;/插入插入 virtual bool Remove(int i,E&x)=0;/删除删除 virtual bool IsEmpty()const=0;/判表空判表空 virtual bool IsFull()const=0;/判表满判表满 virtual void Sort()=0；/排序排序 virtual void input()=0；/输入输入 virtual void output()=0；/输出输出 virtual LinearListoperator=(LinearList&L)=0;/复制
6、复制;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES25 34 57 16 48 09 0 1 2 3 4 5 data2.2 顺序表顺序表(Sequential List)n 顺序表的定义和特点：顺序表的定义和特点：p定义：顺序存储的定义：顺序存储的 n（0）个表项的有限序列个表项的有限序列（a1,a2,an）ai是表项，是表项，n是表长度。是表长度。p特点：特点：所有元素的逻辑先后顺序与其物理存放顺序所有元素的逻辑先后顺序与其物理存放顺序一致一致;可以进行顺序访问可以进行顺序访
7、问,也可以进行随机访问也可以进行随机访问 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES顺序表的静态存储和动态存储顺序表的静态存储和动态存储#define maxSize 100typedef int T;typedef struct T datamaxSize;/顺序表的静态存储表示顺序表的静态存储表示 int n;SeqList;typedef int T;typedef struct T*data;/顺序表的动态存储表示顺序表的动态存储表示 int maxSize,n;Seq
8、List;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES顺序表(SeqList)类的定义 P.46const int defaultSize=100;template class SeqList Type*data;/顺序表存储数组顺序表存储数组 int MaxSize;/最大允许长度最大允许长度 int last;/当前最后元素下标当前最后元素下标public:SeqList(int sz=defaultSize);SeqList()delete data;int Length(
9、)const return last+1;int Find(Type&x)const;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES int IsIn(Type&x);int Insert(Type&x,int i);int Remove(Type&x);int Next(Type&x);int Prior(Type&x);int IsEmpty()return last=-1;int IsFull()return last=MaxSize-1;Type Get(int i)ret
10、urn i last？NULL:datai;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES顺序表部分公共操作的实现顺序表部分公共操作的实现:template /构造函数构造函数 SeqList:SeqList(int sz)if(sz 0)MaxSize=sz;last=-1;data=new TypeMaxSize;if(data=NULL)cerr “存储分配错存储分配错”endl;Department of Computer Science&Technology,Nanjin
11、g University fallDATA STRUCTUREStemplate int SeqList:Search(Type&x)const /搜索函数：在表中从前向后顺序查找搜索函数：在表中从前向后顺序查找 x int i=0;while(i last)return-1;else return i;顺序表的搜索算法顺序表的搜索算法 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES顺序表的查找、插入和删除顺序表的查找、插入和删除n 查找：查找：int Search(Type&x)
12、主要思想：主要思想：（1）从表的第一个数据元素起，依次）从表的第一个数据元素起，依次和和x进行比较，若存在某个表项的值和进行比较，若存在某个表项的值和x相相等，则查找成功，并返回该表项的位置。等，则查找成功，并返回该表项的位置。（2）如果查遍整个顺序表，都没有找）如果查遍整个顺序表，都没有找到其值和到其值和x相等的表项，则查找不成功，相等的表项，则查找不成功，并返回并返回-1。Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESx=50 x=48 Department of Comput
13、er Science&Technology,Nanjing University fallDATA STRUCTURES查找算法分析：查找算法分析：最好：最好：最坏：最坏：平均：平均：212)(11)2(111)(1=10nnnnnninACNni 1n*O(n)相等概率相等概率 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESn 插入：插入：int Insert(Type&x,int i)25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入 x2
14、5 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data50i Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES插入的主要思想：插入的主要思想：（1）检查插入操作要求的有关参数的合理性；）检查插入操作要求的有关参数的合理性；（2）将顺序表最后位置加）将顺序表最后位置加1（3）将第）将第i至第至第n-1个表项依次往后移动一个位个表项依次往后移动一个位置；置；（4）把新的表项插入在顺序表的第）把新的表项插入在顺序表的第i个个位置位置 Department of
15、 Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate int SeqList:Insert(Type&x,int i)/在表中第在表中第 i 个位置插入新元素个位置插入新元素 x if(i last+1|last=MaxSize-1)return 0;/插入不成功插入不成功 else last+;for(int j=last;j i;j-)dataj=dataj-1;datai=x;return 1;/插入成功插入成功 Department of Computer Science&Technolo
16、gy,Nanjing University fallDATA STRUCTURES插入算法分析插入算法分析(移动的元素个数移动的元素个数)最好：最好：最坏：最坏：平均：平均：221)(1)(1 0)1(11)(11=0nnnnnninnAMNni0n*O(n)Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESn删除：删除：int Remove(Type&x)Department of Computer Science&Technology,Nanjing University fall
17、DATA STRUCTURES删除的主要思想：删除的主要思想：(1)在顺序表中查找在顺序表中查找x,如果如果x在表中不存在，在表中不存在，则不能删除；则不能删除；(2)如果如果x在表中存在，设在表中存在，设x在顺序表中的在顺序表中的位置为位置为i;(3)将顺序表的最后位置减将顺序表的最后位置减1；(4)把顺序表中原来第把顺序表中原来第i+1至第至第n-1个表项依个表项依次向前移动一个表项位置次向前移动一个表项位置 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES template i
18、nt SeqList:Remove(Type&x)/在表中删除已有元素在表中删除已有元素 x int i=Find(x);/在表中搜索在表中搜索 x if(i=0)last-;for(int j=i;j=last;j+)dataj=dataj+1;return 1;/成功删除成功删除 return 0;/表中没有表中没有 x Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES删除算法分析删除算法分析（移动的元素个数）（移动的元素个数）最好：最好：最坏：最坏：平均：平均：102121)(
19、11)(1=ninnnninnAMN0n-1*O(n)Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES template void Union(SeqList&LA,SeqList&LB)int n=LA.Length();int m=LB.Length();for(int i=1;i=m;i+)Type x=LB.Get(i);/在在LB中取一元素中取一元素 int k=LA.Find(x);/在在LA中搜索它中搜索它 if(k=-1)/若未找到插入它若未找到插入它 LA.Inse
20、rt(n+1,x);n+;顺序表的应用：集合的顺序表的应用：集合的“并并”和和“交交”运算运算？Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES template void Intersection(SeqList&LA,SeqList&LB)int n=LA.Length();int m=LB.Length();int i=0;while(i link=first;first=newNode;/新结点成为首元结点新结点成为首元结点 else /否则，寻找插入位置否则，寻找插入位置
21、LinkNode*current=first;int k=1;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES while(k-link;k+;if(current=NULL&first!=NULL)/链短链短 cerr-link=current-link;current-link=newNode;return true;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTUREScu
22、rrentdeldel=first；first=firstlink;delete del；aiaiai+1ai+1del删除前删除前删除后删除后firstfirstcurrentcurrentdel Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESai-1ai-1aiaiai+1ai+1currentdel删除前删除后del=currentlink;currentlink=dellink;delete del；Department of Computer Science&Techno
23、logy,Nanjing University fallDATA STRUCTURES单链表的删除算法单链表的删除算法bool List:Remove(int i,int&x)/将链表中的第将链表中的第 i 个元素删去个元素删去,i 从从1开始。开始。LinkNode*del;/暂存删除结点指针暂存删除结点指针if(i link;else LinkNode*current=first;k=1;/找找i-1号结点号结点 while(k link;k+;if(current=NULL|current-link=NULL)cout link;/删中间删中间/尾结点尾结点 current-link=d
24、el-link;x=del-data;delete del;/取出被删结点数据取出被删结点数据 return true;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESn实现单链表的插入和删除算法，实现单链表的插入和删除算法，不需要移动元素不需要移动元素，只需修改结点指针只需修改结点指针，比顺序表方便。，比顺序表方便。n情况复杂，情况复杂，空表和在表头插入的特殊情形要考虑空表和在表头插入的特殊情形要考虑。n寻找插入或删除位置只能沿着链顺序检测寻找插入或删除位置只能沿着链顺序检测。关于
25、单链表的插入和删除关于单链表的插入和删除 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESn表头结点表头结点位于表的最前端，本身不带数据，仅标位于表的最前端，本身不带数据，仅标志表头。志表头。n表头结点表头结点data域内的数据存放一些辅助数据或者域内的数据存放一些辅助数据或者为空。为空。ana1firstfirst Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESnewn
26、odelink=currentlink;currentlink=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入currentcurrentcurrentcurrent非空表非空表:空表空表：Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESbool List:Insert(int i,int x)/将新元素将新元素 x 插入到第插入到第 i 个结点之后。个结点之后。i 从从1开始，开始，/i=0 表示插入到首
27、元结点之前。表示插入到首元结点之前。if(first=NULL|i=0)/空表或首元结点前空表或首元结点前 LinkNode*newNode=new LinkNode(x);/建立一个新结点建立一个新结点 newNode-link=first;first=newNode;/新结点成为首元结点新结点成为首元结点 else /否则，寻找插入位置否则，寻找插入位置 LinkNode*current=first;int k=1;回忆回忆:无表头结点的插入无表头结点的插入 Department of Computer Science&Technology,Nanjing University fallD
28、ATA STRUCTURESnewnodelink=currentlink;currentlink=newnode；newnodecurrentai-1newnodecurrentnewnodelink=currentlink;currentlink=newnode；Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES带附加头结点的单链表带附加头结点的单链表n空表或非空表第一个结点之前的插入可以不作为特空表或非空表第一个结点之前的插入可以不作为特殊情况专门处理殊情况专门处理,与一般情况一
29、样统一处理与一般情况一样统一处理;n统一了空表与非空表的操作统一了空表与非空表的操作。Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES q=plink;plink=qlink;delete q;firstfirstfirstfirstpqpq非空表非空表空表空表if(plink=NULL)last=p;?Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES 用模板定义的单链表类
30、：template /定义在定义在“LinkedList.h”struct LinkNode /链表结点类的定义链表结点类的定义 E data;/数据域数据域 LinkNode*link;/链指针域链指针域 LinkNode()link=NULL;/构造函数构造函数 LinkNode(E item,LinkNode*ptr=NULL)data=item;link=ptr;/构造函数构造函数 bool operator=(T x)return data.key=x;/重载函数，判相等重载函数，判相等 bool operator!=(T x)return data.key!=x;Departmen
31、t of Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate class List:public LinearList/单链表类定义单链表类定义,不用继承也可实现不用继承也可实现protected:LinkNode*first;/表头指针表头指针public:List()first=new LinkNode;/构造函数构造函数 List(E x)first=new LinkNode(x);List(List&L);/复制构造函数复制构造函数 List()/析构函数析构函数 void makeEmp
32、ty();/将链表置为空表将链表置为空表 int Length()const;/计算链表的长度计算链表的长度 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES LinkNode*Search(T x);/搜索含搜索含x元素元素LinkNode*Locate(int i);/定位第定位第i个元素个元素 E*getData(int i);/取出第取出第i元素值元素值 void setData(int i,E x);/更新第更新第i元素值元素值bool Insert(int i,E x);
33、/在第在第i元素后插入元素后插入bool Remove(int i,E&x);/删除第删除第i个元素个元素 bool IsEmpty()const /判表空否判表空否 return first-link=NULL?true:false;LinkNode*getFirst()const return first;void setFirst(LinkNode*f)first=f;void Sort();/排序排序;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate void
34、 List:makeEmpty()LinkNode*q;while(first-link!=NULL)q=first-link;/保存被删结点保存被删结点 first-link=q-link;/从链上摘下该结点从链上摘下该结点 delete q;/删除删除 ；链表置空算法（保留表头结点）Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESfirstqfirstfirstqqfirsta0a1a1a2a2a2current Department of Computer Science&Te
35、chnology,Nanjing University fallDATA STRUCTUREStemplate int List:Length()const ListNode*p=first-link;/检测指针 p 指示第一号结点 int count=0;while(p!=NULL)/逐个结点检测 p=p-link;count+;return count;求单链表的长度的算法 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESfirstpa0a1a2c=0firstpa0a1a2c=
36、1firstpa0a1a2c=2firstpa0a1a2c=3 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES单链表的搜索算法template LinkNode*List:Search(T x)/在表中搜索含数据在表中搜索含数据x的结点的结点,搜索成功时函数返搜索成功时函数返/该结点地址该结点地址;否则返回否则返回NULL。LinkNode*current=first-link;while(current!=NULL¤t-data!=x)current=current-
37、link;/沿着链找含沿着链找含x结点结点 return current;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES单链表的定位算法template LinkNode*List:Locate(int i)/函数返回表中第函数返回表中第 i 个元素的地址。若个元素的地址。若i 0或或 i 超超/出表中结点个数，则返回出表中结点个数，则返回NULL。if(i 0)return NULL;/i不合理不合理 LinkNode*current=first;int k=0;while(cu
38、rrent!=NULL&k-link;k+;return current;/返回第返回第 i 号结点地址或号结点地址或NULL;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES单链表的插入算法template bool List:Insert(int i,E x)/将新元素将新元素 x 插入在链表中第插入在链表中第 i 个结点之后。个结点之后。LinkNode*current=Locate(i);if(current=NULL)return false;/无插入位置无插入位置Link
39、Node*newNode=new LinkNode(x);/创建新结点创建新结点 newNode-link=current-link;/链入链入 current-link=newNode;return true;/插入成功插入成功;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES单链表的删除算法template bool List:Remove(int i,E&x)/删除链表第删除链表第i个元素个元素,通过引用参数通过引用参数x返回元素值返回元素值 LinkNode*current=
40、Locate(i-1);if(current=NULL|current-link=NULL)return false;/删除不成功删除不成功 LinkNode*del=current-link;current-link=del-link;x=del-data;delete del;return true;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES建立单链表建立单链表firstnewnodefirstnewnodenewnodefirstnewnode Department of
41、 Computer Science&Technology,Nanjing University fallDATA STRUCTURESfirstnewnodefirstnewnode Department of Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate void List:createListF(Type endTag)Type val;ListNode*node;first=new ListNode;/表头结点 cin val;while(val!=endTag)node=new Li
42、stNode(val);node-link=first-link;first-link=node;/插入到表前端 cin val;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURESnewnodefirstnewnodelastlastlastlast Department of Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate void List:createListR(Type end
43、Tag)Type val;ListNode*node,*last;first=new ListNode;/表头结点 cin val;last=first;while(val!=endTag)/last指向表尾 node=new ListNode(val);last-link=node;last=node;cin val;/插入到表末端 last-link=NULL;/表收尾 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES Department of Computer Science
44、&Technology,Nanjing University fallDATA STRUCTURES2.3 线性链表的其他变形线性链表的其他变形 循环链表循环链表 双向链表双向链表 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES循环链表循环链表(Circular List)Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES循环链表的特点：循环链表的特点：n是单链表的变形。是
45、单链表的变形。n循环链表最后一个结点的循环链表最后一个结点的 link 指针不指针不 为为 0(NULL)，而是指向了表的前端。，而是指向了表的前端。n为简化操作，在循环链表中往往加入表头为简化操作，在循环链表中往往加入表头结点。结点。n只要知道表中某一结点的地址，就可搜寻只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。到所有其他结点的地址。Department of Computer Science&Technology,Nanjing University fallDATA STRUCTUREStemplate struct CircLinkNode/链表结点类定义链表结点类定义
46、 E data;CircLinkNode*link;CircLinkNode(CircLinkNode*next=NULL)link=next;CircLinkNode(E d,CircLinkNode*next=NULL)data=d;link=next;bool Operator=(E x)return data.key=x.key;bool Operator!=(E x)return data.key!=x.key;循环链表类的定义循环链表类的定义 Department of Computer Science&Technology,Nanjing University fallDATA
47、STRUCTUREStemplate /链表类定义链表类定义class CircList:public LinearList private:CircLinkNode*first,*last;/头指针头指针,尾指针尾指针public:CircList(const E x);/构造函数构造函数CircList(CircList&L);/复制构造函数复制构造函数CircList();/析构函数析构函数 int Length()const;/计算链表长度计算链表长度bool IsEmpty()return first-link=first;/判表空否判表空否CircLinkNode*getHead(
48、)const;/返回表头结点地址返回表头结点地址 Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 current current currentcurrent current current currentcurrent循环链表的操作循环链表的操作1：搜索算法：搜索算法 Department of Computer Science&Technology,Nanjing
49、University fallDATA STRUCTUREStemplate CircListNode*CircList:Find(Type value)/在链表中从头搜索其数据值为value的结点 current=first-link;while(current!=first¤t-data!=value)current=current-link;return current;Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES Department of Computer
50、Science&Technology,Nanjing University fallDATA STRUCTURES Department of Computer Science&Technology,Nanjing University fallDATA STRUCTURES#include#include“CircList.h”Template void CircList:Josephus(int n,int m)Firster();for(int i=0;i n-1;i+)/执行执行n-1次次 for(int j=0;j m-1;j+)Next();cout “出列的人是出列的人是”get
