数据结构C语言 胡学钢线性表.pptx

《数据结构C语言 胡学钢线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言 胡学钢线性表.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第二章 线性表 第二章 线性表 2.1 线性表的定义和运算 2.2 顺序表 2.3 链表 2.4 其它结构形式的链表 2.5 串 第1页/共43页22.1 线性表的定义和运算 p定义：线性表L是由n个元素a1，a2，an组成的 有限 序列。记作 L=（a1，a2，an）其中n=0为表长；n=0时为L空表，记作L=（）p特性：A、只有一个第一个元素和一个最后一个元素；B、除第一个元素外其他元素有且仅有一个直接前趋（前驱）；C、除最后一个元素外其他元素有且仅有一个直接后继p元素ai的含义：同一表中，元素类型相同。在不同的场合有不同的含义 例：字母表（A，B，C，D，Z）；数字表（0，1，2，3，

2、4，9）；每月天数（31,29,31,30,31,30,31,31,30,31,30,31）;第2页/共43页32.1 线性表的定义和运算 运算：(1)初始化 initial_List(L)建立线性表的初始结构，即建空表 (2)求长度 List_length(L)即求表中的元素个数(3)按序号取元素 get_element(L,i)取出表中序号为i的元素(4)按值查找元素 List_locate(L,x)取出指定值为x的元素，若存在则返回其地址；否则返回特殊值(5)插入 List_insert(L,i,x)在表L的第i个位置上插入值为x的元素(1=i=n+1)(6)删除 List_delete

