数据结构线性表课件

数据结构线性表课件第二章 线性表 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓数据结构线性表课件本章目录w 2.1 线性表的类型定义线性表的类型定义 n2.1.1 线性表的概念线性表的概念 n2.1.2 线性表的抽象数据类型线性表的抽象数据类型w 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 n2.2.1 线性表的顺序表示线性表的顺序表示 n2.2.2 顺序表上基本运算的实现顺序表上基本运算的实现w 2.3 线性表的链式表示和实现线性表的链式表示和实现 n2.3.1 单链表的表示单链表的表示 n2.3.2 单链表操作的实现单链表操作的实现w 2.4 线性表实现方法的比较线性表实现方法的比较w 2.5 循环链表循环链表w 2.6 双链表双链表w 2.7 静态链表静态链表 （*2.8 算法设计举例）算法设计举例）数据结构线性表课件主要内容 w知识点知识点n线性表的定义线性表的定义n顺序表顺序表n单链表单链表n双链表双链表n静态链表静态链表w重点难点重点难点n顺序表操作的实现顺序表操作的实现n单链表操作的实现单链表操作的实现n顺序表和链表操作时间复杂度的分析顺序表和链表操作时间复杂度的分析n静态链表静态链表数据结构线性表课件线性结构w在数据元素的非空的有限集合中：在数据元素的非空的有限集合中：n存在唯一的一个被称为存在唯一的一个被称为“第一个第一个”的数的数据元素；据元素；n存在唯一的一个被称为存在唯一的一个被称为“最后一个最后一个”的的数据元素；数据元素；n除第一个元素外，集合中每个元素都有除第一个元素外，集合中每个元素都有且仅有且仅有一个前驱一个前驱；n除最后一个元素外，集合中每个元素都除最后一个元素外，集合中每个元素都有且仅有有且仅有一个后继一个后继；数据结构线性表课件线性表(Linear List)定义w 定义：定义：n个具有相同特性的数据元素组成的有限序列；w 表示：表示：a1,ai-1,ai,ai+1,anw ai必须具有相同特性，即属于同一数据对象w ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素w 数据元素ai在线性表中有确定的位置i，i称为位序w 线性表中数据元素的个数n称为线性表的长度,n=0时，线性表称为空表数据结构线性表课件抽象数据类型定义ADT List数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：数据关系：R=|ai,ai-1D,i=2,n基本操作：基本操作：lListInit(L)；lListLength(L)；lListGet(L,i);lListLocate(L,x);lListClear(L);lListEmpty(L)；lListPrior(L,e)；lListNext(L,e)；lListInsert(L,i,e);lListDelete(L,i);ADT List数据结构线性表课件例如例如2.1 2.1 遍历线性表遍历线性表L L ListTraverse(List L，visit()/遍历线性表遍历线性表if(ListEmpty(L)printf(“空表空表n”);else for(i=1;i=ListLength(L);i+)visit(ListGet(L,i)；数据结构线性表课件例2.2 合并线性表合并线性表List ListMerge(List La,List Lb)/La和和Lb是两个非递减有序的线性表，将线性表是两个非递减有序的线性表，将线性表La和和Lb合并成一合并成一个新的线性表个新的线性表Lc，Lc也非递减有序。也非递减有序。ListInit(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)/La和和Lb均非空均非空 ai=ListGet(La,i);bj=ListGet(Lb,j);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;（接下页）（接下页）数据结构线性表课件 （接上页）（接上页）while(i=La_len)/Lb已空，将已空，将La表的剩余部分复制到新表表的剩余部分复制到新表ai=ListGet(La,i+);ListInsert(Lc,+k,ai);while(j=Lb_len)/La已空，将已空，将Lb表的剩余部分复制到新表表的剩余部分复制到新表bj=ListGet(Lb,j+);ListInsert(Lc,+k,bj);return(Lc);/ListMerge例2.2 合并线性表合并线性表数据结构线性表课件逻辑结构是本质 通过上面两个例子可以看出：w 逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的）逻辑结构与数据元素本身的形式、内容形式、内容无关。无关。（2）逻辑结构与数据元素的）逻辑结构与数据元素的相对位置相对位置无关。无关。（3）逻辑结构与所含数据元素的）逻辑结构与所含数据元素的个数个数无关。无关。w 算法的设计取决于选定的逻辑结构，算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构而算法的实现依赖于采用的存储结构 数据结构线性表课件线性表的顺序表示和实现 线性表的顺序表示线性表的顺序表示 :线性表的顺序存储是指在内存中线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为用这种存储形式存储的线性表称为顺序表顺序表。设设 a a的存储地址为的存储地址为Loc(aLoc(a)，每个数据元素占，每个数据元素占L L个存个存储单元，则第储单元，则第i i个数据元素的地址为：个数据元素的地址为：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i)+(i-1)1)*L 1L 1i in n 0 1 i-1 i n-1 MAXSIZE-1 a a1 1a a2 2a ai ia an ndatadataa ai-1i-1a ai+1i+1顺序存储结构的线性表的类型定义如下：顺序存储结构的线性表的类型定义如下：#define MAXSIZE 100 顺序表的最大容量顺序表的最大容量typedef structElemType dataMAXSIZE;存放线性表的数组存放线性表的数组int last;last是线性表的长度是线性表的长度SeqList;数据结构线性表课件顺序表上基本运算的实现(1)SeqList SeqListInit(SeqList L)/构造一个空的顺序表构造一个空的顺序表 L.length=0;/初始化顺序表初始化顺序表为空表为空表 return L;顺序表的初始化顺序表的初始化 :数据结构线性表课件顺序表上基本运算的实现(2)插入运算插入运算:在第在第 i 个位置，插入元素个位置，插入元素e思想：思想：把从第把从第i个位置开始的元素，依次后个位置开始的元素，依次后移移步骤：步骤：1.当前表是否已经满？当前表是否已经满？2.输入是否有效？输入是否有效？3.插入元素。插入元素。数据结构线性表课件顺序表上基本运算的实现(2)w SeqList SeqListInsert(SeqList L，int i，ElemType x)w 在顺序表中的第在顺序表中的第 i 个位置插入元素个位置插入元素 x w if(L.Last=MAXSIZE)w printf(表满表满n);exit(0);表满，退出表满，退出w if(iL.Last+1)w printf(插入位置错插入位置错n);exit(0);插入位置错，退出插入位置错，退出w for(j=L.Last-1;j=i-1;j-)w L.dataj+1=L.dataj;w 第第i个位置后的数组元素逐一后移个位置后的数组元素逐一后移 w L.datai-1=x;新元素插入到第新元素插入到第i个位置个位置w L.Last+;顺序表长度增顺序表长度增1w return(L);返回插入元素后的顺序表返回插入元素后的顺序表w 数据结构线性表课件顺序表插入元素算法分析w 插入运算的基本操作是移动数据。在第插入运算的基本操作是移动数据。在第i（1in+1）个位置上插入）个位置上插入x，需要移动，需要移动n-i+1个个元素。元素。w 设在第设在第i个位置上作插入的概率为个位置上作插入的概率为 pi，则平均移，则平均移动数据元素的次数（期望值）为动数据元素的次数（期望值）为 w 设：设：pi=1/(n+1)，即为等概率情况，则：，即为等概率情况，则：pi=n/2,约需移动表中一半的数据元素。约需移动表中一半的数据元素。11)1(niiiinsinpE时间复杂度：时间复杂度：O(n)数据结构线性表课件顺序表上基本运算的实现(3)删除运算删除运算:删除第删除第 i 个元素个元素e思想：思想：把第把第i1个位置开始的元素，依次个位置开始的元素，依次前移前移步骤：步骤：1.要检查删除位置的有效性；要检查删除位置的有效性；2.依次移动元素；依次移动元素；3.长度减长度减1。数据结构线性表课件顺序表上基本运算的实现(3)void SeqListDelete(SeqList L,int i)/删除顺序表中的第删除顺序表中的第i个元素个元素 if(iL.last)printf(“位置非法位置非法”)exit(0);/检查空表及删除位置的合法性检查空表及删除位置的合法性 for(j=i;j=L.last-1;j+)L.dataj-1=L.dataj;/向上移动向上移动 L.last-;/顺序表长度减顺序表长度减1 时间复杂度：时间复杂度：O(n)删除元素删除元素 :数据结构线性表课件顺序表删除元素算法分析w 主要操作是移动元素。删除第主要操作是移动元素。删除第i个元素时，个元素时，向前移动向前移动n-i 个元素个元素w 平均移动元素次数的期望值平均移动元素次数的期望值:w 在等概率情况下，在等概率情况下，pi=1/n，则：，则：Edel=(n-1)/2,所以顺序表上的删除运算约需要移动所以顺序表上的删除运算约需要移动表中一半的元素。表中一半的元素。时间复杂度：时间复杂度：O(n)11)(niiidelinpE数据结构线性表课件顺序表上基本运算的实现(4)int SeqListLocate(SeqList L,ElemType x)/在顺序表在顺序表L中查找第一个与中查找第一个与x值相等的元素。若值相等的元素。若查找成功，则返回它在顺序表中的位序；否则，查找成功，则返回它在顺序表中的位序；否则，返回返回0。i=1;while(i=L.last&L.datai-1!=x)i+;if(i=0&j=0)if(LA.datai=LB.dataj)LA.datak-=LA.datai-;else LA.datak-=LB.dataj-;while(j=0)LA.datak-=LB.dataj-;LA.last=m+n;数据结构线性表课件顺序表算法举例（续）请写一个算法将顺序表（请写一个算法将顺序表（a1,.,an）逆置为）逆置为(an,.,a1)。void SeqInvert（ElemType a，int n）/a是具有是具有n个元素的顺序表，本算法将其逆置。个元素的顺序表，本算法将其逆置。for（i=0；idata p-next 数据结构线性表课件线性链表操作的实现(1)LinkedList LinkedListInit()/建立一个空的单链表建立一个空的单链表 L=(LNode*)malloc(sizeof(LNode)；if(L=null)printf(“无内存空间可分配无内存空间可分配”);exit(0);L-next=NULL;return L;带头结点的单链表的初始化：带头结点的单链表的初始化：数据结构线性表课件线性链表操作的实现(2)int LinkedListLength(LinkedList L)/求带头结点的单链表的长度求带头结点的单链表的长度 p=L-next;/p指向第一结点指向第一结点 j=0;while(p)j+;p=p-next;/移动移动p指向下一结点指向下一结点 return j;求表长求表长:数据结构线性表课件线性链表操作的实现(3)LinkedList LinkedListGet(LinkedList L,int i);/在单链表在单链表L中查找第中查找第i个元素结点，返回该结点，否则个元素结点，返回该结点，否则返回空返回空 if(inext;j=1;while(p!=NULL&jnext;j+;if(j=i)return p;else return NULL;取第取第i i个元素个元素:数据结构线性表课件线性链表操作的实现(4)LinkedList LinkedListLocate(LinkedList L,ElemType x)/在单链表在单链表L中查找值为中查找值为x的结点，找到后返回其指针，的结点，找到后返回其指针，否则返回空否则返回空 p=L-next;while(p!=NULL&p-data!=x)p=p-next;if(!p)printf(“无值为无值为X的结点的结点”);return null;else return p;按值查找按值查找:数据结构线性表课件线性链表操作的实现(5)LinkedList LinkedListLocate(LinkedList L,LNode*p)/在单链表在单链表L中求中求p指向的结点指向的结点(假定存在）的前驱假定存在）的前驱 if(L-next=p)printf(“p指向第一元素结点，无前驱指向第一元素结点，无前驱”);exit(0);pre=L;while(pre!=NULL&pre-next!=p)pre=pre-next;if(pre)return pre;else return null;查找结点的前驱查找结点的前驱:数据结构线性表课件线性链表操作的实现(6)LinkedList LinkedListLocate(LinkedList L,LNode*p)/在单链表在单链表L中求中求p指向的结点指向的结点(假定存在）的后继假定存在）的后继 pre=L;while(pre!=NULL&pre-next!=p)pre=pre-next;if(p-next=null)printf(“p指向最后元素结点，无后继指向最后元素结点，无后继”);exit(0);else return p;查找结点的后继查找结点的后继:数据结构线性表课件线性链表操作的实现(7)p表示当前结点，表示当前结点，pre表示前一个结点表示前一个结点(的指的指针针)。在在p前插入元素前插入元素ss-next =pre-next;pre-next=s;aknext插入元素：插入元素：ai-1nextainextpre数据结构线性表课件线性链表操作的实现(7)插入算法插入算法:void LinkedListInsert(LinkedList L,LNode*p,ElemType x)/在结点在结点p之前插入元素为之前插入元素为x的结点的结点pre=L;while(pre!=NULL&pre-next!=p)pre=pre-next;/找找p的直接前驱的直接前驱 if(!pre)printf(“不存在不存在*p结点结点”)；exit(0);s=(LNode*)malloc(sizeof(LNode);/创建新结点创建新结点 s-data=x;/设置新结点的元素值设置新结点的元素值 s-next=pre-next;pre-next=s;/插入新结点插入新结点数据结构线性表课件线性链表操作的实现(8)p表示当前结点，表示当前结点，pre表示前一个结点。表示前一个结点。pre-next=p-next;free(p);/p=pre-next;删除元素删除元素:ai-1nextainextai+1next数据结构线性表课件线性链表操作的实现(8)删除元素删除元素:void LinkedListDel(LinkedList L，int i)/删除单链表删除单链表L上的第上的第i个结点个结点 if(inext&jnext;j+if(p-next=NULL|ji)printf(“删除位置不正确删除位置不正确”)；exit(0);q=p-next;p-next=q-next;/从链表中删除从链表中删除 free(q);/释放被删除结点释放被删除结点 数据结构线性表课件线性链表操作的实现(9)建立单链表头插法建立单链表头插法:L36L3645L103645L23103645L3645102367L数据结构线性表课件线性链表操作的实现(9)LinkedList LinkedListCreat1()/用头插法建立带头结点的单链表用头插法建立带头结点的单链表 LinkedList L;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;/初始化一个空链表，初始化一个空链表，L为头指针为头指针 scanf(&x);/x是和链表元素具有相同类型的变量是和链表元素具有相同类型的变量 while(x!=flag)/flag为结束输入的标志为结束输入的标志 /生成新结点生成新结点 p=(LNode*)malloc(sizeof(LNode);p-data=x;/输入元素值输入元素值 p-next=L-next;L-next=p;/插入到表头插入到表头 scanf(&x);/读入下一个元素的值读入下一个元素的值 return L;头插法建立单链表算法头插法建立单链表算法:数据结构线性表课件线性链表操作的实现(10)建立单链表尾插法建立单链表尾插法:67rL2367rL102367rL36 45102367rL45102367rL数据结构线性表课件线性链表操作的实现(10)LinkedList LinkedListCreat3()/用尾插法建立带头结点的单链表用尾插法建立带头结点的单链表 LinkedList L;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(&x);while(x!=flag)/设置结束标志设置结束标志 p=(LNode*)malloc(sizeof(LNode);p-data=x;/赋值元素值赋值元素值 r-next=p;/在尾部插入新结点在尾部插入新结点 r=p;/r 指向新的尾结点指向新的尾结点 scanf(&x);r-next=NULL;/最后结点的指针域放空指针最后结点的指针域放空指针 return L;尾插法建立单链表算法尾插法建立单链表算法:数据结构线性表课件链表的遍历void print(LinkedList la)/非递归非递归LinkedList p=la-next;while(p)printf(“%c”,p-data);p=p-next;void out(LinkedList p)/递归递归if(p)out(p-next);printf(“%c”,p-data);数据结构线性表课件链表算法举例 合并单链表w LinkedList Union(LinkedList la，LinkedList lb)w 将非递减有序的单链表将非递减有序的单链表la和和lb合并成新的非递减有序单链表合并成新的非递减有序单链表lc，并要求利，并要求利用原表空间用原表空间w lc=(LNode*)malloc(sizeof(LNode);申请结点申请结点w lc-next=NULL;初始化链表初始化链表lcw pa=la-next;pa是链表是链表la的工作指针的工作指针w pb=lb-next;pb是链表是链表lb的工作指针的工作指针w pc=lc;pc是链表是链表lc的工作指针的工作指针w while(pa&pb)la和和lb均非空均非空w if(pa-datadata)w pc-next=pa;pc=pa;w pa=pa-next;w la中元素插入中元素插入lc数据结构线性表课件链表算法举例 （接上页）（接上页）elsew pc-next=pb;w pc=pb;w pb=pb-next;w lb中元素插入lcw if(pa)pc-next=pa;若pa未到尾，将pc指向paw else pc-next=pb;若pb未到尾，将pc指向pbwreturn(lc);w Union 数据结构线性表课件链式结构的特点w非随机存贮结构，所以取表元素要慢非随机存贮结构，所以取表元素要慢于顺序表。于顺序表。n节约了内存节约了内存w适合于插入和删除操作适合于插入和删除操作n实际上用空间换取了时间，结点中实际上用空间换取了时间，结点中加入了指针，使得这两种操作转换加入了指针，使得这两种操作转换为指针操作为指针操作;数据结构线性表课件线性表实现方法的比较 w 实现不同实现不同n顺序表方法简单，各种高级语言中都有数组类型，顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是基于指针的，相对来讲复容易实现；链表的操作是基于指针的，相对来讲复杂些。杂些。w 存储空间的占用和分配不同存储空间的占用和分配不同n从存储的角度考虑，顺序表的存储空间是静态分配从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，的，在程序执行之前必须明确规定它的存储规模，也就是说事先对也就是说事先对“MAXSIZE”要有合适的设定，过要有合适的设定，过大造成浪费，过小造成溢出。而链表是动态分配存大造成浪费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表储空间的，不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链表。的长度或存储规模难以估计时，采用链表。w 线性表运算的实现不同线性表运算的实现不同 n按序号访问数据元素，使用顺序表优于链表。按序号访问数据元素，使用顺序表优于链表。n插入删除操作插入删除操作 ，使用链表优于顺序表。，使用链表优于顺序表。数据结构线性表课件循环链表单循环链表单循环链表:循环链表：循环链表：链表尾链表尾结点的指针域指向结点的指针域指向头结点头结点。这样形成的链表我们叫做循环链表。这样形成的链表我们叫做循环链表。(a)非空表非空表a1Han(b)空表空表H循环链表往往只设尾指针循环链表往往只设尾指针数据结构线性表课件连接两个只设尾指针的单循环链表L1和L2 语句段如下：语句段如下：p=R1next;/保存保存L1 的头结点指针的头结点指针R1-next=R2-next-next;/头尾连接头尾连接free(R2-next);/释放第二个表的头结点释放第二个表的头结点 R2-next=p;R2b1bna1anR1p数据结构线性表课件双链表 如果希望查找前驱的时间复杂度达如果希望查找前驱的时间复杂度达到到O(1)，我们可以用空间换时间，我们可以用空间换时间,每个结每个结点再加一个指向前驱的指针域，使链表点再加一个指向前驱的指针域，使链表可以进行双方向查找。用这种结点结构可以进行双方向查找。用这种结点结构组成的链表称为组成的链表称为双向链表双向链表。结点的结构结点的结构图图:priornextdata数据结构线性表课件双向链表的逻辑表示priordatanextLL数据结构线性表课件双向链表的类型定义typedef struct DLNodeElemType data;struct DLNode*prior,*next;DLNode,*DLinkedList;双向链表结点的类型定义如下：双向链表结点的类型定义如下：数据结构线性表课件双向链表的插入psp-prior=s;12s-prior=p-prior;p-prior-next=s;s-next=p;3 4数据结构线性表课件双向链表的删除p12p-prior-next=p-next;P-next-prior=p-prior;free(p);数据结构线性表课件循环链表算法举例循环链表算法举例（1 1）假设一个单循环链表，其结点含有三个域假设一个单循环链表，其结点含有三个域prepre、datadata、linklink。其中。其中datadata为数据域；为数据域；prepre为指针域，它的为指针域，它的值为空指针（值为空指针（nullnull）；）；linklink为指针域，它指向后继结为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。点。请设计算法，将此表改成双向循环链表。void SToDouble（LinkedList la）while（la-link-pre=null）la-link-pre=la/将结点将结点la后继的后继的pre指针指向指针指向la la=la-link；/la指针后移指针后移 /算法结束算法结束数据结构线性表课件循环链表算法举例循环链表算法举例（2）已知一双向循环链表，从第二个结点至表尾已知一双向循环链表，从第二个结点至表尾递增有序，（设递增有序，（设a1xnext；将第一结点从链表上摘下将第一结点从链表上摘下 p-prior=L-prior；p-prior-next=p；while（p-datanext；查插入位置查插入位置 s-next=p；s-prior=p-prior；插入原第一结点插入原第一结点s p-prior-next=s；p-prior=s；算法结束算法结束数据结构线性表课件链表算法举例链表算法举例（3）L1与与L2分别为两单链表头结点地址指分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个针，且两表中数据结点的数据域均为一个字母。设计把字母。设计把L1中与中与L2中数据相同的连续中数据相同的连续结点顺序完全倒置的算法。结点顺序完全倒置的算法。acabdadadbL 1L 2数据结构线性表课件链表算法举例链表算法举例（3）LinkedList PatternInvert（LinkedList L1，L2）w p=L1；p是每趟匹配时是每趟匹配时L1中的起始结点前驱的指针中的起始结点前驱的指针w q=L1-next；q是是L1中的工作指针。中的工作指针。w s=L2-next；s是是L2中的工作指针。中的工作指针。w while（p!=null&s!=null）w if（q-data=s-data）q=q-next;s=s-next;对应字母相等，指针后移。对应字母相等，指针后移。w else p=p-next；q=p-next；s=L2-next；/失配时失配时L1起始结点后移，起始结点后移，L2从首结点开始。从首结点开始。（接下页）（接下页）数据结构线性表课件链表算法举例链表算法举例（接上页）（接上页）w if（s=NULL）w 匹配成功，这时匹配成功，这时p为为L1中与中与L2中首字母结点相同数据域结点的前中首字母结点相同数据域结点的前驱，驱，q为为L1中与中与L2最后一个结点相同数据域结点的后继。最后一个结点相同数据域结点的后继。w r=p-next；w r为为L1的工作指针，初始指向匹配的首字母结点。的工作指针，初始指向匹配的首字母结点。w p-next=q；将将p与与q结点的链接。结点的链接。w while（r!=q）；逐结点倒置。逐结点倒置。w s=r-next；暂存暂存r的后继。的后继。w r-next=p-next；将将r所指结点倒置。所指结点倒置。w p-next=r；w r=s；恢复恢复r为当前结点。为当前结点。w w w else printf（“L2并未在并未在L1中出现中出现”）；）；w 算法结束算法结束数据结构线性表课件静态链表 有些高级程序设计语言并没有指针类型，如有些高级程序设计语言并没有指针类型，如FORTRAN和和JAVA。我们可以用数组来表示和。我们可以用数组来表示和实现一个链表，称为实现一个链表，称为静态链表静态链表。可定义如下：可定义如下：#define MAXSIZE 1000 /最多元素个数最多元素个数 typedef struct ElemType data;/数据元素数据元素 int next;/指向后继元素在数组中的位置指向后继元素在数组中的位置 SLinkedListMAXSIZE;数据结构线性表课件静态链表图示线性表线性表L=L=（2 2，3 3，4 4，6 6，8 8，9 9）的静态链表）的静态链表图示图示datadatanextnext0416623334142259-168578910数据结构线性表课件静态链表与动态链表 静态链表的操作和动态链表相似，只是静态链表的操作和动态链表相似，只是以整型游标代替动态指针。以整型游标代替动态指针。设以设以SaSa表示静表示静态链表，通常可把态链表，通常可把Sa0Sa0理解为理解为“头结点头结点”，第第1 1个元素的位置由个元素的位置由Sa0.nextSa0.next指出指出,用全局用全局整型变量整型变量avav指出可利用空间的下标。指出可利用空间的下标。初始时将整个静态链表看作一个初始时将整个静态链表看作一个“空空表表”，操作中用，操作中用GetNode()GetNode()和和FreeNode()FreeNode()函函数模拟数模拟C C中的中的malloc()malloc()和和free()free()函数。以下函数。以下是初始化、取结点和释放结点是初始化、取结点和释放结点3 3个函数。个函数。数据结构线性表课件静态链表的初始化int Initilize()/*初始可利用空间表初始可利用空间表*/int i;for(i=0;imaxsize-1;i+)/链成可利用空间表链成可利用空间表 Sai.next=i+1;Samaxsize-1.next=-1;/*链表尾链表尾*/av=1;return av;/*返回可利用空间表的下标返回可利用空间表的下标*/数据结构线性表课件静态链表的申请结点空间int GetNode()/*取结点取结点*/if(av!=-1)/*-1表示无空间表示无空间*/p=av;av=Saav.next;/*p为可利用空间的下标为可利用空间的下标*/return p;数据结构线性表课件静态链表的释放结点空间int FreeNode(int p)/*将p归还到可利用空间表中*/Sap.next=av;av=p;return av;数据结构线性表课件静态链表的操作举例（1）（1）查找值为）查找值为x的结点的结点int Locate(SLinkedList SL,ElemType x)p=SL0.next;while(p!=-1&SLp.data!=x)p=SLp.next;return p;/元素下标 数据结构线性表课件静态链表的操作举例（2）(2)查找查找i第个结点第个结点ElemType Locate(SLinkedList SL,int i)int j=1;if(i0)printf(“参数错误参数错误”);exit(0);p=SL0.next;while(p!=-1&ji)p=SLp.next;j+;if(p=-1)printf(“参数错误参数错误”);exit(0);return SLi.data;数据结构线性表课件静态链表的操作举例（3）(3)插入第插入第i个结点个结点void Insert(SLinkedList SL,ElemType x,int i)pre=0;/*前驱前驱*/j=1;s=GetNode();if(s=-1)printf(“overflown”);exit(0);/*无空间无空间*/else p=SL0.next;while(p!=-1&j0*/pre=0;/*前驱前驱*/j=1;p=SL0.next;/*查找删除元素查找删除元素*/while(p!=-1&ji)j+;pre=p;p=SLp.next;if(p=-1)printf(“i is too big”);exit(0);/*i值太大值太大*/else SLpre.next=SLp.next;av=FreeNode(p);/*删除删除*/return av;数据结构线性表课件静态链表算法举例 设民航公司有一个自动预订飞机票的系统，该系统中设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表有一张用双重链表示的乘客表，表中结点按乘客姓氏的字，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。统写出一个当任一乘客要订票时修改乘客表的算法。序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8数据结构线性表课件静态链表算法举例void Insert（SLinkedList user,int av）user是静态双向链表，表示飞机票订票系统，元素包含是静态双向链表，表示飞机票订票系统，元素包含data、Llink和和Rlink三个域三个域 结点按来客姓名排序。本算法处理任一乘客订票申请。结点按来客姓名排序。本算法处理任一乘客订票申请。w scanf（“%s”，s）；s是字符数组，存放乘客姓名w strcopy（userav.data，s）；w p=1;p为工作指针（下标），p=0时表示链表尾w if(strcmp（userp.data，s）0）沿右链查找w while(p!=0&strcmp（userp.data，s）0）w pre=p;p=userp.Llink;w userav.Rlink=pre；userav.Llink=p；w 将新乘客链入表中w userpre.Llink=av;w if(p!=0)userp.Rlink=av;w w 算法结束