软件基础第一次上机作业

1、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*&

2、); 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-las

3、t=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 c

4、reat(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-ne

5、xt=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

6、);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; /两个递增的链表合并成递增的链表。 ty

7、pedef 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 mai