已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。例如，设 LA=（3,5,8,11） LB=（2,6,8,9,1
已知线性表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,8,9,11,11,15,20）。main.cpp法一：用数组下标解决#include <stdio.h>#include <stdlib.
·
已知线性表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,8,9,11,11,15,20）。
法一：用数组下标解决
main.cpp
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASALBE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList& L);//InitList
Status DestroyList(SqList& L);//DestroyList
Status ClearList(SqList& L);//ClearList
Status ListEmpty(SqList& L);//ListEmpty
Status ListLength(SqList& L);//ListLength
Status GetElem(SqList& L, int i, int& e);//GetElem
Status compare(ElemType a, ElemType b);//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));//LocateElem
Status PriorElem(SqList L, int cur_e, int &pre_e);//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e);//NextElem
Status ListInsert(SqList& L, int i, ElemType e);//ListInsert
Status ListDelete(SqList& L,int i,ElemType& e);//ListDelete
Status visit(SqList& L);//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList));//ListTraverse
void output(SqList& L);//output
void MergeList_1(SqList La, SqList Lb, SqList& Lc);//MergeList_1
Status InitList(SqList& L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//InitList
Status DestroyList(SqList& L)
{
free(&L);
return OK;
}//DestroyList
Status ClearList(SqList& L)
{
free(L.elem);//释放指针L.elem指向的内存，但是指针L.elem指向的地址还是不变，指向的是顺序表的第一个元素的节点
//动态指针是在堆上维护的，动态指针定义后，程序为指针分配了一块内存，而且保证这块内存不会被其他乱七八糟的东西修改。
//free或者delete的时候，是放弃了指针对这个内存的占用，放弃之后，内存的值（顺序表的第一个元素的节点的值）会改写成随机值。
L.elem = NULL;//使顺序表的指针L.elem，使指针L.elem指向NULL（即0），防止产生野指针，避免误访问没有使用权的指针
//野指针就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）
L.length = 0;
return OK;
}//ClearList
Status ListEmpty(SqList& L)
{
if (L.length == 0)
return TRUE;
else
return FALSE;
}//ListEmpty
Status ListLength(SqList& L)
{
return L.length;
}//ListLength
Status GetElem(SqList& L, int i, int& e)
{
int j;
for (j = 0; j < ListLength(L); j++)//遍历顺序表L
{
if (j == i)//用j定位i
{
e = L.elem[j];//把L中第j个，也就是第i个数据元素的值赋值给整数e
return e;
break;
}
}
return ERROR;
}//GetElem
Status compare(ElemType a, ElemType b)
{
if (a == b)
return OK;
else
return ERROR;
}//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
ElemType *p = L.elem;
while (i <= (L.length - 1) && !(*compare)(*p++, e))
++i;
if (i <= L.length - 1)
{
if (i == 0)
return 0;//和else其他这种情况做个区分
else
return i;
}
else
return 0;
}//LocateElem
Status PriorElem(SqList L, int cur_e, int &pre_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != 0 && cur_e == L.elem[i])
{
judge = 1;
pre_e = L.elem[i - 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return pre_e;
}//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != ListLength(L) - 1 && cur_e == L.elem[i])
{
judge = 1;
next_e = L.elem[i + 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return next_e;
}//NextElem
Status ListInsert(SqList& L, int i, ElemType e)//在元素第i个（0<=i<=n-1）之前插入一个数据元素 ，和第n-1个元素之后插入一个数据元素
{
if (i<0 || i>L.length)
return ERROR;
if (L.length >= L.listsize)
{
ElemType* newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType* q = &(L.elem[i]);
for (ElemType *p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList& L,int i,ElemType& e)
{
if ((i<0)|| (i>ListLength(L) - 1))
return ERROR;
ElemType* p=&(L.elem[i]);
e=*p;
ElemType* q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
return OK;
}//ListDelete
Status visit(int i, SqList L)
{
if (L.elem[i] != NULL)
return OK;
else
return ERROR;
}//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList))
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
visit(i, L);
if (visit(i, L) == 1)
return OK;
else
return ERROR;
}
return ERROR;
}//ListTraverse
void output(SqList& L)
{
int i;
printf("Result:");
for (i = 0; i < ListLength(L); i++)
printf("%d ", L.elem[i]);
printf("\n");
}//output
void MergeList_1(SqList La, SqList Lb, SqList& Lc)
{
InitList(Lc);//初始化得到一个空的顺序表Lc
Status La_len = ListLength(La); Status Lb_len = ListLength(Lb);//求出顺序表La和Lb的长度分别为La_len和Lb_len
Status i, j, k;
i = j = k = 0;
int ai, bj;
while ((i <= La_len - 1) && (j <= Lb_len - 1))//遍历顺序表La和Lb
{
GetElem(La, i, ai); GetElem(Lb, j, bj); //把第i个数据元素的值赋值给ai和bj
if (ai <= bj)//如果顺序表La第i个数据元素的值小于等于顺序表Lb第j个数据元素的值
{
ListInsert(Lc, k++, ai);//在顺序表Lc中第k++个位置之前插入新的数据元素ai
++i;//继续向后遍历顺序表La
}
else//如果顺序表La第i个数据元素的值大于顺序表Lb第j个数据元素的值，即顺序表Lb第j个数据元素的值小于顺序表La第i个数据元素的值
{
ListInsert(Lc, k++, bj);//在顺序表Lc中第k++个位置之前插入新的数据元素bj
++j;//继续向后遍历顺序表Lb
}
}
while (i <= La_len - 1)//若Lb扫描完毕，但没有扫描完La
{
GetElem(La, i++, ai);
ListInsert(Lc, k++, ai);
}
while (j <= Lb_len - 1)//若La扫描完毕，但没有扫描完Lb
{
GetElem(Lb, j++, bj);
ListInsert(Lc, k++, bj);
}
}//MergeList_1
int main()
{
SqList *La = (SqList*)malloc(sizeof(SqList));
printf("InitList La Status: %d\n", InitList(*La));
int k = 5;//随便设一个
int i, n, *r = &k;
printf("Enter List Li Length: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++)
{
scanf("%d", &La->elem[i]);
La->length++;
}
// printf("ListLength: %d\n", ListLength(*La));
// printf("ListEmpty Status: %d\n", ListEmpty(*La));
// printf("GetElem: %d\n", GetElem(*La, 3, *r));//此时e是8，即*r是8
// printf("LocateElem: %d\n", LocateElem(*La, 6, compare));//此时e是6
// printf("PriorElem %d\n", PriorElem(*La, 6, *r));//此时pre_e是10，即*r是10
// printf("NextElem: %d\n", NextElem(*La, 6, *r));//此时next_e是8，即*e是8
// printf("ListInsert Status: %d\n", ListInsert(*La, 1, 15));//在i=1的位置之前插入一个数字15
// output(*La);
// printf("ListDelete Status: %d\n", ListDelete(*La, 2, *r));//删除i=2位置上的元素的值
// output(*La);
// printf("ListTraverse Status: %d\n", ListTraverse(*La, visit));
// output(*La);
SqList *Lb = (SqList*)malloc(sizeof(SqList));
printf("InitList Lb Status: %d\n", InitList(*Lb));
int m;
printf("Enter List Lb length: ");
scanf("%d", &m);
printf("Enter %d numbers: ", m);
for (i = 0; i < m; i++)
{
scanf("%d", &Lb->elem[i]);
Lb->length++;
}
SqList *Lc = (SqList*)malloc(sizeof(SqList));
MergeList_1(*La, *Lb, *Lc);
output(*Lc);
printf("ClearList Status: %d\n", ClearList(*Lc));
output(*Lc);
printf("ListEmpty Status: %d\n", ListEmpty(*Lc));
output(*Lc);
printf("DestroyList Status: %d\n", DestroyList(*Lc));
// output(*La);//线性表销毁，不要再输出此线性表
return 0;
}
在VS2019下，需将源文件的scanf改为scanf_s：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASALBE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList& L);//InitList
Status DestroyList(SqList& L);//DestroyList
Status ClearList(SqList& L);//ClearList
Status ListEmpty(SqList& L);//ListEmpty
Status ListLength(SqList& L);//ListLength
Status GetElem(SqList& L, int i, int& e);//GetElem
Status compare(ElemType a, ElemType b);//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));//LocateElem
Status PriorElem(SqList L, int cur_e, int& pre_e);//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e);//NextElem
Status ListInsert(SqList& L, int i, ElemType e);//ListInsert
Status ListDelete(SqList& L, int i, ElemType& e);//ListDelete
Status visit(SqList& L);//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList));//ListTraverse
void output(SqList& L);//output
void MergeList_1(SqList La, SqList Lb, SqList& Lc);//MergeList_1
Status InitList(SqList& L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//InitList
Status DestroyList(SqList& L)
{
free(&L);
return OK;
}//DestroyList
Status ClearList(SqList& L)
{
free(L.elem);//释放指针L.elem指向的内存，但是指针L.elem指向的地址还是不变，指向的是顺序表的第一个元素的节点
//动态指针是在堆上维护的，动态指针定义后，程序为指针分配了一块内存，而且保证这块内存不会被其他乱七八糟的东西修改。
//free或者delete的时候，是放弃了指针对这个内存的占用，放弃之后，内存的值（顺序表的第一个元素的节点的值）会改写成随机值。
L.elem = NULL;//使顺序表的指针L.elem，使指针L.elem指向NULL（即0），防止产生野指针，避免误访问没有使用权的指针
//野指针就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）
L.length = 0;
return OK;
}//ClearList
Status ListEmpty(SqList& L)
{
if (L.length == 0)
return TRUE;
else
return FALSE;
}//ListEmpty
Status ListLength(SqList& L)
{
return L.length;
}//ListLength
Status GetElem(SqList& L, int i, int& e)
{
int j;
for (j = 0; j < ListLength(L); j++)//遍历顺序表L
{
if (j == i)//用j定位i
{
e = L.elem[j];//把L中第j个，也就是第i个数据元素的值赋值给整数e
return e;
break;
}
}
return ERROR;
}//GetElem
Status compare(ElemType a, ElemType b)
{
if (a == b)
return OK;
else
return ERROR;
}//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
ElemType* p = L.elem;
while (i <= (L.length - 1) && !(*compare)(*p++, e))
++i;
if (i <= L.length - 1)
{
if (i == 0)
return 0;//和else其他这种情况做个区分
else
return i;
}
else
return 0;
}//LocateElem
Status PriorElem(SqList L, int cur_e, int& pre_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != 0 && cur_e == L.elem[i])
{
judge = 1;
pre_e = L.elem[i - 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return pre_e;
}//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != ListLength(L) - 1 && cur_e == L.elem[i])
{
judge = 1;
next_e = L.elem[i + 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return next_e;
}//NextElem
Status ListInsert(SqList& L, int i, ElemType e)//在元素第i个（0<=i<=n-1）之前插入一个数据元素 ，和第n-1个元素之后插入一个数据元素
{
if (i<0 || i>L.length)
return ERROR;
if (L.length >= L.listsize)
{
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType* q = &(L.elem[i]);
for (ElemType* p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList& L, int i, ElemType& e)
{
if ((i < 0) || (i > ListLength(L) - 1))
return ERROR;
ElemType* p = &(L.elem[i]);
e = *p;
ElemType* q = L.elem + L.length - 1;
for (++p; p <= q; ++p)
*(p - 1) = *p;
--L.length;
return OK;
}//ListDelete
Status visit(int i, SqList L)
{
if (L.elem[i] != NULL)
return OK;
else
return ERROR;
}//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList))
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
visit(i, L);
if (visit(i, L) == 1)
return OK;
else
return ERROR;
}
return ERROR;
}//ListTraverse
void output(SqList& L)
{
int i;
printf("Result:");
for (i = 0; i < ListLength(L); i++)
printf("%d ", L.elem[i]);
printf("\n");
}//output
void MergeList_1(SqList La, SqList Lb, SqList& Lc)
{
InitList(Lc);//初始化得到一个空的顺序表Lc
Status La_len = ListLength(La); Status Lb_len = ListLength(Lb);//求出顺序表La和Lb的长度分别为La_len和Lb_len
Status i, j, k;
i = j = k = 0;
int ai, bj;
while ((i <= La_len - 1) && (j <= Lb_len - 1))//遍历顺序表La和Lb
{
GetElem(La, i, ai); GetElem(Lb, j, bj); //把第i个数据元素的值赋值给ai和bj
if (ai <= bj)//如果顺序表La第i个数据元素的值小于等于顺序表Lb第j个数据元素的值
{
ListInsert(Lc, k++, ai);//在顺序表Lc中第k++个位置之前插入新的数据元素ai
++i;//继续向后遍历顺序表La
}
else//如果顺序表La第i个数据元素的值大于顺序表Lb第j个数据元素的值，即顺序表Lb第j个数据元素的值小于顺序表La第i个数据元素的值
{
ListInsert(Lc, k++, bj);//在顺序表Lc中第k++个位置之前插入新的数据元素bj
++j;//继续向后遍历顺序表Lb
}
}
while (i <= La_len - 1)//若Lb扫描完毕，但没有扫描完La
{
GetElem(La, i++, ai);
ListInsert(Lc, k++, ai);
}
while (j <= Lb_len - 1)//若La扫描完毕，但没有扫描完Lb
{
GetElem(Lb, j++, bj);
ListInsert(Lc, k++, bj);
}
}//MergeList_1
int main()
{
SqList* La = (SqList*)malloc(sizeof(SqList));
printf("InitList La Status: %d\n", InitList(*La));
int k = 5;//随便设一个
int i, n, * r = &k;
printf("Enter List Li Length: ");
scanf_s("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++)
{
scanf_s("%d", &La->elem[i]);
La->length++;
}
// printf("ListLength: %d\n", ListLength(*La));
// printf("ListEmpty Status: %d\n", ListEmpty(*La));
// printf("GetElem: %d\n", GetElem(*La, 3, *r));//此时e是8，即*r是8
// printf("LocateElem: %d\n", LocateElem(*La, 6, compare));//此时e是6
// printf("PriorElem %d\n", PriorElem(*La, 6, *r));//此时pre_e是10，即*r是10
// printf("NextElem: %d\n", NextElem(*La, 6, *r));//此时next_e是8，即*e是8
// printf("ListInsert Status: %d\n", ListInsert(*La, 1, 15));//在i=1的位置之前插入一个数字15
// output(*La);
// printf("ListDelete Status: %d\n", ListDelete(*La, 2, *r));//删除i=2位置上的元素的值
// output(*La);
// printf("ListTraverse Status: %d\n", ListTraverse(*La, visit));
// output(*La);
SqList* Lb = (SqList*)malloc(sizeof(SqList));
printf("InitList Lb Status: %d\n", InitList(*Lb));
int m;
printf("Enter List Lb length: ");
scanf_s("%d", &m);
printf("Enter %d numbers: ", m);
for (i = 0; i < m; i++)
{
scanf_s("%d", &Lb->elem[i]);
Lb->length++;
}
SqList* Lc = (SqList*)malloc(sizeof(SqList));
MergeList_1(*La, *Lb, *Lc);
output(*Lc);
printf("ClearList Status: %d\n", ClearList(*Lc));
output(*Lc);
printf("ListEmpty Status: %d\n", ListEmpty(*Lc));
output(*Lc);
printf("DestroyList Status: %d\n", DestroyList(*Lc));
// output(*La);//线性表销毁，不要再输出此线性表
return 0;
}
法二：用指针解决
main.cpp
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASALBE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList& L);//InitList
Status DestroyList(SqList& L);//DestroyList
Status ClearList(SqList& L);//ClearList
Status ListEmpty(SqList& L);//ListEmpty
Status ListLength(SqList& L);//ListLength
Status GetElem(SqList& L, int i, int& e);//GetElem
Status compare(ElemType a, ElemType b);//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));//LocateElem
Status PriorElem(SqList L, int cur_e, int &pre_e);//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e);//NextElem
Status ListInsert(SqList& L, int i, ElemType e);//ListInsert
Status ListDelete(SqList& L,int i,ElemType& e);//ListDelete
Status visit(SqList& L);//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList));//ListTraverse
void output(SqList& L);//output
void MergeList_2(SqList La, SqList Lb, SqList& Lc);//MergeList_2
Status InitList(SqList& L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//InitList
Status DestroyList(SqList& L)
{
free(&L);
return OK;
}//DestroyList
Status ClearList(SqList& L)
{
free(L.elem);//释放指针L.elem指向的内存，但是指针L.elem指向的地址还是不变，指向的是顺序表的第一个元素的节点
//动态指针是在堆上维护的，动态指针定义后，程序为指针分配了一块内存，而且保证这块内存不会被其他乱七八糟的东西修改。
//free或者delete的时候，是放弃了指针对这个内存的占用，放弃之后，内存的值（顺序表的第一个元素的节点的值）会改写成随机值。
L.elem = NULL;//使顺序表的指针L.elem，使指针L.elem指向NULL（即0），防止产生野指针，避免误访问没有使用权的指针
//野指针就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）
L.length = 0;
return OK;
}//ClearList
Status ListEmpty(SqList& L)
{
if (L.length == 0)
return TRUE;
else
return FALSE;
}//ListEmpty
Status ListLength(SqList& L)
{
return L.length;
}//ListLength
Status GetElem(SqList& L, int i, int& e)
{
int j;
for (j = 0; j < ListLength(L); j++)//遍历顺序表L
{
if (j == i)//用j定位i
{
e = L.elem[j];//把L中第j个，也就是第i个数据元素的值赋值给整数e
return e;
break;
}
}
return ERROR;
}//GetElem
Status compare(ElemType a, ElemType b)
{
if (a == b)
return OK;
else
return ERROR;
}//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
ElemType *p = L.elem;
while (i <= (L.length - 1) && !(*compare)(*p++, e))
++i;
if (i <= L.length - 1)
{
if (i == 0)
return TRUE;//和else其他这种情况做个区分
else
return i;
}
else
return 0;
}//LocateElem
Status PriorElem(SqList L, int cur_e, int &pre_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != 0 && cur_e == L.elem[i])
{
judge = 1;
pre_e = L.elem[i - 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return pre_e;
}//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != ListLength(L) - 1 && cur_e == L.elem[i])
{
judge = 1;
next_e = L.elem[i + 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return next_e;
}//NextElem
Status ListInsert(SqList& L, int i, ElemType e)//在元素第i个（0<=i<=n-1）之前插入一个数据元素 ，和第n-1个元素之后插入一个数据元素
{
if (i<0 || i>L.length)
return ERROR;
if (L.length >= L.listsize)
{
ElemType* newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType* q = &(L.elem[i]);
for (ElemType *p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList& L,int i,ElemType& e)
{
if ((i<0)|| (i>ListLength(L) - 1))
return ERROR;
ElemType* p=&(L.elem[i]);
e=*p;
ElemType* q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
return OK;
}//ListDelete
Status visit(int i, SqList L)
{
if (L.elem[i] != NULL)
return OK;
else
return ERROR;
}//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList))
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
visit(i, L);
if (visit(i, L) == 1)
return OK;
else
return ERROR;
}
return ERROR;
}//ListTraverse
void output(SqList& L)
{
int i;
printf("Result:");
for (i = 0; i < ListLength(L); i++)
printf("%d ", L.elem[i]);
printf("\n");
}//output
void MergeList_2(SqList La, SqList Lb, SqList& Lc)
{
ElemType* pa = La.elem; ElemType* pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
ElemType* pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem)
exit(OVERFLOW);
ElemType* pa_last = La.elem + La.length - 1;
ElemType* pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last)
*pc++ = *pa++;
while (pb <= pb_last)
*pc++ = *pb++;
}//MergeList_2
int main()
{
SqList *La = (SqList*)malloc(sizeof(SqList));
printf("InitList La Status: %d\n", InitList(*La));
int k = 5;//随便设一个
int i, n, *r = &k;
printf("Enter List Li Length: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++)
{
scanf("%d", &La->elem[i]);
La->length++;
}
// printf("ListLength: %d\n", ListLength(*La));
// printf("ListEmpty Status: %d\n", ListEmpty(*La));
// printf("GetElem: %d\n", GetElem(*La, 3, *r));//此时e是8，即*r是8
// printf("LocateElem: %d\n", LocateElem(*La, 6, compare));//此时e是6
// printf("PriorElem %d\n", PriorElem(*La, 6, *r));//此时pre_e是10，即*r是10
// printf("NextElem: %d\n", NextElem(*La, 6, *r));//此时next_e是8，即*e是8
// printf("ListInsert Status: %d\n", ListInsert(*La, 1, 15));//在i=1的位置之前插入一个数字15
// output(*La);
// printf("ListDelete Status: %d\n", ListDelete(*La, 2, *r));//删除i=2位置上的元素的值
// output(*La);
// printf("ListTraverse Status: %d\n", ListTraverse(*La, visit));
// output(*La);
SqList *Lb = (SqList*)malloc(sizeof(SqList));
printf("InitList Lb Status: %d\n", InitList(*Lb));
int m;
printf("Enter List Lb length: ");
scanf("%d", &m);
printf("Enter %d numbers: ", m);
for (i = 0; i < m; i++)
{
scanf("%d", &Lb->elem[i]);
Lb->length++;
}
// output(*Lb);
SqList *Lc = (SqList*)malloc(sizeof(SqList));
MergeList_2(*La, *Lb, *Lc);
output(*Lc);
printf("ClearList Status: %d\n", ClearList(*Lc));
output(*Lc);
printf("ListEmpty Status: %d\n", ListEmpty(*Lc));
output(*Lc);
printf("DestroyList Status: %d\n", DestroyList(*Lc));
// output(*La);//线性表销毁，不要再输出此线性表
return 0;
}
在VS2019下，需将源文件的scanf改为scanf_s：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASALBE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList& L);//InitList
Status DestroyList(SqList& L);//DestroyList
Status ClearList(SqList& L);//ClearList
Status ListEmpty(SqList& L);//ListEmpty
Status ListLength(SqList& L);//ListLength
Status GetElem(SqList& L, int i, int& e);//GetElem
Status compare(ElemType a, ElemType b);//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));//LocateElem
Status PriorElem(SqList L, int cur_e, int& pre_e);//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e);//NextElem
Status ListInsert(SqList& L, int i, ElemType e);//ListInsert
Status ListDelete(SqList& L, int i, ElemType& e);//ListDelete
Status visit(SqList& L);//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList));//ListTraverse
void output(SqList& L);//output
void MergeList_2(SqList La, SqList Lb, SqList& Lc);//MergeList_2
Status InitList(SqList& L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//InitList
Status DestroyList(SqList& L)
{
free(&L);
return OK;
}//DestroyList
Status ClearList(SqList& L)
{
free(L.elem);//释放指针L.elem指向的内存，但是指针L.elem指向的地址还是不变，指向的是顺序表的第一个元素的节点
//动态指针是在堆上维护的，动态指针定义后，程序为指针分配了一块内存，而且保证这块内存不会被其他乱七八糟的东西修改。
//free或者delete的时候，是放弃了指针对这个内存的占用，放弃之后，内存的值（顺序表的第一个元素的节点的值）会改写成随机值。
L.elem = NULL;//使顺序表的指针L.elem，使指针L.elem指向NULL（即0），防止产生野指针，避免误访问没有使用权的指针
//野指针就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）
L.length = 0;
return OK;
}//ClearList
Status ListEmpty(SqList& L)
{
if (L.length == 0)
return TRUE;
else
return FALSE;
}//ListEmpty
Status ListLength(SqList& L)
{
return L.length;
}//ListLength
Status GetElem(SqList& L, int i, int& e)
{
int j;
for (j = 0; j < ListLength(L); j++)//遍历顺序表L
{
if (j == i)//用j定位i
{
e = L.elem[j];//把L中第j个，也就是第i个数据元素的值赋值给整数e
return e;
break;
}
}
return ERROR;
}//GetElem
Status compare(ElemType a, ElemType b)
{
if (a == b)
return OK;
else
return ERROR;
}//compare
Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
ElemType* p = L.elem;
while (i <= (L.length - 1) && !(*compare)(*p++, e))
++i;
if (i <= L.length - 1)
{
if (i == 0)
return TRUE;//和else其他这种情况做个区分
else
return i;
}
else
return 0;
}//LocateElem
Status PriorElem(SqList L, int cur_e, int& pre_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != 0 && cur_e == L.elem[i])
{
judge = 1;
pre_e = L.elem[i - 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return pre_e;
}//PriorElem
Status NextElem(SqList L, int cur_e, int& next_e)
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
if (i != ListLength(L) - 1 && cur_e == L.elem[i])
{
judge = 1;
next_e = L.elem[i + 1];
break;
}
}
if (judge == 0)
return ERROR;
else
return next_e;
}//NextElem
Status ListInsert(SqList& L, int i, ElemType e)//在元素第i个（0<=i<=n-1）之前插入一个数据元素 ，和第n-1个元素之后插入一个数据元素
{
if (i<0 || i>L.length)
return ERROR;
if (L.length >= L.listsize)
{
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType* q = &(L.elem[i]);
for (ElemType* p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList& L, int i, ElemType& e)
{
if ((i < 0) || (i > ListLength(L) - 1))
return ERROR;
ElemType* p = &(L.elem[i]);
e = *p;
ElemType* q = L.elem + L.length - 1;
for (++p; p <= q; ++p)
*(p - 1) = *p;
--L.length;
return OK;
}//ListDelete
Status visit(int i, SqList L)
{
if (L.elem[i] != NULL)
return OK;
else
return ERROR;
}//visit
Status ListTraverse(SqList& L, Status(*p)(int, SqList))
{
int i, judge;
for (i = 0, judge = 0; i < ListLength(L); i++)
{
visit(i, L);
if (visit(i, L) == 1)
return OK;
else
return ERROR;
}
return ERROR;
}//ListTraverse
void output(SqList& L)
{
int i;
printf("Result:");
for (i = 0; i < ListLength(L); i++)
printf("%d ", L.elem[i]);
printf("\n");
}//output
void MergeList_2(SqList La, SqList Lb, SqList& Lc)
{
ElemType* pa = La.elem; ElemType* pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
ElemType* pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem)
exit(OVERFLOW);
ElemType* pa_last = La.elem + La.length - 1;
ElemType* pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last)
*pc++ = *pa++;
while (pb <= pb_last)
*pc++ = *pb++;
}//MergeList_2
int main()
{
SqList* La = (SqList*)malloc(sizeof(SqList));
printf("InitList La Status: %d\n", InitList(*La));
int k = 5;//随便设一个
int i, n, * r = &k;
printf("Enter List Li Length: ");
scanf_s("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++)
{
scanf_s("%d", &La->elem[i]);
La->length++;
}
// printf("ListLength: %d\n", ListLength(*La));
// printf("ListEmpty Status: %d\n", ListEmpty(*La));
// printf("GetElem: %d\n", GetElem(*La, 3, *r));//此时e是8，即*r是8
// printf("LocateElem: %d\n", LocateElem(*La, 6, compare));//此时e是6
// printf("PriorElem %d\n", PriorElem(*La, 6, *r));//此时pre_e是10，即*r是10
// printf("NextElem: %d\n", NextElem(*La, 6, *r));//此时next_e是8，即*e是8
// printf("ListInsert Status: %d\n", ListInsert(*La, 1, 15));//在i=1的位置之前插入一个数字15
// output(*La);
// printf("ListDelete Status: %d\n", ListDelete(*La, 2, *r));//删除i=2位置上的元素的值
// output(*La);
// printf("ListTraverse Status: %d\n", ListTraverse(*La, visit));
// output(*La);
SqList* Lb = (SqList*)malloc(sizeof(SqList));
printf("InitList Lb Status: %d\n", InitList(*Lb));
int m;
printf("Enter List Lb length: ");
scanf_s("%d", &m);
printf("Enter %d numbers: ", m);
for (i = 0; i < m; i++)
{
scanf_s("%d", &Lb->elem[i]);
Lb->length++;
}
// output(*Lb);
SqList* Lc = (SqList*)malloc(sizeof(SqList));
MergeList_2(*La, *Lb, *Lc);
output(*Lc);
printf("ClearList Status: %d\n", ClearList(*Lc));
output(*Lc);
printf("ListEmpty Status: %d\n", ListEmpty(*Lc));
output(*Lc);
printf("DestroyList Status: %d\n", DestroyList(*Lc));
// output(*La);//线性表销毁，不要再输出此线性表
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
15
0- 0
已为社区贡献1条内容
所有评论(0)