《数据结构》线性结构实验报告
- 格式：docx
- 大小：255.89 KB
- 文档页数：17
《数据结构》线性结构实验报告
一、实验目的：
1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现。
2.以线性表的各种操作（建立、插入、删除等）的实现为重点。
3.熟悉栈和队列的基本运算在两种存储结构（顺序结构和链式结构）上的实现。
4.以栈的应用操作为重点。
二、实验内容：
1.已知下列两个多项表达式：
A(x)=7+3x+9x8+5x17
B(x)=8x+22x7-9x8
编写程序进行表达式的创建并求出A8,(x)+B(x)的和。
表达式类型的定义如下：
typedef struct pnode
{ int coef; //系数
int exp; //指数
struct pnode *next; //指向下一结点
}PolyList;
2.编程序，利用顺序栈或链栈的基本操作（初始化、进栈、出栈及获取栈顶元素）来实现数制转换，并设计主函数来进行调用。
3.编程序，利用顺序栈或链栈的基本操作（初始化、进栈、出栈及取栈顶元素）来实现一个中缀表达式求值，并设计主函数来进行调用。
4.编程实现链队的基本操作（队列的初始化、判队列空、入队列、出队列）来解决舞伴问题，并设计主函数来进行调用。
三、实验过程与结论：（经调试正确的源程序（核心部分）和程序的运行结果）
1、源程序：
#include
#include
typedef struct pnode
{ int coef; //系数
int exp; //指数
struct pnode *next; //指向下一结点
}PolyList;
PolyList* CreatePoly()
{
PolyList *head, *p, *tail;
int ic,ie;
head=(PolyList *) malloc (sizeof(PolyList));
head->next=NULL;
tail=head; printf("请输入系数和数(c,e)，直到输入0结束：\n");
scanf("%d,%d", &ic,&ie);
while(ic!= 0)
{ p =(PolyList *)malloc(sizeof( PolyList ));
p->coef=ic;p->exp=ie;
tail->next=p;
tail=p;
tail->next=NULL;
scanf("%d,%d", &ic,&ie);
}
return(head);
}
void PolyAdd(PolyList *PLA, PolyList *PLB)
{ /*将两个多项式相加，然后将结果存放到多项式polya中，并释放多余结点*/
PolyList *pa,*pb,*tail,*s;
int sum;
pa = PLA->next;
pb = PLB->next;
tail=PLA;
PLB->next = NULL; /*指针初始化*/
while (pa != NULL && pb != NULL )
{ if ( pa->exp < pb->exp ) /*pa所指结点的指数小，将该结点插入和多项式*/
{ tail->next = pa; tail = pa; pa = pa->next; }
else if ( pa->exp > pb->exp ) /*pb所指结点的指数小，将该结点插入和多项式*/
{ tail->next = pb; tail = pb; pb = pb->next; }
else
{ sum = pa->coef + pb->coef;
if( sum!=0 ) /*若和不为0，将系数修改并插入和多项式链表 */
{ pa->coef = sum; tail->next = pa;tail = pa; pa = pa->next; s = pb; pb = pb->next;
free(s); }
else /*和为0，则删除pa与pb所指当前结点，并将pa、pb指针下移*/
{ s = pa; pa = pa->next; free(s); s = pb; pb = pb->next; free(s);}
}
}
if(!pa&&!pb)
tail->next=NULL;
else if ( pa != NULL ) /*将多项式A中剩余项连入和多项式中*/
tail->next = pa;
else /*将多项式B中剩余项连入和多项式中*/
tail->next = pb;
}
void PrintPoly(PolyList *head)
{
PolyList *p; int m=0;
p=head->next;
while(p != NULL)
{ printf("\t%5d%5d", p->coef,p->exp);
p = p->next;
m++;
if(m%4==0)printf("\n\t");
}
printf("\n\n\t多mm=%d\n",m);
}
main()
{
PolyList *PLA,*PLB;
int option;
do
{
printf("=======欢迎进入一元多项式的操作界面========\n");
printf("=======1.输入多项式A 2.输入多项式B 3.输出多项式A和B=======\n");
printf("=======4.多项式A与B相加 5.输出和多项式 0.退出=========\n");
printf("请输入需要操作的序号\n");
scanf("%d",&option);
switch(option)
{
case 1: PLA=CreatePoly();break;
case 2: PLB=CreatePoly();break;
case 3: printf("多项式A:\n");
PrintPoly(PLA);
printf("多项式B:\n");
PrintPoly(PLB);break;
case 4: PolyAdd(PLA,PLB);break;
case 5: printf("和多项式：\n");
PrintPoly(PLA);break;
case 0: printf("谢谢本次操作！\n");break;
default: printf("输入非法操作，请再次输入需要操作的序号\n");
}
}while(option!=0);
}
运行结果： 2、源程序：
#include
#include
#define MAXSIZE 1024
typedef int elemtype;
typedef struct SequenStack
{
elemtype data[MAXSIZE];
int top;
}SequenStack;
SequenStack * Init_SequenStack()
{
SequenStack * S;
S = (SequenStack *)malloc(sizeof(SequenStack));
if (S == NULL)
return S;
S->top = -1;
return S;
}
int SequenStack_Empty(SequenStack * S)//判栈空
{
if (S->top == -1)
{
return 1;
} else
{
return 0;
}
}
int Push_SequenStack(SequenStack * S, elemtype x)//入栈
{
if (S->top >= MAXSIZE - 1)
{
return 0;
}
S->top++;
S->data[S->top] = x;
return 1;
}
int Pop_SequenStack(SequenStack * S, elemtype * x)//出栈
{
if (S->top == -1)
{
return 0;
}
else
{
S->top--;
*x = S->data[S->top + 1];
return 1;
}
}
void Conversion(int N)//进制转化
{
int x;
SequenStack * S = Init_SequenStack();
while (N > 0)
{
Push_SequenStack(S, N % 2);
N = N / 2;
}
while (!SequenStack_Empty(S))
{
Pop_SequenStack(S, &x);
printf("%d", x);
}
}
void main()
