typedef struct DSeqList
{
    int *elem;//指向保存数据的内存
    int length;//有效数据个数
    int listsize;//总格子数
}DSeqList;

typedef DSeqList *PDSeqList;



//初始化函数
void InitDSeqList(PDSeqList plist)//这里的plist自带*
{
    assert(plist != NULL);
    if(plist == NULL)
    {
	return ;
    }

    plist->elem = (int *)malloc(INIT_SIZE*sizeof(int));
    plist->length = 0;
    plist->listsize = INIT_SIZE;
}

主函数中调用

int main()
{
    DSeqList seq;//先定义一个顺序表
    InitDSeqList(&seq);//再对顺序表初始化

  

    return 0;
}


 

2-1 线性表抽象数据类型
线性表


定义：0个 or 多个数据元素的有限序列


特点：

是一个序列 元素之间是有序的  数据元素 之间是 一对一的关系

有限性： 线性表的数据元素的个数是有限的 （食物链中生物的个数是有限的）


常见的操作

创建和初始化 、 查找 、 插入 、 删除（增删改查）

线性表表达：


ADT 线性表（SequenceList） //线性表
Data 
    1、线性表的数据元素是一个集合 {a_1,a_2,a_3...,a_n}, 数据元素的类型DataType{int，char，自定义}
    2、前驱 除了第一个元素a_1外每个元素只有一个直接的前驱元素
    3、后继 除了最后一个元素a_n外，每个元素只有一个直接的后继元素
    4、每个数据元素之间的关系是一对一的关系
Operation
    InitList( *List )                                   //初始化线性表
    InsertElement（*List ， index ， elem）  //在线性表List 的index下标处插入元素elem       
    DeleteElement（*List， index， *elem）  //删除线性表List中第i个元素 并返回删除元素的指针e
    GetLength（*List）                            //得到长度
    IsEmpty（*List）                              //判断是否为空
    ClearList（*List）                            //清空顺序表
    GetElement（*Liset，index ， *elem） //得到指定位置的元素
    
endADT

2-2顺序存储结构的线性表 —— 顺序表
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
描述线性表的顺序存储结构需要三个属性：1. 线性表最大容量 2. 线性表的当前长度 3。存储空间的起始位置
1. 我们需要定义线性表的最大存储空间
#define MAX_SIZE 255
2. 线性表里需要有同一类型的元素集合
typedef int ElemType //这种是给int取了一个别名，其目的是用ElemType自带int 
同理：下面也是这种思想
typedef struct{
    int id,
    char* name;
}ElementType
3、定义顺序表结构
typedef srtuct{
    ElementType datas[ MAX_SIZE] ;
    int length ;
}SeqList;


地址计算方法
约定：

position：表示元素位置 从1开始

index：表示索引下标 从0开始
从0开始实现线性表
1）全局数据结构的头文件 “DataElement.h”
#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
/***********************************************************************
 *  Project:数据结构第二章案例
 *  Function：用来定义数据元素
 *  Author：chillinght
 *
 ***********************************************************************
 *  Copyright：2019 by chillinght
 ***********************************************************************
 */
 #define MAX_SIZE 255
//1、定义数据元素
//typedef int ElementType;
/*
 *datas = {{1,""},{2,""},{3,""}};
 */
typedef struct{
   int id;
   char *name;
 }ElementType;

 //2、定义顺序表结构
 typedef struct{
    ElementType datas[MAX_SIZE];//顺序表中的元素集合
    int length;                 //当前顺序表中元素的个数
 }SeqList;


#endif // DATAELEMENT_H_INCLUDED


2）定义线性表的独有的数据头文件 “SequenceList.h”
#ifndef SEQUENCELIST_H_INCLUDED
#define SEQUENCELIST_H_INCLUDED
/**< 用来定义顺序表的头文件 其中包括方法的定义 */
#include <stdio.h>
#include <stdlib.h>
#include "DataElement.h"

//下面定义顺序表的方法
// 1 初始化 顺序表：需要参数：顺序表头指针、 初始化的元素类型 、 初始化顺序表长度
/**
 * 初始化顺序表
 * @param seqList       要初始化的顺序表名（数组名也就是头指针）
 * @param elemArray     初始化时要添加的元素内容数组
 * @param length        初始化时添加的元素个数
 */
