数据结构练习题----单链表篇（一）

第一题

有一个带头结点的单链表L，设计一个算法使其元素递增有序

思路

先将链表的数据复制到数组中，然后再数组中使用八大排序中的任意一种进行排序，然后再使用尾插法插入到链表当中

Void sort(LinkList &L){ LNode *p=L->next,*pre; LNode *r=p->next,* p->next = NULL; p=r; while(pre->next!=NULL&&pre->next->data<p->data){ pre=pre->next; p->next = pre->next; pre->next = p; p=r; } }

第二题

试编写一个算法带头结点的单链表L中删除一个最小值结点的高效算法

思路

双指针，一个用来遍历链表，一个用来记录当前已遍历的数据中最小值的位置，当遍历结束时，直接在记录最小值的位置进行删除即可

LinkList Delect_Min(LinkList &L){ LNode *pre=L, *p=pre->next; LNode *minpre=pre,*minp=p; while(p!=NULL){ if(p->data<minp->data){ minp=p; minpre=pre; } pre=p; p=p->next; } minpre->next = min->next; free(minp); return L; }

第三题

两个整数序列A，B，判断B是否为A的子序列

思路

遍历A的时候比较是否有和B的第一个数字相等的，如果遍历到最后都没有就说明不是，如果存在，在将A，B同步遍历并且比较大小，然后遍历的B的表尾都相等时才说明B是A的子序列

int patten(LinkList A,LinkList B){ LNode *p=A; LNode *pre=p; LNode *q=B; while(p&&q) if(p->data==q->data){ p=p->next; q=q->next; } else{ pre=pre->next; p=pre; q=B; } if(q==NULL) return 1; else return 0; }