软件基础第一次上机作业

1、设有一个线性表E={e1,e2,…,en-1,en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={en,en-1,…,e2,e1}，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）线性表：#includestdio.h#includemalloc.htypedefchardatatype;constintmaxsize=1024;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;voidcreate(sequenlist*&);voidprint(sequenlist*);voidinvert(sequenlist*);voidmain(){sequenlist*L;create(L);printf(建立的顺序表是：);print(L);invert(L);printf(逆置后的顺序表是：);print(L);}voidcreate(sequenlist*&L){L=(sequenlist*)malloc(sizeof(sequenlist));L-last=0;printf(请输入数据：);charch;while((ch=getchar())!='\n'){L-last++;L-data[L-last]=ch;}}voidprint(sequenlist*L){for(inti=1;i=L-last;i++)printf(%2c,L-data[i]);printf(\n);}voidinvert(sequenlist*L){intn=L-last/2;for(inti=1;i=n;i++){chartemp=L-data[i];L-data[i]=L-data[L-last-i+1];L-data[L-last-i+1]=temp;}}链表：#includestdio.h#includestdlib.h#includemalloc.htypedefstructnode{intdata;structnode*next;}LinkNode,*LinkList;LinkListCreat(LinkListhead);voidInverse(LinkListhead);voidOutput(LinkListhead);LinkListCreat(LinkListhead)//头插法建表{charch;LinkListp=NULL;LinkListq=NULL;head=(LinkList)malloc(sizeof(LinkNode));head-next=NULL;q=head;while((ch=getchar())!='\n'){p=(LinkList)malloc(sizeof(LinkNode));p-data=ch;p-next=q-next;q-next=p;}returnhead;}voidInverse(LinkListhead)//逆置{LinkListp=head-next;LinkListtmp=NULL;head-next=NULL;while(p!=NULL){tmp=p-next;p-next=head-next;head-next=p;p=tmp;}}voidOutput(LinkListhead)//输出{LinkListp=head-next;while(p!=NULL){printf(%d,p-data);p=p-next;}printf(\n);}intmain(void){LinkListhead=NULL;head=Creat(head);printf(建立的单链表是：);Output(head);Inverse(head);printf(逆置后的单链表是：);Output(head);system(pause);return0;}2、将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。#includeiostreamusingnamespacestd;typedefintElemType;//两个递增的链表合并成递增的链表。typedefstructLNode{ElemTypedata;structLNode*next;}LNode;typedefLNode*LinkList;voidCreatList(LinkList&L,intn){LinkListp,q;L=newLNode;L-next=NULL;q=L;cout请从小到大输入链表的元素：;for(inti=1;i=n;i++){p=newLNode;cinp-data;p-next=q-next;q-next=p;q=q-next;}cout所创建得的递增有序链表为：;p=L-next;for(intj=1;j=n;j++){coutp-data;p=p-next;}coutendl;}voidCreatC(LinkList&A,LinkList&B,LinkList&C,intn){LinkListpa,pb,pc,pre=NULL/*C结点的上一个结点*/,q/*t*/;pa=A-next;pb=B-next;//C=t=A;//Awhile(pa||pb){if(!pb||((pa&&pb)&&(pa-datapb-data))){////将A的元素插入新表pc=pa;q=pa-next;pa-next=pre;pa=q;}else{pc=pb;q=pb-next;pb-next=pre;pb=q;//将B的元素插入新表}pre=pc;}cout合并后的递增有序链表为：;C=A;A-next=pc;pa=pc;for(intj=1;j=n;j++){coutpa-data;pa=pa-next;}coutendl;getchar();}voidmain(){LinkListA,B,C;intn,m,k;cout请输入链表A的长度：;cinn;CreatList(A,n);cout请输入链表B的长度：;cinm;CreatList(B,m);k=m+n;CreatC(A,B,C,k);system(0);getchar();}