《链式存储结构的基本操作》由会员分享，可在线阅读，更多相关《链式存储结构的基本操作（6页珍藏版）》请在金锄头文库上搜索。
1、XX大学学生实验报告开课学院及实验室：计算机科学与工程实验室 20XX年 月 日学院计算机科学与教育软件学院年级、专业、班计机姓名学号实验课程名称数据结构成绩实验项目名称实验一 链式存储结构的基本操作指导老师一、实验目的掌握单链表，链式堆栈，链式队列的定义及基本操作二、使用仪器、器材微机一台操作系统：WinXP编程软件：C+三、实验内容及原理（一）单链表的定义及基本操作（1）用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。（2）在上述带表头的链表中删除第i个结点或删除数值为it
2、em的结点。（3）链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。（4）设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。（二）链式堆栈的定义及基本操作（5）先定义堆栈的几个基本操作，再设计一主函数利用堆栈的操作完成以下功能：假设一个算术表达式中可以包含三种括号：()，且这三种括号可以按任意次序嵌套使用（如：.(.)）。编写判别给定表达式中所含括
3、号是否正确配对出现的算法，已知表达式已存入数据元素为字符的单链表中。（三）链式队列的定义及基本操作（6）先定义队列的几个基本操作，再设计一主函数利用队列的操作完成以下功能：键盘输入的字符可以临时存入键盘的缓冲区中。为了充分利用缓冲区的空间，往往将缓冲区设计成链式循环队列的结构，并为循环队列结构的缓冲区设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中，就将尾指针后移，链入缓冲区的循环队列之中；每输出一个字符号，就将队头指针前移，将它从缓冲队列中删除。假设有两个进程同时存在于一个应用程序中，第一个进程连续在屏幕上显示字符“X”，第二个进程不断检查键盘上是否有输入，若有则读入用户键入的字符，
4、将其保存到键盘缓冲区中。四、实验过程原始数据记录1、线性表的链表实现：插入、删除、翻转#include#includeusing namespace std;typedef struct nodeint data;struct node *link;LNode,*LinkList;LinkList insert(LinkList &list) /新建一个链表或插入新元素int item,n;LinkList p,q,r; /list第一个结点指针cout n;for(int i=0;in;i+)coutdataiitem; /输入储存的数据p=(LinkList)malloc(sizeof(L
5、Node); /申请一个新的结点p-data=item; /将数据放入结点的数据域p-link=NULL; /链尾结点指针域置空if(list=NULL)list=p;else if(itemdata) /若a小于第一个链接点p-link=list; /将新的链接点插在链表最前面list=p; /list指向被插入的新结点elseq=list;while(q!=NULL & item=q-data) /寻找插入位置r=q; /r指针总是指向当前链接点的直接前驱结点q=q-link;p-link=q;r-link=p; /将新的链结点插在q指示的链结点后面 return (list);LinkL
6、ist deleteline(LinkList &list,int a) /删除链表中数据域值为item的所有连接点LinkList p,q=list;p=list-link;while(p!=NULL) if(p-data=a)q-link=p-link;free(p);p=q-link;elseq=p;p=p-link;if(list-data=a)q=list;list=list-link;free(q);return(list);LinkList overturnline(LinkList &list) /链表翻转LinkList p,q=NULL,r;p=list;while(p!=
7、NULL)r=q;q=p;p=p-link;q-link=r;list=q;return (list);LinkList combine(LinkList &listA,LinkList &listB) /将两个按值有序链接的非空线性链表合并为一个LinkList listC,p=listA,q=listB,r;if(listA-datadata)listC=listA;r=listA;p=listA-link;elselistC=listB;r=listB;q=listB-link;while(p!=NULL & q!=NULL)if(p-datadata)r-link=p;r=p;p=p-
8、link;elser-link=q;r=q;q=q-link;r-link=p?p:q;return (listC);int line(LinkList &q) /将数据域值链表排列展示int n=0;cout数据域值从小到大排列的有序链表:;while(q!=NULL)n+;coutdatalink;coutn头结点后面的结点数n=n;return (n);void main()int choice;LinkList head=NULL,list=NULL;head=(LinkList)malloc(sizeof(LNode);coutinput LinkListA.link=insert(
9、list);head-data=line(head-link);while(1)coutchoice;switch(choice)case 1:cout插入新元素.datalink-data|list-data=list-link-data)cout链表为升序,不用翻转.link=insert(list); head-data=line(head-link);elsehead-link=overturnline(list);cout链表已由降序翻转为升序.link=insert(list); head-data=line(head-link); break;case 2:int item;co
10、utitem;list=head-link=deleteline(list,item);head-data=line(head-link); break;case 3:list=head-link=overturnline(list);head-data=line(head-link); break;case 4:LinkList listB=NULL;coutinput LinkListB.datalink-data|list-data=list-link-data)coutlink=combine(list,listB);elsecout链表为降序，需翻转为升序.link=overturnline(list);coutlink=combine(list,listB);head-data=line(head-link); break;case 0:exit(0);break;default:coutwrong choice!please choose again.;2、链式堆栈的实现#include#include#define N 100using namespace std;typedef s
