ds200902-线性表.ppt

数据结构数据结构北京化工大学北京化工大学信息科学与技术学院计算机系信息科学与技术学院计算机系史晟辉史晟辉n n线性表线性表n n顺序表顺序表 n n链表链表n n顺序表与链表的比较顺序表与链表的比较第二章第二章 线性表线性表5/25/20242北京化工大学信息学院 数据结构线性表线性表(Linear List)n n线性表的定义和特点线性表的定义和特点uu 定义定义 n n（0 0）个数据元素的有限序列，记作个数据元素的有限序列，记作个数据元素的有限序列，记作个数据元素的有限序列，记作 （a1,a2,ana1,a2,an）aiai 是表中数据元素，是表中数据元素，是表中数据元素，是表中数据元素，n n 是表长度。是表长度。是表长度。是表长度。vv除第一个元素外，其他每一个元素有一个且仅有一除第一个元素外，其他每一个元素有一个且仅有一除第一个元素外，其他每一个元素有一个且仅有一除第一个元素外，其他每一个元素有一个且仅有一个个个个直接前驱直接前驱直接前驱直接前驱。vv除最后一个元素外，其他每一个元素有一个且仅有除最后一个元素外，其他每一个元素有一个且仅有除最后一个元素外，其他每一个元素有一个且仅有除最后一个元素外，其他每一个元素有一个且仅有一个一个一个一个直接后继直接后继直接后继直接后继。uu 特点特点 5/25/20243北京化工大学信息学院 数据结构顺序表顺序表(Sequential List)n n顺序表的定义顺序表的定义顺序表的定义顺序表的定义n n顺序表的特点顺序表的特点顺序表的特点顺序表的特点n n顺序表的连续存储方式顺序表的连续存储方式顺序表的连续存储方式顺序表的连续存储方式n n顺序表顺序表顺序表顺序表(SeqListSeqList)的定义的定义的定义的定义n n顺序表顺序表顺序表顺序表(SeqListSeqList)的的的的操作操作操作操作n n顺序表的应用顺序表的应用顺序表的应用顺序表的应用数据对象数据对象数据对象数据对象逻辑关系逻辑关系逻辑关系逻辑关系存储关系存储关系存储关系存储关系操作操作操作操作5/25/20244北京化工大学信息学院 数据结构顺序表顺序表(Sequential List)n n顺序表的定义和特点顺序表的定义和特点uu 定义定义 将线性表中的元素相继存放在一将线性表中的元素相继存放在一个连续的存储空间中。个连续的存储空间中。uu 可利用一维数组描述存储结构可利用一维数组描述存储结构uu 特点特点 线性表的顺序存储方式线性表的顺序存储方式uu 遍历遍历 顺序访问顺序访问,可以随机存取可以随机存取 25 34 57 16 48 09 0 1 2 3 4 5 0 1 2 3 4 5 data5/25/20245北京化工大学信息学院 数据结构顺序表的连续存储方式顺序表的连续存储方式35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(i)=LOC(i-1)+l=a+i*l,i 0 a,i=0 a+i*la5/25/20246北京化工大学信息学院 数据结构顺序表顺序表(SeqList)的定义的定义#define ListSize 100 /最大允许长度最大允许长度typedef int ListData;typedef struct ListData *data;/存储数组存储数组 int length;/当前元素个数当前元素个数 SeqList;5/25/20247北京化工大学信息学院 数据结构顺序表的操作顺序表的操作n n建立空的顺序表建立空的顺序表建立空的顺序表建立空的顺序表n n求表的长度求表的长度求表的长度求表的长度n n按位置查找按位置查找按位置查找按位置查找n n按值查找按值查找按值查找按值查找n n顺序表的插入顺序表的插入顺序表的插入顺序表的插入n n顺序表的删除顺序表的删除顺序表的删除顺序表的删除5/25/20248北京化工大学信息学院 数据结构建立空的顺序表建立空的顺序表 voidvoid InitListInitList (SeqListSeqList&L)L)L.data=(L.data=(ListData ListData*)*)malloc malloc (ListSize ListSize*sizeof sizeof (ListData ListData);if if(L.data(L.data=NULL)NULL)printfprintf (“(“存储分配失败存储分配失败存储分配失败存储分配失败!n”n”);exit exit(1)(1);L.length=0 L.length=0;5/25/20249北京化工大学信息学院 数据结构n n 求表的长度求表的长度 int Length(SeqList&L)return L.length;n n按位置查找：在表中提取第按位置查找：在表中提取第 i 个元素的值个元素的值 ListData GetData(SeqList&L,int i)if (i=0&i L.length)return L.datai;else printf(“参数 i 不合理！n”);/在出错情况，函数返回值不能用！5/25/202410北京化工大学信息学院 数据结构int Find(SeqList&L,ListData x)int i=0;while(i L.length&L.datai!=x)i+;if(i L.length)return i;else return-1;（在顺序表中从头查找结点值等于给定值（在顺序表中从头查找结点值等于给定值（在顺序表中从头查找结点值等于给定值（在顺序表中从头查找结点值等于给定值 x x 的结点）的结点）的结点）的结点）按值查找按值查找5/25/202411北京化工大学信息学院 数据结构顺序查找图示顺序查找图示25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功5/25/202412北京化工大学信息学院 数据结构25 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失败查找失败5/25/202413北京化工大学信息学院 数据结构查找成功的平均比较次数查找成功的平均比较次数 若查找概率相等，则若查找概率相等，则查找不成功查找不成功 数据比较数据比较 n 次次5/25/202414北京化工大学信息学院 数据结构顺序表的插入顺序表的插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data50i5/25/202415北京化工大学信息学院 数据结构int Insert(SeqList&L,ListData x,int i)/在表中第 i 个位置插入新元素 x if(i L.length|L.length=ListSize)return 0;/插入不成功 else for(int j=L.length;j i;j-)L.dataj=L.dataj-1;L.datai=x;L.length+;return 1;/插入成功 顺序表的插入顺序表的插入5/25/202416北京化工大学信息学院 数据结构顺序表的删除顺序表的删除25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7data5/25/202417北京化工大学信息学院 数据结构int Delete(SeqList&L,ListData x)/在表中删除已有元素 x int i=Find(L,x);/在表中查找 x if(i=0)L.length-;for(int j=i;j L.length;j+)L.dataj=L.dataj+1;return 1;/成功删除 return 0;/表中没有 x 顺序表的删除顺序表的删除5/25/202418北京化工大学信息学院 数据结构顺序表的应用：集合的顺序表的应用：集合的“并并”运算运算void Union(SeqList&A,SeqList&B)int n=Length(A);int m=Length(B);for(int i=0;i m;i+)int x=GetData(B,i);/在B中取一元素 int k=Find(A,x);/在A中查找它 if(k=-1)/若未找到插入它 Insert(A,x,n);n+;5/25/202419北京化工大学信息学院 数据结构 void Intersection(SeqList&A,SeqList&B)int n=Length(A);int m=Length(B);int i=0;while(i-link=first;link=first;first=first=newnodenewnode;（插入前）（插入前）firstnewnodenewnodefirst（插入后）（插入后）5/25/202426北京化工大学信息学院 数据结构 uu 第二种情况：在链表中间插入第二种情况：在链表中间插入第二种情况：在链表中间插入第二种情况：在链表中间插入 newnodenewnode-link=plink=p-link;link;p p-link=link=newnode newnode；(插入前插入前)newnodeppnewnode(插入后插入后)5/25/202427北京化工大学信息学院 数据结构uu 第三种情况：在链表末尾插入第三种情况：在链表末尾插入第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newnodenewnode-link=plink=p-link;link;p p-link=link=newnodenewnode；(插入前插入前)newnodep newnodep(插入后插入后)5/25/202428北京化工大学信息学院 数据结构int Insert(LinkList&first,int x,int i)/在链表第 i 个结点处插入新元素 x ListNode*p=first;int k=0;while(p!=NULL&k link;k+;/找第 i-1个结点 if(p=NULL&first!=NULL)printf(“无效的插入位置!n”);return 0;ListNode*newnode=/创建新结点 (ListNode*)malloc(sizeof(ListNode);5/25/202429北京化工大学信息学院 数据结构 newnode-data=x;if(first=NULL|i=1)/插在表前 newnode-link=first;first=newnode;else /插在表中或末尾 newnode-link=p-link;p-link=newnode;return 1;5/25/202430北京化工大学信息学院 数据结构n n删除删除uu第一种情况第一种情况第一种情况第一种情况:删除表中第一个元素删除表中第一个元素删除表中第一个元素删除表中第一个元素uu第二种情况第二种情况第二种情况第二种情况:删除表中或表尾元素删除表中或表尾元素删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含ai的结点的结点ai-1aiai+1删除前删除前ai-1aiai+1pq删除后删除后5/25/202431北京化工大学信息学院 数据结构int Delete(LinkList&first,int i)/在链表中删除第 i 个结点 ListNode*p,*q;if(i=1)/删除表中第 1 个结点 q=first;first=first-link;else p=first;int k=0;/找第 i-1个结点 while(p!=NULL&k link;k+;5/25/202432北京化工大学信息学院 数据结构 if(p=NULL|p-link=NULL)printf(“无效的删除位置!n”);return 0;else /删除表中或表尾元素 q=p-link;/重新链接 p-link=q-link;free(q);/删除q return 1;5/25/202433北京化工大学信息学院 数据结构带表头结点的单链表带表头结点的单链表n n表头结点位于表的最前端，本身不带数据，表头结点位于表的最前端，本身不带数据，表头结点位于表的最前端，本身不带数据，表头结点位于表的最前端，本身不带数据，仅标仅标仅标仅标志表头志表头志表头志表头。n n设置表头结点的目的是设置表头结点的目的是设置表头结点的目的是设置表头结点的目的是uu统一空表与非空表的操作统一空表与非空表的操作统一空表与非空表的操作统一空表与非空表的操作uu简化链表操作的实现。简化链表操作的实现。简化链表操作的实现。简化链表操作的实现。非空表非空表 空表空表0ana1firstfirst05/25/202434北京化工大学信息学院 数据结构在带表头结点的单链表在带表头结点的单链表 第一个结点前插入新结点第一个结点前插入新结点 newnode-link=p-link;p-link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp5/25/202435北京化工大学信息学院 数据结构 q=p-link;p-link=q-link;free q;从带表头结点的单链表中删除第一个结点从带表头结点的单链表中删除第一个结点firstfirst(非空表）非空表）first0first(空表）空表）0pqpq5/25/202436北京化工大学信息学院 数据结构前插法建立单链表前插法建立单链表n n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：uu生成新结点生成新结点生成新结点生成新结点uu将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中uu将该新结点插入到链表的前端将该新结点插入到链表的前端将该新结点插入到链表的前端将该新结点插入到链表的前端n n直到读入结束符为止直到读入结束符为止直到读入结束符为止直到读入结束符为止。firstnewnodefirstnewnode005/25/202437北京化工大学信息学院 数据结构LinkList createListF(void)char ch;ListNode*s;LinkList head=/建立表头结点 (LinkList)malloc(sizeof(ListNode);head-link=NULL;while(ch=getchar()!=n)s=(listNode*)malloc(sizeof(ListNode);s-data=ch;/建立新结点 s-link=head-link;/插入到表前端 head-link=s;return head;5/25/202438北京化工大学信息学院 数据结构后插法建立单链表后插法建立单链表n n每次将新结点加在链表的表尾；每次将新结点加在链表的表尾；每次将新结点加在链表的表尾；每次将新结点加在链表的表尾；n n设置一个尾指针设置一个尾指针设置一个尾指针设置一个尾指针 r r，总是指向表中最后一个结总是指向表中最后一个结总是指向表中最后一个结总是指向表中最后一个结点，新结点插在它的后面；点，新结点插在它的后面；点，新结点插在它的后面；点，新结点插在它的后面；n n尾指针尾指针尾指针尾指针 r r 初始时置为指向表头结点地址。初始时置为指向表头结点地址。初始时置为指向表头结点地址。初始时置为指向表头结点地址。00newnodefirstnewnode00rrrr5/25/202439北京化工大学信息学院 数据结构LinkList createListR(void)char ch;LinkList head=/建立表头结点 (LinkList)malloc(sizeof(ListNode);ListNode*s,*r=head;/r指向表尾 while(ch=getchar()!=n)s=(listNode*)malloc(sizeof(ListNode);s-data=ch;/建立新结点 r-link=s;r=s;/插入到表末端 r-link=NULL;/表收尾 return head;5/25/202440北京化工大学信息学院 数据结构firstqfirstfirstqqfirsta0a1a1a2a2a2单链表清空单链表清空5/25/202441北京化工大学信息学院 数据结构单链表清空单链表清空void void makeEmptymakeEmpty(LinkListLinkList first)first)/删去链表中除表头结点外的所有其他结点删去链表中除表头结点外的所有其他结点删去链表中除表头结点外的所有其他结点删去链表中除表头结点外的所有其他结点 ListNodeListNode*q*q;while while(first(first-link!=NULL)link!=NULL)q=first q=first-linklink;first first-link=qlink=q-linklink;/将表头结点后第一个结点从链中摘下将表头结点后第一个结点从链中摘下将表头结点后第一个结点从链中摘下将表头结点后第一个结点从链中摘下 free(q)free(q);/释放它释放它释放它释放它 5/25/202442北京化工大学信息学院 数据结构firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3计算单链表长度计算单链表长度5/25/202443北京化工大学信息学院 数据结构int Length(LinkList first)ListNode*p=first-link;/检测指针 p 指示第一个结点 int count=0;while(p!=NULL)/逐个结点检测 p=p-link;count+;return count;计算单链表长度计算单链表长度5/25/202444北京化工大学信息学院 数据结构ListNode*Find(LinkList first,ListData value)/在链表中从头搜索其数据值为value的结点 ListNode*p=first-link;/检测指针 p 指示第一个结点 while(p!=NULL&p-data!=value)p=p-link;return p;在单链表中按值查找在单链表中按值查找5/25/202445北京化工大学信息学院 数据结构ListNodeListNode*Locate(*Locate(LinkListLinkList first,first,intint i)i)/返回表中第返回表中第返回表中第返回表中第 i i 个元素的地址个元素的地址个元素的地址个元素的地址 if if(i (i 0)0)return return NULL NULL;/;/i/i 值不合理值不合理值不合理值不合理 ListNodeListNode*p=first*p=first;int int k=k=0 0;/;/置于表头置于表头置于表头置于表头 while while(p!=NULL(p!=NULL&k i)k-linklink;k+k+;/找第找第找第找第 i i 个结点个结点个结点个结点 if if (k=i)(k=i)return return p p;else returnelse return NULL NULL;/返回第返回第返回第返回第 i i 个结点地址或个结点地址或个结点地址或个结点地址或NULLNULL 在单链表中按序号查找（定位）在单链表中按序号查找（定位）5/25/202446北京化工大学信息学院 数据结构在单链表中插入新结点在单链表中插入新结点 newnode-link=p-link;p-link=newnode;firstnewnodefirstnewnode插入newnodenewnode插入pppp5/25/202447北京化工大学信息学院 数据结构intint Insert(Insert(LinkList LinkList first,first,ListDataListData x,x,intint i)i)/将新元素将新元素将新元素将新元素 x x 插入在链表中第插入在链表中第插入在链表中第插入在链表中第 i i 号结点位置号结点位置号结点位置号结点位置 ListNodeListNode*p=Locate(first,i-1)*p=Locate(first,i-1);if if(p (p=NULL)NULL)return return 0 0;/不插入不插入不插入不插入 ListNodeListNode*newnodenewnode=/创建新结点创建新结点创建新结点创建新结点 (ListNode ListNode*)*)mallocmalloc (sizeofsizeof(ListNodeListNode);newnode newnode-data=xdata=x;newnode newnode-link=plink=p-link;/link;/链入链入链入链入 p p-link=link=newnodenewnode;return return 1 1;/插入成功，函数返回插入成功，函数返回插入成功，函数返回插入成功，函数返回1 1 在单链表中插入新元素在单链表中插入新元素5/25/202448北京化工大学信息学院 数据结构在单链表中删除一个结点在单链表中删除一个结点 q=p-link;p-link=q-link;delete q;first0firstpppqqq5/25/202449北京化工大学信息学院 数据结构intint delete(delete(LinkListLinkList first,first,intint i)i)/将链表第将链表第将链表第将链表第 i i 号元素删去号元素删去号元素删去号元素删去 ListNodeListNode*p=Locate(first,i*p=Locate(first,i-1)1);/寻找被删结点的前驱结点寻找被删结点的前驱结点寻找被删结点的前驱结点寻找被删结点的前驱结点 if if(p (p=NULL|p NULL|p-link=NULL)link=NULL)return return 0 0;/不删除不删除不删除不删除 ListNodeListNode*q=p*q=p-linklink;/被删结点地址被删结点地址被删结点地址被删结点地址 p p-link=qlink=q-linklink;/摘下被删结点摘下被删结点摘下被删结点摘下被删结点 free free(q(q );/释放释放释放释放 returnreturn l l;在单链表中删除一个结点在单链表中删除一个结点5/25/202450北京化工大学信息学院 数据结构【例例例例】单链表求和函数单链表求和函数单链表求和函数单链表求和函数 typedef typedef intint ListDataListData;intint sum(sum(LinkList lsLinkList ls)ListNodeListNode*p=*p=ls ls-linklink;int int retvalue retvalue=0=0;while while(p!=NULL)(p!=NULL)retvalue retvalue+=p+=p-datadata;/累加累加累加累加 p=pp=p-linklink;returnreturn retvalue retvalue;5/25/202451北京化工大学信息学院 数据结构循环链表循环链表(Circular List)n n循环链表是单链表的变形。循环链表是单链表的变形。循环链表是单链表的变形。循环链表是单链表的变形。n n循环链表最后一个结点的循环链表最后一个结点的循环链表最后一个结点的循环链表最后一个结点的 linklink 指针不指针不指针不指针不 为为为为NULLNULL，而是指向了表的前端。而是指向了表的前端。而是指向了表的前端。而是指向了表的前端。n n为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。n n循环链表的特点是：只要知道表中某一结点的地循环链表的特点是：只要知道表中某一结点的地循环链表的特点是：只要知道表中某一结点的地循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。址，就可搜寻到所有其他结点的地址。址，就可搜寻到所有其他结点的地址。址，就可搜寻到所有其他结点的地址。5/25/202452北京化工大学信息学院 数据结构n n循环链表的示例循环链表的示例n n带表头结点的循环链表带表头结点的循环链表 a0a1a2an-1firstan-1firsta1a0first(空表空表)(非空表非空表)5/25/202453北京化工大学信息学院 数据结构查找成功查找成功查找不成功查找不成功循环链表的查找循环链表的查找firstfirst3131484815155757查找查找15 查找查找25 pppppppp5/25/202454北京化工大学信息学院 数据结构循环链表的定义循环链表的定义typedef char ListData;typedef struct cnode /链表结点链表结点 ListData data;/结点数据域结点数据域 struct cnode*link;/结点链域结点链域 CircListNode;typedef CircListNode*CircLinkList;/循环循环链表头指针链表头指针CircLinkList first;/循环循环链表头指针链表头指针5/25/202455北京化工大学信息学院 数据结构循环链表的查找算法循环链表的查找算法CircListNode*Find(CircLinkList first,ListData value)/在链表中从头搜索其数据值为value的结点 CircListNode*p=first-link;/检测指针 p 指示第一个结点 while(p!=first&p-data!=value)p=p-link;return p;5/25/202456北京化工大学信息学院 数据结构双向链表双向链表(Doubly Linked List)n n双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。n n双向链表每个结点结构：n n双向链表通常采用带表头结点的循环链表形式。前驱方向前驱方向 后继方向后继方向prior data next5/25/202457北京化工大学信息学院 数据结构n n结点指向结点指向结点指向结点指向p=pp=p-priorprior-next=pnext=p-nextnext-priorprior非空表非空表 空表空表p-priorp-nextppriornextfirstfirst5/25/202458北京化工大学信息学院 数据结构双向循环链表的定义双向循环链表的定义typedef inttypedef int ListData ListData;typedef structtypedef struct dnode dnode ListNodeListNode data data;/数据数据数据数据 structstruct dnode dnode*prior,*next*prior,*next;/指针指针指针指针 DblNodeDblNode;typedef typedef DblNode DblNode*DblListDblList;/双向链表双向链表双向链表双向链表 5/25/202459北京化工大学信息学院 数据结构建立空的双向循环链表建立空的双向循环链表voidvoid CreateDblListCreateDblList(DblListDblList&first)first)first=(first=(DblNode DblNode*)*)mallocmalloc (sizeofsizeof (DblNodeDblNode);if if(first (first=NULL)NULL)print(“print(“存储分配错存储分配错存储分配错存储分配错!n”)n”);exit;exit(1)(1);first first-prior=firstprior=first-next=firstnext=first;/表头结点的链指针指向自己表头结点的链指针指向自己表头结点的链指针指向自己表头结点的链指针指向自己 5/25/202460北京化工大学信息学院 数据结构计算双向循环链表的长度计算双向循环链表的长度intint Length(Length(DblListDblList first)first)/计算带表头结点的双向循环链表的长度计算带表头结点的双向循环链表的长度计算带表头结点的双向循环链表的长度计算带表头结点的双向循环链表的长度 DblNodeDblNode*p=first*p=first-nextnext;intint count=0 count=0;while while(p!=first)(p!=first)p=pp=p-nextnext;count+count+;return return count count;5/25/202461北京化工大学信息学院 数据结构查找成功查找成功查找不成功查找不成功双向循环链表的查找双向循环链表的查找firstfirst3131484815155757查找查找15 查找查找25 5/25/202462北京化工大学信息学院 数据结构ListNode*Find(DblList first,ListData x)/在双向循环链表中搜索含 x 的结点,若找到,/则返回该结点的地址,否则返回表头地址。DblNode*p=first-next;while(p!=first&p-data!=x)p=p-next;return p;/也可以在也可以在 prior(前驱前驱)方向查找方向查找,程序类似。程序类似。5/25/202463北京化工大学信息学院 数据结构DblNode*Locate(DblList first,int i)if(i next;int j=1;while(p!=first&j next;j+;return p;/也可以在也可以在 prior(前驱前驱)方向查找方向查找,程序类似。程序类似。定位：查找第定位：查找第 i 个结点在链中的位置个结点在链中的位置5/25/202464北京化工大学信息学院 数据结构双向循环链表的插入双向循环链表的插入(非空表非空表)firstfirst314815在结点在结点在结点在结点 *p 后插入后插入后插入后插入25pp31482515q-prior=p;q-next=p-next;p-next=q;q-next-prior=q;q5/25/202465北京化工大学信息学院 数据结构双向循环链表的插入双向循环链表的插入(空表空表)first在结点在结点*p 后插入后插入25pq25q-prior=p;q-next=p-next;(=first)p-next=q;q-next-prior=q;(first-prior=q)firstp5/25/202466北京化工大学信息学院 数据结构int Insert(DblList first,int i,ListData x)DblNode*p=Locate(first,i-1);/指针定位于插入位置 if(p=first&i!=1)return 0;DblNode*q=(DblNode*)malloc (sizeof(DblNode);/分配结点 q-data=x;q-prior=p;p-next-prior=q;/在前驱方向链入新结点 q-next=p-next;p-next=q;/在后继方向链入新结点 return 1;5/25/202467北京化工大学信息学院 数据结构删除删除48双向循环链表的删除双向循环链表的删除firstfirst非空表非空表314815p3115p-next-prior=p-prior;p-prior-next=p-next;5/25/202468北京化工大学信息学院 数据结构删除删除31双向循环链表的删除双向循环链表的删除firstfirst31pp-next-prior=p-prior;p-prior-next=p-next;5/25/202469北京化工大学信息学院 数据结构int Remove(DblList first,int i)DblNode*p=Locate(first,i);/指针定位于删除结点位置指针定位于删除结点位置 if(p=first)return 0;p-next-prior=p-prior;p-prior-next=p-next;/将被删结点将被删结点*p 从链上摘下从链上摘下 free(p);/删去删去 return 1;5/25/202470北京化工大学信息学院 数据结构顺序表与链表的比较顺序表与链表的比较基于空间的比较基于空间的比较n n存储分配的方式存储分配的方式uu顺序表的存储空间是顺序表的存储空间是静态分配静态分配的的uu链表的存储空间是链表的存储空间是动态分配动态分配的的n n存储密度存储密度=结点数据本身所占的存储量结点数据本身所占的存储量/结点结点结构所占的存储总量结构所占的存储总量uu顺序表的存储密度顺序表的存储密度=1=1uu链表的存储密度链表的存储密度 1 next;A-next=NULL;while(p!=NULL)ListNode*q=p;p=p-next;q-next=A-next;A-next=q;return 1;5/25/202474北京化工大学信息学院 数据结构试题分析试题分析例例2.已知顺序结构线性表的结构定义如下，且表中的元素按已知顺序结构线性表的结构定义如下，且表中的元素按非降序排列：非降序排列：struct SListstruct SList int int bufferMAXLENGTH;bufferMAXLENGTH;int tablelen int tablelen;请编写高效算法，删除表中的重复元素。请编写高效算法，删除表中的重复元素。如，若原表为如，若原表为(1,1,2,3,3,3,4,5,5)，经，经过算法处理后，表为过算法处理后，表为(1,2,3,4,5)。参考算法代码形式如下：参考算法代码形式如下：int PackSList(SList&L).5/25/202475北京化工大学信息学院 数据结构参考代码如下：参考代码如下：int PackSList(SList&L)int i,j;for(i=0;iL.tablelen-1;i+)if(L.bufferi=L.bufferi+1)break;for(j=i+1;jL.tablelen;j+)if(L.bufferj!=L.bufferi)i+;L.bufferi=L.bufferj;L.tablelen=i+1;return 1;5/25/202476北京化工大学信息学院 数据结构Thanks.5/25/202477北京化工大学信息学院 数据结构