数据结构2-3线性表的链式表示和实现.ppt

* 单链表： typedef struct Lnode { ElemType data; struct LNode *next; } Lnode，*LinkList; 另一种实现链表的方法是使用一维数组实现静态链表。 静态链表 结构： #define MAXSIZE 1000 100 Typedef struct { Elemtype data; int cur; }component，SLinkList[MAXSIZE ]; * * 静态链表 S[0].cur：指示第一个结点在数组中的位置； 若i= S[0].cur ，则： S[i].data存储线性表的第一个元素； S[i].cur存储第二个结点在数组中的位置 * * 例： 数组下标 数据 指针 0 头结点 3 1 赵明 0 2 3 张红 5 4 5 黎明 1 Head 黎明 赵明 ∧ 张红 * * 0 1 1 张斌 2 2 刘丽 3 3 李英 4 4 陈华 5 5 王奇 6 6 董强 7 7 王萍 0 8 9 下标 数据 next 0 1 1 张斌 2 2 刘丽 3 3 李英 5 4 陈华 5 5 王奇 6 6 董强 7 7 王萍 0 8 9 下标 数据 next 删除陈华 * * 0 1 1 张斌 2 2 刘丽 3 3 李英 4 4 陈华 5 5 王奇 6 6 董强 7 7 王萍 0 8 9 0 1 1 张斌 2 2 刘丽 8 3 李英 5 4 5 王奇 6 6 董强 7 7 王萍 0 8 王芳 3 9 在“刘丽”之后插入“王芳”： 在刘丽的后面插入王芳： * * 静态存储结构与顺序存储结构的比较： 不同点： 插入和删除操作不需要移动元素 仅需要修改cur值 相同点： 都需要预先分配一个较大的存储空间 * * 定义：最后一个结点的指针指向头结点，使链表构成环状。 循环链表是表是另一种形式的链式存储结构； 特点：从表中任一结点出发均可找到表中其他结点，查找效率高。 循环链表 H a1 ai-1 an ∧ ai p * * 循环链表 将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。 H a1 ai-1 an ∧ ai p * * 循环链表 空表和非空表的处理一致 附设头结点 H 空循环链表 H a1 ai-1 an ai 非空循环链表 * * 循环链表 a1 a2 … an head 判断空表的条件是： head head-next= =Head 判断结点P为表尾条件： P-next= =Head * * 单链表具有单向性的缺点，查找不方便。 prior 结点结构： 带头结点的非空双向链表： 双向链表 Next * * b c a p 结点定义 typedef struct DuLNode { Elemtype data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DuLinkList; p-prior-next= p= p-next-proir 双向链表 * * 结点删除 结点插入 双向链表的运算 * * b c p-prior-next=p-next; p-next-prior=p-prior; 删除操作 a p * * 算法描述 Status ListDelete_Dul(DuLinkList L,int i, ElemType e) { //删除带头结点的双向链表L中第i个元素 if(!(p=GetElemP_Dul(L,i))) //在L中确定第i个元素位置 return ERROR; e = p-data; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; } * * 插入操作算法描述： 在指针p所指结点之前插入指针s所指结点： * s-prior = p-prior; p-prior-next = s; s-next = p; p-prior=s; * 双向循环链表 * * 链式存储结构的特点 优点： 可动态申请和释放空间，不需设定最大存储空间 插入和删除操作方便 缺点： 每个结点的指针域需要另外加存储空间 链式存储是一种非随机存储结构，对于任意结点的操作都要首先从开始指针顺链查找该结点，增加了一些操作的算法时间复杂度 * * 练 习 设L为带头结点的单链表，表中元素值递增有序，编写算法删除表中相同的多余元素。 输出单链表元素值并进行计数。 * 免疫进化理论 焦