线性表的定义类型
线性表(linear_list)
一个线性表是n个数据元素的有限序列。
一个数据元素可以由多个数据项(item)组成,这个时候把数据元素称为记录(record),含有大量记录的线性表又称为文件(file)。
同一线性表中的元素必定具有相同特性,即属同一数据对象。
线性表中元素的个数n(n>=0)定义为线性表的长度,n=0时称为空表。
在非空表中的每个数据元素都有一个确定的位置,a[i]是第i个数据元素,称i为数据元素a[i]在线性表中的位序。
线性表的长度可根据需要而变化,对线性表的数据元素不仅可以访问,还可以进行插入和删除等。
抽象数据类型线性表的定义如下:
ADT List{
数据对象:D={a[i],i=1,2,...,n,n>=0}
数据关系:R1={<a[i-1],a[i]>,i=2,...,n}
基本操作:
initList(&L)
操作结果:构造一个空的线性表
destroyList(&L)
初始条件:线性表已存在
操作结果:销毁线性表L
clearList(&L)
初始条件:线性表L已存在
操作结果:将L重置为空表
listEmpty(&L)
初始条件:线性表L已存在
操作结果:若L为空表,则返回TRUE,否则返回FALSE
listLength(&L)
初始条件:线性表L已存在
操作结果:返回L中数据元素个数
GetElem(&L,i,e)
初始条件:线性表L已存在,1<=i<=listLength(&L)
locateElem(&L,e,compare())
初始条件:线性表L已存在,compare()是数据元素判定函数
操作结果:返回L中第1个与e满足关系compare()的数据元素的位序,若这样的元素不存在,则返回0
priorElem(&L,cur_e,e)
初始条件:线性表L已存在
操作结果:若cur_e是L的数据元素,且不是第一个,则用e返回它的前驱,否则操作失败
nextElem(&L,cur_e,e)
初始条件:线性表L已存在
操作结果:若cur_e是L的数据元素,且不是最后一个,则用e返回它的后继,否则操作失败
listInsert(&L,i,e)
初始条件:线性表L已存在,1<=i<=listLength(&L)+1
操作结果:在L中第i个位置之前插入新的数据元素e,L的长度+1
listDelete(&L,i,e)
初始条件:线性表L已存在且非空,1<=i<=listLength(L)
操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1
listTraverse(L,visit())
初始条件:线性表L已存在
操作结果:依次对L的每个数据元素调用函数visit(),一旦visit()失败,则操作失败
}ADT List
C语言程序模拟线性表如下:
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 11
typedef int elemType;
typedef struct{
elemType *list;
int length;
}sqList;
/*1.初始化线性表L,分配内存空间*/
void initList(sqList *L){
L->length = 0;
L->list = malloc(MAXSIZE * sizeof(elemType));
if(!L->list){
printf("空间分配失败!\n");
exit(0);
}
printf("空间分配成功!\n");
return;
}
/*2.销毁线性表,释放内存空间*/
void destroyList(sqList *L){
if(!L->list){
printf("该线性表不存在!\n");
exit(0);
}
free(L->list);
L->list = NULL;
L->length = 0;
printf("线性表销毁成功!\n");
return;
}
/*3.将线性表置为空表,不释放存储空间*/
void clearList(sqList *L){
if(L->list != NULL){
L->length = 0;
}
return;
}
/*4.若L为空表,则返回TRUE,否则返回FALSE*/
int listEmpty(sqList *L){
return L->length == 0 ? TRUE : FALSE;
}
/*5.返回线性表L中数据元素的个数*/
int listLength(sqList *L){
return L->length;
}
/*6.获取线性表中指定位置的元素*/
elemType getElem(sqList *L,int i){
if(i<1 || i >listLength(L)){
printf("序号越界!");
exit(0);
}
return L->list[i-1];
}
/*7.返回L中第1个等于e的数据元素的位序,不存在,则返回0*/
int locateElem(sqList *L,elemType e){
elemType *p = L->list;
int i=0;
while(i<listLength(L) && *p!=e){
p++;
i++;
}
if(i == listLength(L)){
i=0;
}
return i+1;
}
/*8.若cur_e是L的数据元素,且不是第一个,则用e返回它的前驱,否则操作失败*/
elemType priorElem(sqList *L,elemType cur_e){
int i;
elemType *p = L->list;
for(i=1;i<listLength(L);i++,p++){
if(*p == cur_e){
break;
}
}
if(i == listLength(L)){
printf("输入的不是该线性表的元素!");
exit(0);
}
if(i == 1){
printf("输入的元素没有前驱元素!");
exit(0);
}
return L->list[i-2];
}
/*9.若cur_e是L的数据元素,且不是最后一个,则用e返回它的后继,否则操作失败*/
elemType nextElem(sqList *L,elemType cur_e){
int i;
elemType *p = L->list;
for(i=1;i<listLength(L);i++,p++){
if(*p == cur_e){
break;
}
}
if(i == listLength(L)){
printf("输入的不是该线性表的元素!");
exit(0);
}
if(i == listLength(L)-1){
printf("输入的元素没有后继元素!");
exit(0);
}
return L->list[i];
}
/*10.在线性表L中第i个位置之前插入新的数据元素e,L的长度+1*/
void listInsert(sqList *L,int i,elemType e){
if(i < 1 || i >listLength(L)+1){
printf("序号越界,插入失败!\n");
exit(0);
}
if(listLength(L) >= MAXSIZE){
printf("元素已满,不能插入\n");
exit(0);
}
int j=listLength(L);
while(j >= i){
L->list[j] = L->list[j-1];
j--;
}
L->list[i-1] = e;
L->length++;
return;
}
/*11.删除线性表L的第i个元素,并使用e返回,L长度-1*/
void listDelete(sqList *L,int i,elemType e){
if(i < 1 || i >listLength(L)){
printf("序号越界,插入失败!\n");
exit(0);
}
e = L->list[i-1];
while(i<listLength(L)+1){
L->list[i-1] = L->list[i];
i++;
}
L->length--;
}
/*12.依次对线性表L的每个元素调用函数visit()*/
void listTraverse(sqList *L){
int i;
for(i=0;i<listLength(L);i++){
printf("%d ",L->list[i]);
}
printf("\n");
return;
}
int main(){
sqList L;
initList(&L);
int i;
for(i=1;i<=10;i++){
listInsert(&L,i,i);
}
listTraverse(&L);
elemType e;
listDelete(&L,5,e);
listTraverse(&L);
e = L.list[3];
printf("元素 %d 下一个元素是: %d\n",e,nextElem(&L,e));
printf("元素 %d 前一个元素是: %d\n",e,priorElem(&L,e));
printf("元素 %d 的位序是: %d\n",e,locateElem(&L,e));
printf("线性表的第 %d 个元素是 : %d\n",9,getElem(&L,9));
printf("当前线性表长度为:%d\n",listLength(&L));
destroyList(&L);
return 0;
}
分享到:
相关推荐
数据结构线性表一元多项式的表示及相加PPT学习教案.pptx
其它课程c线性表一PPT教案学习.pptx
2.4 线性表的应用:一元多项式的表示及运算2.4.1 一元多项式的表示2.4.2一元多项式的实现其中一元多项式代码在VS13中运行无误。
该源程序是数据结构的代码实现:用线性表实现一个一元多项式Polynomial
实验一 线性表及其应用 一、 实验目的和要求 1、掌握线性表的插入、删除、查找等基本操作设计与实现 2、学习利用线性表提供的接口去求解实际问题 3、熟悉线性表的的存储方法 二、 实验内容和原理 1、实验内容:设计...
我自己写的一个线性表一个枚,供大家参考,哈哈
将这个线性表拆分成一个奇数线性表和一个偶数线性表线,性表的最大长度为20.
将一个整数线性表拆分成奇数和偶数线性表,课后习题,完整好用
educoder数据结构与算法线性表第2关:实现一个链接存储的线性表 定义线性表节点的结构.pdf
本ppt简述数据结构线性表一章 一、线性表逻辑结构 (a1, a2, ……ai-1, ai, ai+1, …….an) n(n>=0)个元素的有限集。每个元素的类型是相同 的,元素之间的位置关系是一维(线性)的。 二、线性表存储结构 1. 顺序...
要求完成两个同样功能的程序,一个程序采用顺序存储结构,另一个程序采用链表实现线性表的存储。其中链表实现时,要求利用两个升序链表的结点实现归并,即归并时不能新建结点,归并后原来两个升序链表的存储空间不在...
一、 实验目的: (1) 理解线性表的逻辑结构、两种存储结构和数据操作; (2) 应用顺序表的基本算法实现集合A=AUB算法,应用顺序表的基本算法实现两有序顺序表的归并算法; (3) 掌握单链表的遍历、插入和删除等...
线性表小程序,C#,可以实现线性表中某一元素的删除、插入,及线性表的连接,绝对原创,拿出来和大家分享一下,望大家多提宝贵意见
可以使用链表实现,也可以使用顺序表实现 具体要求如下: 能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减 能够计算一元多项式在x处的值 能够计算一元多项式的导数(选作) ...
线性表基本操作的实现,分别采用数组和链表结构实现线性表,实现线性表的基本操作。 利用实现的线性表,存储一元n次多项式,完成多项式的输入、显示;实现多项式的加法操作
数据结构:线性表求一元多项式的值,用C++实现
清华大学出版社Java版数据结构关于线性表一章的课件,含基本框架内容和代码实例,便于理解和学习
数据结构课程中要求用线性表实现一个多项式,这是完整的实验报告.
线性表的顺序存储,此程序主要实现线性表的顺序存储,有C++语言实现,还是比较轻易看得懂的!
线性表存储结构(五选一):1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能:1、 构造:使用头插法、尾插法两种方法2、 插入:要求建立的链表按照关键字从小到大...