计算机软件基础优秀PPT.ppt

《计算机软件基础优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机软件基础优秀PPT.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY计算机计算机 软件基础软件基础其次篇数据结构基础其次篇数据结构基础第八章线性表（第八章线性表（第八章线性表（第八章线性表（linear listlinear listlinear listlinear list）桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY一、线性表的概念一、线性表的概念1.线性表的逻辑结构线性表的逻辑结构（1）线性表：是由）线性表：是由n（n 0）个数据节点个数据节点 a0，a1,，an-1

2、组成的组成的有限有限序列。序列。（2）线性表的逻辑结构特征：）线性表的逻辑结构特征：对于非空线性表：对于非空线性表：有且仅有一个起先节点，该节点有且仅有一个干有且仅有一个起先节点，该节点有且仅有一个干脆的后继；脆的后继；有且只有一个终结节点，该节点有且仅有一个干有且只有一个终结节点，该节点有且仅有一个干脆的前驱；脆的前驱；其余内部节点有且仅有一个干脆前驱和一个干脆其余内部节点有且仅有一个干脆前驱和一个干脆后继。后继。桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY一、线性表的概念一、线性表的概念（2）线性表的逻辑结构特征：）线

3、性表的逻辑结构特征：同一个线性表中的数据节点具有相同的属性。同一个线性表中的数据节点具有相同的属性。线性表长度：线性表中数据节点的个数。线性表长度：线性表中数据节点的个数。2.线性表的存储结构线性表的存储结构（1）依次存储结构：依次表结构；）依次存储结构：依次表结构；（2）链式存储结构：链表结构；）链式存储结构：链表结构；桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表1.依次表依次表（1）依次表：）依次表：把线性表中的数据节点按其逻辑依次依次存把线性表中的数据节点按其逻辑依次依次存放到计算机内存中的一连续

4、空间中，将这一连续放到计算机内存中的一连续空间中，将这一连续空间称为依次表。空间称为依次表。（2）依次表中数据节点地址的计算）依次表中数据节点地址的计算Loc(ai)=loc(a0)+i*d (0in-1)桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表1.依次表依次表（3）依次表）依次表C语言描述：语言描述：struct sequenliststruct sequenlist datatype alistsize;/datatype alistsize;/表示线性表有（表示线性表有（表示线性表有（表示线性

5、表有（a0a0，a1 a1，.，an-1an-1）int length;/length int length;/length表示线性表的实际长度表示线性表的实际长度表示线性表的实际长度表示线性表的实际长度;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表2.依次表的基本运算依次表的基本运算查找查找struct sequenlist /*struct sequenlist /*构建构建构建构建sequenlistsequenlist型型型型*/*/datatype datalistsize;datatype

6、datalistsize;int length;int length;struct sequenlist L;/*struct sequenlist L;/*定义定义定义定义sequenlistsequenlist变量变量变量变量L*/L*/int find(struct sequenlist L,datatype x)/*int find(struct sequenlist L,datatype x)/*定义定义定义定义findfind函数函数函数函数*/*/int i=0;int i=0;while(iL.length&L.datai!=x)i+;while(iL.length&L.dat

7、ai!=x)i+;if(iL.length)return(i);/*if(iL.length)return(i);/*假如找到了，则返回数值假如找到了，则返回数值假如找到了，则返回数值假如找到了，则返回数值i*/i*/else return(0);/*else return(0);/*假如找不到，则返回数值假如找不到，则返回数值假如找不到，则返回数值假如找不到，则返回数值0*/0*/桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一个完整的查找程序：一个完整的查找程序：#include#include#de

8、fine listsize 50#define listsize 50struct sequenlist /*struct sequenlist /*构建构建构建构建sequenlistsequenlist型型型型*/int datalistsize;int datalistsize;int length;int length;struct sequenlist L;/*struct sequenlist L;/*定义定义定义定义sequenlistsequenlist变量变量变量变量L*/L*/int find(struct sequenlist L,int x)/*int find(str

