数据结构与算法（2）：顺序表与链表

1.前言

哈喽大家好喔，今天博主继续进行数据结构的分享与学习，今天的主要内容是顺序表与链表，是最简单但又相当重要的数据结构，为以后的学习有重要的铺垫，希望大家一起交流学习，互相进步，让我们开始吧。

2.正文

数据结构是计算机科学中非常重要的一部分，用于组织和管理数据以便高效地访问和修改。顺序表和链表是两种常见且基础的数据结构，它们各有特点和适用场景。以下是对这两种数据结构的详细分析：

2.1顺序表

顺序表是在计算机内存中以数组的形式保存的线性表。其有点类似数组，但添加了几个额外的概念。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

这里面有俩个定义顺序表功能的俩个变量：分别是count和size变量，size是用来确定顺序表的存储空间大小的，count是用来标记顺序表中当前元素位置的。

2.1.1结构特点：

2.1.2结构定义：

typedef struct vector {
    int size, count;
    int *data;
    //总大小,元素数量
//指针指向连续的存储区
} vector;
//初始化
vector *getnewvector(int n) {
    vector *p = (vector *)malloc(sizeof(vector));
    p->size = n;//存储上限
    p->count = 0;
    p->data = (int *)malloc(sizeof(int) * n);
    return p;
}

2.1.3结构操作：

2.1.3.1插入操作：

//插入操作
int insert(vector *v, int pos, int val) {
    if (pos < 0 || pos > v->count) return 0;
    if (v->size == v->count && !expand(v)) return 0;
    for (int i = v->count - 1; i >= pos; i--) {
        v->data[i + 1] = v->data[i];
    }
    v->data[pos] = val;
    v->count += 1;
    return 1;
}

 2.1.3.2删除操作：

//删除操作
void clear(vector *v) {
    if (v == null) return ;
    free(v->data);
    free(v);
    return ;
}

 2.1.3.3销毁操作：

//销毁操作
int erase(vector *v, int pos) {
    if (pos < 0 || pos >= v->count) return 0;
    for (int i = pos + 1; i < v->count; i++) {
        v->data[i - 1] = v->data[i];
    }
    v->count -= 1;
    return 1;
}

2.1.3.4自动扩容操作 ：

//扩容操作
int expand(vector *v) {
    if (v == null) return 0;
    printf("expand v from %d to %d\n", v->size, 2 * v->size);
    int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
    if (p == null) return 0;
    v->data = p;
    v->size *= 2;
    return 1;
}

 完整调试代码：

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

typedef struct vector {
    int size, count;
    int *data;
    //总大小,元素数量
//指针指向连续的存储区
} vector;
//初始化
vector *getnewvector(int n) {
    vector *p = (vector *)malloc(sizeof(vector));
    p->size = n;//存储上限
    p->count = 0;
    p->data = (int *)malloc(sizeof(int) * n);
    return p;
}

int expand(vector *v) {
    if (v == null) return 0;
    printf("expand v from %d to %d\n", v->size, 2 * v->size);
    int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
    if (p == null) return 0;
    v->data = p;
    v->size *= 2;
    return 1;
}
//插入操作
int insert(vector *v, int pos, int val) {
    if (pos < 0 || pos > v->count) return 0;
    if (v->size == v->count && !expand(v)) return 0;
    for (int i = v->count - 1; i >= pos; i--) {
        v->data[i + 1] = v->data[i];
    }
    v->data[pos] = val;
    v->count += 1;
    return 1;
}
//销毁操作
int erase(vector *v, int pos) {
    if (pos < 0 || pos >= v->count) return 0;
    for (int i = pos + 1; i < v->count; i++) {
        v->data[i - 1] = v->data[i];
    }
    v->count -= 1;
    return 1;
}

