第07课 线性链表.pptVIP

main() { LINKLIST *L=NULL; LINKLIST *p; L=RearCreate(); PrintLinkList(L); p=get(L,4); InsertAfter(p, 45); PrintLinkList(L); InsertBefore(L, 8, 65); PrintLinkList(L); } Smp4_4.c 10 20 30 40 50 60 70 80 90 10 20 30 40 45 50 60 70 80 90 10 20 30 40 45 50 60 65 70 80 90 记住要删除的结点：t=p-next; 将该结点摘除：p-next=t-next; 释放要删除的结点：free(t); p t 释放该结点 int DeleteAfter(LINKLIST *p) { LINKLIST *t; int r=1; if (p-next!=NULL) { t=p-next; p-next=t-next; free(t); } else r=0; return r; } Smp4_5.c 查找到要删除结点p的前趋结点q。 调用DeleteAfter算法删除q结点的后继结点(即结点p)。 p(已知结点) q(前趋结点) 释放该结点 该删除算法程序略，请同学们自己思考如何实现该算法，主要是解决如何找到p结点的前趋结点。 先找到第i个结点的直接前趋pp=get(head, i-1); 删除p结点的后继结点(即第i个结点)DeleteAfter(p); 第i个结点 p(前趋结点) int DeleteOrder(LINKLIST *head, int i) { LINKLIST *p; int r=1; p=get(head, i-1); if ((p!=NULL) (p-next!=NULL)) DeleteAfter(p); else r=0; return r; } Smp4_5.c main() { LINKLIST *L=NULL; LINKLIST *p; L=RearCreate(); PrintLinkList(L); p=get(L,4); DeleteAfter(p); PrintLinkList(L); DeleteOrder(L, 6); PrintLinkList(L); } Smp4_5.c 10 20 30 40 50 60 70 80 90 100 10 20 30 40 60 70 80 90 100 10 20 30 40 60 80 90 100 信息工程系 软件教研室 范宏宇 peierfan@126.com 线性表顺序存储的特点是：物理位置相邻的元素在逻辑关系上也是相邻的。这一特点使顺序表具有以下优点： 可以方便地随机读取表中任一元素，读取任一元素所花时间相同。 存储空间连续，不必增加额外的存储空间。 但顺序存储的缺点也很明显： 插入和删除运算除特殊位置外一般要移动大量元素，所花时间较多，效率较低。 由于顺序表要求连续存储空间，存储分配只能预先进行。因此当表长经常变化时，难以确定合适存储空间。 ZHAO QIAN SUN LI WANG head typedef struct node { 　　int data; 　　struct node *next; }LINKLIST; 37 45 21 35 58 head 数据域 指针域 35 27 66 4 12 6 ... … … … 链表： 200 204 208 ... 210 206 202 ..... 顺序表： 头结点 ... 210 212 216 .. 206 202 … null … ... 66 35 12 .. 4 27 6 204 200 204 208 212 210 206 202 ..... 214 216 在66后面插入17 头结点 ... 210 212 216 .. 206 202 … null … ... 66 35 12 .. 4 27 6 204 200 204 208 212 210 206 202 ..... 214 216 在66后面插入17 头结点 ... 210 212 216 ... 206 202 … null … ... 66 35 12 17 4 27 6 204 200 204 208 212 210 206 202 ..... 214