我们终于可以学习第一个数据结构的知识了！首先先了解线性表的概念

定义：

线性表是由零个或多个相同类型的元素组成的有限序列。每个元素在表中都有一个前驱元素（除第一个元素外）和后继元素（除最后一个元素外）

线性表的两种常见实现方式：

顺序表（数组）
链表（链式结构）

由定义可知由n(n>=0)个数据特性相同的元素构成的有限序列,称为线性表，即线性表是n个数据元素的有限序列,其中n个数据是相同数据类型的

线性表中元素个数 n(n>=0) 定义为线性表的长度，当n等于零时称之为空表

对于非空的线性表或线性结构,其特点是:

存在唯一的一个被称作”第一个”的数据元素并且存在唯一的一个被称作”最后一个”的数据元素除第一个元素外,

结构中的每个数据元素均只有一个前驱(即前一个元素) 以及除最后一个元素外,结构中的每个数据元素均只有一个后驱(即后一个元素)

这个我们先讲顺序表

顺序表

顺序表（即数组）是一种线性表的数据结构，它包含一组相同类型的数据元素，这些元素按顺序存储在连续的内存空间中。每个元素在顺序表中的位置是固定的，可以通过索引（下标）直接访问

由定义可以知道 , 我们前几篇中回顾的struct结构体不是顺序表,而是一个容器,因为结构体中的元素是无序的,而像数组这样每个索引元素的位置是固定的

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct book{
	int isbn;
	char bookName[20];
	double price;
};

int main(){
	struct book b;
	b.isbn=767645;
	strcpy(b.bookName,"Dune");
	b.price=70;
	return 0;
}

可以看出访问结构体成员没有顺序

顺序表的特点

元素类型必须相同。所有元素都必须是同一种数据类型（例如，都为 int，float 等）
元素按顺序存储，每个元素都有一个确定的位置，可以通过下标访问
**可以是静态的（如固定大小数组）**或动态的（如通过动态内存分配的数组）

以下所有功能我都会封装在函数里,3个语言都是,你们在main函数里修改一下即可

什么你问我为啥另外两种语言用lua 和 C# 而不是 Java 和 C++ ? emmm , 当然是我现在正在学习Unity 和 Love2d做游戏,而这两个游戏引擎分别使用C# 和 Lua写脚本 (毕竟我想把学到的东西快速投入到实践中,只是目前还不知道数据结构有什么用狗头狗头狗头)

顺序表的初始化

C版本

#include <stdio.h>
#define MAXSIZE 100	//设置最大值防止数组越界

//定义表元素类型位整型
typedef int ElemType;

//构造结构体(或者说对象)
typedef struct{
	ElemType data[MAXSIZE];
	int length;
}SeqList;

//初始化表的长度为0的函数
void initList(SeqList*L){
    //-> 是 C/C++ 的“通过指针访问结构体/类成员”的运算符
    //L 是指向 SeqList 的指针,L->length = 0; 等价于 (*L).length = 0;  如果是普通对象而非指针,用点号：list.length = 0;
	L->length=0;
}

int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
	printf("初始化成功,目前长度占用%d\n",list.length);
	printf("目前占用内存%zu字节\n",sizeof(list.data));
	return 0;
	
}

Lua版本

用lua表示就是如下

lua因为比较自由没有太多的限制

local SeqList = {}
SeqList.__index = SeqList

--构造函数
function SeqList:new()
    local instance = setmetatable({}, SeqList)
    instance:initList()
    return instance
end

--初始化
function SeqList:initList()
    self.data = {}
end

--获取顺序表长度
function SeqList:getLength()
    return #self.data
end

local function main()
    local list = SeqList:new()
    -- 也直接用 #list.data 获取长度
    print(string.format("初始化成功, 目前长度占用:" .. list:getLength()))
end

main()

C#版本

在C#里我们可以用面向对象的思想来实现顺序表的初始化,在C#里 List 类似于C里面的数组

// 定义 ElemType 为 int 类型
using ElemType = System.Int32;

//定义顺序表类
public class SeqList
{
    public List<ElemType> data = new List<ElemType>();// 存储顺序表元素的动态数组
    public int length// 顺序表当前长度
    {
        get { return data.Count; }
    }

    //之所以构造函数,是因为实例化时会自动调用构造函数
    public SeqList()
    {
        initList();
    }

    // 初始化函数
    public void initList()
    {
        data = new List<ElemType>();
    }
}

class Program
{
    static void Main(string[] args)
    {

        SeqList list = new SeqList();// 创建顺序表实例

        Console.WriteLine($"初始化成功,目前长度占用{list.length}");

        // C# 是托管内存，无法像 C 一样用 sizeof(list.data) 这种方式看预分配的字节大小
        // Capacity 属性可以看到底层数组当前分配的容量（个数，不是字节）
        Console.WriteLine($"目前内部数组容量(Capacity): {list.data.Capacity}");
    }
}

