第8章结构体共用体和枚举类型研究.ppt

head 0001 89.5 0002 76 0003 88 NULL void print(struct student *p) { cout“These ”n“ records are:”endl; if(p==NULL) return; do{ coutp-num“ ”p-scoreendl; p=p-next; //使p指向下一个结点 }while(p!=NULL); } 0001 89.5 0002 76 0003 88 NULL (next) p p1 p1 void print(struct student *p) { cout“These ”n“ records are:”endl; if(p==NULL) return; do{ coutp-num“ ”p-scoreendl; p=p-next; //使p指向下一个结点 }while(p!=NULL); } 对链表的删除操作是把某个结点从链表中摘除,并不是真正从内存中将这个结点删除掉，使它脱离原来的链表，解除原来的链接关系。 算法分析：以指定的学号为删除标志。从指针变量p指向的第一个结点开始，检查该结点中的num是否为要删除的学号,如果是则将其删除;如果不是，则将p移到下一个结点，再继续判断，直到删除或到表尾为止。 对链表的删除操作 head 0001 89.5 0002 76 0003 88 NULL 执行过程：设两个指针p1和p2,先使p1指向第一个结点。如果p1所指的结点不是要删除的结点,就将p2指向p1所指的结点(p2=p1),然后将p1指向下一个结点(p1=p1-next)。再继续判断p1所指的结点是不是要删除的结点,如此重复,直到找到要删除的结点并将其删除或是检查完全部链表为止。 head 0001 89.5 0002 76 0003 88 NULL p1 p2 p1 0001 89.5 0002 76 0003 88 NULL 要删除的结点分两种情况： ①要删除的是第一个结点（即p1==head），则执行head=p1-next。这时，head指向了原来的第二个结点。此时，第一个结点虽然还存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它，也就不能访问它了，即已被删除。 head p1 head 0001 89.5 0002 76 0003 88 NULL head 要删除的结点分两种情况： ②要删除的不是第一个结点,则应执行 p2-next=p1-next,即p2-next指向了p1-next所指向的结点， p1所指向的结点就被删除而不再是链表的成员了。 p1 p2 struct student *dele( student *head, long num) { student *p1, *p2; if (head==NULL) { coutlist nullendl; return head; } p1=head; while(p1-num!=nump1-next!=NULL) { p2=p1; p1=p1-next; } if (num==p1-num) { if(p1==head) head=p1-next; else p2-next=p1-next; coutdelete:num; n=n-1; } else coutnumnot been found!endl; return(head); } 对链表的插入是指将一个结点插入到一个已有的链表中。为简单起见，假设有一个学生链表，各结点已按其成员学号（num）的值由小到大顺序排列，现在要插入一个学生的结点，要求按学号的顺序插入。 过程分析： 先将要插入的结点学号与第一个结点的学号相比，若小则插入到第一个结点前面，否则与第二个结点相比，如此重复，直到找到一个比它大的学号插入到它的前面或链表结束插入到链表的尾部。 对链表的插入操作 过程实现：