标签：key length 原理 定义数据 delete 归并 empty 后退 语言
/***********************************线性表顺序存储结构的ADT定义(数组实现)**********************************************
ADT List
{
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ |ai-1 ,ai∈D, i=2,...,n }
基本操作：
（1）线性表的初始化操作
InitList（&L,n）
操作结果：将L初始化为空表,申请空间的大小为n。
（2）线性表元素输入操作
ListInput(&L)
初始条件：线性表L已存在 。
操作结果：线性表中的部分元素或全部元素已被赋值。
（3）线性表的置空操作
ClearList(&L)
初始条件：线性表L已存在且不为空 。
操作结果：将表L置为空表。
（4）线性表的判空操作
ListIsEmpty(&L)
初始条件：线性表L已存在。
操作结果：如果L为空表则返回1，否则返回0。
（5）获取线性表元素个数的操作
ListLength（L）
初始条件：线性表L已存在。
操作结果：如果L为空表则返回0，否则返回表中的元素个数。
（6）获取线性表第i个元素的操作（用元素的位序查找元素的值）
GetItem(L,i,&e)
初始条件：表L已存在且不为空，1
#include //使用了malloc、realloc、free函数
//******************************************自定义符号常量*******************************************
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
#define OVERFLOW -2 //内存溢出错误常量
#define ILLEGAL -1 //非法操作错误常量
#define OK 1 //表示操作正确的常量
#define ERROR 0 //表示操作错误的常量
//******************************************自定义数据类型********************************************
typedef int Status;
typedef float ElemType;
typedef struct{
ElemType *elem; //线性表存储空间初始分配量
int length; //当前长度
int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;
//******************************************线性表的主要操作******************************************
//1.--------------------线性表的初始化操作----------------------------
/*
函数：InitList_Sq
参数：SqList &L 线性表引用
int n 线性表最多能存储n个元素
返回值：状态码，OK表示操作成功
作用：构造一个空线性表L
*/
Status InitList_Sq(SqList &L, int n) {
//申请线性表的内存空间，申请n个元素大小的内存空间
L.elem = (ElemType *)malloc(n * sizeof(ElemType));
//判断内存是否分配成功
if(!L.elem){ //if(!L.elem) if(L.elem == NULL)
printf("内存申请失败！\n");
exit(OVERFLOW); //若内存分配失败，则退出程序
}//if
printf("内存申请成功！\n");
//设置线性表的各个参数
L.length = 0; //设置线性表的长度为0
L.listsize = n; //设置线性表的空间大小为100个元素所占空间的大小
printf("线性表创建成功！\n");
//操作成功后返回OK
return OK;
}//InitList_Sq
//2.----------------------输入线性表元素的操作-------------------
/*
函数：ListInput_Sq
参数：SqList &L 线性表引用
返回值：状态码，OK表示操作成功
作用：初始化线性表L中的元素
*/
Status ListInput_Sq(SqList &L){
//i声明在这里不是好的写法，应该将i写在for循环中，有利于缩短i的作用域，及早回收其内存空间。
//但是由于C语言不兼容这种写法，考虑到兼容性所以将i写在外面。（C++支持这种写法）
int n, i; //n代表元素的个数,i用作循环变量
//从键盘接收元素的个数，用户输入正确后退出此循环
while(1){ //while(1)是一个死循环，除非在循环体内执行break语句，否则永远无法退出循环
//先确定元素的个数
printf("您想输入几个元素，请输入个数，最多不可以超过:%d\n", L.listsize);
scanf("%d",&n);
if(n 100) {
//如果发生非法操作，就提醒用户重新输入
printf("您的输入非法，请重新输入！！！\n");
}//if
else {
break;
}//else
}//while
//使用键盘输入的方式初始化每一个元素
printf("请输入线性表L的元素，中间用空格隔开，最多不可以超过100个元素\n");
for(i = 0; i L.length + 1) {
return ERROR; //i的值不合法，返回错误
}//if
//插入操作之前需要先检查存储空间是否够用，若不够用就需要扩容
if(L.length >= L.listsize) { //当前存储已满，需要扩容
//realloc函数第一个参数是已经分配了的那部分存储空间的首地址，
//第二个参数是重新分配的内存的大小，这个参数的值一般情况下
//会比已经分配的内存空间大一些或者小一些，但是需要注意的是
//如果新的大小小于原内存大小，可能会导致数据丢失。
//realloc函数的工作原理： 先判断当前的指针是否有足够的连续空间，
//如果有，扩大mem_address指向的地址，并且将mem_address返回，
//如果空间不够，先按照newsize指定的大小分配空间，将原有数据
//从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域
//（注意：原来指针是自动释放，不需要使用free），
//同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
//realloc函数的特点：如果我们只扩大不缩小，原先已分配内存的保存的数据不会丢失
//这部分数据会被realloc函数转移到新的内存空间中，我们不需要
//手工写拷贝数据的代码，也不需要手工释放第一个参数指示的已分配内存空间。
//我们只需要接收返回值，就能得到新的内存空间的首地址
//使用realloc函数为线性表重新分配内存空间
newbase = (ElemType *)realloc(L.elem,
(LIST_INIT_SIZE + L.listsize) * sizeof(ElemType));
//判断内存空间是否分配成功
if(!newbase){ //if(!newbase) if(newbase == NULL)
printf("内存申请失败！\n");
//若内存分配失败，则后续操作就没有意义了，此时应退出程序
exit(OVERFLOW);
}//if
printf("内存申请成功！\n");
L.elem = newbase; //将线性表新基址赋给elem
L.listsize += LISTINCREMENT; //增加存储容量
}//if
//找到插入位置
q = &(L.elem[i - 1]); //q指示了插入位置
//将插入位置及之后的元素后移
for(p = &(L.elem[L.length - 1]); p >= q; --p) {
*(p + 1) = *p;
}//for
//将e插入到q指示的插入位置
*q = e;
//插入元素e后表长应该增加1
++L.length;
//操作成功
return OK;
}//ListInsert_Sq
//5.----------------------线性表中删除元素的操作----------------------------
/*
函数：ListDelete_Sq
参数：SqList &L 线性表引用
int i 删除位置，1 if(ListIsEmpty_Sq(L) != 0)
if(ListIsEmpty_Sq(L)) {
return ERROR;
}//if
//判断删除位置的参数i的值是否合法
if(i L.length) {
return ERROR; //i的值不合法，返回错误
}//if
//找到删除位置，p指示了被删除元素的位置
p = &(L.elem[i - 1]);
//保存将被删除的元素
e = *p;
//找到表尾元素的位置，q指示了表尾元素的位置
q = L.elem + L.length - 1;
//从被删除元素之后开始到表尾元素位置，将被删除元素之后的所有元素前移一位
//当此循环结束时，被删除元素被其紧随其后的元素覆盖了，也就是删除了
for(++p; p
int main(){
int max(int, int), min(int, int), add(int, int);
void process(int, int, int (*fun)(int, int));
int a, b;
printf("enter a and b:");
scanf("%d,%d", &a, &b);
process(a, b, max);
process(a, b, min);
process(a, b, add);
}//main
process(int x, int y, int (*fun)(int, int)){
int result;
result = (*fun)(x, y);
printf("%d\n",result);
}//process
max(int x, int y) {
printf(“max=”);
return(x > y ? x : y);
}//max
min(int x, int y){
printf(“min=”);
return(x if(ListIsEmpty_Sq(L) != 0)
if(ListIsEmpty_Sq(L)) {
return ERROR;
}//if
//设置查找的起始位置
int i = 1; //i的初值为第一个元素的位序
p = L.elem; //p的初值为第一个元素的存储位置
//以compare函数返回值为基准在线性表中查找元素e
while(i if(ListIsEmpty_Sq(La) != 0)
if(ListIsEmpty_Sq(La)) {
return ERROR;
}//if
//if(ListIsEmpty_Sq(Lb)) if(ListIsEmpty_Sq(Lb) != 0)
if(ListIsEmpty_Sq(Lb)) {
return ERROR;
}//if
//工作指针pa, pb保存了线性表a、b存储元素内存空间的首地址
pa = La.elem;
pb = Lb.elem;
//合并后的线性表c表长等于被合并的线性表a和b的表长之和
Lc.listsize = Lc.length = La.length + Lb.length;
//确定线性表c的长度之后为其申请内存空间，大小等于a和b两表之和
pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType));
//检查内存分配是否成功
if(!Lc.elem){ //if(!Lc.elem) if(Lc.elem == NULL)
printf("内存申请失败！");
exit(OVERFLOW); //若内存分配失败，则退出程序
}//if
//计算出线性表a和b的表尾元素所在位置，分别赋给对应的指针变量pa_last和pb_last
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
//合并pa和pb到pc
//首先将线性表a和b中较短的一个完全合并到pc，另一个只合并一部分
while (pa if(ListIsEmpty_Sq(L) != 0)
if(ListIsEmpty_Sq(L)) {
return ERROR;
}//if
//设置变量的初始值
int low = 0;
int high = L.length-1;
int tmp, j;
while (low L.elem[j + 1]) {
tmp = L.elem[j];
L.elem[j] = L.elem[j + 1];
L.elem[j + 1] = tmp;
}//if
}//for
//修改high值, 前移一位
--high;
//反向冒泡,找到最小者
for (j = high; j > low; --j) {
if (L.elem[j] if(visit(L.elem[i]) != ERROR)
if(!visit(L.elem[i])) {
return ERROR; //如果访问某个元素失败则退出
}//if
}//for
//便利完成后打印空行，作用是在控制台输出时能够区分开不同的输出
//使输出清楚美观
printf("\n");
return OK;
}//ListTraverse_Sq
//***************************************主函数********************************************
int main(int argc, char *argv[]){
SqList L1, L2, L3; //声明三个线性表
int i; //i代表元素的位序
ElemType e; //e用于传入和保存元素的值
printf("*******************************线性顺序表测试程序*******************************\n");
//---------------------------------测试初始化功能----------------------------------
printf("---------------------------------测试初始化功能---------------------------------\n");
printf("->初始化线性表L1\n");
InitList_Sq(L1, LIST_INIT_SIZE); //初始化线性表1
ListInput_Sq(L1); //为L1中的元素赋值
printf("恭喜您，线性表L1初始化并赋值完毕！\n\n");
printf("->初始化线性表L2\n");
InitList_Sq(L2, LIST_INIT_SIZE); //初始化线性表2
ListInput_Sq(L2); //为L2中的元素赋值
printf("恭喜您，线性表L2初始化并赋值完毕！\n\n");
//-----------------------------测试输出功能---------------------------------------
printf("----------------------------------测试输出功能----------------------------------\n");
printf("初始化操作之后L1、L2的元素为：\n");
printf("->输出线性表L1的所有元素：\n");
ListTraverse_Sq(L1, Print); //在执行其他操作之前先输出一遍所有元素，以供参考
printf("->输出线性表L2的所有元素：\n");
ListTraverse_Sq(L2, Print);
//-----------------------------测试插入功能---------------------------------------
printf("\n----------------------------------测试插入功能----------------------------------\n");
printf("->现在为L1插入元素\n"); //为线性表L1插入一个元素
printf("您想在线性表L1的哪个位置之前插入值？\n");
scanf("%d", &i);
printf("您想在线性表L1的该位置之前插入的值为多少？\n");
scanf("%f", &e);
ListInsert_Sq(L1,i,e);
printf("执行插入操作后线性表L1的所有元素为：\n"); //输出执行操作后的线性表，以便与原始结果对比
ListTraverse_Sq(L1,Print);
printf("->现在为L2插入元素\n");
printf("您想在线性表L2的哪个位置之前插入值？\n"); //为线性表L2插入一个元素
scanf("%d", &i);
printf("您想在线性表L2的该位置之前插入的值为多少？\n");
scanf("%f", &e);
ListInsert_Sq(L2, i, e);
printf("执行插入操作后线性表L2的所有元素为：\n"); //输出执行操作后的线性表，以便与原始结果对比
ListTraverse_Sq(L2, Print);
printf("\n插入操作执行完毕！\n\n");
//-----------------------------测试删除功能---------------------------------------
printf("----------------------------------测试删除功能----------------------------------\n");
printf("->现在在L1中删除元素\n"); //在L1中删除一个元素
printf("您想在线性表L1的哪个位置之前删除值？\n");
scanf("%d", &i);
ListDelete_Sq(L1, i, e);
printf("被删除的元素为%f\n", e);
printf("执行删除操作后线性表L1的所有元素为：\n"); //输出执行操作后的线性表，以便与原始结果对比
ListTraverse_Sq(L1, Print);
printf("->现在在L2中删除元素\n"); //在L2中删除一个元素
printf("您想在线性表L2的哪个位置之前删除值？\n");
scanf("%d", &i);
ListDelete_Sq(L2, i, e);
printf("被删除的元素为%f\n", e);
printf("执行删除操作后线性表L2的所有元素为：\n"); //输出执行操作后的线性表，以便与原始结果对比
ListTraverse_Sq(L2, Print);
printf("\n删除操作执行完毕！\n\n");
//-----------------------------测试查找功能---------------------------------------
printf("----------------------------------测试查找功能----------------------------------\n");
printf("您想在线性表L1中查找的值为：\n");
scanf("%f", &e);
i = LocateElem_Sq(L1, e, compare);
if(i == 0){
printf("对不起，没有找到您输入的元素！\n");
}//if
else {
printf("恭喜，找到啦！您想要的元素在表中的位序为%d\n",i);
}//else
printf("您想在线性表L2中查找的值为：\n");
scanf("%f", &e);
i = LocateElem_Sq(L2, e, compare);
if(i == 0) {
printf("对不起，没有找到您输入的元素！\n");
}//if
else {
printf("恭喜，找到啦！您想要的元素在表中的位序为%d\n", i);
}//else
printf("\n查找操作执行完毕！\n\n");
//---------------------------------测试排序功能---------------------------------------
printf("----------------------------------测试排序功能----------------------------------\n");
printf("排序前 L1、L2的元素为：\n");
printf("->线性表L1的所有元素：\n");
ListTraverse_Sq(L1, Print); //在执行操作之前先输出一遍所有元素，以供参考
printf("->线性表L2的所有元素：\n");
ListTraverse_Sq(L2, Print);
SortList_Sq(L1); //分别对L1和L2进行排序
SortList_Sq(L2);
printf("排序后 L1、L2的元素为：\n");
printf("->线性表L1的所有元素：\n");
ListTraverse_Sq(L1, Print); //执行操作之后再输出一遍所有元素
printf("->线性表L2的所有元素：\n");
ListTraverse_Sq(L2, Print);
printf("\n排序操作执行完毕！\n\n");
//-----------------------------测试归并(合并)功能---------------------------------------
printf("----------------------------------测试归并功能----------------------------------\n");
printf("->初始化线性表L3\n");
InitList_Sq(L3, L1.listsize + L2.listsize); //初始化线性表3，空间大小为L1与L2的和，但不给元素赋值
printf("线性表L3初始化成功！开始归并操作\n\n");
MergeList_Sq(L1, L2, L3);
printf("->线性表L3的所有元素：\n");
ListTraverse_Sq(L3, Print);
printf("归并操作执行完毕！\n\n");
//--------------------------------测试销毁功能------------------------------------------
printf("----------------------------------测试销毁功能----------------------------------\n");
printf("->销毁线性表L1：");
DestoryList_Sq(L1);
printf("->销毁线性表L2：");
DestoryList_Sq(L2);
printf("->销毁线性表L3：");
DestoryList_Sq(L3);
printf("销毁操作执行完毕！\n\n");
printf("所有操作执行完毕，测试成功！\n");
return 0;
}
/* --------------------------------- 运行结果 ------------------------------
*******************************线性顺序表测试程序*******************************
---------------------------------测试初始化功能---------------------------------
->初始化线性表L1
内存申请成功！
线性表创建成功！
您想输入几个元素，请输入个数，最多不可以超过:100
5
请输入线性表L的元素，中间用空格隔开，最多不可以超过100个元素
1 45 7 89 6
该线性表初始化操作已完成！
恭喜您，线性表L1初始化并赋值完毕！
->初始化线性表L2
内存申请成功！
线性表创建成功！
您想输入几个元素，请输入个数，最多不可以超过:100
10
请输入线性表L的元素，中间用空格隔开，最多不可以超过100个元素
45 75 24 16 23 45 89 62 51 44
该线性表初始化操作已完成！
恭喜您，线性表L2初始化并赋值完毕！
----------------------------------测试输出功能----------------------------------
初始化操作之后L1、L2的元素为：
->输出线性表L1的所有元素：
1.00 45.00 7.00 89.00 6.00
->输出线性表L2的所有元素：
45.00 75.00 24.00 16.00 23.00 45.00 89.00 62.00 51.00 44.00
----------------------------------测试插入功能----------------------------------
->现在为L1插入元素
您想在线性表L1的哪个位置之前插入值？
2
您想在线性表L1的该位置之前插入的值为多少？
55
执行插入操作后线性表L1的所有元素为：
1.00 55.00 45.00 7.00 89.00 6.00
->现在为L2插入元素
您想在线性表L2的哪个位置之前插入值？
6
您想在线性表L2的该位置之前插入的值为多少？
33
执行插入操作后线性表L2的所有元素为：
45.00 75.00 24.00 16.00 23.00 33.00 45.00 89.00 62.00 51.00 44.00
插入操作执行完毕！
----------------------------------测试删除功能----------------------------------
->现在在L1中删除元素
您想在线性表L1的哪个位置之前删除值？
4
被删除的元素为7.000000
执行删除操作后线性表L1的所有元素为：
1.00 55.00 45.00 89.00 6.00
->现在在L2中删除元素
您想在线性表L2的哪个位置之前删除值？
2
被删除的元素为75.000000
执行删除操作后线性表L2的所有元素为：
45.00 24.00 16.00 23.00 33.00 45.00 89.00 62.00 51.00 44.00
删除操作执行完毕！
----------------------------------测试查找功能----------------------------------
您想在线性表L1中查找的值为：
55
恭喜，找到啦！您想要的元素在表中的位序为2
您想在线性表L2中查找的值为：
99
对不起，没有找到您输入的元素！
查找操作执行完毕！
----------------------------------测试排序功能----------------------------------
排序前 L1、L2的元素为：
->线性表L1的所有元素：
1.00 55.00 45.00 89.00 6.00
->线性表L2的所有元素：
45.00 24.00 16.00 23.00 33.00 45.00 89.00 62.00 51.00 44.00
排序后 L1、L2的元素为：
->线性表L1的所有元素：
1.00 6.00 45.00 55.00 89.00
->线性表L2的所有元素：
16.00 23.00 24.00 33.00 44.00 45.00 45.00 51.00 62.00 89.00
排序操作执行完毕！
----------------------------------测试归并功能----------------------------------
->初始化线性表L3
内存申请成功！
线性表创建成功！
线性表L3初始化成功！开始归并操作
->线性表L3的所有元素：
1.00 6.00 16.00 23.00 24.00 33.00 44.00 45.00 45.00 45.00 51.00 55.00 62.00 89.00 89.00
归并操作执行完毕！
----------------------------------测试销毁功能----------------------------------
->销毁线性表L1：内存空间释放成功!
->销毁线性表L2：内存空间释放成功!
->销毁线性表L3：内存空间释放成功!
销毁操作执行完毕！
所有操作执行完毕，测试成功！
--------------------------------
Process exited with return value 0
Press any key to continue . . .
*/
线性顺序表动态内存分配(C语言实现)
标签：key length 原理 定义数据 delete 归并 empty 后退 语言
原文地址：https://www.cnblogs.com/btlord/p/14791023.html