9、uct sequenlist L,int x)/*定义定义定义定义findfind函数函数函数函数*/int i=0;int i=0;while(iL.length&L.datai!=x)while(iL.length&L.datai!=x)i+;i+;if(iL.length)return(i);if(iL.length)return(i);else return(0);else return(0);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一个完整的查找程序（续）：一个完整的查找程序（续）：mai

10、n()main()int i,j,y;int i,j,y;struct sequenlist a;struct sequenlist a;scanf(%d,&a.length);/*scanf(%d,&a.length);/*输入实际表长输入实际表长输入实际表长输入实际表长*/scanf(%d,&j);/*scanf(%d,&j);/*输入要查找的数据输入要查找的数据输入要查找的数据输入要查找的数据*/for(i=0;ia.length;i+)for(i=0;i=listsze)printf(overflown);if(L.length=listsze)printf(overflown);el

11、se if(iL.length)printf(position is no correctn);else if(iL.length)printf(position is no correctn);elseelse for(j=L.length-1;j=i;j-)for(j=L.length-1;j=i;j-)L.dataj+1=L.dataj;L.dataj+1=L.dataj;L.datai=x;L.datai=x;L.length+;L.length+;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一

12、个完整的插入运算程序一个完整的插入运算程序#include#include#define listsze 10#define listsze 10struct sequenlist /*struct sequenlist /*构建构建构建构建sequenlistsequenlist型型型型*/int datalistsze;int datalistsze;int length;int length;struct sequenlist L;struct sequenlist L;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二

13、、依次表二、依次表一个完整的插入运算程序（续）一个完整的插入运算程序（续）void insert(struct sequenlist L,int x,int i)/*void insert(struct sequenlist L,int x,int i)/*定义定义定义定义insertinsert函数函数函数函数*/int j;int j;if(L.length=listsze)printf(overflown);if(L.length=listsze)printf(overflown);else if(iL.length)printf(position is no correctn);els

14、e if(iL.length)printf(position is no correctn);elseelse for(j=L.length-1;j=i;j-)for(j=L.length-1;j=i;j-)L.dataj+1=L.dataj;L.dataj+1=L.dataj;L.datai=x;L.datai=x;L.length+;L.length+;for(j=0;jL.length;j+)for(j=0;jL.length;j+)printf(%d,L.dataj);printf(%d,L.dataj);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELE

15、CTRONIC TECHNOLOGY二、依次表二、依次表一个完整的插入运算程序（续）一个完整的插入运算程序（续）main()main()int i,j,y;int i,j,y;struct sequenlist a;struct sequenlist a;scanf(%d,&a.length);/*scanf(%d,&a.length);/*输入实际表长输入实际表长输入实际表长输入实际表长*/scanf(%d,&y);/*scanf(%d,&y);/*输入要插入的数据输入要插入的数据输入要插入的数据输入要插入的数据*/scanf(%d,&j);/*scanf(%d,&j);/*输入要插入数据的

16、位置输入要插入数据的位置输入要插入数据的位置输入要插入数据的位置*/for(i=0;ia.length;i+)for(i=0;ia.length;i+)scanf(%d,&a.datai);scanf(%d,&a.datai);insert(a,y,j);insert(a,y,j);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表依次表插入运算的结论：依次表插入运算的结论：（1）在线性表中插入一个数据节点须要移动依次表）在线性表中插入一个数据节点须要移动依次表的一半节点，即：的一半节点，即：n/2。（2）时

17、间困难度：插入运算的时间困难度与）时间困难度：插入运算的时间困难度与n有关，有关，即：即：T(n)=O(n)。桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表3.依次表的基本运算依次表的基本运算删除删除step1:推断表是否为空？假如为空，则输出推断表是否为空？假如为空，则输出“无法删除无法删除”；否则进行其次步；否则进行其次步；step2:推断要删除的位置是否在表内？假如不在，则推断要删除的位置是否在表内？假如不在，则输出输出“位置不对位置不对”；否则进行第三步；否则进行第三步；step3:从第从第i+1

