软件基础第一次上机作业.doc

.1、设有一个线性表E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表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(请输入数据：);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、将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。#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