欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

数据结构第二章C语言———线性表

程序员文章站 2022-03-10 19:55:38
...

数据结构第二章C语言 —— 线性表

1.什么是线性表

线性表是一种线性结构。线性结构是除了第一个元素无直接前驱，最后一个无直
接后继外，其他每个数据元素都有一个前驱和后继的数据结构。

（线性表，栈，队列，串和数组都属于线性结构。）
数据结构第二章C语言———线性表

2案例引入

比如多项式的运算，建立图书管理系统并进行各种操作。都可用到线性表。

3线性表的类型定义

线性表一种最常用且最简单的数据结构

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素

不仅可以进行访问还可以进行插入删除等操作。

抽象数据类型线性表的定义如下：
数据结构第二章C语言———线性表

4.1线性表的顺序表示和实现

线性表是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得

逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位

置，第 i 个元素元素的存储位置后面紧接着存储的是第 i + 1 个元素。因此，顺序

表的特点是表中元素的逻辑顺序与其物理顺序相同。

一般来说，线性表的第i个数据元素ai的存储位置为：

					LOC（ai） = LOC（a1） +  （i-1）*l；

数据结构第二章C语言———线性表

#define MAXSIZE 100   //顺序表的最大长度
struct Sqlist{		//定义的结构体，名字叫做Sqlist
	int length;		//当前长度
	Elemtype *elem;//存储空间的基地址
}

注意：

  1. 初始化完成后，数组指针elem指示顺序表的基地址；数组空间大小为MAXSIZE

    2. 什么是Elemtype,我在这引用这位大神的

在定义结构体array的时候有这样一段：
typedef struct
{
ElemType data[maxsize];
int length;
}array;
在《数据结构》中，关于数据元素的类型定义均用“ ElemType e；”来表示，其中e是表示数据元素的变量，而ElemType则是它的类型，ElemType的含义就是“数据元素的类型”，是一个抽象的概念，是表示我们所要使用的数据元素应有的类型。
使用：typedef int ElemType;//定义ElemType为int类型
你想让它是什么类型自己用typedef重定义就行。
也可以用模板表示，类似template里面的T。
这对于初学数据结构的学生来说理解起来有些难度，为了利于理解，我们可以把”ElemType“等同于”一套房子“来理解：
“一套房子”的含义大家都非常清楚，但一套房子的具体含义是因人而异的，有的认为是“四室二厅”，有的认为是“二室一厅”，也有的认为是“一室一厅”，对此大家也没有任何异议！其实ElemType也是这样的，它有时表示“整型”，有时表示“用户自定义的结构体”，也可以是其他形式的类型*表示！

3.length表示顺序表中当前数据元素的个数。C语言数组下标是从0开始的，而位置序号是1开始的。所以数据元素a1,a2,a3…an 存放在elem[0],elem[1],elem
[2]…elem[n-1]中 。

示例：
用线性表存储图书馆的数据

#define MAXSIZE 100
struct Book{//定义一个名字为Book的结构体
	char no[20];//书的***
	int price;//价格
	char name[20];//名字
}

struct SqList{//图书表的顺序存储结构类型为Sqlist
	Book *elem;//储存位置的基地址
	int length;//当前长度
}

Sqlist L;//上述定义完后，可定义“Sqlist L”;把L，定义为Sqlist.便可以使用L.elem[i-1]访问表中位置序号为i的图书记录

4.2顺序表中基本操作的实现

4.2.1 判断是否为空

int ListEmpty(SqList L)
{
    if (L.length == 0)
        return OK;//关于OK的定义会在最后的汇总中讲
    else
        return ERROR;//关于ERROR的定义会在最后的汇总中讲
}

4.2.2 返回长度

int length(Sqlist L)
{
	return  L.length;
}

上述两个方法都比较容易实现因为表的长度是顺序表的一个属性，直接返回 L 的length 值即可。

4.2.3顺序表的初始化

这里我开始也分不清楚 顺序表初始化 和 顺序表的顺序表示 两则和的区别。

后来自己想觉得两者的区别就像是

顺序表的顺序表示 为 我定义a为int型；
顺序表初始化 为 a = 100;(不过这里要特殊点，顺序表的初始化要求都为0)

初始化的步骤：

