C程序设计第九章ppt西工大讲义.ppt

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现 * （有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.） 。 * （有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.） 。 * * 9.4.1 单链表插入结点 图9.8 单链表插入结点示意 * 9.4.1 单链表插入结点 图9.8 单链表插入结点示意 * 9.4.1 单链表插入结点 图9.8 单链表插入结点示意 总结：插入节点需要知道插入点之前的节点位置p。 * 9.4.1 单链表插入结点 实现上述步骤的C语言语句如下： 请注意，这两个表达式的顺序不能颠倒。因为若先修改结点p的指针域指向结点 s，结点p的后一个结点（p-next ）就此从链表中断开，再让结点s的指针域指向结点p的后一个结点已成错误的。 在单链表中第i个位置上插入元素e的新结点s的算法如下： s-next=p-next, p-next=s; //结点插入算法 节点的插入 插入可分为随意插入和按顺序插入，随意插 入包括插入到头部、尾部或中间指定位置；按顺 序插入是指按某关键字的顺序插入，而在插入前 链表必须已按该关键字进行了排序。 按顺序插入的步骤： 开辟待插入节点的存储区域并输入数据； 2) 查找插入位置：从链表首节点开始按关键字成 员与待插入节点相同成员进行比较，直到确定了插入位置； 3) 将插入位置前一节点的“链节”成员赋给待插入节点的“链节”成员； 4) 将待插入节点的指针赋给前一节点“链节”成员； 若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。 2101 89.5 1370 head 1048 2304 90 1012 2414 78 1048 1370 1012 1012 2680 2680 2918 85 NULL 1394 91 1048 2030 2030 【例】在上例增加“按学号插入节点的函数” 插入函数： struct tagSTU *insert(struct tagSTU *head) { struct tagSTU *p0, *p1, *p2; long n; int len; len=sizeof(struct tagSTU); p0=(struct tagSTU *)malloc(len); //申请新节点 printf(Enter num,score to insert:); scanf(%ld,%f, p0-num, p0-score); n=p0-num; //产生学号副本n p1=head; //从首节点开始查找 ┇ ┇ p1=head; //↓插入在头部 if(np1-num) { p0-next=head; head=p0; } else { do //查找插入位置 { p2=p1; p1=p1-next; } while(p1!=NULL np1-num); p0-next=p2-next; //插入点在p1之前位置 p2-next=p0; } return(head); } //insert SX09-12 * 9.4.2 单链表删除结点 结点删除操作是指将链表中的某个结点从链表中删除。删除位置可能在头结点、尾结点或者链表中间，删除操作后需要释放删除结点的内存空间。 将链表中第i个结点删去的方法是先在单链表中找到第i-1个结点p，再删除其后的结点，如图（a）所示。若要删除结点p的后一个结点（即p-next ），只需要将p的指针域指向p-next的后一个结点（即p-next-next ），如图（b）所示。 * 9.4.2 单链表删除结点 图9.9 单链表删除结点示意 * 9.4.2 单链表删除结点 图9.9 单链表删除结点示意 第一步：将予删除节点后一个节点连到d前一个节点 * 9.4.2 单链表删除结点 图9.9 单链表删除结点示意 第二步：将予删除节点的内存空间释放 free(d); //释放结点 实现分析：需要保存访问节点的前一个节