1、数据结构数据结构North China Electric Power UniversityData Structure华北电力大学计算机科学与工程系华北电力大学计算机科学与工程系Dept.of Computer Science&Engineering of North China Electric Power University第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 链表链表 第第4章章 数组和广义表数组和广义表第第5章章 串串第第6 6章章 树树第第7章章 图图第第8章章 查找表查找表第第9章章 内内排序排序目目 录录North China Electric Power U
2、niversityNorth China Electric Power University第三章第三章 链链 表表3.1 3.1 单链表单链表3.2 3.2 链栈、链队链栈、链队3.3 3.3 循环链表、多重链表循环链表、多重链表North China Electric Power University 3.1 3.1 单链表单链表North China Electric Power University当前内存的状态当前内存的状态建立一个含有建立一个含有8 8个元素的线性表个元素的线性表 L=(a1,a2,a3,a4,a5,a6,a7,a8)可以采用链式存储结构，每一个数据元素占用两个可以
3、采用链式存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不为链式存储结构。在这种结构中，数据元素存放是不连续的。连续的。a1Heada2a3 a4a5a6a7a8地址地址 数据数据 指针指针6462149594327901137991a24212743495990a1a3a7 a6a4a5a86499027594321HeadNorth China Electric Power Uni
4、versityNorth China Electric Power University用一组用一组地址任意地址任意的存储单元存放线性表中的数据元素的存储单元存放线性表中的数据元素结点结点(表示数据元素表示数据元素)=)=元素元素(数据元素的映象数据元素的映象)+指针指针(指示后继元素存储位置指示后继元素存储位置)链表：链表：以以“结点的序列结点的序列”表示的线性表。表示的线性表。头指针：头指针：指向链表中第一个结点的指针。指向链表中第一个结点的指针。数据数据域域 指针域指针域链表结点链表结点ABCD E F G H头结点头结点首元结点首元结点表结点表结点头指针头指针Head一、线性表的链式存
5、储结构一、线性表的链式存储结构链表基本概念链表基本概念头结点：头结点：单链表的第一个结点之前附设的一个结点，单链表的第一个结点之前附设的一个结点，它的数据域不存放信息、或存放如线性的长它的数据域不存放信息、或存放如线性的长 度等附加信息。度等附加信息。首元结点：首元结点：单链表中存放第一个元素的结点。单链表中存放第一个元素的结点。表结点：表结点：存放线性表中数据元素的结点。存放线性表中数据元素的结点。North China Electric Power University单链表中设置头结点的单链表中设置头结点的 好处好处1)1)其头指针是指向头结点的非空指针，无论链表是否为空，头其头指针是指
6、向头结点的非空指针，无论链表是否为空，头指针始终保持值不变，因此头指针的处理方法对空表和非空表指针始终保持值不变，因此头指针的处理方法对空表和非空表的操作是一致的，这与不带头结点的单链表为空时头指针为空的操作是一致的，这与不带头结点的单链表为空时头指针为空不同。不同。2)2)首元结点的地址存放在头结点的指针域中，对该结点的操作首元结点的地址存放在头结点的指针域中，对该结点的操作与其它结点的操作一致，无需进行特殊处理与其它结点的操作一致，无需进行特殊处理(如删除首元结点时，如删除首元结点时，对不带头结点的单链表要修改头指针对不带头结点的单链表要修改头指针)。North China Electri
7、c Power University1)Initial(Head):初始化一个单链表初始化一个单链表 void Initial(Pointer&head)/创建一个带头结点的空链表，创建一个带头结点的空链表，head为指向头结点的指针为指向头结点的指针 head=new Node;if(!head)exit(1);/存储空间分配失败存储空间分配失败 head-next=NULL;单链表的类型定义如下：单链表的类型定义如下：typedef struct Node ElemType data struct Node *next *Pointer;二、单链表上基本运算的实现二、单链表上基本运算的实现
8、North China Electric Power University2)Length(Head):返回单链表中所含表结点的个数。返回单链表中所含表结点的个数。int Length(Pointer&head)/求表求表head的长度，的长度，P是是Pointer类型变量类型变量 p=head;j=0;/计数器置初值计数器置初值 while(p-next!=NULL)/继续点数继续点数 p=p-next;j+;return(j);/回传表长回传表长3)Find(Head,i):返回指向线性表第返回指向线性表第i i个结点的指针。个结点的指针。North China Electric Powe
9、r UniversityPointer Find(Pointer head,int i)/在单链表在单链表head中查找第中查找第i个结点，若找到则回传指向该结点个结点，若找到则回传指向该结点 的指针；否则回传的指针；否则回传NULL p=head-next;/变量初始化，变量初始化，p 指向第一个结点指向第一个结点 j=0;while(p-next!Null)&(jnext;j+;/while if(i=j)return(p);else return(NULL);/FindNorth China Electric Power University4)Locate(Head,x):在单链表中查
10、找值等于在单链表中查找值等于x x的结点，的结点，返回指向该结点的指针。返回指向该结点的指针。int Locate(Pointer head,ElemType x)p=head;j=0;/置初值置初值 while(p-next)&(p-data!=x)p=p-next;j+;if(p-data=x)return(j);else return(0);ABCD x=CHeadpNorth China Electric Power University5)Insert(Head,x,i):在单链表的第在单链表的第i i个结点之前插入值等于个结点之前插入值等于x x的结点。的结点。ABCD x=F i
11、=3HeadpF Svoid Insert(Pointer&head,int i,ElemType x)/在表在表head的第的第i个结点之前插入一个以个结点之前插入一个以x为值的新结点为值的新结点 p=Find(head,i-1);if(!p)error(“without”);/参数不合法，参数不合法，i 小于小于1或者大于表长或者大于表长+1 else s=new Node;if(!s)exit(1);/存储空间分配失败存储空间分配失败 s-data=x;/创建新元素的结点创建新元素的结点 s-next=p-next;p-next=s;/修改指针修改指针 North China Elect
12、ric Power UniversityNorth China Electric Power University6)Delete (Head,i):删除单链表的第删除单链表的第i i个结点。个结点。void Delete(Pointer&head,int pos,ElemType&x)p=Find(head,i-1);/p指向第指向第i-1个结点个结点 if(p!=NULL)&(p-next!=NULL)q=p-next;p-next=q-next;/修改指针修改指针 x=q-data;delete(q);/释放结点空间释放结点空间 else error(“Without”);ABCD i=
13、3HeadpNorth China Electric Power University7)CreateList (Head):建立一个单链表。建立一个单链表。void CreateList(Pointer&head)head=new Node;/生成头结点生成头结点 p=head;/尾指针指向头结点尾指针指向头结点 getchar(x);/读入第一个元素读入第一个元素 while(x!=*)q=new Node;if(!q)exit(1);/存储空间分配失败存储空间分配失败 q-data=x;p-next=q;p=q;getchar(x);p-next=NULL;North China Ele
14、ctric Power Universityvoid Create_Link_2(Pointer&head);/从前建立链表从前建立链表 void Create_Link_3(Pointer&head);/从后建立链表从后建立链表华电计算机系华电计算机系Initial(Head);p=Head;getchar(x);while(x!=*)q=new Node;q-data=x;p-next=q;p=q;getchar(x);p-next=NULL;p=NULL;getchar(x);while(x!=*)q=new Node;q-data=x;q-next=p;p=q;getchar(x);I
15、nitial(Head);Head-next=p;North China Electric Power University1)1)存储空间动态分配，可以按需要使用；存储空间动态分配，可以按需要使用；2)2)插入插入/删除结点操作时，只需要修改指针，不必移动删除结点操作时，只需要修改指针，不必移动数据元素数据元素线性表的链式存储结构的优缺点：线性表的链式存储结构的优缺点：优点优点缺点缺点1)1)每个结点需加一指针域，存储密度降低；每个结点需加一指针域，存储密度降低；2)2)非随机存储结构，查找定位操作需要从头指针出非随机存储结构，查找定位操作需要从头指针出发顺着链表扫描。发顺着链表扫描。Nor
16、th China Electric Power University例例1.1.将一个单链表逆置将一个单链表逆置void Invert_Link_1(Pointer&head);/不带头结点不带头结点 p=Head;Head=NULL;while(p!=NULL)s=p;p=p-next;s-next=Head;Head=s;void Invert_Link_2(Pointer&head);/带头结点带头结点 p=Head-next;h=NULL;while(p!=NULL)s=p;p=p-next;s-next=h;h=s;head-next=h;单链表的应用示例单链表的应用示例例例2 2：
17、一元多项式的表示及相加。：一元多项式的表示及相加。在数学上，一个一元在数学上，一个一元n n次多项式次多项式Pn(XPn(X)可按升幂写成：可按升幂写成：Pn(xPn(x)=P)=P1 1x xe1e1+P+P2 2x xe2e2+P+Pm mx xemem其中其中,P,Pi i是指数为是指数为eiei的项的非零系数，且满足的项的非零系数，且满足 0e1e20e1e2em next;q=pb-next;S=pa;pc=pa;/S指向指向p结点的直接前驱结点的直接前驱 while(p!=NULL)&(q!=NULL)if(p-expexp)s=p;p=p-next;/p指针后移指针后移 if(p
18、-exp=q-exp)x=p-coef+q-coef;if(x!=0)p-coef=x;s=p/修改修改p结点结点 else s-next=p-next;delete(p);p=s-next;u=q;q=q-next;delete(u);if(p-expq-exp)u=q-next;q-next=p;s-next=q;s=q;q=u;if(q!=NULL)s-next=q;delete(pb);练习练习1 若已知非空线性链表第一个结点的指针为若已知非空线性链表第一个结点的指针为list，请请 写一个算法，写一个算法，将该链表中数据域值最小的那个将该链表中数据域值最小的那个 结点移到链表的最前端
19、。结点移到链表的最前端。North China Electric Power Universitylist356718658271521014list356718658271521014qpqs华电华电计算机系计算机系North China Electric Power University void Remove(Pointer&list);q=list;p=list-next;r=list;while (p!=null)if (p-data data)s=r;q=p;r=p p=p-next;/s始终指向始终指向q的前一个结点的前一个结点 /找到值最小的那个结点找到值最小的那个结点，地址由
20、，地址由q记录记录 if (q!=list)/若值最小的结点不是链表最前面那个结点若值最小的结点不是链表最前面那个结点 s-next=q-next;q-next=list;list=q;end;堆栈的链式存储结构堆栈的链式存储结构一一.构造原理构造原理 链接堆栈就是用一个线性链表来实现一个堆链接堆栈就是用一个线性链表来实现一个堆栈结构栈结构,同时设置一个指针变量同时设置一个指针变量(这里用这里用 Ls表示表示)指指出当前栈顶元素所在链结点的位置。当栈为空时，出当前栈顶元素所在链结点的位置。当栈为空时，有有Ls=nil。North China Electric Power University
21、3.2 3.2 链栈和链队链栈和链队 在一个初始为空的链接堆栈中依次插入数据元素在一个初始为空的链接堆栈中依次插入数据元素 A,B,C,D以后以后,堆栈的状态为堆栈的状态为DCBALs栈顶元素栈顶元素North China Electric Power UniversityitempLs.二二.插入插入(进栈进栈)算法算法void PushStack(Stack&S,ElemType x)/将元素将元素x压入栈压入栈Ls中中 p=new Node;/生成新结点生成新结点 p-data=x;p-next=S;/链入栈中链入栈中 S=p;/修改栈顶指针修改栈顶指针 算法算法North China
22、Electric Power UniversityLsitem.pitem三三.删除删除(退栈退栈)算法算法void PopStack(Stack&S)/若栈空给出错误信息；否则删除栈顶元素若栈空给出错误信息；否则删除栈顶元素 if(S=Null)error(“栈空栈空”);else p=S;S=S-next;delete(p);算法算法North China Electric Power University队列的链式存储结构队列的链式存储结构一一.构造原理构造原理 队列的链式存储结构是用一个线性链表表示队列的链式存储结构是用一个线性链表表示一个队列，一个队列，指针指针 front 与与re
23、ar 分别指向实际队头分别指向实际队头元素与实际队尾元素所在的链结点。元素与实际队尾元素所在的链结点。约约 定定：rear 指出实际队尾元素所在的位置指出实际队尾元素所在的位置 front 指出实际队头元素所在位置的前一个位置指出实际队头元素所在位置的前一个位置North China Electric Power University 在一个初始为空的链接队列中依次插入数据元素在一个初始为空的链接队列中依次插入数据元素 A,B,C,D以后以后,队列的状态为队列的状态为ABCDfrontrear空队对应的链表为空链表，空队的标志是空队对应的链表为空链表，空队的标志是 front=nilNorth
24、 China Electric Power Universityfront=rear=nilpitem front rearfrontrear二二.插入算法插入算法pitemNorth China Electric Power Universityvoid InQueue(Squeue&f,&r,ElemType x)/将将x入链队入链队 p=new Node;p-data=x;p-next=NULL;r-next=p;r=p;算算 法法North China Electric Power Universityfrontrearvoid OutQueue(Squeue&f,&r)/若链队为空给
25、出出错信息；否则删除队头元素若链队为空给出出错信息；否则删除队头元素 if(r=f)error(“队空队空”);else q=f-next;f-next=q-next;if(q-next=NULL)r=f;delete(q);三三.删除算法删除算法算算 法法North China Electric Power University 循环链表循环链表 是指链表中最后那个链结点的指针是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表域存放指向链表最前面那个结点的指针，整个链表形成一个环。形成一个环。North China Electric Power University
26、3.3 3.3 循环链表与多重链表循环链表与多重链表 3.3.1 3.3.1 循环链表循环链表listlist 线性链表线性链表带头结点的循环链表带头结点的循环链表North China Electric Power University循环链表的特点循环链表的特点1.只要给出表中任何一个结点的位置，则由此出发就可以访只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。问表中其他所有结点。2.2.对循环链表，若在它的第一个结点之前设立一个特殊的称对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链为表头的结点，它的数据域可以按需
27、要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。表和非空表的处理统一起来。3.3.当需要将整个链表中所有结点归还给可用空间栈时，用循当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。环链表比用普通链表要方便的多。Havav单链表单链表Havav循环链表循环链表North China Electric Power University双向链表及其操作双向链表及其操作1.双向链表的构造双向链表的构造2.双向链表的插入与删除双向链表的插入与删除North China Elec
28、tric Power University 3.4.2 3.4.2 多重链表多重链表 一一.双向链表的构造双向链表的构造 所谓所谓双向链表双向链表是指链表的每一个结点中除了数据域以是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。另外一个指向结点的直接后继结点。链结点的实际构造可以形象地描述如下：链结点的实际构造可以形象地描述如下：llinkdata rlink其中，其中，data 为数据域为数据域 llink,rlink 分别为指向该结点的直接前驱结点分别为指向该结点的直接前驱
29、结点 与直接后继结点的指针域与直接后继结点的指针域华电计算机系华电计算机系North China Electric Power University双向链表的几种形式双向链表的几种形式list不带头结点的双向链表不带头结点的双向链表list不带头结点的双向循环链表不带头结点的双向循环链表list带头结点的双向循环链表带头结点的双向循环链表North China Electric Power University 二二.双向链表的插入双向链表的插入功能功能：在带有头结点的非空双向循环链表中第一个数据在带有头结点的非空双向循环链表中第一个数据 域的内容为域的内容为x 的链结点右边插入一个数据信息为
30、的链结点右边插入一个数据信息为 item 的新结点。的新结点。list1.找到满足条件的结点。找到满足条件的结点。2.若找到，申请一个新的链结点。若找到，申请一个新的链结点。3.将新结点插到满足条件的结点后面。将新结点插到满足条件的结点后面。需要做的工作需要做的工作North China Electric Power Universityitemitemitemp插入前插入前xq插入后插入后插入插入p-llink=qp-rlink=q-rlinkq-rlink=pq-rlink-llink=pNorth China Electric Power University p=hd-Rlink;/p
31、指向链表的第一个结点指向链表的第一个结点 while(p!=hd)&(p-data!=x)p=p-Rlink;/查找结点查找结点x if(p=hd)printf(“No node x”);void inserdoublink(DnLink&hd，ElemType x，ElemType y)-/在以在以hd为头指针的双向链表中的数域等于为头指针的双向链表中的数域等于x的结点右边插入含的结点右边插入含y值的结点值的结点 else q=new DbNode;/申请一个新的结点申请一个新的结点 /q-data=y;p-Rlink=q;(p-Rlink)-Llink=q;q-Llink=p;q-Rlin
32、k=p-Rlink;算法算法xitempNorth China Electric Power University 三三.双向链表的删除双向链表的删除1.找到满足条件的结点。找到满足条件的结点。2.若找到，删除并释放该结点。若找到，删除并释放该结点。list 功能功能：删除带有头结点的非空双向循环链表中第一个删除带有头结点的非空双向循环链表中第一个 数据域的内容为数据域的内容为x 的链结点。的链结点。需要做的工作需要做的工作North China Electric Power University删除前删除前删除后删除后 删除删除q-llink-rlink:=q-rlinkq-rlink-ll
33、ink:=q-llinkNorth China Electric Power University p=hd-Rlink；/令令p指向表的第一个结点指向表的第一个结点 while(p-data!=x)&(p!=hd)p=p-Rlink;/查找结点查找结点x if(p=hd)printf(“No this node”);void dedoublink(DbLink&hd，ElemTypex)end;delete(q);/释放被删除的结点的存储空间释放被删除的结点的存储空间 /(p-Rlink)-Llink=p-Llink;/修改后继结点的左链域修改后继结点的左链域 else (p-Llink)-Rlink=p-Rlink;/修改前驱结点的右链域修改前驱结点的右链域华电计算机系华电计算机系算法算法xqNorth China Electric Power UniversityNorth China Electric Power University
