#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define status int #define elemtype int typedef struct lnode{ elemtype date; struct lnode *next; }node,*linklist; void init(linklist &l){ linklist p=(linklist)malloc(sizeof(lnode)); p->next=NULL; l=p; } status get_elem(linklist l,int i,elemtype &e){ ////L为带头结点的单链表的头指针, 当第i个元素存在时, 其值赋给e并返回OK, 否则返回ERROR struct lnode *p=NULL; p=l->next; elemtype j=1; while(p&&j<i){//若j<n,在while循环结束后j==i，指针p指向第i个节点 p=p->next; j++; } if(!p||j>i) return ERROR; e=p->date; return OK; } //插入和删除都是需要先便利值第i个位置的前一个节点 status listinsert(linklist &l,int i,elemtype &e){// 在第i个位置插入元素e，其实就是在第i个元素之前插入 linklist p=l; linklist s=NULL; elemtype j=0; while(p&&j<i-1){ p=p->next; j++; } if(!p||j>i-1) return ERROR; s=(linklist)malloc(sizeof(lnode)); s->date=e; s->next=p->next; p->next=s; return OK; } status listdelete(linklist &l,int i,elemtype &e){//删除第i个元素 linklist p=l; linklist q=NULL; elemtype j=0; while(p->next&&j<i-1){//注意此处的p->next,因为我们删除的下个节点必须不为NULL； p=p->next; j++; } if(!p->next||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->date; free(q); return OK; } void creatlist(linklist &l,int n){//倒序插入值建立链表 page：30 struct lnode *p=NULL; l=(linklist)malloc(sizeof(lnode)); l->next=NULL; for(int i=n;i>0;i--){ p=(linklist)malloc(sizeof(lnode)); scanf("%d",&p->date); p->next=l->next; l->next=p; } } void mergelist(linklist &la,linklist &lb,linklist &lc){ //已知单链线性表La和Lb的元素按值非递减排列 //归并La和Lb得到新的单链线性表Lc, Lc的元素也按值非递减排列 struct lnode *pa = NULL; struct lnode *pb = NULL; struct lnode *pc = NULL; pa=la->next; pb=lb->next; pc=lc=la; while(pa&&pb){ if(pa->date<=pb->date){ pc->next=pa; pc=pa; pa=pa->next; } else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; free(lb); } int get_pos(linklist &l,elemtype e,int n){//查找是否有元素e，有返回位序，没有返回0 linklist q=l; q=q->next; int j=1; while(j<=n){ if(q->date==e) break; j++; q=q->next; } if(j<=n) return j; return 0; } void Union(linklist &l1,linklist l2,elemtype &cnt){ //输入两个链表并分别构造，将l2中不含l1的元素插入到l1链表的尾部 //此调用函数的主函数是最后一个主函数 linklist p1=l1; linklist p11=l1; p1=p1->next; linklist p2=l2; p2=p2->next; while(p1){ p11=p1; p1=p1->next; cnt++; } int len1=cnt; while(p2){ int tmp=p2->date; int flag=get_pos(l1,tmp,len1); if(!flag){ linklist s=(linklist)malloc(sizeof(lnode)); s->date=tmp; s->next=NULL; p11->next=s; p11=s; cnt++; } p2=p2->next; } } int main(){ linklist l; // creatlist(l,0);//倒叙插入的时候，而且明确了元素的个数的时候使用，第二个参数传的值为元素的个数 init(l);//，没有明确个数，直接初始化的时候用 //上述两种初始化根据题意要求选择适合的 linklist p=l; int e,cnt=0;; while(~scanf("%d",&e)){ cnt++; listinsert(l,cnt,e); } printf("%d ",cnt);//输出元素的个数 // 逆序输出，i++的时候正序输出 for(int i=cnt;i>0;i--){ listdelete(l,i,e); printf("%d",e); } /*正序输出 ,和上面一样的，选一种即可 int x; scanf("%d",&x); p=p->next; while(p){ if(p->date>=x)//如果需要输出只比x大的数加上此行，如果需要输出只比x小的数把符号改变即可， printf("%d ",p->date); p=p->next; }*/ //输出链表中第pos个数 int pos; scanf("%d",&pos); get_elem(l,pos,e); printf("%d ",e); //查找线性表中是否有元素e，如果有，返回他的位序，否则返回0 scanf("%d",&e); int ans; ans= get_pos(l,e,cnt); printf("%d ",ans); return 0; } int main(){ //输入两个链表l1,l2,将l1,l2按照非递减顺序排列存到l3中 // 此主函数针对调用 mergelist（）函数 linklist l1,l2,l3; init(l1); init(l2); init(l3); int e,cnt=0; elemtype n1,n2,i; scanf("%d",&n1);//输入第一个链表的个数 for( i=1;i<=n1;i++){ cnt++; scanf("%d",&e); listinsert(l1,i,e); } scanf("%d",&n2);//输入第二个链表的个数 for( i=1;i<=n2;i++){ cnt++; scanf("%d",&e); listinsert(l2,i,e); } printf("%d ",cnt);//输出合并后的序列的个数 mergelist(l1,l2,l3); linklist p=l3; p=p->next; while(p){//按照顺序输出合并后的元素 printf("%d ",p->date); p=p->next; } return 0; } int main(){ //输入两个链表并分别构造，将l2中不含l1的元素插入到l1链表的尾部 linklist l1,l2; init(l1); init(l2); elemtype n1,n2,i,e,cnt=0; scanf("%d",&n1);//输入第一个链表的个数 for( i=1;i<=n1;i++){ scanf("%d",&e); listinsert(l1,i,e); } scanf("%d",&n2);//输入第二个链表的个数 for( i=1;i<=n2;i++){ scanf("%d",&e); listinsert(l2,i,e); } Union(l1,l2,cnt); printf("%d ",cnt);//输出合并后的序列的个数 linklist p=l1; p=p->next; while(p){ printf("%d ",p->date); p=p->next; } return 0; } /*样例 4 3 5 8 11 7 2 6 8 9 11 15 20 */