void InitList(SeqList * seqlist, ElementType * elemArray, int length);
// 2 插入 参数：顺序表头指针 、 插入元素类型 、 插入元素位置position/索引值index
/**
 * 向顺序表插入元素
 * @param seqList       顺序表名（数组名也就是头指针）
 * @param index         插入元素下标
 * @param element       元素内容
 */
void InsertElement(SeqList* seqlist,int index,ElementType element );
//3 打印顺序表
void PrintList(SeqList* seqlist);

#endif // SEQUENCELIST_H_INCLUDED


头文件的实现文件(包括其中定义的函数：插入、删除、初始化、打印)  “SequenceList.c”
#include "SequenceList.h"

//下面实现顺序表的方法
// 1 初始化 顺序表：需要参数：顺序表头指针、 初始化的元素类型 、 初始化顺序表长度
/**
 * 初始化顺序表
 * @param seqList       要初始化的顺序表名（数组名也就是头指针）
 * @param elemArray     初始化时要添加的元素内容数组
 * @param length        初始化时添加的元素个数
 */
void InitList(SeqList * seqlist, ElementType * elemArray, int length)
{
    //1 验证传入的length是否超出了max_size 的范围
    //2 调用插入函数进行初始化
    if(length > MAX_SIZE){
        printf("插入的长度太大，请减小length的长度");//这里突然想到 length在main中应该和elemArray长度一样
        return;
    }
    //记得在插入前将 顺序表中的length 置0 否则插入位置不确定
    seqlist->length = 0;
    for(int i = 0; i < length; i++)
    {
        InsertElement(seqlist,i,elemArray[i]);
    }
}

// 2 插入 参数：顺序表头指针 、 插入元素类型 、 插入元素位置position/索引值index
/**
 * 向顺序表插入元素
 * @param seqList       顺序表名（数组名也就是头指针）
 * @param index         插入元素下标
 * @param element       元素内容
 */
void InsertElement(SeqList* seqlist,int index,ElementType element )//其实就是向数组中插入一个元素
{
    //1、验证插入后的元素空间是否超过MAX_SIZE
    //2、index的值是否合法[0,MAX_SIZE - 1]
    //3、插入的index 应该在length 之内
    //4、从后向前第 length - 1 的index位置开始 到index 前面一个元素赋值给后面一个元素。
    //5、将插入的元素赋值给index下标的元素
    //6、顺序表总长度+1
    if(seqlist->length + 1 > MAX_SIZE){
        printf("插入后数据溢出，数组已满，插入失败\n");
        return;
    }
    if(index < 0 || index > MAX_SIZE || index >seqlist->length){
        printf("index数值不合法，请在合法的下标范围[0,%d]内进行插入\n",seqlist->length);
        return;
    }
    for(int i = seqlist->length - 1;i > index - 1;i--)
    {
        seqlist->datas[i+1] = seqlist->datas[i];
    }
    seqlist->datas[index] = element;
    seqlist->length += 1;
}
void PrintList(SeqList * seqlist){
    for(int i = 0; i < seqlist->length;i++){
        printf("%d\t%s\n",seqlist->datas[i].id,seqlist->datas[i].name);
    }
}


测试用例 "main.c"中
#include <stdio.h>
#include <stdlib.h>
#include "SequenceList.h"
#include "DataElement.h"
//测试一下~
void TestSequenceList();


int main()
{
    TestSequenceList();
    return 0;
}
void TestSequenceList()
{
    ElementType dataArray[] = {
    {1,"海绵宝宝"},
    {2,"派大星"},
    {3,"章鱼哥"},
    {4,"蟹老板"},
    {5,"痞老板"}
    };
    SeqList seqlist;
    InitList(&seqlist,dataArray,sizeof(dataArray) / sizeof(dataArray[0]));
    PrintList(&seqlist);
}


测试用例结果

#include <iostream>
#include <cstdlib>
#define MAXSIZE 20  //顺序表的最大长度
#define N 11
using namespace std;