18、个节点到第个节点到第n-1个节点全部前移个节点全部前移1位（位（采采用覆盖的形式删除用覆盖的形式删除）；）；step4:将依次表的表长减去将依次表的表长减去1；桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表删除运算的类删除运算的类C语言算法：语言算法：void delete(struct sequenlist L ,int i)/*void delete(struct sequenlist L ,int i)/*定义定义定义定义deletedelete函数函数函数函数*/int j;int j;if(L.

19、length=0)printf(Empty list,can not delete!n);if(L.length=0)printf(Empty list,can not delete!n);else if(i=L.length)printf(position is no correctn);else if(i=L.length)printf(position is no correctn);else else for(j=i+1;jL.length;j+)for(j=i+1;jL.length;j+)L.dataj-1=L.dataj;L.dataj-1=L.dataj;L.length-;L

20、.length-;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一个完整的删除运算程序一个完整的删除运算程序#include /*#include /*调用头文件调用头文件调用头文件调用头文件“stidio.h”*/stidio.h”*/#define listsze 10#define listsze 10struct sequenlist /*struct sequenlist /*构建构建构建构建sequenlistsequenlist型型型型*/int datalistsze;int datali

21、stsze;int length;int length;struct sequenlist L;/*struct sequenlist L;/*定义定义定义定义sequenlistsequenlist变量变量变量变量L*/L*/桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一个完整的删除运算程序（续）一个完整的删除运算程序（续）void delete(struct sequenlist L ,int i)/*void delete(struct sequenlist L ,int i)/*定义定义定义定义

22、deletedelete函数函数函数函数*/int j;int j;if(L.length=0)printf(Empty list,can not delete!n);if(L.length=0)printf(Empty list,can not delete!n);else if(i=L.length)printf(position is no correctn);else if(i=L.length)printf(position is no correctn);else else for(j=i+1;jL.length;j+)for(j=i+1;jL.length;j+)L.dataj-

23、1=L.dataj;L.dataj-1=L.dataj;L.length-;L.length-;for(j=0;jL.length;j+)for(j=0;jL.length;j+)printf(%d,L.dataj);printf(%d,L.dataj);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY二、依次表二、依次表一个完整的删除运算程序（续）一个完整的删除运算程序（续）main()/*main()/*定义主函数定义主函数定义主函数定义主函数*/*/int i,j;int i,j;struct sequenlist a;

