数据结构与算法实验报告(线性表).doc

一、实验目的1、深刻理解线性结构的特点以及线性表的概念。2、熟练掌握线性表的顺序存储结构、链式存储结构及基本运算算法的实现，特别是查找、插入和删除等算法。二、实验环境1) 硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP。2) 软件：visual c+6.0。三、实验题目和实验内容实验题目：线性表的顺序、链式表示及其应用实验内容：1、基本题：实验2.1、实验2.2、实验2. 4、实验2.72、附加题：实验2.3、实验2.6(没做)四、实验数据和实验结果2.1a,b,c,d,e2.2 a,b,c,d,e2.4a,b,c,d,e2.7第一个多项式:2x+6x2-4x3+3x4 第二个多项式1x-3x2+6x3-3x4五、附录（程序代码）2.1#include#include#define MaxSize 50typedef structchar dataMaxSize;int length;SqList;void CreateList(SqList *&L,char a,int n)int i;L=(SqList *)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;void InitList(SqList *&L)L=(SqList *)malloc(sizeof(SqList);L-length=0;void DestroyList(SqList *&L)free(L);int ListEmpty(SqList *L)return (L-length=0);int ListLength(SqList *L)return (L-length);void DispList(SqList *L)int i;for(i=0;ilength;i+)coutdatai;coutendl;char GetElem(SqList *L,int i,char &e)if(iL-length)return 0;e=L-datai-1;return e;int LocateElem(SqList *L,char e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;elsereturn i+1;int ListInsert(SqList*&L,int i,char e)int j;if(iL-length+1)return 0;i-;for(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=e;L-length+;return 1;int ListDelete(SqList *&L,int i,char &e)int j;if(iL-length)return 0;i-;e=L-datai;for(j=i;jlength-1;j+)L-length-;return 1;void main ()SqList *p;char b10,e;int k;coutk;cout输入元素:;for(int m=0;mbm; InitList(p);CreateList(p,b,k);cout输出顺序表:;DispList(p);cout顺序表长度是:ListLength(p)endl;if(ListEmpty(p)cout顺序表为空endl;elsecout顺序表不为空endl;cout顺序表第3位元素是:GetElem(p,3,e)endl;cout元素a的位置是:第LocateElem(p,a)位endl;ListInsert(p,4,f);cout在第4个元素上插入元素f:;DispList(p);cout删除顺序表第3个元素:;ListDelete(p,3,e);DispList(p);DestroyList(p);2.2#include#includetypedef struct LNodechar data;struct LNode *next;LinkList;void CreateListR(LinkList *&L,char a,int n)LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList);r=L;for(i=0;idata=ai;r-next=s;r=s;r-next=NULL;void InitList(LinkList *&L)L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;void DestroyList(LinkList *&L)LinkList *pre=L,*p=pre-next;while(p)free(pre);pre=p;p=pre-next;free(pre);int ListEmpty(LinkList *L)return(L-next=NULL);int ListLength(LinkList *L)int n=0;LinkList *p=L;while(p-next)n+;p=p-next;return(n);void DispList(LinkList *L)LinkList *p=L-next;while(p)coutdata;p=p-next;coutendl;char GetElem(LinkList *L,int i,char &e)int j=0;LinkList *p=L;while(jnext;if(!p)return 0;elsee=p-data;return e;int LocateElem(LinkList *L,char e)int i=1;LinkList *p=L-next;while(p&p-data!=e)p=p-next;i+;if(!p)return(0);elsereturn(i);int ListInsert(LinkList *&L,int i,char e)int j=0;LinkList *p=L,*s;while(jnext;if(!p)return 0;elses=(LinkList *)malloc(sizeof(LinkList);s-data=e;s-next=p-next;p-next=s;return 1;int ListDelete(LinkList *&L,int i,char &e)int j=0;LinkList *p=L,*q;while(jnext;if(!p)return 0;elseq=p-next;if(!q)return 0;e=q-data;p-next=q-next;free(q);return 1;void main()LinkList *h;char b10,e;int k;coutk;cout输入元素:;for(int m=0;mbm;InitList(h);CreateListR(h,b,k);cout输出单链表:;DispList(h);cout单链表长度是:ListLength(h)endl;if(ListEmpty(h)cout单链表为空endl;elsecout单链表不为空endl;cout单链表第3位元素是:GetElem(h,3,e)endl;cout元素a的位置是:第LocateElem(h,a)位endl;ListInsert(h,4,f);cout在第4个元素上插入元素f:;DispList(h);cout删除单链表第3个元素:;ListDelete(h,3,e);DispList(h);DestroyList(h);2.4#include#includetypedef struct LNodechar data;struct LNode *next;LinkList;void CreateListR(LinkList *&L,char a,int n)LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList);r=L;for(i=0;idata=ai;r-next=s;r=s;r-next=L;void InitList(LinkList *&L)L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;void DestroyList(LinkList *&L)LinkList *pre=L-next,*p=pre-next;L-next=NULL;while(p)free(pre);pre=p;p=pre-next;free(pre);int ListEmpty(LinkList *L)return(L-next=NULL);int ListLength(LinkList *L)int n=0;LinkList *p=L;while(p-next!=L&p-next)n+;p=p-next;return(n);void DispList(LinkList *L)LinkList *p=L-next;while(p!=L&p)coutdata;p=p-next;coutnext;while(jnext;if(!p)return 0;elsee=p-data;return e;int LocateElem(LinkList *L,char e)int i=1;LinkList *p=L-next;while(p!=L&p-data!=e&p)p=p-next;i+;if(!p)return(0);elsereturn(i);int ListInsert(LinkList *&L,int i,char e)int j=1;LinkList *p=L-next,*s;while(jnext;if(!p)return 0;elses=(LinkList *)malloc(sizeof(LinkList);s-data=e;s-next=p-next;p-next=s;return 1;int ListDelete(LinkList *&L,int i,char &e)int j=1;LinkList *p=L-next,*q;while(jnext;if(!p)return 0;elseq=p-next;if(!q|q=L-next)return 0;e=q-data;p-next=q-next;free(q);return 1;void main()LinkList *h;char b10,e;int k;coutk;cout输入元素:;for(int m=0;mbm;InitList(h);CreateListR(h,b,k);cout输出循环单链表:;DispList(h);cout循环单链表长度是:ListLength(h)endl;if(ListEmpty(h)cout循环单链表为空endl;elsecout循环单链表不为空endl;cout循环单链表第3位元素是:GetElem(h,3,e)endl;cout元素a的位置是:第LocateElem(h,a)位endl;ListInsert(h,4,f);cout在第4个元素上插入元素f:;DispList(h);cout删除循环单链表第3个元素:;ListDelete(h,3,e);DispList(h);DestroyList(h); 2.7#include#includetypedef struct polynomialint coef; /系数int index; /指数struct polynomial *next;LinkList;void CreateList(LinkList *&L, int n) LinkList *s,*r; int i; L=(LinkList *)malloc(sizeof(LinkList); r=L; for(i=0;in;i+) s=(LinkList*)malloc(sizeof(LinkList); couts-coefs-index; s-next = NULL; r-next=s;r=s; void InitList(LinkList *&L)L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;void AddList(LinkList *&list1,LinkList *&list2,int m,int n)LinkList *s,*r,*t;int i;s=list1-next;r=list2-next;t=list1;for(i=0;inext;t=list1;while(s!=NULL)if(s-index!=r-index)s=s-next;t=t-next;else break;if(!s)s=(LinkList*)malloc(sizeof(LinkList);s-coef=r-coef;s-index=r-index;s-next=NULL;t-next=s;s=s-next;r=r-next;continue;elseif(s-index=r-index)s-coef=s-coef+r-coef;if(s-coef=0)LinkList *temp1;temp1=s;s=s-next;t-next=s;delete temp1;r=r-next;s=NULL;coutnext;while(list1)coutcoefxindex;if(list1-next!=NULL)coutnext;void DispList(LinkList *L)L=L-next;while(L)cout