《数据结构（C语言版）》顺序线性表的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第二章线性表中顺序表的代码实现，函数部分与课本基本相同
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct
{
ElemType* elem;//存储空间基址
int length;//当前长度
int listsize;//最大长度
}SqList;
int InitList_sq(SqList& L);//构造一个空的线性表L
int ListInsert_Sq(SqList& L, int i, ElemType e);//在顺序线性表L中第i个位置之前插入新的元素e
int ListDelete_Sq(SqList& L, int i, ElemType& e);//在顺序线性表L中删除第i个元素，并返回这个元素的值e
int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType));//查找第一个与e满足compare（）的元素的位置
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc);//已知顺序线性表La和Lb的元素按值递增排列，归并获得同样递增排列的线性表Lc
void Output_Sq(SqList L);//打印线性表中所有元素的值
int compareEqual(int a, int b);
int compareBig(int a, int b);
int compareSmall(int a, int b);
void Menu()
{
printf("*****************************\n");
printf("*********开 始 菜 单*********\n");
printf("*********0：退出系统*********\n");
printf("*********1：插入元素*********\n");
printf("*********2：删除元素*********\n");
printf("*********3：查找元素*********\n");
printf("*********4：打印表单*********\n");
printf("*****************************\n");
}
int main()
{
SqList MySqList;
int input=0;
int position = 1;
int ret = 0;
int value = 0;
int relation = 1;
InitList_sq(MySqList);
do
{
Menu();
scanf("%d", &input);
if (input < 0 || input > 4)
{
printf("输入错误，请重新输入\n");
input = 0;
}
else
{
switch (input)
{
case 1:
printf("请输入你想插入的位置:");
scanf("%d", &position);
printf("请输入你想插入的值：");
scanf("%d", &value);
ret = ListInsert_Sq(MySqList, position, value);
if (!ret)
{
printf("插入失败，请重试\n");
}
else
{
printf("插入成功\n");
}
break;
case 2:
printf("请输入你想删除的位置:");
scanf("%d", &position);
ret = ListDelete_Sq(MySqList, position, value);
if (!ret)
{
printf("删除失败，请重试\n");
}
else
{
printf("删除成功，您删除的值为%d\n", value);
}
break;
case 3:
printf("请输入你想查找的元素：");
scanf("%d", &value);
printf("请输入你想查找的关系：\n");
printf("查找线性表中第一个与其等的元素请按1\n");
printf("查找线性表中第一个比它大的元素请按2\n");
printf("查找线性表中第一个比它小的元素请按3\n");
scanf("%d", &relation);
switch (relation)
{
case 1:
ret = LocateElem_Sq(MySqList, value, compareEqual);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("满足条件的元素所在的位置为%d\n", ret);
}
break;
case 2:
ret = LocateElem_Sq(MySqList, value, compareBig);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("满足条件的元素所在的位置为%d\n", ret);
}
break;
case 3:
ret = LocateElem_Sq(MySqList, value, compareSmall);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("满足条件的元素所在的位置为%d\n", ret);
}
break;
default:
printf("你输入的值有误");
break;
}
break;
case 4:
Output_Sq(MySqList);
printf("\n");
break;
case 0:
exit(0);
break;
default:
printf("你输入的值有误，请重新输入");
break;
}
}
} while (input);
//归并线性表函数测试
/*SqList MySqList1;
SqList MySqList2;
SqList MySqList3;
InitList_sq(MySqList1);
InitList_sq(MySqList2);
InitList_sq(MySqList3);
ListInsert_Sq(MySqList1, 1, 12);
ListInsert_Sq(MySqList1, 2, 14);
ListInsert_Sq(MySqList1, 3, 18);
ListInsert_Sq(MySqList1, 4, 32);
ListInsert_Sq(MySqList2, 1, 1);
ListInsert_Sq(MySqList2, 2, 2);
ListInsert_Sq(MySqList2, 3, 5);
ListInsert_Sq(MySqList2, 4, 69);
ListInsert_Sq(MySqList2, 5, 70);
ListInsert_Sq(MySqList2, 6, 81);
MergeList_Sq(MySqList1, MySqList2, MySqList3);
Output_Sq(MySqList3);*/
return 0;
}
int InitList_sq(SqList& L)//构造一个空的线性表L
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
{
exit(OVERFLOW);
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(SqList& L, int i, ElemType e)//在顺序线性表L中第i个位置之前插入新的元素e
{
//判断插入位置是否合法
if (i<1 || i>L.length + 1)//注意要+1
{
return ERROR;
}
if (L.length >= L.listsize)//如果存储空间满了用realloc增加分配
{
//关于realloc函数的注释：
//成功分配内存后L.elem将被系统回收，一定不可再对L.elem指针做任何操作，包括 free()；相反的，可以对 realloc()函数的返回值newbase进行正常操作。
//如果是扩大内存操作会把L.elem指向的内存中的数据复制到新地址（新地址也可能会和原地址相同，但依旧不能对原指针进行任何操作）；如果是缩小内存操作，原始据会被复制并截取新长度。
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
{
exit(OVERFLOW);
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
int* q = &L.elem[i - 1];//q为插入位置，注意要减一
for (int* p = &L.elem[L.length - 1]; p >= q; p--)
{
*(p + 1) = *p;
}
*q = e;
L.length++;//更新表长
return OK;
}
int ListDelete_Sq(SqList& L, int i, ElemType& e)//在顺序线性表L中删除第i个元素，并返回这个元素的值e
{
//判断删除位置是否合法
if (i<1 || i>L.length)
{
return ERROR;
}
int* p = &L.elem[i - 1];//p为删除位置，注意要减一
e = *p;//用e保存被删去元素的值
int* q = L.elem + L.length - 1;//q为表尾位置
for (p++; p <= q; p++)
{
*(p - 1) = *p;
}
L.length--;//更新表长
return OK;
}
int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType))//查找第一个与e满足compare（）的元素的位置
{
int i = 1;
int* p = L.elem;
while (i <= L.length && !(*compare)(*p++, e))
{
i++;
}
if (i <= L.length)
{
return i;
}
else
{
return 0;
}
}
int compareEqual(int a, int b)
{
if (a == b)
{
return 1;
}
else
{
return 0;
}
}
int compareBig(int a, int b)
{
if (a > b)
{
return 1;
}
else
{
return 0;
}
}
int compareSmall(int a, int b)
{
if (a < b)
{
return 1;
}
else
{
return 0;
}
}
void Output_Sq(SqList L)//打印线性表中所有元素的值
{
if (L.length == 0)
{
printf("空表");
}
else
{
for (int i = 0; i < L.length; i++)
{
printf("%d ", *(L.elem + i));
}
}
}
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)//已知顺序线性表La和Lb的元素按值递增排列，归并获得同样递增排列的线性表Lc
{
int* pa = La.elem;
int* pb = Lb.elem;
Lc.length = La.length + Lb.length;
Lc.listsize = Lc.length;
Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem)
{
exit(OVERFLOW);
}
int* pc = Lc.elem;
int* pa_last = La.elem + La.length - 1;
int* pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while (pa <= pa_last)//如果表a或表b有剩余元素则全部添加到表c后面
{
*pc++ = *pa++;
}
while (pb <= pb_last)
{
*pc++ = *pb++;
}
}
