09年自考《数据结构》各章要点一[4]

单链表运算

·建立单链表

·头插法s>next=head;head=s;生成的顺序与输入顺序相反平均时间复杂度均为O(n)

·尾插法head=rear=null;if(head=null) head=s;else r>next=s;r=s; 平均时间复杂度均为O(n)

·加头结点的算法对开始结点的操作无需特殊处理统一了空表和非空表

·查找

·按序号与查找位置有关平均时间复杂度均为O(n)

·按值与输入实例有关平均时间复杂度均为O(n)

·插入运算p=GetNode(Li);s>next=p>next;p>next=s;平均时间复杂度均为O(n)

·删除运算p=GetNode(Li);r=p>next;p>next=r>next;free(r);平均时间复杂度均为O(n)

单循环链表是一种首尾相接的单链表终端结点的指针域指向开始结点或头结点链表终止条件是以指针等于头指针或尾指针

采用单循环链表在实用中多采用尾指针表示单循环链表优点是查找头指针和尾指针的时间都是O()不用遍历整个链表

双链表就是双向链表就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior形成两条不同方向的链由头指针head惟一确定

双链表也可以头尾相链接构成双(向)循环链表

双链表上的插入和删除时间复杂度均为O ()

[] [] [] [] [] [] [] [] [] [] []