数据结构与算法之线性表基础——顺序表（C与C++双人打）
·
线性表
线性表的特点
对于非空的线性表或线性结构，其特点是：
- （1）存在唯一的一个被称作“第一个”的数据元素；
- （2）存在唯一的一个被称作“最后一个”的数据元素；
- （3）除第一个之外，结构中的每个数据元素均只有一个前驱；
- （4）除最后一个之外，结构中的每个数据元素均只有一个后继。
抽象数据类型线性表的定义
每一个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
采用顺序存储的线性表称为顺序表，采用链式存储的线性表称为链表。链表又分为单链表、双向链表和循环链表
顺序表存储结构
静态分配
动态分配
数组下标与位序
结构体定义的解释说明
问题1：使用typedef有什么用处？
问题2：为什么使用ElemType作为数据类型？
问题2：使用ElemType是为了让算法的通用性更好，因为使用线性表的结构体定义后，并不清楚具体问题处理的数据是什么类型，不能简单地写成某一种类型。结合typedef使用，可以提高算法的通用性和可移植性。
顺序表的基本操作
下面以动态分配空间的方法为例，分别介绍顺序表的初始化、创建、取值、查找、插入、删除等基本操作。
初始化
初始化是指为顺序表分配一段预定义大小的连续空间，用elem记录这段空间的基地址，当前空间内没有任何数据元素，因此元素的实际个数为0。假设我们已经预定义了一个最大空间数Maxsize，那么就用new分配大小为Maxsize的空间，分配成功会返回空间的首地址，分配失败会返回空指针。
#include<bits/stdc++.h>
using namespace std;
#define Maxsize 100
typedef struct SqList{
ElemType *elem; //顺序表基地址
int length; //表内已装的空间大小
int listSize; //可容纳的总空间大小
}SqList;
bool InitList(SqList &L)
{
L.elem = new int[Maxsize];
if(!L.elem)
{
return false;
}
L.length = 0;
L.listSize = Maxsize;
return true;
}
创建
顺序表创建是向顺序表中输入数据，输入数据的类型必须与类型定义中的类型一致。
算法步骤
- 1）初始化下标变量i=0，判断顺序表是否已满，如果是则结束；否则执行第2步。
- 2）输入一个数据元素x。
- 3）将数据x存入顺序表的第i个位置，即L.elem[i]=x，然后i++。
- 4）顺序表长度加1，即L.length++。
- 5）直到数据输入完毕。
当然如果想更完美的顺序表，即当顺序表满了就动态增加数组长度，这样确实可以，但是又要申请一块更大的连续地址空间来存放新顺序表，所以一般当顺序表满了，我们就停止插入，如果你是完美主义者，接下来你可以完善代码，我这里只是给一个框架
图解
bool CreateList(SqList &L)
{
int x, i = 0;
cin >> x;
while(x != -1)
{
if(L.length == Maxsize)
{
cout << "顺序表已满！" << endl;
return false;
}
cin >> x;
L.elem[i++] = x;
L.length++;
cin>>x;
}
return true;
}
按位取值
顺序表中的任何一个元素都可以立即找到，称为随机存取方式。例如，要取第i个元素，只要i值是合法的（1≤i≤L.length），那么立即就可以找到该元素。由于下标是从0开始的，因此第i个元素，其下标为i-1，即对应元素为L.elem[i-1]
注意：位序是指第几个元素，位序和下标差1。
bool GetElem(SqList L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
return true;
}
按值查找
在顺序表中查找一个元素e，可以从第一个元素开始顺序查找，依次比较每一个元素值。如果相等，则返回元素位置（位序，即第几个元素）；如果查找整个顺序表都没找到，则返回-1。
例如，在图2-11的顺序表中，查找元素8，查找到其下标为5，返回位序为6。
int LocateElem(SqList L, int e)
{
for(int i = 0; i < L.length; i++)
{
if(L.elem[i] == e)
{
return i + 1; //下标为i，实际上为第i + 1个元素
}
return -1; //没找到
}
}
算法复杂度分析
如果顺序表的表长为n，即n=L.length，那么可以分最好、最坏和平均3种情况分析顺序表查找算法的复杂性。
因此，假设每个关键字查找的概率均等，顺序表查找算法的平均时间复杂度为O(n)。
插入
在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始，后移一位……直到把第i个元素也后移一位，然后把e放入第i个位置
算法步骤
- 1）判断插入位置i是否合法（1≤i≤L.length+1），可以在第一个元素之前插入，也可以在第L.length+1个元素之前插入。
- 2）判断顺序表的存储空间是否已满。
- 3）将第L.length至第i个元素依次向后移动一个位置，空出第i个位置。
- 4）将要插入的新元素e放入第i个位置。
- 5）表长加1，插入成功返回true。
图解
例：在图2-13的顺序表中的第5个位置之前插入一个元素9。
bool ListInsert_Sq(SqList &L, int i, int e)
{
if(i < 1 || i > L.length + 1)
{
return false;
}
if(L.length >= Maxsize)
{
return false;
}
for(int j = L.length; j >= i; j--)
{
L.elem[j] = L.elem[j - 1];
}
L.elem[i - 1] = e;
L.length++;
return true;
}
算法复杂度分析
删除
在顺序表中删除第i个元素，需要把该元素暂存到变量e中，然后从i+1个元素开始前移……直到把第n个元素也前移一位，即可完成删除操作
算法步骤
- 1）判断删除位置i是否合法（1≤i≤L.length）。
- 2）将欲删除的元素保存在e中。
- 3）将第i+1至第n个元素依次向前移动一个位置。
- 4）表长减1，删除成功，返回true。
图解
例：从图2-20的顺序表中删除第5个元素。
删除过程如下
bool ListDelete_Sq(SqList &L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
for(int j = i; j <= L.length; j++)
{
L.elem[j - 1] = L.elem[j];
}
L.length--;
return true;
}
算法复杂度分析
动态增加数组长度
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len)
{
int *p = L.data;
L.data = (int *)malloc((L.Maxsize + len) * sizeof(int));
for(int i = 0; i < L.length; i++)
{
L.data[i] = p[i];
}
L.Maxsize = L.Maxsize + len;
free(p);
}
终于可以好好玩弄一下顺序表了（C++版）
#include<bits/stdc++.h>
using namespace std;
#define Maxsize 10
#define INCREMENT 10
typedef int ElemType;
typedef struct SqList{
ElemType *elem; //顺序表基地址
int length; //表内已装的空间大小
int listSize; //可容纳的总空间大小
}SqList;
bool IncreaseSize(SqList &L)
{
int *p = L.elem;
L.elem = new ElemType[L.listSize + INCREMENT];
if(!L.elem)
{
return false;
}
L.length = 0;
L.listSize += INCREMENT;
delete(p);
return true;
}
bool InitList(SqList &L)
{
cout << "开始初始化..." << endl;
L.elem = new int[Maxsize];
if(!L.elem)
{
return false;
}
L.length = 0;
L.listSize = Maxsize;
cout << "初始化已完成..." << endl;
return true;
}
bool CreateList(SqList &L)
{
cout << "开始创建顺序表..." << endl;
int x, i = 0;
cin >> x;
while(x != -1)
{
if(L.length == Maxsize)
{
cout << "顺序表已满！" << endl;
return false;
}
L.elem[i++] = x;
L.length++;
cin>>x;
}
cout << "顺序表创建完毕..." << endl;
return true;
}
bool GetElem(SqList L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
return true;
}
int LocateElem(SqList L, int e)
{
for(int i = 0; i < L.length; i++)
{
if(L.elem[i] == e)
{
return i + 1; //下标为i，实际上为第i + 1个元素
}
return -1; //没找到
}
}
bool ListInsert_Sq(SqList &L, int i, int e)
{
cout << "顺序表开始插入元素..." << endl;
if(i < 1 || i > L.length + 1)
{
return false;
}
if(L.length == Maxsize)
{
// return false;
IncreaseSize(L);
}
for(int j = L.length; j >= i; j--)
{
L.elem[j] = L.elem[j - 1];
}
L.elem[i - 1] = e;
L.length++;
cout << "顺序表结束插入元素" << endl;
return true;
}
bool ListDelete_Sq(SqList &L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
for(int j = i; j <= L.length; j++)
{
L.elem[j - 1] = L.elem[j];
}
L.length--;
return true;
}
void PrintSqList(SqList &L)
{
for(int i = 0; i < L.length; i++)
{
cout << L.elem[i] << " ";
}
cout << endl;
}
int main()
{
SqList R;
InitList(R);
CreateList(R);
ListInsert_Sq(R, 3, 3);
PrintSqList(R);
return 0;
}
运行结果
说句实话，上面那个代码有缺陷，以下是改动过的代码
#include<bits/stdc++.h>
using namespace std;
#define Maxsize 10
#define INCREMENT 10
typedef int ElemType;
typedef struct SqList{
ElemType *elem; //顺序表基地址
int length; //表内已装的空间大小
int listSize; //可容纳的总空间大小
}SqList;
bool IncreaseSize(SqList &L)
{
int *p = L.elem;
L.elem = new ElemType[L.listSize + INCREMENT];
if(!L.elem)
{
return false;
}
for(int i = 0; i < L.length; i++)
{
L.elem[i] = p[i];
}
L.listSize += INCREMENT;
delete(p);
return true;
}
bool InitList(SqList &L)
{
cout << "开始初始化..." << endl;
L.elem = new int[Maxsize];
if(!L.elem)
{
return false;
}
L.length = 0;
L.listSize = Maxsize;
cout << "初始化已完成..." << endl;
return true;
}
bool CreateList(SqList &L)
{
cout << "开始创建顺序表..." << endl;
int x, i = 0;
cin >> x;
while(x != -1)
{
if(L.length == Maxsize)
{
cout << "顺序表已满！" << endl;
return false;
}
L.elem[i++] = x;
L.length++;
cin>>x;
}
cout << "顺序表创建完毕..." << endl;
return true;
}
bool GetElem(SqList L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
return true;
}
int LocateElem(SqList L, int e)
{
for(int i = 0; i < L.length; i++)
{
if(L.elem[i] == e)
{
return i + 1; //下标为i，实际上为第i + 1个元素
}
return -1; //没找到
}
}
bool ListInsert_Sq(SqList &L, int i, int e)
{
cout << "顺序表开始插入元素..." << endl;
if(i < 1 || i > L.length + 1)
{
return false;
}
if(L.length >= Maxsize)
{
// return false;
cout << "增加顺序表容量" << endl;
IncreaseSize(L);
}
for(int j = L.length; j >= i; j--)
{
L.elem[j] = L.elem[j - 1];
}
L.elem[i - 1] = e;
L.length++;
cout << "顺序表结束插入元素" << endl;
return true;
}
bool ListDelete_Sq(SqList &L, int i, int &e)
{
if(i < 1 || i > L.length)
{
return false;
}
e = L.elem[i - 1];
for(int j = i; j <= L.length; j++)
{
L.elem[j - 1] = L.elem[j];
}
L.length--;
return true;
}
void PrintSqList(SqList &L)
{
for(int i = 0; i < L.length; i++)
{
cout << L.elem[i] << " ";
}
cout << endl;
}
int main()
{
SqList R;
InitList(R);
CreateList(R);
ListInsert_Sq(R, 3, 3);
ListInsert_Sq(R, 6, 6);
ListInsert_Sq(R, 3, 6);
ListInsert_Sq(R, 6, 3);
ListInsert_Sq(R, 3, 10);
ListInsert_Sq(R, 3, 310);
PrintSqList(R);
return 0;
}
运行结果
顺序表的优点
操作简单，存储密度高，可以随机存取，只需要O(1)的时间就可以取出第i个元素。
顺序表的缺点
需要预先分配最大空间，最大空间数估计过大或过小会造成空间浪费或溢出。插入和删除操作需要移动大量元素。在实际问题中，如果经常需要插入和删除操作，则顺序表的效率很低。为了克服该缺点，可以采用链式存储。
相关代码的实现
人狠话不多，干货先上咯，先来个简单的线性表基本构造代码
普通环境下就可以运行的代码
C代码：
#include<stdio.h>
#define MAX 10
struct SList{
int data[MAX];
int length;
};
void init(struct SList *p)
{
p->length = 0;
}
void printList(const struct SList* p)
{
int i;
for(i = 0; i < p->length; i++)
{
printf("%d ", p->data[i]);
}
putchar('\n');
}
int insert(struct SList *p, int k, int x)
{
if(k < 0 || k > p->length || p->length == MAX - 1)
{
/*表示插入失败 */
return 0;
}
else /*插入成功 */
{
int i;
for(i = p->length - 1; i >= k; i--)
{
p->data[i + 1] = p->data[i];
}
p->data[k] = x;
p->length++;
return 1;
}
}
int delete1(struct SList *p, int k, int *px)
{
if(k < 0 || k >= p->length)
{
return 0;
}
else
{
int i;
*px = p->data[k];
for(i = k; i < p->length; i++)
{
p->data[i] = p->data[i + 1];
}
p->length--;
return 1;
}
}
int main()
{
struct SList a;
/* a.length = 0;
*/
init(&a);
/*k表示要插入的位置
x表示要插入的元素
insert(&a, k, x);
*/
insert(&a, 0, 11);
insert(&a, 0, 22);
insert(&a, 1, 33);
int x;
printList(&a);
delete1(&a, 1, &x);
printList(&a);
printf("We deleted %d\n", x);
return 0;
}
C++代码：
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
int main()
{
vector<int> v;
v.push_back(11);
v.push_back(22);
v.push_back(33);
v.insert(v.begin() + 2, 666);
v.erase(v.begin() + 1);
// vector<int>::iterator it;
// for(it = v.begin(); it != v.end(); it++)
// {
// cout << *it << ", ";
// }
// cout << endl;
for(int i : v)
{
cout << i << ", ";
}
cout << endl;
return 0;
}
在Linux环境上运行的代码
seq.h
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100 //定义线性表的最大长度
typedef struct
{
char key[15]; //结点的关键字
char name[20];
int age;
}DATA; //定义结点类型，可定义为简单类型，也可定义为结构
typedef struct //定义顺序表结构
{
DATA ListData[MAXSIZE + 1]; //保存顺序表的数组
int ListLen; //顺序表已存结点 的数量
}SeqListType;
//void SeqListInit(SeqListType *SL); //初始化顺序表
//int SeqListLength(SeqListType *SL); //返回顺序表的元素数量
//int SeqListAdd(SeqListType *SL,DATA data); //向顺序表中添加元素
//int SeqListInsert(SeqListType *SL,int n,DATA data); //向顺序表中插入元素
//int SeqListDelete(SeqListType *SL,int n); //删除顺序表中的据元素
//DATA *SeqListFindByNum(SeqListType *SL,int n); //根据序号返回元素
//int SeqListFindByCont(SeqListType *SL,char *key); //按关键字查找
//int SeqListAll(SeqListType *SL); //遍历顺序表中的内容
void SeqListInit(SeqListType *SL) //初始化顺序表
{
SL->ListLen = 0; //初始化时，设置顺序表长度为0
}
int SeqListLength(SeqListType *SL) //返回顺序表的元素数量
{
return (SL->ListLen);
}
int SeqListAdd(SeqListType *SL, DATA data) //增加元素到顺序表尾部
{
if(SL->ListLen >= MAXSIZE) //顺序表已满
{
printf("顺序表已满，不能再添加结点了！\n");
return 0;
}
SL->ListData[++SL->ListLen] = data;
return 1;
}
int SeqListInsert(SeqListType *SL, int n, DATA data)
{
int i;
if(SL->ListLen >= MAXSIZE) //顺序表结点数量已超过最大数量
{
printf("顺序表已满，不能插入结点!\n");
return 0; //返回0表示插入不成功
}
if(n < 1 || n > SL->ListLen - 1) //插入结点序号不正确
{
printf("插入元素序号错误，不能插入元素！\n");
return 0; //返回0，表示插入不成功
}
for(i = SL->ListLen; i >= n; i--) //将顺序表中的数据向后移动
SL->ListData[i + 1] = SL->ListData[i];
SL->ListData[n] = data; //插入结点
SL->ListLen++; //顺序表结点数量增加1
return 1; //返回成功插入
}
int SeqListDelete(SeqListType *SL, int n) //删除顺序表中的数据元素
{
int i;
if(n < 1 || n > SL->ListLen + 1) //删除元素序号不正确
{
printf("删除结点序号错误，不能删除结点！\n");
return 0; //返回0，表示删除不成功
}
for(i = n; i < SL->ListLen; i++) //将顺序表中的数据向前移动
SL->ListData[i] = SL->ListData[i + 1];
SL->ListLen--; //顺序表元素数量减1
return 1; //返回成功删除
}
DATA *SeqListFindByNum(SeqListType *SL, int n) //根据序号返回数据元素
{
if(n < 1 || n > SL->ListLen + 1) //元素序号不正确
{
printf("结点序号错误，不能返回结点！\n");
return NULL; //返回0，表示不成功
}
return &(SL->ListData[n]);
}
int SeqListFindByCont(SeqListType *SL, char *key) //按关键字查询结点
{
int i;
for(i = 1; i <= SL->ListLen; i++)
if(strcmp(SL->ListData[i].key, key) == 0) //如果找到所需结点
return i; //返回结点序号
return 0; //遍历后仍没有找到，则返回0
}
seqtest.c
#include <stdio.h>
#include "seq.h"
int SeqListAll(SeqListType *SL) //遍历顺序表中的结点
{
int i;
for(i = 1; i <= SL->ListLen; i++)
printf("(%s, %s, %d)\n", SL->ListData[i].key, SL->ListData[i].name, SL->ListData[i].age);
}
int main()
{
int i;
SeqListType SL; //定义顺序表变量
DATA data, *data1; //定义结点保存数据类型变量和指针变量
char key[15]; //保存关键字
SeqListInit(&SL); //初始化顺序表
do{ //循环添加结点数据
printf("输入添加的结点(学号 姓名 年龄)：");
fflush(stdin); //清空输入缓冲区
scanf("%s %s %d", &data.key, &data.name, &data.age);
if(data.age) //若年龄不为0
{
if(!SeqListAdd(&SL,data)) //若添加结点失败
break; //退出死循环
}else //若年龄为0
break; //退出死循环
}while(1);
printf("\n顺序表中的结点顺序为：\n");
SeqListAll(&SL); //显示所有结点数据
fflush(stdin); //清空输入缓冲区
printf("\n要取出结点的序号：");
scanf("%d",&i); //输入结占点序号
data1=SeqListFindByNum(&SL,i); //按序号查找结点
if(data1) //若返回的结点指针不为NULL
printf("第%d个结点为：(%s,%s,%d)\n", i, data1->key, data1->name, data1->age);
fflush(stdin); //清空输入缓冲区
printf("\n要查找结点的关键字：");
scanf("%s",key); //输入关键字
i=SeqListFindByCont(&SL,key); //按关键字查找 ，返回结点序号
data1=SeqListFindByNum(&SL,i); //按序号查询，返回结点指针
if(data1) //若结点指针不为NULL
printf("第%d个结点为：(%s,%s,%d)\n",i,data1->key,data1->name,data1->age);
printf("\n要插入的结点及其所要插入的位置（位置 结点）");
DATA data2;
int j;
scanf("%d %s %s %d", &j, data2.key, data2.name, &data2.age);
SeqListInsert(&SL, j, data2);
printf("\n顺序表中的结点顺序为：\n");
SeqListAll(&SL);
int k;
printf("\n要删除的结点位置");
scanf("%d", &k);
if(SeqListDelete(&SL, k))
printf("Delete Successfully\n");
printf("\n顺序表中的结点顺序为：\n");
SeqListAll(&SL);
//getch();
return 0;
}
我的样例运行结果如下：
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献4条内容
所有评论(0)