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

1、设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）

线性表：#include<stdio.h>
#include<malloc.h>
typedef char datatype;
const int maxsize=1024;
typedef struct
{ datatype data[maxsize];
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->data[L->last]=ch;
}
}
void print(sequenlist*L)
{
for(int i=1;i<=L->last;i++)
printf("%2c",L->data[i]);
printf("\n");
}
void invert(sequenlist*L)
{
int n=L->last/2;
for(int i=1;i<=n;i++)
{
char temp=L->data[i];
L->data[i]=L->data[L->last-i+1];
L->data[L->last-i+1]=temp;
}
}

链表：#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

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 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<iostream>
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;i<=n;i++)
{
p=new LNode;
cin>>p->data;
p->next=q->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=A->next;
pb=B->next;
// C=t=A;// A
while (pa||pb)
{
if (!pb||((pa&&pb)&&(pa->data<pb->data)))
{
////将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;
}
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;
cout<<"请输入链表A的长度：";
cin>>n;
CreatList(A,n);
cout<<"请输入链表B的长度：";
cin>>m;
CreatList(B,m);
k=m+n;
CreatC(A,B,C,k);
system(0);
getchar();
}