3、（L,i）删除表L中序号为i的元素1=ilistlen=0;int List_length（seqlist L）return L.listlen;void get_element（seqlist L，int i,elementtype&x）if（i L.listlen）error(“超出范围”);else x=L.datai-1;int List_locate（seqlist L，elementtype x）int i;for(i=0;ilistlen=maxlen）error（“overflow”）;else if（iL-listlen+1）error(“position error”）;e

4、lse for（j=L-listlen-1;j=i-1;j-）L-dataj+1=L-dataj;L-datai-1=x;L-listlen+;a1 a2 a3 ai an 0 1 2 i-1 n-1 maxlen-1x条件：顺序表不满；序号正确，在1,n+1中操作：ai an后移;填入x;listlen+算法分析第6页/共43页72.2 顺序表 删除void List_delete(seqlist*L,int i)int j;if(L-listlenL-listlen|i=0)error(“删除位置出错”);else for(j=i;jlistlen-1;j+)L-data j-1=L-da

5、ta j;L-listlen-;a1 a2 a3 ai an 0 1 2 i-1 n-1 maxlen-1算法分析第7页/共43页82.2 顺序表算法分析：插入时 在i=1,2,n+1，元素移动的次数分别为n,n-1,0。在等概率的情况下，平均移动(n+1)n/2(n+1)=n/2次删除时 在i=1,2,n，元素移动的次数分别为n-1,n-2,0。在等概率的情况下，平均移动(n-1)n/2n=(n-1)/2次结论：n较大时，大量移动元素，耗时解决：考虑不移动元素教材P17例第8页/共43页92.3 链表基本结构以链接形式连接元素次序。a1a2a3a4 L=(a1,a2,a3,a4)结点包括 元

6、素和地址。datanext第9页/共43页102.3 链表存储实现（静态链表）1、静态链表用数组C3A2B0D5F-1E4data next012345L=(A,B,C,D,E,F)head第10页/共43页112.3 链表存储实现（动态链表）2、动态链表用指针和动态变量实现（1）结点结构datanext（2）类型定义 typedef struct elementtype data;node *next;node;引用：node *head；第11页/共43页122.3 链表图例a1a2a3a4 Head*HeadHead-next首元素第12页/共43页132.3 链表基本运算 运算：(1)

7、初始化 initial_List(L)建立表的初始结构，即建空表 (2)求长度 List_length(L)即求表中的元素个数(3)按序号取元素 get_element(L,i)取出表中序号为i的元素(4)按值查找元素 List_locate(L,x)取出指定值为x的元素，若存在则返回其地址；否则返回特殊值(5)插入 List_insert(L,i,x)在表L的第i个位置上插入值为x的元素(1=i=n+1)(6)删除 List_delete（L,i）删除表L中序号为i的元素1=inext=P-next;P-next=S;注意：两个操作不能交换p如果是作为第一个结点插入，过程如下：S-next=

8、head;head=S;a1a2a3 a4 headxS第14页/共43页152.3 链表讨论(引入头结点)为保持插入操作一致，引入头结点。注意：头结点与首元素的区别。a1a2a3 xheadSPS-next=P-next;P-next=S;第15页/共43页162.3 链表讨论(删除操作)p删除（一般位置）：假设被删除的前一个结点的指针P已找到：Pa1a2a3a5 heada4 P-next=P-next-next;p如果是删除第一个结点，过程如下：head=head-next;a1a2a3a5 heada4 p讨论结果：引入头结点P-next=P-next-next;a1a2a4 head

9、a3 P第16页/共43页172.3 链表运算的实现（有头结点）1、初始化单链表（建空表）Lvoid initial_List(node&*L)L=new node;/L=(node*)malloc(sizeof(node);L-next=NULL;第17页/共43页182.3 链表求表长（1）2、求单链表表长a1a2a3 LPlen=0P=L-next;len=0;P!=NULLreturn(len);P=P-next;len+;YNint List_length(node *L)P=L-next;len=0;while(P!=NULL)P=P-next;len+;return(len);第

10、18页/共43页192.3 链表求表长（2）2、求单链表表长a1a2a3 Lint List_length(node *L)P=L;len=0;while(P-next!=NULL)P=P-next;len+;return(len);Plen=0P=L;len=0;P-next!=NULLreturn(len);P=P-next;len+;YN第19页/共43页202.3 链表按序号取值3、按序号取值返回指向结点的指针,否则返回NULLa1a2a3 LPj=0node*get(node*L,int i)node*get(node*L,int i)P=L;j=0;P=L;j=0;while(P-

11、next!=NULL&j!=i)while(P-next!=NULL&j!=i)P=P-next;j+;P=P-next;j+;return(P);return(P);P=L;j=0;P-next!=NULLreturn(P);P=P-next;j+;YNj=iYNreturn(P);第20页/共43页212.3 链表按值查询 4、按值查询 返回元素结点指针，否则返回NULL；a1a2a3 LPP=L-next;P-data!=xreturn(P);P=P-next;YNP!=NULLNYreturn(P);node*locate(node*L,elementtype x)P=L-next;w

12、hile(P!=NULL&P-data!=x)P=P-next;return(P);第21页/共43页222.3 链表 插入5、插入ai-1aixSP分析：A、搜索位置；B、装入x；C、插入x；P=get(L,i-1);if(P=NULL)error(“序号错”);else S=new node;S-data=x;S-next=P-next;P-next=S;void insert(node&*L,elementtype x,int i)第22页/共43页232.3 链表 删除6、删除Pai-1aiai+1 分析：A、搜索位置；B、删除结点；C、释放结点；P=get(L,i-1);if(P=N

13、ULL)error(“序号错”);else u=P-next;P-next=P-next-next;delete u;/free(u);void delete(node&*L,int i)第23页/共43页242.3 链表单链表的应用(头结点)链表的遍历：访问链表每个结点一次且仅一次。基本算法如下：void print(node *L)P=L-next;while(P!=NULL)visit(P-data);P=P-next;a1a2a3 LP第24页/共43页252.3 链表单链表的应用(头结点)设计算法，判断带头结点单链表L是否递增？若递增，则返回true，否则返回false。分析：（1）

14、链表空，返回true；（2）只有一个结点，返回true；（3）每个元素都小于其直接后继，返回true；否则，返回false；例例第25页/共43页262.3 链表单链表的应用(头结点)由分析得如下流程图：P=L-next;P=P-next;P!=NULLP-next!=NULLP-datanext-dataYYY返回true返回trueNN返回fasleNbool Judge(node*L)P=L-next;if(P=NULL)return(true);while(P-next!=NULL)if(P-datanext-data)P=P-next;else return(false);retur

15、n(true);第26页/共43页272.3 链表构造链表构造链表基本方法：从键盘输入数据，每读入一个元素，产生结点装入，插入链表中，重复上述操作X不是结束符cin xs=new node;s-data=x;插入操作n 讨论：产生结点：s=new node;s-data=x;插入链表：插入位置如何确定，有 表头/表尾 两个位置可选 头插法 尾插法重复上述操作：何时结束?a1a2a3 L第27页/共43页282.3 链表头插法头插法运算实现：void create_List(node*&L)L=new node;L-next=NULL;cin x;while(x!=End_of_Num)u=ne

16、w node;u-data=x;u-next=L-next;L-next=u;cinx;a1a2an UxLX不是结束符cin xu=new node;u-data=x;u-next=L-next;L-next=u;第28页/共43页292.3 链表尾插法尾插法运算实现：void create_List(node*&L)L=new node;R=L;/尾指针cinx;while(x!=End_of_Numo)u=new node;u-data=x;R-next=u;R=u;cinx;R-next=NULL;a1a2an x uLR第29页/共43页302.3 链表练习题P 31 例2.6、2.

17、7、2.81）链表A，B，设计算法求CAB，并分析其时间复杂度2）递增链表A，B，设计算法求CAB，并分析其时间复杂度第30页/共43页312.4 其他结构形式的链表单循环链表（优点：可在表中反复搜索）初始化操作为：head=new node;head-next=head;求长度：p=head-next;n=0;while(p!=head)p=p-next;n+;应用：m人开m把锁问题（每人一把钥匙，要求所有锁都能开）约瑟夫环问题（利用循环队列，不带头结点的循环链表都可）a1a2an headhead第31页/共43页322.4 其他结构形式的链表带尾指针的单循环链表（优点：表尾操作方便）应用

18、：将A、B两链表首尾相连 实现部分语句为：u=A-next;1:A-next=B-next-next;2:free(B-next);3:B-next=u;4:A=B;a1a2an reara1a2an a1a2an BAu123第32页/共43页332.4 其他结构形式的链表p双链表（优点：求前驱后继都方便）带头结点 或者 不带头结点 typedef struct elementtype data;dnode*prior,*next;dnode;p双循环链表prior data next a1a2 an head第33页/共43页342.4 其他结构形式的链表初始化：head=new node

19、;head-prior=head-next=head;求长度查找类似插入时：s-prior=p-prior;s-next=p;p-prior=s;s-prior-next=s;删除时：p-prior-next=p-next;p-next-prior=p-prior;delete p;应用：判断双循环链表是否对称 双循环链表倒置（动指针、动结点值）head ai ai+1 xsp ai-1 ai ai+1p第34页/共43页352.4 其他结构形式的链表小结：线性表 逻辑上相邻的元素 顺序表 物理上也相邻 插入、删除需移动元素 链表 物理上不一定相邻 插入、删除不需移动元素第35页/共43页36

20、2.5 串定义：串：由n个字符a1,a2,an组成的有限序列（n=0）元素是字符的线性表，记作 S=“a1,a2,an”，其中n为串长度。n=0时为空串。注意：空串和空格串的区别。空串没有元素。空格串元素是空格符。子串 串S中若干个连续的字符组成的序列。书上书上P37例例第36页/共43页372.5 串运算：基本运算 赋值=：将一个串值S1传送给一个串名S。如：S=S1 求长度length(S)：返回串S的长度值。连接运算+：将S1和S2连接成一个新串（如S1+S2）求子串substr（S,i,j）：返回串S从第i个元素开始的j个元素所组成的子串。串比较strcmp(S1,S2)：比较两个串的

21、大小。对齐按ASCII码进行比较。结果为-1、0、1第37页/共43页382.5 串常用运算：可由基本运算实现 插入（insert（S,i,S1）：将子串S1插入到串S的从第i个字符开始的位置上。删除（deletestr（S,i,len）：删除串S中从第i个字符开始的len个字符。替换（replace(S,i,len,S1)）：用字串S1替换串S中从第i个字符开始的len个字符。定位（index（S,S1）/模式匹配 例：S=“a1,a2,an”，在S的第i个位置插入S1 运算为 insert(S,i,S1)，为常用运算 可操作为：X1=substr(S,1,i-1,)X2=substr(S,

22、i,length()-(i-1),)S=X1+S1+X2 /为基本运算 两者可互换第38页/共43页392.5 串存储结构 顺序串 紧凑格式：优点：节省空间；缺点：运算不方便。非紧凑格式：优点：运算方便；缺点：浪费空间。链串 结点大小（规模）：大于1：等于1：S a1 a2 a3ana4.a3.a2.a1a8.a7.a6.a5ana1a2a3a4a5a6a7a8an 第39页/共43页40第二章 线性表 第二章 线性表 2.1 线性表的定义和运算 2.2 顺序表 2.3 链表 2.4 其它结构形式的链表 2.5 串 第40页/共43页41第二章第二章 线性表线性表 重点重点 掌握顺序存储结构的

23、描述方法。掌握顺序存储结构的描述方法。掌握线性表在顺序存储结构中实现基本运算（查找、插掌握线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析入、删除、合并等）的算法及分析掌握链式存储结构的描述方法。掌握链式存储结构的描述方法。掌握线性表在链式存储结构中实现基本运算（查找、插掌握线性表在链式存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析。入、删除、合并等）的算法及分析。掌握并学会何时选用何种链表的方法。掌握并学会何时选用何种链表的方法。串的存储结构及基本运算的实现。串的存储结构及基本运算的实现。41第41页/共43页42第二章第二章结束第42页/共43页43感谢您的观看！第43页/共43页