軟件基礎(chǔ)第一次上機作業(yè).doc

.1、設(shè)有一個線性表E=e1, e2, , en-1, en，設(shè)計一個算法，將線性表逆置，即使元素排列次序顛倒過來，成為逆線性表E= en , en-1 , , e2 , e1 ，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個程序來完成。（文件夾：順序表逆置、單鏈表逆置）線性表：#include #includetypedef char datatype; const int maxsize=1024; typedef struct datatype datamaxsize; int last; sequenlist; void create(sequenlist*&); void print(sequenlist*); void invert(sequenlist*); void main()sequenlist*L; create(L); printf(建立的順序表是：);print(L); invert(L); printf(逆置后的順序表是：);print(L);void create(sequenlist*&L) L=(sequenlist*)malloc(sizeof(sequenlist); L-last=0; printf(請輸入數(shù)據(jù)：);char ch; while(ch=getchar()!=n) L-last+;L-dataL-last=ch;void print(sequenlist*L) for(int i=1;ilast;i+) printf(%2c,L-datai); printf(n);void invert(sequenlist*L) int n=L-last/2; for(int i=1;idatai; L-datai=L-dataL-last-i+1; L-dataL-last-i+1=temp; 鏈表：#include #include #include typedef struct nodeint data;struct node *next;LinkNode, *LinkList;LinkList Creat(LinkList head);void Inverse(LinkList head);void Output(LinkList head);LinkList Creat(LinkList head)/頭插法建表char ch;LinkList p = NULL;LinkList q = 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;return head;void Inverse(LinkList head)/逆置LinkList p = head-next;LinkList tmp = NULL;head-next = NULL;while (p!=NULL )tmp = p-next;p-next = head-next;head-next = p;p = tmp;void Output(LinkList head)/輸出LinkList p = head-next;while (p!= NULL)printf(%d , p-data);p = p-next;printf(n);int main(void)LinkList head = NULL;head = Creat(head);printf(建立的單鏈表是：);Output(head);Inverse(head);printf(逆置后的單鏈表是：);Output(head);system(pause); return 0;2、將兩個非遞減的有序鏈表合并為一個非遞減的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。#include using namespace std; typedef int ElemType; /兩個遞增的鏈表合并成遞增的鏈表。 typedef struct LNode ElemType data; struct LNode *next; LNode; typedef LNode *LinkList; void CreatList(LinkList &L,int n) LinkList p,q; L=new LNode; L-next=NULL; q=L; cout請從小到大輸入鏈表的元素：; for (int i=1;ip-data; p-next=q-next; q-next=p; q=q-next; coutnext; for (int j=1;j=n;j+) coutdatanext; coutnext; pb=B-next; / C=t=A;/ A while (pa|pb) if (!pb|(pa&pb)&(pa-datadata) /將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; coutnext=pc; pa=pc; for (int j=1;j=n;j+) coutdatanext; coutendl; getchar(); void main() LinkList A,B,C