实验报告三 堆栈的应用.doc

《数据结构》实验报告三
系别：
班级：
学号：
：
日期：
指导教师：
一、上机实验的问题和要求：
堆栈是运算受限制的单链表，其插入和删除的操作仅限于在表头位置上进行。本实验主要要求学生掌握堆栈的定义、堆栈的入栈、出栈特性。
实验容：
1. 编写一个程序，借助于栈实现将一个存储整型数据元素的单链表倒置。本程序实现时首先应该创建一个单链表，然后将单链表元素结点依次入栈，再依次出栈构成一个新的单链表，借助于单链表的先进后出特性，新构成的单链表是原单链表的反置。
2. 编写一个程序，借助于栈实现十进制数和其他进制（二，八，十六进制）之间的转换。由于十进制转换为其他进制，采取的计算方法是除2/8/16取余，余数依次入栈，直到商为0为止，然后再将堆栈中的数据依次弹出，构成的新的数据序列，就是进制转换后的结果。
二、程序设计的基本思想，原理和算法描述：
（包括程序的结构，数据结构，输入/输出设计，符号名说明等）
三、源程序及注释：
1．单链表和堆栈之间的相互操作
#include ""
#include ""
typedef int datatype;
/*栈结点的定义*/
typedef struct node
{
datatype data;
struct node * next;
}linkstack;
/*单链表结点的定义*/
typedef struct LNode{
datatype data;
struct LNode *next;
}* LinkList;
/*LinkList La,Lb,Lc;*/
void printlk(LinkList L) {
LinkList p;
p=L;
while (p) {
printf("%d -> ",p->data);
p = p->next;
}
printf("NULL\n");
}
void Free_List(LinkList Head)
{
LinkList Pointer; /*节点声明*/
while( Head!=NULL) /*判断链表是否结束，如果结束则结束循环*/
{
Pointer=Head; /*将Pointer指针指向链表头节点*/
Head=Head->next; /*将链表的头指针Head指向下一个节点*/
free(Pointer); /*释放Pointer指针所指节点*/
}
}
/*Creat linklist from head node. */
LinkList CreatList ()
{
int i,n;
LinkList L,p,q;
p=(LinkList)malloc(sizeof(LinkList));
printf("input the head data:");
scanf("%d",&p->data);
p->next=NULL;
L = q = p;
printf("Please input the number of data : ");
scanf("%d",&n);
for (i=0;i<n;i++) {
p=(LinkList)malloc(sizeof(LinkList));
printf("\n\n");
printf("input the %d data:",i+1);
scanf("%d",&p->data);
/*在q指针所指向的结点之后插入新输入的数据结点*/
______________________________
_________________________________
_______________________________________
}
return L;
}
linkstack *PushLinkStack(LinkList head)
{
linkstack *p,*top;