学习使用C语言实现线性表

来源:转载


线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列,序列中的每个数据元素,可以是一个数字,可以是一个字符,也可以是复杂的结 构体或对象。例如:1,2,3,4,5是一个线性表,A,B,C,D...Z是一个线性表,一列列车的车厢1,车厢2...车厢n是一个线性表。

线性表的机内表示法(又称存储结构)有2种,一种是顺序存储结构,另一种是链式存储结构。

顺序存储结构,顾名思义就是按顺序来存储的一种存储结构,比如线性表(1,2,3,4,5),共计5个元素,

每个int型的数据元素假设占用4个存储单元,假设第1个元素数字1的存储地址是1000,则第2个元素数字2的存储地址是1004,第3个元 素数字3的存储地址是1008,依此类推,第n个数据元素的存储地址是LOC(an) = LOC(a1)+(n-1)k.(k表示每个数据元素占用的存储单元的长度)

显而易见,这种存储结构,相邻元素在物理位置上也相邻。

通常,我们把采用这种存储结构的线性表称为“顺序表”。

链式存储结构,它不要求相邻的元素在物理位置上也相邻,所以它可用一组处在任意位置的存储单元来存储线性表的数据元素。既然这样,那应该怎样表示数据元素之间的逻辑关系呢?

为了表示数据元素之间的逻辑关系,对于数据元素a1来说,除了存储其自身的信息之外,还需要存储一个指示其直接后继的信息,所以我们引入指针的概念:称存储数据元素信息的域称为数据域,而存储直接后继地址信息的域称为指针域。

我们形象地称这种即包含自身数据信息,又包含其直接后继地址信息的数据元素为“结点”。

显而易见,这种存储结构,相邻元素在物理位置上不一定相邻,他们之间用指针来表示逻辑关系。

通常,我们把采用这种存储结构的线性表称为“线性链表”。

有了基本的概念之后,我们就可以使用编程语言进行描述,使用C、C++、C#、Java等都可以,这篇文章我使用C语言描述。

一、顺序表

为了描述顺序表,我们首先要声明一个结构,如下:

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量(当存储空间不够时要用到)typedef int ElemType; //数据元素的类型,假设是int型的typedef struct{ ElemType *elem; //存储空间的基地址 int length; //当前线性表的长度 int listsize; //当前分配的存储容量}SqList;

定义好线性表后,就可以对它进行操作了,常见的线性表的基本操作有:创建线性表、查找元素、插入元素、删除元素、清空、归并等。

线性表的基本操作在顺序表中的实现:

1.创建线性表

int InitList(SqList &L){L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//开辟一个存储空间,并把这块存储空间的基地址赋值给elemif (!L.elem){return -1; //空间分配失败}L.length = 0; //当前长度L.listsize = LIST_INIT_SIZE; //当前分配量return 0;}

2.查找元素(按值查找)

线性表的按值查找是指在线性表中查找与给定值x相等的数据元素。完成该操作最简单的方法是从第一个元素a1开始依次和x比较,若相等,则返回该元素的下标。

若查遍整个表都没有找到与x相等的元素,则返回-1。

时间复杂度:算法的基本操作(比较x与L中第i<1,n>个元素)与元素x在表中的位置有关,也与表长有关。当a1=x时,比较1次成功,当an=x时,比较n次成功,平均比较次数为n+1/2,时间复杂度为O(n)。

int LocateElem(SqList L, ElemType x){int pos = -1;for (int i = 0; i < L.length; i++){if (L.elem[i] == x){pos = i;}}return pos;}

3.插入元素

时间复杂度O(L.length)即O(n)

int ListInsert(SqList &L, int i, ElemType e){//判断插入位置的合法性if (i<1 || i>L.length+1) return -1; //判断存储空间是否够用if (L.length >= L.listsize){ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));if (!newbase) return -1;//存储空间分配失败L.elem = newbase;//新基址L.listsize += LISTINCREMENT;//增加存储容量}//插入操作ElemType *q, *p; //定义2个指针变量q = &(L.elem[i-1]); //q为插入位置(注意形参i是序号,序号是从从1开始的,而下标是从0开始的,因此这里转成下标后是i-1)for (p = &(L.elem[L.length - 1]); p >= q; --p) //从ai到an-1依次后移,注意后移操作要从后往前进行{*(p + 1) = *p;}*q = e;++L.length;//表长加1return 0;}

4.删除元素

时间复杂度O(L.length)即O(n)

int ListDelete(SqList &L, int i, ElemType &e){//判断删除位置的合法性if (i<1 || i>L.length) return -1; //删除操作ElemType *q, *p;//定义2个指针变量 p = &(L.elem[i - 1]);//p为被删除元素的位置(注意形参i是序号,序号是从从1开始的,而下标是从0开始的,因此这里转成下标后是i-1)e = *p; //被删除的元素赋值给e(可能用不到,也可能用到,所以保存给e吧)q = L.elem + L.length - 1;//q指向表尾最后一个元素(q是最后一个元素的地址)for (++p; p <= q; ++p) //从p的下一个元素开始依次前移{*(p - 1) = *p;}--L.length;//表长减1return 0;}

测试代码如下:

#include <stdio.h>#include <stdlib.h>int main(){ SqList list; InitList(list); int n = 10; //添加10个数字给线性表list for (int i = 0; i < 10; i++) { ListInsert(list, i+1, i+1); } //删除第5个 ElemType e; ListDelete(list, 5, e); printf("删除的元素是:%d/n", e); //在第2个位置插入一个元素-1 ListInsert(list, 2, -1); //输出线性表 for (int i = 0; i < 10; i++) { printf("%d ", list.elem[i]); } //输出结果是:1 -1 2 3 4 6 7 8 9 10 system("pause");}

小子初学数据结构,如有不足之处,欢迎大神指正。



分享给朋友:
您可能感兴趣的文章:
随机阅读: