软件基础第一次上机作业

1、1、设有一个线性表 E=e1, e2,，en-1, en，设计一个算法，将线性表逆置，即使元素排 列次序颠倒过来，成为逆线性表E = en , en-1，e2 , el ,要求逆线性表占用原线性表 空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）线性表：#in clude#in cludetypedef char datatype;const int maxsize=1024;typedef struct datatype datamaxsize;int last;seque nlist;void create(seque nlist*&);vo

2、id prin t(seque nlist*);void in vert(seque nlist*);void mai n()seque nlist*L;create(L);printf(建立的顺序表是：”)； prin t(L);in vert(L);printf(逆置后的顺序表是：”)； prin t(L);void create(seque nlist*&L)L=(seque nlist*)malloc(sizeof(seque nlist);L-last=0;printf(请输入数据：”)；char ch;while(ch=getchar()!=n)L_last+;L-dataL-la

3、st=ch;void prin t(seque nlist*L)for(i nt i=1;ilast;i+)prin tf(%2c,L-datai);prin tf(n);void in vert(seque nlist*L)int n=L-last/2;for(i nt i=1;idatai;L-datai=L-dataL-last-i+1;L-dataL-last-i+1=temp;链表：#in clude #i nclude#i nclude typedef struct nodeint data;struct node *n ext;Li nkNode, *Li nkList;Lin

4、kList Creat(L in kList head); void In verse(L in kList head); void Output(L in kList head);Lin kList Creat(Li nkList head)/ 头插法建表char ch;Li nkList p = NULL;Lin kList q = NULL;head = (Lin kList) malloc (sizeof(L in kNode); head- next = NULL;q = head;while (ch=getchar()!=n)p = (Lin kList) malloc (size

5、of(L in kNode); p-data=ch;p_n ext=q _n ext;q_n ext = p;retur n head;void Inverse(LinkList head)/ 逆置 Lin kList p = head-n ext;Lin kList tmp = NULL;head- next = NULL;while (p!=NULL )tmp = p_n ext;p-n ext = head-n ext; head-next = p;p = tmp; void Output(LinkList head)/ 输出Lin kList p = head-n ext; while

6、 (p!= NULL)prin tf(%d , p-data);p = p-n ext;prin tf(n); int mai n(void)Lin kList head = NULL;head = Creat(head);printf(建立的单链表是：); Output(head);In verse(head);printf(逆置后的单链表是：); Output(head);system(pause);return 0;2、将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个 链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。#in cludeusing

7、 n amespace std;typedef int ElemType;/两个递增的链表合并成递增的链表。typedef struct LNodeElemType data;struct LNode *n ext;LNode;typedef LNode *Lin kList;void CreatList(Li nkList & L,i nt n)Lin kList p,q;L=new LNode;L- next=NULL;q=L;cout请从小到大输入链表的元素：;for (int i=1;i p-data;p_n ext=q _n ext;q_n ext=p;q=q_n ext;coutn

8、 ext;for (int j=1;j=n ;j+)coutdatan ext;coutn ext;pb=B-n ext;/C=t=A;/ Awhile (pa|pb)if (!pb|(pa&pb)&(pa-datadata) Illi将A的元素插入新表pc=pa;q=pa-n ext;pa-n ext=pre;pa=q;elsepc=pb;q=pb-n ext;pb-n ext=pre;pb=q; II将B的元素插入新表pre=pc;coutn ext=pc;pa=pc;for (int j=1;j=n ;j+)coutdatan ext;coute ndl;getchar();void mai n()Li nkList A,B,