数据结构线性表.ppt

《数据结构线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表.ppt（35页珍藏版）》请在优知文库上搜索。

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

2、义 例：字母表（A，B，C，D，Z）； 数字表（0，1，2，3，4，9）； 每月天数（31,29,31,30,31,30,31,31,30,31,30,31）;42.1 线性表的定义和运算 o 运算：运算： (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个位

3、置上插入值为x的元素( 1=i=n+1)(6)删除 List_delete（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（“ove

4、rflow”）; else if（iL-listlen+1） error(“position error”）; else 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 +82.2 顺序表void List_delete(seqlist *L,int i) int j; if (L-listlenL-listlen|i=0) er

5、ror(“删除位置出错”); else for (j=i;jlistlen-1;j+) L-dataj-1=L-dataj; L-listlen-; 92.2 顺序表o 算法分析：插入时 在i=1,2,n+1，元素移动的次数分别为n,n-1,0。 在等概率的情况下，平均移动(n+1)n/2(n+1)=n/2次删除时 在i=1,2,n，元素移动的次数分别为n,n-1,0。 在等概率的情况下，平均移动(n-1)n/2n=(n-1)/2次结论：n较大时，大量移动元素，耗时解决：考虑不移动元素102.3 链表基本结构以链接形式连接元素次序。a1a2a3a4 L=(a1,a2,a3,a4)结点包括 元素

6、和地址。datanext112.3 链表存储实现（静态链表）1、静态链表用数组C3A2B0D5F-1E4data next012345L=(A,B,C,D,E,F)head122.3 链表存储实现（动态链表）2、动态链表用指针和动态变量实现（1）结点结构datanext（2）类型定义 typedef struct elementtype data; node *next; node; 引用：node *head；132.3 链表图例a1a2a3a4 Head*HeadHead-next首元素首元素142.3 链表讨论(插入操作)p 插入（一般位置）：假设被插入位置的前一个结点的指针P已找到，插

7、入由S指向的结点：Pa1a2a3a4 headxS S-next=P-next P-next=S注意注意：两个操作不能交换p 如果是作为第一个结点插入，过程如下：S-next=head head=Sa1a2a3 a4 headxS152.3 链表讨论 (引入头结点)为保持插入操作一致，引入头结点头结点。注意：头结点与首元素的区别。a1a2a3 xheadSPS-next=P-next P-next=S162.3 链表讨论(删除操作)p 删除（一般位置）：假设被删除的前一个结点的指针P已找到，插入由S指向的结点：Pa1a2a3a5 heada4 P-next=P-next-nextp 如果是删除

8、第一个结点，过程如下：head=head-nexta1a2a3a5 heada4 p 讨论结果：引入头结点P-next=P-next-nexta1a2a4 heada3 P172.3 链表运算的实现（有头结点） 1、初始化单链表（建空表）Lint initial_List(node *L) L=(node*)malloc(sizeof(node);if(!L) printf(“初始化链表错误n”);elseL - next = NULL;182.3 链表求表长（1）2、求单链表表长a1a2a3 LPlen=0int List_length(node *L)P=L-next; len=0; wh

9、ile(P!=NULL) P=P-next; len+; return(len);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=0202.3 链表按序号取值3、按序号取值返回指向结点的指针,否则返回NULLa1a2a3 LPj=0212.3 链表按值查询 4、按值查询 返回元素结点指针，否则返回NULL；a1a2a3 LPnode *locate(node *L,elementtype x) P=L-nex

10、t; while(P!=NULL&P-data!=x) P=P-next; if(P-data=x) return(P); else return NULL; 222.3 链表 插入5、插入ai-1aixSP分析：A、搜索位置；B、装入x；C、插入x；P=get(L,i-1);if(P=NULL) error(“序号错”);else S = (node *)malloc(sizeof(node); S-data=x; S-next=P-next; P-next=S; void insert(node *L,elementtype x,int i)232.3 链表 删除6、删除Pai-1aiai

11、+1 分析：A、搜索位置；B、删除结点；C、释放结点；P=get(L,i-1);if(P=NULL) error(“序号错”);else u=P-next; P-next=P-next-next; free(u); void delete(node *L,int i)242.3 链表单链表的应用(头结点)o链表的遍历：访问链表每个结点一次且仅一次。基本算法如下：void print(node *L) P=L-next; while(P!=NULL) visit(P-data); P=P-next; a1a2a3 LP252.3 链表单链表的应用(头结点) 设计算法，判断带头结点单链表L是否递增

12、？若递增，则返回true，否则返回false。分析：（1）链表空，返回true；（2）只有一个结点，返回true；（3）每个元素都小于其直接后继，返回true；否则，返回false；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

13、; else return(false); return(true); 272.3 链表构造链表o 构造链表构造链表n 基本方法：从键盘输入数据，每读入一个元素，产生结点装入，插入链表中，重复上述操作X是结束是结束0非0Scanf(“%d” ,x);s = (node*)malloc(sizeof(node);s - data = x;s - next = head -next;head - next =s ;n 讨论：产生结点：s=(node *)malloc(sizeof(node);s-data=x;插入链表：插入位置如何确定， 有 表头/表尾 两个位置可选 头插法 尾插法重复上述操作：

14、 何时结束?282.3 链表头插法头插法运算实现：头插法运算实现：void create_List(node *L)L= (node *)malloc(sizeof(node); L-next=NULL;scanf(“%d”,& x);while( x != End_of_Num ) u = (node *)malloc(sizeof(node); u-data=x; u-next=L-next; L-next=u; printf(“%dn”,x);a1a2an UxL292.3 链表尾插法尾插法运算实现：尾插法运算实现：void create_List(node * L)L=(node *)

15、malloc(sizeof(node);R=L; /尾指针尾指针scanf(“%d”,&x);while(x!=End_of_Numo) u=(node *)malloc(sizeof(node); u-data=x; R-next=u; R=u; printf(“%dn”,x);R-next=NULL;a1a2an x sLR302.3 链表练习题1）链表A，B，设计算法求CAB，并分析其时间复杂度2）递增链表A，B，设计算法求CAB，并分析其时间复杂度312.4 其他结构形式的链表o 单循环链表单循环链表（优点：可在表中反复搜索 ）初始化操作为： head = (node *)malloc

16、(sizeof(node); head - next = head;求长度： p = head - next; n = 0; while ( p != head ) p = p - next; n + ;应用：约瑟夫环问题（利用循环队列，不带头结点的循环链表都可） (用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。作业)a1a2an headhead322.4 其他结构形式的链表o带尾指针的单循环链表（带尾指针的单循环链表（优点：表尾操作方便 ） 应用：将A、B两链表首尾相连 实现部分语句为：实现部分语句为： u = A - next; A - next = B - next - next; free( B - next); B - next = u; A = B; a1a2an reara1a2an a1a2an BA332.4 其他结构形式的链表p 双链表（双链表（优点：求前驱后继都方便） 带头结点 或者 不带头结点 typedef struct elementtype data; dnode * prior, * next; dnode;