|
设计一个算法，借助栈实现单链表链接顺序的逆转。 （真的又臭又长建议别看）
//设计算法借助栈实现单链表顺序逆转。创建一个单链表，然后创建一个空栈，把元素放进去在取出来
#include
#include
#include
#define Elemtype int
#define STACKINCREMENT 10
#define STACK_INIT_SIZE 20
//链表定义
typedef struct node
{
Elemtype data;
struct node* next;
}ListNode;
//栈的定义
typedef struct
{
Elemtype *top;
Elemtype *base;
int stackSize;
}SqStack;
//初始化
void InitStack(SqStack* s)
{
s->base = (Elemtype*)malloc(STACK_INIT_SIZE * sizeof(Elemtype));//分配空间
if (!s->base) //分配失败则退出
{
exit(0);
}
s->top = s->base;//初始化
s->stackSize = STACK_INIT_SIZE;//栈的容量等于初始设的值
}
//输出函数
void PrintListNode(node* p)
{
p = p->next;
if (p == NULL) {
printf("链表为空:\n");
}
else
{
printf("输出当前读入的链表：\n");
while (p != NULL)
{
printf("%d", p->data);
p = p->next;
}
}
}
//链表正序读入
node* CreatList()
{
int num = 0, len;
printf("请输入链表长度：\n");
scanf_s("%d", &len);
if (len next = NULL; //创建头结点
printf("请开始输入:\n");
for (int i = len - 1; i >= 0; i--)
{
q = (ListNode*)malloc(sizeof(ListNode));//新结点
scanf_s("%d", &q->data);
q->next = head->next;
head->next = q;
}
return head;
}
//进栈操作
void Push(SqStack *s, Elemtype e)
{
if (s->top - s->base >= s->stackSize) //检验是否满栈，栈满
{
s->base = (Elemtype*)realloc(s->base, (s->stackSize + STACK_INIT_SIZE) * sizeof(Elemtype));//重新分配空间，扩大栈的容量
if (!s->base) //再次进行检查
{
exit(0);
}
}
*(s->top) = e;
s->top++;
}
//出栈操作
void Pop(SqStack* s, Elemtype* e)
{
if (s->top == s->base)
{
return;
}
(s->top)--;
*e = *(s->top);
}
//求下栈长
int StackLen(SqStack s)
{
return(s.top - s.base);
}
//逆序
void Revers(node *head)
{
node *p = head;
SqStack s; Elemtype c; int len;
InitStack(&s);//初始化栈
while (p != NULL)
{
Push(&s, p->data);
p = p->next;
}
printf("输出逆转后的链表：\n");
len = StackLen(s);
while (len > 1) {
Pop(&s, &c);
printf("%d", c);
len--;
}
return;
}
int main()
{
node *head;
head = CreatList();
PrintListNode(head);
printf("\n");
Revers(head);
return 0;
}
（如果看了心情很不好真的又臭又长那就看下面的这个，是学长的）
#include
#include
typedef struct
{ //顺序栈定义
float *base; //栈底指针
float *top; //栈顶指针
int stacksize; //当前已分配的存储空间
} SeqStack;
typedef struct Node
{
float data;
struct Node *next;
} SeqNode,*SeqList;
int createList(SeqList& L); //创建并进行链表的输入
void printList(SeqList& L); //对链表中的数据进行输出
void tool(SeqList& L,SeqStack& M); //借助栈实现单链表链接顺序的逆转
void InitStack(SeqStack& M,int num); //对栈进行初始化
int main()
{
int num;
while(1)
{
SeqList L;SeqStack M;
printf("#直接向链表L中输入浮点数：\n");
num=createList(L);
InitStack(M,num);
printf("通过栈将链表中的数据进行倒转\n");
tool(L,M);
printf("#倒叙输出链表L中的浮点数：\n");
printList(L);
free(L);
}
}
int createList(SeqList& L)
{
L=(SeqList)malloc(sizeof(SeqNode));
SeqList head=L;
char temp='\0';
int n=0;
while(temp!='\n')
{
head->next=(SeqList)malloc(sizeof(SeqNode));
head=head->next;
scanf("%f",&head->data);
temp=getchar();
n++;
}
head->next=NULL;
return n;
}
void printList(SeqList& L)
{
SeqList head=L;
while(head->next!=NULL)
{
head=head->next;
printf("%g,",head->data);
}
printf("\n\n");
}
void tool(SeqList& L,SeqStack& M)
{
SeqList head=L;
while(head->next!=NULL)
{
head=head->next;
*(M.top++)=head->data;
}
head=L;
while(head->next!=NULL)
{
head=head->next;
head->data=*(--M.top);
}
}
void InitStack(SeqStack& M,int num)
{
M.stacksize=num;
M.base=(float*)malloc(sizeof(float)*num);
if(!M.base) exit;
M.top=M.base;
}
|