lenth（全网最全线性表代码大全(顺序表）

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define MaxSize 50 typedef 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("%dt",p->data); p=p->next; } printf("n"); } //打印双链表 void printDList(DLinkList L){ DNode *p=L->next; while(p!=L){ printf("%dt",p->data); p=p->next; } printf("n"); } //计算长度 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 1 int 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]; }else{ printf("Error!n"); } 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 2 void reverse(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 3 void 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++; else 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++); //循环将相关元素移动 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++; }else{ 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 false; //只要中间有一个顺序表结束就终止循环 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 9 void reverse(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){ reverse(A,0,m+n-1,arrraySize); reverse(A,0,n-1,arrraySize); reverse(A,n,m+n-1,arrraySize); } //p17 9 void 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; }else if(L.data[mid]>x){ high=mid-1; }else{ 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之间的偶数表示为两个素数之和(哥德巴赫猜想) void mergeNum(){ int i,j,k,a,b,count=0; int num[100]; //表示所有偶数 for(i=8;i<=100;i+=2){ //计算每个偶数的素数 for(j=2;j<i;j++){ for(k=2;k<j;k++){ //不是素数 if(j%k==0){ break; } } //是素数 if(k==j){ num[count++]=j; } } //找该元素的所有素数之和 for(a=0;a<count-1;a++){ for(b=a+1;b<count;b++){ if(num[a]+num[b]==i){ //printf("%dt",count); printf("%d+%d=%dt",num[a],num[b],i); } } } printf("n"); count=0; } } //P17 11找两个升序序列的中位数 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++]; }else{ 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]; } //找出数组中的主元素 ElemType find_element(SqList &L){ int i,j,k=0,count=0,temp[L.length]; //选择查找每一个元素的出现次数 for(i=0;i<L.length-1;i++){ for(j=0;j<L.length;j++){ //如果元素相等,count++ if(L.data[i]==L.data[j]){ count++; } } //如果是主元素直接返回，否则继续循环 if(count>L.length/2){ return L.data[i]; }else{ count=0; } } //没有主元素 return -1; } //p18 13 int find_n(int A[],int n){ //定义相关变量 int i,*B; B=(int *)malloc(sizeof(int)*n); //将A中相关变量放在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("%dt",L.data[i]); } printf("n"); } //头插法建立链表 LinkList List_HeadInsert(LinkList &L){ int x; LNode *s; //申请头节点 L=(LNode *)malloc(sizeof(LNode)); L->next=NULL; //输入要插入的元素 scanf("%d",&x); while(x!=9999){ //为插入节点申请地址 s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); } return L; } //王道P37 1 void Del_x_3(LinkList &L,ElemType x){ LNode *p; //L为空直接返回 if(L==NULL){ return; } //找到数值 if(L->data==x){ p=L; L=L->next; free(p); Del_x_3(L,x); }else{ Del_x_3(L->next,x); } } //王道 P38 2 void Del_x_4(LinkList &L,ElemType x){ LNode *p=L->next,*pre=L,*q; //遍历链表 while(p!=NULL){ //找到数值相同节点，删除 if(p->data==x){ q=p; p=p->next; pre->next=p; free(q); }else{ pre=p; p=p->next; } } } //王道 P38 3 void R_Print(LinkList &L){ //先找到最后的元素 if(L->next!=NULL){ R_Print(L->next); } //反向输出 if(L!=NULL){ printf("%dt",L->data); } } void R_Ignorance_Head(LinkList &L){ if(L!=NULL){ R_Print(L->next); } } //王道P38 3 LinkList 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; } //后面继续遍历 pre=p; p=p->next; } //删除最小元素 minpre->next=minp->next; free(minp); return L; } //王道 P38 5(反转链表) LinkList Reverse_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 6 LinkList Sort(LinkList &L){ LNode *p,*r,*pre; //断链 p=L->next; r=p->next; p->next=NULL; p=r; //遍历 while(p!=NULL){ //保存节点 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(删除介于两个数值之间的所有元素) LinkList Del_x_5(LinkList &L,int min,int max){ //定义变量 LNode *pre=L,*p=pre->next,*q; //开始循环 while(p!=NULL){ //判断是否介于两者之间 if(p->data>min && p->data<max){ q=p; pre->next=p->next; p=p->next; free(q); }else{ pre=p; p=p->next; } } return L; } //王道 p38 8(查找两个链表的公共节点，暴力算法) 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){ //设置指针,计算长度 LNode *longList,*shortList; int len1=length(L1),len2=length(L2),dist; //比较长度 if(len1>len2){ //指针确定指向 longList=L1->next; shortList=L2->next; dist=len1-len2; }else{ 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) { //只剩下头节点 while (L->next != NULL) { //设置相关指针 LNode *pre = L, *p = pre->next, *q; //遍历找到最小的元素 while (p->next != NULL) { //判断 if (p->next->data < pre->next->data) { pre = p; } p = p->next; } //展现节点，删除节点 printf("%d", pre->next->data); q = pre->next; pre->next = q->next; free(q); } //释放头节点 free(L); } LinkList resolve(LinkList &A){ //设置相关节点 int count=0; LinkList B=(LNode*)malloc(sizeof(LNode)); B->next=NULL; LNode *p=A->next,*ra=A,*rb=B; //断链 A->next=NULL; //遍历循环 while(p!=NULL){ count++; //奇偶性判断 if(count%2==0){ rb->next=p; rb=p; }else{ ra->next=p; ra=p; } //p指向下一个元素 p=p->next; } ra->next=NULL; ra->next=NULL; return B; } //王道 P38 11 void 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(删除有序链表中的重复元素) LinkList Del_x_7(LinkList &L){ //定义相关辅助变量 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); }else{ pre=p; p=p->next; } } return L; } //P38 13(将两个单调递增的序列合并成一个单调递减的序列） LinkList merge_L(LinkList &A,LinkList &B){ //声明相关变量 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; }else{ r=lb->next; lb->next=B->next; B->next=lb; lb=r; } } //处理剩下的链表段 //无论谁剩下都将lb指向对应的地址 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){ //创建一个c链表 LinkList C=(LNode*)malloc(sizeof(LNode)); C->next=NULL; //尾插法设置尾端变量，还有两个辅助变量 LNode *r=C,*la=A->next,*lb=B->next; //遍历两个链表 while(la && lb){ //判断两个链表的元素大小 if(la->data<lb->data){ la=la->next; }else if(la->data>lb->data){ lb=lb->next; }else{ 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; //循环 while(pa && pb){ //判断 if(pa->data==pb->data){ pa=pa->next; pb=pb->next; }else{ pa=pre->next; pb=B->next; pre=pre->next; } } //如果pb为空则是子序列 if(pb==NULL){ return true; }else{ return false; } } int main() { DLinkList L; create_DL(L); printDList(L); }