数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！/*
数据结构C语言版 线性表的动态分配顺序存储结构表示和实现
P22-26
编译环境：Dev-C++ 4.9.9.2 日期：2011年2月9日
*/
#include
#include
#include
typedef int ElemType;
// 定义数据结构元素的数据类型
// 线性表存储空间的初始分配量
// 线性表存储空间的分配增量 #define LIST_INIT_SIZE 10 #define LISTINCREMENT 5
// 线性表的动态分配顺序存储结构
typedef struct
{
ElemType *elem; // 存储空间基址
int length;
int listsize;
}SqList;
// 算法2.3，P23
// 构造一个空的顺序线性表即对顺序表结构体中的所有元素
// 进行初始化。
int InitList(SqList *L)
{
// 分配指定大小的存储空间给顺序表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if( !(*L).elem ) // 存储分配失败 exit(0); (*L).length = 0; // 当前长度初始化为0 // 指定分配的存储容量 (*L).listsize = LIST_INIT_SIZE; return 1; // 当前长度 // 当前分配的存储容量(以sizeof(ElemType)为单位)
}
// 销毁顺序线性表L即将顺序表结构体中的所有成员销毁（空间释放，
// 数值置0）。
int DestroyList(SqList *L)
{
// 先释放空间，然后置空
free( (*L).elem );
}
// 将L重置为空表（当前长度为0即是空表）。
int ClearList(SqList *L)
{
}
/*
若L为空表，则返回1，否则返回0。
如何判断是否为空表呢？结构体中已经包含一个可以说明的元素，
那就是length，表示当前顺序表的长度，根据当前的长度就可以
判断了，为0就是空表，不为0就不是空表了。
*/
int ListEmpty(SqList L)
{
if(0 == L.length)
return 1; else
return 0; (*L).length = 0; return 1; (*L).elem = NULL; (*L).length = 0; (*L).listsize = 0; return 1;
}
// 返回L中数据元素个数。
int ListLength(SqList L)
{
// L.length刚好记录了当前顺序表的长度，直接返回
return L.length;
}
// 用e返回L中第i个数据元素的值，第i个数据元素就是L.elem[i-1]。 int GetElem(SqList L,int i,ElemType *e)
{
// 首先进行异常处理 if(i L.length) exit(0); /* 注意顺序表基址L.elem[0] 表示第一个数，而第i个数则是用 */ *e = *(L.elem + i - 1); // *e = L.elem[i-1]; return 1; 基址L.elem + i - 1来表示,也可以用L.elem[i-1]表示。为什么 可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指 示了一个首地址，然后对地址进行加减，形成不同元素的地址。 *是取地址所指的内容，所以*(L.elem+i-1)就是第i个数据的值了。
}
/* 算法2.6，P26
返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0。
*/
int LocateElem(SqList L,ElemType e,
int(* compare)( ElemType, ElemType))
{
}
#if 0
/* 算法2.7 与算法2.2区别
已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序 线性表Lc,Lc的元素也按值非递减排列。
算法的时间复杂度为O(La.length + Lb.length).
*/ ElemType *p; int i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置即地址 // 循环比较，直到找到符合关系的元素 while(i
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
ElemType *pa, *pa_last, *pb, *pb_last, *pc; pa = La.elem; //pa指向线性表La的头结点 pb = Lb.elem; //pb指向线性表Lb的头结点 /* 不用InitList()创建空表Lc */ (*Lc).listsize = (*Lc).length = La.length + Lb.length; // pc指向线性表Lc的头结点 pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType)); /* 存储分配失败 */ //pa_last指向线性表La的尾结点 //pb_last指向线性表Lb的尾结点 /* 表La和表Lb均非空 */ if( !(*Lc).elem ) exit(0); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while(pa
/* 插入Lb的剩余元素 */ } while(pa
}
#endif
// 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否 // 则返回0。
int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{
int i = 2;
// 因为第一个数据元素无前继，从第二个数据元素开始 ElemType *p = L.elem + 1; // 找到该cur_e对应的元素并赋给p while(i L.length)
}
return 0; else { /* 将该cur_e的前驱赋给*pre_e. } */ *pre_e = *--p; return 1; 对等式说明下：* 和 --是同优先级的，且它们的结合性是自右 向左的，所以先p自减1，p指向其前驱，然后将p所指向的地址 的内容赋给*pre_e。从这里要明白为什么用指针进行传值，我 给你一个地址，你把内容放进去，然后我就知道其中的值了。 这就是使用指针的用处。
/*
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继,否 则返回0
*/
int NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
int i = 1;
ElemType *p = L.elem;
while(i
{ i++; p++; } if(i == L.length) return 0; else { /* 对这个等式说明下：* 和 --是同优先级的，且它们的结合性 是自右向左的，所以先p自加1，然后将p所指向的地址的内容 赋给*next_e */ *next_e = *++p; return 1;
}
}
// 算法2.4 P24
// 在L中第i个位置之前插入新的数据元素e，L的长度加1.
int ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase, *q, *p;
// 输入的i不合法 if(i (*L).length + 1) return 0; // 当前存储空间已满,增加分配 if( (*L).length >= (*L).listsize) { // realloc改变(*L).elem所指内存的大小，原始所指内存中的 // 数据不变。 newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; // 新基址 (*L).listsize += LISTINCREMENT; // 增加存储容量 } // 指定插入的位置 q = (*L).elem + i - 1; // q之后的元素右移一步，以腾出位置 for(p = (*L).elem + (*L).length - 1; p >= q; --p) *(p+1) = *p; *q = e; // 插入e ++(*L).length; // 表长增1
return 1;
}
/* 算法2.5 P25
删除L的第i个数据元素，并用e返回其值，L的长度减1.
*/
int ListDelete(SqList *L,int i,ElemType *e)
{
ElemType *p,*q; // i值不合法 if( i (*L).length) return 0; p = (*L).elem + i - 1; // p为被删除元素的位置 *e = *p; // 被删除元素的值赋给e q = (*L).elem + (*L).length-1; // 表尾元素的位置
}
*(p-1) = *p; (*L).length--; return 1; // 表长减1
// 依次对L的每个数据元素调用函数vi()。
int ListTraverse(SqList L, void( *vi )(ElemType* ))
{
ElemType *p; int i; p = L.elem; // 对顺序表中的每一元素调用函数vi() for(i = 1; i
}
// 判断两元素的值是否相等的函数，Union()用到，相等返回1，不相等返回0 int equal(ElemType c1,ElemType c2)
{
if(c1 == c2)
}
/* 算法2.1 P20
将所有在线性表Lb中但不在La中的数据元素插入到La中。
*/
void Union(SqList *La, SqList Lb)
{
ElemType e; int La_len, Lb_len; int i; La_len = ListLength(*La); Lb_len = ListLength(Lb); // 依次对Lb中的元素与La的所有元素进行比较 return 1; else return 0;
{ // 取Lb中第i个数据元素赋给e GetElem(Lb, i, &e); // La中不存在和e相同的元素,则插入之 if( !LocateElem(*La, e, equal) ) ListInsert(La, ++La_len, e); }
}
/*
算法2.2。P21 已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新 的线性表Lc,Lc的数据元素也按值非递减排列。 */
void MergeList(SqList La, SqList Lb, SqList *Lc) {
int i = 1, j = 1, k = 0;
int La_len, Lb_len;
ElemType ai, bj; InitList(Lc); // 创建空表Lc La_len = ListLength(La); Lb_len = ListLength(Lb); while(i
} // 表Lb非空且表La空 则将Lb的剩余部分接到Lc中 while(j
}
}
// 在L中按非降序插入新的数据元素e，L的长度加1. void InsertAscend(SqList *L, ElemType e) {
ElemType *newbase, *p;
int k; // k为e要插入的位置 if( (*L).length >= (*L).listsize ) // 当前存储空间已满,增加分配 { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } p = (*L).elem; // 中介，做对比用的。 for(k = 1; k *p) p++; else break;
ListInsert(L, k, e);
}
// 在L中按非升序插入新的数据元素e，L的长度加1。 void InsertDescend(SqList *L,ElemType e) {
ElemType *newbase, *p; int k; // k为e要插入的位置 if((*L).length >= (*L).listsize) { newbase = (ElemType *)realloc( (*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0);
}
(*L).listsize += LISTINCREMENT; } p = (*L).elem; for(k = 1; k
// 在L的头部插入新的数据元素e，L的长度加1 。 int HeadInsert(SqList *L, ElemType e) {
ElemType *p, *q, *newbase;
}
// 在L的尾部插入新的数据元素e，L的长度加1。 int EndInsert(SqList *L, ElemType e)
{
ElemType *q, *newbase; if( (*L).length >= (*L).listsize) { newbase = (ElemType *)realloc((*L).elem, if( (*L).length >= (*L).listsize ) { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem; // 从表头至表尾的元素依次向后移动一位 for(p = (*L).elem + (*L).length-1; p >= q; --p) *(p+1) = *p; *q = e; (*L).length++; //长度加1 return 1;
} ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if(!newbase) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem+(*L).length; // q为插入位置 *q = e; (*L).length++; return 1;
// 删除L的第一个数据元素，并由e返回其值，L的长度减1。
int DeleteFirst(SqList *L,ElemType *e)
{
ElemType *p, *q; if( ListEmpty(*L) ) // 空表无法删除 return 0; p = (*L).elem; // p指向第一个元素 *e = *p; q = (*L).elem + (*L).length - 1; // q指向最后一个元素 for(++p; p
return 1;
}
// 删除L的最后一个数据元素，并用e返回其值，L的长度减1 。
int DeleteTail(SqList *L,ElemType *e)
{
ElemType *p;
if( !(*L).length ) // 空表 return 0; p = (*L).elem + (*L).length - 1; // 最后一个数据元素的位置 *e = *p; // 被删除元素的值赋给e (*L).length--; // 表长减1
return 1;
}
// 删除表中值为e的元素，并返回1；如无此元素，则返回0
int DeleteElem(SqList *L, ElemType e)
{
int i = 0, // 记录与e值相同的元素的位置
j;
// 先判断i的位置是否越界，然后将e与顺序表的每一个元素相比较， // 直到找到 while(i
}
}
// 用e取代表L中第i个元素的值。
int ReplaceElem(SqList L, int i, ElemType e)
{
}
// 按非降序建立n个元素的线性表。
int CreatAscend(SqList *L, int n)
{
int i,
j; //记录数据要插入的位置 ElemType e; InitList(L); printf(
} { } return 1; scanf(
// 按非升序建立n个元素的线性表。
int CreatDescend(SqList *L, int n)
{
int i, j; //记录数据要插入的位置 ElemType e; InitList(L); printf(
return 1;
}
// 进行测试
// 数据元素判定函数(平方关系)
int comp(ElemType c1, ElemType c2)
{
if(c1 == c2*c2)
return 1;
else
return 0;
}
// ListTraverse()调用的函数(类型要一致)
void visit(ElemType *c)
{
printf(
}
// ListTraverse()调用的另一函数(元素值加倍)
void dbl(ElemType *c)
{
*c *= 2;
}
int main()
{
SqList L;
SqList La, Lb, Lc; ElemType e, e0, d; int i; int j, k, n; int a[4] = { 3, 5, 8, 11}, b[7] = { 2, 6, 8, 9, 11, 15, 20}; // 初始化操作 i = InitList(&L); printf(
// 清空顺序表 i = ClearList(&L); printf(
for(j = 1; j
// 销毁顺序表 DestroyList(&L); printf(
// 按非降序建立n个元素的线性表L printf(
CreatDescend(&L,n); printf(
return 0;
}
/*
输出效果：
初始化L后：L.elem=3412184 L.length=0 L.listsize=10
在L的表头依次插入1～5后：*L.elem=5 4 3 2 1
L.elem=3412184 L.length=5 L.listsize=10
L是否空：i=0(1:是 0:否)
清空L后：L.elem=3412184 L.length=0 L.listsize=10
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：*L.elem=1 2 3 4 5 6 7 8 9 10
L.elem=3412184 L.length=10 L.listsize=10
在L的表头插入0后：*L.elem=0 1 2 3 4 5 6 7 8 9 10
L.elem = 3412184(有可能改变) L.length = 11(改变)L.listsize = 15(改变)
第5个元素的值为：4
第10个元素的值为3的平方
没有值为4的平方的元素
元素0无前驱
元素1的前驱为：0
元素9的后继为：10
元素10无后继
删除第12个数据失败
删除的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9
L的元素值加倍后：
0 2 4 6 8 10 12 14 16 18
销毁L后：L.elem=0 L.length=0 L.listsize=0
La= 1 2 3 4 5
Lb= 2 4 6 8 10
La与Lb合并后新的La= 1 2 3 4 5 6 8 10
La= 3 5 8 11
Lb= 2 6 8 9 11 15 20
合并La与Lb后得到的Lc= 2 3 5 6 8 8 9 11 11 15 20
按非降序建立n个元素的线性表L,请输入元素个数n: 3
请输入3个元素:（空格）
1 2 3
依次输出L的元素：1 2 3
按非降序插入元素10后，线性表L为：1 2 3 10
在L的头部插入12，尾部插入9后，线性表L为：12 1 2 3 10 9
请输入要删除的元素的值: 3
成功删除3
线性表L为：12 1 2 10 9
请输入要取代的元素的序号 元素的新值:（空格） 5 4
线性表L为：12 1 2 10 4
销毁L后,按非升序重新建立n个元素的线性表L,请输入元素个数n(>2): 3 请输入3个元素:
1 2 3
依次输出L的元素：3 2 1
按非升序插入元素10后，线性表L为：10 3 2 1
请输入要删除的元素的值: 10
成功删除10
线性表L为：3 2 1
删除表头元素3和表尾元素1后,线性表L为：
2
请按任意键继续. . .
*/
数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！/*
数据结构C语言版 线性表的动态分配顺序存储结构表示和实现
P22-26
编译环境：Dev-C++ 4.9.9.2 日期：2011年2月9日
*/
#include
#include
#include
typedef int ElemType;
// 定义数据结构元素的数据类型
// 线性表存储空间的初始分配量
// 线性表存储空间的分配增量 #define LIST_INIT_SIZE 10 #define LISTINCREMENT 5
// 线性表的动态分配顺序存储结构
typedef struct
{
ElemType *elem; // 存储空间基址
int length;
int listsize;
}SqList;
// 算法2.3，P23
// 构造一个空的顺序线性表即对顺序表结构体中的所有元素
// 进行初始化。
int InitList(SqList *L)
{
// 分配指定大小的存储空间给顺序表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if( !(*L).elem ) // 存储分配失败 exit(0); (*L).length = 0; // 当前长度初始化为0 // 指定分配的存储容量 (*L).listsize = LIST_INIT_SIZE; return 1; // 当前长度 // 当前分配的存储容量(以sizeof(ElemType)为单位)
}
// 销毁顺序线性表L即将顺序表结构体中的所有成员销毁（空间释放，
// 数值置0）。
int DestroyList(SqList *L)
{
// 先释放空间，然后置空
free( (*L).elem );
}
// 将L重置为空表（当前长度为0即是空表）。
int ClearList(SqList *L)
{
}
/*
若L为空表，则返回1，否则返回0。
如何判断是否为空表呢？结构体中已经包含一个可以说明的元素，
那就是length，表示当前顺序表的长度，根据当前的长度就可以
判断了，为0就是空表，不为0就不是空表了。
*/
int ListEmpty(SqList L)
{
if(0 == L.length)
return 1; else
return 0; (*L).length = 0; return 1; (*L).elem = NULL; (*L).length = 0; (*L).listsize = 0; return 1;
}
// 返回L中数据元素个数。
int ListLength(SqList L)
{
// L.length刚好记录了当前顺序表的长度，直接返回
return L.length;
}
// 用e返回L中第i个数据元素的值，第i个数据元素就是L.elem[i-1]。 int GetElem(SqList L,int i,ElemType *e)
{
// 首先进行异常处理 if(i L.length) exit(0); /* 注意顺序表基址L.elem[0] 表示第一个数，而第i个数则是用 */ *e = *(L.elem + i - 1); // *e = L.elem[i-1]; return 1; 基址L.elem + i - 1来表示,也可以用L.elem[i-1]表示。为什么 可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指 示了一个首地址，然后对地址进行加减，形成不同元素的地址。 *是取地址所指的内容，所以*(L.elem+i-1)就是第i个数据的值了。
}
/* 算法2.6，P26
返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0。
*/
int LocateElem(SqList L,ElemType e,
int(* compare)( ElemType, ElemType))
{
}
#if 0
/* 算法2.7 与算法2.2区别
已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序 线性表Lc,Lc的元素也按值非递减排列。
算法的时间复杂度为O(La.length + Lb.length).
*/ ElemType *p; int i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置即地址 // 循环比较，直到找到符合关系的元素 while(i
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
ElemType *pa, *pa_last, *pb, *pb_last, *pc; pa = La.elem; //pa指向线性表La的头结点 pb = Lb.elem; //pb指向线性表Lb的头结点 /* 不用InitList()创建空表Lc */ (*Lc).listsize = (*Lc).length = La.length + Lb.length; // pc指向线性表Lc的头结点 pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType)); /* 存储分配失败 */ //pa_last指向线性表La的尾结点 //pb_last指向线性表Lb的尾结点 /* 表La和表Lb均非空 */ if( !(*Lc).elem ) exit(0); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while(pa
/* 插入Lb的剩余元素 */ } while(pa
}
#endif
// 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否 // 则返回0。
int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{
int i = 2;
// 因为第一个数据元素无前继，从第二个数据元素开始 ElemType *p = L.elem + 1; // 找到该cur_e对应的元素并赋给p while(i L.length)
}
return 0; else { /* 将该cur_e的前驱赋给*pre_e. } */ *pre_e = *--p; return 1; 对等式说明下：* 和 --是同优先级的，且它们的结合性是自右 向左的，所以先p自减1，p指向其前驱，然后将p所指向的地址 的内容赋给*pre_e。从这里要明白为什么用指针进行传值，我 给你一个地址，你把内容放进去，然后我就知道其中的值了。 这就是使用指针的用处。
/*
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继,否 则返回0
*/
int NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
int i = 1;
ElemType *p = L.elem;
while(i
{ i++; p++; } if(i == L.length) return 0; else { /* 对这个等式说明下：* 和 --是同优先级的，且它们的结合性 是自右向左的，所以先p自加1，然后将p所指向的地址的内容 赋给*next_e */ *next_e = *++p; return 1;
}
}
// 算法2.4 P24
// 在L中第i个位置之前插入新的数据元素e，L的长度加1.
int ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase, *q, *p;
// 输入的i不合法 if(i (*L).length + 1) return 0; // 当前存储空间已满,增加分配 if( (*L).length >= (*L).listsize) { // realloc改变(*L).elem所指内存的大小，原始所指内存中的 // 数据不变。 newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; // 新基址 (*L).listsize += LISTINCREMENT; // 增加存储容量 } // 指定插入的位置 q = (*L).elem + i - 1; // q之后的元素右移一步，以腾出位置 for(p = (*L).elem + (*L).length - 1; p >= q; --p) *(p+1) = *p; *q = e; // 插入e ++(*L).length; // 表长增1
return 1;
}
/* 算法2.5 P25
删除L的第i个数据元素，并用e返回其值，L的长度减1.
*/
int ListDelete(SqList *L,int i,ElemType *e)
{
ElemType *p,*q; // i值不合法 if( i (*L).length) return 0; p = (*L).elem + i - 1; // p为被删除元素的位置 *e = *p; // 被删除元素的值赋给e q = (*L).elem + (*L).length-1; // 表尾元素的位置
}
*(p-1) = *p; (*L).length--; return 1; // 表长减1
// 依次对L的每个数据元素调用函数vi()。
int ListTraverse(SqList L, void( *vi )(ElemType* ))
{
ElemType *p; int i; p = L.elem; // 对顺序表中的每一元素调用函数vi() for(i = 1; i
}
// 判断两元素的值是否相等的函数，Union()用到，相等返回1，不相等返回0 int equal(ElemType c1,ElemType c2)
{
if(c1 == c2)
}
/* 算法2.1 P20
将所有在线性表Lb中但不在La中的数据元素插入到La中。
*/
void Union(SqList *La, SqList Lb)
{
ElemType e; int La_len, Lb_len; int i; La_len = ListLength(*La); Lb_len = ListLength(Lb); // 依次对Lb中的元素与La的所有元素进行比较 return 1; else return 0;
{ // 取Lb中第i个数据元素赋给e GetElem(Lb, i, &e); // La中不存在和e相同的元素,则插入之 if( !LocateElem(*La, e, equal) ) ListInsert(La, ++La_len, e); }
}
/*
算法2.2。P21 已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新 的线性表Lc,Lc的数据元素也按值非递减排列。 */
void MergeList(SqList La, SqList Lb, SqList *Lc) {
int i = 1, j = 1, k = 0;
int La_len, Lb_len;
ElemType ai, bj; InitList(Lc); // 创建空表Lc La_len = ListLength(La); Lb_len = ListLength(Lb); while(i
} // 表Lb非空且表La空 则将Lb的剩余部分接到Lc中 while(j
}
}
// 在L中按非降序插入新的数据元素e，L的长度加1. void InsertAscend(SqList *L, ElemType e) {
ElemType *newbase, *p;
int k; // k为e要插入的位置 if( (*L).length >= (*L).listsize ) // 当前存储空间已满,增加分配 { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } p = (*L).elem; // 中介，做对比用的。 for(k = 1; k *p) p++; else break;
ListInsert(L, k, e);
}
// 在L中按非升序插入新的数据元素e，L的长度加1。 void InsertDescend(SqList *L,ElemType e) {
ElemType *newbase, *p; int k; // k为e要插入的位置 if((*L).length >= (*L).listsize) { newbase = (ElemType *)realloc( (*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0);
}
(*L).listsize += LISTINCREMENT; } p = (*L).elem; for(k = 1; k
// 在L的头部插入新的数据元素e，L的长度加1 。 int HeadInsert(SqList *L, ElemType e) {
ElemType *p, *q, *newbase;
}
// 在L的尾部插入新的数据元素e，L的长度加1。 int EndInsert(SqList *L, ElemType e)
{
ElemType *q, *newbase; if( (*L).length >= (*L).listsize) { newbase = (ElemType *)realloc((*L).elem, if( (*L).length >= (*L).listsize ) { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem; // 从表头至表尾的元素依次向后移动一位 for(p = (*L).elem + (*L).length-1; p >= q; --p) *(p+1) = *p; *q = e; (*L).length++; //长度加1 return 1;
} ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if(!newbase) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem+(*L).length; // q为插入位置 *q = e; (*L).length++; return 1;
// 删除L的第一个数据元素，并由e返回其值，L的长度减1。
int DeleteFirst(SqList *L,ElemType *e)
{
ElemType *p, *q; if( ListEmpty(*L) ) // 空表无法删除 return 0; p = (*L).elem; // p指向第一个元素 *e = *p; q = (*L).elem + (*L).length - 1; // q指向最后一个元素 for(++p; p
return 1;
}
// 删除L的最后一个数据元素，并用e返回其值，L的长度减1 。
int DeleteTail(SqList *L,ElemType *e)
{
ElemType *p;
if( !(*L).length ) // 空表 return 0; p = (*L).elem + (*L).length - 1; // 最后一个数据元素的位置 *e = *p; // 被删除元素的值赋给e (*L).length--; // 表长减1
return 1;
}
// 删除表中值为e的元素，并返回1；如无此元素，则返回0
int DeleteElem(SqList *L, ElemType e)
{
int i = 0, // 记录与e值相同的元素的位置
j;
// 先判断i的位置是否越界，然后将e与顺序表的每一个元素相比较， // 直到找到 while(i
}
}
// 用e取代表L中第i个元素的值。
int ReplaceElem(SqList L, int i, ElemType e)
{
}
// 按非降序建立n个元素的线性表。
int CreatAscend(SqList *L, int n)
{
int i,
j; //记录数据要插入的位置 ElemType e; InitList(L); printf(
} { } return 1; scanf(
// 按非升序建立n个元素的线性表。
int CreatDescend(SqList *L, int n)
{
int i, j; //记录数据要插入的位置 ElemType e; InitList(L); printf(
return 1;
}
// 进行测试
// 数据元素判定函数(平方关系)
int comp(ElemType c1, ElemType c2)
{
if(c1 == c2*c2)
return 1;
else
return 0;
}
// ListTraverse()调用的函数(类型要一致)
void visit(ElemType *c)
{
printf(
}
// ListTraverse()调用的另一函数(元素值加倍)
void dbl(ElemType *c)
{
*c *= 2;
}
int main()
{
SqList L;
SqList La, Lb, Lc; ElemType e, e0, d; int i; int j, k, n; int a[4] = { 3, 5, 8, 11}, b[7] = { 2, 6, 8, 9, 11, 15, 20}; // 初始化操作 i = InitList(&L); printf(
// 清空顺序表 i = ClearList(&L); printf(
for(j = 1; j
// 销毁顺序表 DestroyList(&L); printf(
// 按非降序建立n个元素的线性表L printf(
CreatDescend(&L,n); printf(
return 0;
}
/*
输出效果：
初始化L后：L.elem=3412184 L.length=0 L.listsize=10
在L的表头依次插入1～5后：*L.elem=5 4 3 2 1
L.elem=3412184 L.length=5 L.listsize=10
L是否空：i=0(1:是 0:否)
清空L后：L.elem=3412184 L.length=0 L.listsize=10
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：*L.elem=1 2 3 4 5 6 7 8 9 10
L.elem=3412184 L.length=10 L.listsize=10
在L的表头插入0后：*L.elem=0 1 2 3 4 5 6 7 8 9 10
L.elem = 3412184(有可能改变) L.length = 11(改变)L.listsize = 15(改变)
第5个元素的值为：4
第10个元素的值为3的平方
没有值为4的平方的元素
元素0无前驱
元素1的前驱为：0
元素9的后继为：10
元素10无后继
删除第12个数据失败
删除的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9
L的元素值加倍后：
0 2 4 6 8 10 12 14 16 18
销毁L后：L.elem=0 L.length=0 L.listsize=0
La= 1 2 3 4 5
Lb= 2 4 6 8 10
La与Lb合并后新的La= 1 2 3 4 5 6 8 10
La= 3 5 8 11
Lb= 2 6 8 9 11 15 20
合并La与Lb后得到的Lc= 2 3 5 6 8 8 9 11 11 15 20
按非降序建立n个元素的线性表L,请输入元素个数n: 3
请输入3个元素:（空格）
1 2 3
依次输出L的元素：1 2 3
按非降序插入元素10后，线性表L为：1 2 3 10
在L的头部插入12，尾部插入9后，线性表L为：12 1 2 3 10 9
请输入要删除的元素的值: 3
成功删除3
线性表L为：12 1 2 10 9
请输入要取代的元素的序号 元素的新值:（空格） 5 4
线性表L为：12 1 2 10 4
销毁L后,按非升序重新建立n个元素的线性表L,请输入元素个数n(>2): 3 请输入3个元素:
1 2 3
依次输出L的元素：3 2 1
按非升序插入元素10后，线性表L为：10 3 2 1
请输入要删除的元素的值: 10
成功删除10
线性表L为：3 2 1
删除表头元素3和表尾元素1后,线性表L为：
2
请按任意键继续. . .
*/