|
首先两个基础操作，查找和插入
//链表按位查找
Node GetElem(LinkList L,int i){
Node *p=L;
int j=0;
while(p&&j<i){
j++;
p=p->next;
}
return p;
}
void Insert(LinkList &L,int i,ElemType e){
//在某一点插入e
Node *p=GetElem(L,i);
Node *s=(Node*)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
}
有了基础，才能更好做题
逆置
1.元素逆置
5.A[m+n]中存了两个数组a，b，整体逆置；（原来是a,b交换为b,a这样排）
顺序表算法-移动k个位置
2.顺序表删除所有值为k的
基于有序顺序表
3.有序顺序表删除重复的值，使元素均不相同
4.两个有序表合并为一个新的有序表
链表
6.递归算法–删除不带头节点的链表的所有值为x的元素
7.求两个单链表的公共结点
8.递增输出结点，并释放空间（不允许使用数组）
9.把一个链表A{a1,b1…an,bn}，拆为两个链表A{a1,a2}和B{bn…b1}
10.判断链表是否有环，有则返回入口
扫描前半部分元素，与对应的后半部分交换。
//1.顺序表逆置
void Reverse(SqList &L){
ElemType temp;
for(int i=0;i<n/2;i++){
temp=L.data[i]; //关键在于谁与谁对应，若一共有n个元素，则1~n，2~n-1...
L.data[i]=L.data[L.lengh-1-i]; //而在数组中从0开始存储，则 0~n-1 ,1~n-1-1,
L.data[L.lengh-1-i]=temp; //则 i 与 n-1-i 对应
}
}
//2.链表逆置
//先将一个头节点摘下，然后依次从第一个元素往后进行头插法，就实现逆置了
void Reverse(LinkList &L){
Node *p,*r; // p为工作指针，r为p的后继，防止断链
p=L->next; //p指向第一个元素
L->next=null; //t头节点摘下来
while(p){
r=p->next; //暂存，防止断链
//把p头插
p->next=L->next;
L->next=p;
p=r; //暂存的还给p
}
}
//3.链表逆序输出而非逆置
//由栈与递归作用相同可知，可利用递归进行输出，实现倒序
void RePrint(LinkList L){
if(L->next!=NULL) //链表后面还有，则一路往后递归，直到最后一个元素
return RePrint(L->next);
if(L!=NULL) //已经到最后一个元素了，输出，然后返回上一层，继续输出，倒序
print(L->data);
}
规定时间复杂度为O(n),只能遍历一遍，只能边遍历，边删除
两种类似而又对立的思想：1.统计有多少个=x；2.统计有多少个 !=x
//统计多少个=x
void del_x(SqList &L,ElemType x){
int k=0;
for(int i=0;i<n;i++){
if(L.data[i]==x) //遍历这个数组时，发现有一个等于x，则k++，而不做其他操作
k++;
else{ //此时元素不等于x，则进行前移，它移动完，他就空了，实际上前移了多少个元素（删了多少个x），这个裂缝就会有多少个元素这么长
L.data[i-k]=L.data[i];
}
L.length=L.length-k; //最后修改表长
}
}
//统计非x元素
void del_x(SqList &L,ElemType x){
int k=0;
for(int i=0;i<n;i++){
if(L.data[i]!=x){ 若这个循环没发现x，则k一直等于i，自身和自身赋值，发现一个x则k和i就会差1，有几个x就差几，然后就会前移几，实现功能
L.data[k]=L.data[i];
k++;
}
L.length=k; //最后修改表长
}
}
有序顺序表，值相同的元素一定在连续的位置上，用类似于直插排序的思想
初始时将第一个元素视为不重复的有序表。之后依次判断后面的是否与前面重复（直插是判断是否大于这个元素，这里是判断是否相等）
//一趟循环，用i标记不相同的元素，j 工作指针进行遍历；
//有相同的就继续往后找，找到了不同的元素，需要把他和上一个不同的元素连接起来，上一个不同的元素为 i，所以要放到i+1的位置。
bool Delete_same(SqList &L){
if(L.length==0)
return false;
int i,j; //i存储第一个不相同的元素，j为工作指针
for(i=0,j=1;j<L.length;j++){
if(L.data[i]!=L.data[j]) //找值不同的元素，//直插是无序的，现在是有序的。一趟循环即可解决，
L.data[++i]=L.data[j]; //把不同的元素插到i之后
}
L.length=i+1; //因为数组从0开始
return true;
}
//有序的单链表删重复
//结点在逻辑上也是相邻的。p扫描链表，若p和p->next 值一样，则删除后者。
void Del_same(LinkList &L){
LNode *p=L;
while(p->next!=NULL){
if(p->data==p->next->data){
LNode *q=p->next;
p->next=q->next;
free(q);
}
else{
p=p->next;
}
}
}
按顺序比较两个表头较小的结点，存入新的顺序表。直至有个表为空，把另一个剩余的，全部加入新表。
void Merge(SqList A,SqList B,SqList &C){
int i=0,j=0,k=0; //分别为A，B，C的遍历计数器
while(i<A.length&&j<B.length){ //都没完
if(A.data[i]<B.data[j]){ //找到A，B中较小的，把C[k]=A[i]，然后各自++。
C.data[k++]=A.data[i++];
else
C.data[k++]=B.data[j++];
}
while(i<A.length) //A没完，B肯定完了，下面那个其实不执行
C.data[k++]=A.data[i++];
while(j<B.length) //B没完，上面那个while没走
C.data[k++]=B.data[j++];
C.length=k;
}
//链表存储--合并
void Merge(LinkList &La,LinkList &Lb){
LNode *r; //暂存pa或pb的后继，防止断链。
LNode *pa=La->next,*pb=Lb->next; //各自的工作指针
La->next=NULL; //把La作为新的链表，头给他摘掉
while(pa&&pb){ //都还有，都没空
if(pa->data>pb->data){ //pa大，选pa插入La，递增需要头插，要递减呢，改条件！
r=pa->next; //暂存
pa->next=La->next ;
La->next=pa; //头插
pa=r; //恢复
}
else{ //插Lb的
r=pb->next;
pb->next=La->next ;
La->next=pb; //头插
pb=r; //恢复
}
} //while
if(pa)
pb=pa; //其实和那个while循环一样，我剩你就不剩，把我的给你，你去循环
while(pb){
r=pb->next;
pb->next=La->next ;
La->next=pb; //头插
pb=r; //恢复
}
free(Lb);//合并完了 ，Lb释放
}
//本来为ab，先让a、b各自逆置，变为(a逆)(b逆),再整体逆置，-->ba
void Reverse(int A[],int from,int to){ //这里给边界因为有两个数组，需要各自逆置
int i,temp;
int mid=(from+to)/2; //中间点，左右两边交换
for(i=0;i<mid-from;i++){
temp=A[from+i];
A[from+i]=A[to-i];
A[to-i]=temp;
}
}
void Converse(int R[],int m,int n){
Reverse(A,0,n-1);
Reverse(A,n,n+m-1); //逆置第二个数组
Reverse(A,0,n+m-1); //整体逆置
}
//递归时需要借助递归工作栈，且深度为O(n),则空间复杂度为O(n)
void Dex(LinkList &L,int x){
Node *p; //指向待删除结点，
if(L==NULL)return ; //递归出口，一般都是啥啥为空
if(L->data==x){ //删完当前，继续向下递归
p=L;
L=L->next;
free(p);
Dex(L,x);
}
else //不符合条件，不删，直接往下递归。
Dex(L->next,x);
}
LinkList Search_com(LinkList L1,LinkList L2){
int len1=L1.length;
int len2=L2.length; //两表长，暂存
LinkList longList,shortList; //长表指针，短表指针
if(len1>len2){ //L1比较长
LinkList longList=L1->next; //L1设为长表
shortList=L2->next;
dist=len1-len2; //两表长度之差,（长的减去短的）
}
else{ //L2比较长
LinkList longList=L2->next; //L2设为长表
shortList=L1->next;
dist=len2-len1; //两表长度之差
}
//他们有一端是对齐的，即公共结点，多出来的肯定是不公共的。从对齐的地方开始比较
while(dist--) longList=longList->next; //让长的和短的对齐
while(longList!=NULL){ //同步寻找公共结点
if(longList==shortList)
return longList; //找到了公共结点，直接返回当前结点
else{
longList=longList->next;
shortList=shortList->next;
}
return NULL; //到最后都没返回，就没有
}
}
//每次遍历找到最小的元素，输出，并释放空间。
void Del_min(LinkList *L){
Node *pre,*p; //pre存最小值的前驱，便于删除，p为工作指针
while(L->next!=NULL){ //循环到只剩下头节点，删的就剩下他了
p=L->next;
pre=L;
while(p->next!=NULL){ //p不是最后一个结点
if(p->next->data<p->data)
pre=p; //p的下一个比p还小，则pre存最小元素的前驱，即p
p=p->next;
}
print(pre->next->data); //一整趟遍历出来最小的元素
Node *u=pre->next;
pre->next=u->next;
free(u);
}//大while
free(L); //把头也释放了
}
各自需要变量
拆成A直接尾插，而B为逆序，则需要头插
头插会断链，需要变量q暂存后继！！
尾插,需要尾指针 r ！！
LinkList Dispart(LinkList &A){
LinkList B=(LinkList)malloc(sizeof(LNode)); //创建B的表头
B->next=NULL;
LNode *p=A->next,*q;//工作指针p和暂存后继q
LNode *ra=A; //A的尾指针
//以上为准备工作
while(p!=NULL){
ra->next=p;ra=p; //A先尾插，
p=p->next; //后移
if(p!=NULL) q=p->next; //暂存p的后继，头插后恢复
p->next=B->next; //B头插
B->next=p;
p=q; //恢复
}
ra->next=NULL; //尾插需要置空
return B; //A由引用带回，B直接返回
}
算法思想：设置快慢指针。
fast和slow
fast每次走两步，slow每次走一步，fast先进入环，slow后进；
fast肯定会套圈，此时fast=slow证明有环。
列关系：时间相同，即路程比速度相同
slow速度为1，fast为2
slow走了a+x,则fast走了 a+x+n * r, 多走了n圈
(a+x)/1=(a+n*r+x)/2
化简得 a = n *r - x。
从头节点到环的入口的距离a等于n倍的环长减去入口到相遇点的距离。
可设置两个指针，分别指向head和相遇点。两个指针同步移动，相遇时就是入口…
LNode * FindStart(LNode *head){
LNode *fast,*slow;
fast=head;
slow=head;
while(slow!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(slow==fast) break;
} //此循环结束，1要么fas或slow为空了（无环），2要么相遇了（fast=slow）
if(slow==NULL||fast->next==NULL)
return NULL; //无环
//利用公式找到入口！！！，一个从头，一个从相遇点，同步后移，直到相遇
LNode *p1=head,*p2=slow;
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}
return p1;
}
|