数据结构顺序线性表的例题算法2.2——C语言完整实现
本帖最后由 兔子不吃窝边草 于 2021-10-2 16:39 编辑已知线性表La，Lb的数据元素是升序排列。将La与Lb合并为一个新的表Lc，Lc中的数据元素也是升序排列。La=（3,5,8,11），Lb=（2,6,8,9,11,15,20）
求出来的Lc=（2,3,5,6,8,9,11,11,15,20）
动态数组的插入ListInsert(),加入了判断是否满的情况，因此不用担心溢出的问题。
#include<stdio.h>
#include<stdlib.h>
#define ListInitsize 20//初始分配内存数
#define OVERFLOW -2 //异常状态
#define ADD 10 //分配内存增量
typedef struct
{
int *data;//顺序线性表动态数组名
int length;//线性表长度
int Listsize;//线性表当前分配的内存数量；
}List;
int InitList(List *L)//线性表初始化
{
L->data =malloc(ListInitsize*sizeof(int));//分配内存
if(!L->data)
exit(OVERFLOW);//分配内存失败，则退出。
L->length = 0;
L->Listsize = ListInitsize;// 线性表内存为初始化内存数。
return 1;
}
int GetElem(List *L,int i,int *e)//获取线性表第i个元素
{
if(i<1||i>L->length)//若i不在范围内，则退出。
return 0;
*e = L->data;
return 1;
}
int ListInsert(List *L,int i,int e)//插入e至第i个元素位置，需要将i个元素至最后一个元素向后移动一个位置
{
int *p=malloc(sizeof(int));
int *q=malloc(sizeof(int));
int *newbase; //新分配的动态数组名
if(i<1||i>L->length+1)//若插入位置在最后一个元素的后一个元素之后也要退出
return 0;
if(L->length>=L->Listsize)//判定分配内存空间是否满或溢出了。
{
newbase = realloc(L->data,(L->Listsize+ADD)*sizeof(int));//若满或溢出就重新分配内存 ，将原来的内存空间增加ADD个单位
if(!newbase)
exit(OVERFLOW);//分配内存失败，则异常退出。
L->data = newbase;//新的内存首地址为newbase，将它赋值给data。
L->Listsize += ADD;//性表当前分配的内存为原来的增加ADD。
}
q= &L->data; //将q指向第i个元素。
for(p=&L->data;p>=q;p--) //p初始化指向数组最后一个元素，依次递减至指向第i个元素。
*(p+1) = *p;//依次将最后一个元素到第i个元素的值，赋给最后一个元素的后一个元素到 i+1个元素。
//相当于i到最后一个元素整体后移一位。
*q =e; //将e插入第i的位置。
L->length++; //线性表的长度增加1。
return 1;
}
int ListDelete(List *L,int i,int *e)//删除线性表的一个元素，本题用不到。
{
int *p=malloc(sizeof(int));
int *q=malloc(sizeof(int));
if(i<1||i>L->length)
return 0;
p = &L->data;//指向第i个元素的指针。
*e = *p; //将其值保存在*e中。
q = L->data+L->length-1;//指向最后一个元素的指针。
for(++p;p<=q;p++)
*(p-1) = *p;//将第i+1个元素到最后一个元素向前移动一个位置。
L->length--;
return 1;
}
int ListLength(List L)//获取线性表长度
{
return L.length;
}
void MergeList(List La,List Lb,List *Lc)//将La与Lb中的元素按从小到大的顺序插入到Lc中，从大到小也行，改一下比较符就行。
{
int i=1,j=1,k=0; //i,j,k分别为在表la,lb,lc的位置，即第几个元素，i，j初始化为第一个元素。k初始化为第一个元素之前的位置，后面自增用前缀。
int La_len,Lb_len,ai,bj;
InitList(Lc);
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while(i<=La_len&&j<=Lb_len) //依次从La和Lb中读取较小的元素插入到 Lc中。
{
GetElem(&La,i,&ai);
GetElem(&Lb,j,&bj);
if(ai<=bj)
{
ListInsert(Lc,++k,ai);
i++;
}
else
{
ListInsert(Lc,++k,bj);
j++;
}
}
while(i<=La_len) //当Lb的元素都插入完了，剩下的La的元素依次读取并插入到Lc中。
{
GetElem(&La,i++,&ai);//注意结束上面的循环后，若是Lb的元素插入完，i指向的元素还没有插入到Lc中，因此i自增是后缀。
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len) //这是La插入完的情况，这两个只会执行一个因为有一个是插入完的。
{
GetElem(&Lb,j++,&bj);
ListInsert(Lc,++k,bj);
}
}
int main()
{
int i,e;
List La,Lb,Lc;
InitList(&La);
InitList(&Lb);
printf("创建链表La\n");
for(i=0;i<4;i++)
{
scanf("%d",&e);
ListInsert(&La,i+1,e);
}
printf("创建链表Lb\n");
for(i=0;i<7;i++)
{
scanf("%d",&e);
ListInsert(&Lb,i+1,e);
} //如题创建线性表La，Lb。
printf("数量：%d\n",ListLength(La)+ListLength(Lb));//新的线性表Lc的元素数量，这里是做一个验证，La与Lb的元素数量和与下面打印的数量应该相同。
MergeList(La,Lb,&Lc);
for(i=1;i<=Lc.length;i++)
{
GetElem(&Lc,i,&e);
printf("%d ",e);
}//依次打印新的线性表的元素。
return 0;
}
页:
[1]