下面给出相应的C函数 struct ist /结构类型 { int V MAXN;/整型数组,MAXN为预估数组容量* int /表长 typedef struct list LIST;定义LIST为上述结构类型* int sqdelete(p, py, i) LIST "P,py /p指向结构类型的指针* /py指向变量y的指针* int i为被删除元素位置* f int j; if (p->n<=0 { printf(“表长错误Ⅷ”); return(-1);
下面给出相应的C函数. struct list /* 结构类型*/ { int v[MAXN]; /* 整型数组, MAXN为预估数组容量*/ int n; /* 表长 */ }; typedef struct list LIST; /* 定义LIST为上述结构类型*/ int sqdelete(p,py,i) LIST *p,*py; /* p指向结构类型的指针 */ /* py指向变量y的指针*/ int i; /* i为被删除元素位置*/ { int j; if (p->n<=0) { printf(“表长错误\n ”); return(-1); }
if(i<l‖i>p->n) { printf(“删除位置i不恰当n”); return(-1); py=p->v]: /被删除元素存入y* forli=i; j<p->n;j++) p>vljl=p->vj+1l;/移动* p->n- 表长减1*/ printf(“删除成功n”); return(0) 该算法的时间复杂度与插入算法相似,删除一个元素 仍需移动元素,当i=1时移动n-个,当i=n时不需移动, 故算法的时间复杂度为O(m)
if (i<1 || i>p->n) { printf(“删除位置i不恰当\n ”）; return(-1); } *py=p->v[i]; /* 被删除元素存入y */ for(j=i;j<p->n;j++) p->v[j]=p->v[j+1]; /* 移动 */ p->n--; /* 表长减1 */ printf(“删除成功\n ”）; return(0); } 该算法的时间复杂度与插入算法相似, 删除一个元素 仍需移动元素, 当i =1时,移动n-1个, 当i = n时不需移动, 故算法的时间复杂度为O(n)
设P为删除第个元素的概率,且设在线性表的任何位置 上的删除机会相等,即等概,则平均移动次数(期望值)为: n-1 E=∑p(m-1)=∑(m-1) 12i 2 23线性表的链式存储结构 由上节对顺序表的讨论可见,通过物理位置上的相邻 关系来表示逻辑上的相邻关系,使得顺序存储结构有如下 优点: (1)无需为表示元素间的逻辑关系而增加额外的存储空间; (2)可方便地存取表中任一元素; 有如下缺点: (1)插入和删除运算移动大量元素,其效率较低; (2)必须事先进行存储空间分配,表的容量难以扩充 本节将讨论线性表的另一种存储结构—链式存储结 构,也叫非顺序存储结构.这种存储结构即可表示线性 表,也可表示非线性数据结构
设 pi 为删除第i个元素的概率, 且设在线性表的任何位置 上的删除机会相等, 即等概, 则平均移动次数(期望值)为: 2 1 ( ) 1 ( ) 1 1 − = − = − = = = n n i n E p n i n i n i d e i 2.3 线性表的链式存储结构 由上节对顺序表的讨论可见, 通过物理位置上的相邻 关系来表示逻辑上的相邻关系, 使得顺序存储结构有如下 优点: (1)无需为表示元素间的逻辑关系而增加额外的存储空间; (2)可方便地存取表中任一元素; 有如下缺点: (1)插入和删除运算移动大量元素, 其效率较低; (2)必须事先进行存储空间分配, 表的容量难以扩充. 本节将讨论线性表的另一种存储结构—链式存储结 构, 也叫非顺序存储结构. 这种存储结构即可表示线性 表, 也可表示非线性数据结构
231单链表(线性链表) 所谓链式存储结构,其特点是用一组任意的存储单元 存放线性表中的元素,而这组存储单元在地址上可以连续 也可不连续,甚至可零散地分布在内存中的任何位置上 由其特点,为表示每个数据元素a与其直接后继数据元素 1之间的逻辑关系,对a来说,除存储其本身的信息外 还需存储一个指示其直接后继a1+1的存储地址.用以完整 表示一个元素及其关系的这两部分信息的存储映象,叫做 结点(node).结点中存储数据元素信息的域叫数据域,存 储直接后继数据元素存储单元地址的域叫指针域,指针域 中的信息叫指针或链,下面是结点的示意图: datal next 例如线性表为(mon,tue,wed,thu,fri,sat,sun),其链式存 储示意图可表示为:
2.3.1 单链表(线性链表) 所谓链式存储结构, 其特点是用一组任意的存储单元 存放线性表中的元素, 而这组存储单元在地址上可以连续 也可不连续, 甚至可零散地分布在内存中的任何位置上. 由其特点, 为表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系, 对 ai 来说, 除存储其本身的信息外 还需存储一个指示其直接后继 ai+1 的存储地址. 用以完整 表示一个元素及其关系的这两部分信息的存储映象,叫做 结点(node). 结点中存储数据元素信息的域叫数据域,存 储直接后继数据元素存储单元地址的域叫指针域,指针域 中的信息叫指针或链, 下面是结点的示意图: data next 例如线性表为(mon,tue,wed,thu,fri,sat,sun),其链式存 储示意图可表示为:
存储地址数据域指针域由于我们关心的只是结点 tue 16 10 间的逻辑关系,而不是结 5 头指针 16 wed 20 点的实际位置,故可将左 17 30图表示成下图,由图可见 20m17各结点只有一个指针域 sun 链表,故称为线性链表或 30 sat 29 单链表.由于单链表中每 h四m[me[[samo 个结点的存储地址存放在其直接前趋的地址域中,因此, 整个链表的存取必须从第一个结点开始,为此,需设立头 指针指示链表中的第一个结点(也叫首元结点),如上图所 示,将上例推广到一般情形,有下图所示单链表: -…区…-囚
由于我们关心的只是结点 间的逻辑关系, 而不是结 点的实际位置, 故可将左 30 29 20 17 16 10 5 sat sun thu fri wed mon tue 29 17 30 20 5 16 存储地址 数据域 指针域 mon tue wed thu fri sat mon 图表示成下图, 由图可见 各结点只有一个指针域, 各结点通过指针连成一个 链表, 故称为线性链表或 单链表. 由于单链表中每 个结点的存储地址存放在其直接前趋的地址域中, 因此, 整个链表的存取必须从第一个结点开始, 为此, 需设立头 指针指示链表中的第一个结点(也叫首元结点), 如上图所 示, 将上例推广到一般情形, 有下图所示单链表: h 头指针 10 ai+1 h a1 a2 ai−1 ai a n