线性表的建立与应用 实验报告

线性表的建立与应用 实验报告

实 验 报 告

课程名称 数据结构实验 实验名称 线性表的建立与应用 实验类型 设计型 实验地点 实验日期 指导教师 杨 崇

专 业 班 级 学 号 姓 名 成 绩

线性表的建立与应用 实验报告

辽宁石油化工大学计算机与通信工程学院

实验一

一 实验目的：通过实验，了解并掌握线性表逻辑特性和物理特性，了解并掌握队列和栈的运算方法，培养结合理论知识进行实际应用的实践能力。

二 实验内容：栈和队列的初始化及基本运算的实现，实现栈和队列的初始化、栈的入栈、退栈操作、队列的入队、退队运算，以及将退栈结果入队、退队结果入栈等基本操作。 三 实验原理：栈是限制在线性表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。

入栈

出栈

栈的运算包括初始化、入栈、退栈、读取栈顶元素等。当栈为空的时候不允许退栈，当栈为满的时候不允许入栈。标识栈的特性的是四个变量：栈的首地址V，栈的容量m，栈顶指针Top。

栈的初始化：

void init-stack(s,m.top) ET s; int m,*top; {s=malloc(m*sizeof(ET));

线性表的建立与应用 实验报告

*top=0; return; } 入栈运算

void push(s,m,top,x) ET s[],x; int m,*top;

{ if {*top= =m} {printf(“stack overflow\n”);return;} *top=*top+1; s[*top-1]=x; return; } 退栈运算

void pop(s,m.top,y) ET s[],*y;int m,*top;

{ if (*top= =0) { printf(“stack underflow\n”);return; y=s[*top-1]; *top=*top-1; return; }

读取栈顶元素 void top(s,m,top,y) ET s[],*y;int m,*top;

{ if (*top = =0) {printf(“stack empty\n”);return;} y=s[*top-1]; return;}

插入在线性表的一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。当队列中没有数据时，我们称这个时候的队列为空队

队列示意图

入队

a1

a2

a3

a4

a5

出队

队列也是一种运算受限制的线性表，它的运算包括：初始化队、入队、退队、读取队首和队尾的数据。当队列为空时不允许退队，当队列未满的时候不允许入队。

线性表的建立与应用 实验报告

在实际应用中，通常使用循环队列

MZXSIZE-1

循环队列示意图

初始化循环队列

void init_queue(q,m,front,rear,s) ET q;int m,*front,*rear,*s; { q=malloc(m*sizeof(ET)); *front=m;*rear=m;*s=0; return;} 循环队列入队运算

vsid addcq(q,m,rear,front,s,x) ET q[];int m,*front,*rear,*s;

{ if ((*s==1) && (*rear= =*front)){printf(“queue overflow\n”);return;} *rear=*rear+1;

if (*rear= =m+1) *rear=1; q[*rear-1]=x;*s=1;return;} 循环队列退队运算

void delcq(q,m,rear,front,s,y) ET q[],*y;int m,*front,*rear,*s;

{ if (*s= =0) {printf(“queue underflow \n”);return;} *front=*front+1;

if (*front= =m+1) *front=1;

线性表的建立与应用 实验报告

*y=q[front-1];

if(*front= =*rear) *s=0; return;}

四、实验步骤:

1 进入Turbo C 2.0，新建一个文件。 2 输入程序，程序要求使用子函数进行组织。 3 将源程序保存到指定文件夹“D:\学生姓名”。 4 按F9调试，纠正语法错误。 5按Ctrl＋F9运行，调试逻辑错误。 6 按Alt＋F5查看结果。

五、实验截图：

六、程序源代码： #include"math.h" #include"stdlib.h" #define nd struct node struct node { int d;

struct node *next; };

nd *create(head) nd *head; {

线性表的建立与应用 实验报告

int d; nd *p; nd *q; d=1;

head=(nd *)malloc(sizeof(nd)); head->next=NULL; p=head; while (d>0) {

printf("\n Please input the number:"); scanf("%d",&d); if (d>0) {

q=(nd *)malloc(sizeof(nd)); q->d=d;

q->next=NULL; p->next=q; p=p->next; } }

return(head); };

prt(head) nd *head; {

nd *p;

if (head!=NULL) {

p=head->next;

printf("The element in the list are: "); while (p!=NULL) {

printf("%d ",p->d); p=p->next; }

printf("\n"); } }

nd *look(head,x) nd *head; int x; {

nd *p; p=head;

while((p->next!=NULL)&&(((p->next)->d)!=x)) p=p->next;

线性表的建立与应用 实验报告

}

ins(head,x,y)

nd *head; int x;int y; {

nd *p,*q;

p=look(head,x);

q=(nd *)malloc(sizeof(nd)); q->d=y;

q->next=p->next; p->next=q; }

del(head,x) nd *head;int x; {

nd *p; nd *q;

p=head->next; q=head;

while ((p->d!=x)&&(p->next!=NULL)) {

p=p->next; q=q->next; }

if(p->d==x) {

q->next=p->next; free(p); } else

printf("No thie element in the list\n"); }

nd *un(l1,l2) nd *l1,*l2; { nd *p,*q; if (l2!=NULL) { p=l1;

while (p->next!=NULL) p=p->next; p->next=l2->next; }

free(l2); return(l1); }

线性表的建立与应用 实验报告

nd *head; {

nd *p,*q,*h; p=head->next; q=p->next; h=q;

p->next=NULL; while (q!=NULL) {

head->next=q; h=h->next; q->next=p; p=q; q=h; }

return(head); }

nd *copy(head) nd *head; {

nd *p,*q,*h,*t;

p=(nd *)malloc(sizeof(nd)); p->next=NULL; q=head->next; h=p; …… 此处隐藏：3718字，全部文档内容请下载后查看。喜欢就下载吧 ……