« 上一篇下一篇 »

数据结构<三>——线性表的顺序存储

1、scanf()函数用法

scanf()返回接收到的变量值的个数!!!这个一定要记得。

scanf("%d %d", &a, &b);

如果a和b都被成功读入,那么scanf的返回值就是2;

如果只有a被成功读入,返回值则为1;

如果a和b都未被成功读入,返回值则为0;

如果遇到错误或遇到end of file,返回值为EOF。

且返回值为int型。

所以scanf()用法就直接为

scanf("%d", &pos);                   // 正确代码

而千万不要写成

pos = scanf("%d", &pos);        // 错误代码

我刚刚就犯了这个错误,查找程序查找到的老是第1个元素的值,还以为是代码出错了呢,原来是scanf的用错了。

2、指针的使用

定义指针时一定要初始化!!!一定要记得。

也是刚刚出现的错误,我开始是这样定义指针的

/* 错误代码 */
int *p;
GetElem(L, pos, p);

就这么直接的把一个未初始化的,根本不知道指向哪儿的指针用做了函数参数,所以程序一运行就自动停止。

问题就在于指针没有初始化,它不知道指向哪儿,正确的用法是这样的:

/* 正确代码 */
int value;
int *p = &value;        // 必须把一个内存的地址赋给指针,之后才能对这个指针进行操作
GetElem(L, pos, p);

3、线性表(List)

下面为线性表顺序存储的结构代码:

#include <stdio.h>
#define MAXSIZE 20// 存储空间初始分配量
typedef int ElemType;// ElemType 类型根据实际情况而定,这里为int
typedef struct
{
ElemType data[MAXSIZE];// 数组用来存储数据元素,最大量为MAXSIZE
int length;// 线性表当前长度
}SqList;
#define OK1
#define ERROR0
#define TRUE1
#define FALSE0
typedef int Status;

(1)获得元素操作:GetElem()

对于线性表的顺序存储结构来说,要实现获取元素操作,即将线性表L中的第i个位置的元素值返回,其实不难。在程序里面,只要i的数值在存储线性表的数组的下标范围内,就直接把数组第 (i - 1) 下标的值返回就行了。来看代码:

// Status 是函数的类型,其值是函数结果状态代码,如OK等
// 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
// 操作结果:用e返回L中第i个数据元素的值
Status GetElem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i < 1 || i > L.length)// 如果为空表或元素位置i不合法,则报错
return ERROR;
*e = L.data[i - 1];// i位置的元素的值赋给e指向的内存
return OK;
}

(2)插入操作:ListInsert()

插入算法的思路:

* 如果线性表已满,则提示异常或动态增加容量;

* 如果插入位置不合理,则提示异常;

* 从最后一个元素开始向前遍历到第i个位置,将它们依次向后移动一个位置;

* 将要插入的元素填入位置i处;

* 表长加1。

代码如下:

// 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
// 操作结果:在L中第i个位置插入新的数据元素e,L的长度加1
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if(L->length == MAXSIZE)// 如果顺序线性表已满,则报错
return ERROR;
if(i < 1 || i > L->length + 1)// 如果i不合法,也报错
return ERROR;
if(i <= L->length)// 如果插入的位置不在表尾,则从最后一个元素开始到第i个位置,均向后移一位
{
for(k = L->length - 1; k >= i - 1; k--)
L->data[k + 1] = L->data[k];
}
L->data[i - 1] = e;// 第i个位置插入新值
L->length++;// 表长加1
return OK;
}

(3)删除操作:ListDelete()

删除算法的思路:

* 如果线性表为空表,提示异常;

* 如果删除位置不合理,提示异常;

* 取出要删除元素的值;

* 从要删除元素位置的后一个位置开始遍历到最后一个元素位置,依次向前移动一个位置;

* 表长减1。

代码如下:

// 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
// 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
if(L->length == 0)// 如果线性表为空,则报错
return ERROR;
if(i < 1 || i > L->length)// 如果删除位置不合法,也报错
return ERROR;
*e = L->data[i - 1];// 把删除的元素值赋给*e 
if(i < L->length)// 如果删除位置不在表尾
{
for(k = i; k < L->length; k++)// 将删除位置的后继元素前移
L->data[k - 1] = L->data[k];
}
L->length--;// 表长减1
return OK;
}

函数功能验证:

void main()
{
SqList L = { {5, 4, 2, 8, 10}, 5 };// 定义线性表L,并初始化
int i;
int elem;// 用以存储返回的元素值
int *p = &elem;// 定义一个指针并初始化为指向elem
for(i = 1; i <= L.length; i++)
{
GetElem(L, i, p);// 调用函数获取元素值
printf("第 %d 个位置的数值为  %d  .\n", i, *p);// 显示对应位置元素值
}
printf("\n");
ListInsert(&L, 2, 99);// 在线性表L的第2个位置插入99
for(i = 1; i <= L.length; i++)
{
GetElem(L, i, p);// 调用函数获取元素值
printf("第 %d 个位置的数值为  %d  .\n", i, *p);// 显示对应位置元素值
}
printf("\n");
ListDelete(&L, 1, p);// 删除线性表第1个位置的元素,并用p返回
printf("已成功删除 %d  .\n", *p);// 显示已删除元素的值
for(i = 1; i <= L.length; i++)
{
GetElem(L, i, p);// 调用函数获取元素值
printf("第 %d 个位置的数值为  %d  .\n", i, *p);// 显示对应位置元素值
}
printf("\n");
}

程序先定义一个线性表L,并初始化,

然后进行获得元素操作,并把元素依次显示,

再在表L的第2个位置插入数值99,然后调用获得元素函数,把插入新值后的线性表所有元素依次显示,

之后删除表L第1个位置的元素,由p返回并显示,再次调用获得元素函数,把删除值后的线性表所有元素依次显示。

运行结果如下图示: