数据结构单链表.ppt

1、上堂课要点回顾,线性表的抽象数据类型定义 顺序表 类型定义 基本操作实现 应用,数据结构课程内容,第 三 次 课,阅读： 朱战立，第26-35页 练习： 作业3,2.3 线性表的链式表示和实现 链表,链式存储结构 定义：用一组任意的存储单元来存放线性表 中的数据元素。 特点：逻辑结构上相邻的元素在其存储的物 理位置上不一定相邻。 通过指针把链表的存储结点链接成一 个链。,2.3.1 单链表的存储结构, 结点结构：链表每个结点中只有一个指针 域指向直接后继结点。, 结点类型定义（借用指针类型） typedef int DataType; typedef struct Node DataType

2、data; struct Node * next; /递归定义 SLNode; /*单链表结点结构体类型SLNode*/,SLNode *head;,数据域：元素本身信息 指针域：指示直接后继的存储位置,a0,a1,a2,an-1,head,空表：,非空表：, 单链表的逻辑状态,首元结点,l1-next = l2; l2-next = l3; l3-next = NULL;,SLNode *l1= (SLNode*) malloc ( sizeof (SLNode); SLNode *l2 = (SLNode*) malloc ( sizeof (SLNode); SLNode *l3 = (

3、SLNode*) malloc ( sizeof (SLNode); l1-data = 7; l2-data = 0; l3-data = 6;,l1,l2,l3,sizeof(x)计算变量x的所占的字节数 malloc(m) 开辟m字节长度的地址空间，并返回这段空间的首地址 free(p) 释放指针p所指变量的存储空间，即彻底删除一个变量,存储结构,带头结点的单链表： 非空表：,空表：,满足 head-next=NULL,头结点是在链表的首元结点之前附设的一个结点；其数据域不存储线性表的数据元素，只放表长等信息；其指针域存储首元结点的地址,头结点,初始化单链表, 单链表的操作实现,void

4、 ListInitiate(SLNode * head) /置以head为头指针的带头结点的单链表为空表 *head = (SLNode*) malloc ( sizeof (SLNode); (*head)-next = NULL; main( ) SLNode *head; ListInitiate( . ,空表：,读取单链表中第i个结点,思想：从头指针开始，顺着链向后查找。 具体：设p为搜索指针，计数器 j 从-1开始计数。初始p指向头结点。 循环：p=p-next; j+;直至j=i或至表尾 循环退出后如果j=i 时，p所指结点即为第 i 个结点，否则 ，表空或 in-1（非法）,a0

5、,a1,an-1,ai,head,int ListGet(SLNode *head, int i, DataType *x) /* 在以head为头指针的带头结点的单链表中，读取第i个元素 */ SLNode *p; int j; p=head; j=-1; /*从头指针开始查找ai */ while (p-next!=NULL /注意：仅当 p!=NULL时，p-data、p-next才有意义,【单链表取元素算法】,|i0,单链表取元素算法的时间复杂度： 上述算法的时间复杂度与while语句的频度有关，最坏情况下搜索完整个链表，因此，对于长度为 n 的单链表而言，算法的时间复杂度为 O(n)

6、。,插入前插,思想：要在第 i 个结点之前插入元素 x，必须先找到第 i-1 个结点的地址，这样，才能将第 i-1 个结点的指针修改指向新插入的结点，而新结点的指针指向第 i 个结点。,q-next=p-next;,注意：两条语句的顺序不能颠倒，否则ai的地址会丢失。,另外，要注意合法 i 值为：0i size 若 isize，则 i 值非法。,ai-1,head,a0,p-next=q;,q-next,p-next,q=(SLNode*)malloc(sizeof(SLNode); q-data=x;,int ListInsert(SLNode *head, int i, DataType

7、x) /*在以head为头指针的带头结点的单链表中的第i个结点之前插入值为x的结点*/ SLNode *p, *q; /*p：搜索指针，q：新生成指针*/ int j; p=head; j= - 1; while (p-next!=NULL ,【单链表前插算法】,if (j!=i-1) printf(“n插入位置i不合理!”); return 0; /*产生新结点q*/ q=(SLNode *) malloc (sizeof ( SLNode) ) ; q-data=x; /*插入*/ q-next=p-next; p-next=q; /*注意：上面两条语句的次序不能颠倒*/ return 1

8、;,思想：要删除第 i 个结点，同样必须找 到第 i-1 个结点的地址，这样，才能将第 i-1 个结点的指针修改指向第 i+1 个结点。,删除,s=p-next;,ai-1,p-next=p-next-next;,free(s);,an-1,ai+1,另外，要注意合法 i 值为：0i size-1,head,a0,p-next,p-next-next,int ListDelete(SLNode *head, int i, DataType *x) /*删除以head为头指针的带头结点的单链表中的第i个结点*/ SLNode *p, *s; /*p：搜索指针，s：缓冲指针*/ int j; p=

9、head; j= - 1; /*寻找第i-1个结点*/ while (p-next!=NULL ,【单链表删除算法】,if (j!=i-1) printf(“n删除位置不合理!”); return 0; /*删除*/ s=p-next; *x=s-data; p-next=p-next-next; free(s); return 1; ,单链表插入删除算法时间复杂度分析： 插入、删除算法的时间复杂度均为O(n)。这是因为，虽在单链表中插入或删除元素时无需移动元素，只需修改指针域。但由于它不是随机存取结构，为寻找第i-1个元素，尚需执行ListGet(head, i-1, x)操作，这和顺序存储

10、结构正好相反。,单链表空间复杂度分析：,单链表中每个结点都要增加一个指针域，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。,int ListLength(SLNode *head) /求以head为头指针的带头结点的单链表表长 SLNode *p=head; /*p：搜索指针*/ int size=0; while(p-next!=NULL) p=p-next; size+; return size; ,【单链表求表长算法】,void Destroy(SLNode *head) /释放以head为头指针的带头结点的单链表所占空间

11、 SLNode *p, *p1; p = *head; while(p != NULL) p1 = p; p = p-next; free(p1); *head = NULL; ,【撤消单链表算法】,空表：,在单链表中为什么引入头结点？,引入头结点是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。 如果不增加头结点，插入和删除操作如何变动？,1） 在带头结点单链表第一个数据元素前插入结点,2）删除带头结点单链表第一个数据元素结点,3）在不带头结点单链表第一个数据元素前插入结点,4）在不带头结点单链表其他数据元素前插入结点,5）删除不带头结点单链表第一个数据

12、元素结点,6）删除不带头结点单链表其他数据元素结点,结论： （1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）因此，带头结点单链表的算法设计简单, 2.3.4单链表应用举例 例23（P35） 文件 LinList.h (P29-34) 文件 LinListExample.c（P35）,作业3,算法设计题： 1、补充实现单链表的基本操作 1、IsEmpty（）函数实现判断单链表是否为空表。 2、InsertFront（）函数实现在单链表首元结点前插入一新结点x。 3、InsertEnd（）函数实现在单链表的表尾插入一个新结点x。 4、Find()函数实现在单链表中寻找值为x的元素。 5、FindPrevious（）函数实现在单链表中寻找值为x的前一个元素。,2、实现带尾指针和表长信息的单链表数据结构 1、InsertEnd( )函数实现在单链表的表尾插入新结点，但它的运行时间代价为O(n)，因为要从头指针开始遍历整个链表找到尾结点。要求你修改单链表数据