数据结构(二)

╰半橙微兮° 2022-08-20 10:09 140阅读 0赞

数据结构\-线性结构：数组、链表

数组的原理，底层实现。在c语言中，有int arr\[\]，java有String arr\[\]，ArrayList。但他们在底层是如何实现的，比如ArrayList的add，remove函数的底层c代码，下面是完整的程序：

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    struct Arr
    {
    	int * pBase;//储存的数组的首地址
    	int len;//数组能够容纳的最大元素个数
    	int cnt;//数组元素的有效个数
    };
    
    void init_arr(struct Arr * pArr,int length);//初始化
    bool append_arr(struct Arr * pArr,int val);//追加
    bool insert_arr(struct Arr * pArr,int pos,int val);//插入
    bool delete_arr(struct Arr * pArr,int pos,int * pval);//删除
    int get();//获取
    bool is_empty(struct Arr * pArr);//是否为空
    bool is_full(struct Arr * pArr);//是否满了
    void sort_arr(struct Arr * pArr);//排序
    void show_arr(struct Arr * pArr);//显示
    void inversion_arr(struct Arr * pArr);//倒序
    
    int main(void)
    {
    	struct Arr arr;
    	int pval;
    	printf("原先数组\n");
    	init_arr(&arr,6);
    	//show_arr(&arr);
    	append_arr(&arr,1);
    	append_arr(&arr,2);
    	append_arr(&arr,3);
    	append_arr(&arr,4);
    	append_arr(&arr,5);
    	show_arr(&arr);
    	printf("删除后数组\n");
    	if(delete_arr(&arr,3,&pval))
    	{
    		printf("删除了 %d\n",pval);
    	}
    	show_arr(&arr);
    	printf("倒序后数组\n");
    	inversion_arr(&arr);
    	show_arr(&arr);
    	printf("排序后数组\n");
    	sort_arr(&arr);
    	show_arr(&arr);
    	return 0;
    }
    
    void init_arr(struct Arr * pArr,int length)
    {
    	pArr->pBase=(int *)malloc(sizeof(int) * length);
    	if(NULL == pArr->pBase)
    	{
    		printf("动态内存分配失败!\n");
    		exit(-1);
    	}
    	else
    	{
    		pArr->len = length;
    		pArr->cnt = 0;
    	}
    }
    
    bool is_empty(struct Arr * pArr)
    {
    	if(0 == pArr->cnt)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    bool is_full(struct Arr * pArr)
    {
    	if(pArr->len == pArr->cnt)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    void show_arr(struct Arr* pArr)
    {
    	if(is_empty(pArr))
    	{
    		printf("数组为空!\n");
    	}
    	else
    	{
    		for(int i=0;i<pArr->cnt;i++)
    		{
    			printf("%d    ",pArr->pBase[i]);
    		}
    		printf("\n");
    	}
    }
    
    bool append_arr(struct Arr * pArr,int val)
    {
    	if(is_full(pArr))
    	{
    		return false;
    	}
    	pArr->pBase[pArr->cnt] = val;
    	(pArr->cnt)++;
    	return true;
    }
    
    bool insert_arr(struct Arr * pArr,int pos,int val)
    {
    	int i;
    	if(is_full(pArr))
    	{
    		return false;
    	}
    	if(pos<1 || pos>pArr->len)
    	{
    		return false;
    	}
    	for(i=pArr->cnt-1;i>pos-1;i++)
    	{
    		pArr->pBase[i+1]=pArr->pBase[i];
    	}
    	pArr->pBase[pos-1]=val;
    	return true;
    }
    
    bool delete_arr(struct Arr * pArr,int pos,int * pval)
    {
    	int i;
    	if(is_empty(pArr))
    	{
    		return false;
    	}
    	if(pos<1 || pos>pArr->cnt)
    	{
    		return false;
    	}
    	*pval =pArr->pBase[pos-1];
    	for(i=pos;i<pArr->cnt;i++)
    	{
    		pArr->pBase[i-1]=pArr->pBase[i];
    	}
    	pArr->cnt--;
    	return true;
    }
    
    void inversion_arr(struct Arr * pArr)
    {
    	int i=0;
    	int j=pArr->cnt-1;
    	int t;
    	while(i<j)
    	{
    		t=pArr->pBase[i];
    		pArr->pBase[i]=pArr->pBase[j];
    		pArr->pBase[j]=t;
    		i++;
    		j--;
    	}
    	return;
    }
    
    void sort_arr(struct Arr * pArr)
    {
    	int i,j,t;
    	for(i=0;i<pArr->cnt;i++)
    	{
    		for(j=i+1;j<pArr->cnt;j++)
    		{
    			if(pArr->pBase[i]>pArr->pBase[j])
    			{
    				t=pArr->pBase[i];
    				pArr->pBase[i]=pArr->pBase[j];
    				pArr->pBase[j]=t;
    			}
    		}
    	}
    	return;
    }

![Center][]

函数的功能：

初始化函数：void init\_arr(struct Arr \* pArr,int length);初始化的作用是向系统请求内存分配给结构体指针，如果没有初始化，结构体指针保存的是垃圾数字。

排序函数：void sort\_arr(struct Arr \* pArr)；是用冒泡法，每一次比较将大的往后移。

ArrayList的方法在底层差不多就是这样了。

在定义结构体时，为了方便，可以使用typedef，PSTU代表struct Student \*,STU 代表struct Student

例如：

![Center 1][]

链表：链表是数据结构的基础，树和图的实现基本靠链表实现

定义：

n个结点离散分配

彼此通过指针相连

每个结点只有一个前驱结点，每个结点只有一个后续结点

首结点没有前驱结点，尾结点没有后续结点

专业术语：

首结点

第一个有效结点

尾结点

最后一个有效结点

头结点

第一个有效结点前面的结点

头结点并不存放有效数据

加头结点的目的是方便对链表的操作

头指针

指向首结点的指针变量

尾指针

指向尾结点的指针变量

确定一个链表只需要一个参数：头指针

![Center 2][]

链表的分类：

单链表

双链表：每一个结点都有一个指针域

循环链表：能通过任何一个结点找到所有的结点

非循环链表

结点插入原理：将q结点插在p结点和r结点中间

1.r=p->pNext;p->pNext=q->pNext;q->pNext=r;

2.q->pNext=p->pNext;p->pNext=q;

[Center]: /images/20220731/a471c9d8096244e5a76c1c6fac01ffb6.png
[Center 1]: /images/20220731/2ee7825f29314ed19585892a6cab20c7.png
[Center 2]: /images/20220731/3f30477b53b042a0b175fdca133c1f3d.png