链式存储结构的基础操纵[新版].doc

广州大学学生实验报告 开课学院及实验室：计算机科学与工程实验室 2011年 月 日 学院 计算机科学与教育软件学院 年级、专业、班 计机094 姓名 潘永航 学号 0923010089 实验课程名称 数据结构 成绩 实验项目名称 实验一 链式存储结构的基本操作 指导老师 一、实验目的 掌握单链表，链式堆栈，链式队列的定义及基本操作 二、使用仪器、器材 微机一台 操作系统：WinXP 编程软件：C++ 三、实验内容及原理 （一）单链表的定义及基本操作 （1）用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。 （2）在上述带表头的链表中删除第i个结点或删除数值为item的结点。 （3）链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。 （4）设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。 （二）链式堆栈的定义及基本操作 （5）先定义堆栈的几个基本操作，再设计一主函数利用堆栈的操作完成以下功能：假设一个算术表达式中可以包含三种括号：()[]{}，且这三种括号可以按任意次序嵌套使用（如：...[...{...}...[...]...]...(...)）。编写判别给定表达式中所含括号是否正确配对出现的算法，已知表达式已存入数据元素为字符的单链表中。 （三）链式队列的定义及基本操作 （6）先定义队列的几个基本操作，再设计一主函数利用队列的操作完成以下功能：键盘输入的字符可以临时存入键盘的缓冲区中。为了充分利用缓冲区的空间，往往将缓冲区设计成链式循环队列的结构，并为循环队列结构的缓冲区设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中，就将尾指针后移，链入缓冲区的循环队列之中；每输出一个字符号，就将队头指针前移，将它从缓冲队列中删除。假设有两个进程同时存在于一个应用程序中，第一个进程连续在屏幕上显示字符“X”，第二个进程不断检查键盘上是否有输入，若有则读入用户键入的字符，将其保存到键盘缓冲区中。 四、实验过程原始数据记录 1、线性表的链表实现：插入、删除、翻转 #includeiostream #includemalloc.h using namespace std; typedef struct node { int data; struct node *link; }LNode,*LinkList; LinkList insert(LinkList list) //新建一个链表或插入新元素 { int item,n; LinkList p,q,r; //list第一个结点指针 couthow many data do you want to insert:n=; cin n; for(int i=0;in;i++) { coutdata[i]=; cinitem; //输入储存的数据 p=(LinkList)malloc(sizeof(LNode)); //申请一个新的结点 p-data=item; //将数据放入结点的数据域 p-link=NULL; //链尾结点指针域置空 if(list==NULL) { list=p; } else { if(itemlist-data) //若a小于第一个链接点 { p-link=list; //将新的链接点插在链表最前面 list=p; //list指向被插入的新结点 } else { q=list; while(q!=NULL item=q-data) //寻找插入位置 { r=q; //r指针总是指向当前链接点的直接前驱结点 q=q-link; } p-link=q; r-link=p; //将新的链结点插在q指示的链结点后面 } } } return (list); } LinkList deleteline(LinkList list,