数据结构(二)——顺序表
一、抽象数据类型ADT
ADT是一种编程概念,用于定义数据的类型及其操作,而不涉及具体实现细节。它提供了一种将数据的逻辑表示与物理实现分离的方法,从而使程序更具可维护性和可扩展性。
在C语言中,ADT 通常通过结构体和函数的结合来实现。结构体用于定义数据的类型,而函数用于操作这些数据。通过这种方式,程序员可以隐藏数据的内部结构,仅暴露出操作数据的接口。
例如:
设计一台电视机
设计一个复数
复数的表示与实现:
二、线性表的定义与特点
1.由n(n>=0)个数据特性相同的元素构成的有限序列,称为线性表
线性表是n个数据元素的有限序列,其中n个数据是相同数据类型的
线性表中元素的个数n(n>=0)定义为线性表的长度,当n=0时称之为空表
对于非空的线性表或线性结构,其特点是:
(1)存在唯一的一个被称作“第一个”的数据元素;(头节点)
(2)存在唯一的一个被称作“最后一个”的数据元素;(尾节点)
(3)除第一个元素外,结构中的每个数据元素均只有一个前驱(前一个元素);
(4)除最后一个元素外,结构中的每个数据元素均只有一个后继(后一个元素);
例如:图书信息管理系统
2.线性表ADT
三、线性表的顺序存储形式——顺序表
顺序表:用一组连续的内存单元依次存储线性表的各个元素,也就是说,逻辑上相邻的元素,实际的物理存储空间也是连续的
1.顺序表——存储结构
#define MAXSIZE 100
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
2.顺序表——初始化(创建一个顺序表)
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
return 0;
}
运行:
3.顺序表——在尾部添加元素
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
appendElem(&list,88);
return 0;
}
4.顺序表——遍历
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
//遍历
void listElem(Seqlist *L)
{
for(int i=0;i < L->length;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
appendElem(&list,88);
appendElem(&list,45);
appendElem(&list,43);
appendElem(&list,17);
listElem(&list);
return 0;
}
运行:
5.顺序表——插入元素
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
//遍历
void listElem(Seqlist *L)
{
for(int i=0;i < L->length;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
//插入数据
//pos指的是逻辑上插入的位置,从1开始,只有索引从0开始
int insertElem(Seqlist *L,int pos,ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("顺序表已满");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if(pos <= L->length)
{
for(int i = L->length - 1;i >= pos - 1;i--){
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
appendElem(&list,88);
appendElem(&list,45);
appendElem(&list,43);
appendElem(&list,17);
listElem(&list);
insertElem(&list,2,18);
listElem(&list);
return 0;
}
运行:
顺序表插入数据的最好时间复杂度是:O(1)
顺序表插入数据的最坏时间复杂度是:O(n)
6.顺序表——删除元素
原理:删除56后,后面的每一个元素向前覆盖前一个元素,最后剩余一个12没有覆盖,直接length-1即可
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
//遍历
void listElem(Seqlist *L)
{
for(int i=0;i < L->length;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
//插入数据
//pos指的是逻辑上插入的位置,从1开始,只有索引从0开始
int insertElem(Seqlist *L,int pos,ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("顺序表已满");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if(pos <= L->length)
{
for(int i = L->length - 1;i >= pos - 1;i--){
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
//删除元素
int deleteElem(Seqlist *L,int pos,ElemType *e)
{
if(L->length == 0){
printf("空表\n");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1]; //把要删的数据放到e的指针里,pos-1是索引下标
if(pos < L->length)
{
for(int i = pos;i < L->length;i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
appendElem(&list,88);
appendElem(&list,67);
appendElem(&list,40);
appendElem(&list,8);
appendElem(&list,23);
listElem(&list);
insertElem(&list,1,18);
listElem(&list);
ElemType delData;
deleteElem(&list,2,&delData);
printf("被删除的数据是:%d\n",delData);
listElem(&list);
return 0;
}
运行:
7.顺序表——查找
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}Seqlist;
//顺序表初始化
void initList(Seqlist *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
//遍历
void listElem(Seqlist *L)
{
for(int i=0;i < L->length;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
//插入数据
//pos指的是逻辑上插入的位置,从1开始,只有索引从0开始
int insertElem(Seqlist *L,int pos,ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("顺序表已满");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if(pos <= L->length)
{
for(int i = L->length - 1;i >= pos - 1;i--){
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
//删除元素
int deleteElem(Seqlist *L,int pos,ElemType *e)
{
if(L->length == 0){
printf("空表\n");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1]; //把要删的数据放到e的指针里,pos-1是索引下标
if(pos < L->length)
{
for(int i = pos;i < L->length;i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}
//查找
int findElem(Seqlist *L,ElemType e)
{
if(L->length == 0)
{
printf("空表\n");
return 0;
}
for(int i=0;i < L->length;i++)
{
if(L->data[i] == e)
{
return i+1;
//i是下标,i+1返回的是该元素具体的位置
}
}
return 0;
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));
appendElem(&list,88);
appendElem(&list,67);
appendElem(&list,40);
appendElem(&list,8);
appendElem(&list,23);
listElem(&list);
insertElem(&list,1,18);
listElem(&list);
ElemType delData;
deleteElem(&list,2,&delData);
printf("被删除的数据是:%d\n",delData);
listElem(&list);
printf("40所在的位置是:%d\n",findElem(&list,40));
return 0;
}
运行:
8.顺序表——动态分配内存地址初始化
malloc在内存当中开辟一片内存空间
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType *data;
int length;
}Seqlist;
//顺序表初始化--动态分配内存
Seqlist* initList()
{
Seqlist *L = (Seqlist*)malloc(sizeof(Seqlist));
L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
L->length = 0;
return L;
}
//尾部添加元素
int appendElem(Seqlist *L,ElemType e)
{
if(L->length >= MAXSIZE){
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e; //添加元素
L->length++;
return 1; //添加成功
}
//遍历
void listElem(Seqlist *L)
{
for(int i=0;i < L->length;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
//插入数据
//pos指的是逻辑上插入的位置,从1开始,只有索引从0开始
int insertElem(Seqlist *L,int pos,ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("顺序表已满");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if(pos <= L->length)
{
for(int i = L->length - 1;i >= pos - 1;i--){
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
//删除元素
int deleteElem(Seqlist *L,int pos,ElemType *e)
{
if(L->length == 0){
printf("空表\n");
return 0;
}
if(pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1]; //把要删的数据放到e的指针里,pos-1是索引下标
if(pos < L->length)
{
for(int i = pos;i < L->length;i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}
//查找数据位置
int findElem(Seqlist *L,ElemType e)
{
if(L->length == 0)
{
printf("空表\n");
return 0;
}
for(int i=0;i < L->length;i++)
{
if(L->data[i] == e)
{
return i+1;
//i是下标,i+1返回的是该元素具体的位置
}
}
return 0;
}
int main(int argc,char const *argv[])
{
//声明一个顺序表并初始化
Seqlist *list = initList();
printf("初始化成功,目前长度占用%d\n",list->length);
printf("目前占用内存%zu字节\n",sizeof(list->data));
appendElem(list,88);
appendElem(list,67);
appendElem(list,40);
appendElem(list,8);
appendElem(list,23);
listElem(list);
insertElem(list,1,18);
listElem(list);
ElemType delData;
deleteElem(list,2,&delData);
printf("被删除的数据是:%d\n",delData);
listElem(list);
printf("40所在的位置是:%d\n",findElem(list,40));
return 0;
}
运行: