数据结构实验报告-顺序表的创建、遍历及有序合并操作.doc

数据结构实验报告-顺序表的创建、遍历及有序合并操作
二、实验内容与步骤
实现顺序表的创建、遍历及有序合并操作，基本数据结构定义如下:
typedef int ElemType；
＃define MAXSIZE 100
#define FALSE 0
＃define TRUE 1
typedef struct
｛ElemType data［MAXSIZE］;
int length；
｝seqlist；
创建顺序表,遍历顺序表
#include〈stdio。h〉
#include<stdlib。h〉
＃define MAXSIZE 100
＃define Icreament 20
#define FALSE 0
#define TRUE 1
typedef int ElemType； //用户自定义数据元素类型
// 顺序表结构体的定义
typedef struct
｛
ElemType *elem； //顺序表的基地址
int length； //顺序表的当前长度
int listsize; //预设空间容量
｝SqList； //线性表的顺序存储结构
SqList* InitList（） //创建空的顺序表
{
SqList＊ L = (SqList＊）malloc（sizeof（SqList)）；//定义顺序表L
if（!L)
｛
printf（"空间划分失败,程序退出\n”）；
return NULL；
｝
L-〉elem=(ElemType ＊）malloc（MAXSIZE＊sizeof（ElemType））；
if(!L—>elem)
｛
printf（”空间划分失败,程序退出\n”);
return NULL；
}
L—〉length=0；
L—〉listsize=MAXSIZE;
return L；
}
int CreateList(SqList＊ L) //创建顺序表（非空）
｛
int number; //顺序表中元素的个数
int i; //循环变量
printf("请输入顺序表中元素的个数：”）；
scanf（"％d"，&number）；
if（number 〉 MAXSIZE） //一定要判断输入的个数是否大于顺序表的最大长度
｛
printf（”输入个数大于顺序表的长度\n”）；
return 0；
｝
for（i=0;i〈number；i++）
｛
printf（"输入第％d个数: ”，i+1)；
scanf（”％d"，L—〉elem+i）; //L-〉elem+i：每次的输入都保存在顺序表元素中的下一个地址，而不是一直放在元素的首地址
}//给顺序表中每个数据元素赋值
L->length=number; //当前顺序表的长度
return 1；
｝
void print（SqList* L） //遍历顺序表
｛
int i；
printf（”\n开始遍历顺序表\n”);
for(i=0;i〈L—>length；i++）
｛
printf("％d”，*（L-〉elem + i)); //L—〉elem+i：和输入是一个道理
}
printf（”\n遍历结束\n”)；
printf（"\n”）;
｝
int main（）
｛
SqList* L = InitList（）; //申请一个指向顺序表的指针,并对其初始化
if(！L) //判断申请是否成功
｛
printf（”初始化线性表失败\n”）；
return 1；
｝
if（！CreateList（L)) //判断创建顺序表是否成功
｛
printf（"创建顺序表失败\n");
return 1;
}
print（L）； //打印顺序表与上面遍历顺序表相对应，若没有就不遍历
free(L-〉elem）； //释放申请的顺序表元素的内存
free（L）; //释放申请的顺序表内存
return 0；
｝
表的有序合并
＃include 〈stdio。h〉
＃include 〈stdlib。h>
#define MAXSIZE 100
typedef int ElemType；
//顺序表结构体的定义
typedef struct｛
ElemType data[MAXSIZE］ ；
int size;
｝seqlist;
//函数声明
void init(seqlist ＊slt） ；
void display（seqlist slt) ;
void sort(seqlist ＊s） ；
void combine（ seqlist *s1 ,seqlist *s2 ,seqlist *s3） ；
//顺序表的初始化函数
void init（seqlist ＊slt）
｛
slt—>size=0 ；
}
//顺序表的显示函数
void display(seqlist slt）
｛
int i;
if(!slt。size）
｛
printf(”\n顺序表为空"） ；
｝
else
｛
for(i=0；i<slt。size；i++)
printf(”\n%d\n”，slt.data[i］） ;
｝
｝
//顺序表排序
void sort（seqlist *s）
{
int i ；
int j ;
int temp ;
for(i=0；i<s—〉size-1；i++）
｛
for（j=i+1；j〈s—>size;j++）
｛
if（s-〉data［i］〉=s->data［j］)
｛
temp=s—>data［i]；
s->data［i］=s->data［j］；
s->data［j]=temp;
}
}
｝
｝
//两个有序顺序表连接函数
void combine（seqlist *s1 ， seqlist ＊s2 ， seqlist ＊s3 ）
｛
int i=0 ；
int j=0 ；
int k=0 ；
while（ i 〈 s1->size &＆ j < s2-〉size)
｛
if（s1—>data［i］〈=s2—>data［j］）
{
s3—〉data[k］=s1->data[i］；
i++；
｝
else
｛
s3->data［k]=s2—>data［j］;
j++；
}
k++；
｝
if（i==s1—>size）
｛
while(j<s2—>size)
｛
s3—〉data[k］=s2—〉data[j］；
k++；
j++；
｝
｝
if（j==s2—〉size）
｛
while（i<s1—〉size）
｛
s3—>data[k］=s1-〉data［i]；
k++；
i++;
｝
｝
s3—>size=k；
｝
//主函数
int main()
{
int i ;
int j ;
int x ;
int n ;
seqlist list1 ；
seqlist list2 ;
seqlist list3 ;
init（＆list1);
printf(”第一个顺序表元素个数：\n"）；
scanf(”％d” ,＆n） ；
printf("第一个顺序表输入:\n");
for（i=0 ； i<n ； i++）
｛
scanf（”％d”,＆list1.data［i］) ；
list1。size++ ；
｝
sort（＆list1）；//第一个表排序
init（&list2）；
printf（"第二个顺序表元素个数：\n”);
scanf（”％d” ，＆n） ；
printf(”第二个顺序表输入:\n"）；
for(i=0 ； i<n ; i++）
{
scanf(”%d"，＆list2。data［i]) ；
list2。size++ ；
｝
sort(&list2)；//第二个表排序
init（＆list3） ；
combine（＆list1 ，＆list2 ,＆list3) ；
printf（”表一与表二连接后:\n”） ；
display（list3) ;
return 0;
｝