/**
*实现顺序表的初始化和增删改查
*注意:该程序默认顺序表的第0个位置不用，元素从1开始存放
*/

typedef struct
{
    int *elem; //存一个地址,动态分配空间
    int lenth;
}Sqlist;

/****************顺序表初始化函数****************/
void initlist(Sqlist &l)        //用引用
{
    int nums[N]={0,1,2,3,4,5,6,7,8,9,10};
    l.elem = new int[MAXSIZE];  //后面要delete
    if(l.elem == NULL )
    {
        exit(0);                //非正常退出，要引入头文件<cstdlib>
    }else
    {
        for(int i=0;i<N;i++)
        {
             l.elem[i]=nums[i];
        }
        l.lenth=N-1;
    }
}
/****************顺序表查找函数****************/
//查找到就返回元素下标位置，没找到就返回0
int Find_Sq(Sqlist &l , int e) //e是要查找的值
{
    int i=1;
    while(i<=l.lenth && e != l.elem[i])
        i++;
    if(i != l.lenth+1) //表示跳出循环，还没找到，此时i为l.lenth+1
        return i;
    else
        return 0;
}
/****************顺序表插入函数****************/
int Inser_Sq(Sqlist &l , int pos , int num)
{
    if(pos<1 || pos >l.lenth)
        return 0;//插入位置错误
    if(l.lenth >= MAXSIZE -1)
        return 0;//空间已满，无法插入
    for(int i=l.lenth ; i>=pos ; i--)
        l.elem[i+1]=l.elem[i];
    l.elem[pos]=num;
    l.lenth++;
    return 1;
}
/****************顺序表删除函数****************/
int Dele_Sq( Sqlist &l , int pos , int &e) //e保存要删掉的值，所以用引用
{
    e=l.elem[pos];   //e保存要删掉的值
    if(pos<1 || pos >l.lenth)
        return 0;
    for(int i = pos ; i<l.lenth ; i++)
        l.elem[i]=l.elem[i+1];
    l.lenth --;
    return 1;
}
/****************顺序表打印函数****************/
void Print_Sq(Sqlist &l)
{
    for(int i=1;i<=l.lenth;i++)
    {
        cout<<l.elem[i]<<endl;
    }
}
int main()
{
/******************************************/
    //初始化
    Sqlist q;     //创建顺序表
    initlist(q);  //初始化顺序表
/******************************************/
    //顺序表查找元素(表中查找元素99)
    int result = Find_Sq(q,99);
    if(result == 0)
        cout<<"没有找到"<<endl;
    else
        cout<<"找到了，数组下标为"<<result<<endl;
/******************************************/
    //顺序表插入元素(在第三个位置插入数据666)
    Inser_Sq(q , 3 , 666);
/******************************************/
    //顺序表删除元素(把第5个元素删除，并把删除的值保存在e中)
    int e; //接受保存将被删除的元素
    Dele_Sq(q,5,e);
/******************************************/
    Print_Sq(q);
    delete []q.elem;
    return 0;
}

             顺序表在进行初始化操作中必须传地址，否则，一切都是徒劳。

 •以下，通过画图的形式详细介绍为什么要传地址而不能传值



大家了解C语言的肯定知道传值和传址的区别，但是在学习数据结构时不得不强调传址的重要性。

传值：图1.17中程序执行时，先给实参 sl 分配一块存储空间，sl 中包括 data[100] 及 nLength 。紧接着，在调用 initList() 时，为形参 list 分配同样的一块空间 。此时，list 是 sl 的一份拷贝。那么，在执行操作时，使得 list 中的 nLength 为0。此时，函数调用完之后，形参 list 会被释放，返回主函数之后，我们发现 sl 中的 nLength 依然为0，因此顺序表内容并没有被改变。

传址：和上述执行顺序一样，在给形参分配存储空间时，list 获得一块固定大小的空间，并且 list 直接指向实参 数量 sl 。当执行 initList() 时，同时改变了  sl 中 nLength 的值，之后 list 的 释放并没有影响。

综上，在进行初始化操作时，必须通过指针传递，传值是行不通的。采用传值得方式，不仅不能改变实参，而且在很大程度上浪费了更多的时间和空间 。