前言:本篇文章我们来详细的讲解一下顺序的有关知识,这篇文章中博主会以C语言的方式实现顺序表。以及用顺序表去实现通讯录的代码操作。
目录
一.顺序表的概念
二.顺序表的分类
1.静态顺序表
三.动态顺序表的实现
1.顺序表的初始化
2.顺序表的尾插
3.顺序表的尾删
4.顺序表的头插
5.顺序表的头删
6.打印顺行表
7.查找表内元素
编辑 8.指定位置插入
9.指定位置删除
10.销毁顺序表
四.顺序表所有实现代码
五.结言
一.顺序表的概念
在学习顺序表之前我们要了解顺序表的概念:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删。
笼统的说就是顺序表是一种存储结构,也就是我们所说的数据结构。
那么什么是数据结构呢?
其实我们最早接触到的数据结构就是数组,一种在连续的空间内存储数据的结构。
简单来说存储数据的结构就是数据结构,在日常生活中我们避免不了的要对数据进行增删查改,那么这就要基于我们的数据结构来实现了。
二.顺序表的分类
1.静态顺序表
所谓的静态顺序表就是:使用定长数组存储元素。
也就是使用一个固定的空间来存放。
2.动态顺序表
所谓的静态顺序表就是:使用动态开辟的数组存储。
在后续的操作中如果空间不够则会扩容。
三.动态顺序表的实现
动态顺序表就是基于静态顺序表的改造升级款,所以我们只对动态顺序表进行讲解,下面会有代码以及详细的讲解。
1.顺序表的初始化
首先我们需要做好对于我们顺序表的准备工作,以防随机值以及其他意外情况的发生:
void SLinit(SL* sl)
{assert(sl);sl->a = NULL;sl->capacity = sl->size = 0;
}
首先防止的就是向我们的函数传递一个空指针,所以在这里断言一下。
并把我们顺序表的内容进行初始化。、
2.顺序表的尾插
void SLbackpush(SL* sl, SLType x)
{assert(sl);if (sl->capacity == sl->size){int newcapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLType* temp = (SLType*)realloc(sl->a,sizeof(SLType) * newcapacity);if (temp == NULL){perror("malloc error!");return;}sl->capacity = newcapacity;sl->a = temp;}sl->a[sl->size] = x;sl->size++;
}
在进行插入的同时我们需要进行对空间的判断判断是否还有空间,之后再进行插入。由于我们后续还要进行我们的头插,以及指定位置插入所以我们可以将判断是否还有空间包装成一个函数,方便后续的使用。
void IfCapacity(SL* sl)
{assert(sl);if (sl->capacity == sl->size){int newcapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLType* temp = (SLType*)realloc(sl->a, sizeof(SLType) * newcapacity);if (temp == NULL){perror("malloc error!");return;}sl->capacity = newcapacity;sl->a = temp;}
}
void SLbackpush(SL* sl, SLType x)
{assert(sl);IfCapacity(sl);sl->a[sl->size] = x;sl->size++;
}
就像这样。
3.顺序表的尾删
void SLbackpop(SL* sl)
{assert(sl);sl->size--;
}
这个就简单很多了,就是将 size-- 这样当插入下一个数据的时候就会将要删除的数据覆盖,以达到尾删的目的。
4.顺序表的头插
void SLheadpush(SL* sl, SLType x)
{assert(sl);IfCapacity(sl);for (int i = sl->size; i >0; i--){sl->a[i] = sl->a[i - 1];}sl->a[0] = x;sl->size++;
}
与尾删不一样的就是需要将原有的数据像后挪动一格,之后再进行头插也没有什么可以说的。
5.顺序表的头删
void SLhedpop(SL* sl)
{assert(sl);for (int i = 0; i < sl->size-1; i++){sl->a[i] = sl->a[i + 1];}sl->size--;
}
时我们也只是需要将后面的数据向前挪动一格将第一个数据覆盖即可。
6.打印顺行表
void SLprint(SL* sl)
{assert(sl);for (int i = 0; i < sl->size; i++){printf("%d->", sl->a[i]);}printf("\n");
}
这个就是很简单的打印函数了没有什么好讲的。
7.查找表内元素
int SLfind(SL* sl,SLType x)
{assert(sl);int i = 0;while (sl->a[i]!=x&&i<sl->size){i++;}if (i == sl->size){return 0;}return i;
}
同样这也没有什么好说的遍历顺序表当遇到寻找元素时退出循环,返回元素所在的位置。没有找到则返回0。
8.指定位置插入
void Slrandompush(SL* sl, int flag, SLType x)
{assert(sl);assert(flag < sl->size);IfCapacity(sl);for (int i = sl->size; i >= flag; i--){sl->a[i] = sl->a[i - 1];}sl->a[flag] = x;sl->size++;
}
9.指定位置删除
void SLrandompop(SL* sl, int flag)
{assert(sl);assert(flag < sl->size);for (int i = flag; i < sl->size-1; i++){sl->a[i] = sl->a[i + 1];}sl->size--;
}
10.销毁顺序表
void SLdestory(SL* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->capacity = 0;sl->size = 0;
}
以防空间的浪费要将使用完的空间free掉。
四.顺序表所有实现代码
SL.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define CP 20
//typedef int SLType;//typedef strcuct SL
//{
// SLType* a[CP];
// int size;
//}SL;
typedef int SLType;typedef struct SL
{SLType* a;int size;int capacity;
}SL;void SLinit(SL* sl);
void SLbackpush(SL* sl, SLType x);
void SLbackpop(SL* sl);
void SLheadpush(SL* sl, SLType x);
void SLhedpop(SL* sl);
void SLprint(SL* sl);
int SLfind(SL* sl,SLType);
void Slrandompush(SL* sl, int flag,SLType x);
void SLrandompop(SL* sl, int flag);
void SLdestory(SL* sl);SL.c
#include"SL.h"void SLinit(SL* sl)
{assert(sl);sl->a = NULL;sl->capacity = sl->size = 0;
}
void IfCapacity(SL* sl)
{assert(sl);if (sl->capacity == sl->size){int newcapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLType* temp = (SLType*)realloc(sl->a, sizeof(SLType) * newcapacity);if (temp == NULL){perror("malloc error!");return;}sl->capacity = newcapacity;sl->a = temp;}
}
void SLbackpush(SL* sl, SLType x)
{assert(sl);IfCapacity(sl);sl->a[sl->size] = x;sl->size++;
}
void SLbackpop(SL* sl)
{assert(sl);sl->size--;
}
void SLheadpush(SL* sl, SLType x)
{assert(sl);IfCapacity(sl);for (int i = sl->size; i >0; i--){sl->a[i] = sl->a[i - 1];}sl->a[0] = x;sl->size++;
}
void SLhedpop(SL* sl)
{assert(sl);for (int i = 0; i < sl->size-1; i++){sl->a[i] = sl->a[i + 1];}sl->size--;
}
void SLprint(SL* sl)
{assert(sl);for (int i = 0; i < sl->size; i++){printf("%d->", sl->a[i]);}printf("\n");
}
int SLfind(SL* sl,SLType x)
{assert(sl);int i = 0;while (sl->a[i]!=x&&i<sl->size){i++;}if (i == sl->size){return 0;}return i;
}
void Slrandompush(SL* sl, int flag, SLType x)
{assert(sl);assert(flag < sl->size);IfCapacity(sl);for (int i = sl->size; i >= flag; i--){sl->a[i] = sl->a[i - 1];}sl->a[flag] = x;sl->size++;
}
void SLrandompop(SL* sl, int flag)
{assert(sl);assert(flag < sl->size);for (int i = flag; i < sl->size-1; i++){sl->a[i] = sl->a[i + 1];}sl->size--;
}
void SLdestory(SL* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->capacity = 0;sl->size = 0;
}test.c#include "SL.h"void Test()
{SL sl = { 0 };SLbackpush(&sl, 1);SLheadpush(&sl, 0);SLbackpush(&sl, 2);SLbackpush(&sl, 3);SLbackpush(&sl, 4);SLbackpush(&sl, 5);SLprint(&sl);//if (SLfind(&sl, 100))//{// printf("找到了\n");//}//else//{// printf("没有找到\n");//}int flag = SLfind(&sl, 4);Slrandompush(&sl, flag, 9);SLprint(&sl);//SLrandompop(&sl, flag);//SLprint(&sl);}
int main()
{Test();return 0;
}
五.结言
这就是我们顺序表的实现内容了,当然还有一些其他的功能,但都是万变不离其中。无非就是插入与删除其中要注意我们元素的位置移动。但有了这些功能对于大部分的问题都可以解决了。
下一篇给大家详细讲解一下基于顺序表对通讯录的实现。
如果有喜欢的大家请一键三连感谢了!!!
看到之后肯定会回的。拜拜了!!!