大学数据结构课件2.线性表.ppt

第2章 线性表 2.1 线性表抽象数据类型 2.2 线性表的顺序存储结构及实现 在结构体中还可以使用动态一维数组。如下定义： typedef struct { ElemType *elem ; int length ; } Sqlist1 ; 顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n), 其余操作的时间复杂度都为O(1) 2.3 线性表的链式表示和实现 假设h, p, q为指针变量，可说明如下： Lnode *h, *p, *q; /* 4 bytes 未赋值 */ h=NULL; /* set NULL to h */ h=(Lnode*)malloc(sizeof(Lnode)); /* point to a new node */ p=h; /* p 和 h 中存放的是同一结点的首地址 */ p-data = 12; p-next =NULL; free(h) /* or free(p) ,release the node’s space to the system*/ 2.3.3 线性链表基本运算的实现 2.4 循环链表与双向链表 4).在不带头结点单链表其他数据元素前插入结点 p ai-1 a1 ai an ∧ … h data next x ∧ s … 插入前 p ai-1 a1 ai an ∧ … h data next x s … s-next = p-next (x.next =ai -1.next) p-next = s (ai -1.next = s) 插入后 * 在不带头结点单链表首元结点和其他结点前插入结点之比较 p ai-1 a1 ai an ∧ … h data next x s … s-next = p-next (x.next =ai -1.next) p-next = s (ai -1.next = s) a1 a2 an ∧ … h x s 第一步: s-next = h 第二步: h = s 5) 删除不带头结点单链表第一个数据元素结点 6) 删除不带头结点单链表其他数据元素结点 a1 a2 an ∧ … h data next × h=h-next p ai-1 a1 ai an ∧ … h data next … × ai+1 p-next = p-next -next ( ai-1 .next = ai.next ) 结 论 （1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）因此，带头结点单链表的算法设计简单 2.3.4 单链表的操作实现举例 x ∧ … h q … s p { q=h; while(q-next!=p) q=q-next; s=(Lnode*)malloc(sizeof(Lnode)) s-data = x; s-next =p; q-next = s; } Typedef struct node { ElemType data; struct node *next; } Lnode 1、在p 指向的结点前插入数据元素x 2、在线性表中值为x的元素前插入值为y的数据元素 ai y an ∧ … h q … x a1 s p void Insert(Lnode *h, ElemType x, ElemType y) { s=(Lnode*)malloc(sizeof(Lnode)) s-data = y; q=h; p=q-next; while((p!=NULL)(p-data!=x)) { q=p; p=p-next; } s-next =p; q-next = s; } Typedef struct node { ElemType data; struct node *next; } Lnode 3、删除p所指向的结点 b … q p c a { q=h; while( q-next !=p ) q=q-next; q-next = p-next; f