数据结构，线性表，链表常见算法

算法和问题来自于试卷，辅导书，以及网络。

// 数据结构 typedef struct LNode{ int data; struct Lnode *next; }LNode,*LinkList;

算法2.2.1

设计一个递归算法，删除不带头节点的单链表L中所有值为x的节点

分析：略

bool deleteX(LinkList &L,int x) { LinkList *p; if(L==NULL) return 0; else if(L->data==x) { p=L; L=L->next; free(p); deleteX(L,x); } else { L=L->next; deleteX(L,x); } return 1; }

算法2.2.2

假设单链表L带有头节点，设计一个算法，删除L中所有值为x的节点

分析：略

void deleteX(LinkList &L,int x) { LinkList *p=L->next,*q; LinkList *pre=L; //p指针作用遍历链表，q指针指向其前一个，用于删除节点 if(L->next==NULL) return ; while(p) { if(p.data==x) { q=p; p=p->next; pre->next=p; free(q); } else { pre->next=p; p=p->next; //注意要先改变前驱的指针，再改变遍历指针 } } }

算法2.2.3

假设单链表L带有头节点，设计一个算法，从表尾到表头，输出L中每一个节点

分析：如果采用暴力算法，对每个链表中的元素遍历一次，时间复杂度可达到O（n²），或者采用头插法重新建立链表，两者实现都比较复杂，因此可以考虑递归的思想，表下一个不空时，优先输出下一个。

int invertPrint(LinkList &L) { LinkList *p=L->next; if(p->next!=NULL) return invertPrint(p->next); if(p!=null) return p; }

//分析其运算结果， 假设有链表L-1-2-3-4-6-9, 当前p指向1，p满足(p->next!=NULL)，不执行 if(p!=null) return p; 指针一直往前走，当指针指向9时，此时不满足(p->next!=NULL)，程序继续向下执行，此时才返回第一个元素9，程序退出一层递归，转到上一层递归未执行的 return p，输出8，以此类推。

算法2.2.4

假设单链表L带有头节点，设计一个算法，删除其中最小值（假设唯一）

分析：由算法2.2.2 我们可以知道，删除一个节点，还需要知道它的前驱节点，因此我们可以用两个节点m，n记录最小值节点它的前驱节点，用两个节点p和pre遍历链表，采用整形变量min记录最小值。

void deleteMin(LinkList &L) { int min; LinkList *pre=L，*p=L->next; //遍历链表指针 LinkList *m=pre,*n=p; //记录最小值节点和它的前驱,q方便删除 if(L->next==NULL) return; min=p->data; while(p!=>null) { if(p->next->data<min) { min=p->next->data; pre=p; p=p->next; m=pre; n=p; } else { pre=p; p=p->next; } } //若后面的值更小 更新m，n指针 m->next=n->next; //删除最小指针 free(n); }

算法2.2.5

假设单链表L带有头节点，设计一个算法，将其就地逆置（空间复杂度为o(1)）

分析：由算法2.2.3 我们可以知道，对这个链表采用头插法重新建表即可。

void invertL(LinkList &L) { LinkList *p=L->next，*q ; L->next==NULL; while(p!=NULL) { q=p->next; p->next=L->next; L->next=p; p=q; } //头插法的常规操作 }

算法2.2.6

假设无序单链表L带有头节点，设计一个算法，使其元素递增有序。

分析： ①可将L的值存在一个数组中，采用排序算法使其递增有序，再依次采用尾插法插入，时间复杂度跟排序算法的时间复杂度有关； ②若不采用数组的方法，可将头节点和第一个节点断开，从无序表第二个节点开始查找在有序表中插入的位置(要插入链表中某个位置，必须知道该位置前驱)。这里要注重指针的设置，稍微复杂。

void sortL(LinkList &L) { LinkList *p=L->next,*pre,*q;//pre节点指向当前有序表中的第一个节点，用于寻找插入位置，p节点用来遍历链表，q节点为插入过程做准备。 q=p->next; p->next=NULL; //断链，将头节点和第一个节点作为有序表 p=q; while(p!=NULL) { pre=L; //每次循环都先让L指向有序表第一个位置 while(pre->next!=NULL&&pre->next->data<p->data) pre->pre->next; //寻找插入位置，如果pre的下一个元素大于p中的元素，则pre就是当前要插入节点前驱的位置。 q=p->next; //防止断链 p->next=pre->next; pre->next=p; p=q; //继续遍历链表 } }

不难发现内外层循环的时间复杂度均为o(n)，因此该算法时间复杂度为o(n²)

算法2.2.7

假设无序单链表L带有头节点，设计一个算法，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素。

分析：简单算法，比较2.2.2，改变if条件语句即可

void deleteX(LinkList &L,int min,int max) { LinkList *p=L->next,*q; LinkList *pre=L; //p指针作用遍历链表，q指针指向其前一个，用于删除节点 if(L->next==NULL) return ; while(p) { if(p->data>min&&p-><max) { q=p; p=p->next; pre->next=p; free(q); } else { pre->next=p; p=p->next; //注意要先改变前驱的指针，再改变遍历指针 } } }

算法2.2.8

给定一个带头节点的单链表，试编写算法，按递增次序输出单链表中各节点的数据元素，并释放节点所占存储空间。（不许使用数组辅助）

分析：本题类似算法2.2.6 可直接在2.2.6后面加上输出和释放存储空间的语句，或者每次遍历找到最小的时候就输出并释放。

void ascendL(LinkList &L) { LinkList *p,*pre,*q;//pre节点指向当前有序表中的第一个节点，用于寻找插入位置，p节点用来遍历链表，q节点为插入过程做准备。 q=p->next; while(L->next!=NULL) { pre=L; p=L->next; while(p->next!=NULL) { if(p->next->data<p->data) pre->pre->next; p=p->next; } print(pre->next->data); q=pre->next; pre->next=q->next; free(q); } free(L); }

算法2.2.9

将一个带头节点的单链表A分解为两个带头节点的链表A,B, 其中，A表中含有原来表中的奇数，B表中含有原来表中的偶数，并且使其相对顺序不变。

分析：将A表表头摘下，再申请B表表头，遍历A表中元素，并且在遍历时对其进行判断，如果是奇数就插到A表中，否则插入到B表，由于要求相对位置不变则使用尾插法。

void diverseL(LinkList &La) { Lb=(LinkList)malloc(sizeof(*Lnode)); LinkList *p=La->next,q; LinkList *ra=La,*rb=Lb; La->next=NULL; Lb->next=NULL; while(pa!=NULL) { if(pa->data%2==0) { q=p->next; p->next=ra->next; ra->next=p; ra=p; p=q } else { q=rb->next; p->next=rb->next; rb->next=p; rb=p; p=q; } } free(p); free(q); }

算法2.2.10

在一个递增有序的单链表中，有数值相同的元素存在，设计算法去掉其中相同的元素，使其中不在有相同元素。如（7，10，10，21，21）将变为（7，10，21）

分析：链表递增有序，则相同元素比相邻。

void deleteSameValue(LinkList &L) { Lnode *p=L->next,*q; //假设存在头节点 while(p->next!=NULL) { if(p->data==p->next->data) { q=p->next; p->next=q->next; free(q); } else p=p->next; } }