[C++] 纯文本查看 复制代码
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
#include<time.h>
#define TRUE 1 //是
#define FALSE 0 //否
#define OK 1 //完成
#define ERROR 0 //错误
#define Warnning 0 //警告
#define FAILED 0 //失败
#define OVERFLOW -2 //内存溢出
/* 上述7个变量本质都一样，只是取个名字方便理解 */
#define LIST_INIT_SIZE 10 //分配大小
typedef int Order; //排序方式
typedef int Status; //完成状态
typedef int ElemType; //代表元素
/* 上述三个都是int类型，取个别名方便理解 */
typedef struct
{
ElemType *Elem;
int Length;
int ListSize;
}pList;
Status InitList(pList *L)
{ //初始化线性表
// 操作结果：构造一个空的顺序线性表L
L->Elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
if(!L->Elem)
{
printf("内存分配请求失败，你脸真的是太黑了！\n");
exit(OVERFLOW);// 存储分配失败
}
L->Length=0; // 空表长度为0
L->ListSize=LIST_INIT_SIZE; // 初始存储容量
printf("线性表初始化成功！\n");
return OK;
}
void DestroyList(pList *L)
{ // 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
if(L->Elem)
{
free(L->Elem);
L->Elem=NULL;
L->Length=NULL;
L->ListSize=NULL;
printf("线性表销毁成功！\n");
}
}
void ClearList(pList *L)
{ // 初始条件：顺序线性表L已存在。操作结果：将L重置为空表
L->Length=0;
printf("线性表置空成功！\n");
}
Status ListEmpty(pList *L)
{ // 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if(L->Length)
return TRUE;
else
return FALSE;
}
Status ListLength(pList *L)
{ // 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
return L->Length;
}
ElemType GetElem(pList *L,int i,ElemType *e)
{ // 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值
int Len=ListLength(L);
if(i < 1 || i > Len)
{
printf("当前线性表范围为%d，输入范围不在此范围中！\n",Len);
return Warnning;
}
*e=L->Elem[i-1];
return *e;
}
int LocateElem(pList *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->Elem; // p的初值为第1个元素的存储位置
while(i <= L->Length && !compare(*p++,e))
++i;
if(i<=L->Length)
return i;
else
return 0;
}
ElemType PriorElem(pList *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)
{
p++;
i++;
}
if(i > L->Length)
{
printf("当前线性表中并无此元素：%d！\n",cur_e);
return FAILED;
exit(0);
}
else
{
*pre_e = *--p;
return *pre_e;
}
}
ElemType NextElem(pList *L,ElemType cur_e,ElemType *next_e)
{ // 初始条件：顺序线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 否则操作失败，next_e无定义
int i=1;
ElemType *p=L->Elem;
while(i < L->Length && *p != cur_e)
{
p++;
i++;
}
if(i == L->Length)
{
printf("当前线性表中并无此元素：%d！\n",cur_e);
return FAILED;
exit(0);
}
else
{
*next_e = *++p;
return *next_e;
}
}
Status InsertList(pList *L,int i,ElemType e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
if(i < 1 || i > L->Length+1)
{
printf("您要插入的位置不在当前线性表范围！\n");
return ERROR;
}
if(L->Length == L->ListSize) // 当前存储空间已满,增加分配
{
ElemType *newbase = (ElemType *)realloc(L->Elem,sizeof(ElemType)*(L->ListSize + LIST_INIT_SIZE));
if(!newbase)
{
printf("内存分配请求失败，你脸真的是太黑了！\n");
return ERROR;
}
L->Elem=newbase;
L->ListSize += LIST_INIT_SIZE;
}
ElemType *q = &(L->Elem[i-1]); //q存储插入位置
ElemType *p;
for(p = &(L->Elem[L->Length - 1]);p >= q; p--)
*(p+1) = *p;
*q = e;
L->Length++;
return OK;
}
Status DeleteList(pList *L,int i,ElemType *e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
if(i < 1 || i > L->Length)
{
printf("需要删除的位置不存在！\n");
return ERROR;
}
ElemType *p = &(L->Elem[i-1]);
*e = *p;
ElemType *q=L->Elem + L->Length-1;
for(p = p + 1;p <= q;p++)
*(p-1) = *p;
L->Length--;
return OK;
}
void TraverseList(pList *L)
{ // 初始条件：顺序线性表L已存在
// 操作结果：输出线性表所有元素
int i;
if(L->Length == 0)
{
printf("当前线性表为空！\n");
}
else
{
printf( "当前线性表为：");
for(i = 1; i <= L->Length ; i++)
printf("%d ", L->Elem[i-1]);
printf("\n");
}
}
void SortList(pList *L)
{ //选择排序法
if(L->Length == 0)
{
printf("当前线性表为空或不存在，无法排序！\n");
exit(0);
}
Order order;
printf("请输入排序方式，0表示从小到大排序，1表示从大到小排序：");
scanf("%d",&order);
int i,j,tmp,max,min;
switch (order)
{
case 0: //从小到大排序
for(i = 0;i < L->Length-1;i++)
{
min = i;
for(j = i;j < L->Length;j++)
{
if(L->Elem[min] > L->Elem[j])
min = j;
}
tmp = L->Elem[i];
L->Elem[i] = L->Elem[min];
L->Elem[min] = tmp;
}
break;
case 1: //从大到小排序
for(i = 0;i < L->Length-1;i++)
{
max = i;
for(j = i;j < L->Length;j++)
{
if(L->Elem[max] < L->Elem[j])
max = j;
}
tmp = L->Elem[i];
L->Elem[i] = L->Elem[max];
L->Elem[max] = tmp;
}
break;
default:
break;
}
}
void InvertList(pList *L)
{ //前后倒置
int i,j,k=L->Length,tmp;
for(i=0,j=k-1;i<k/2;i++,j--)
{
tmp=L->Elem[i];
L->Elem[i]=L->Elem[j];
L->Elem[j]=tmp;
}
}
void Init()
{ //初始化函数
printf("输入数字以完成操作\n");
printf("初始化线性表：1\n");
printf("销毁线性表：2\n");
printf("置空线性表：3\n");
printf("判断是否为空：4\n");
printf("返回线性表长度：5\n");
printf("获取第i个值：6\n");
printf("数据元素判定：7\n");
printf("获取某元素的前驱：8\n");
printf("获取某元素的后继：9\n");
printf("在第i个位置插入元素：10\n");
printf("删除第i个位置的元素：11\n");
printf("遍历输出当前线性表：12\n");
printf("排序当前线性表：13\n");
printf("倒置当前线性表：14\n");
printf("退出：0\n");
}
int main(void)
{
pList L;
ElemType e; //e表示元素，用来存储对线性表操作的元素
int i; //i表示对线性表操作的位置
srand((unsigned int)time(NULL)); //用于产生随机数，此句话加上可使每次产生的随机数都不一样
Init();
int j=1; //j指示进行哪一种操作
while(j!=0)
{
scanf("%d",&j);
switch (j)
{
case 0:
exit(0);
break;
case 1:
if(InitList(&L))
{
printf("开始赋值\n");
for(i=1;i<=8;++i)
{
e=rand()%100+1;
InsertList(&L,i,e);
}
TraverseList(&L);
}
break;
case 2:
DestroyList(&L);
TraverseList(&L);
break;
case 3:
ClearList(&L);
TraverseList(&L);
break;
case 4:
if(ListEmpty(&L) == 0)
printf("当前线性表为空！\n");
else
{
printf("当前线性表不为空！\n");
TraverseList(&L);
}
break;
case 5:
i=ListLength(&L);
printf("当前线性表长度为%d\n",i);
break;
case 6:
printf("请输入获取第几个元素的值：");
scanf("%d",&i);
e=GetElem(&L,i,&e);
printf("第%d个元素是：%d\n",i,e);
break;
case 7:
printf("我还不知道这个函数啥意思呢，compare我也不知道是什么，你如果知道告诉下我！\n");
break;
case 8:
printf("请输入要获取哪个元素的前驱：");
scanf("%d",&i);
e=PriorElem(&L,i,&e);
printf("第%d个元素的前驱是：%d\n",i,e);
break;
case 9:
printf("请输入要获取哪个元素的后继：");
scanf("%d",&i);
e=NextElem(&L,i,&e);
printf("第%d个元素的后继是：%d\n",i,e);
break;
case 10:
printf("请输入要插入的位置及值：");
scanf("%d %d",&i,&e);
InsertList(&L,i,e);
TraverseList(&L);
break;
case 11:
printf("请输入要删除第几个元素：");
scanf("%d",&i);
DeleteList(&L,i,&e);
printf("删除的元素都是:%d\n",e);
break;
case 12:
TraverseList(&L);
break;
case 13:
SortList(&L);
TraverseList(&L);
break;
case 14:
InvertList(&L);
TraverseList(&L);
break;
default:
break;
}
}
return 0;
}
发表于 2018-6-8 22:04
