数据结构实验报告.doc

年级
2013级
班号
 
 学号
专业
信息
 姓名
实验名称
一、线性表运算
实验
类型
设计型
综合型
创新型
√
实
验
目
的
或
要
求
1、 掌握线性表的结构特点;
2、掌握线性表的基本操作:初始化,插入,删除,查找,判空,求线性表长度等运算在顺序存储结构和链式存储结构上的实现。
实
验
原
理
(
算
法
流
程
图
或
者
含
注
释
的
源
代
码
)
实验题目:
实现线性表的基本操作:初始化,插入,删除,查找,判空,求线性表长度等。
(选做题)利用构造的线性表实现一元多项式的相加。
 
/*线性表的操作(单链表)*/
#include<>
#include<>
typedef struct LNode
{
int data;
struct LNode *next; 
 }LNode, *Linklist;/*线性表的结构*/
 
/*基本操作函数*/
/*构造空线性表。操作结果:构造空线性表,如成功返回1,否则返回0。*/
int InitList(Linklist L)
{
L=(Linklist)malloc(sizeof(LNode)); 
if(L)
{
  L->next=NULL;
return 1;
  }
else
return 0;
}
/*顺序创建一个线性链表函数。当输入的结点的数据值为0时,线性链表创建结束。
返回线性表的头结点指针。*/
Linklist hrear_create()
{
int x;
Linklist head, p, rear;
head=(Linklist)malloc(sizeof(LNode));
head->data=0;
rear=head;
printf("请输入线性表中的元素值,以0结束输入:\n");
scanf("%d",&x);
while(x!=0)
{
p=(Linklist)malloc(sizeof(LNode));
p->data=x;
rear->next=p;
rear=p;
scanf("%d",&x);
}
rear->next=NULL;
return head;
}
/*判断链表是否为空。初始条件:线性表存在。操作结果:若线性表为空,返回1,否则返回0。*/
int ListEmpty(Linklist L)
{
if(L->next==NULL){return 1;}
else
{return 0;}
}
/*求线性链表的长度函数。初始条件:线性表存在。操作结果:返回线性表中数据元素的个数。*/
int Listlength(Linklist L)
{
Linklist p;
int count=0;
p=L;
while(p->next!=NULL)
{
p=p->next;
count++;
}
return count;
}
/*确定元素e的位置。初始条件:线性表存在。操作结果:返回第一个与e相同的元素的位置;如果这样的元素不存在,则返回0。*/
int LocateElem(Linklist L,int e)
{
Linklist p;
int pos=1;
p=L->next;
while(p!=NULL)
{
if(p->data!=e)
{
p=p->next;
pos++;
}
else
return pos;
}
return 0;
}
/*在第i个元素前插入元素。初始条件:线性表存在,且1<=i<=ListLength(L)+1*。操作结果:在L中第i个位置之前插入新的元素e,插入成功返回1,否则返回0。*/
int ListInsert(Linklist L, int i, int e)
{
Linklist p,findpri;/*p用于申请空间,findpri用于找第i个节点的前驱*/
int j;
if((1<=i)&&(i<=Listlength(L)+1))/*判断i是否合法*/
{
p=(Linklist)malloc(sizeof(LNode));
if(!p) return 0;/*判断申请空间是否成功*/
else
p->data=e;
findpri=L;
for(j=1;j<i;j++)
{ findpri=findpri->next; }
p->n