模块划分:
（1） 结构体struct Node的创建。
（2） struct Node *create（）链表的创建。
（3） void print（struct Node *head）功能是对链表进行输出。
（4） struct Node * inter_link（struct Node * chain1, int a, struct Node * chain2, int b）
算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。
（5） void InsertSort（struct Node *p,int m）算法的功能是对一合并好的链表进行升序插入排序。
（6） main（）函数主要是对算法进行测试。
数据结构：
数据结构定义如下：
struct Node
{
long int number;
struct Node *next;
};
源程序：
#include
#include
#include
#include
#define L sizeof（struct Node）
struct Node //结构体
{
long int number;
struct Node *next;
};
struct Node *create（int a）//链表创建函数
{
int n;
struct Node *p1, *p2, *head;
head = NULL;
n = 0;
p2 = p1 = （struct Node *） malloc（L）; //分配内存
scanf（"%ld", &p1->number）;
while （a）//录入链表信息
{
n = n + 1;
if （n == 1）
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = （struct Node *） malloc（L）;
if （a !
= 1）//分配内存
scanf（"%ld", &p1->number）;
a--; //控制输入的个数
}
p2->next = NULL;
return （head）;
}//链表创建函数结束
void print（struct Node *head）//输出函数
{
struct Node *p;
p = head;
printf（"数字:
\n"）;
if （head !
= NULL）
do//循环实现输出
{
printf（"%ld", p->number）;
printf（" "）;
p = p->next;
} while （p !
= NULL）;
printf（"\n"）;
}
//链表的交叉合并算法
struct Node * inter_link（struct Node * chain1, int a, struct Node * chain2, int b） {
int temp;
struct Node *head, *p1, *p2, *pos;
/*判断a，b大小并合并 */
if （a >= b） {
head = p1 = chain1;
p2 = chain2;
} else/*b>a*/ {
head = p1 = chain2;
p2 = chain1;
temp = a, a = b, b = temp; /*交换a和b*/
}
/*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/
pos = head; /*此时pos指向p1中的第一个元素*/
while （p2 !
= NULL） {//漂亮，蛇形插入
p1 = p1->next;
pos->next = p2;
pos = p2;
p2 = p2->next;
pos->next = p1;
pos = p1;
}
return head;
}
//对合并好的链表进行排序
void InsertSort（struct Node *p, int m）//排序函数
{
int i, j, t;
struct Node *k;
k = p;
for （i = 0; i < m - 1; i++） {
for （j = 0; j < m - i - 1; j++） {
if （p->number > （p->next）->number） {
t = p->number;
p->number = （p->next）->number;
（p->next）->number = t;
}
p = p->next;
}
p = k;
}
}
//主函数
int main（）//main函数
{
struct Node *p1, *p2;
int a;
int b;
int h;
printf（"请输入第一个链表:
\n"）;
printf（"\n输入链表的长度a:
\n"）;
scanf（"%d", &a）;
printf（"请输入链表数据：
"）;
p1 = create（a）;
printf（"\n你刚才输入的第一个链表信息:
\n "）;
print（p1）;
printf（"\n 请输入第二个链表:
\n"）;
printf（"\n输入链表的长度b:
\n"）;
scanf（"%d", &b）;
printf（"请输入链表数据：
"）;
p2 = create（b）;
printf（"\n你刚才输入的第二个链表的信息:
\n"）;
print（p2）;
p1 = inter_link（p1, a, p2, b）;
h = a + b;
printf（"\n合并后的链表\n：
"）;
print（p1）;
InsertSort（p1, h）;
printf（"\n排序后的链表:
\n"）;
print（p1）;
return 0;
}
测试结果：
（1）
（2）测试结果分析：
程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。
题目：
可变长顺序表设计
基本要求：
（1）使用动态数组结构。
（2）顺序表的操作包括：
初始化、求数据元素个数、插入、删除、取数据元素，编写每个操作的函数。
（3）设计一个测试主函数。
测试数据:
4，5，6，7，8
算法思想：
可变长顺序表的设计，主要是利用动态数组结构的设计方法。
动态数组是指用动态内存分配方法定义的数组，它其中的元素的个数是在用户申请动态数组空间时才确定的。
此外，用键盘输入顺序表的元素，进行建立顺序表。
依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。
模块划分：
（1）结构体typedefstruct的创建
（2）初始化空表DatatypeInitList_Sq（SqList&L）
（3）建立顺序表DatatypeCreatList_Sq（SqList&L,intn）
（4）销毁线性表DatatypeDestoryList_Sq（SqList&L）
（5）判定是否为空表DatatypeListEmpty_Sq（SqListL）
（6）求L表中的元素的个数intListLength_Sq（SqListL）
（7）取表中的的第i个元素DatatypeGetElem_Sq（SqListL,inti,Datatype&e）
（8）插入节点DatatypeListInsert_Sq（SqList&L,inti,Datatypee）
（9）删除节点DatatypeListDelete_Sq（SqList&L,inti,Datatype&e）
（10）输出线性表LvoidOutput（SqListL）
（11）main（）函数主要是调用以上函数对算法进行测试
数据结构：
1、顺序表结构体定义
typedefstruct
{
Datatype*elem;
intlength;
intlistsize;
}SqList;
2、动态数组
动态申请空间：
L.elem=（Datatype*）malloc（LIST_INIT_SIZE*sizeof（Datatype））;
源程序：
#defineNULL0
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间的分配增量
#include
#include
typedefintDatatype;
typedefstruct
{
Datatype*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList;
//1.初始化空表
DatatypeInitList_Sq（SqList&L）
{
L.elem=（Datatype*）malloc（LIST_INIT_SIZE*sizeof（Datatype））;
if（!
L.elem）
exit（-1）;//存储分配失败
L.length=0;//空表长度为
L.listsize=LIST_INIT_SIZE;//初始存储容量
return1;
}
//2.建立顺序表L
DatatypeCreatList_Sq（SqList&L,intn）
{
inti;
Datatypee;
printf（"输入顺序表的长度:
"）;
scanf（"%d",&n）;
L.length=n;
if（L.length>LIST_INIT_SIZE）
L.elem=（Datatype*）realloc（L.elem,L.length*sizeof（Datatype））;
printf（"输入数据:
"）;
for（i=0;i<=L.length-1;i++）
{
scanf（"%d",&e）;
L.elem[i]=e;
}
return1;
}
//3.销毁线性表
DatatypeDestoryList_Sq（SqList&L）
{
if（L.elem）
{
free（L.elem）;
L.elem=NULL;
L.length=L.listsize=0;
return1;
}
return0;
}
//4.判定是否空表
DatatypeListEmpty_Sq（SqListL）
{
if（L.length）
return0;
return1;
}
//5.求L中数据元素的个数
intListLength_Sq（SqListL）
{
returnL.length;
}
//6.取表第i个元素
DatatypeGetElem_Sq（SqListL,inti,Datatype&e）//用e返回顺序表L中第i个数据元素的值,i的合法值为<=i<=ListLength_Sq（L）
{
if（（i<1）||（i>L.length））
return0;//i值不合法
else
e=L.elem[i-1];
return1;
}
//7.插入结点
DatatypeListInsert_Sq（SqList&L,inti,Datatypee）//在顺序线性表L中第i个位置之前插入新的元素e,i的合法值为<=i<=ListLength_Sq（L）+1
{
Datatype*q,*p,*newbase;
if（i<1||i>L.length+1）
return0;//i值不合法
q=&（L.elem[i-1]）;//q为插入位置
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;//插入位置及之后的元素后移
*q=e;//插入e
++L.length;//表长增
return1;
}
//8.删除结点
DatatypeListDelete_Sq（SqList&L,inti,Datatype&e）//在顺序线性表L中删除第i个元素,并用e返回其值,i的合法值为<=i<=ListLength_Sq（L）
{
Datatype*p,*q;
if（（i<1）||（i>L.length））
return0;//i值不合法
p=&（L.elem[i-1]）;//p为被删除元素的位置
e=*p;//被删除元素的值赋给e
q=L.elem+L.length-1;//表尾元素的位置
for（++p;p<=q;++p）
*（p-1）=*p;//被删除元素之后的元素左移
--L.length;//表长减
return1;
}
//9.输出顺序表
voidOutput（SqListL）//输出线性表L
{
inti;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
}
voidput（）//窗口边框
{
inti;
for（i=0;i<10;i++）
printf（""）;
for（i=0;i<31;i++）
printf（"*"）;
printf（"\n"）;
}
voidmainpp（）//显示窗口
{
inti;
put（）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"1.建立一个顺序表"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"2.输出一个顺序表"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"3.向顺序表中插入一个元素"）;
for（i=0;i<2;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"4.删除顺序表中的一个元素"）;
for（i=0;i<2;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"5.从顺序表中取出一个元素"）;
for（i=0;i<2;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"6.求顺序表中数据元素个数"）;
for（i=0;i<2;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"7.判断顺序表中是否为空"）;
for（i=0;i<4;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"8.销毁线性表"）;
for（i=0;i<14;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
for（i=0;i<10;i++）
printf（""）;
printf（"*"）;
printf（"0.退出"）;
for（i=0;i<8;i++）
printf（""）;
printf（"*"）;
printf（"\n"）;
put（）;
}
intmain（）//主函数
{
intn=0,i,j=0,k=1,m,q,x,y,e;
SqListl,la,lc;
InitList_Sq（l）;
mainpp（）;
while（k）
{
printf（"请选择--8：
"）;
scanf（"%d",&m）;
getchar（）;
switch（m）
{
case0:
exit（0）;
case1:
{
CreatList_Sq（l,n）;
Output（l）;
break;
}
case2:
Output（l）;printf（"\n"）;break;
case3:
{
printf（"请输入要插入的元素的位置及其值：
"）;
fflush（stdin）;
scanf（"%d,%d",&i,&x）;
ListInsert_Sq（l,i,x）;
Output（l）;
printf（"\n"）;
break;
}
case4:
{
printf（"请输入要删除元素的位置：
"）;
fflush（stdin）;
scanf（"%d",&i）;
ListDelete_Sq（l,i,y）;
Output（l）;
printf（"\n"）;
break;
}
case5:
{
printf（"请输入要取出的元素的序号：
"）;
fflush（stdin）;
scanf（"%d",&i）;
GetElem_Sq（l,i,e）;
printf（"取出的第%d个元素为：
%d\n",i,e）;
break;
}
case6:
{
printf（"顺序表中数据元素的个数为：
%d",ListLength_Sq（l））;
}
case7:
{
q=ListEmpty_Sq（l）;
if（q==1）
printf（"此表为空"）;
else
printf（"此表不空"）;
printf（"\n"）;
break;
}
case8:
{
DestoryList_Sq（l）;
break;
}
default:
exit（0）;
}
printf（"继续运行吗？
Y（）/N（）：
"）;
scanf（"%d",&k）;
if（!
k）
exit（0）;
}
return0;
}
测试结果：
（2）测试结果分析：
程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。
升级会员 