赞
踩
一.什么线性表
线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中,数据元素之间通过一对一首尾相接的方式连接起来。具体实现时,线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表实现方案:
该方案将线性表存储在一片连续空间里,并通过data
、len
和max
三个属性元素。组织成为一个结构:
data
: 给出线性表存储空间的起始地址;max
: 指明线性表存储空间最多可存储的数据元素个数;len
: 当前线性表里的数据元素个数。为了讨论简化,我们假设每个数据元素是一个整数:
typedef char ElemType; // 数据元素的数据类型
该线性表的结构定义如下:
struct SqList{
ElemType data[i]; // 数据元素存储空间的开始地址
int length; // 线性表的当前长度
};
以上示意图中的L是指向该结构的一个指针,只要给定L指针,就可对线性表进行操作。
对数据元素进行操作处理是一个数据结构的重要组成部分。线性表涉及的主要操作如下:
创建线性表:创建一个最多可存储MaxSize个数据元素的顺序存储的线性表,并将其初始状态设置为length=0
。void CreateList(SqList *& L,ElemType a[],int n)
释放线性表存储空间:释放L->data
所指向的用于存储线性表数据元素的存储空间。该操作函数具体定义如下: void EestorySqlist(SeqList* L);
获取线性表当前长度:获取并返回线性表的当前长度L->length
。该操作函数具体定义如下: int ListLength(SqList *L)
判断线性表是否为空:若当前线性表是空表,则返回false
,否则返回true
。该操作函数具体定义如下:bool ListEmpty(SqList *& L)
返回线性表第i
个数据元素:返回线性表的第i
个数据元素L->data[i]
。该操作函数具体定义如下: bool GetElem(SqList *L,int i,ElemType &e)
在线性表位置i
插入数据元素x
: 将x
插入L->data[i]
之前。若插入失败(i>L->len
gth或i<0
时,无法插入),返回 false
,否则返回 true
。该操作函数具体定义如下:bool ListInsert(SqList *&L,int i,ElemType e)
删除线性表位置i
处的数据元素: 删除线性表的i
号数据元素。输入参数i
范围应在[0,L->length-1]
内,否则会产生不能预料的异常或错误。返回被删除的数据元素的值。该操作函数具体定义如下:bool ListDelete(SqList *&L,int i,ElemType e)
查找线性表中第一个值为e的数据元素的位置: 找到线性表中第一个值为x
的数据元素的编号。返回值-1
表示没有找到,返回值>=0
表示该元素位置。该操作函数具体定义如下: int LocateElem(SqList *L,ElemType e)
打印线性表: 打印整个线性表。该操作函数具体定义如下:void DisList(SqList *L)
线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中,数据元素之间通过一对一首尾相接的方式连接起来。具体实现时,线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表实现方案:
代码展示:
- #include<stdio.h>
- #include<stdio.h>
- #include<malloc.h>
- #define MaxSize 100
- typedef char ElemType;
- typedef struct
- {
- ElemType data[MaxSize]; //存放顺序表元素
- int length; //存放顺序表长度
- /* data */
- }SqList;
-
- void CreateList(SqList *& L,ElemType a[],int n){ //创立线性表
- L =(SqList *)malloc(sizeof(SqList));
- for(int i=0;i<n;i++){
- L->data[i]=a[i];
- }
- L ->length =n;
- }
-
- void InitList(SqList *& L){ //初始化线性表
- L =(SqList *)malloc(sizeof(SqList));
- L ->length =0;
- }
-
- void DestoryList(SqList *&L){ //销毁线性表
- free(L);
- }
-
- bool ListEmpty(SqList *& L){ //判断线性表是否为空
- return (L->length ==0);
- }
-
- int ListLength(SqList *L){ //求线性表的长度
- return L->length;
- }
-
- void DisList(SqList *L){ //输出线性表
- for(int i=0;i<L->length;i++){
- printf("%c",L ->data[i]);
- }
- printf("\n");
- }
-
- bool GetElem(SqList *L,int i,ElemType &e){ //求线性表中第i个元素
- if(i<1||i>L->length){
- return false; //判断是否在表内
- }
- e =L->data[i-1];
- return true;
- }
-
- int LocateElem(SqList *L,ElemType e) { //查找第一个e的位置·
- int i=0;
- while (i<L->length &&L->data[i]!=e)
- {
- i++;
- }
- if(i>=L->length){
- return 0;
- }else {
- return i+1;
- }
-
-
- }
-
- bool ListInsert(SqList *&L,int i,ElemType e){ //插入第i个元素
- int j;
- if(i<1||i>L->length+1||L->length ==MaxSize){
- return false;
- }
- i--;
- for(j =L->length;j>i;j--){
- L->data[j]=L->data[j-1];
- }
- L->data[i]=e;
- L->length++;
- return true;
- }
-
- bool ListDelete(SqList *&L,int i,ElemType e){ //删除第i个元素
- int j;
- if(i<1||i>L->length){
- return false;
- }
- i--;
- e=L->data[i];
- for(j=i;j<L->length;j++){
- L->data[j]=L->data[j+1];
- }
- L ->length--;
- return true;
-
- }
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。