亲宝软件园·资讯

展开

C语言线性表

​ 世纪末的架构师   ​ 人气:2

线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是n个数据元素的有限序列

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 实现工具：dev 顺序表示要实现的功能：

准备工作

1.在dev新建一个Source File文件即可 File>new>Source File 

实现线性表

在实现程序时导入的头文件有

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

在这里我调用windows头文件是为了在后面的代码中修改控制台的名称，在实现线性表的顺序结构时真正用到的只有前三个头文件

在写代码之前先对一些表示结果状态的字符进行预定义：

//函数结果状态字符
#define TRUE     1     //代码中出现TRUE相当于出现了1
#define FALSE    0     //出现FALSE相当于出现了0
#define OK       1     //出现OK相当于出现了1
#define ERROR    0     //出现ERROR相当于出现了0
#define INFEASIBLE    -1
#define OVERFLOW      -2 .

typedef int Status;
typedef int ElemType;

在这里使用了typedef定义了Status和ElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同

线性表的动态分配顺序存储结构

#define LIST_INIT_SIZE    100     //线性表存储空间的初始分配量 
#define LISTINCREMENT     10      //线性表存储空间的分配增量 

typedef struct{
	ElemType *elem;          //存储空间的基址
	int length;              //当前线性表的长度
	int listsize;            //当前线性表的存储容量
}SqList;

构造一个空的线性表

//构造一个空的线性表
Status InitList_Sq(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));      //L.elem为首元素的地址 
	if(!L.elem){            //如果存储空间分配失败，L.elem为NULL
	printf("存储空间分配失败\n");
	exit(OVERFLOW);
	}
	L.length = 0;            //当前线性表为空表，即线性表长度为0
	L.listsize = LIST_INIT_SIZE;           //给线性表分配初始容量
	printf("一个空的线性表已经构建成功\n");      //输出空线性表构建成功的提示消息 
	return OK; 
}

在构造空线性表时参数加&符号表示引用传递，确保形参和实参同时改变 L.elem为线性表首元素的地址，L.length为当前线性表的长度，L.listsize为顺序表当前分配空间的大小 我们现在来简单的介绍一下sizeof函数 sizeof函数：获取数据在内存中所占用的存储空间（以字节为单位来计数） 图示：

对线性表进行赋值

Status ValueList_Sq(SqList &L){
	int i,j;
	printf("请输入线性表元素的个数：");
	scanf("%d",&i);
	if(i > L.listsize)                     //如果当要输入的元素个数大于内存大小时 
	{
		while(1)             //一直开辟新空间，直到开辟的空间大于需要的空间为止
		{
			if(i > L.listsize){
				L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
				L.listsize += LISTINCREMENT;
			}
			else
			break;
		}
	}
	for(j = 0;j < i;j++){
		printf("请输入第%d个元素：",j + 1);
	    scanf("%d",&L.elem[j]);
	} 
	L.length = i;          //赋值完成后，修改并保存线性表的长度 
	printf("赋值成功\n");
	return OK;
}

这里的形参同样要加&符号来确保形参与实参同时改变 进行线性表赋值操作时用到了realloc函数，在这里简单的介绍一下realloc函数的作用 realloc()函数：重新分配空间
参数：原空间基址，现需空间大小
返回值：1. 成功：新空间地址(本质上是一个数值) 2. 失败：NULL 当我们在输入线性表元素个数大于构造空线性表给线性表分配初始容量时，要一直开辟新空间，直到开辟的空间大于需要的空间为止

对线性表进行销毁

Status DistoryList_Sq(SqList &L){
	if(!L.elem){ 
	  printf("您还未建立线性表，请先建立线性表\n");
	  return ERROR; 
	} 
	free(L.elem);            //使用free函数，将之前动态分配的内存还给系统 
	L.elem = NULL;           //重置elem的值为Null 
	L.length = 0;            //将线性表的元素个数重置为0
	L.listsize = 0;          //将线性表的存储容量重置为0 
	printf("线性表已经销毁\n"); 
	return OK;
}