顺序表的尾插法

C版本

//尾部添加元素
int appendElem(SeqList*L,ElemType e){
    //先判断表长度是否超过规定值
	if(L->length>=MAXSIZE){
		printf("顺序表已满\n");
		return 0;
	}
 
	L->data[L->length]=e;//C语言数组索引从0开始,data[length]处刚好是尾部可添加的位置,而data[length-1]才是末尾的位置
	L->length++;//添加后把长度自动增加一下
	return 1;
}
int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
	printf("初始化成功,目前长度占用%d\n",list.length);
	printf("目前占用内存%zu字节\n",sizeof(list.data));
	appendElem(&list,88);
	return 0;
	
}

Lua版本

--插入元素
function SeqList:appendElem(e)
    table.insert(self.data, e)
    return 1
end

local function main()
    local list = SeqList:new()

    -- 直接用 #list.data 获取长度
    print(string.format("初始化成功, 目前长度占用:" .. list:getLength()))

    -- 添加元素
    list:appendElem(88)
    list:appendElem(100)

    -- 再次查看长度
    print(string.format("目前长度占用:" .. list:getLength()))

    -- 验证一下数据
    print(string.format("第一个元素: %d, 第二个元素: %d", list.data[1], list.data[2]))
end

main()

C#版本

//定义顺序表类
public class SeqList
{
   //添加元素
    public int appendElem(int e)
    {
        //使用Add
        data.Add(e);
        return 1;
    }
}

class Program
{
    static void Main(string[] args)
    {

        SeqList list = new SeqList();// 创建顺序表实例

        Console.WriteLine($"初始化成功,目前长度占用{list.length}");

        list.appendElem(88);
        Console.WriteLine($"目前长度占用: {list.length}");
    }
}

顺序表的遍历

C版本

//遍历
void listElem(SeqList *L){
	for(int i=0;i<L->length;i++){
		printf("%d ",L->data[i]);
	}
	printf("\n");
}

int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
	printf("初始化成功,目前长度占用%d\n",list.length);
	printf("目前占用内存%zu字节\n",sizeof(list.data));
	appendElem(&list,88);
	appendElem(&list,45);
	appendElem(&list,43);
	appendElem(&list,17);
	listElem(&list);
	
	return 0;
}

Lua版本

--遍历 
function SeqList:listElem()
    -- ipairs 自动遍历数组部分的 index 和 value(不推荐,这种方法和C#里的foreach差不多)
    for v in ipairs(self.data) do
        io.write(v .. "\n")
    end
    --或者(推荐,lua自带的遍历表函数)
    print(table.concat(self.data, "\n"))
end

local function main()
    local list = SeqList:new()

    -- 添加元素
    list:appendElem(88)
    list:appendElem(100)

    -- 遍历顺序表
    print("顺序表元素如下:")
    list:listElem()
end

main()

C#版本

//定义顺序表类
public class SeqList
{
    //遍历 
    public void listElem()
    {
        //第一种 foreach遍历
        foreach (var item in data)
        {
            Console.WriteLine(item);
        }
        
        //或者使用 string.Join
    	Console.WriteLine(string.Join("\n", data));
    }
    
}

class Program
{
    static void Main(string[] args)
    {

        SeqList list = new SeqList();// 创建顺序表实例

        list.appendElem(23);
        list.appendElem(45);
        list.appendElem(88);
        Console.WriteLine("顺序表的元素有:");
        list.listElem();// 遍历顺序表
    }
}

顺序表的删除

C版本

//删除
//pos=position  即删除位置
int deleteElem(SeqList*L,int pos,ElemType*e){
	if(L->length==0){
		printf("空表\n");
		return 0;
	}
	if(pos<1||pos>L->length){
		printf("删除数据位置有误\n");
		return 0;
	}
	
	*e=L->data[pos-1];
	if(pos<L->length){
		for(int i=pos;i<L->length;i++){
			L->data[i-1]=L->data[i];
		}
	}
	L->length--;
	return 1;
}
int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
	appendElem(&list,88);
	appendElem(&list,45);
	appendElem(&list,43);
	appendElem(&list,17);
	listElem(&list);
	
	ElemType delData;
	deleteElem(&list,2,&delData);
	printf("被删除的数据为:%d\n",delData);
	listElem(&list);
	
	return 0;
}

Lua版本

--删除元素
function SeqList:deleteElem(pos)
    if #self.data == 0 then
        print("空表")
        return nil
    end
    if pos < 1 or pos > #self.data then
        print("删除数据位置有误")
        return nil
    end

    -- table.remove 会移除指定位置元素,并自动前移后续元素
    -- 它直接返回被移除的值
    local e = table.remove(self.data, pos)
    return e
end

