名词介绍
1.typedef介绍
typedef
:为C语言的关键字,作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型(int
,char
等)和自定义的数据类型(struct
等)在编程中使用typedef
目的一般有两个,一个是给变量一个易记且意义明确的新名字,另一个是简化一些比较复杂的类型声明。而且可以达到快速修改类型的操作
用法:
1.给类型添加一个别名,以便于结构体的类型修改
typedef <原名> <类型别名>
typedef int ElemType
这里我们把int型加了一个别名ElemType。
struct Student
{
int age;
char s;
……
}
如果要定义一个该结构体变量,就需要:
struct Student st1(变量名);
定义结构体变量的时候每次都要再写一次struct
非常麻烦。
如果我们使用typedef
:
typedef struct
{
int age;
char s;
……
}Stu
解释:把struct类型新增了一个别名Stu
,再进行结构体变量的时候就可以使用
Stu st1(变量名);
Stu st2(变量名)
这样定义变量就简单多了。上面就是定义一个新的结构体,声明为Stu
换个角度思考其实就是typedef直接定义一个新的结构体,并声明。
如果我们的代码有很多变量,类型一致,如果要修改则需要一个个更改,但是用了typedef
给类型增一个别名,可以达到群体修改效果。
例如:
typedef int Elmtype;
Elmtype a,b;
这里Elmtype
只是int
型的一个别名,可以更改成其他英文,我们定义的时候也可以直接用Elmtype
定义变量,他与int
类型是一样的。
typedef int bond;
bond a,b;
bond c,d;
当我们要修改变量a,b,c,d
的类型的时候,只需要把int
换成其他类型就可以了,以此达到便捷.
malloc(m)
函数,开辟m字节长度的地址空间,并返回这段空间的首地址。
指针自身 = (指针类型*)malloc(sizeof(指针类型)*数据数量)
sizeof(x)
运算,计算变量x的长度
free(p)函数
,释放指针p所指变量的存储空间,即彻底删除一个变量
ElmType
:意为任意类型,可以换成int
char
float
double
等类型
elem
:名字,可以 更改数组名
LIST_INIT_SIZE
:数组大小
lastIndex
:最后一个元素的下标
SeqList
:名词,用来表示顺序表结构
1. C语言描述
#define SUCCESS 1 //用SUCCESS来代替计算机识别的1,也就是真
#define FAILURE 0
#define MAXSIZE 100
typedef int ElemType;
//ElemType 类型根据实际情况而定,这里假设为int*
Typedef struct
{
ElemType *data; //数组,存储数据元素
int lastIndex; //最后一个元素的下标
}SeqList;
2.顺序表的初始化
初始化:顺序表的初始化指建立一个空表,即分配存储空间,但不包含任何数据元素。
初始化的C语言描述如下:
/*初始化顺序表 */
/*参数:无 */
/*返回值:SeqList*初始化的顺序表*/
SeqList* InitList()
{
SeqList* L =(SeqList *)malloc(sizeof(SeqList))
}
if(!L)
{
printf("init list error!")
return NULL;
}
L->lastIndex = -1;
return L;
- action:
表的长度=lastIndex + 1
(表的长度:数据元素的个数) - 其中malloc()函数返回的是空间的首地址,要进行强制类型转换。
- 这里
L->lastIndex = -1
的意思是让L取最后一个元素,让其下标等于-1,就相当于你动态开辟一块内存给你的数组,这样这个内存里面的所有数据都是你需要的,向前寻址也没什么问题。让其满足公式表的长度=lastIndex + 1
,则此时长度为0; - 这里的
Seqlist*
就是强制类型转换,因为malloc返回的是无类型指针,但是假设我们的数据表是int
类型,需要转换成整型指针。
3.求顺序表的长度
公式:表的长度=lastIndex + 1
int ListLength(SeqList *L)
{
return L->lastIndex + 1;
返回最后一个元素的下标+1就是长度
4.清空操作
void ClearList(SeqList *L)
{
L->LastIndex = -1;
让下标等于-1,则长度为0,满足公式表的长度=lastIndex + 1
5.附加操作
附加操作是在顺序表未满的情况下,在表的末端添加一个新元素,然后使顺序表的lastIndex
加1.
//ElemType item 是添加的新元素,
//SeqList *L 顺序表L
返回值:int 是否添加成功
int AppendList(SeqList *L,ElemType item)
{
if(L->lastIndex == MAXSIZE - 1) //顺序表已经满
{
return FAILURE;
}
L->data[++(L->lastIndex)] = item; //L取data中最后一个元素下标+1的位置添加新元素item
return SUCCESS;
}
L取data[]中最后一个元素下标+1的位置添加新元素item
6. 插入操作
/* 在顺序表指定位置插入一个新元素 */
/* 参数:SeqList *L 顺序表L */
/* ElemType item 需要添加的新元素 */
/* int pos 新元素插入的位置 */
/* 返回值:int 是否插入成功 */
int ListInsert(SeqList *L, ElemType item, int pos)
{
int i = 0;
if(L->lastIndex == MAXSIZE - 1) /*顺序表已满*/
{
return FAILURE;
}
/*插入的位置不正确
pos小于1表示在第一个位置之前插入
pos大于lastIndex+2表示在最后一个元素后面的第二个位置插入,
均超出顺序表范围 */
if((pos<1||lastIndex > L->lastIndex + 2))
{
return FAILURE;
}
if(pos == L->lastindex + 2)
}
/* 移动元素 */
for(i = L->lastIndex; i >= pos - 1;--1)
{
L->data[i + 1] = L->data[i]
}
/*插入新的数据元素*/
L->data[pos - 1] =item;
/*表增长1*/
++L->lastIndex;
return SUCCESS;
}
数据元素位置=下标+1
pos是a的下指标 范围:a1-a(pos)
长度=lastIndex+1
L
取lastIndex
的下标,判断其是否等于长度-1,相等则表满了。- 插入元素的范围,是第一个,或者最后一个元素的后面,所以范围可以写成
1 < pos < n+1
这里的n是表的长度
。 - 用一个
if
语句来防止插入位置插入错误,不正确的插入范围是:pos <1 || pos>lastIndex+1
。 pos
大于lastIndex+2
表示在最后一个元素后面的第二个位置插入,中间空了一个位置,不连续了。lastIndex+2
这个位置是表尾的下一位。lastIdenx+1则是最后一个元素的位置,也是表的长度
,数据元素位置(apos)=下标+1
- 在表尾插入数据元素:如果pos是最后一个元素的位置,那么让
pos-1
就是最后一个元素位置的下标,也就是lastIndex,data[pos - 1]
就表示data数组中的位置, - 移动元素,把lastIndex的值赋给i,让最后一个元素的位置pos变成后面一个位置,就是
L->data[i + 1] = L->data[ i ]
假如在第pos个位置插入一个元素,则需要把apos-an个元素向后移。
pos-1与否是根据i的初始量来决定的,如果i=0,则pos-1。
7.删除操作
/* 删除顺序表知道位置的一个元素 */
/* 参数:SeqList *L 顺序表L */
/* int pos 删除元素的位置 */
/* 返回值:ElemType 删除的元素 */
ElemType ListDel(SeqList *L,int pos)
{
ElemType tmp;
int i = 0;
if(L->lastIndex == -1) /* 判断表是否为空 */
{
printf("List is empty!");
return FAILURE;
}
/* 删除的位置不正确
pos小于1表示删除第1个位置之前的元素,
pos大于lastIndex + 1 表示删除最后一个元素后面的元素 */
if((pos < 1) || (pos > L->lastIndex + 1))
{
printf("Position is error!");
return FAILURE;
}
if(pos == L->lastIndex + 1) /* 删除最后一个元素 */
{
tmp = L->data[lastIndex--];
return tmp;
}
/* 移动元素 */
tmp = L->data[pos - 1];
for(i = pos; i <= L->lastIndex; ++i)
{
L->data[i - 1] = L->data[i];
}
}
为了数据安全tmp存放删除的数据元素