#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 5 //顺序表的最大容量
typedef struct{
int *base;//顺序表基址 ，base存储的是顺序表第一个元素的地址
int length;//长度 ，即线性表中元素个数
}SqList;
/*顺序表（数组）需要三个参数：首地址；长度；*/
void init(SqList *L);//初始化 顺序表
bool append(SqList *L,int elem);//追加元素，将元素elem追加到顺序表L后面
bool insert(SqList *L,int i,int elem);//插入元素：在第i个位置之前插入元素elem
bool delete(SqList *L,int i,int* elem);//删除元素
int get();//获取某个元素的值
bool is_empty(SqList *L);//判断是否为空
bool is_full(SqList *L);//判断是否满
void sort(SqList *L);//线性表元素排序 （先写一个冒泡排序）
void show(SqList *L);//输出所有元素
bool inverse(SqList *L);//倒置线性表
int main(){
int deleted_elem;
SqList L;//定义了结构体变量，所以分配了内存空间
/*没有初始化之前，这一块内存空间里是垃圾值，所以base没有指向一个有效的元素，
初始化之后，base指向一个有效的数组*/
init(&L);//如果不加地址，传参只传进来了值(只复制了实参的值)，与外面的实参毫无关系，也就是说修改形参对实参不起作用
printf("初始化\n");
show(&L);
printf("追加后\n");
append(&L,1);
append(&L,2);
append(&L,3);
append(&L,3);
show(&L);
insert(&L,3,5);
printf("插入后\n");
show(&L);
if(delete(&L,8,&deleted_elem)){
printf("删除后\n");
printf("被删除的元素是%d\n",deleted_elem);
}
show(&L);
inverse(&L);
printf("逆转后\n");
show(&L);
printf("排序后\n");
sort(&L);
show(&L);
return 0;
}
void init(SqList *L){//因为该操作对线性表做出了修改，所以参数用指针型
L->base = (int*)malloc(sizeof(int)*MAXSIZE);//也可以写成(*L).base
//初始化第一个成员：在内存中开辟一块连续的，大小为MAXSIZE个元素的空间，将第一小块的地址（基地址）赋给L。
if(!L->base) exit(-1);//表示终止整个程序
//如果内存空间不够用或者出现其他异常状况，导致内存分配不成功，返回失败。
L->length = 0;
//初始化第二个成员：刚开始顺序表中没有元素，所以顺序表长度为 0 .
/*注意区分length 与 MAXSIZE：length代表顺序表中元素的个数；
MAXSIZE代表顺序表的容量，也就是最多能存储多少个元素
*/
return;
}
void show(SqList *L){
int i;
if(is_empty(L)){
printf("空\n");
}else{
for(i=0; i<L->length; i++)
{
printf("%d ",L->base[i]);
}
printf("\n");
}
}
bool is_empty(SqList *L){
if(L->length==0)
return true;
else
return false;
}
bool append(SqList *L,int elem){
//int elem;
if(is_full(L)){
printf("满\n");
return false;
}
//scanf("%d",&elem);
L->base[L->length] = elem;
(L->length)++; //注意运算符优先级
return true;
}
bool is_full(SqList *L){
if(L->length==MAXSIZE)
return true;
else
return false;
}
bool insert(SqList *L,int i,int elem){
/*
思想：先移后插,长度加一
移：从顺序表最后一个元素开始到第i个位置的元素，依次往后移动一个位置。（注意1.先移动最后一个元素 2.注意数组下标越界）
插：将元素elem插入到第i个位置，即L->base[i-1] */
int j;
if(is_full(L)){
printf("空间不足，不允许插入！\n");
return false;
}
if(i<1||i>L->length+1){
printf("插入位置不合法！\n");
return false;
}
//移
for(j=L->length; j>=i; j--)
{
L->base[j] = L->base[j-1];
}
/*也可以写成下面这种，看哪一种自己更容易理解
for(j=L->length-1; j>=i-1; j--)
{
L->base[j+1] = L->base[j];
}
*/
//插
L->base[i-1] = elem;
L->length++;
return true;
}
bool delete(SqList *L,int i,int* elem){
/*返回类型选择：假如需要返回被删除的值，
既希望返回删除是否成功，还希望带回删除的值，所以用bool类型来表示删除是否成功，在参数中用指针类型带回删除的值
*/
int j;
if(is_empty(L)){
printf("表为空！\n");
return false;
}
if(i<1||i>L->length)
{
printf("删除位置不合法！\n");
return false;
}
*elem = L->base[i-1];
for(j=i-1; j<=L->length-1; j++)
{
L->base[j-1] = L->base[j];
}
L->length--;
return true;
}
//思想：首尾元素交换
bool inverse(SqList *L){
int i = 0;
int j = L->length-1;
int t;
while(i<j)
{
t = L->base[i];
L->base[i] = L->base[j];
L->base[j] = t;
i++;
j--;
}
return true;
}
/*
思想：定义一个新的顺序表，将元素逆序复制到新的线性表里，将表头指针赋给L。
缺点：空间复杂度变高
bool inverse(SqList *L){
int i;
SqList T;
init(&T);
for(i=0; i<L->length; i++)
{
T.base[i] = L->base[L->length-1-i];
T.length++;
}
L->base = T.base;
return true;
}
*/
void sort(SqList *L){
int i;
int j;
int t;
for(i=0;i<L->length;i++)//外层循环，N个数比较N-1轮
{
for(j=0;j<L->length-1-i;j++)//内层循环，每一轮都把最大的数放在了最下面
{
if(L->base[j]>L->base[j+1])
{
t = L->base[j];
L->base[j] = L->base[j+1];
L->base[j+1] = t;
}
}
}
return;
}
运行结果：