在销毁线性表时，首先先对线性表是否存在进行判断，如果线性表不存在，L.elem为NULL，所以此时！L.elem为true，执行后面的return ERROR; L.elem中存储的是初始化是动态分配内存首元素的地址，free函数的作用就是将之前动态分配的内存还给系统，但是在调用free函数之后，虽然归还了内存，但是L.elem中仍然指向原来的地址，而这个地址在归还内存之后程序便无权进行访问，所以此时L.elem就成了一个野指针，我们重置L.elem为NULL就是为了防止发生野指针访问的情况，接着将线性表元素的个数L.length和存储容量L.listsize重置为0

对线性表进行重置

//对线性表进行重置
Status ClearList_Sq(SqList &L){
	if(L.elem){                  //如果线性表存在 
	    L.length = 0;            //将线性表的元素个数重置为0
	    printf("线性表已重置\n");
	    return OK;
	}
	else 
	printf("线性表不存在，无法重置\n");
	return OK;
}

重置线性表时仍然先对线性表是否存在进行判断，如果线性表存在只需将线性表元素个数L.length重置为0即可，不需要改变其它变量

判断线性表是否为空

//判断线性表是否为空
Status ListEmpty_Sq(SqList L){
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在 
		if(L.length != 0){               //如果线性表中元素为0，即L.length的值为0时说明线性表是空表 
		       printf("线性表不是空表\n");
		       return FALSE;
			}
			else
			   printf("线性表是空表\n");
		return TRUE;
	}
	else
	printf("线性表不存在，无法判断\n");
	return OK;
}

判断线性表是否为空只需要看线性表当中的元素个数L.length是否为0即可，如果为0，则说明线性表是空表；不等于0则说明该线性表不为空

获取线性表的长度

//获取线性表的长度
Status ListLength_Sq(SqList L){
	if(L.elem){              //判断当前线性表存在
		int K;
		K = L.length;        //将线性表的元素个数赋值给K
		printf("线性表长度为%d\n",K);
		return OK;
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
}

线性表的长度是由当前线性表中的元素个数来体现的，所以获取线性表的长度仅需定义一个int类型变量，并将L.length赋值给K即可

获取线性表某一位置对应的元素

//获取线性表某一位置对应的元素
Status GetElem_Sq(SqList L,int index){
	int Num;
	if(index <= 0 || index > L.length){              //如果要获取元素的位置是否出界 
		printf("请输入一个有效的数字\n");
		return ERROR;
	}
	else
	Num = L.elem[index - 1];
	printf("第%d个位置的元素为：%d\n",index,Num);
	return OK;
}

同样地，获取线性表某一位置对应的元素时先判断要获取的位置是否合法，和判断线性表的长度一样，只需要将L.elem[index-1]位置的元素赋值给一个int型变量Num即可（index-1是因为数组元素的下标是从0开始的）

在线性表某一位置插入元素

//在线性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
	ElemType *newbase;
	int *q,*p; 
	if(i < 1 || i > L.length+1)         //判断插入位置的index值是否合法
	    return ERROR;
	if(L.length >= L.listsize){         //如果当前线性表存储空间已满，增加分配
		newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)  {                 //如果存储空间分配失败，则执行异常退出
			printf("存储空间分配失败\n");
			exit(OVERFLOW);
		}
		L.elem = newbase;               //新的存储空间基址
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i-1]);                 //L.elem[index-1]为数组中的最后一个元素，q为要插入的位置 
	for(p = &(L.elem[L.length - 1]);p >= q;--p)
	    *(p+1) = *p;                    //要插入位置以及之后的位置向后移 
	*q = e;                             //将e插入到想要插入的位置 
	++L.length;                         //插入新的元素之后表长加1 
	printf("元素插入成功\n");
	return OK;
}

在线性表中的某一位置插入一个元素，同样要先判断要插入的位置是否合法，接着就是判断线性表是否已满，如果线性表没有存储位置，则需要通过realloc函数重新分配一块空间，要想在某一位置插入一个元素，首先要将这个想要插入元素的位置空出来，所以在插入元素时要先从表尾开始到想要插入元素的位置将元素依次向后移动一位 realloc函数如果分配空间成功的话返回的就是新空间的地址，但是本质上是一个数值，因此就需要进行强制类型转换，将数值改成指针类型 