local function main()
    local list = SeqList:new()

    -- 添加元素
    list:appendElem(88)
    list:appendElem(100)

    -- 遍历顺序表
    print("顺序表元素如下:")
    list:listElem()

    -- 删除(第一种,查看被删除的是谁)
    local delData = list:deleteElem(2)
    print("删除第2个位置的数据后,被删除的数据为:" .. delData)
    list:listElem()

    --删除(第二种,不需要看)
    list:deleteElem(2)
    print("删除第2个位置的数据后,顺序表元素如下:")
    list:listElem()
end

main()

C#版本

//定义顺序表类
public class SeqList
{
     //删除
    public int deleteElem(int pos, out ElemType e)
    {
        e = 0; // out 参数必须赋值

        if (length == 0)
        {
            Console.WriteLine("空表");
            return 0;
        }
        if (pos < 1 || pos > length)
        {
            Console.WriteLine("删除数据位置有误");
            return 0;
        }

        // 取出要删除的元素
        e = data[pos - 1];

        //直接调用 List.RemoveAt,底层自动处理移位
        data.RemoveAt(pos - 1);

        return 1;
    }
}

class Program
{
    static void Main(string[] args)
    {

        SeqList list = new SeqList();// 创建顺序表实例

        list.appendElem(23);
        list.appendElem(45);
        list.appendElem(88);
        Console.WriteLine("顺序表的元素有:");
        list.listElem();// 遍历顺序表

        ElemType deletedElem;//模拟C版本的可以查看删除的是什么
        list.deleteElem(2, out deletedElem);
        list.listElem();// 遍历顺序表
        Console.WriteLine("被删除的元素是:" + deletedElem);
    }
}

顺序表的指定位置插入

C版本

//指定位置插入
int insertElem(SeqList*L,int pos,ElemType e){
	if(L->length>=MAXSIZE){
		printf("表已经满了\n");
		return 0;
	}
	if(pos<1||pos>L->length){
		printf("插入位置错误\n");
		return 0;
	}
	if(pos<=L->length){
		for(int i=L->length-1;i>=pos-1;i--){
			L->data[i+1]=L->data[i];
		}
		L->data[pos-1]=e;
		L->length++;
	}
	return 1;
}
int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
	printf("初始化成功,目前长度占用%d\n",list.length);
	printf("目前占用内存%zu字节\n",sizeof(list.data));
	appendElem(&list,88);
	appendElem(&list,45);
	appendElem(&list,43);
	appendElem(&list,17);
	listElem(&list);
	insertElem(&list,2,18);
	listElem(&list);
	
	return 0;
}

顺序表的查找

C版本

//查找
int findElem(SeqList*L,ElemType e){
	if(L->length==0){
		printf("空列表\n");
		return 0;
	}
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			return i+1;
		}
	}
	return 0;
}

int main(){
	//声明一个顺序表并初始化
	SeqList list;
	initList(&list);
    
	appendElem(&list,88);
	appendElem(&list,45);
	appendElem(&list,43);
	appendElem(&list,17);
	listElem(&list);
	
	insertElem(&list,2,18);
	listElem(&list);
    
    int number=1;
	printf("找到%d位置的数据值为%d",number,findElem(&list,number));
	
	return 0;
}

顺序表的动态分配内存并初始化

C版本

//动态分配内存地址初始化
SeqList* initList(){
	SeqList*L=(SeqList*)malloc(sizeof(SeqList));
	L->data =(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
	L->length=0;
	return L;
}

int main(){
	//声明一个线性表并初始化
	SeqList *list=initList();

	appendElem(list,88);
	appendElem(list,45);
	appendElem(list,43);
	appendElem(list,17);
	listElem(list);
	
	insertElem(list,2,18);
	listElem(list);
	
	printf("%d\n",findElem(list,40));	
	return 0;
}

暂时没有精力去兼顾lua和C#版本的吧,毕竟快考试了,以后我再慢慢补票吧

数据结构第三天----线性表和顺序表的学习

我们终于可以学习第一个数据结构的知识了！首先先了解线性表的概念

线性表的两种常见实现方式：

顺序表

顺序表的特点

顺序表的初始化

C版本

Lua版本

C#版本

顺序表的尾插法

C版本

Lua版本

C#版本

顺序表的遍历

C版本

Lua版本

C#版本

顺序表的删除

C版本

Lua版本

C#版本

顺序表的指定位置插入

C版本

顺序表的查找

C版本

顺序表的动态分配内存并初始化

C版本

评论区

数据结构第三天----线性表和顺序表的学习

我们终于可以学习第一个数据结构的知识了！首先先了解线性表的概念

线性表的两种常见实现方式：

顺序表

顺序表的特点

顺序表的初始化

C版本

Lua版本

C#版本

顺序表的尾插法

C版本

Lua版本

C#版本

顺序表的遍历

C版本

Lua版本

C#版本

顺序表的删除

C版本

Lua版本

C#版本

顺序表的指定位置插入

C版本

顺序表的查找

C版本

顺序表的动态分配内存并初始化

C版本

分享这篇文章到

评论区