大学数学第02章 线性表2.pptVIP

简单回顾 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点:可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路：改用另一种线性存储方式： 2.3 线性表的链式表示和实现 线性表的链式存储结构 定义: 是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。 特点: 为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。 示例: 假设有一个线性表（a,b,c,d），可用下图所示的形式存储： 一、 单链表的存储结构 例：请画出26个英文字母表的链式存储结构。 4）头指针、头结点和首元结点的区别 习题: 下面关于线性表叙述中，错误的是___ A.顺序表必须占用一片地址连续的存 储单元 B.链表不必占用一片地址连续的存储单元 C.顺序表可以随机存取任一元素 D.链表可以随机存取任一元素 二、单链表的操作实现 sizeof(x):计算x的长度 malloc(m):开m字节空间 free(p) :删除一个变量 1、单链表的建立 假设： 　　数据元素是整型的数据，逐个输入这些整数结点，并以-1作为输入结束标志符。创建如下所示的单链表： 采用尾插法建立有头结点单链表. LinkList CreateList2() { LinkList H=(LinkList)malloc(sizeof(LNode)); LNode *s, *r=H; int x; H-next=NULL; scanf(%d,x); while(x!=-1) {s=(LinkList)malloc(sizeof(LNode)); s-data=x; s-next=r-next; r-next=s; r=s; scanf(%d,x);} return H; } 2、单链表中查找第K个元素 LinkList Get_LinkList(LinkList H,int k) {LNode *p=H; int j=0; while(p-next!=NULLjk) {p=p-next;j++;} if(j==k) return p; else return NULL;} 3、向单链表中插入一个元素 4、从 单链表中删除一个元素 三、单链表的操作效率分析 （1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 五、循环单链表 循环单链表是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。 １、双向链表的存储结构 　　　双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。 其结点的结构为： 　　 双向链表结点的结构体定义如下： 　　　typedef struct dlnode { ElemType data; struct dlnode *next ,*prior; }DLNode,*DLinkList; 习题 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p-next=s;s-next=p-next; B． s-next=p-next;p-next=s; C．p-next=s;p-next=s-next; D． p-next=s-next;p-next=s; next data prior 双向链表的操作特点： “查询” 和单链表相同 “插入” 和“删除”时需要同时修改两个方向上的指针。 ai-1 x (1)s-prior = p-prior; (3)s-next = p; (2)p- prior -next = s; (4)p-prior = s; p s ai 插入 思考： 若将下列两个语句执行顺序对换是否可行？ p-prior =s; p-prior-next = s ; ai-1 删除 ai ai+1 p-prior-next = p-next; p-next-prior = p-prior; free(p) p ai-1 讨论1： 顺序存储和链式存储的区别和