图示：

在这里要强调一点这一条语句，为什么不直接将newbase直接赋值给L.elem，要先进行判断是否分配存储成功？

if(!newbase) { //如果存储空间分配失败，则执行异常退出

		printf("存储空间分配失败\n");
		exit(OVERFLOW);
	}
	L.elem = newbase;

如果分配空间失败，此时的newbase的值为NULL，所以此时L.elem就会被赋值为NULL，原信息丢失 插入元素后，表长加一

删除线性表某一位置的元素

//删除线性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
	int *p,*q;
	if(i < 1 || i > L.length){            //如果要删除的位置不合法
		printf("请输入一个有效数字\n");
		return ERROR;
	} 
	p = &(L.elem[i - 1]);                 //p为被删除元素的位置
	q = L.elem + L.length - 1;            //将表尾元素的位置赋值给q
	for(++p;p <= q;p++)
	    *(p - 1) = *p;                    //被删除的元素之后的元素全部左移 
	--L.length;                           //表长减1 
	printf("第%d个元素删除成功\n",i);
	return OK;
}

L.elem + L.length - 1为表尾元素，删除元素相比起插入元素要简便些，不需要进行后移操作，数据向前覆盖，删除完成后表长减1即可。如果有需要的话，可以单独定义一个int类型的变量在进行删除操作之前将要删除的元素赋值给该变量。

求线性表某一元素的前驱

//求线性表某一元素的前驱
Status PriorElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在
	    if(i <= 1 || i > L.length + 1)              //判断输入的i值是否合法 
	        printf("请输入一个有效数字\n");
		K = L.elem[i - 2];        //将第i个元素的前一个元素赋值给K
		printf("第%d个位置的直接前驱为：%d\n",i,K); 
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
}

求前驱时除了要判断线性表是否存在外，只需要将L.elem[i-2]赋给int型变量K即可

求线性表某一元素的后继

//求线性表某一元素的后继 
Status NextElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在
	    if(i <= 1 || i > L.length - 1)              //判断输入的i值是否合法
	        printf("请输入一个有效数字\n");
		K = L.elem[i];        //将第i个元素的后一个元素赋值给K
		printf("第%d个位置的直接后继为：%d\n",i,K);
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
}

求后继和求前驱除了在元素位置上有区别外，其余的思路都一致，在此不多做赘述

打印线性表

//打印线性表
Status PrintList_Sq(SqList L){
	printf("当前线性表的元素为：");
	for(int K = 0;K < L.length;K++)      //遍历当前线性表
	    printf("  %d",L.elem[K]);
	printf("\n");                        //换行
	return OK;
}

运行结果演示：

为了方便演示，在这里线性表一次赋值为1,2,3,4,5

构建一个空线性表

 赋值操作

 判断此时的线性表是否为空

 获取线性表的长度

 获取2号位置的元素

在3号位置插入520并打印线性表

 删除3号位置的520并打印线性表 

 求3号位置的前驱和后继

以上便是线性表顺序表示和实现，由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常用数组来描述数据结构中的顺序存储结构。在这种结构中，很容易实现线性表的某些操作，但是需要特别注意的是C语言的数组下标是从“0”开始。

源码

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

//函数结果状态代码 
#define TRUE     1     //代码中出现TRUE相当于出现了1
#define FALSE    0     //出现FALSE相当于出现了0
#define OK       1     //出现OK相当于出现了1
#define ERROR    0     //出现ERROR相当于出现了0
#define INFEASIBLE    -1
#define OVERFLOW      -2

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE    100     //线性表存储空间的初始分配量
#define LISTINCREMENT     10      //线性表存储空间的分配增量

typedef struct{
	ElemType *elem;          //存储空间的基址
	int length;              //当前线性表的长度
	int listsize;            //当前线性表的存储容量
}SqList;

//构造一个空的线性表
Status InitList_Sq(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));      //L.elem为首元素的地址 
	if(!L.elem){            //如果存储空间分配失败，L.elem为NULL
	printf("存储空间分配失败\n");
	exit(OVERFLOW);
	}
	L.length = 0;            //当前线性表为空表，即线性表长度为0
	L.listsize = LIST_INIT_SIZE;           //给线性表分配初始容量
	printf("一个空的线性表已经构建成功\n");      //输出空线性表构建成功的提示消息 
	return OK;
}

