数据结构——使用C语言版(朱战立)线性表.ppt

* * * * * * * * * * * * * * * * * * * * void LinListInsert(SLNode *head, DataType x) { SLNode *curr, *pre, *q; curr = head-next; pre = head; while(curr != NULL curr-data = x) { pre = curr; curr = curr-next; } q = (SLNode *)malloc(sizeof(SLNode)); q-data = x; q-next = pre-next; pre-next = q; } 算法设计说明： （1）在循环定位插入位置时，循环条件必须首先是curr != NULL，然后是curr-data = x。如果次序颠倒，则当curr为空（即等于链表结束标记NULL）时,将因为curr-data不存在而出错；次序不颠倒时，当curr等于NULL时将退出循环，不会进行后边条件curr-data = x的比较。 （2）当比较到最后一个结点仍有data小于等于x时，此时有pre指向最后一个结点，curr等于NULL，则上述算法把新结点插入到了单链表尾作为了单链表新的表尾结点。 例2-7 设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照数据元素的值递增有序的顺序进行就地排序。 算法思想：在例2-6算法的基础上，再增加一重循环即可实现全部数据元素的排序。由于此时的排序过程没有申请新的结点空间，所以这样的排序算法满足就地排序，即不增加新的内存空间的设计要求。 具体实现过程是：把头指针head所指单链表置空（即初始时head所指单链表仅包含一个头结点），把去掉头结点的原单链表（设由头指针p指示）中的数据元素逐个重新插入head所指单链表中。每次插入从head所指单链表的第一个数据元素结点开始，逐个比较head所指单链表每个结点的data域值和p所指单链表的当前第一个数据元素结点的data域值，当前者小于或等于后者时，用head所指单链表的下一个结点进行比较；否则就找到了插入结点的合适位置，从p所指单链表中取下当前第一个数据元素结点插入到head所指单链表的合适位置。这样的过程一直进行到p所指单链表为空时结束。 void LinListSort(SLNode *head) { SLNode *curr, *pre, *p, *q; p = head-next; head-next = NULL; while(p != NULL) { curr = head-next; pre = head; while(curr != NULL curr-data = p-data) { pre = curr; curr = curr-next; } q = p; p = p-next; q-next = pre-next; pre-next = q; } } 练习：编写算法实现带头结点的单链表的逆置。阅读下列程序，查找程序中的问题。 void converse(SLNode *head) { SLNode *p,*q; p=head-next; head-next=NULL; while (p!=NULL) { q=p; p=p-next; head-next=p-next; } } 正确的程序： void converse(SLNode *head) { SLNode *p,*q; p=head-next; head-next=NULL; while (p!=NULL) { q=p; p=p-next; q-next= head-next; head-next=q; } } 1) 习题2-1，2-2 ，2-3 习题2-4，2-10，2-14 2) 习题2-16 3) 习题2-5，2-6，2-15 4)习题2-20，2-21 5)习题2-18，2-22 作业 * * * *