【数据结构】线性结构 之 顺序表

目录

前言

顺序表概念及结构

静态代码实现：

动态代码实现：

SeqList.h文件

SeqList.c文件

test.c文件

---

前言

本章节博主将会带领大家了解数据结构的线性结构的顺序表。

提到线性结构那么不得不先说说说线性表：

线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串 ...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以   顺序结构 （ 顺序表 ）和 链式结构 ( 链表 )的形式存储

线性表，顺序表，链表的区别

线性表：逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。

顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。

---

 

顺序表概念及结构

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用 。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素 。

 

2. 动态顺序表：使用动态开辟的数组存储。

 

静态代码实现：

/*第一部分内容：头文件包含和常量定义*/
#include <stdio.h>
#include <stdlib.h> 
#define OK 1
#define ERROR 0
#define MAXSIZE 100
/*第二部分内容：先用typedef确定元素类型，*/
typedef int ElemType;
typedef struct
{
	ElemType elem[MAXSIZE];
	int last;
}SeqList;
/*第三部分，自定义函数*/
int  Locate(SeqList L, ElemType e)
{
	int i = 0;
	/*i为扫描计数器，初值为0，即从第一个元素开始比较*/
	while ((i <= L.last) && (L.elem[i] != e))		/*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
		i++;
	if (i <= L.last)
		return(i + 1);  /*若找到值为e的元素，则返回其序号*/
	else
		return(-1);  /*若没找到，则返回空序号*/
}
int ListInsert(SeqList* L, int i, ElemType e)
{
	int k;
	if ((i < 1) || (i > L->last + 2)) /*首先判断插入位置是否合法*/
	{
		printf("插入位置i值不合法");
		return(ERROR);
	}
	if (L->last >= MAXSIZE - 1)
	{
		printf("表已满无法插入");
		return(ERROR);
	}
	for (k = L->last; k >= i - 1; k--)   /*为插入元素而移动位置*/
		L->elem[k + 1] = L->elem[k];
	L->elem[i - 1] = e;   /*在C语言数组中，第i个元素的下标为i-1*/
	L->last++;
	return(OK);
}
int  DelList(SeqList* L, int i, ElemType* e)
/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */
{
	int k;
	if ((i < 1) || (i > L->last + 1))
	{
		printf("删除位置不合法!");
		return(ERROR);
	}
	*e = L->elem[i - 1];  /* 将删除的元素存放到e所指向的变量中*/
	for (k = i; k <= L->last; k++)
		L->elem[k - 1] = L->elem[k];  /*将后面的元素依次前移*/
	L->last--;
	return(OK);
}
void Print(SeqList* L)
{
	printf("表中的元素为:\n");
	for (int i = 0; i < L->last; i++)
		printf("%4d", L->elem[i]);
	printf("\n");
}
void InitList(SeqList* L)
{

	for (int i = 0; i < MAXSIZE; i++)
		L->elem[i] = 0;
	L->last = 0;           //空表
}

void menu()
{
	printf("=============================================================== \n");
	printf("			           顺序表基本操作                           \n");
	printf("--------------------------------------------------------------- \n");
	printf("                       1.输出顺序表\n");
	printf("                       2.查找数据元素\n");
	printf("                       3.插入数据元素\n");
	printf("                       4.删除第i个元素\n");
	printf("                       0.退出\n");
	printf("================================================================= \n");

}
/*第四部分，main函数*/
void main()
{
	SeqList H;
	int a;
	int m, i, e, select;
	InitList(&H);            // 初始化表格 
	ListInsert(&H, 1, 5);      //将 5,3,4,6,6,6,9依次插入表格 
	ListInsert(&H, 2, 3);
	ListInsert(&H, 3, 4);
	ListInsert(&H, 4, 6);
	ListInsert(&H, 5, 6);
	ListInsert(&H, 6, 6);
	ListInsert(&H, 7, 9);
	menu();
	while (1)
	{
		SeqList L;
		printf("\n请输入选项：");
		scanf("%d", &select);
		switch (select)
		{
		case 0:
			exit(0);
			break;
		case 1:
			Print(&H);
			break;
		case 2:
		{
			printf("请输入你要查找的某个元素");
			scanf("%d", &m);

			a = Locate(H, m);
			if (a == -1)
				printf("没找到！");
			else
				printf("找到了，它的元素下标为%d", a);
			break;
		}
		case 3:
			printf("请输入插入位置i和插入的数据元素e: ");
			scanf("%d %d", &i, &e);
			ListInsert(&H, i, e);
			Print(&H);
			break;
		case 4:
			printf("请输入删除位置i: ");
			scanf("%d", &i);
			DelList(&H, i, &e);
			Print(&H);
			break;
		}
	}
}

---

动态代码实现：

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了，空

间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间

大小，所以下面我们实现动态顺序表。

SeqList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
#define N 10

typedef struct SeqList
{
	SLDataType* a;
	int size;	 //有效数据个数
	int capacity;//空间的容量
}SL;

void SLInit(SL* ps);//创建
void SLDestory(SL* s);//销毁
void SLExpend(SL* s);//增容
void Push_Back(SL* ps, SLDataType x);//尾插
void Pop_Back(SL* ps);//尾删
void SLPrint(SL* ps);//打印
void Push_Front(SL* ps, SLDataType x);//头插
void Pop_Front(SL* ps);//头删

SeqList.c文件

#include"SeqList.h"

void SeqInit(SL* ps)
{
	ps->a= (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
	}
	ps->size = 0;
	ps->capacity= INIT_CAPACITY;
}

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

void SLExpend(SL* s)
{
	SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType)*s->capacity * 2);
	if (tmp == NULL)
	{
		perror("realloc fail");
		return;
	}
	s->a = tmp;
	s->capacity *= 2;
	printf("扩容成功\n");
}

void Push_Back(SL* ps, SLDataType x)
{
	if (ps->capacity == ps->size)
	{
		SLExpend(ps);
	}
	ps->a[ps->size++] = x;
}

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	puts("");
}

void Pop_Back(SL* ps)
{
	if (ps->size == 0)
	{
		return;
	}
	ps->size--;
}

void Push_Front(SL* ps, SLDataType x)
{
	if (ps->capacity == ps->size)
	{
		SLExpend(ps);
	}
	int end = ps->size;
	while (end)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void Pop_Front(SL* ps)
{
	int pos = 1;
	while (pos < ps->size)
	{
		ps->a[pos - 1] = ps->a[pos];
		pos++;
	}
	ps->size--;
}

test.c文件

#include"SeqList.h"

int main(void)
{
	SL s;
	SeqInit(&s);
	Push_Back(&s, 1);
	Push_Back(&s, 2);
	Push_Back(&s, 8);
	Push_Back(&s, 8);
	Push_Front(&s, 100);
	Push_Front(&s, 99);
	Push_Front(&s, 98);
	SLPrint(&s);
	Pop_Front(&s);
	Pop_Front(&s);
	SLPrint(&s);
	printf("%d %d", s.capacity, s.size);
	return 0;
}