JSLENGTH(jslength方法)

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define MaxSize 50typedef int ElemType ;//定義順序表typedef struct{ ElemType data[MaxSize]; int length;}SqList;//定義單鏈表typedef struct LNode{ ElemType data; struct LNode *next;}LNode,*LinkList;//定義雙鏈表typedef struct DNode{ ElemType data; struct DNode *next,*prior;}DNode,*DLinkList;//初始化順序表void InitList(SqList &L){ for(int i=0;i<MaxSize;i++){ L.data[i]=0; } L.length=0;}//打印單鏈表void printList(LinkList L){ LNode *p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf(" ");}//打印雙鏈表void printDList(DLinkList L){ DNode *p=L->next; while(p!=L){ printf("%d ",p->data); p=p->next; } printf(" ");}//計算長度int length(LinkList L){ LNode *p=L->next; int len=0; while(p!=NULL){ len++; p=p->next; } return len;}//頭插法建立雙鏈表DLinkList create_DL(DLinkList &L){ DNode *s; int x; L=(DNode *)malloc(sizeof(DNode)); L->next=L->prior=NULL; scanf("%d",&x); while(x!=9999){ s=(DNode *)malloc(sizeof(DNode)); s->data=x; s->next=s->prior=NULL; s->next=L->next; L->next->prior=s; s->prior=L; L->next=s; scanf("%d",&x); } return L;}//P17 1int deleteElement(SqList &L){ int i,temp=0,min=L.data[0]; if(L.length>0){ for(i=0;i<L.length;i++){ if(L.data[i]<min){ min=L.data[i]; temp=i; } } L.data[temp]=L.data[L.length-1]; }el{ printf("Error! "); } return min;}//計算方差double fun(double x[10]){ double sum=0.0,avg=0.0,s,temp=0.0; int i,j; for(i=0;i<10;i++){ sum+=x[i]; } avg=sum/10; for(j=0;j<10;j++){ temp+=(x[j]-avg)*(x[j]-avg); } s=sqrt(temp/10); return s;}//P17 2void rever(SqList &L){ int temp; for(int i=0;i<L.length/2;i++){ temp=L.data[i]; L.data[i]=L.data[L.length-1-i]; L.data[L.length-1-i]=temp; }}//P17 3void del_x(SqList &L,ElemType e){ int i,k=0; for(i=0;i<L.length;i++){ if(L.data[i]!=e){ L.data[k]=L.data[i]; k++; } } L.length=k;}void del_x_1(SqList &L,ElemType e){ int i=0,k=0; while(i<L.length){ if(L.data[i]==e) k++; el L.data[i-k]=L.data[i]; i++; } L.length-=k;}//刪除s-t其中的元素void del_s_t(ElemType s,ElemType t,SqList &L){ int i,j; //判斷范圍 if(s>=t || L.length==0){ printf("Error!"); } //找到第一個要刪除的元素 for(i=0;i<L.length && L.data[i]<s;i++); //判斷范圍 if(i>=L.length) printf("Error!"); //找到最后一個刪除元素的下一個元素 for(j=i;j<L.length && L.data[j]<=t;j++); //循環(huán)將相關(guān)元素移動 for(;j<L.length;j++,i++){ L.data[i]=L.data[j]; } L.length=i;}//自己的想法void del_s_t_1(ElemType s,ElemType t,SqList &L){ int i,j,k=0; for(i=0;i<L.length;i++){ if(L.data[i]>=s && L.data[i]<=t){ k++; }el{ for(j=0;j<k;j++){ L.data[j+i-k]=L.data[i+j]; } } } L.length-=k;}//有序表刪除相同元素void del_key(SqList &L){ int i,j; for(i=0,j=1;j<L.length;j++){ if(L.data[i]!=L.data[j]){ L.data[++i]=L.data[j]; } } L.length=i+1;}//合并兩個有序順序表bool mergeList(SqList &L1,SqList &L2,SqList L){ int i=0,j=0,k=0; if(L1.length+L2.length>L.length) return fal; //只要中間有一個順序表結(jié)束就終止循環(huán) while(i<L1.length && j<L2.length){ //L1中元素小于L2元素 if(L1.data[i]<=L2.data[j]){ L.data[k++]=L1.data[i++]; } //L2中元素小于L1 if(L2.data[j]<L1.data[i]){ L.data[k++]=L2.data[j++]; } } //L1中元素剩余 while(i<L1.length){ L.data[k++]= L1.data[i++]; } while(j<L2.length){ L.data[k++]=L2.data[j++]; } L.length=k;}//p17 9void rever(ElemType A[],int left,int right,int arraySize){ int mid=(left+right)/2; if(left>right || right>arraySize) return; for(int i=0;i<mid-left;i++){ ElemType temp=A[left+i]; A[left+i]=A[right-i]; A[right-i]=temp; }}void exchange(ElemType A[],int m,int n,int arrraySize){ rever(A,0,m+n-1,arrraySize); rever(A,0,n-1,arrraySize); rever(A,n,m+n-1,arrraySize);}//p17 9void find_x(SqList &L,ElemType x){ int low=0,high=L.length-1,mid; //折半查找 while(low<=high){ mid=(low+high)/2; if(L.data[mid]==x){ break; }el if(L.data[mid]>x){ high=mid-1; }el{ low=mid+1; } } //直接mid查到 if(L.data[mid]==x && mid<=L.length-1){ int temp=L.data[mid]; L.data[mid]=L.data[mid+1]; L.data[mid+1]=temp; } //查不到 if(low>high){ for(int j=L.length;j>=low;j--){ L.data[j]=L.data[j-1]; } L.data[low]=x; }}//將6-100之間的偶數(shù)表示為兩個素數(shù)之和(哥德巴赫猜想)void mergeNum(){ int i,j,k,a,b,count=0; int num[100]; //表示所有偶數(shù) for(i=8;i<=100;i+=2){ //計算每個偶數(shù)的素數(shù) for(j=2;j<i;j++){ for(k=2;k<j;k++){ //不是素數(shù) if(j%k==0){ break; } } //是素數(shù) if(k==j){ num[count++]=j; } } //找該元素的所有素數(shù)之和 for(a=0;a<count-1;a++){ for(b=a+1;b<count;b++){ if(num[a]+num[b]==i){ //printf("%d ",count); printf("%d+%d=%d ",num[a],num[b],i); } } } printf(" "); count=0; }}//P17 11找兩個升序序列的中位數(shù)ElemType find_mid_x(SqList &L1,SqList &L2,SqList &L){ int i=0,j=0,k=0; while(i<L1.length && j<L2.length){ //分別比較排序 if(L1.data[i]<L2.data[j]){ L.data[k++]=L1.data[i++]; }el{ L.data[k++]=L2.data[j++]; } } //L1還有剩余 while(i<L1.length) L.data[k++]=L1.data[i++]; //L2還有剩余 while(j<L2.length) L.data[k++]=L2.data[j++]; L.length=L1.length+L2.length; return L.data[L.length/2+1];}//找出數(shù)組中的主元素ElemType find_element(SqList &L){ int i,j,k=0,count=0,temp[L.length]; //選擇查找每一個元素的出現(xiàn)次數(shù) for(i=0;i<L.length-1;i++){ for(j=0;j<L.length;j++){ //如果元素相等,count++ if(L.data[i]==L.data[j]){ count++; } } //如果是主元素直接返回，否則繼續(xù)循環(huán) if(count>L.length/2){ return L.data[i]; }el{ count=0; } } //沒有主元素 return -1;}//p18 13int find_n(int A[],int n){ //定義相關(guān)變量 int i,*B; B=(int *)malloc(sizeof(int)*n); //將A中相關(guān)變量放在B中 for(i=0;i<n;i++){ if(A[i]>0 && A[i]<=n){ B[A[i]-1]=A[i]; } } for(i=0;i<n;i++){ if(B[i]==0){ return i+1; } }}//打印順序表void print(SqList L){ for(int i=0;i<L.length;i++){ printf("%d ",L.data[i]); } printf(" ");}//頭插法建立鏈表LinkList List_HeadInrt(LinkList &L){ int x; LNode *s; //申請頭節(jié)點 L=(LNode *)malloc(sizeof(LNode)); L->next=NULL; //輸入要插入的元素 scanf("%d",&x); while(x!=9999){ //為插入節(jié)點申請地址 s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); } return L;}//王道P37 1void Del_x_3(LinkList &L,ElemType x){ LNode *p; //L為空直接返回 if(L==NULL){ return; } //找到數(shù)值 if(L->data==x){ p=L; L=L->next; free(p); Del_x_3(L,x); }el{ Del_x_3(L->next,x); }}//王道 P38 2void Del_x_4(LinkList &L,ElemType x){ LNode *p=L->next,*pre=L,*q; //遍歷鏈表 while(p!=NULL){ //找到數(shù)值相同節(jié)點，刪除 if(p->data==x){ q=p; p=p->next; pre->next=p; free(q); }el{ pre=p; p=p->next; } }}//王道 P38 3void R_Print(LinkList &L){ //先找到最后的元素 if(L->next!=NULL){ R_Print(L->next); } //反向輸出 if(L!=NULL){ printf("%d ",L->data); }}void R_Ignorance_Head(LinkList &L){ if(L!=NULL){ R_Print(L->next); }}//王道P38 3LinkList Del_min_x(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; } //后面繼續(xù)遍歷 pre=p; p=p->next; } //刪除最小元素 minpre->next=minp->next; free(minp); return L;}//王道 P38 5(反轉(zhuǎn)鏈表)LinkList Rever_L(LinkList &L){ //定義指針 LNode *p,*r; //斷鏈并存儲地址 p=L->next; L->next=NULL; while(p!=NULL){ //保存下一個地址 r=p->next; //頭插 p->next=L->next; L->next=p; //將p重新指向r p=r; }}//王道 p38 6LinkList Sort(LinkList &L){ LNode *p,*r,*pre; //斷鏈 p=L->next; r=p->next; p->next=NULL; p=r; //遍歷 while(p!=NULL){ //保存節(jié)點 r=p->next; pre=L; while(pre->next!=NULL && pre->next->data<p->data){ pre=pre->next; } //找到位置插入位置 p->next=pre->next; pre->next=p; p=r; } return L;}//王道 p38 7(刪除介于兩個數(shù)值之間的所有元素)LinkList Del_x_5(LinkList &L,int min,int max){ //定義變量 LNode *pre=L,*p=pre->next,*q; //開始循環(huán) while(p!=NULL){ //判斷是否介于兩者之間 if(p->data>min && p->data<max){ q=p; pre->next=p->next; p=p->next; free(q); }el{ pre=p; p=p->next; } } return L;}//王道 p38 8(查找兩個鏈表的公共節(jié)點，暴力算法)LinkList Find_x(LinkList &L,LinkList L1,LinkList L2){ LNode *p=L1->next,*q=L2->next,*r; L=(LNode *)malloc(sizeof(LNode)); r=L; L->next=NULL; while(p!=NULL && q!=NULL){ if(p->data==q->data){ L->next=p; r=p; r->next=NULL; } p=p->next; q=q->next; } return L;}//第二種方法（先算出長度，然后將長的鏈表先遍歷，然后再同時遍歷）LinkList Find_x_1(LinkList &L1,LinkList &L2){ //設(shè)置指針,計算長度 LNode *longList,*shortList; int len1=length(L1),len2=length(L2),dist; //比較長度 if(len1>len2){ //指針確定指向 longList=L1->next; shortList=L2->next; dist=len1-len2; }el{ longList=L2->next; shortList=L1->next; dist=len2-len1; } //先將多余的遍歷完成 while(dist--) longList=longList->next; //同時遍歷 while(longList!=NULL){ if(longList==shortList){ return longList; } longList=longList->next; shortList=shortList->next; } return NULL;}//P38 9將元素按遞增排序后刪除void Del_x_6(LinkList &L) { //只剩下頭節(jié)點 while (L->next != NULL) { //設(shè)置相關(guān)指針 LNode *pre = L, *p = pre->next, *q; //遍歷找到最小的元素 while (p->next != NULL) { //判斷 if (p->next->data < pre->next->data) { pre = p; } p = p->next; } //展現(xiàn)節(jié)點，刪除節(jié)點 printf("%d", pre->next->data); q = pre->next; pre->next = q->next; free(q); } //釋放頭節(jié)點 free(L);}LinkList resolve(LinkList &A){ //設(shè)置相關(guān)節(jié)點 int count=0; LinkList B=(LNode*)malloc(sizeof(LNode)); B->next=NULL; LNode *p=A->next,*ra=A,*rb=B; //斷鏈 A->next=NULL; //遍歷循環(huán) while(p!=NULL){ count++; //奇偶性判斷 if(count%2==0){ rb->next=p; rb=p; }el{ ra->next=p; ra=p; } //p指向下一個元素 p=p->next; } ra->next=NULL; ra->next=NULL; return B;}//王道 P38 11void resolve_1(LinkList &C,LinkList &A,LinkList &B){ //聲明鏈表 A->next=NULL; B->next=NULL; //聲明輔助變量 LNode *p=C->next; //聲明A鏈表的鏈尾變量 LNode *ra=A; //聲明B的保存變量 LNode *q; //斷鏈 C->next=NULL; //開始遍歷 while(p!=NULL){ ra->next=p; ra=p; p=p->next; //保存地址 if(p!=NULL){ q=p->next; } //頭插 p->next=B->next; B->next=p; p=q; }}//王道 p38 13(刪除有序鏈表中的重復(fù)元素)LinkList Del_x_7(LinkList &L){ //定義相關(guān)輔助變量 LNode *pre=L,*p=pre->next,*q; //開始遍歷 while(p!=NULL){ //判斷 if(pre->next->data==p->next->data){ q=pre->next; pre->next=q->next; free(q); }el{ pre=p; p=p->next; } } return L;}//P38 13(將兩個單調(diào)遞增的序列合并成一個單調(diào)遞減的序列）LinkList merge_L(LinkList &A,LinkList &B){ //聲明相關(guān)變量 LNode *la=A->next,*lb=B->next,*r; //初始化A鏈表，斷鏈 A->next=NULL; //開始遍歷(兩個鏈表都不可以為空) while(la && lb){ //比較 if(la->data<lb->data){ //保存地址 r=la->next; //頭插法 la->next=A->next; A->next=la; la=r; }el{ r=lb->next; lb->next=B->next; B->next=lb; lb=r; } } //處理剩下的鏈表段 //無論誰剩下都將lb指向?qū)?yīng)的地址 if(la){ lb=la; } //處理lb指向的地址 while(lb){ r=lb->next; lb->next=A->next; A->next=lb; lb=r; } free(lb); return A;}//王道 P38 14(從兩個鏈表中找出公共元素，形成新的鏈表)LinkList create_c(LinkList &A,LinkList &B){ //創(chuàng)建一個c鏈表 LinkList C=(LNode*)malloc(sizeof(LNode)); C->next=NULL; //尾插法設(shè)置尾端變量，還有兩個輔助變量 LNode *r=C,*la=A->next,*lb=B->next; //遍歷兩個鏈表 while(la && lb){ //判斷兩個鏈表的元素大小 if(la->data<lb->data){ la=la->next; }el if(la->data>lb->data){ lb=lb->next; }el{ LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=la->data; r->next=s; r=s; la=la->next; lb=lb->next; } } r->next=NULL; return C;}//王道 P38 16(判斷B是不是A的子序列)bool rank_L(LinkList A,LinkList B){ //兩個輔助指針 LNode *pa=A->next,*pb=B->next; //記錄A地址指針 LNode *pre=A->next; //循環(huán) while(pa && pb){ //判斷 if(pa->data==pb->data){ pa=pa->next; pb=pb->next; }el{ pa=pre->next; pb=B->next; pre=pre->next; } } //如果pb為空則是子序列 if(pb==NULL){ return true; }el{ return fal; }}int main() { DLinkList L; create_DL(L); printDList(L);}