《用栈将线性表逆置实验.docx》由会员分享，可在线阅读，更多相关《用栈将线性表逆置实验.docx（7页珍藏版）》请在三一办公上搜索。
1、用栈将线性表逆置实验数据结构课程设计题 实验2 栈 一、 实验的目的要求 1、 了解栈的特性，以及它在实际问题中的应用。 2、 掌握栈的实现方法以及它的基本操作，学会运用栈来解决问题。 二、 实验的主要内容 1、已知head是带头结点的单链表,有关说明如下： typedef int datatype; #include #define NULL 0 typedef struct node datatype data; struct node *next; linklist; linklist *head; 请设计一个算法，利用一个栈将上述单链表实现逆置，即利用一个栈将单链表逆置为。 调试运行实
2、例： 含多个结点的顺序表； 含一个结点的顺序表； 空表。 三、 栈的特性 1、栈是限定在表尾进行插入和删除操作的线性表。其表尾称为栈顶(top)，表头称为栈底(bottom)。栈的特点是后进先出。 出栈 入栈 栈顶 an a3 a2 栈底 a1 图2.1 栈的示意图 1 2、栈的基本操作 和线性表类似，栈也有两种存储结构，即顺序栈和链栈。 顺序栈可以定义为 #define maxsize 100 /*栈的最大元素数为100*/ typedef struct /*定义顺序栈*/ datatype dmaxsize; int top; seqstack; seqstack *s; /*定义顺序栈的
3、指针*/ 顺序栈的基本操作如下： 栈的初始化 void InitStack(seqstack *s) /*构造一个空栈s*/ s-top=-1; 入栈操作 seqstack *push(seqstack *s,datatype x) /*入栈*/ if(s-top=maxsize -1) printf(“栈已满，不能入栈！n”)； return NULL; else s-top+; /*栈顶指针上移*/ s-ds-top=x; /*将x存入栈中*/ return s; 出栈函数 datatype pop(seqstack *s) /*出栈*/ datatype y; if(s-top=-1)
4、printf(“栈为空，无法出栈！n”)； return 0; else y=s-ds-top; /*栈顶元素出栈，存入y中*/ s-top-; /*栈顶指针下移*/ return y; 判栈空函数 2 int StackEmpty(seqstack *s) if(s-top=-1) return 1; /*栈为空时返回1*/ else return 0; /*栈非空时返回0*/ 链栈可以定义为 #define NULL 0 typedef struct node /*定义链栈结点类型*/ datatype data; struct node *next; linkstack; linksta
5、ck *top; /*定义栈顶指针*/ 链栈的基本操作如下： 栈的初始化 void init_linkstack(linkstack *top) top=NULL; 入栈操作 linkstack *push_linkstack(linkstack *top, datatype x) linkstack *p; p=(linkstack *)malloc(sizeof(linkstack);/*开辟新结点*/ p-data=x; p-next=top; top=p; return top; 出栈函数 datatype pop_linkstack(linkstack *top) /*出栈*/ da
6、tatype y; linkstack *p; if(top=NULL) printf(“栈为空，无法出栈！n”)； return 0; else p=top; y=top-data; /*栈顶元素出栈，存入y中*/ top=top-next; /*栈顶指针下移*/ free(p); /*释放存储空间*/ return y; 3 判栈空函数 int empty_linkstack(linkstack *top) if(top=NULL) return 1; /*栈为空时返回1*/ else return 0; /*栈非空时返回0*/ 四、 解题思路 方法1 1、 建立一个带头结点的单链表hea
7、d； 2、 输出该单链表； 3、 建立一个空栈s； 4、 依次将单链表的数据入栈； 5、 依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域; 6、 再输出单链表。 程序如下(采用顺序栈实现)： typedef int datatype; #include 4 #define NULL 0 #define maxsize 100 /*设栈的最大元素数为100*/ typedef struct node datatype data; struct node *next; linklist; linklist *head; /*定义单链表的头指针*/ typedef struct /*定
8、义顺序栈*/ datatype dmaxsize; int top; seqstack; seqstack *s; /*定义顺序栈的指针*/ linklist *creatlist /*建立单链表*/ linklist *p,*q; /*int n=0;*/ p=q=(struct node *)malloc(sizeof(linklist); head=p; p-next=NULL; /*头结点的数据域不存放任何东西*/ p=(struct node *)malloc(sizeof(linklist); scanf(%d,&p-data); while(p-data!=-1) /*输入-1表
9、示链表结束*/ /*n=n+1;*/ q-next=p; q=p; p=(struct node *)malloc(sizeof(linklist); scanf(%d,&p-data); q-next=NULL; return head; void print(linklist *head;) /*输出单链表*/ linklist *p; p=head-next; if (p=NULL) printf(This is an empty list.n); else do printf(%6d,p-data); p=p-next; while(p!=NULL); printf(n); 5 voi
10、d InitStack(seqstack *s) /*构造一个空栈s*/ s-top=-1; seqstack *push(seqstack *s,datatype x) /*入栈*/ if(s-top=maxsize -1) printf(“栈已满，不能入栈！n”)； return NULL; else s-top+; /*栈顶指针上移*/ s-ds-top=x; /*将x存入栈中*/ return s; datatype pop(seqstack *s) /*出栈*/ datatype y; if(s-top=-1) printf(“栈为空，无法出栈！n”)； return 0; else
11、 y=s-ds-top; /*栈顶元素出栈，存入y中*/ s-top-; /*栈顶指针下移*/ return y; int StackEmpty(seqstack *s) if(s-top=-1) return 1; /*栈为空时返回1*/ else return 0; /*栈非空时返回0*/ linklist *back_linklist(linklist *head) /*利用栈s逆置单链表*/ linklist *p; p=head-next; /*p指向首元结点*/ InitStack(s); /*构造一个空栈，即栈的初始化*/ while(p) push(s, p-data); /*
12、链表结点中的数据入栈*/ p=p-next; /*p指针后移*/ 6 p=head-next; /*p再指向首元结点*/ while(!StackEmpty(S) /*当栈S非空时循环*/ p-data =pop(s); /*数据出栈,并存入p所指结点的数据域*/ p=p-next; /*p指针后移*/ return head; main linklist *head; head=creatlist; print(head); head= back_linklist(head); print(head); 此算法的时间复杂度为O(n)；算法的空间复杂度为O(n)。为什么？ 想一想，在上述问题中，能不能将链表结点中的地址入栈，来实现一个单链表的逆置？如果要求使用链栈来实现单链表的逆置，那么程序应该怎么修改？ 思考题 请设计一个算法，用一个栈S将一个队列Q逆置，要求采用顺序栈和顺序队列来实现；要求采用链栈和链队列来实现。 7
