数据结构实验报告全集 实验一 线性表基本操作和简单程序 1． 实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2． 实验要求 （1） 认真阅读和掌握和本实验相关的教材内容。 （2） 认真阅读和掌握本章相关内容的程序。 （3） 上机运行程序。 （4） 保存和打印出程序的运行结果，并结合程序进行分析。 （5） 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果

实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表 nodetype *create()//建立单链表，由用户输入各结点data域之值， //以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< while(1) { cout <<" 输入第"<< i <<"结点data域值："; cin >> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点 } i++; } return h; } 3）输出单链表中的元素 void disp(nodetype*h)//输出由h指向的单链表的所有data域之值 { nodetype *p=h; cout<<"输出一个单链表:"< if(p==NULL)cout<<"空表"; while(p!=NULL) { coutnext; } cout<} 4）计算单链表的长度 int len(nodetype *h)//返回单链表的长度 { int i=0; nodetype *p=h; while(p!=NULL) { p=p->next;i++; } return i; } 5）寻找第i个节点 nodetype *find(nodetype *h,int i)//返回第i个节点的指针 { nodetype *p=h; int j=1; if(i>len(h)||i<=0) return NULL;//i上溢或下溢c else { while (p!=NULL&&j<1)//查找第i个节点，并由p指向该节点 { j++;p=p->next; } return p; } } 6）单链表的插入操作 nodetype *ins(nodetype *h,int i,elemtype x)//在单链表head中第i个节点 //（i>=0）之后插入一个data域为x的节点 { nodetype *p,*s; s=(nodetype*)malloc(sizeof(nodetype));//创建节点s s->data=x;s->next=NULL; if(i==0)//i=0:s作为该单链表的第一个节点 { s->next=h;h=s; } else {p=find(h,i);//查找第i个节点，并由p指向该节点 if(p!=NULL) { s->next=p->next; p->next=s; } return h; } } 7）单链表的删除操作 nodetype *del(nodetype *h,int i)//删除第i个节点 { nodetype *p=h, *s; int j=1; if(i==1)//删除第1个节点 { h=h->next;free(p); } else { p=find(h,i-1);//查找第i-1个节点，并由p指向该节点 if(p!=NULL&&p->next!=NULL) { s=p->next;//s指向要删除的节点 p->next=s->next; free(s); } else cout<<"输入i的值不正确"< } return h; } 8）释放节点空间 void dispose(nodetype *h)//释放单链表的所有节点占用的空间 { nodetype *pa=h,*pb; if(pa!=NULL) { pb=pa->next; if(pb==NULL)//只有一个节点的情况 free(pa); else { while (pb!=NULL)//有两个及以上节点的情况 { free(pa);pa=pb;pb=pb->next; } free(pa); } } } 9)主程序模块: #include"slink.h"//包含头文件slink void main() { nodetype *head;//定义节点指针变量 head=create();//创建一个单链表 disp(head);//输出单链表 cout<<"单链表长度:"< ins(head, 2,0);//在第二个节点之后插入以0为元素的节点 disp(head);//输出新链表 del(head,2);//删除第二个节点 disp(head);//输出新链表

} 5．实验结果

建立一个单链表： 输入第1结点data域值：1 输入第2结点data域值：2 输入第3结点data域值：3 输入第4结点data域值：4 输入第5结点data域值：5 输入第6结点data域值：6 输入第7结点data域值：7 输入第8结点data域值：8 输入第9结点data域值：9 输入第10结点data域值0： 输出一个单链表： 1 2 3 4 5 6 7 8 9 单链表长度：9 输出一个单链表： 1 0 2 3 4 5 6 7 8 9 输出一个单链表： 1 2 3 4 5 6 7 8 实验二 顺序栈的实现

1.实验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1） 认真阅读和掌握和本实验相关的教材内容。 （2） 分析问题的要求，编写和调试完成程序。 （3） 保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下： （1） 定义栈的顺序存取结构。 （2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3） 定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4） 设计一个测试主函数进行测试。 （5） 对程序的运行结果进行分析。 实验代码： #include #define MaxSize 100

typedef struct { int data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空 { return (st->top==-1); } void Push(SqStack *st,int x) //元素进栈 { if(st->top==MaxSize-1) printf("栈上溢出!\n"); else { st->top++; st->data[st->top]=x; } } void Pop(SqStack *st) //退栈 { if(st->top==-1) printf("栈下溢出\n"); else st->top--; } int Gettop(SqStack *st) //获得栈顶元素 { if(st->top==-1) { printf("栈空\n"); return 0; } else return st->data[st->top]; }