🌱博客主页:大寄一场.
🌱系列专栏:数据结构与算法
😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注
目录
前言
顺序表概念及结构
静态代码实现:
动态代码实现:
SeqList.h文件
SeqList.c文件
test.c文件
前言
本章节博主将会带领大家了解数据结构的线性结构的顺序表。
提到线性结构那么不得不先说说说线性表:
线性表:逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现,数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。
顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
![【数据结构】线性结构 之 顺序表](https://imgs.yssmx.com/Uploads/2023/05/464420-3.png)
文章来源地址https://www.toymoban.com/news/detail-464420.html
顺序表概念及结构
![【数据结构】线性结构 之 顺序表](https://imgs.yssmx.com/Uploads/2023/05/464420-4.png)
![【数据结构】线性结构 之 顺序表](https://imgs.yssmx.com/Uploads/2023/05/464420-5.png)
静态代码实现:
/*第一部分内容:头文件包含和常量定义*/
#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;
}
}
}
动态代码实现:
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;
}
文章来源:https://www.toymoban.com/news/detail-464420.html
到了这里,关于【数据结构】线性结构 之 顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!