实验线性表操作Word格式文档下载.docx
《实验线性表操作Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《实验线性表操作Word格式文档下载.docx（12页珍藏版）》请在冰点文库上搜索。
函数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<
i<
n）
函数LinkListListInsert_L（LinkListL，inti，chari_e）
（5）在单链表LA上删除第i个数据元素，并用r_e来返回删除的数据元素值
函数LinkListListDelete_L（LinkListL，inti）
输出单链表进行插入（删除）操作前、后的数据元素
函数voidShowList（LinkListL）
图1.2单链表进行插入（删除）操作前、后的数据元素
三、问题讨论
四、实验心得
附：
程序源代码一（不包含在实验报告里边）
/*顺序表操作*/
#include<
stdio.h>
string.h>
stdlib.h>
#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（"
存储空间分配失败"
）;
length=0;
//空表长度为0
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>
length+1）
i值不合法"
if（L->
length>
=L->
listsize）{//当前存储空间已满，增加容量
int*newbase=（int*）realloc（L->
data,（L->
listsize+LISTINCREMENT）*sizeof（int））;
newbase）
printf（"
存储分配失败"
//存储分配失败
data=newbase;
//新基址
listsize+=LISTINCREMENT;
//增加存储容量
}
q=&
（L->
data[i-1]）;
//q为插入位置
for（p=&
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>
length）
//i值不合法
p=&
//p为被删除元素的位置
e=*p;
//被删除元素的值赋给e
q=L->
data+L->
length-1;
//表尾元素的位置
for（++p;
p<
++p）
*（p-1）=*p;
//被删除元素之后的元素左移
--L->
//表长减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->
Lb_len=Lb->
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）{
i++;
while（j<
=Lb_len）{
j++;
}//MergeList
/*创建一个具有n个数据元素的线性表*/
voidCreatList_Sq（SqList*L,intn）
inti=0;
InitList_Sq（L）;
输入%d个元素建立顺序表：
\n"
n）;
while（i<
{
scanf（"
%d,"
&
data[i]））;
i++;
length=n;
/*打印顺序表中元素*/
voidShowList（SqList*L）//打印顺序表
inti;
for（i=0;
i<
i++）
%d"
L->
data[i]）;
/*释放顺序表*/
voidClearList（SqList*L）
{
if（L->
data!
=NULL）
{
free（L->
data）;
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
输入插入的位置：
"
scanf（"
&
i）;
输入插入的元素：
e）;
在LA表中第%d个数据元素前插入新元素%d后表：
i,e）;
ListInsert_Sq（&
LA,i,e）;
ShowList（&
LA）;
/*在LA表中删除第i个数据元素，并显示删除的数据元素*/
输入在表LA中要删除第k个元素：
k）,
e=ListDelete_Sq（&
LA,k）;
删除的第%d个元素为：
%d\n"
k,e）;
/*LA和LB表归并到LC中并输出其中的数据元素*/
LB,N）;
//建立顺序表LB
InitList_Sq（&
LC）;
//初始化LC
MergeList（&
LA,&
LB,&
LA和LB表归并后表LC中的元素：
ClearList（&
LB）;
程序二：
/*单链表操作*/
#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为结点数目
单链表结点数：
p=p->
next;
//firstnode
单链表的所有结点依次为:
）;
/*
while（p&
i<
{
printf（"
p->
p=p->
}*/
while（p）
}
}else
单链表为空\n"
/*头插法*/
LinkListh,p1,p2;
h=InitList_L（）;
p1=（LinkList）malloc（sizeof（LNode））;
//头结点
p1->
data=n;
h=p1;
next=NULL;
头插法—输入单链表的%d个数据元素:
n）;
for（i=0;
n;
i++）
p2=（LinkList）malloc（sizeof（LNode））;
（p2->
data））;
p2->
next=p1->
p1->
next=p2;
return（h）;
/*尾插法建立单链表*/
LinkListCreatList_L_T（intn）
尾插法—输入单链表的%d个数据元素:
next=p2;
p1=p2;
/*头插法和尾插法分别创建一个单链表，并依次输出其中元素*/
LinkListInitList_L（）;
LinkListCreatList_L（intn）;
voidShowList（LinkListL）;
LinkListL,L_T;
L=CreatList_L（M）;
ShowList（L）;
L_T=CreatList_L_T（N）;
ShowList（L_T）;
升级会员 