1 顺序表
//SeqList.cpp
//SeqList.cpp
#include <stdio.h>
#include <malloc.h>//动态存储分配函数头文件
#define MaxSize 50 //定义常量
typedef char ElemType; //为char创建别名ElemType
typedef struct //创建结构体
{
ElemType data[MaxSize];//声明ElemType类型数组,数组名为data,数组长度为MaxSize,即第4行的宏定义50
int length;//声明整型变量length,用来存储数组长度
} SqList;//为结构体创建别名SqList
void InitList(SqList *&L)//定义空类型函数InitList,形参列表有一个参数,参数类型为指向结构体的指针???,用于初始化顺序表L
{
L=(SqList *)malloc(sizeof(SqList));//指针分配空间
/*
0.赋值号左边L是一个SqList *指针,指向名为SqList的结构体;
1.malloc的全称是memory allocation,中文叫动态内存分配.
用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址.
当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存。
void* 类型表示未确定类型的指针。C,C++规定,void* 类型可以通过类型转换强制转换为任何其它类型的指针。
一般需和free函数配对使用。
2.sizeof() 是一个判断数据类型或者表达式长度的运算符。
3.(SqList *)表示把这个地址强制转化为SqlList *的指针。
4.malloc(sizeof(SqList))是分配一块大小为sizeof(SqList)的内存,并返回首地址并赋值给左边的L指针,
*/
L->length=0;
/*
L应该是一个结构体指针,该结构体可能有好几个字段,其中有一个字段叫length,
L->length表示取L结构体的length字段。
L->length = 10;表示给这个字段赋值10,
而temp = L->length表示取该字段的值赋值给temp变量。
*/
}
void DestroyList(SqList *L)//定义空类型函数DestroyList,用于销毁顺序表,形参列表有一个参数,参数类型为指向结构体的指针???
{
free(L);
/*
原型: void free(void *ptr)
功 能: 释放ptr指向的存储空间。被释放的空间通常被送入可用存储区池,以后可在调用malloc、realloc以及calloc函数来再分配。
*/
}
int ListEmpty(SqList *L)//定义整型函数ListEmpty,判断顺序表L是否为空表
{
return(L->length==0);//如果表L为空,即(L->length==0)的值为0;非0即不为空
}
int ListLength(SqList *L)//返回顺序表L的元素个数
{
return(L->length);
/*
->在C语言中称为间接引用运算符,是二目运算符,优先级同成员运算符“.”。
用法:
p->a,其中p是指向一个结构体的指针,a是这个结构体类型的一个成员。表达式p->a引用了指针p指向的结构体的成员a。
例如:
struct T
{
int a;
char b;
}s;
struct T* p=&s;
那么,
p->a相当于s.a。
显然,有个等价写法:(*p).a,和p->a完全等效。
*/
}
void DispList(SqList *L)//定义空类型函数DispList,用于输出顺序表L
{
int i;//定义整型变量i
if (ListEmpty(L)) return;//如果顺序表为空,则返回主调函数
/*
return 表示把程序流程从被调函数转向主调函数并把表达式的值带回主调函数,实现函数值的返回,返回时可附带一个返回值,由return后面的参数指定。
return通常是必要的,因为函数调用的时候计算结果通常是通过返回值带出的。
如果函数执行不需要返回计算结果,也经常需要返回一个状态码来表示函数执行的顺利与否(-1和0就是最常用的状态码),主调函数可以通过返回值判断被调函数的执行情况。
*/
for (i=0;i<L->length;i++)//扫描整个数组
printf("%c",L->data[i]);//打印数组(顺序表L)内容
printf("\n");//打印换行符
}
int GetElem(SqList *L,int i,ElemType &e)
//定义整型函数GetElem, 获取顺序表中第i个函数
{
if (i<1 || i>L->length)
return 0;
e=L->data[i-1];
return 1;
}
int LocateElem(SqList *L, ElemType e)
{
int i=0;
while (i<L->length && L->data[i]!=e) i++;
if (i>=L->length)
return 0;
else
return i+1;
}
int ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1)
return 0;
i--; //将顺序表位序转化为elem下标*/
for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置*/
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++; //顺序表长度增1*/
return 1;
}
int ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1 || i>L->length)
return 0;
i--; //将顺序表位序转化为elem下标*/
e=L->data[i];
for (j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return 1;
}
void main()
{
SqList *L;
ElemType e;
printf("(1)初始化顺序表L\n");
InitList(L);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("(3)输出顺序表L:");
DispList(L);
printf("(4)顺序表L长度=%d\n",ListLength(L));
printf("(5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("(6)顺序表L的第3个元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));
printf("(8)在第4个元素位置上插入f元素\n");
ListInsert(L,4,'f');
printf("(9)输出顺序表L:");
DispList(L);
printf("(10)删除L的第3个元素\n");
ListDelete(L,3,e);
printf("(11)输出顺序表L:");
DispList(L);
printf("(12)释放顺序表L\n");
DestroyList(L);
}