//对线性表进行赋值
Status ValueList_Sq(SqList &L){
	int i,j;
	printf("请输入线性表元素的个数：");
	scanf("%d",&i);
	if(i > L.listsize)                     //如果当要输入的元素个数大于内存大小时 
	{
		while(1)             //一直开辟新空间，直到开辟的空间大于需要的空间为止
		{
			if(i > L.listsize){
				L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
				L.listsize += LISTINCREMENT;
        /*realloc()函数：重新分配空间
		           参数：原空间基址，现需空间大小
		           返回：1.成功：新空间地址(本质上是一个数值)
		                 2.失败：Null
	    */
			}
			else
			break;
		}
	}
	for(j = 0;j < i;j++){
		printf("请输入第%d个元素：",j + 1);
	    scanf("%d",&L.elem[j]);
	} 
	L.length = i;          //赋值完成后，修改并保存线性表的长度 
	printf("赋值成功\n");
	return OK;
}

//对线性表进行销毁
Status DistoryList_Sq(SqList &L){
	if(!L.elem){
	  printf("您还未建立线性表，请先建立线性表\n");
	  return ERROR;
	}
	free(L.elem);            //使用free函数，将之前动态分配的内存还给系统 
	L.elem = NULL;           //重置elem的值为Null 
	L.length = 0;            //将线性表的元素个数重置为0
	L.listsize = 0;          //将线性表的存储容量重置为0 
	printf("线性表已经销毁\n"); 
	return OK;
}

//对线性表进行重置
Status ClearList_Sq(SqList &L){
	if(L.elem){                  //如果线性表存在 
	    L.length = 0;            //将线性表的元素个数重置为0
	    printf("线性表已重置\n");
	    return OK;
	}
	else
	printf("线性表不存在，无法重置\n");
	return OK;
}

//判断线性表是否为空
Status ListEmpty_Sq(SqList L){
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在
		if(L.length != 0){               //如果线性表中元素为0，即L.length的值为0时说明线性表是空表
		       printf("线性表不是空表\n");
		       return FALSE; 
			}
			else
			   printf("线性表是空表\n");
		return TRUE;
	}
	else
	printf("线性表不存在，无法判断\n");
	return OK; 
}

//获取线性表的长度
Status ListLength_Sq(SqList L){
	if(L.elem){              //判断当前线性表存在 
		int K;
		K = L.length;        //将线性表的元素个数赋值给K
		printf("线性表长度为%d\n",K);
		return OK;
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
}

//获取线性表某一位置对应的元素
Status GetElem_Sq(SqList L,int index){
	int Num;
	if(index <= 0 || index > L.length){              //如果要获取元素的位置是否出界 
		printf("请输入一个有效的数字\n");
		return ERROR;
	}
	else
	Num = L.elem[index - 1];
	printf("第%d个位置的元素为：%d\n",index,Num);
	return OK;
} 

//在线性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
	ElemType *newbase;
	int *q,*p;
	if(i < 1 || i > L.length+1)         //判断插入位置的index值是否合法
	    return ERROR;
	if(L.length >= L.listsize){         //如果当前线性表存储空间已满，增加分配
		newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)  {                 //如果存储空间分配失败，则执行异常退出
			printf("存储空间分配失败\n");
			exit(OVERFLOW);
		}
		L.elem = newbase;               //新的存储空间基址
		L.listsize += LISTINCREMENT; 
	}
	q = &(L.elem[i-1]);                 //L.elem[index-1]为数组中的最后一个元素，q为要插入的位置
	for(p = &(L.elem[L.length - 1]);p >= q;--p)
	    *(p+1) = *p;                    //要插入位置以及之后的位置向后移
	*q = e;                             //将e插入到想要插入的位置
	++L.length;                         //插入新的元素之后表长加1
	printf("元素插入成功\n");
	return OK;
}

