实验线性表操作.docx
《实验线性表操作.docx》由会员分享，可在线阅读，更多相关《实验线性表操作.docx（12页珍藏版）》请在冰点文库上搜索。
实验线性表操作
实验一线性表基本操作
一、实验目的
1、理解线性表的数据结构及其应用
2、掌握线性表的顺序存储方式及其基本操作（建表、插入、删除）
3、掌握线性表的链式存储方式以及基本操作（建表、插入、删除）
4、理解链式存储的概念和具体语言环境下的表示方法
二、实验内容
1、顺序表的操作
具体要求：
（1）顺序表的存储结构
typedefstruct｛
int*data；//整型数据元素，可以是其它类型
intlength；//顺序表的当前长度（元素个数）
intlistsize；//当前分配的存储容量（已经分配的内存空间大小）
｝SqList；
或者
#defineN10;
intdata[N];//用数组来模拟实现顺序表
（2）构造一个空表L
函数:
voidInitList_Sq（SqList*L）
（3）分别建立有n个数据元素的顺序表
函数voidCreatList_Sq（SqList*L,intn）
（4）在第i个元素之前插入一个数据元素
函数voidInsertList_Sq（SqList*L，inte）
（5）删除一个数据元素e
函数intListDelete_Sq（SqList*L,inti）
（6）结果显示：
输出顺序表中的数据元素
函数voidShowList_Sq（SqList*L）
（7）顺序表元素排序：
对顺序表中元素按非递减排序（选做）
函数voidSortList_Sq（SqList*L）
（8）归并两个有序的（非递减排列）顺序表Sq_LA和Sq_LB，新表Sq_Lnew中数据元素非递减排列（选做）
函数voidMergeList_Sq（SqList*La,SqList*Lb,SqList*Lc）
实验步骤：
源程序主函数如下：
运行结果：
图1.1顺序表进行归并操作前、后的各个表中数据元素
2、建立一个线性链表（单链表），实现单链表上数据元素的插入、删除操作。
具体要求：
（1）单链表的存储结构
typedefstructLNode｛
chardata；//数据元素为字符类型，可以为其它类型，例如整型
structLNode*next；//指向后继结点的指针
｝LNode，*LinkList；
（2）构造一个空的单链表
函数LinkListInitList_L（void）
（3）建立一个带头节点的具有n个结点的单链表L
函数尾插法LinkListCreatList_L_T（intn）或头插法
LinkListCreatList_L（intn）
（4）在单链表LA上插入一个数据元素i_e，插入位置为i（1函数LinkListListInsert_L（LinkListL，inti，chari_e）
（5）在单链表LA上删除第i个数据元素，并用r_e来返回删除的数据元素值
函数LinkListListDelete_L（LinkListL，inti）
（6）结果显示：
输出单链表进行插入（删除）操作前、后的数据元素
函数voidShowList（LinkListL）
实验步骤：
源程序主函数如下：
运行结果：
图1.2单链表进行插入（删除）操作前、后的数据元素
三、问题讨论
四、实验心得
附：
程序源代码一（不包含在实验报告里边）
/*顺序表操作*/
#include
#include
#include
#defineLIST_INIT_SIZE50
#defineLISTINCREMENT20
#defineM6//LA中元素个数
#defineN4//LB中元素个数
typedefintElemType;
/*顺序表的当前长度（元素个数）length,当前分配的存储容量（已经分配的内存空间大小）listsize*/
typedefstruct{
int*data;
intlength;
intlistsize;
}SqList;
/*书上算法2.3,初始化线性表，分配存储空间*/
voidInitList_Sq（SqList*L）{
L->data=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;//分配100个数据元素大小的空间
if（!
L->data）
printf（"存储空间分配失败"）;
L->length=0;//空表长度为0
L->listsize=LIST_INIT_SIZE;//初始存储容量
return;
}//InitList_Sq
/*书上算法2.4,线性表插入元素*/
voidListInsert_Sq（SqList*L,inti,inte）{
//在顺序线性表L的第i个元素之前插入新的元素e
//i的合法值为1≤i≤L->length+1
int*p,*q;
if（i<1||i>L->length+1）
printf（"i值不合法"）;
if（L->length>=L->listsize）{//当前存储空间已满，增加容量
int*newbase=（int*）realloc（L->data,（L->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）
printf（"存储分配失败"）;//存储分配失败
L->data=newbase;//新基址
L->listsize+=LISTINCREMENT;//增加存储容量
}
q=&（L->data[i-1]）;//q为插入位置
for（p=&（L->data[L->length-1]）;p>=q;--p）
*（p+1）=*p;//插入位置及之后的元素右移
*q=e;//插入e
++L->length;//表长增1
}//ListInsert_Sq
intListDelete_Sq（SqList*L,inti）{//算法2.5
//在顺序线性表L中删除第i个元素，并用e返回其值。
//i的合法值为1≤i≤ListLength_Sq（L）。
int*p,*q;
inte;
if（i<1||i>L->length）
printf（"i值不合法"）;//i值不合法
p=&（L->data[i-1]）;//p为被删除元素的位置
e=*p;//被删除元素的值赋给e
q=L->data+L->length-1;//表尾元素的位置
for（++p;p<=q;++p）
*（p-1）=*p;//被删除元素之后的元素左移
--L->length;//表长减1
returne;
}//ListDelete_Sq
/*对顺序表中元素进行非递减排序*/
voidSortList_Sq（SqList*L）
{
/*函数体：
具体功能实现*/
}
//书中算法2.7
voidMergeList（SqList*La,SqList*Lb,SqList*Lc）{
//已知线性表La和Lb中的元素按值非递减排列。
//归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。
intLa_len,Lb_len;
intai,bj;
inti=1,j=1,k=0;
La_len=La->length;
Lb_len=Lb->length;
while（（i<=La_len）&&（j<=Lb_len））{//La和Lb均非空
ai=La->data[i-1];
bj=Lb->data[j-1];
if（ai<=bj）{
ListInsert_Sq（Lc,++k,ai）;
++i;
}else{
ListInsert_Sq（Lc,++k,bj）;
++j;
}
}
while（i<=La_len）{
ai=La->data[i-1];
i++;
ListInsert_Sq（Lc,++k,ai）;
}
while（j<=Lb_len）{
bj=Lb->data[j-1];
j++;
ListInsert_Sq（Lc,++k,bj）;
}
}//MergeList
/*创建一个具有n个数据元素的线性表*/
voidCreatList_Sq（SqList*L,intn）
{
inti=0;
InitList_Sq（L）;
printf（"输入%d个元素建立顺序表：
\n",n）;
while（i{
scanf（"%d,",&（L->data[i]））;
i++;
}
L->length=n;
return;
}
/*打印顺序表中元素*/
voidShowList（SqList*L）//打印顺序表
{
inti;
for（i=0;ilength;i++）
printf（"%d",L->data[i]）;
printf（"\n"）;
}
/*释放顺序表*/
voidClearList（SqList*L）
{
if（L->data!
=NULL）
{
free（L->data）;
L->length=0;
L->listsize=0;
}
}
voidmain（）
{
voidInitList_Sq（SqList*L）;
voidCreatList_Sq（SqList*L,intn）;
voidListInsert_Sq（SqList*L,inti,inte）;
intListDelete_Sq（SqList*L,inti）;
voidShowList（SqList*L）;
voidSortList_Sq（SqList*L）;
voidMergeList（SqList*L1,SqList*L2,SqList*L3）;
voidClearList（SqList*L）;
inti,k,e;
SqListLA,LB,LC;//顺序表LA，LB,LC
//建立并初始化顺序表LA
CreatList_Sq（&LA,M）;
//在LA表中第i个数据元素前面插入一个数据元素e
printf（"输入插入的位置：
"）;
scanf（"%d,",&i）;
printf（"输入插入的元素：
"）;
scanf（"%d,",&e）;
printf（"在LA表中第%d个数据元素前插入新元素%d后表：
\n",i,e）;
ListInsert_Sq（&LA,i,e）;
ShowList（&LA）;
/*在LA表中删除第i个数据元素，并显示删除的数据元素*/
printf（"输入在表LA中要删除第k个元素：
"）;
scanf（"%d,",&k）,
e=ListDelete_Sq（&LA,k）;
printf（"删除的第%d个元素为：
%d\n",k,e）;
ShowList（&LA）;
/*LA和LB表归并到LC中并输出其中的数据元素*/
CreatList_Sq（&LB,N）;//建立顺序表LB
InitList_Sq（&LC）;//初始化LC
MergeList（&LA,&LB,&LC）;
printf（"LA和LB表归并后表LC中的元素：
\n"）;
ShowList（&LC）;
ClearList（&LA）;
ClearList（&LB）;
ClearList（&LC）;
}
程序二：
/*单链表操作*/
#include
#include
#defineM5//L中元素个数
#defineN6
/*线性链表存储结构*/
typedefstructLNode{
intdata;
structLNode*next;
}LNode,*LinkList;
/*初始化函数，返回头指针*/
LinkListInitList_L（void）
{
LinkListhead;
head=NULL;
return（head）;
}
/*从头结点开始依次输出单链表所有元素*/
voidShowList（LinkListL）
{
inti=0,n=0;
LinkListp;
p=L;
if（p!
=NULL）
{
n=p->data;//n为结点数目
printf（"单链表结点数：
%d\n",n）;
p=p->next;//firstnode
printf（"单链表的所有结点依次为:
\n"）;
/*
while（p&&i{
printf（"%d",p->data）;
p=p->next;
}*/
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
}else
printf（"单链表为空\n"）;
}
/*头插法*/
LinkListCreatList_L（intn）
{
inti;
LinkListh,p1,p2;
h=InitList_L（）;
p1=（LinkList）malloc（sizeof（LNode））;//头结点
p1->data=n;
h=p1;
p1->next=NULL;
printf（"头插法—输入单链表的%d个数据元素:
\n",n）;
for（i=0;i{
p2=（LinkList）malloc（sizeof（LNode））;
scanf（"%d,",&（p2->data））;
p2->next=p1->next;
p1->next=p2;
}
return（h）;
}
/*尾插法建立单链表*/
LinkListCreatList_L_T（intn）
{
inti;
LinkListh,p1,p2;
h=InitList_L（）;
p1=（LinkList）malloc（sizeof（LNode））;//头结点
p1->data=n;
h=p1;
printf（"尾插法—输入单链表的%d个数据元素:
\n",n）;
for（i=0;i{
p2=（LinkList）malloc（sizeof（LNode））;
scanf（"%d,",&（p2->data））;
p2->next=NULL;
p1->next=p2;
p1=p2;
}
return（h）;
}
/*头插法和尾插法分别创建一个单链表，并依次输出其中元素*/
voidmain（）
{
LinkListInitList_L（）;
LinkListCreatList_L（intn）;
voidShowList（LinkListL）;
LinkListL,L_T;
L=CreatList_L（M）;
ShowList（L）;
printf（"\n"）;
L_T=CreatList_L_T（N）;
ShowList（L_T）;
}
升级会员 