24、/*struct sequenlist a;/*定义依次表定义依次表定义依次表定义依次表a*/a*/scanf(%d,&a.length);/*scanf(%d,&a.length);/*输入实际表长输入实际表长输入实际表长输入实际表长*/*/scanf(%d,&j);/*scanf(%d,&j);/*输入要删除数据的位置输入要删除数据的位置输入要删除数据的位置输入要删除数据的位置*/*/for(i=0;ia.length;i+)/*for(i=0;inext!=null)/p while(p-next!=null)/p指针所指节点不是链表的最终一个节点指针所指节点不是链表的最终一个节点指针所

25、指节点不是链表的最终一个节点指针所指节点不是链表的最终一个节点 p=p-next;/p p=p-next;/p指针前进一个节点指针前进一个节点指针前进一个节点指针前进一个节点 n+;/n+;/节点个数加节点个数加节点个数加节点个数加1 1 return(n)/return(n)/返回表长返回表长返回表长返回表长n n 桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY6.查找运算（查找运算（find）struct node*find(head,x)struct node*find(head,x)struct node*p;str

26、uct node*p;p=head-next;/p p=head-next;/p指针指向第一个数据节点指针指向第一个数据节点指针指向第一个数据节点指针指向第一个数据节点 while(p-next!=null)&(p-data!=x)/p while(p-next!=null)&(p-data!=x)/p指针所节点不是最终节点，指针所节点不是最终节点，指针所节点不是最终节点，指针所节点不是最终节点，而且其而且其而且其而且其datadata域的值不为域的值不为域的值不为域的值不为x x p=p-next;/p p=p-next;/p前进一个节点前进一个节点前进一个节点前进一个节点 if(p-dat

27、a=x)return(p);/if(p-data=x)return(p);/找到了该节点，则返回对应找到了该节点，则返回对应找到了该节点，则返回对应找到了该节点，则返回对应p p指针的值指针的值指针的值指针的值 else return(null);/else return(null);/没找到该节点，则返回没找到该节点，则返回没找到该节点，则返回没找到该节点，则返回nullnull（空）（空）（空）（空）桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY7.插入运算（插入运算（insert）-插入已知插入已知地址地址的节点的节点

28、如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知地址为地址为s的节点的节点p pP-nextP-nexts s(1)(1)s-next=p-next;s-next=p-next;(2)(2)p-next=s;p-next=s;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY7.插入运算（插入运算（insert）-插入已知插入已知内容内容的节点的节点如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知内容为内容为x的节点的节点p pP-nextP-nexts s(1)(1)s-next=p-next;s-

29、next=p-next;(2)(2)P-next=s;P-next=s;s=(struct node)malloc(sizeof(struct node);s=(struct node)malloc(sizeof(struct node);s-data=x;s-data=x;x x桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY8.删除运算（删除运算（delete）如：删除如：删除p指针所指节点的下一个节点指针所指节点的下一个节点p pp-next-nextp-next-nextp-nextp-nextq=p-next;q=p

30、-next;q qq-nextq-nextp-next=p-next-next;p-next=p-next-next;（或（或（或（或p-next=q-nextp-next=q-next）free(q);free(q);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY四、单循环链表四、单循环链表1.单循环链表的形态单循环链表的形态非空表：非空表：a ab bmmheadhead空表：空表：headheadr r留意：留意：单链表只能沿着链表从前向后访问单链表只能沿着链表从前向后访问表中的各节点，表中的各节点，无法找到某节点前无

31、法找到某节点前面的其他节点面的其他节点；单循环链表可以通过任一节点访问单循环链表可以通过任一节点访问表中的其他节点。表中的其他节点。桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY四、单循环链表四、单循环链表2.单循环链表的删除运算单循环链表的删除运算例如：一个单循环链表，没有头指针只有尾指针例如：一个单循环链表，没有头指针只有尾指针r，试，试写出删除尾指针写出删除尾指针r的前一个节点。的前一个节点。a1a1an-2an-2ananr ra0a0an-1an-1桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY

32、 OF ELECTRONIC TECHNOLOGY四、单循环链表四、单循环链表2.单循环链表的删除运算单循环链表的删除运算a1a1an-2an-2ananr ra0a0an-1an-1Step1：找出：找出r节点前前的那个节点节点前前的那个节点p；Step2：让：让q指向指向 p的下一个节点；的下一个节点；Step3：从链表中删除：从链表中删除q所指向的节点；所指向的节点；Step3：回收：回收q。p pp-nextp-nextq qp-next-nextp-next-next桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY四

33、、单循环链表四、单循环链表2.单循环链表的删除运算单循环链表的删除运算void delete(r)void delete(r)struct node*p,*q;/struct node*p,*q;/定义两个定义两个定义两个定义两个nodenode型指针型指针型指针型指针p p和和和和q q p=r-next;/p=r-next;/让让让让p p指向指向指向指向r r的后继节点（给的后继节点（给的后继节点（给的后继节点（给p p赋初值）赋初值）赋初值）赋初值）while(p-next-next!=r)/while(p-next-next!=r)/找找找找r r节点的前前节点节点的前前节点节点的前

34、前节点节点的前前节点 p=p-next;p=p-next;q=p-next;/q=p-next;/将要删除节点的地址保存到将要删除节点的地址保存到将要删除节点的地址保存到将要删除节点的地址保存到q q中中中中 p-next=r;/p-next=r;/从链表中删除从链表中删除从链表中删除从链表中删除q q free(q);/free(q);/回收被删除节点回收被删除节点回收被删除节点回收被删除节点q q的空间的空间的空间的空间 桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表1.双循环链表的形态双循环

35、链表的形态h ha ab bc c非空表：非空表：h h空表：空表：桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表2.双循环链表的类型定义双循环链表的类型定义每个节点有每个节点有3个成员：个成员：priorpriordatadatanextnextprior：左链域，存放干脆前驱节点的地址；：左链域，存放干脆前驱节点的地址；next：右链域，存放干脆后继节点的地址；：右链域，存放干脆后继节点的地址；data：数据域，存放本节点的信息内容。数据域，存放本节点的信息内容。桂林电子科技大学桂林电子科技大

36、学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表2.双循环链表的类型定义双循环链表的类型定义struct nodestruct node datatype data;/datatype data;/节点的数据域节点的数据域节点的数据域节点的数据域 struct node *prior,*next;/struct node *prior,*next;/干脆前驱、后继的指针干脆前驱、后继的指针干脆前驱、后继的指针干脆前驱、后继的指针 3.双循环链表的特点双循环链表的特点:p-prior-next=p-next-prior=p桂林电子

37、科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表4.双循环链表的基本运算双循环链表的基本运算-插入插入例如：在例如：在p所指节点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。mmn nx xp pp-priorp-priors s(2)(2)(1)(1)(3)(3)(4)(4)桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表4.双循环链表的基本运算双循环链表的基本运算-插入插入例如：在例如：在p所指节

38、点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。(1)s-prior=p-prior;(1)s-prior=p-prior;(2)s-next=p;(2)s-next=p;(3)p-prior-next=s;(3)p-prior-next=s;(4)p-prior=s;(4)p-prior=s;桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY五、双循环链表五、双循环链表4.双循环链表的基本运算双循环链表的基本运算-删除删除例如：删除例如：删除p指针所指的节点指针所指的节点p pp-priorp-priorp-nex

39、tp-next(1)(1)(2)(2)(1)p-prior-next=p-next;(1)p-prior-next=p-next;(2)p-next-prior=p-(2)p-next-prior=p-prior;prior;(3)free(p);(3)free(p);桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY六、链表的建立六、链表的建立1.尾插法尾插法依次输入依次输入abc时，以尾插法建立的单链表为：时，以尾插法建立的单链表为：headheada ab b2.头插法头插法依次输入依次输入abc时，以头插法建立的单链表为

40、：时，以头插法建立的单链表为：c cheadheadc cb ba a桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY历年真题演练历年真题演练1.（2010.4单选）对依次存储的线性表，其长度为单选）对依次存储的线性表，其长度为n，在等概率状况下，插入一个数据节点须要移动数据节在等概率状况下，插入一个数据节点须要移动数据节点的平均次数是（点的平均次数是（）。）。A n/2 B n-1 C (n+1)/2 D (n-1)/22.（2010.4单选）线性表接受链式存储时，其存储空间单选）线性表接受链式存储时，其存储空间是（是（）。

41、）。A 必需是连续的必需是连续的 B 确定是不连续的确定是不连续的 C 可连续，也可不连续可连续，也可不连续 D 多个节点地址必需连续多个节点地址必需连续桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY历年真题演练历年真题演练3.（2010.4填空）已知填空）已知q指向单链表中一个节点，若在指向单链表中一个节点，若在q 指向的节点之后插入一个指向的节点之后插入一个s指向的新节点，则所须要指向的新节点，则所须要的两步是的两步是s-next=q-next;。桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF

42、ELECTRONIC TECHNOLOGY历年真题演练历年真题演练4.（2010.4程序设计）已知下面链表节点类型，设计一程序设计）已知下面链表节点类型，设计一个算法个算法dellinklist，删除以，删除以head为头指针的单链表（带为头指针的单链表（带头节点）中数据为头节点）中数据为x的节点。的节点。struct nodestruct node int data;int data;struct node*nexy;struct node*nexy;；桂林电子科技大学桂林电子科技大学GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY历年真题演练历年真题演练

43、4.（答案：（答案：void dellinklist(struct node*head,int x)void dellinklist(struct node*head,int x)struct node*p,*q;struct node*p,*q;if(head=null|head-next=null)return;if(head=null|head-next=null)return;q=head;q=head;p=q-next;p=q-next;while(p!=null)&(p-data!=x)while(p!=null)&(p-data!=x)q=p;q=p;p=p-next;p=p-next;if(p-data=x)if(p-data=x)q-next=p-next;q-next=p-next;free(p);free(p);else printf(no find x!/n);else printf(no find x!/n);