一、实验目的
1、深刻理解线性结构的特点以及线性表的概念。
2、熟练掌握线性表的顺序存储结构、链式存储结构及基本运算算法的实现，特别是查找、插入和删除等算法。
二、实验环境
1) 硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP。
2) 软件：visual c++6.0。
三、实验题目和实验内容
实验题目：线性表的顺序、链式表示及其应用
实验内容：
1、基本题：实验2.1、实验2.2、实验2. 4、实验2.7
2、附加题：实验2.3、实验2.6(没做)
四、实验数据和实验结果
2.1
a,b,c,d,e
2.2
a,b,c,d,e
2.4
a,b,c,d,e
2.7
第一个多项式:2x+6x^2-4x^3+3x^4 第二个多项式1x-3x^2+6x^3-3x^4
五、附录（程序代码）
2.1
#include<iostream.h>
#include<malloc.h>
#define MaxSize 50
typedef struct
{
char data[MaxSize];
int length;
}SqList;
void CreateList(SqList *&L,char a[],int n)
{
int i;
L=(SqList *)malloc(sizeof(SqList));
for(i=0;i<n;i++)
L->data[i]=a[i];
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;i<L->length;i++)
cout<<L->data[i];
cout<<endl;
}
char GetElem(SqList *L,int i,char &e)
{
if(i<1||i>L->length)
return 0;
e=L->data[i-1];
return e;
}
int LocateElem(SqList *L,char e)
{
int i=0;
while(i<L->length&&L->data[i]!=e)
i++;
if(i>=L->length)
return 0;
else
return i+1;
}
int ListInsert(SqList*&L,int i,char e)
{
int j;
if(i<1||i>L->length+1)
return 0;
i--;
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return 1;
}
int ListDelete(SqList *&L,int i,char &e)
{
int j;
if(i<1||i>L->length)
return 0;
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->length--;
return 1;
}
void main ()
{
SqList *p;
char b[10],e;
int k;
cout<<"元素个数:";
cin>>k;
cout<<"输入元素:";
for(int m=0;m<k;m++)
cin>>b[m];
InitList(p);
CreateList(p,b,k);
cout<<"输出顺序表:";
DispList(p);
cout<<"顺序表长度是:"<<ListLength(p)<<endl;
if(ListEmpty(p))
cout<<"顺序表为空"<<endl;
else
cout<<"顺序表不为空"<<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<iostream.h>
#include<malloc.h>
typedef struct LNode
{
char 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;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=a[i];
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)
{
cout<<p->data;
p=p->next;
}
cout<<endl;
}
char GetElem(LinkList *L,int i,char &e)
{
int j=0;
LinkList *p=L;
while(j<i&&p!=NULL)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
e=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);
else
return(i);
}
int ListInsert(LinkList *&L,int i,char e)
{
int j=0;
LinkList *p=L,*s;
while(j<i-1&&p)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
s=(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(j<i-1&&p)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
q=p->next;
if(!q)
return 0;
e=q->data;
p->next=q->next;
free(q);
return 1;
}
}
void main()
{
LinkList *h;
char b[10],e;
int k;
cout<<"元素个数:";
cin>>k;
cout<<"输入元素:";
for(int m=0;m<k;m++)
cin>>b[m];
InitList(h);
CreateListR(h,b,k);
cout<<"输出单链表:";
DispList(h);
cout<<"单链表长度是:"<<ListLength(h)<<endl;
if(ListEmpty(h))
cout<<"单链表为空"<<endl;
else
cout<<"单链表不为空"<<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<iostream.h>
#include<malloc.h>
typedef struct LNode
{
char 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;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=a[i];
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)
{
cout<<p->data;
p=p->next;
}
cout<<endl;
}
char GetElem(LinkList *L,int i,char &e)
{
int j=1;
LinkList *p=L->next;
while(j<i&&p!=L&&p)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
e=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);
else
return(i);
}
int ListInsert(LinkList *&L,int i,char e)
{
int j=1;
LinkList *p=L->next,*s;
while(j<i-1&&p&&p!=L)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
s=(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(j<i-1&&p&&p!=L)
{
j++;
p=p->next;
}
if(!p)
return 0;
else
{
q=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 b[10],e;
int k;
cout<<"元素个数:";
cin>>k;
cout<<"输入元素:";
for(int m=0;m<k;m++)
cin>>b[m];
InitList(h);
CreateListR(h,b,k);
cout<<"输出循环单链表:";
DispList(h);
cout<<"循环单链表长度是:"<<ListLength(h)<<endl;
if(ListEmpty(h))
cout<<"循环单链表为空"<<endl;
else
cout<<"循环单链表不为空"<<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<iostream.h>
#include<malloc.h>
typedef struct polynomial
{
int 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;i<n;i++)
{
s=(LinkList*)malloc(sizeof(LinkList));
cout<<"依次输入多项式系数和指数：";
cin>>s->coef>>s->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;i<n;i++)
{
if(s==NULL)
{
s=list1->next;
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;
}
else
{
if(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;
}
cout<<"多项式相加的结果是:";
list1=list1->next;
while(list1)
{
cout<<list1->coef<<"x^"<<list1->index;
if(list1->next!=NULL)
cout<<"+";
list1=list1->next;
}
}
void DispList(LinkList *L)
{
L=L->next;
while(L)
{
cout<<L->coef<<"x^"<<L->index;
if(L->next!=NULL)
if(L->next->coef>0)
cout<<"+";
L=L->next;
}
}
void main()
{
LinkList *list1,*list2;
InitList(list1);
InitList(list2);
int m,n;
cout<<"请输入第一个多项式的项数:";
cin>>m;
CreateList(list1,m);
cout<<"多项式表示是:";
DispList(list1);
cout<<endl;
cout<<"请输入第二个多项式的项数:";
cin>>n;
CreateList(list2,n);
cout<<"多项式表示是:";
DispList(list2);
cout<<endl;
AddList(list1,list2,m,n);
cout<<endl;
}