/*1.有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数*/#include 
    
     #include 
     
      using namespace std;struct node{  int data;  struct node *next;  };struct node *head; /*计算数据域为x的结点个数*/int List_count (int x){            int count=0;            node*p;            p=head;            while(p){                if (p->data==x)                {                    count++;                }                p=p->next;            }            return count;        }int main(){   struct node *p,*q,*t;    int i,n,a;    printf("输入data个数\n");    scanf("%d",&n);    head = NULL;    printf("输入data\n");    for(i=1;i<=n;i++){        scanf("%d",&a);        p=(struct node *)new(struct node);        p->data=a;        p->next=NULL;        if(head==NULL)            head=p;        else            q->next=p;        q=p;    }    /*打印这个链表*/    t= head;    printf("你输入的data为： \n");    while(t!=NULL){        printf("%d ",t->data);        t=t->next;          }        printf("\n");        printf("输入要计数的数据域x\n");        int x;        scanf("%d",&x);        printf("数据域为%d的节点个数为%d",x,List_count(x));    return 0;}/*2.有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。*/#include 
      
       #include 
       
        using namespace std;struct node{  int data;  struct node *next;  };int main(){   struct node *head,*p,*q,*t;    int i,n,a;    scanf("%d",&n);    head = NULL;    for(i=1;i<=n;i++){        scanf("%d",&a);        p=(struct node *)new(struct node);        p->data=a;        p->next=NULL;        if(head==NULL)            head=p;        else            q->next=p;        q=p;    }    scanf("%d",&a);    t= head;    while(t!=NULL){        if(t->next==NULL||t->next->data > a){            p=(struct node *)new(struct node);            p->data=a;            p->next=t->next;            t->next=p;            break;        }                t=t->next;    }    t=head;    while(t!=NULL){        printf("%d ",t->data);        t=t->next;    }    return 0;}/*3.编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。*/#include 
        
         #include 
         
          using namespace std;struct node{ int data; node * next;}*hda,*hdb;void text(){ node *tmp=hda; for(int i=1;i<=20;i++) { tmp->next=(node*)new(node); tmp=tmp->next; tmp->data=i; printf("%d ",tmp->data); } tmp->next=NULL; printf("\n");}void print(){ node *ta,*tb; ta=hda; ta=ta->next; while(ta!=NULL) printf("%d ",ta->data),ta=ta->next; printf("\n"); tb=hdb; tb=tb->next; while(tb!=NULL) printf("%d ",tb->data),tb=tb->next; printf("\n");}void div(node *a,node *b){ int cnt=1; node *ta,*tb,*tc; ta=a; tb=b; tc=a->next; while(tc!=NULL) { if(cnt&1) ta->next=tc,tc=tc->next,ta=ta->next; else tb->next=tc,tc=tc->next,tb=tb->next; cnt++; } ta->next=tb->next=NULL; return ;}int main(){ hda=(node*)new(node); hdb=(node*)new(node); text(); div(hda,hdb); print(); return 0; }/*4.假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性。*/node *p, *q;node *mergelink(){ node *h, *r; h=(node *)new(node); h->next=NULL; r=h;//r一直指着这条链的末尾 while (p!=NULL && q!=NULL) if (p->data<=q->data) { r->next=p; r=p;//r=p是因为刚才把p的第一个节点接到了h上，r的地址要继续指着h这条链的话必需把r的地址指向p，也就是刚刚接到h上的这个节点 p=p->next; } else { r->next=q; r=q; q=q->next; } if (p= =NULL) r->next=q; if (q= =NULL) r->next=p; return h; }node *mergelink(p, q);/*5. 设A=（a ,…,a ）和B=（b ,…,bn）均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x,y,y,z），在A’=B’=空表，则A=B；若A’=空表，而B’<>空表，或者两者均不为空表，且A’的首元小于B’的首元，则A
          
           B。（词典次序）试写一个比较A，B大小的算法（在算法中，不要破坏原表A和B，并且不一定先求得A’和B’才进行比较）。*/typedef struct { ElemType *elem; int length; int listsize;} SqList;char Compare(SqList A, SqList B){ int i,j; i = j = 0; if(A.length > A.listsize || B.length > B.listsize) return (OVERFLOW); if(A.elem && B.elem){ while(i <= A.length && j <= B.length){ if(A.elem[i] == B.elem[j]){ i++; j++; } else break; } if(!A.elem[i] && !B.elem[j]) return '='; if(A.elem[i] > B.elem[j]) return '>'; if(A.elem[i] < B.elem[j]) return '<'; }}/*6.设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，并允许在原表的存储空间外再增加一个附加的工作单元。*/void ConvertList( Seqlist *L){int t;//附加单元int i;for ( i=1 ; i < L->length/2 ; i++){ t = L->data[i];//交换数据 L -> data[ i ] = L -> data[ L -> length + 1 - i ] ; L -> data[ L -> length + 1 - i ] = t ;}}/*7.已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(提示：求并集不是归并!)*//*思路：处理好三种大于等于小于的情况就行了*/node*ha,*hb,*hc;void union(ha,ha,hc){ node*p,*q,*r,*s; hc=(node*)new(node); r=hc;p=ha;q=hb;//建立一个头结点，r总是指向HC链表的最后一个结点 while(p!=NULL && q!=NULL) { if(p->data
           
            data) { s=(node*)new(node); s->data=p->data; r->next=s; r=s; p=p->next; } else if(p->data>q->data) { s=(node*)new(node); s->data=q->data; r->next=s; r=s; q=q->next; } else //相等的情况，取其中一个，然后后移 { s=(node*)new(node); s->data=q->data; r->next=s; r=s; p=p->next; q=q->next; } } if(p==NULL) while(q!=NULL) { s=(node*)new(node); s->data=q->data; r->next=s; r=s; q=q->next; } if(q==NULL) while(p!=NULL) { s=(node*)new(node); s->data=p->data; r->next=s; r=s; p=p->next; } r->next=NULL; s=hc; hc=hc->next; free(s);}/*8.已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。*//*思路:釆用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。比较两个节点时，小的节点指针后移一位*/LinkList intersection(LinkList &la,LinkList &lb) { pa=la->next; pb=lb->next; pc=la; while(pa&&pb){ if(pa->data==pb->data) { pc->next=pa; pc=pa; pa=pa->next; u=pb; pb=pb->next; free(u); } else if (pa->data
            
             data) { u=pa; pa=pa->next; //后移指针 free(u) ; }else{ u=pb; pb=pb->next; free (u) ; } } //while 结束 while(pa){ u=pa; pa=pa->next; free (u) ; } while(pb){ u=pb; pb=pb->next; free(u) ; } pc->next=NULL; free (lb) ; return la;}