//打印线性表
Status PrintList_Sq(SqList L){
	printf("当前线性表的元素为：");
	for(int K = 0;K < L.length;K++)      //遍历当前线性表
	    printf("  %d",L.elem[K]);
	printf("\n");                        //换行
	return OK;
} 

//删除线性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
	int *p,*q;
	if(i < 1 || i > L.length){            //如果要删除的位置不合法
		printf("请输入一个有效数字\n"); 
		return ERROR;
	} 
	p = &(L.elem[i - 1]);                 //p为被删除元素的位置
	q = L.elem + L.length - 1;            //将表尾元素的位置赋值给q
	for(++p;p <= q;p++)
	    *(p - 1) = *p;                    //被删除的元素之后的元素全部左移
	--L.length;                           //表长减1
	printf("第%d个元素删除成功\n",i);
	return OK;
}

//求线性表某一元素的前驱
Status PriorElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在
	    if(i <= 1 || i > L.length + 1)              //判断输入的i值是否合法 
	        printf("请输入一个有效数字\n");
		K = L.elem[i - 2];        //将第i个元素的前一个元素赋值给K
		printf("第%d个位置的直接前驱为：%d\n",i,K);
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
}

//求线性表某一元素的后继
Status NextElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判断线性表是否为空的前提是线性表存在，当首元素地址即L.elem存在时说明线性表存在
	    if(i <= 1 || i > L.length - 1)              //判断输入的i值是否合法 
	        printf("请输入一个有效数字\n");
		K = L.elem[i];        //将第i个元素的后一个元素赋值给K
		printf("第%d个位置的直接后继为：%d\n",i,K);
	}
	else
		printf("线性表不存在，无法判断\n");
	return OK;
} 

int main(){
	SetConsoleTitle("Dream_飞翔");
	SqList L;
	int choose,index,e;
	while(1){
		printf("*****************************************\n");
		printf("*                                       *\n");
		printf("*  线性表的顺序表示和实现：             *\n");
		printf("*                                       *\n");
		printf("*    1.  构造一个空的线性表             *\n");
		printf("*    2.  对线性表进行赋值               *\n");
		printf("*    3.  对线性表进行销毁               *\n");
		printf("*    4.  对线性表进行重置               *\n"); 
		printf("*    5.  判断线性表是否为空             *\n");
		printf("*    6.  获取线性表的长度               *\n");
		printf("*    7.  获取线性表某一位置对应的元素   *\n");
		printf("*    8.  在线性表某一位置插入元素       *\n");
		printf("*    9.  删除线性表某一位置的元素       *\n");
		printf("*    10. 求线性表某一元素的前驱         *\n");
		printf("*    11. 求线性表某一元素的后继         *\n");
		printf("*    12. 打印线性表                     *\n");
		printf("*    13. 退出                           *\n");
		printf("*                                       *\n");
		printf("*****************************************\n");
		printf("请做出您的选择：");
		scanf("%d",&choose);
		switch(choose){
			case 1:InitList_Sq(L);break;
			case 2:ValueList_Sq(L);break;
			case 3:DistoryList_Sq(L);break;
			case 4:ClearList_Sq(L);break;
			case 5:ListEmpty_Sq(L);break;
			case 6:ListLength_Sq(L);break;
			case 7:{
				printf("请输入要获取元素的位置：");
				scanf("%d",&index);
				GetElem_Sq(L,index);
			}
			break;
			case 8:{
				printf("请输入要插入元素的位置：");
				scanf("%d",&index);
				printf("请输入要插入的元素：");
				scanf("%d",&e);
				ListInsert_Sq(L,index,e);
			}
			break;
			case 9:{
				printf("请输入要删除元素的位置：");
				scanf("%d",&index);
				DeleteList_Sq(L,index);
			}
			break;
			case 10:{
				printf("请输入想要查找哪一个元素的前驱：");
				scanf("%d",&index);
				PriorElem_Sq(L,index);
			}
			break;
			case 11:{
				printf("请输入想要查找哪一个元素的后继：");
				scanf("%d",&index);
				NextElem_Sq(L,index);
			}
			break; 
			case 12:PrintList_Sq(L);break;
			case 13:exit(0);
		}
	}
	return 0;
}

加载全部内容
相关教程
猜你喜欢
用户评论