1 >使顺序表L动态分配一个预定义大小为MAXSIZE的数组空间。elem（数组元素的基地址）指向这段空间的基地址。
2> 将表的当前长度设为0。

int InitList (SqList *L)//我要对线性表L进行修改，所以要用到*，用指针作为参数
{
	L.elem = MAXSIZE;//将顺序表的大小定为MAXSIZE
	if(!L.elem)//如果L的储存数据元素的基地址为0，就退出失败；
		exit (ERROR);
	L.length = 0;//L当前的长度为0；
	retrun OK;
}

关于exit和return的区别

4.2.4顺序表的取值

由于我们前面提到过：*“length表示顺序表中当前数据元素的个数。C语言数组下标是从0开始的，而位置序号是1开始的。所以数据元素a1,a2,a3…an 存放在elem[0],elem[1],elem[2]…elem[n-1]中 。”*所以在取第i个数据元素时我们对elem[i-1]进行操作

算法步骤：
1>判断位置合不合理
2>取值

int GetELem(Sqlist L，int i,Elemtype *e)
{
	if(i < 1 || i>L.length)
		return ERROR;
	else 
		 *e = L.elem[i-1];
		return OK;
}

4.2.5顺序表的查找

给出数据e找到数据e相等的元素L.elem[i]。
算法步骤
1>从第一个数据开始进行查找，如果找到了返回与e相等的L.elem[i]，返回i+1；
2>如果没有找到，返回ERROR

	int LOcateElem(SqList L,ElemType e)
	{
		for(int i  =  0 ; i < L.length ; i++)
			if(elem[i]  = e)
				return i+1;
			else return  ERROR；
	}

4.2.6顺序表的插入

因为线性表的物理顺序与实际的存储顺序一致，所以我在第i上插入一个元素，i后面的元素都要向后移动（实际上顺序表并不适合大规模的实现插入和删除）

算法实现步骤：
1>判断给出的位置i是否合理
2>判断存储空间是否满，（满了无法插入）
3>将第i个位置上的元素到第n个元素都向后移动一个位置，若要移动的是最后一个即第i+1个，则无需向后移动
4>将要插入的元素e插入到第i个位置
5>L的length加1

int LIstInsert(SqList &L,int  i ,ElemType e)
{
	if(i<1||i>L.length) return ERROR;//判断给出的位置i是否合理
	if(L.length + 1 > MAXSIZE)	return ERROR;//判断存储空间是否满，（*满了无法插入*）
	for(int j = L.length-1 ; i>=i-1 ; i++)//将第i个位置上的元素到第n个元素都向后移动一个位置，若要移动的是最后一个即第i+1个，则无需向后移动
		L.elem[j+1] = L.elem[j];
	L.elem[i-1] =  e;//将要插入的元素e插入到第i个位置
	L.length++;//L的length加1
	return OK:	
}

4.2.7顺序表的删除

和线性表的插入差不多，插入是i到n的元素向后移动，删除是i到n向前移动
算法步骤：
1>判断i的位置是否合理；
2>将第i+1个到第n个的元素 向前移动
3>length-1;

int ListDelete (Sqlist &L,int i)
{
	if（i<1||i>L.length）return ERROR;//判断i的位置是否合理；
	for(int j = 1;j<=L.length;j++)//将第i+1个到第n个的元素 向前移动
		L.elem[j-1]  = L.elem[j];
		L.length--;
		return OK;
}

4.2.7顺序表的全部输出

这没啥好讲的，直接看代码

int ListTravse(Sqlist L)
{
	fot(int i = 0;i<L.length;i++)
	cout<<L.elem.[i]<<" "<<endl;	//C++的输出流方式
	return OK;
}

线性表的全部实现

#include<stdio.h>
#include<stdlib.h>

#define OK       1					//我要先定义了OK是啥，后面才能用
#define ERROR    0					//一样的
#define MAXSIZE  20

typedef struct {
    int data[MAXSIZE];                //数组，存储线性表数据
    int length;                		  //线性表长度
}SqList;

/*初始化线性表*/
int InitList(SqList *L)
{
    L->length = 0;
    return OK;
}

/*判断线性表是否为空，为空返回OK，否则返回ERROR*/
int ListEmpty(SqList L)
{
    if (L.length == 0)
        return OK;
    else
        return ERROR;
}

/*清除线性表*/
int ClearList(SqList *L)
{
    L->length = 0;
    return OK;
}

