数据结构课件-第二章.pptVIP

LinkList CreateFromHead( ) { /*用头插法建立带头结点的单链表*/ LinkList head； /*头指针*/ ListNode *s； /*工作指针*/ char ch ； int flag=1； /*设置一个标志变量flag，初值为1，当输入“$”时将 flag 置0， 建表结束 */ head=(Linklist) malloc(sizeof(ListNode))； head -next =NULL； /* 链表开始时为空*/ while (flag) { ch=getchar()； if (ch!=’$’) /*插入读入的字符*/ { s=(LinklList) malloc (sizeof(listNode))； s-data=ch； s-next=head-next； head-next=s； } else flag=0； } return head； /*返回头指针 */ } 尾插法建表 将新结点插到当前链表的表尾上。为此，必须增加一个尾指针r ，使之始终指向当前链表的表尾。其建表过程如图 算法描述如下： LinkList CreateFromTail( ) { /*用尾插法建立头结点的单链表 */ LinkList head； ListNode *r，*s； char ch； int flag=1； /*设置一个标志，初值为1，当输入”$”时，flag为0，建表结束 */ head=(LinkList)malloc(sizeof(ListNode))； /*为头结点分配存储空间 */ if(head==NULL) error(“No space for node can be obtained”)；/*动态分配空间失败,退出运行 */ head-next=NULL； /*初始化为空链表 */ r=head； /* r指针始终动态指向链表的当前表尾，以便于做尾插入，其初始值指向头结点 */ while(flag) {ch=getchar( )； if (ch!=’$’) {s=(ListNode*)malloc(sizeof(ListNode))； s-data=ch； r-next=s； r=s； } else {flag=0； r-next=NULL； /*将最后一个结点的next域置为空，表示链表的结束*/ } } /*while*/ return head； } 2.4.2 循环链表 循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其它结点。 2.4.3 双向链表 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双向链表 (Double LinkedList)。双链表的结构定义如下： typedef struct DuLNode { ElemType data； struct DuLNode *prior； struct DuLNode *next； }DuLNode, *DuLinkList； 插入：设要在p所指结点的前面插入一个新结点*s ①s-prior=p-prior； ②s-next=p； ③p-prior-next=s； ④p-prior=s 删除：设p指向待删除的结点，则需修改两个指针 ①p-prior-next=p-next ②p-next-prior=p-prior 2.5 顺序表与链表的比较 基于空间的考虑 当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜于采用顺序表作为存储结构。 2.基于时间的考虑 若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。对于频繁进行插入和删除的线性表，应采用链表做存储结构。若表的插入和删除主要发生在