线性表的两种表示：顺序表示与链式表示。
一、顺序表示。（ 参见 https://baike.1688.com/doc/view-d2690888.html）
首先，表示出线性表(动态分配顺序存储结构)
#define LIST_INTI_SIZE 100 //线性表的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 //避免初始分配量不够，实现灵活的再分配，且再分配时借助基址与realloc函数进行增加容量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }Sqlist;此处，数据元素类型约定为ElemType。
初始化线性表：
Status InitList(Sqlist &L){ //构造一个空的线性表L； L.elem = (ElemType*)malloc(LIST_INTI_SIZE*sizeof(ElemType)); if (!L.elem)exit(OVERFLOW);//存储分配失败 L.length = 0;//空表长度为0 L.listsize = LIST_INTI_SIZE;//初始存储容量 return OK; } exit(0)表示正常退出，exit(x)（x不为0）都表示异常退出，这个x是返回给操作系统（包括UNIX,Linux,和MS DOS）的，以供其他程序使用。与return（）的不同方是return是返回上一级，而exit会终止程序。数值插入：
Status ListInsert(Sqlist &L,int i,int e){ ElemType *newbase, *q, *p; L.length = ListLength(L); if ((i<1) || (i>L.length+1))//i不合法 return ERROR; if (L.length >= L.listsize) {//当前存储空间已满 newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); L.elem = newbase;//新基址 L.listsize += LISTINCREMENT;//增加容量 } q = &(L.elem[i - 1]);//p为插入位置 for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; *q = e;//插入e ++(L.length);//表长增1 return OK; }
整段代码如下： #include<stdio.h> #include<stdlib.h> #define LIST_INTI_SIZE 100 //线性表的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 //避免初始分配量不够，实现灵活的再分配，且再分配时借助基址与realloc函数进行增加容量 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }Sqlist; Status InitList(Sqlist &L){ //构造一个空的线性表L； L.elem = (ElemType*)malloc(LIST_INTI_SIZE*sizeof(ElemType)); if (!L.elem)exit(OVERFLOW);//存储分配失败 L.length = 0;//空表长度为0 L.listsize = LIST_INTI_SIZE;//初始存储容量 return OK; } int ListLength(Sqlist &L) { int i; i = 0; while (L.elem[i + 1] >= L.elem[i]) { i++; L.length++; } return i+1; //返回长度 } void GetElem(Sqlist L, int i,int &e){ if ((i<1)|| (i>(L.length+1))) { printf("输入非法"); return ; } e = L.elem[i - 1]; } Status ListInsert(Sqlist &L,int i,int e){ ElemType *newbase, *q, *p; L.length = ListLength(L); if ((i<1) || (i>L.length+1))//i不合法 return ERROR; if (L.length >= L.listsize) {//当前存储空间已满 newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));//基于原来的基址在增加分配 if (!newbase) exit(OVERFLOW); L.elem = newbase;//新基址 L.listsize += LISTINCREMENT;//增加容量 } q = &(L.elem[i - 1]);//p为插入位置 for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; *q = e;//插入e ++(L.length);//表长增1 return OK; } void MergeList(Sqlist La, Sqlist Lb, Sqlist &Lc) { //已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列 InitList(Lc); int ai, bj; int i = 1; int j = 1; int k = 0; int La_len = ListLength(La); int Lb_len = ListLength(Lb); Lc.length = La_len + Lb_len; while ((i <= La_len) && (j <= Lb_len)) { 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) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } } int main() { void MergeList(); Sqlist La, Lb, Lc; InitList(La); InitList(Lb); int i; for (i = 0; i<4; i++) scanf("%d", &La.elem[i]); for (i = 0; i<7; i++) scanf("%d", &Lb.elem[i]); MergeList(La, Lb, Lc); /*for (i = 0; i < 11; i++) printf("%d", Lc.elem[i]);*/ }
中间不知道该如何求解线性表的长度，想不出其他方法，只好依据其元素非递减排列进而进行判断。
MergeList()为上篇文章中最清晰的算法，其中调用ListInsert（）将元素值按非递减顺序一次存入。
同，也可使用指针，直接对所求线性表进行赋值。
其使用如下：
#include<stdio.h> #include<stdlib.h> #define LIST_INTI_SIZE 100 //线性表的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 //避免初始分配量不够，实现灵活的再分配，且再分配时借助基址与realloc函数进行增加容量 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }Sqlist; Status InitList(Sqlist &L){ //构造一个空的线性表L； L.elem = (ElemType*)malloc(LIST_INTI_SIZE*sizeof(ElemType)); if (!L.elem)exit(OVERFLOW);//存储分配失败 L.length = 0;//空表长度为0 L.listsize = LIST_INTI_SIZE;//初始存储容量 return OK; } int ListLength(Sqlist &L) { int i; i = 0; while (L.elem[i + 1] >= L.elem[i]) { i++; L.length++; } return i+1; //返回长度 } void MergeList(Sqlist La, Sqlist Lb, Sqlist &Lc){ int *pa = La.elem; int *pb = Lb.elem; Lc.length = ListLength(La) + ListLength(Lb); Lc.listsize = Lc.length; Lc.elem = (int *)malloc(Lc.listsize*sizeof(int)); int *pc = Lc.elem; if (!Lc.elem) exit(OVERFLOW); int *pa_last = La.elem + La.length ; int *pb_last = Lb.elem + Lb.length ; while (pa <= pa_last&&pb <= pb_last){ //归并 if (*pa <= *pb){ *pc= *pa; pa++; pc++; } else{ *pc = *pb; pb++; pc++; } } while (pa <= pa_last){ //插入La的剩余元素 *pc = *pa; pa++; pc++; } while (pb <= pb_last){ //插入Lb的剩余元素 *pc = *pb; pb++; pc++; } } int main() { void MergeList(); Sqlist La, Lb, Lc; InitList(La); InitList(Lb); int i; for (i = 0; i<4; i++) scanf_s("%d", &La.elem[i]); for (i = 0; i<7; i++) scanf_s("%d", &Lb.elem[i]); MergeList(La, Lb, Lc); for (i = 0; i < 11; i++) printf("%d", Lc.elem[i]); }通过指针显然更为简单。
代码还有许多不足，还望大家指教