void output_vector(vector *v) {
    int len = 0;
    for (int i = 0; i < v->size; i++) {
        len += printf("%3d", i);
    }
    printf("\n");
    for (int i = 0; i < len; i++) printf("-");
    printf("\n");
    for (int i = 0; i < v->count; i++) {
        printf("%3d", v->data[i]);
    }
    printf("\n");
    printf("\n\n");
    return ;
}
//删除操作
void clear(vector *v) {
    if (v == null) return ;
    free(v->data);
    free(v);
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20
    vector *v = getnewvector(2);
    for (int i = 0; i < max_op; i++) {
        int op = rand() % 4, pos, val, ret;
        switch (op) {
            case 0:
            case 1:
            case 2:
                pos = rand() % (v->count + 2);//为了可以看到插入到非法位置时程序的反应
                val = rand() % 100;
                ret = insert(v, pos, val);
                printf("insert %d at %d to vector = %d\n", 
                    val, pos, ret);
                break;
            case 3:
                pos = rand() % (v->count + 2);
                ret = erase(v, pos);
                printf("erase item at %d in vector = %d\n", 
                    pos, ret);
                break;
        }
        output_vector(v);
    }
    clear(v);
    return 0;
}

2.2链表

链表是一种物理存储结构上非 连续、非顺序的存储结构，但逻辑上是顺序的。链表由一系列结点（链表中每一个元素称为结点）组成，每个结点包含两个部分：数据域和指针域。数据域用来存储数据，而指针域则用来指向下一个结点。

2.2.1链表的分类：

2.2.2结构特点：

2.2.3结构定义：

typedef struct lnode
{
	int data;
	struct lnode *next;
} lnode, *linklist;

void initlist (linklist *l)   //二级指针的目的是地址传递，因为该函数没有返回值，用地址传递带回头节点地址。
{
	linklist p;
	p = (linklist)malloc(sizeof(lnode));
	if(p == null)
		cout << "申请内存空间失败。" << endl;
	p->next=null;
	*l = p;
	flag++;
}//初始化一个空的链表

2.2.4结构操作：

2.2.4.1创建链表操作：

void creatlist(linklist l,int n)
{
    int i;	
	lnode *p,*pt;
	pt=l;
	for(i=1;i<=n;i++)
	{	
		p=(linklist)malloc(sizeof(lnode));
		if(p==null)
			cout << "申请内存空间失败。" << endl;
		cout << "请输入链表中元素：" << endl;
		cin >> p->data;		
		p->next=pt->next;
		pt->next=p;
		pt=p;
	}
	//flag++;
}//创建链表

 2.2.4.2查找操作：

int getelem(linklist l, int i)
{
	lnode *p;
	int e;
	int j;
	p=l->next;j=1;
	while (p && j<i)
	{
		p=p->next;
		++j;
	}
	if(!p || j>i)
		cout << "该位序不存在。" << endl;
	else
	{
		e=p->data;
		cout << "第" << i << "个元素为：" << e << endl;
	}
	return ok;
}//用e返回l中第i个数据元素的值.

 2.2.4.3插入操作：

int listinsert(linklist l,int i,int e)
{
	int j;
	lnode *p,*s;
	p=l; j=0;
	while(p && j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p || j>i-1)
		return error;
	s=(linklist)malloc(sizeof(lnode));
	if(s==null)
		cout << "申请内存空间失败。" << endl;
	s->data=e;
	s->next=p->next;
	p->next=s;
	cout << "插入的元素是：" << e << endl;
	return ok;
}//在第i个位置插入元素e

2.2.4.1销毁链表操作：

int destroylist(linklist l)
{
	lnode *p;
	p=null;
	if(l && flag!=0)
	{
		while(l)
		{   
			p=l;
			l=l->next;
			free(p);	
		}
		cout << "链表已销毁。" << endl;
	}
	else
		cout << "链表不存在。" << endl;
	return ok;
	flag++;
}//销毁链表

2.3顺序表和链表的比较：

这边列举一个表格方便大家对着俩个功能类似的数据结构的特点有更加充分的理解：

3.小结

今天数据结构第二讲：顺序表与链表到这里就结束了，未来俩天会有链表相关延展问题实现的博客出炉，不要忘了点一手关注再走哦，希望喜欢的朋友多多支持我哦~