c++默认构造函数的形参列表中没有形参这句话错在哪里？_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
c++默认构造函数的形参列表中没有形参这句话错在哪里？
我有更好的答案
默认构造函数是有不止一个的：空构造复制构造右值复制构造(C++11)后两个构造函数都是带有参数的（即复制源）
采纳率：48%
p>默认构造函数有;//带有一个参数，但是参数有默认值，复制构造函数和移动构造函数不属于默认构造函数。例如：不带任何参数的构造函数；带有参数，所以是默认构造函数，但是所有的参数都有默认值。默认构造函数就是不用传递任何参数就可以调用的构造函数：class T {public:&&&&T( int data = 0 ); &nbsp
为您推荐：
其他类似问题
构造函数的相关知识
等待您来回答以下试题来自：
单项选择题下列情况中，不会调用复制构造函数的是A．用一个对象去初始化同一类的另一个新对象时B．将类的一个对象赋予该类的另一个对象时C．函数的形参是类的对象，调用函数进行形参和实参结合时D．函数的返回值是类的对象，函数执行返回调用时
为您推荐的考试题库
你可能感兴趣的试题
1A．如果一个派生类私有继承其基类，则该派生类对象不能访问基类的保护成员B．派生类的成员函数可以访问基类的所有成员C．基类对象可以赋值给派生类对象D．如果派生类没有实现基类的一个纯虚函数，则该派生类是一个抽象类2A．63B．64C．6D．73A．=()[]-＞B．+-++--C．＞＜＞=＜=D．+=-=*=/=4A．ifstream file("d:\ncre\test.txt")；B．ifstream file("d：\\ncre\\test.txt")；C．ifstream file；file．open("d：\\ncre\\test.txt")；D．ifstream*pFile=new ifstream("d：\\ncre\\test.txt")；5A．_radiusB．foo～barC．elseD．3 room
热门相关试卷
最新相关试卷线性表 - xiedeacc的专栏 - CSDN博客
1.连续线性表
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */
#include&stdlib.h& /* atoi() */
#include&io.h& /* eof() */
#include&math.h& /* floor(),ceil(),abs() */
#include&process.h& /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int S /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int B /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int ElemT
#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */
#define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */
typedef struct
ElemType * /* 存储空间基址 */
/* 当前长度 */
/* 当前分配的存储容量(以sizeof(ElemType)为单位) */
Status InitList(SqList *L);
Status DestroyList(SqList *L);
Status ClearList(SqList *L);
Status ListEmpty(SqList L);
int ListLength(SqList L);
Status GetElem(SqList L, int i, ElemType *e);
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e);
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e);
Status ListInsert(SqList *L, int i, ElemType e);
Status ListDelete(SqList *L, int i, ElemType *e);
Status ListTraverse(SqList L, void(*vi)(ElemType*));
void InsertAscend(SqList *L, ElemType e);
void InsertDescend(SqList *L, ElemType e);
Status HeadInsert(SqList *L, ElemType e);
Status EndInsert(SqList *L, ElemType e);
Status DeleteFirst(SqList *L, ElemType *e);
Status DeleteTail(SqList *L, ElemType *e);
Status DeleteElem(SqList *L, ElemType e);
Status ReplaceElem(SqList L, int i, ElemType e);
Status CreatAscend(SqList *L, int n);
Status CreatDescend(SqList *L, int n); 
#include &arrList.h&
Status InitList(SqList *L) /* 算法2.3 */
{ /* 操作结果：构造一个空的顺序线性表 */
(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!(*L).elem)
exit(OVERFLOW); /* 存储分配失败 */
(*L).length = 0; /* 空表长度为0 */
(*L).listsize = LIST_INIT_SIZE; /* 初始存储容量 */
return OK;
Status DestroyList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */
free((*L).elem);
(*L).elem = NULL;
(*L).length = 0;
(*L).listsize = 0;
return OK;
Status ClearList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
(*L).length = 0;
return OK;
Status ListEmpty(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if (L.length == 0)
return TRUE;
return FALSE;
int ListLength(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
Status GetElem(SqList L, int i, ElemType *e)
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
if (i&1 || i&L.length)
exit(ERROR);
*e = *(L.elem + i - 1);
return OK;
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0) */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
若这样的数据元素不存在，则返回值为0。算法2.6 */
ElemType *p;
int i = 1; /* i的初值为第1个元素的位序 */
p = L. /* p的初值为第1个元素的存储位置 */
while (i &= L.length&&!compare(*p++, e))
if (i &= L.length)
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{ /* 初始条件：顺序线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
否则操作失败，pre_e无定义 */
int i = 2;
ElemType *p = L.elem + 1;
while (i &= L.length&&*p != cur_e)
if (i&L.length)
return INFEASIBLE;
*pre_e = *--p;
return OK;
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e)
{ /* 初始条件：顺序线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
否则操作失败，next_e无定义 */
int i = 1;
ElemType *p = L.
while (i&L.length&&*p != cur_e)
if (i == L.length)
return INFEASIBLE;
*next_e = *++p;
return OK;
Status ListInsert(SqList *L, int i, ElemType e) /* 算法2.4 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
ElemType *newbase, *q, *p;
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 = /* 新基址 */
(*L).listsize += LISTINCREMENT; /* 增加存储容量 */
q = (*L).elem + i - 1; /* q为插入位置 */
for (p = (*L).elem + (*L).length - 1; p &= --p) /* 插入位置及之后的元素右移 */
*(p + 1) = *p;
*q = /* 插入e */
++(*L). /* 表长增1 */
return OK;
Status ListDelete(SqList *L, int i, ElemType *e) /* 算法2.5 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
ElemType *p, *q;
if (i&1 || i&(*L).length) /* i值不合法 */
return ERROR;
p = (*L).elem + i - 1; /* p为被删除元素的位置 */
*e = *p; /* 被删除元素的值赋给e */
q = (*L).elem + (*L).length - 1; /* 表尾元素的位置 */
for (++p; p &= ++p) /* 被删除元素之后的元素左移 */
*(p - 1) = *p;
(*L).length--; /* 表长减1 */
return OK;
Status ListTraverse(SqList L, void(*vi)(ElemType*))
{ /* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败 */
vi()的形参加'&'，表明可通过调用vi()改变元素的值 */
ElemType *p;
for (i = 1; i &= L. i++)
printf(&\n&);
return OK;
void InsertAscend(SqList *L, ElemType e)
{ /* 初始条件：按非降序排列的顺序线性表L已存在 */
/* 操作结果：在L中按非降序插入新的数据元素e，L的长度加1 */
ElemType *newbase, *p;
if ((*L).length &= (*L).listsize) /* 当前存储空间已满,增加分配 */
newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase)
exit(OVERFLOW); /* 存储分配失败 */
(*L).elem = /* 新基址 */
(*L).listsize += LISTINCREMENT; /* 增加存储容量 */
for (k = 1; k &= (*L). k++)
ListInsert(L, k, e); /* 函数在bo2-1.c中 */
void InsertDescend(SqList *L, ElemType e)
{ /* 初始条件：按非升序排列的顺序线性表L已存在 */
/* 操作结果：在L中按非升序插入新的数据元素e，L的长度加1 */
ElemType *newbase, *p;
if ((*L).length &= (*L).listsize) /* 当前存储空间已满,增加分配 */
newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase)
exit(OVERFLOW); /* 存储分配失败 */
(*L).elem = /* 新基址 */
(*L).listsize += LISTINCREMENT; /* 增加存储容量 */
for (k = 1; k &= (*L). k++)
ListInsert(L, k, e); /* 函数在bo2-1.c中 */
Status HeadInsert(SqList *L, ElemType e)
{ /* 初始条件：顺序线性表L已存在。操作结果：在L的头部插入新的数据元素e，L的长度加1 */
ElemType *p, *q, *
if ((*L).length &= (*L).listsize)
newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
(*L).elem =
(*L).listsize += LISTINCREMENT;
for (p = (*L).elem + (*L).length - 1; p &= --p)
*(p + 1) = *p;
(*L).length++;
return OK;
Status EndInsert(SqList *L, ElemType e)
{ /* 初始条件：顺序线性表L已存在。操作结果：在L的尾部插入新的数据元素e，L的长度加1 */
ElemType *q, *
if ((*L).length &= (*L).listsize) /* 当前存储空间已满,增加分配 */
newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase)
exit(OVERFLOW); /* 存储分配失败 */
(*L).elem = /* 新基址 */
(*L).listsize += LISTINCREMENT; /* 增加存储容量 */
q = (*L).elem + (*L). /* q为插入位置 */
(*L).length++;
return OK;
Status DeleteFirst(SqList *L, ElemType *e)
{ /* 初始条件：顺序线性表L已存在，且有不少于1个元素 */
/* 操作结果：删除L的第一个数据元素，并由e返回其值，L的长度减1 */
ElemType *p, *q;
if (ListEmpty(*L)) /* 空表无法删除 */
return ERROR;
p = (*L). /* p指向第一个元素 */
q = (*L).elem + (*L).length - 1; /* q指向最后一个元素 */
for (++p; p &= ++p)
*(p - 1) = *p; /* 从第2个元素起，所有元素向前移动一个位置 */
(*L).length--; /* 当前长度减1 */
return OK;
Status DeleteTail(SqList *L, ElemType *e)
{ /* 初始条件：顺序线性表L已存在，且有不少于1个元素 */
/* 操作结果：删除L的最后一个数据元素，并用e返回其值，L的长度减1 */
ElemType *p;
if (!(*L).length) /* 空表 */
return ERROR;
p = (*L).elem + (*L).length - 1; /* 最后一个数据元素的位置 */
*e = *p; /* 被删除元素的值赋给e */
(*L).length--; /* 表长减1 */
return OK;
Status DeleteElem(SqList *L, ElemType e)
{ /* 删除表中值为e的元素，并返回TRUE；如无此元素，则返回FALSE */
int i = 0,
while (i&(*L).length&&e != *((*L).elem + i))
if (i == (*L).length) /* 没找到 */
return FALSE;
for (j = j&(*L). j++)
*((*L).elem + j) = *((*L).elem + j + 1); /* 后面的元素依次前移 */
(*L).length--; /* 当前长度减1 */
return TRUE;
Status ReplaceElem(SqList L, int i, ElemType e)
{ /* 用e取代表L中第i个元素的值 */
if (i&1 || i&L.length) /* i值不合法 */
exit(ERROR);
*(L.elem + i - 1) =
return OK;
Status CreatAscend(SqList *L, int n)
{ /* 按非降序建立n个元素的线性表 */
InitList(L);
printf(&请输入%d个元素:\n&, n);
scanf(&%d&, &e);
ListInsert(L, 1, e); /* 在空表中插入第1个元素 */
for (i = 1; i&n; i++)
scanf(&%d&, &e);
for (j = 0; j&(*L). j++)
if (e &= *((*L).elem + j))
ListInsert(L, j + 1, e); /* 插于表中 */
return TRUE;
Status CreatDescend(SqList *L, int n)
{ /* 按非升序建立n个元素的线性表 */
InitList(L);
printf(&请输入%d个元素:\n&, n);
scanf(&%d&, &e);
ListInsert(L, 1, e); /* 在空表中插入第1个元素 */
for (i = 1; i&n; i++)
scanf(&%d&, &e);
for (j = 0; j&(*L). j++)
if (e &= *((*L).elem + j))
ListInsert(L, j + 1, e); /* 插于表中 */
return TRUE;
测试文件一
#include &arrList.h&
Status comp(ElemType c1, ElemType c2) /* 数据元素判定函数(平方关系) */
if (c1 == c2*c2)
return TRUE;
return FALSE;
void visit(ElemType *c) /* ListTraverse()调用的函数(类型要一致) */
printf(&%d &, *c);
void dbl(ElemType *c) /* ListTraverse()调用的另一函数(元素值加倍) */
void main()
ElemType e, e0;
i = InitList(&L);
printf(&初始化L后：L.elem=%u L.length=%d L.listsize=%d\n&, L.elem, L.length, L.listsize);
for (j = 1; j &= 5; j++)
i = ListInsert(&L, 1, j);
printf(&在L的表头依次插入1～5后：*L.elem=&);
for (j = 1; j &= 5; j++)
printf(&%d &, *(L.elem + j - 1));
printf(&\n&);
printf(&L.elem=%u L.length=%d L.listsize=%d\n&, L.elem, L.length, L.listsize);
i = ListEmpty(L);
printf(&L是否空：i=%d(1:是 0:否)\n&, i);
i = ClearList(&L);
printf(&清空L后：L.elem=%u L.length=%d L.listsize=%d\n&, L.elem, L.length, L.listsize);
i = ListEmpty(L);
printf(&L是否空：i=%d(1:是 0:否)\n&, i);
for (j = 1; j &= 10; j++)
ListInsert(&L, j, j);
printf(&在L的表尾依次插入1～10后：*L.elem=&);
for (j = 1; j &= 10; j++)
printf(&%d &, *(L.elem + j - 1));
printf(&\n&);
printf(&L.elem=%u L.length=%d L.listsize=%d\n&, L.elem, L.length, L.listsize);
ListInsert(&L, 1, 0);
printf(&在L的表头插入0后：*L.elem=&);
for (j = 1; j &= ListLength(L); j++) /* ListLength(L)为元素个数 */
printf(&%d &, *(L.elem + j - 1));
printf(&\n&);
printf(&L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变)\n&, L.elem, L.length, L.listsize);
GetElem(L, 5, &e);
printf(&第5个元素的值为：%d\n&, e);
for (j = 3; j &= 4; j++)
k = LocateElem(L, j, comp);
printf(&第%d个元素的值为%d的平方\n&, k, j);
printf(&没有值为%d的平方的元素\n&, j);
for (j = 1; j &= 2; j++) /* 测试头两个数据 */
GetElem(L, j, &e0); /* 把第j个数据赋给e0 */
i = PriorElem(L, e0, &e); /* 求e0的前驱 */
if (i == INFEASIBLE)
printf(&元素%d无前驱\n&, e0);
printf(&元素%d的前驱为：%d\n&, e0, e);
for (j = ListLength(L) - 1; j &= ListLength(L); j++) /* 最后两个数据 */
GetElem(L, j, &e0); /* 把第j个数据赋给e0 */
i = NextElem(L, e0, &e); /* 求e0的后继 */
if (i == INFEASIBLE)
printf(&元素%d无后继\n&, e0);
printf(&元素%d的后继为：%d\n&, e0, e);
k = ListLength(L); /* k为表长 */
for (j = k + 1; j &= j--)
i = ListDelete(&L, j, &e); /* 删除第j个数据 */
if (i == ERROR)
printf(&删除第%d个数据失败\n&, j);
printf(&删除的元素值为：%d\n&, e);
printf(&依次输出L的元素：&);
ListTraverse(L, visit); /* 依次对元素调用visit()，输出元素的值 */
printf(&L的元素值加倍后：&);
ListTraverse(L, dbl); /* 依次对元素调用dbl()，元素值乘2 */
ListTraverse(L, visit);
DestroyList(&L);
printf(&销毁L后：L.elem=%u L.length=%d L.listsize=%d\n&, L.elem, L.length, L.listsize);
测试文件二
#include &arrList.h&
void visit(ElemType *c) /* ListTraverse()调用的函数(类型要一致) */
printf(&%d &, *c);
void main()
ElemType d,
printf(&按非降序建立n个元素的线性表L,请输入元素个数n: &);
scanf(&%d&, &n);
CreatAscend(&L, n);
printf(&依次输出L的元素：&);
ListTraverse(L, visit);
InsertAscend(&L, 10); /* 按非降序插入元素10 */
printf(&按非降序插入元素10后，线性表L为：&);
ListTraverse(L, visit);
HeadInsert(&L, 12); /* 在L的头部插入12 */
EndInsert(&L, 9); /* 在L的尾部插入9 */
printf(&在L的头部插入12，尾部插入9后，线性表L为：&);
ListTraverse(L, visit);
printf(&请输入要删除的元素的值: &);
scanf(&%d&, &e);
i = DeleteElem(&L, e);
printf(&成功删除%d\n&, e);
printf(&不存在元素%d!\n&, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
printf(&请输入要取代的元素的序号 元素的新值: &);
scanf(&%d%d&, &n, &e);
ReplaceElem(L, n, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
DestroyList(&L);
printf(&销毁L后,按非升序重新建立n个元素的线性表L,请输入元素个数n(&2): &);
scanf(&%d&, &n);
CreatDescend(&L, n);
printf(&依次输出L的元素：&);
ListTraverse(L, visit);
InsertDescend(&L, 10); /* 按非升序插入元素10 */
printf(&按非升序插入元素10后，线性表L为：&);
ListTraverse(L, visit);
printf(&请输入要删除的元素的值: &);
scanf(&%d&, &e);
i = DeleteElem(&L, e);
printf(&成功删除%d\n&, e);
printf(&不存在元素%d!\n&, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
DeleteFirst(&L, &e);
DeleteTail(&L, &d);
printf(&删除表头元素%d和表尾元素%d后,线性表L为：\n&, e, d);
ListTraverse(L, visit);
}测试文件三
#include &arrList.h&
Status equal(ElemType c1, ElemType c2)
{ /* 判断是否相等的函数，Union()用到 */
if (c1 == c2)
return TRUE;
return FALSE;
void Union(SqList *La, SqList Lb) /* 算法2.1 */
{ /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */
int La_len, Lb_
La_len = ListLength(*La); /* 求线性表的长度 */
Lb_len = ListLength(Lb);
for (i = 1; i &= Lb_ i++)
GetElem(Lb, i, &e); /* 取Lb中第i个数据元素赋给e */
if (!LocateElem(*La, e, equal)) /* La中不存在和e相同的元素,则插入之 */
ListInsert(La, ++La_len, e);
void print(ElemType *c)
printf(&%d &, *c);
void main()
SqList La, Lb;
i = InitList(&La);
if (i == 1) /* 创建空表La成功 */
for (j = 1; j &= 5; j++) /* 在表La中插入5个元素 */
i = ListInsert(&La, j, j);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 也可不判断是否创建成功 */
for (j = 1; j &= 5; j++) /* 在表Lb中插入5个元素 */
i = ListInsert(&Lb, j, 2 * j);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
Union(&La, Lb);
printf(&new La= &); /* 输出新表La的内容 */
ListTraverse(La, print);
测试文件四
#include &arrList.h&
void MergeList(SqList La, SqList Lb, SqList *Lc) /* 算法2.2 */
{ /* 已知线性表La和Lb中的数据元素按值非递减排列。 */
/* 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列 */
int i = 1, j = 1, k = 0;
int La_len, Lb_
ElemType ai,
InitList(Lc); /* 创建空表Lc */
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while (i &= La_len&&j &= Lb_len) /* 表La和表Lb均非空 */
GetElem(La, i, &ai);
GetElem(Lb, j, &bj);
if (ai &= bj)
ListInsert(Lc, ++k, ai);
ListInsert(Lc, ++k, bj);
while (i &= La_len) /* 表La非空且表Lb空 */
GetElem(La, i++, &ai);
ListInsert(Lc, ++k, ai);
while (j &= Lb_len) /* 表Lb非空且表La空 */
GetElem(Lb, j++, &bj);
ListInsert(Lc, ++k, bj);
void print(ElemType *c)
printf(&%d &, *c);
void main()
SqList La, Lb, Lc;
int j, a[4] = { 3, 5, 8, 11 }, b[7] = { 2, 6, 8, 9, 11, 15, 20 };
InitList(&La); /* 创建空表La */
for (j = 1; j &= 4; j++) /* 在表La中插入4个元素 */
ListInsert(&La, j, a[j - 1]);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 创建空表Lb */
for (j = 1; j &= 7; j++) /* 在表Lb中插入7个元素 */
ListInsert(&Lb, j, b[j - 1]);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
MergeList(La, Lb, &Lc);
printf(&Lc= &); /* 输出表Lc的内容 */
ListTraverse(Lc, print);
测试文件五
#include &arrList.h&
void MergeList(SqList La, SqList Lb, SqList *Lc) /* 算法2.7 */
{ /* 已知顺序线性表La和Lb的元素按值非递减排列。 */
/* 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列 */
ElemType *pa, *pa_last, *pb, *pb_last, *
(*Lc).listsize = (*Lc).length = La.length + Lb./*不用InitList()创建空表Lc */
pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType));
if (!(*Lc).elem) /* 存储分配失败 */
exit(OVERFLOW);
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa &= pa_last&&pb &= pb_last) /* 表La和表Lb均非空 */
{ /* 归并 */
if (*pa &= *pb)
*pc++ = *pa++;
*pc++ = *pb++;
while (pa &= pa_last) /* 表La非空且表Lb空 */
*pc++ = *pa++; /* 插入La的剩余元素 */
while (pb &= pb_last) /* 表Lb非空且表La空 */
*pc++ = *pb++; /* 插入Lb的剩余元素 */
void print(ElemType *c)
printf(&%d &, *c);
void main()
SqList La, Lb, Lc;
InitList(&La); /* 创建空表La */
for (j = 1; j &= 5; j++) /* 在表La中插入5个元素 */
ListInsert(&La, j, j);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 创建空表Lb */
for (j = 1; j &= 5; j++) /* 在表Lb中插入5个元素 */
ListInsert(&Lb, j, 2 * j);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
MergeList(La, Lb, &Lc);
printf(&Lc= &); /* 输出表Lc的内容 */
ListTraverse(Lc, print);
测试文件六
#include &arrList.h&
int comp(ElemType c1, ElemType c2)
if (c1&c2)
else if (c1 == c2)
void MergeList(SqList La, SqList Lb, SqList *Lc)
{ /* 另一种合并线性表的方法（根据算法2.7下的要求修改算法2.7） */
*pa, *pa_last, *pb, *pb_last, *
(*Lc).listsize = La.length + Lb. /* 此句与算法2.7不同 */
pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType));
if (!(*Lc).elem)
exit(OVERFLOW);
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa &= pa_last&&pb &= pb_last) /* 表La和表Lb均非空 */
switch (comp(*pa, *pb)) /* 此句与算法2.7不同 */
1: *pc++ = *pa++;
case -1: *pc++ = *pb++;
while (pa &= pa_last) /* 表La非空且表Lb空 */
*pc++ = *pa++;
while (pb &= pb_last) /* 表Lb非空且表La空 */
*pc++ = *pb++;
(*Lc).length = pc - (*Lc). /* 加此句 */
void print(ElemType *c)
printf(&%d &, *c);
void main()
SqList La, Lb, Lc;
InitList(&La); /* 创建空表La */
for (j = 1; j &= 5; j++) /* 在表La中插入5个元素 */
ListInsert(&La, j, j);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 创建空表Lb */
for (j = 1; j &= 5; j++) /* 在表Lb中插入5个元素 */
ListInsert(&Lb, j, 2 * j);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
MergeList(La, Lb, &Lc);
printf(&Lc= &); /* 输出表Lc的内容 */
ListTraverse(Lc, print);
#include &stdio.h&
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */
#include&stdlib.h& /* atoi() */
#include&io.h& /* eof() */
#include&math.h& /* floor(),ceil(),abs() */
#include&process.h& /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int S /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int B /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int ElemT
struct LNode
struct LNode *
typedef struct LNode *LinkL /* 另一种定义LinkList的方法 */
Status InitList(LinkList *L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList L);
Status ListEmpty(LinkList L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType *e);
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e);
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e);
Status ListInsert(LinkList L, int i, ElemType e);
Status ListDelete(LinkList L, int i, ElemType *e);
Status ListTraverse(LinkList L, void(*vi)(ElemType));
void InsertAscend(LinkList L, ElemType e);
void InsertDescend(LinkList L, ElemType e);
Status HeadInsert(LinkList L, ElemType e);
Status EndInsert(LinkList L, ElemType e);
Status DeleteFirst(LinkList L, ElemType *e);
Status DeleteTail(LinkList L, ElemType *e);
Status DeleteElem(LinkList L, ElemType e);
Status ReplaceElem(LinkList L, int i, ElemType e);
Status CreatAscend(LinkList *L, int n);
Status CreatDescend(LinkList *L, int n);
Status GetFirstElem(LinkList L, ElemType *e);
#include &list.h&
Status InitList(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)-&next=NULL; /* 指针域为空 */
return OK;
Status DestroyList(LinkList *L)
{ /* 初始条件：线性表L已存在。操作结果：销毁线性表L */
return OK;
Status ClearList(LinkList L) /* 不改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LinkList p,q;
p=L-& /* p指向第一个结点 */
while(p) /* 没到表尾 */
L-&next=NULL; /* 头结点指针域为空 */
return OK;
Status ListEmpty(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L-&next) /* 非空 */
return FALSE;
return TRUE;
int ListLength(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
LinkList p=L-& /* p指向第一个结点 */
while(p) /* 没到表尾 */
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{ /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* j为计数器 */
LinkList p=L-& /* p指向第一个结点 */
while(p&&j&i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */
if(!p||j&i) /* 第i个元素不存在 */
return ERROR;
*e=p-& /* 取第i个元素 */
return OK;
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
若这样的数据元素不存在,则返回值为0 */
LinkList p=L-&
if(compare(p-&data,e)) /* 找到这样的数据元素 */
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
LinkList q,p=L-& /* p指向第一个结点 */
while(p-&next) /* p所指结点有后继 */
q=p-& /* q为p的后继 */
if(q-&data==cur_e)
*pre_e=p-&
return OK;
p=q; /* p向后移 */
return INFEASIBLE;
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */
LinkList p=L-& /* p指向第一个结点 */
while(p-&next) /* p所指结点有后继 */
if(p-&data==cur_e)
*next_e=p-&next-&
return OK;
return INFEASIBLE;
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
LinkList p=L,s;
while(p&&j&i-1) /* 寻找第i-1个结点 */
if(!p||j&i-1) /* i小于1或者大于表长 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s-&data=e; /* 插入L中 */
s-&next=p-&
p-&next=s;
return OK;
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */
{ /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */
LinkList p=L,q;
while(p-&next&&j&i-1) /* 寻找第i个结点,并令p指向其前趋 */
if(!p-&next||j&i-1) /* 删除位置不合理 */
return ERROR;
q=p-& /* 删除并释放结点 */
p-&next=q-&
return OK;
Status ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */
{ /* 初始条件：线性表L已存在 */
/* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p=L-&
vi(p-&data);
printf(&\n&);
return OK;
/* bo2-9.c 单链表线性表(存储结构由c2-2.h定义)的扩展操作(11个) */
void InsertAscend(LinkList L, ElemType e)
{ /* 初始条件：按非降序排列的线性表L已存在。操作结果：在L中按非降序插入新的数据元素e */
LinkList q = L, p = L-&
while (p&&e&p-&data)
q-&next = (LinkList)malloc(sizeof(struct LNode)); /* 插在q后 */
q-&next-&data =
q-&next-&next =
void InsertDescend(LinkList L, ElemType e)
{ /* 初始条件：按非升序排列的线性表L已存在。操作结果：在L中按非升序插入新的数据元素e */
LinkList q = L, p = L-&
while (p&&e&p-&data)
q-&next = (LinkList)malloc(sizeof(struct LNode)); /* 插在q后 */
q-&next-&data =
q-&next-&next =
Status HeadInsert(LinkList L, ElemType e)
{ /* 初始条件：线性表L已存在。操作结果：在L的头部插入新的数据元素e,作为链表的第一个元素 */
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s-&data = /* 给结点赋值 */
s-&next = L-& /* 插在表头 */
return OK;
Status EndInsert(LinkList L, ElemType e)
{ /* 初始条件：线性表L已存在。操作结果：在L的尾部插入新的数据元素e,作为链表的最后一个元素 */
LinkList p = L;
while (p-&next) /* 使p指向表尾元素 */
p-&next = (LinkList)malloc(sizeof(struct LNode)); /* 在表尾生成新结点 */
p-&next-&data = /* 给新结点赋值 */
p-&next-&next = NULL; /* 表尾 */
return OK;
Status DeleteFirst(LinkList L, ElemType *e)
{ /* 初始条件：线性表L已存在，且有不少于1个元素 */
/* 操作结果：删除L的第一个数据元素，并由e返回其值 */
LinkList p = L-&
L-&next = p-&
return OK;
return ERROR;
Status DeleteTail(LinkList L, ElemType *e)
{ /* 初始条件：线性表L已存在，且有不少于1个元素 */
/* 操作结果：删除L的最后一个数据元素，并用e返回其值 */
LinkList p = L, q = NULL;
if (!p-&next) /* 链表为空 */
return ERROR;
while (p-&next)
q-&next = NULL; /* 新尾结点的next域设为NULL */
return OK;
Status DeleteElem(LinkList L, ElemType e)
{ /* 删除表中值为e的元素，并返回TRUE；如无此元素，则返回FALSE */
LinkList p = L,
if (q&&q-&data == e)
p-&next = q-&
return TRUE;
return FALSE;
Status ReplaceElem(LinkList L, int i, ElemType e)
{ /* 用e取代表L中第i个元素的值 */
LinkList p = L;
int j = 0;
while (p-&next&&j&i)
if (j == i)
return OK;
else /* 表中不存在第i个元素 */
return ERROR;
Status CreatAscend(LinkList *L, int n)
{ /* 按非降序建立n个元素的线性表 */
LinkList p, q,
if (n &= 0)
return ERROR;
InitList(L);
printf(&请输入%d个元素:\n&, n);
s = (LinkList)malloc(sizeof(struct LNode)); /* 第一个结点 */
scanf(&%d&, &s-&data);
s-&next = NULL;
(*L)-&next =
for (j = 1; j&n; j++)
s = (LinkList)malloc(sizeof(struct LNode)); /* 其余结点 */
scanf(&%d&, &s-&data);
p = (*L)-&
while (p&&p-&data&s-&data) /* p没到表尾，且所指元素值小于新值 */
p = p-& /* 指针后移 */
s-&next = q-& /* 元素插在q的后面 */
return OK;
Status CreatDescend(LinkList *L, int n)
{ /* 按非升序建立n个元素的线性表 */
LinkList p, q,
if (n &= 0)
return ERROR;
InitList(L);
printf(&请输入%d个元素:\n&, n);
s = (LinkList)malloc(sizeof(struct LNode)); /* 第一个结点 */
scanf(&%d&, &s-&data);
s-&next = NULL;
(*L)-&next =
for (j = 1; j&n; j++)
s = (LinkList)malloc(sizeof(struct LNode)); /* 其余结点 */
scanf(&%d&, &s-&data);
p = (*L)-&
while (p&&p-&data&s-&data) /* p没到表尾，且所指元素值大于新值 */
p = p-& /* 指针后移 */
s-&next = q-& /* 元素插在q的后面 */
return OK;
Status GetFirstElem(LinkList L, ElemType *e)
{ /* 返回表头元素的值 */
LinkList p = L-&
if (!p) /* 空表 */
return ERROR;
else /* 非空表 */
return OK;
测试文件一
#include&list.h& /* 与main2-1.c不同 */
Status comp(ElemType c1,ElemType c2)
{ /* 数据元素判定函数(相等为TRUE,否则为FALSE) */
if(c1==c2)
return TRUE;
return FALSE;
void visit(ElemType c) /* 与main2-1.c不同 */
printf(&%d &,c);
void main() /* 除了几个输出语句外，主程和main2-1.c很像 */
LinkList L; /* 与main2-1.c不同 */
ElemType e,e0;
i=InitList(&L);
for(j=1;j&=5;j++)
i=ListInsert(L,1,j);
printf(&在L的表头依次插入1～5后：L=&);
ListTraverse(L,visit); /* 依次对元素调用visit()，输出元素的值 */
i=ListEmpty(L);
printf(&L是否空：i=%d(1:是 0:否)\n&,i);
i=ClearList(L);
printf(&清空L后：L=&);
ListTraverse(L,visit);
i=ListEmpty(L);
printf(&L是否空：i=%d(1:是 0:否)\n&,i);
for(j=1;j&=10;j++)
ListInsert(L,j,j);
printf(&在L的表尾依次插入1～10后：L=&);
ListTraverse(L,visit);
GetElem(L,5,&e);
printf(&第5个元素的值为：%d\n&,e);
for(j=0;j&=1;j++)
k=LocateElem(L,j,comp);
printf(&第%d个元素的值为%d\n&,k,j);
printf(&没有值为%d的元素\n&,j);
for(j=1;j&=2;j++) /* 测试头两个数据 */
GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
i=PriorElem(L,e0,&e); /* 求e0的前驱 */
if(i==INFEASIBLE)
printf(&元素%d无前驱\n&,e0);
printf(&元素%d的前驱为：%d\n&,e0,e);
for(j=ListLength(L)-1;j&=ListLength(L);j++)/*最后两个数据 */
GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
i=NextElem(L,e0,&e); /* 求e0的后继 */
if(i==INFEASIBLE)
printf(&元素%d无后继\n&,e0);
printf(&元素%d的后继为：%d\n&,e0,e);
k=ListLength(L); /* k为表长 */
for(j=k+1;j&=k;j--)
i=ListDelete(L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf(&删除第%d个数据失败\n&,j);
printf(&删除的元素为：%d\n&,e);
printf(&依次输出L的元素：&);
ListTraverse(L,visit);
DestroyList(&L);
printf(&销毁L后：L=%u\n&,L);
测试文件二
#include &list.h&
void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */
printf(&%d &, c);
void main()
LinkList L; /* 此句和main2-8.c不同 */
ElemType d,
printf(&按非降序建立n个元素的线性表L,请输入元素个数n: &);
scanf(&%d&, &n);
CreatAscend(&L, n);
printf(&依次输出L的元素：&);
ListTraverse(L, visit);
InsertAscend(L, 10); /* 按非降序插入元素10 */
printf(&按非降序插入元素10后，线性表L为：&);
ListTraverse(L, visit);
HeadInsert(L, 12); /* 在L的头部插入12 */
EndInsert(L, 9); /* 在L的尾部插入9 */
printf(&在L的头部插入12，尾部插入9后，线性表L为：&);
ListTraverse(L, visit);
i = GetFirstElem(L, &e); /* 此句加 */
printf(&第1个元素是: %d\n&, e); /* 此句加 */
printf(&请输入要删除的元素的值: &);
scanf(&%d&, &e);
i = DeleteElem(L, e);
printf(&成功删除%d!\n&, e);
printf(&不存在元素%d!\n&, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
printf(&请输入要取代的元素的序号 元素的新值: &);
scanf(&%d%d&, &n, &e);
ReplaceElem(L, n, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
DestroyList(&L);
printf(&销毁L后,按非升序重新建立n个元素的线性表L,请输入元素个数n(&2): &);
scanf(&%d&, &n);
CreatDescend(&L, n);
printf(&依次输出L的元素：&);
ListTraverse(L, visit);
InsertDescend(L, 10); /* 按非升序插入元素10 */
printf(&按非升序插入元素10后，线性表L为：&);
ListTraverse(L, visit);
printf(&请输入要删除的元素的值: &);
scanf(&%d&, &e);
i = DeleteElem(L, e);
printf(&成功删除%d!\n&, e);
printf(&不存在元素%d!\n&, e);
printf(&线性表L为：&);
ListTraverse(L, visit);
DeleteFirst(L, &e);
DeleteTail(L, &d);
printf(&删除表头元素%d和表尾元素%d后,线性表L为：&, e, d);
ListTraverse(L, visit);
测试文件三
#include &list.h&
void CreateList(LinkList *L, int n) /* 算法2.11 */
{ /* 逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L */
*L = (LinkList)malloc(sizeof(struct LNode));
(*L)-&next = NULL; /* 先建立一个带头结点的单链表 */
printf(&请输入%d个数据\n&, n);
for (i = i&0; --i)
p = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
scanf(&%d&, &p-&data); /* 输入元素值 */
p-&next = (*L)-& /* 插入到表头 */
(*L)-&next =
void CreateList2(LinkList *L, int n)
{ /* 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表 */
LinkList p = NULL, q = NULL;
*L = (LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */
(*L)-&next = NULL;
printf(&请输入%d个数据\n&, n);
for (i = 1; i &= i++)
p = (LinkList)malloc(sizeof(struct LNode));
scanf(&%d&, &p-&data);
p-&next = NULL;
void MergeList(LinkList La, LinkList *Lb, LinkList *Lc)/* 算法2.12 */
{ /* 已知单链线性表La和Lb的元素按值非递减排列。 */
/* 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列 */
LinkList pa = La-&next, pb = (*Lb)-&next,
*Lc = pc = La; /* 用La的头结点作为Lc的头结点 */
while (pa&&pb)
if (pa-&data &= pb-&data)
pc-&next =
pc-&next =
pc-&next = pa ? pa : /* 插入剩余段 */
free(*Lb); /* 释放Lb的头结点 */
Lb = NULL;
void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */
printf(&%d &, c);
void main()
int n = 5;
LinkList La, Lb, Lc;
printf(&按非递减顺序, &);
CreateList2(&La, n); /* 正位序输入n个元素的值 */
printf(&La=&); /* 输出链表La的内容 */
ListTraverse(La, visit);
printf(&按非递增顺序, &);
CreateList(&Lb, n); /* 逆位序输入n个元素的值 */
printf(&Lb=&); /* 输出链表Lb的内容 */
ListTraverse(Lb, visit);
MergeList(La, &Lb, &Lc); /* 按非递减顺序归并La和Lb,得到新表Lc */
printf(&Lc=&); /* 输出链表Lc的内容 */
ListTraverse(Lc, visit);
测试文件四
#include &list.h&
Status equal(ElemType c1, ElemType c2)
{ /* 判断是否相等的函数，Union()用到 */
if (c1 == c2)
return TRUE;
return FALSE;
void Union(LinkList La, LinkList Lb) /* 算法2.1,此句与algo2-1.c不同 */
{ /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */
int La_len, Lb_
La_len = ListLength(La); /* 求线性表的长度 */
Lb_len = ListLength(Lb);
for (i = 1; i &= Lb_ i++)
GetElem(Lb, i, &e); /* 取Lb中第i个数据元素赋给e */
if (!LocateElem(La, e, equal)) /* La中不存在和e相同的元素,则插入之 */
ListInsert(La, ++La_len, e);
void print(ElemType c)
printf(&%d &, c);
void main()
LinkList La, Lb; /* 此句与algo2-1.c不同(因为采用不同的结构) */
i = InitList(&La);
if (i == 1) /* 创建空表La成功 */
for (j = 1; j &= 5; j++) /* 在表La中插入5个元素 */
i = ListInsert(La, j, j);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 也可不判断是否创建成功 */
for (j = 1; j &= 5; j++) /* 在表Lb中插入5个元素 */
i = ListInsert(Lb, j, 2 * j);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
Union(La, Lb);
printf(&new La= &); /* 输出新表La的内容 */
ListTraverse(La, print);
测试程序五
#include &list.h&
void MergeList(LinkList La, LinkList Lb, LinkList *Lc) /* 算法2.2,此句与algo2-2.c不同 */
{ /* 已知线性表La和Lb中的数据元素按值非递减排列。 */
/* 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列 */
int i = 1, j = 1, k = 0;
int La_len, Lb_
ElemType ai,
InitList(Lc); /* 创建空表Lc */
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while (i &= La_len&&j &= Lb_len) /* 表La和表Lb均非空 */
GetElem(La, i, &ai);
GetElem(Lb, j, &bj);
if (ai &= bj)
ListInsert(*Lc, ++k, ai);
ListInsert(*Lc, ++k, bj);
while (i &= La_len) /* 表La非空且表Lb空 */
GetElem(La, i++, &ai);
ListInsert(*Lc, ++k, ai);
while (j &= Lb_len) /* 表Lb非空且表La空 */
GetElem(Lb, j++, &bj);
ListInsert(*Lc, ++k, bj);
void print(ElemType c)
printf(&%d &, c);
void main()
LinkList La, Lb, Lc; /* 此句与algo2-2.c不同 */
int j, a[4] = { 3, 5, 8, 11 }, b[7] = { 2, 6, 8, 9, 11, 15, 20 };
InitList(&La); /* 创建空表La */
for (j = 1; j &= 4; j++) /* 在表La中插入4个元素 */
ListInsert(La, j, a[j - 1]);
printf(&La= &); /* 输出表La的内容 */
ListTraverse(La, print);
InitList(&Lb); /* 创建空表Lb */
for (j = 1; j &= 7; j++) /* 在表Lb中插入7个元素 */
ListInsert(Lb, j, b[j - 1]);
printf(&Lb= &); /* 输出表Lb的内容 */
ListTraverse(Lb, print);
MergeList(La, Lb, &Lc);
printf(&Lc= &); /* 输出表Lc的内容 */
ListTraverse(Lc, print);
测试文件六
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */
#include&stdlib.h& /* atoi() */
#include&io.h& /* eof() */
#include&math.h& /* floor(),ceil(),abs() */
#include&process.h& /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int S /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int B /* Boolean是布尔类型,其值是TRUE或FALSE */
#define NAMELEN 8 /* 姓名最大长度 */
#define CLASSLEN 4 /* 班级名最大长度 */
struct stud /* 记录的结构 */
char name[NAMELEN + 1];
char Class[CLASSLEN + 1];
typedef struct stud ElemT /* 链表结点元素类型为结构体 */
struct LNode
struct LNode *
typedef struct LNode *LinkL /* 另一种定义LinkList的方法 */
char sta[3][9] = { &健康
&, &神经衰弱& }; /* 健康状况(3类) */
Status InitList(LinkList *L) /* 拷自bo2-2.c */
{ /* 操作结果：构造一个空的线性表L */
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if (!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)-&next = NULL; /* 指针域为空 */
return OK;
Status ListTraverse(LinkList L, void(*vi)(ElemType)) /* 拷自bo2-2.c */
{ /* 初始条件：线性表L已存在 */
/* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p = L-&
vi(p-&data);
printf(&\n&);
return OK;
void InsertAscend(LinkList L, ElemType e) /* 此函数是由bo2-9.c中的同名函数改写 */
{ /* 按学号非降序插入 */
LinkList q = L, p = L-&
while (p&&e.num&p-&data.num)
q-&next = (LinkList)malloc(sizeof(struct LNode)); /* 插在q后 */
q-&next-&data =
q-&next-&next =
void Print(struct stud e)
{ /* 显示记录e的内容 */
printf(&%-8s %6ld&, e.name, e.num);
if (e.sex == 'm')
printf(& 男&);
printf(& 女&);
printf(&%5d
%-4s&, e.age, e.Class);
printf(&%9s\n&, sta[e.health]);
void ReadIn(struct stud *e)
{ /* 由键盘输入结点信息 */
printf(&请输入姓名(&=%d个字符): &, NAMELEN);
scanf(&%s&, e-&name);
printf(&请输入学号: &);
scanf(&%ld&, &e-&num);
printf(&请输入性别(m:男 f:女): &);
scanf(&%*c%c&, &e-&sex);
printf(&请输入年龄: &);
scanf(&%d&, &e-&age);
printf(&请输入班级(&=%d个字符): &, CLASSLEN);
scanf(&%s&, e-&Class);
printf(&请输入健康状况(0:%s 1:%s 2:%s):&, sta[0], sta[1], sta[2]);
scanf(&%d&, &e-&health);
void WriteToFile(struct stud e)
{ /* 将结点信息写入fp指定的文件 */
fwrite(&e, sizeof(struct stud), 1, fp);
Status ReadFromFile(struct stud *e)
{ /* 由fp指定的文件读取结点信息到e */
i = fread(e, sizeof(struct stud), 1, fp);
if (i == 1) /* 读取文件成功 */
return OK;
return ERROR;
Status FindFromNum(LinkList L, long num, LinkList *p, LinkList *q)
{ /* 查找表中学号为num的结点,如找到,q指向此结点,p指向q的前驱, */
/* 并返回TRUE;如无此元素,则返回FALSE */
while (*p)
*q = (*p)-&
if (*q && (*q)-&data.num&num) /* 因为是按学号非降序排列 */
if (*q && (*q)-&data.num == num) /* 找到该学号 */
return TRUE;
return FALSE;
Status FindFromName(LinkList L, char name[], LinkList *p, LinkList *q)
{ /* 查找表中姓名为name的结点,如找到,q指向此结点,p指向q的前驱, */
/* 并返回TRUE;如无此元素,则返回FALSE */
while (*p)
*q = (*p)-&
if (*q&&!strcmp((*q)-&data.name, name)) /* 找到该姓名 */
return TRUE;
return FALSE;
Status DeleteElemNum(LinkList L, long num)
{ /* 删除表中学号为num的元素，并返回TRUE；如无此元素，则返回FALSE */
LinkList p,
if (FindFromNum(L, num, &p, &q)) /* 找到此结点,且q指向其,p指向其前驱 */
p-&next = q-&
return TRUE;
return FALSE;
Status DeleteElemName(LinkList L, char name[])
{ /* 删除表中姓名为name的元素，并返回TRUE；如无此元素，则返回FALSE */
LinkList p,
if (FindFromName(L, name, &p, &q)) /* 找到此结点,且q指向其,p指向其前驱 */
p-&next = q-&
return TRUE;
return FALSE;
void Modify(ElemType *e)
{ /* 修改结点内容 */
char s[80];
Print(*e); /* 显示原内容 */
printf(&请输入待修改项的内容，不修改的项按回车键保持原值:\n&);
printf(&请输入姓名(&=%d个字符): &, NAMELEN);
if (strlen(s))
strcpy(e-&name, s);
printf(&请输入学号: &);
if (strlen(s))
e-&num = atol(s);
printf(&请输入性别(m:男 f:女): &);
if (strlen(s))
e-&sex = s[0];
printf(&请输入年龄: &);
if (strlen(s))
e-&age = atoi(s);
printf(&请输入班级(&=%d个字符): &, CLASSLEN);
if (strlen(s))
strcpy(e-&Class, s);
printf(&请输入健康状况(0:%s 1:%s 2:%s):&, sta[0], sta[1], sta[2]);
if (strlen(s))
e-&health = atoi(s); /* 修改完毕 */
#define N 4 /* student记录的个数 */
void main()
struct stud student[N] = { { &王小林&, 790631, 'm', 18, &计91&, 0 },
{ &陈红&, 790632, 'f', 20, &计91&, 1 },
{ &刘建平&, 790633, 'm', 21, &计91&, 0 },
{ &张立立&, 790634, 'm', 17, &计91&, 2 } }; /* 表的初始记录 */
int i, j, flag = 1;
char filename[13], name[NAMELEN + 1];
LinkList T, p,
InitList(&T); /* 初始化链表 */
while (flag)
printf(&1:将结构体数组student中的记录按学号非降序插入链表\n&);
printf(&2:将文件中的记录按学号非降序插入链表\n&);
printf(&3:键盘输入新记录，并将其按学号非降序插入链表\n&);
printf(&4:删除链表中第一个有给定学号的记录\n&);
printf(&5:删除链表中第一个有给定姓名的记录\n&);
printf(&6:修改链表中第一个有给定学号的记录\n&);
printf(&7:修改链表中第一个有给定姓名的记录\n&);
printf(&8:查找链表中第一个有给定学号的记录\n&);
printf(&9:查找链表中第一个有给定姓名的记录\n&);
printf(&10:显示所有记录 11:将链表中的所有记录存入文件 12:结束\n&);
printf(&请选择操作命令: &);
scanf(&%d&, &i);
switch (i)
case 1: for (j = 0; j&N; j++)
InsertAscend(T, student[j]);
case 2: printf(&请输入文件名: &);
scanf(&%s&, filename);
if ((fp = fopen(filename, &rb&)) == NULL)
printf(&打开文件失败!\n&);
while (ReadFromFile(&e))
InsertAscend(T, e);
fclose(fp);
case 3: ReadIn(&e);
InsertAscend(T, e);
case 4: printf(&请输入待删除记录的学号: &);
scanf(&%ld&, &num);
if (!DeleteElemNum(T, num))
printf(&没有学号为%ld的记录\n&, num);
case 5: printf(&请输入待删除记录的姓名: &);
scanf(&%s&, name);
if (!DeleteElemName(T, name))
printf(&没有姓名为%s的记录\n&, name);
case 6: printf(&请输入待修改记录的学号: &);
scanf(&%ld%*c&, &num); /* %*c吃掉回车符 */
if (!FindFromNum(T, num, &p, &q))
printf(&没有学号为%ld的记录\n&, num);
Modify(&q-&data);
if (q-&data.num != num) /* 学号被修改 */
p-&next = q-& /* 把q所指的结点从L中删除 */
InsertAscend(T, q-&data); /* 把元素插入L */
free(q); /* 删除q */
case 7: printf(&请输入待修改记录的姓名: &);
scanf(&%s%*c&, name); /* %*c吃掉回车符 */
if (!FindFromName(T, name, &p, &q))
printf(&没有姓名为%s的记录\n&, name);
num = q-&data. /* 学号存入num */
Modify(&q-&data);
if (q-&data.num != num) /* 学号被修改 */
p-&next = q-& /* 把q所指的结点从L中删除 */
InsertAscend(T, q-&data); /* 把元素插入L */
free(q); /* 删除q */
case 8: printf(&请输入待查找记录的学号: &);
scanf(&%ld&, &num);
if (!FindFromNum(T, num, &p, &q))
printf(&没有学号为%ld的记录\n&, num);
Print(q-&data);
case 9: printf(&请输入待查找记录的姓名: &);
scanf(&%s&, name);
if (!FindFromName(T, name, &p, &q))
printf(&没有姓名为%s的记录\n&, name);
Print(q-&data);
case 10:printf(&
学号 性别 年龄 班级 健康状况\n&);
ListTraverse(T, Print);
case 11:printf(&请输入文件名: &);
scanf(&%s&, filename);
if ((fp = fopen(filename, &wb&)) == NULL)
printf(&打开文件失败!\n&);
ListTraverse(T, WriteToFile);
fclose(fp);
case 12:flag = 0;
3.另一种线性表
/* c1.h (程序名) */
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */
#include&stdlib.h& /* atoi() */
#include&io.h& /* eof() */
#include&math.h& /* floor(),ceil(),abs() */
#include&process.h& /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int S /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int B /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int ElemT
/* c2-6.h 抽象数据类型Polynomial的实现 */
//typedef struct /* 项的表示,多项式的项作为LinkList的数据元素 */
/* 系数 */
/* 指数 */
//}term, ElemT
/* 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名 */
/* c2-5.h 带头结点的线性链表类型 */
typedef struct LNode /* 结点类型 */
struct LNode *
}LNode, *Link, *P
typedef struct LinkList /* 链表类型 */
Link head, /* 分别指向线性链表中的头结点和最后一个结点 */
/* 指示线性链表中数据元素的个数 */
Status MakeNode(Link *p, ElemType e);
void FreeNode(Link *p);
Status InitList(LinkList *L);
Status ClearList(LinkList *L);
Status DestroyList(LinkList *L);
Status InsFirst(LinkList *L, Link h, Link s);
Status DelFirst(LinkList *L, Link h, Link *q);
Status Append(LinkList *L, Link s);
Position PriorPos(LinkList L, Link p);
Status Remove(LinkList *L, Link *q);
Status InsBefore(LinkList *L, Link *p, Link s);
Status InsAfter(LinkList *L, Link *p, Link s);
Status SetCurElem(Link p, ElemType e);
ElemType GetCurElem(Link p);
Status ListEmpty(LinkList L);
int ListLength(LinkList L);
Position GetHead(LinkList L);
Position GetLast(LinkList L);
Position NextPos(Link p);
Status LocatePos(LinkList L, int i, Link *p);
Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
Status ListTraverse(LinkList L, void(*visit)(ElemType));
Status OrderInsert(LinkList *L, ElemType e, int(*comp)(ElemType, ElemType));
Status LocateElemP(LinkList L, ElemType e, Position *q, int(*compare)(ElemType, ElemType));
#include &LinkList2.h&
/* bo2-6.c 具有实用意义的线性链表(存储结构由c2-5.h定义)的24个基本操作 */
Status MakeNode(Link *p, ElemType e)
{ /* 分配由p指向的值为e的结点，并返回OK；若分配失败。则返回ERROR */
*p = (Link)malloc(sizeof(LNode));
return ERROR;
(*p)-&data =
return OK;
void FreeNode(Link *p)
{ /* 释放p所指结点 */
*p = NULL;
Status InitList(LinkList *L)
{ /* 构造一个空的线性链表 */
p = (Link)malloc(sizeof(LNode)); /* 生成头结点 */
p-&next = NULL;
(*L).head = (*L).tail =
(*L).len = 0;
return OK;
return ERROR;
Status ClearList(LinkList *L)
{ /* 将线性链表L重置为空表，并释放原链表的结点空间 */
if ((*L).head != (*L).tail)/* 不是空表 */
p = q = (*L).head-&
(*L).head-&next = NULL;
while (p != (*L).tail)
(*L).tail = (*L).
(*L).len = 0;
return OK;
Status DestroyList(LinkList *L)
{ /* 销毁线性链表L，L不再存在 */
ClearList(L); /* 清空链表 */
FreeNode(&(*L).head);
(*L).tail = NULL;
(*L).len = 0;
return OK;
Status InsFirst(LinkList *L, Link h, Link s) /* 形参增加L,因为需修改L */
{ /* h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 */
s-&next = h-&
if (h == (*L).tail) /* h指向尾结点 */
(*L).tail = h-& /* 修改尾指针 */
(*L).len++;
return OK;
Status DelFirst(LinkList *L, Link h, Link *q) /* 形参增加L,因为需修改L */
{ /* h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。 */
/* 若链表为空(h指向尾结点)，q=NULL，返回FALSE */
if (*q) /* 链表非空 */
h-&next = (*q)-&
if (!h-&next) /* 删除尾结点 */
(*L).tail = /* 修改尾指针 */
(*L).len--;
return OK;
return FALSE; /* 链表空 */
Status Append(LinkList *L, Link s)
{ /* 将指针s(s-&data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的 */
/* 一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新 */
/* 的尾结点 */
int i = 1;
(*L).tail-&next =
while (s-&next)
(*L).tail =
(*L).len +=
return OK;
Position PriorPos(LinkList L, Link p)
{ /* 已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置 */
/* 若无前驱，则返回NULL */
q = L.head-&
if (q == p) /* 无前驱 */
return NULL;
while (q-&next != p) /* q不是p的直接前驱 */
Status Remove(LinkList *L, Link *q)
{ /* 删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点 */
Link p = (*L).
if ((*L).len == 0) /* 空表 */
*q = NULL;
return FALSE;
while (p-&next != (*L).tail)
*q = (*L).
p-&next = NULL;
(*L).tail =
(*L).len--;
return OK;
Status InsBefore(LinkList *L, Link *p, Link s)
{ /* 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前， */
/* 并修改指针p指向新插入的结点 */
q = PriorPos(*L, *p); /* q是p的前驱 */
if (!q) /* p无前驱 */
s-&next = *p;
(*L).len++;
return OK;
Status InsAfter(LinkList *L, Link *p, Link s)
{ /* 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后， */
/* 并修改指针p指向新插入的结点 */
if (*p == (*L).tail) /* 修改尾指针 */
(*L).tail =
s-&next = (*p)-&
(*p)-&next =
(*L).len++;
return OK;
Status SetCurElem(Link p, ElemType e)
{ /* 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 */
return OK;
ElemType GetCurElem(Link p)
{ /* 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 */
return p-&
Status ListEmpty(LinkList L)
{ /* 若线性链表L为空表，则返回TRUE，否则返回FALSE */
if (L.len)
return FALSE;
return TRUE;
int ListLength(LinkList L)
{ /* 返回线性链表L中元素个数 */
Position GetHead(LinkList L)
{ /* 返回线性链表L中头结点的位置 */
Position GetLast(LinkList L)
{ /* 返回线性链表L中最后一个结点的位置 */
Position NextPos(Link p)
{ /* 已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置 */
/* 若无后继，则返回NULL */
return p-&
Status LocatePos(LinkList L, int i, Link *p)
{ /* 返回p指示线性链表L中第i个结点的位置，并返回OK，i值不合法时返回ERROR */
/* i=0为头结点 */
if (i&0 || i&L.len)
return ERROR;
for (j = 1; j &= j++)
*p = (*p)-&
return OK;
Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ /* 返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置， */
/* 若不存在这样的元素，则返回NULL */
Link p = L.
while (p&&!(compare(p-&data, e))); /* 没到表尾且没找到满足关系的元素 */
Status ListTraverse(LinkList L, void(*visit)(ElemType))
{ /* 依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 */
Link p = L.head-&
for (j = 1; j &= L. j++)
visit(p-&data);
printf(&\n&);
return OK;
Status OrderInsert(LinkList *L, ElemType e, int(*comp)(ElemType, ElemType))
{ /* 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式） */
Link o, p,
while (p != NULL&&comp(p-&data, e)&0) /* p不是表尾且元素值小于e */
o = (Link)malloc(sizeof(LNode)); /* 生成结点 */
o-&data = /* 赋值 */
q-&next = /* 插入 */
(*L).len++; /* 表长加1 */
if (!p) /* 插在表尾 */
(*L).tail = /* 修改尾结点 */
return OK;
Status LocateElemP(LinkList L, ElemType e, Position *q, int(*compare)(ElemType, ElemType))
{ /* 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中 */
/* 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数 */
/* compare()取值&0的元素的前驱的位置。并返回FALSE。（用于一元多项式） */
Link p = L.head,
} while (p && (compare(p-&data, e)&0)); /* 没到表尾且p-&data.expn&e.expn */
if (!p || compare(p-&data, e)&0) /* 到表尾或compare(p-&data,e)&0 */
return FALSE;
else /* 找到 */
return TRUE;
测试文件一
#include &LinkList2.h&
Status compare(ElemType c1, ElemType c2) /* c1等于c2 */
if (c1 == c2)
return TRUE;
return FALSE;
int cmp(ElemType a, ElemType b)
{ /* 根据a&、=或&b,分别返回-1、0或1 */
if (a == b)
return (a - b) / abs(a - b);
void visit(ElemType c)
printf(&%d &, c);
void main()
LinkList L;
i = InitList(&L);
if (!i) /* 初始化空的线性表L不成功 */
exit(FALSE); /* 退出程序运行 */
for (j = 1; j &= 2; j++)
MakeNode(&p, j); /* 生成由p指向、值为j的结点 */
InsFirst(&L, L.tail, p); /* 插在表尾 */
OrderInsert(&L, 0, cmp); /* 按升序插在有序表头 */
for (j = 0; j &= 3; j++)
i = LocateElemP(L, j, &p, cmp);
printf(&链表中有值为%d的元素。\n&, p-&data);
printf(&链表中没有值为%d的元素。\n&, j);
printf(&输出链表：&);
ListTraverse(L, visit); /* 输出L */
for (j = 1; j &= 4; j++)
printf(&删除表头结点：&);
DelFirst(&L, L.head, &p); /* 删除L的首结点，并以p返回 */
printf(&%d\n&, GetCurElem(p));
printf(&表空，无法删除 p=%u\n&, p);
printf(&L中结点个数=%d L是否空 %d(1:空 0:否)\n&, ListLength(L), ListEmpty(L));
MakeNode(&p, 10);
p-&next = NULL; /* 尾结点 */
for (j = 4; j &= 1; j--)
MakeNode(&h, j * 2);
} /* h指向一串5个结点，其值依次是2 4 6 8 10 */
Append(&L, h); /* 把结点h链接在线性链表L的最后一个结点之后 */
OrderInsert(&L, 12, cmp); /* 按升序插在有序表尾头 */
OrderInsert(&L, 7, cmp); /* 按升序插在有序表中间 */
printf(&输出链表：&);
ListTraverse(L, visit); /* 输出L */
for (j = 1; j &= 2; j++)
p = LocateElem(L, j * 5, compare);
printf(&L中存在值为%d的结点。\n&, j * 5);
printf(&L中不存在值为%d的结点。\n&, j * 5);
for (j = 1; j &= 2; j++)
LocatePos(L, j, &p); /* p指向L的第j个结点 */
h = PriorPos(L, p); /* h指向p的前驱 */
printf(&%d的前驱是%d。\n&, p-&data, h-&data);
printf(&%d没前驱。\n&, p-&data);
k = ListLength(L);
for (j = k - 1; j &= j++)
LocatePos(L, j, &p); /* p指向L的第j个结点 */
h = NextPos(p); /* h指向p的后继 */
printf(&%d的后继是%d。\n&, p-&data, h-&data);
printf(&%d没后继。\n&, p-&data);
printf(&L中结点个数=%d L是否空 %d(1:空 0:否)\n&, ListLength(L), ListEmpty(L));
p = GetLast(L); /* p指向最后一个结点 */
SetCurElem(p, 15); /* 将最后一个结点的值变为15 */
printf(&第1个元素为%d 最后1个元素为%d\n&, GetCurElem(GetHead(L)-&next), GetCurElem(p));
MakeNode(&h, 10);
InsBefore(&L, &p, h); /* 将10插到尾结点之前，p指向新结点 */
p = p-& /* p恢复为尾结点 */
MakeNode(&h, 20);
InsAfter(&L, &p, h); /* 将20插到尾结点之后 */
k = ListLength(L);
printf(&依次删除表尾结点并输出其值：&);
for (j = 0; j &= j++)
i = Remove(&L, &p);
if (!i) /* 删除不成功 */
printf(&删除不成功 p=%u\n&, p);
printf(&%d &, p-&data);
MakeNode(&p, 29); /* 重建具有1个结点(29)的链表 */
InsFirst(&L, L.head, p);
DestroyList(&L); /* 销毁线性链表L */
printf(&销毁线性链表L之后: L.head=%u L.tail=%u L.len=%d\n&, L.head, L.tail, L.len);
测试文件二
#include &LinkList2.h&
typedef LinkL
#define DestroyPolyn DestroyList /* 与bo2-6.cpp中的函数同义不同名 */
#define PolynLength ListLength /* 与bo2-6.cpp中的函数同义不同名 */
Status OrderInsertMerge(LinkList *L, ElemType e, int(*compare)(term, term))
{ /* 按有序判定函数compare()的约定，将值为e的结点插入或合并到升序链表L的适当位置 */
Position q,
if (LocateElemP(*L, e, &q, compare)) /* L中存在该指数项 */
q-&data.coef += e. /* 改变当前结点系数的值 */
if (!q-&data.coef) /* 系数为0 */
{ /* 删除多项式L中当前结点 */
s = PriorPos(*L, q); /* s为当前结点的前驱 */
if (!s) /* q无前驱 */
DelFirst(L, s, &q);
FreeNode(&q);
return OK;
else /* 生成该指数项并插入链表 */
if (MakeNode(&s, e)) /* 生成结点成功 */
InsFirst(L, q, s);
return OK;
else /* 生成结点失败 */
return ERROR;
int cmp(term a, term b) /* CreatPolyn()的实参 */
{ /* 依a的指数值&、=或&b的指数值，分别返回-1、0或+1 */
if (a.expn == b.expn)
return (a.expn - b.expn) / abs(a.expn - b.expn);
void CreatPolyn(polynomial *P, int m) /* 算法2.22 */
{ /* 输入m项的系数和指数，建立表示一元多项式的有序链表P */
Position q,
InitList(P);
printf(&请依次输入%d个系数，指数：\n&, m);
for (i = 1; i &= ++i)
{ /* 依次输入m个非零项（可按任意顺序） */
scanf(&%f,%d&, &e.coef, &e.expn);
if (!LocateElemP(*P, e, &q, cmp)) /* 当前链表中不存在该指数项,cmp是实参 */
if (MakeNode(&s, e)) /* 生成结点并插入链表 */
InsFirst(P, q, s);
void PrintPolyn(polynomial P)
{ /* 打印输出一元多项式P */
q = P.head-& /* q指向第一个结点 */
printf(&%f
%d\n&, q-&data.coef, q-&data.expn);
void AddPolyn(polynomial *Pa, polynomial *Pb) /* 算法2.23 */
{ /* 多项式加法:Pa=Pa+Pb,并销毁一元多项式Pb */
Position ha, hb, qa,
ha = GetHead(*Pa);
hb = GetHead(*Pb); /* ha和hb分别指向Pa和Pb的头结点 */
qa = NextPos(ha);
qb = NextPos(hb); /* qa和qb分别指向Pa和Pb中当前结点（现为第一个结点） */
while (!ListEmpty(*Pa) && !ListEmpty(*Pb) && qa)
{ /* Pa和Pb均非空且ha没指向尾结点(qa!=0) */
a = GetCurElem(qa);
b = GetCurElem(qb); /* a和b为两表中当前比较元素 */
switch (cmp(a, b))
case -1:ha = /* 多项式Pa中当前结点的指数值小 */
qa = NextPos(ha); /* ha和qa均向后移一个结点 */
case 0: qa-&data.coef += qb-&data.
/* 两者的指数值相等,修改Pa当前结点的系数值 */
if (qa-&data.coef == 0) /* 删除多项式Pa中当前结点 */
DelFirst(Pa, ha, &qa);
FreeNode(&qa);
DelFirst(Pb, hb, &qb);
FreeNode(&qb);
qb = NextPos(hb);
qa = NextPos(ha);
case 1: DelFirst(Pb, hb, &qb); /* 多项式Pb中当前结点的指数值小 */
InsFirst(Pa, ha, qb);
qb = NextPos(hb);
if (!ListEmpty(*Pb))
(*Pb).tail =
Append(Pa, qb); /* 链接Pb中剩余结点 */
DestroyPolyn(Pb); /* 销毁Pb */
void AddPolyn1(polynomial *Pa, polynomial *Pb)
{ /* 另一种多项式加法的算法:Pa=Pa+Pb,并销毁一元多项式Pb */
qb = GetHead(*Pb); /* qb指向Pb的头结点 */
qb = qb-& /* qb指向Pb的第一个结点 */
while (qb)
b = GetCurElem(qb);
OrderInsertMerge(Pa, b, cmp);
DestroyPolyn(Pb); /* 销毁Pb */
void Opposite(polynomial Pa)
{ /* 一元多项式系数取反 */
while (p-&next)
p-&data.coef *= -1;
void SubtractPolyn(polynomial *Pa, polynomial *Pb)
{ /* 多项式减法:Pa=Pa-Pb,并销毁一元多项式Pb */
Opposite(*Pb);
AddPolyn(Pa, Pb);
void MultiplyPolyn(polynomial *Pa, polynomial *Pb)
{ /* 多项式乘法:Pa=PaPb,并销毁一元多项式Pb */
polynomial Pc;
Position qa,
term a, b,
InitList(&Pc);
qa = GetHead(*Pa);
while (qa)
a = GetCurElem(qa);
qb = GetHead(*Pb);
while (qb)
b = GetCurElem(qb);
c.coef = a.coef*b.
c.expn = a.expn + b.
OrderInsertMerge(&Pc, c, cmp);
DestroyPolyn(Pb); /* 销毁Pb */
ClearList(Pa); /* 将Pa重置为空表 */
(*Pa).head = Pc.
(*Pa).tail = Pc.
(*Pa).len = Pc.
void main()
polynomial p,
printf(&请输入第一个一元多项式的非零项的个数：&);
scanf(&%d&, &m);
CreatPolyn(&p, m);
printf(&请输入第二个一元多项式的非零项的个数：&);
scanf(&%d&, &m);
CreatPolyn(&q, m);
AddPolyn(&p, &q);
printf(&两个一元多项式相加的结果：\n&);
PrintPolyn(p);
printf(&请输入第三个一元多项式的非零项的个数：&);
scanf(&%d&, &m);
CreatPolyn(&q, m);
AddPolyn1(&p, &q);
printf(&两个一元多项式相加的结果(另一种方法)：\n&);
PrintPolyn(p);
printf(&请输入第四个一元多项式的非零项的个数：&);
scanf(&%d&, &m);
CreatPolyn(&q, m);
SubtractPolyn(&p, &q);
printf(&两个一元多项式相减的结果：\n&);
PrintPolyn(p);
printf(&请输入第五个一元多项式的非零项的个数：&);
scanf(&%d&, &m);
CreatPolyn(&q, m);
MultiplyPolyn(&p, &q);
printf(&两个一元多项式相乘的结果：\n&);
PrintPolyn(p);
DestroyPolyn(&p);
测试文件三
#include &LinkList2.h&
Status ListInsert_L(LinkList *L, int i, ElemType e) /* 算法2.20 */
{ /* 在带头结点的单链线性表L的第i个元素之前插入元素e */
if (!LocatePos(*L, i - 1, &h))
return ERROR; /* i值不合法 */
if (!MakeNode(&s, e))
return ERROR; /* 结点分配失败 */
InsFirst(L, h, s); /*对于从第i个结点开始的链表,第i-1个结点是它的头结点 */
return OK;
Status MergeList_L(LinkList La, LinkList Lb, LinkList *Lc, int(*compare)(ElemType, ElemType))
{ /* 已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链 */
/* 线性表Lc，Lc的元素也按值非递减排列。（不改变La、Lb）算法2.21 */
Link ha, hb, pa, pb,
ElemType a,
if (!InitList(Lc))
return ERROR; /* 存储空间分配失败 */
ha = GetHead(La); /* ha和hb分别指向La和Lb的头结点 */
hb = GetHead(Lb);
pa = NextPos(ha); /* pa和pb分别指向La和Lb的第一个结点 */
pb = NextPos(hb);
while (!ListEmpty(La) && !ListEmpty(Lb)) /* La和Lb均非空 */
a = GetCurElem(pa); /* a和b为两表中当前比较元素 */
b = GetCurElem(pb);
if (compare(a, b) &= 0)
DelFirst(&La, ha, &q);
InsFirst(Lc, (*Lc).tail, q);
pa = NextPos(ha);
else /* a&b */
DelFirst(&Lb, hb, &q);
InsFirst(Lc, (*Lc).tail, q);
pb = NextPos(hb);
if (!ListEmpty(La))
Append(Lc, pa);
Append(Lc, pb);
FreeNode(&ha);
FreeNode(&hb);
return OK;
int comp(ElemType c1, ElemType c2)
return c1 - c2;
void visit(ElemType c)
printf(&%d &, c); /* 整型 */
void main()
LinkList La, Lb, Lc;
InitList(&La);
for (j = 1; j &= 5; j++)
ListInsert_L(&La, j, j); /* 顺序插入 1 2 3 4 5 */
printf(&La=&);
ListTraverse(La, visit);
InitList(&Lb);
for (j = 1; j &= 5; j++)
ListInsert_L(&Lb, j, 2 * j); /* 顺序插入 2 4 6 8 10 */
printf(&Lb=&);
ListTraverse(Lb, visit);
InitList(&Lc);
MergeList_L(La, Lb, &Lc, comp); /* 归并La和Lb，产生Lc */
printf(&Lc=&);
ListTraverse(Lc, visit);
DestroyList(&Lc);
4.设头尾指针的循环单链表
#include &stdio.h&
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */
#include&stdlib.h& /* atoi() */
#include&io.h& /* eof() */
#include&math.h& /* floor(),ceil(),abs() */
#include&process.h& /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int S /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int B /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int ElemT
struct LNode
struct LNode *
typedef struct LNode *LinkL /* 另一种定义LinkList的方法 */
Status InitList_CL(LinkList *L);
Status DestroyList_CL(LinkList *L);
Status ClearList_CL(LinkList *L);
Status ListEmpty_CL(LinkList L);
int ListLength_CL(LinkList L);
Status GetElem_CL(LinkList L, int i, ElemType *e);
int LocateElem_CL(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
Status PriorElem_CL(LinkList L, ElemType cur_e, ElemType *pre_e);
Status NextElem_CL(LinkList L, ElemType cur_e, ElemType *next_e);
Status ListInsert_CL(LinkList *L, int i, ElemType e);
Status ListDelete_CL(LinkList *L, int i, ElemType *e);
Status ListTraverse_CL(LinkList L, void(*vi)(ElemType));
#include &cirList.h&
Status InitList_CL(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if (!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)-&next = *L; /* 指针域指向头结点 */
return OK;
Status DestroyList_CL(LinkList *L)
{ /* 操作结果：销毁线性表L */
LinkList q, p = (*L)-& /* p指向第一个（非头结点）结点 */
while (p != *L) /* 没到表尾 */
*L = NULL;
return OK;
Status ClearList_CL(LinkList *L) /* 改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LinkList p,
*L = (*L)-& /* L指向头结点 */
p = (*L)-& /* p指向第一个结点 */
while (p != *L) /* 没到表尾 */
(*L)-&next = *L; /* 头结点指针域指向自身 */
return OK;
Status ListEmpty_CL(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if (L-&next == L) /* 空 */
return TRUE;
return FALSE;
int ListLength_CL(LinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i = 0;
LinkList p = L-& /* p指向头结点 */
while (p != L) /* 没到表尾 */
Status GetElem_CL(LinkList L, int i, ElemType *e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j = 1; /* 初始化,j为计数器 */
LinkList p = L-&next-& /* p指向第一个结点 */
if (i &= 0 || i&ListLength_CL(L)) /* 第i个元素不存在 */
return ERROR;
while (j&i)
{ /* 顺指针向后查找,直到p指向第i个元素 */
*e = p-& /* 取第i个元素 */
return OK;
int LocateElem_CL(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ /* 初始条件：线性表L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
若这样的数据元素不存在，则返回值为0 */
int i = 0;
LinkList p = L-&next-& /* p指向第一个结点 */
while (p != L-&next)
if (compare(p-&data, e)) /* 满足关系 */
Status PriorElem_CL(LinkList L, ElemType cur_e, ElemType *pre_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
否则操作失败，pre_e无定义 */
LinkList q, p = L-&next-& /* p指向第一个结点 */
while (q != L-&next) /* p没到表尾 */
if (q-&data == cur_e)
*pre_e = p-&
return TRUE;
return FALSE;
Status NextElem_CL(LinkList L, ElemType cur_e, ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继， */
否则操作失败，next_e无定义 */
LinkList p = L-&next-& /* p指向第一个结点 */
while (p != L) /* p没到表尾 */
if (p-&data == cur_e)
*next_e = p-&next-&
return TRUE;
return FALSE;
Status ListInsert_CL(LinkList *L, int i, ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
LinkList p = (*L)-&next, /* p指向头结点 */
int j = 0;
if (i &= 0 || i&ListLength_CL(*L) + 1) /* 无法在第i个元素之前插入 */
return ERROR;
while (j&i - 1) /* 寻找第i-1个结点 */
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s-&data = /* 插入L中 */
s-&next = p-&
if (p == *L) /* 改变尾结点 */
return OK;
Status ListDelete_CL(LinkList *L, int i, ElemType *e) /* 改变L */
{ /* 删除L的第i个元素,并由e返回其值 */
LinkList p = (*L)-&next, /* p指向头结点 */
int j = 0;
if (i &= 0 || i&ListLength_CL(*L)) /* 第i个元素不存在 */
return ERROR;
while (j&i - 1) /* 寻找第i-1个结点 */
q = p-& /* q指向待删除结点 */
p-&next = q-&
if (*L == q) /* 删除的是表尾元素 */
free(q); /* 释放待删除结点 */
return OK;
Status ListTraverse_CL(LinkList L, void(*vi)(ElemType))
{ /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p = L-&next-&
while (p != L-&next)
vi(p-&data);
printf(&\n&);
return OK;
测试文件一
#include &cirList.h&
Status compare(ElemType c1, ElemType c2)
if (c1 == c2)
return TRUE;
return FALSE;
void visit(ElemType c)
printf(&%d &, c);
void main()
LinkList L;
i = InitList_CL(&L); /* 初始化单循环链表L */
printf(&初始化单循环链表L i=%d (1:初始化成功)\n&, i);
i = ListEmpty_CL(L);
printf(&L是否空 i=%d(1:空 0:否)\n&, i);
ListInsert_CL(&L, 1, 3); /* 在L中依次插入3,5 */
ListInsert_CL(&L, 2, 5);
i = GetElem_CL(L, 1, &e);
j = ListLength_CL(L);
printf(&L中数据元素个数=%d,第1个元素的值为%d。\n&, j, e);
printf(&L中的数据元素依次为：&);
ListTraverse_CL(L, visit);
PriorElem_CL(L, 5, &e); /* 求元素5的前驱 */
printf(&5前面的元素的值为%d。\n&, e);
NextElem_CL(L, 3, &e); /* 求元素3的后继 */
printf(&3后面的元素的值为%d。\n&, e);
printf(&L是否空 %d(1:空 0:否)\n&, ListEmpty_CL(L));
j = LocateElem_CL(L, 5, compare);
printf(&L的第%d个元素为5。\n&, j);
printf(&不存在值为5的元素\n&);
i = ListDelete_CL(&L, 2, &e);
printf(&删除L的第2个元素：\n&);
printf(&删除的元素值为%d,现在L中的数据元素依次为：&, e);
ListTraverse_CL(L, visit);
printf(&删除不成功！\n&);
printf(&清空L：%d(1: 成功)\n&, ClearList_CL(&L));
printf(&清空L后，L是否空：%d(1:空 0:否)\n&, ListEmpty_CL(L));
printf(&销毁L：%d(1: 成功)\n&, DestroyList_CL(&L));
测试文件二
#include &cirList.h&
void MergeList_CL(LinkList *La, LinkList Lb)
LinkList p = Lb-&
Lb-&next = (*La)-&
(*La)-&next = p-&
void visit(ElemType c)
printf(&%d &, c);
void main()
int n = 5,
LinkList La, Lb;
InitList_CL(&La);
for (i = 1; i &= i++)
ListInsert_CL(&La, i, i);
printf(&La=&); /* 输出链表La的内容 */
ListTraverse_CL(La, visit);
InitList_CL(&Lb);
for (i = 1; i &= i++)
ListInsert_CL(&Lb, 1, i * 2);
printf(&Lb=&); /* 输出链表Lb的内容 */
ListTraverse_CL(Lb, visit);
MergeList_CL(&La, Lb);
printf(&La+Lb=&); /* 输出合并后的链表的内容 */
ListTraverse_CL(La, visit);
5.双向循环链表
头文件/* c1.h (程序名) */
#include&string.h&
#include&ctype.h&
#include&malloc.h& /* malloc()等 */
#include&limits.h& /* INT_MAX等 */
#include&stdio.h& /* EOF(=^Z或F6),NULL */