/*返回线性表长度*/
int ListLength(SqList L)
{
    return L.length;
}

/*返回L中第i个数据元素的值*/
int GetElemt(SqList L, int i, int *e)
{
    if (L.length == 0 || i < 0 || i > L.length)
        return ERROR;
    else
        *e = L.data[i - 1];

    return OK;
}

/*返回线性表中第1个与e满足关系的位置*/
int LocateElem(SqList L, int e)
{
    int i;
    if (L.length == 0)
        return ERROR;

    for (i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
            break;
    }

    if (i >= L.length)
        return ERROR;

    return i + 1;

}

/*在线性表L的第i个位置插入新的数据元素e*/
int ListInsert(SqList *L, int i, int e)
{
    int k;
    if (L->length == MAXSIZE)
        return ERROR;
    if (i<1 || i>L->length + 1)
        return ERROR;

    if (i <= L->length)
    {
        for (k = L->length ; k >= i; k--)
        {
            L->data[k] = L->data[k-1];
        }
    }

    L->data[i-1] = e;
    L->length++;

    return OK;

}

/*删除线性表L的第i个元素*/
int ListDelet(SqList *L, int i, int *e)
{
    int k;
    if (L->length == 0)
        return ERROR;
    if (i < 1 || i > L->length)
        return ERROR;

    *e = L->data[i - 1];
    if (i < L->length)
    {
        for (k = i; k < L->length; k++)
            L->data[k-1] = L->data[k];
    }
    L->length--;
    return OK;

}

/*依次输出线性表L中的元素*/
int ListTravse(SqList L)
{
    int i;
    for (i = 1; i <=L.length; i++)
        printf("%d", L.data[i-1]);
    printf("\n");

    return OK;
}

void unionL(SqList *La, SqList Lb)
{
    int La_len, Lb_len,i;
    int e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++)
    {
        GetElemt(Lb, i, &e);
        if (!LocateElem(*La, e))
            ListInsert(La, ++La_len, e);
    }
}

int main()
{
    SqList L;
    SqList Lb;
    int e;
    int i;
    int j, k;
    i = InitList(&L);
    printf("初始化线性表L后长度为：%d\n", L.length);
    for (i = 1; i <= 5; i++)
        j = ListInsert(&L, 1, i);
    ListTravse(L);
    printf("线性表L后长度为：%d\n", L.length);
    i = ListEmpty(L);
    printf("L是否为空：i=%d(0为非空，1为空\n", i);
    i = ClearList(&L);
    printf("L是否为空：i=%d(0为非空，1为空\n", i);

    for (j = 1; j <= 10; j++)
    {
        i = ListInsert(&L, j, j);
    }
    printf("在L末尾依次插入1到10后，L.data=\n");
    ListTravse(L);
    printf("L.length = %d\n", L.length);
    ListInsert(&L, 1, 0);
    printf("在L表头插入0后L.data为\n");
    ListTravse(L);
    GetElemt(L, 5, &e);
    printf("第5个数据为%d\n",e);
    for (j = 3; j <= 4; j++)
    {
        k = LocateElem(L, j);
        if (k)
            printf("第%d个元素为%d\n", k, j);
        else
            printf("线性表中没有%d这个元素\n", j);
    }

    j = 5;
    k = ListDelet(&L, j, &e);
    if (k = ERROR)
        printf("删除第j个元素失败");
    else
    printf("删除的第%d个元素为%d\n",j, e);

    printf("依次输出L的元素\n");
    ListTravse(L);
    i = InitList(&Lb);
    for (j = 6; j <= 15; j++)
        i = ListInsert(&Lb, 1, j);
    ListTravse(Lb);
    unionL(&L, Lb);
    printf("合并了Lb的L元素\n");
    ListTravse(L);
    return 0;

}

后记：
1-数据结构中" . "和“->”的区别
2-指针中*和&的区别
3-这是我期末复习的总结，有错误的地方请大家海涵

参考资料：
1.winner_chenwei关于线性表的文章
2.数据结构C语言版第二版严蔚敏版 中国工信出版集团 第二章 线性表

相关标签： 数据结构 算法

上一篇： 数据结构第二章C语言 —— 单链表

下一篇： java栈实现中缀转后缀并计算后缀表达式

推荐阅读