数据结构之线性表课件(编辑修改稿)

数据结构之线性表课件(编辑修改稿)内容摘要：

如下面的图所示。 假设指针 p指向单链表中的第 i个结点，指针 s指向已生成的新结点，链入新结点的操作如下： 将新结点 *s的链域指向结点 *p的后继结点 (即 snext=pnext)； 将结点 *p的链域指向新结点 (即 pnext=s)。 head a1 a 2 a i a n ∧ a i +1 S x P insert(head) /*在第 i个结点 后 插入结点 S { linklist *p=head。 int k=0。 while ((p!=null) $$ (kI)) { p=pnext。 k=k+1。 } s=(linklist *)malloc(sizeof(linklist)) if (s= =null) { printf (“没有足够的空间 ” ) Return(null) } snext=pnext。 pnext=s。 return(head) 插入算法 Linklist *insertllist (head, x, k) / 在头指针为 linklist *head。 head的单链表的第 K个 elementtype x。 结点之 前 插入 X int k。 {linklist *p,*pre,*s。 int j=1。 p=head； pre=null。 while [(p!=null) $$ (jk)] /*找出第 k个结点的 {pre=p； /*指针 p和它的前趋 p=pnext。 /*结点 pre j++ } 插入算法续 if(j!=k) { printf(“k超出链表的长度 ” )。 return(null)。 } s=(linklist *)malloc(sizeof(listlist)) if (s= =null) { printf (“没有足够的空间 ” ) Return(null) } 插入算法续 sdata=x。 If (pre==null) /*插入的结点位于链 { snext=head。 /*表的头部 ， 即 k=1 head=s。 } else { snext=p。 prenext=s。 } return(head) } 3. 删除 假设单链表 带有头结点 ，头指针为 head，删除单链表上一个 其值为 x的结点。 主要操作 是： 1) 用遍历的方法在单链表上找到该结点； 2) 从单链表上删除该结点。 欲从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。 假设指针 q指向待删除结点的前一个结点，指针 p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点 *q的链域指向 *p的后继结点（即 qnext=pnext）。 x head ∧ p q 删除算法 Linklist * Delete (head, x) linklist *head。 elementtype x。 { linklist *q,*p。 q=head。 p=headnext。 while((p!=null) amp。 amp。 (pdata!=x)) { q=p。 p=pnext。 } 删除算法续 if (p=NULL) { printf (“x不存在 ” ) return(null)。 } else { qnext=pnext。 /*修改指针 free(p)。 } return(head)。 } 返回 静态链表 在某些语言中，没有指针类型，就不能实现链表，可用一数组来模拟链表，这就是静态链表。 静态链表的定义 define maxsize 元素的最大个数 typedef struct {elementtype data。 int next。 }slinklist。 如： slinklist sl[maxsize]。 定义了一个有 maxsize个元素的数组，每个元素由信息域和指针域组成。 例： L=（ a， b， c， d， e， f）， 0 0 1 1 2 2 3 3 4 4 5 5 6 6 插入 h之后 0 1 a 2 b 3 c 4 d 5 e 6 f 0 0 1 a 2 b 7 c 4 d 5 e 6 f 0 h 3 线性表实现方法比较 链表：在已知元素个数的情况下，浪费空间； 在未知元素个数的情况下，节约空间； 速度快。 顺序表：在已知元素个数的情况下，空间利用率 高；。