实验报告--线性表.doc

姓名 王倩 学号 1104180204 班级 计科1102 年级 1102级 指导教师 李翠 西安财经学院信息学院 算法与数据结构 实验报告实验名称 线性表 实验室 实验日期 顺序表的基本运算一、 实验目的1. 掌握线性表的顺序存储结构（顺序表）的含义与实现方法；2. 熟练掌握线性表在顺序存储结构上的插入、删除、查找等操作。二、 实验相关理论及内容1. 实验相关理论 线性表是最简单、最基本也是最常用的一种线性结构。线性表有两种存储方法：顺序存储和链式存储。线性表的基本操作是插入、删除和检索等。了解有关顺序表的概念和性质；掌握线性表的基本操作的原理以及实现其的算法。2. 实验内容编写实现顺序表的基本算法（初始化、查找、插入、删除等）的函数，并在此基础上设计一个主程序完成如下功能：初始化顺序表L；建立顺序表L，如（a,b,c,d,c）；输出顺序表L的长度；输出顺序表L的第i个元素，如第3个元素；输出给定元素的位置，如输出元素a的位置；在第i个元素前插入给定元素，如在第4个元素前插入元素f；删除顺序表L的第i个元素，如删除顺序表L的第3个元素。注：最好编写输出顺序表L的函数供主程序调用，以检验操作是否成功。三、 实验环境 Windows XP 2007 ， Visual C+ 6.0四、 实验步骤(必须包括代码描述).插入元素在顺序表的某个位置，首先是要查看该位置是否合理，假如顺序表中有n个元素，要插入元素在第i个位置，那么插入的位置i应当在第1与第n+1个元素位置之间，然后利用插入算法，将第n个元素一直到原第i个元素依次后移，腾出一个空位，将新数据插入在该位置，最后将顺序表的表长加1；.删除顺序表中的元素，首先仍然要判断要删除元素是否在顺序表的合理位置，若是合理位置，则将包括该元素在内的后面所有元素依次向前前移，直接用后继覆盖直接前驱，最后将顺序表的表长减1；.查找某个元素是否在顺序表中，则可以利用顺序查找的方法，从第一个元素开始依次将元素关键字的值与给定元素关键字的值进行比较，若相等则返回该元素在顺序表中的位置，若不相等则返回值为空。实现代码顺序表的初始化(构造一个空表）SeqList *init_SeqList()SeqList *L;L=(SeqList*)malloc(sizeof(SeqList);L-last=-1;return L; 设调用函数为主函数。主函数对初始化函数的调用如下：main( ) SeqList *L; L=init_SeqList(); （2） 插入运算int Insert_SeqList(SeqList *L,int i,datatype x) int j;if(L-last=MAXSIZE-1) printf(table is full!); return(-1); if(i(L-last+2) printf(place is wrong!); return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj;L-datai-1=x;L-last+;return(1); 删除运算int Delete_SeqList(SeqList *L,int i) int j;if(i(L-last+1) printf(this element dont exist!);return(0);for(j=i;jlast;j+) L-dataj-1=L-dataj;L-last-;return(1); 然后依次输出计算结果。五、 实验数据记录及分析(可包括错误提示,原因,如何解决等)六、 实验总结上机实验创建了一个顺序表，并且熟练的掌握了线性存储结构的完成了在顺序表上的插入元素，删除元素，按值查找 。通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；可随机存取顺序表的元素； 顺序表的插入、删除操作要通过移动元素实现。七、代码清单#includetypedef structchar s10;int last;Seqlist;void initlist(Seqlist *l) /初始化线性表l-last=(-1);void creat(Seqlist *l) /创建线性表char ch;ch=getchar();while(ch!=#)l-last=l-last+1; l-sl-last=ch; ch=getchar();void locatdisply(Seqlist *l,int n) /输出指定位置的元素int log=0; while(log!=n&loglast)log+;printf(%cn,l-slog);void dislylocat(Seqlist *l,char m) /输出指定元素的位置 int log=0;while(l-slog!=m&loglog+1)log+;printf(%dn,log+1);void disly(Seqlist *l) /输出整个线性表int i;for( i=0;ilast;i+)printf(%c ,l-si);void intset(Seqlist *l,int n) /在指定位置插入元素 int k=l-last;for(;k=n;k-)l-sk+1=l-sk;l-sn=f;l-last=l-last+1;void del(Seqlist *l,int n) /删除指定位置的元素 int log=n-1;for(;loglast;log+)l-slog=l-slog+1;l-last=l-last-1;void main() Seqlist a; printf(初始化完成n);initlist(&a);printf(请输入线性表的元素：n);creat(&a);printf(线性表输出为：n);disly(&a);printf(n);printf(线性表的长度为:);printf(%dn,a.last+1);printf(第3个元素是：); locatdisply(&a,2);printf(元素a的位置为：);dislylocat(&a,a);printf(在第4个元素前插入元素f,插入后：n);intset(&a,4);disly(&a);printf(n);printf(删除第3个元素后为：);del(&a,3);disly(&a);单链表的基本运算一、 实验目的1. 掌握线性表的链式存储结构（单链表）的含义与实现方法；2. 熟练掌握单链表上的建立、插入、删除和查找等算法。二、 实验相关理论及内容1. 实验相关理论 .线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。这组存储单元可以是连续的，也可以是不连续的。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。 .单链表的建立是将每一个结点单向地串连起来。单链表分不带头结点和带头结点两种。每种单链表都可通过头插和尾插建立。2. 实验内容编写实现单链表的基本算法（初始化、查找、插入、删除等）的函数，并在此基础上设计一个主程序完成如下功能：初始化单链表H;采用尾插法建立单链表H，如（a,b,c,d,c）；输出单链表H的长度；输出单链表H的第i个元素，如输出单链表H的第3个元素；输出给定元素的位置，如输出元素a的位置；在第i个元素前插入给定元素，如在第4个元素前插入元素f；删除单链表H的第i个元素，如删除单链表H的第3个元素。注：最好编写输出单链表H的函数供主程序调用，以检验操作是否成功。三、 实验环境Microsoft visual c+ 6.0四、 实验步骤(必须包括代码描述)先初始化单链表H并建立头结点，使用尾插法建立单链表H，并输出链表。然后使用以下算法输出单链表的长度：void ListLength(LinkList l)/int a=0;while(l-next!=NULL)a+;l=l-next;printf(单链表的长度为:%dn,a);然后输出单链表的第i个元素，如输出单链表的第3个元素：void GetDate(LinkList l,int i);LinkList p;p=l;printf(请输入元素的位置？:);scanf(%d,&i);for(int k=1;knext;printf(输出第%d个元素为:%cn,i,p-data);输出给定元素的位置，如输出元素a的位置：void LocateList(LinkList l,int ch)；int i=0;LinkList p;p=l;ch=a;while(p!=NULL)p=p-next;i+;if(p-data=ch)break;printf(输出元素a的位置为:%dn,i);在第i个元素前插入给定元素，如在第4个元素前插入元素f的算法如下：void InsList(LinkList l,int i,char ch)；Node *h,*t;t=l;int k=0;printf(请输出插入元素的位置为:);scanf(%d,&i);ch=f;printf(插入元素为:f);while(t!=NULL&knext;k=k+1;h=(Node *)malloc(sizeof(Node);h-data=ch;h-next=t-next;t-next=h;printf(n);然后删除单链表的第i个元素，如删除单链表的第3个元素：void DelList(LinkList l,int i,char *c);Node *h=NULL,*t=NULL;int k=0;t=l;printf(请输出删除元素的位置为:);scanf(%d,&i);while(t!=NULL&knext;k=k+1;最后释放结点，并将结果输出。五、 实验数据记录及分析(可包括错误提示,原因,如何解决等)六、 实验总结经过该实验单链表是线性表的一种链式存储结构。通过对线性表的链式存储结构进行了解与学习，了解了其与顺序表不同之处，1. 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2. 插入删除操作通过修改结点的指针实现；3. 不能随机存取元素；七、代码清单#include#include#define NULL 0typedef struct Node/结点类型定义char data;struct Node *next;Node,*LinkList; int InitList(LinkList *l)/初始化单链表H*l=(LinkList)malloc(sizeof(Node);/建立头结点(*l)-next=NULL;return 0;void CreatFromTail(LinkList l)/尾插法建立单链表Node *s,*r;r=l;char ch;int flat=1;printf(请输入链表的各个元素:);while(flat)ch=getchar();if(ch!=#)s=(Node *)malloc(sizeof(Node);/申请新结点s-data=ch;r-next=s;r=s;elseflat=0;r-next=NULL;void PutList(LinkList l) /输出链表 LinkList p;p=l;printf(创建成功的单链表为:);if(l!=NULL)dop=p-next;printf(%c,p-data);while(p-next!=NULL);printf(n);void ListLength(LinkList l)/输出单链表的长度int a=0;while(l-next!=NULL)a+;l=l-next;printf(单链表的长度为:%dn,a);void GetDate(LinkList l,int i)/输出单链表的第i个元素，如输出单链表的第3个元素；LinkList p;p=l;printf(请输入元素的位置？:);scanf(%d,&i);for(int k=1;knext;printf(输出第%d个元素为:%cn,i,p-data);void LocateList(LinkList l,int ch)/输出给定元素的位置，如输出元素a的位置；int i=0;LinkList p;p=l;ch=a;while(p!=NULL)p=p-next;i+;if(p-data=ch)break;printf(输出元素a的位置为:%dn,i);void InsList(LinkList l,int i,char ch)/在第i个元素前插入给定元素，如在第4个元素前插入元素f；Node *h,*t;t=l;int k=0;printf(请输出插入元素的位置为:);scanf(%d,&i);ch=f;printf(插入元素为:f);while(t!=NULL&knext;k=k+1;h=(Node *)malloc(sizeof(Node);h-data=ch;h-next=t-next; /插入操作t-next=h;printf(n);void DelList(LinkList l,int i,char *c)/删除单链表的第i个元素，如删除单链表的第3个元素Node *h=NULL,*t=NULL;int k=0;t=l;printf(请输出删除元素的位置为:);scanf