#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n#include <math.h>\n#define MaxSize 50\ntypedef int ElemType ;\n//界说次序表\ntypedef struct{\n ElemType data[MaxSize];\n int length;\n}SqList;\n//界说单链表\ntypedef struct LNode{\n ElemType data;\n struct LNode *next;\n}LNode,*LinkList;\n//界说双链表\ntypedef struct DNode{\n ElemType data;\n struct DNode *next,*prior;\n}DNode,*DLinkList;\n//初始化次序表\nvoid InitList(SqList &L){\n for(int i=0;i<MaxSize;i++){\n L.data[i]=0;\n }\n L.length=0;\n}\n//打印单链表\nvoid printList(LinkList L){\n LNode *p=L->next;\n while(p!=NULL){\n printf("%d\\t",p->data);\n p=p->next;\n }\n printf("\\n");\n}\n//打印双链表\nvoid printDList(DLinkList L){\n DNode *p=L->next;\n while(p!=L){\n printf("%d\\t",p->data);\n p=p->next;\n }\n printf("\\n");\n}\n//核算长度\nint length(LinkList L){\n LNode *p=L->next;\n int len=0;\n while(p!=NULL){\n len++;\n p=p->next;\n }\n return len;\n}\n//头插法树立双链表\nDLinkList create_DL(DLinkList &L){\n DNode *s;\n int x;\n L=(DNode *)malloc(sizeof(DNode));\n L->next=L->prior=NULL;\n scanf("%d",&x);\n while(x!=9999){\n s=(DNode *)malloc(sizeof(DNode));\n s->data=x;\n s->next=s->prior=NULL;\n s->next=L->next;\n L->next->prior=s;\n s->prior=L;\n L->next=s;\n scanf("%d",&x);\n }\n return L;\n}\n//P17 1\nint deleteElement(SqList &L){\n int i,temp=0,min=L.data[0];\n if(L.length>0){\n for(i=0;i<L.length;i++){\n if(L.data[i]<min){\n min=L.data[i];\n temp=i;\n }\n }\n L.data[temp]=L.data[L.length-1];\n }else{\n printf("Error!\\n");\n }\n return min;\n}\n//核算方差\ndouble fun(double x[10])\n{\n double sum=0.0,avg=0.0,s,temp=0.0;\n int i,j;\n for(i=0;i<10;i++){\n sum+=x[i];\n }\n avg=sum/10;\n for(j=0;j<10;j++){\n temp+=(x[j]-avg)*(x[j]-avg);\n }\n s=sqrt(temp/10);\n return s;\n}\n//P17 2\nvoid reverse(SqList &L){\n int temp;\n for(int i=0;i<L.length/2;i++){\n temp=L.data[i];\n L.data[i]=L.data[L.length-1-i];\n L.data[L.length-1-i]=temp;\n }\n}\n//P17 3\nvoid del_x(SqList &L,ElemType e){\n int i,k=0;\n for(i=0;i<L.length;i++){\n if(L.data[i]!=e){\n L.data[k]=L.data[i];\n k++;\n }\n }\n L.length=k;\n}\nvoid del_x_1(SqList &L,ElemType e){\n int i=0,k=0;\n while(i<L.length){\n if(L.data[i]==e)\n k++;\n else\n L.data[i-k]=L.data[i];\n i++;\n }\n L.length-=k;\n}\n//删去s-t其间的元素\nvoid del_s_t(ElemType s,ElemType t,SqList &L){\n int i,j;\n //判别规模\n if(s>=t || L.length==0){\n printf("Error!");\n }\n //找到第一个要删去的元素\n for(i=0;i<L.length && L.data[i]<s;i++);\n //判别规模\n if(i>=L.length)\n printf("Error!");\n //找到最终一个删去元素的下一个元素\n for(j=i;j<L.length && L.data[j]<=t;j++);\n //循环将相关元素移动\n for(;j<L.length;j++,i++){\n L.data[i]=L.data[j];\n }\n L.length=i;\n}\n//自己的主意\nvoid del_s_t_1(ElemType s,ElemType t,SqList &L){\n int i,j,k=0;\n for(i=0;i<L.length;i++){\n if(L.data[i]>=s && L.data[i]<=t){\n k++;\n }else{\n for(j=0;j<k;j++){\n L.data[j+i-k]=L.data[i+j];\n }\n }\n }\n L.length-=k;\n}\n//有序表删去相同元素\nvoid del_key(SqList &L){\n int i,j;\n for(i=0,j=1;j<L.length;j++){\n if(L.data[i]!=L.data[j]){\n L.data[++i]=L.data[j];\n }\n }\n L.length=i+1;\n}\n//兼并两个有序次序表\nbool mergeList(SqList &L1,SqList &L2,SqList L){\n int i=0,j=0,k=0;\n if(L1.length+L2.length>L.length)\n return false;\n //只需中心有一个次序表完毕就停止循环\n while(i<L1.length && j<L2.length){\n //L1中元素小于L2元素\n if(L1.data[i]<=L2.data[j]){\n L.data[k++]=L1.data[i++];\n }\n //L2中元素小于L1\n if(L2.data[j]<L1.data[i]){\n L.data[k++]=L2.data[j++];\n }\n }\n //L1中元素剩余\n while(i<L1.length){\n L.data[k++]= L1.data[i++];\n }\n while(j<L2.length){\n L.data[k++]=L2.data[j++];\n }\n L.length=k;\n}\n//p17 9\nvoid reverse(ElemType A[],int left,int right,int arraySize){\n int mid=(left+right)/2;\n if(left>right || right>arraySize)\n return;\n for(int i=0;i<mid-left;i++){\n ElemType temp=A[left+i];\n A[left+i]=A[right-i];\n A[right-i]=temp;\n }\n}\nvoid exchange(ElemType A[],int m,int n,int arrraySize){\n reverse(A,0,m+n-1,arrraySize);\n reverse(A,0,n-1,arrraySize);\n reverse(A,n,m+n-1,arrraySize);\n}\n//p17 9\nvoid find_x(SqList &L,ElemType x){\n int low=0,high=L.length-1,mid;\n //减半查找\n while(low<=high){\n mid=(low+high)/2;\n if(L.data[mid]==x){\n break;\n }else if(L.data[mid]>x){\n high=mid-1;\n }else{\n low=mid+1;\n }\n }\n //直接mid查到\n if(L.data[mid]==x && mid<=L.length-1){\n int temp=L.data[mid];\n L.data[mid]=L.data[mid+1];\n L.data[mid+1]=temp;\n }\n //查不到\n if(low>high){\n for(int j=L.length;j>=low;j--){\n L.data[j]=L.data[j-1];\n }\n L.data[low]=x;\n }\n}\n//将6-100之间的偶数表明为两个素数之和(哥德巴赫猜测)\nvoid mergeNum(){\n int i,j,k,a,b,count=0;\n int num[100];\n //表明一切偶数\n for(i=8;i<=100;i+=2){\n //核算每个偶数的素数\n for(j=2;j<i;j++){\n for(k=2;k<j;k++){\n //不是素数\n if(j%k==0){\n break;\n }\n }\n //是素数\n if(k==j){\n num[count++]=j;\n }\n }\n //找该元素的一切素数之和\n for(a=0;a<count-1;a++){\n for(b=a+1;b<count;b++){\n if(num[a]+num[b]==i){\n //printf("%d\\t",count);\n printf("%d+%d=%d\\t",num[a],num[b],i);\n }\n }\n }\n printf("\\n");\n count=0;\n }\n}\n//P17 11找两个升序序列的中位数\nElemType find_mid_x(SqList &L1,SqList &L2,SqList &L){\n int i=0,j=0,k=0;\n while(i<L1.length && j<L2.length){\n //别离比较排序\n if(L1.data[i]<L2.data[j]){\n L.data[k++]=L1.data[i++];\n }else{\n L.data[k++]=L2.data[j++];\n }\n }\n //L1还有剩余\n while(i<L1.length) L.data[k++]=L1.data[i++];\n //L2还有剩余\n while(j<L2.length) L.data[k++]=L2.data[j++];\n L.length=L1.length+L2.length;\n return L.data[L.length/2+1];\n}\n//找出数组中的主元素\nElemType find_element(SqList &L){\n int i,j,k=0,count=0,temp[L.length];\n //挑选查找每一个元素的呈现次数\n for(i=0;i<L.length-1;i++){\n for(j=0;j<L.length;j++){\n //假如元素持平,count++\n if(L.data[i]==L.data[j]){\n count++;\n }\n }\n //假如是主元素直接回来，不然持续循环\n if(count>L.length/2){\n return L.data[i];\n }else{\n count=0;\n }\n }\n //没有主元素\n return -1;\n}\n//p18 13\nint find_n(int A[],int n){\n //界说相关变量\n int i,*B;\n B=(int *)malloc(sizeof(int)*n);\n //将A中相关变量放在B中\n for(i=0;i<n;i++){\n if(A[i]>0 && A[i]<=n){\n B[A[i]-1]=A[i];\n }\n }\n for(i=0;i<n;i++){\n if(B[i]==0){\n return i+1;\n }\n }\n}\n//打印次序表\nvoid print(SqList L){\n for(int i=0;i<L.length;i++){\n printf("%d\\t",L.data[i]);\n }\n printf("\\n");\n}\n//头插法树立链表\nLinkList List_HeadInsert(LinkList &L){\n int x;\n LNode *s;\n //请求头节点\n L=(LNode *)malloc(sizeof(LNode));\n L->next=NULL;\n //输入要刺进的元素\n scanf("%d",&x);\n while(x!=9999){\n //为刺进节点请求地址\n s=(LNode*)malloc(sizeof(LNode));\n s->data=x;\n s->next=L->next;\n L->next=s;\n scanf("%d",&x);\n }\n return L;\n}\n//王道P37 1\nvoid Del_x_3(LinkList &L,ElemType x){\n LNode *p;\n //L为空直接回来\n if(L==NULL){\n return;\n }\n //找到数值\n if(L->data==x){\n p=L;\n L=L->next;\n free(p);\n Del_x_3(L,x);\n }else{\n Del_x_3(L->next,x);\n }\n}\n//王道 P38 2\nvoid Del_x_4(LinkList &L,ElemType x){\n LNode *p=L->next,*pre=L,*q;\n //遍历链表\n while(p!=NULL){\n //找到数值相同节点，删去\n if(p->data==x){\n q=p;\n p=p->next;\n pre->next=p;\n free(q);\n }else{\n pre=p;\n p=p->next;\n }\n }\n}\n//王道 P38 3\nvoid R_Print(LinkList &L){\n //先找到最终的元素\n if(L->next!=NULL){\n R_Print(L->next);\n }\n //反向输出\n if(L!=NULL){\n printf("%d\\t",L->data);\n }\n}\nvoid R_Ignorance_Head(LinkList &L){\n if(L!=NULL){\n R_Print(L->next);\n }\n}\n//王道P38 3\nLinkList Del_min_x(LinkList &L){\n //界说四个变量别离指向不同的方位\n LNode *pre=L,*p=pre->next;\n LNode *minpre=pre,*minp=p;\n //遍历链表\n while(p!=NULL){\n if(p->data<minp->data){\n minp=p;\n minpre=pre;\n }\n //后边持续遍历\n pre=p;\n p=p->next;\n }\n //删去最小元素\n minpre->next=minp->next;\n free(minp);\n return L;\n}\n//王道 P38 5(回转链表)\nLinkList Reverse_L(LinkList &L){\n //界说指针\n LNode *p,*r;\n //断链并存储地址\n p=L->next;\n L->next=NULL;\n while(p!=NULL){\n //保存下一个地址\n r=p->next;\n //头插\n p->next=L->next;\n L->next=p;\n //将p从头指向r\n p=r;\n }\n}\n//王道 p38 6\nLinkList Sort(LinkList &L){\n LNode *p,*r,*pre;\n //断链\n p=L->next;\n r=p->next;\n p->next=NULL;\n p=r;\n //遍历\n while(p!=NULL){\n //保存节点\n r=p->next;\n pre=L;\n while(pre->next!=NULL && pre->next->data<p->data){\n pre=pre->next;\n }\n //找到方位刺进方位\n p->next=pre->next;\n pre->next=p;\n p=r;\n }\n return L;\n}\n//王道 p38 7(删去介于两个数值之间的一切元素)\nLinkList Del_x_5(LinkList &L,int min,int max){\n //界说变量\n LNode *pre=L,*p=pre->next,*q;\n //开端循环\n while(p!=NULL){\n //判别是否介于两者之间\n if(p->data>min && p->data<max){\n q=p;\n pre->next=p->next;\n p=p->next;\n free(q);\n }else{\n pre=p;\n p=p->next;\n }\n }\n return L;\n}\n//王道 p38 8(查找两个链表的公共节点，暴力算法)\nLinkList Find_x(LinkList &L,LinkList L1,LinkList L2){\n LNode *p=L1->next,*q=L2->next,*r;\n L=(LNode *)malloc(sizeof(LNode));\n r=L;\n L->next=NULL;\n while(p!=NULL && q!=NULL){\n if(p->data==q->data){\n L->next=p;\n r=p;\n r->next=NULL;\n }\n p=p->next;\n q=q->next;\n }\n return L;\n}\n//第二种方法（先算出长度，然后将长的链表先遍历，然后再一起遍历）\nLinkList Find_x_1(LinkList &L1,LinkList &L2){\n //设置指针,核算长度\n LNode *longList,*shortList;\n int len1=length(L1),len2=length(L2),dist;\n //比较长度\n if(len1>len2){\n //指针确认指向\n longList=L1->next;\n shortList=L2->next;\n dist=len1-len2;\n }else{\n longList=L2->next;\n shortList=L1->next;\n dist=len2-len1;\n }\n //先将剩余的遍历完结\n while(dist--)\n longList=longList->next;\n //一起遍历\n while(longList!=NULL){\n if(longList==shortList){\n return longList;\n }\n longList=longList->next;\n shortList=shortList->next;\n }\n return NULL;\n}\n//P38 9将元素按递加排序后删去\nvoid Del_x_6(LinkList &L) {\n //只剩余头节点\n while (L->next != NULL) {\n //设置相关指针\n LNode *pre = L, *p = pre->next, *q;\n //遍历找到最小的元素\n while (p->next != NULL) {\n //判别\n if (p->next->data < pre->next->data) {\n pre = p;\n }\n p = p->next;\n }\n //展示节点，删去节点\n printf("%d", pre->next->data);\n q = pre->next;\n pre->next = q->next;\n free(q);\n }\n //开释头节点\n free(L);\n}\nLinkList resolve(LinkList &A){\n //设置相关节点\n int count=0;\n LinkList B=(LNode*)malloc(sizeof(LNode));\n B->next=NULL;\n LNode *p=A->next,*ra=A,*rb=B;\n //断链\n A->next=NULL;\n //遍历循环\n while(p!=NULL){\n count++;\n //奇偶性判别\n if(count%2==0){\n rb->next=p;\n rb=p;\n }else{\n ra->next=p;\n ra=p;\n }\n //p指向下一个元素\n p=p->next;\n }\n ra->next=NULL;\n ra->next=NULL;\n return B;\n}\n//王道 P38 11\nvoid resolve_1(LinkList &C,LinkList &A,LinkList &B){\n //声明链表\n A->next=NULL;\n B->next=NULL;\n //声明辅佐变量\n LNode *p=C->next;\n //声明A链表的链尾变量\n LNode *ra=A;\n //声明B的保存变量\n LNode *q;\n //断链\n C->next=NULL;\n //开端遍历\n while(p!=NULL){\n ra->next=p;\n ra=p;\n p=p->next;\n //保存地址\n if(p!=NULL){\n q=p->next;\n }\n //头插\n p->next=B->next;\n B->next=p;\n p=q;\n }\n}\n//王道 p38 13(删去有序链表中的重复元素)\nLinkList Del_x_7(LinkList &L){\n //界说相关辅佐变量\n LNode *pre=L,*p=pre->next,*q;\n //开端遍历\n while(p!=NULL){\n //判别\n if(pre->next->data==p->next->data){\n q=pre->next;\n pre->next=q->next;\n free(q);\n }else{\n pre=p;\n p=p->next;\n }\n }\n return L;\n}\n//P38 13(将两个单调递加的序列兼并成一个单调递减的序列）\nLinkList merge_L(LinkList &A,LinkList &B){\n //声明相关变量\n LNode *la=A->next,*lb=B->next,*r;\n //初始化A链表，断链\n A->next=NULL;\n //开端遍历(两个链表都不可认为空)\n while(la && lb){\n //比较\n if(la->data<lb->data){\n //保存地址\n r=la->next;\n //头插法\n la->next=A->next;\n A->next=la;\n la=r;\n }else{\n r=lb->next;\n lb->next=B->next;\n B->next=lb;\n lb=r;\n }\n }\n //处理剩余的链表段\n //无论谁剩余都将lb指向对应的地址\n if(la){\n lb=la;\n }\n //处理lb指向的地址\n while(lb){\n r=lb->next;\n lb->next=A->next;\n A->next=lb;\n lb=r;\n }\n free(lb);\n return A;\n}\n//王道 P38 14(从两个链表中找出公共元素，构成新的链表)\nLinkList create_c(LinkList &A,LinkList &B){\n //创立一个c链表\n LinkList C=(LNode*)malloc(sizeof(LNode));\n C->next=NULL;\n //尾插法设置尾端变量，还有两个辅佐变量\n LNode *r=C,*la=A->next,*lb=B->next;\n //遍历两个链表\n while(la && lb){\n //判别两个链表的元素巨细\n if(la->data<lb->data){\n la=la->next;\n }else if(la->data>lb->data){\n lb=lb->next;\n }else{\n LNode *s=(LNode *)malloc(sizeof(LNode));\n s->data=la->data;\n r->next=s;\n r=s;\n la=la->next;\n lb=lb->next;\n }\n }\n r->next=NULL;\n return C;\n}\n//王道 P38 16(判别B是不是A的子序列)\nbool rank_L(LinkList A,LinkList B){\n //两个辅佐指针\n LNode *pa=A->next,*pb=B->next;\n //记载A地址指针\n LNode *pre=A->next;\n //循环\n while(pa && pb){\n //判别\n if(pa->data==pb->data){\n pa=pa->next;\n pb=pb->next;\n }else{\n pa=pre->next;\n pb=B->next;\n pre=pre->next;\n }\n }\n //假如pb为空则是子序列\n if(pb==NULL){\n return true;\n }else{\n return false;\n }\n}\n\nint main() {\n DLinkList L;\n create_DL(L);\n printDList(L);\n}\n
