设有一个线性表E = { e1, e2, … , en - 1, en },设计一个算法,将线性表逆置,即使元素排列次序颠倒过来,成为逆线性表E’={ en , en-1 , … , e2 , e1 },要求逆线性表占用原线性表空间,并且用顺序表和单链表两种方法表示,分别用两个程序来完成。
将链表倒置就是把原本指向右的链表方向反过来,让这个链表指向方向变成左,这样就可以不用移动链表的内存位置,就实现了链表的倒置。
顺序表就很简单了,互换就行了。
这是链表的:
#include<stdio.h>
#include<stdio.h>
typedef struct node
{
char data;
struct node *next;
}* linklist;
linklist creat();
void print(linklist head);
void Reversal(linklist head);
#include <stdio.h>
#include <stdlib.h>
int main()
{
linklist head=NULL;
head=creat();
printf("您输入的字符串是:");
print(head);
Reversal(head);
puts("逆置后的字符串是:");
print(head);
return 0;
}
linklist creat()
{
char ch;
linklist pNew,pEnd=NULL ;
linklist a = NULL;
a = (linklist)malloc(sizeof(linklist));
pEnd = a;
puts("请输入字符串(输入“*”结束):");
while ((ch = getchar()) != '*')
{
pNew = (linklist)malloc(sizeof(linklist)); //采用尾插法
pNew->data = ch;
pEnd->next = pNew;
pEnd = pNew;
}
pEnd->next = NULL;
return a;
}
void print(linklist head)
{
head = head->next;
while (head->next != NULL)
{
printf("%c ", head->data);
head = head->next;
}
printf("%c\n", head->data);
}
//void Reversal(linklist head)
//{
// linklist p, q, r;
// p = head->next;
// q = p->next;
// while (q != NULL)
// {
// r = q->next;
// q->next = p;
// p = q;
// q = r;
// }
// head->next->next = NULL;
// head->next = p;
//}
//单链表逆置 //两种都可以
void Reversal(linklist head)
{
linklist p, q;
p = head->next;
head->next = NULL;
while (p)
{
q = p;
p = p->next;
q->next = head->next;
head->next = q;
}
}
这是顺序表的:
#include "stdio.h"
#include "stdlib.h"
typedef struct student
{
char *data;
int m;
}*plink;
plink CreateLista(int x);
void printfplink(plink Lb);
plink Reversal(plink Lb);
int main()
{
plink La=NULL;
int x;
printf("请输入你字符串字符个数:");
scanf_s("%d", &x);
La=CreateLista(x);
printfplink(La);
La = Reversal(La);
printfplink(La);
return 0;
}
plink CreateLista(int x)
{
char ch, i;
plink L;
L = (plink)malloc(sizeof(plink));
L->m = x;
L->data = (char *)malloc((x * sizeof(char)));
printf("请输入一字符串(输入%d个结束):\n",x);
getchar(); //清除上次回车键
for (i = 0; i < x; i++) {
ch = getchar();
L->data[i] = ch;
}
return L;
}
void printfplink(plink Lb)
{
for (int i = 0; i < Lb->m; i++)
printf("%c ", Lb->data[i]);
printf("\n");
}
plink Reversal(plink Lb)
{
int x = Lb->m - 1;
char t;
for (int i = 0; i < (Lb->m)/2; i++,x--)
{
t = Lb->data[i];
Lb->data[i]= Lb->data[x];
Lb->data[x] = t;
}
return Lb;
}