软件基础第一次上机作业

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

2、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(" 请输入数据："

3、);char ch;while(ch=getchar()!='n')L->last+;L->dataL->last=ch;void print(sequenlist*L)for(int i=1;i<=L->last;i+)printf("%2c",L->datai);printf("n");void invert(sequenlist*L) int n=L->last/2;for(int i=1;i<=n;i+) char temp=L->datai;L->datai=L->

4、;dataL->last-i+1;L->dataL->last-i+1=temp;链表： #include <>#include <>#include <>typedef struct node int data;struct node *next;LinkNode, *LinkList;LinkList Creat(LinkList head);void Inverse(LinkList head);void Output(LinkList head);LinkList Creat(LinkList head)/ 头插法建表 char c

5、h;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->n

6、ext;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

7、 head = NULL; head = Creat(head);printf(" 建立的单链表是：Output(head);Inverse(head);printf(" 逆置后的单链表是：Output(head); system("pause");return 0;");");2、将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。#include<iostream>using namespace std;typedef int E

8、lemType;/ 两个递增的链表合并成递增的链表。typedef struct LNodeElemType 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;i<=n;i+)p=new LNode;cin>>p->data;p->next=q-

9、>next;q->next=p;q=q->next;cout<<" 所创建得的递增有序链表为："p=L->next;for (int j=1;j<=n;j+)cout<<p->data<<" "p=p->next;cout<<endl;void CreatC(LinkList &A,LinkList &B,LinkList &C,int n)LinkList pa,pb,pc,pre=NULL/*C 结点的上一个结点*/,q/*t*/;pa=

10、A->next;pb=B->next;/ C=t=A;/ Awhile (pa|pb)if (!pb|(pa&&pb)&&(pa->data<pb->data)/将 A 的元素插入新表pc=pa;q=pa->next;pa->next=pre;pa=q;elsepc=pb;q=pb->next;pb->next=pre;pb=q; /将 B 的元素插入新表pre=pc;cout<<" 合并后的递增有序链表为："C=A;A->next=pc;pa=pc;for (int j=1;j<=n;j+)cout<<pa->data<<" "pa=pa->next;cout<<endl;getchar();void main()LinkList A,B,C;int n,m,k;