数据结构-使用C语言 朱战立第2章线性表的链式表示.ppt

* 循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p或p-next=head h h 空表 * 双向链表（double linked list） 单链表具有单向性的缺点 结点定义 typedef struct node { datatype element; struct node *prior,*next; }dnode; prior element next L 空双向循环链表： 非空双向循环链表： L A B b c a p p-prior-next= p= p-next-prior; NextElem的执行时间为O(1) PriorElem的执行时间为O(n) * b c a P void del_dulist(dnode *p) {p-prior-next=p-next; p-next-prior=p-prior; free(p); } 删除 算法描述 算法评价：T(n)=O(1) p-prior-next=p-next; p-next-prior=p-prior; * void ins_dulist(dnode* p,int x) {dnode *s; s=(dnode*)malloc(sizeof(dnode)); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; } 算法描述 算法评价：T(n)=O(1) x S b a P 插入 * 本章小结 线性结构(包括表、栈、队、数组）的定义和特点： 仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。 2. 线性表 逻辑结构：“一对一” 或 “1:1” 存储结构：顺序、链式 运 算：修改、插入、删除[查找和排序另述] 3.顺序存储 特征：逻辑上相邻，物理上也相邻； 优点：随机查找修改快 O(1) 缺点：插入、删除慢 O(n) 改进方案：链表存储结构 * 循环链表的特点：从任一结点出发均可找到表中其 他结点 双向链表的特点：可方便找到任一结点的前驱 静态链表的特点：不用指针也能实现链式存储和运算 4.链式存储 特征：逻辑上相邻，物理上未必相邻 优点：插入、删除快 O(1) 缺点：顺序查找修改慢 O(n) 5.几种特殊链表的特点： * 讨论1： 顺序存储和链式存储的区别和优缺点？ 　　顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。 　　链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 * 讨论2：什么是指针？指针的作用？ 指针—即变量的内存地址。指针主要功能有二： ①提供了一种快速访问数组单元的途径； ②使C语言函数可以修改其调用的参数。 ---指针操作符（单目），返回操作数地址； *---运算符（单目），是对的补充，返回位于这个地址内的变量之值。 例： q=*m意即“q取地址m中的值”。如果数值100存储在内存地址2000中，而这一地址又存在m中，则q=(2000)=100 讨论3：与指针有关的符号和*之间有何区别？ * 作业 一、基础知识题 1. 试比较顺序表与链表的优缺点 2. 写出在循环双链表中的p所指结点之后插入一个s所指结点的操作。 3. 写出在单链表中的p所指结点之前插入一个s所指结点的操作。 2：ptNode Insert_after(ptNode??*p, int x){????????ptNode s;????????s=(ptNode)malloc(sizeof(node));//建立新结点????????s-data=x;????????????????????//将x的值赋给s-data????????s-next=p-next;??????????//1)将新结点S的后继指向结点P的后继????????s-prior=p;?????????????