2--顺序表

2024-09-06 06:58

文章标签 顺序

本文主要是介绍2--顺序表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一：线性表的本质

线性表是具有相同类型的n个数据元素的有限序列

二：线性表的相关操作：

创建线性表

销毁线性表

清空线性表

将元素插入线性表

将元素删除线性表

获取线性表中对应位置的元素

获取线性表的长度

获取线性表的最大长度

线性表表现为一种特殊的数据类型

线性表的操作表现为一组相关的函数

线性表的实现方式：顺序存储结构，链式存储结构

优点：无需增加额外的空间

快速获取表中合法的元素

缺点：插入和删除需要移动大量的元素

线性表长度变化较大时难以确定存储空间容量

二：创建可复用的顺序表（sequence）

Seqlist.h

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

//数据封装，包含头文件以后顺序表隐藏实现的细节
typedef void SeqList;
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity);
void SeqList_Destroy(SeqList* list);
void SeqList_Clear(SeqList* list);
int SeqList_Length(SeqList* list);
int SeqList_Capacity(SeqList* list);
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
SeqListNode* SeqList_Get(SeqList* list, int pos);
SeqListNode* SeqList_Delete(SeqList* list, int pos);
#endif

SeqList.c

//顺序表的元素为指针，因为在32位系统中指针为4个字节和unsigned int所占空间一致

typedef unsigned int TSeqListNode;

typedef struct _tag_SeqList
{
int capacity; //线性表的容量
int length; //当前容量的大小
TSeqListNode* node; //node的值是一个地址
} TSeqList;
/*
功能：创建线性表
参数：链表最大元素的个数
返回：
*/
SeqList* SeqList_Create(int capacity) // O(1)
{
TSeqList* ret = NULL;

if( capacity >= 0 )
{
ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
}

if( ret != NULL )
{
ret->capacity = capacity;
ret->length = 0;
ret->node = (TSeqListNode*)(ret + 1); //设计技巧实现node指向0节点的地址
}

return ret;
}
/*
功能：销毁
参数：
返回：
*/
void SeqList_Destroy(SeqList* list) // O(1)
{
free(list);
}
/*
功能：清空
参数：
返回：
*/
void SeqList_Clear(SeqList* list) // O(1)
{
TSeqList* sList = (TSeqList*)list; //SeqList为void,必须进行转换

if( sList != NULL )
{
sList->length = 0;
}
}
/*
功能：获取线性表长度
参数：
返回：-1表示线性表不存在
*/
int SeqList_Length(SeqList* list) // O(1)
{
TSeqList* sList = (TSeqList*)list;
int ret = -1;

if( sList != NULL )
{
ret = sList->length;
}

return ret;
}
/*
功能：获取线性表最大的元素个数
参数：
返回：-1表示线性表不存在
*/
int SeqList_Capacity(SeqList* list) // O(1)
{
TSeqList* sList = (TSeqList*)list;
int ret = -1;

if( sList != NULL )
{
ret = sList->capacity;
}

return ret;
}
//进行修正，传址
int SeqList_Insert(SeqList* list, SeqListNode* node, int *pos) // O(n)
{
TSeqList* sList = (TSeqList*)list;
int ret = (sList != NULL);
int i = 0;

ret = ret && (sList->length + 1 <= sList->capacity); //有足够的空间,没空间了添加不上

ret = ret && (0 <= (*pos));

if( ret )
{
if( (*pos) >= sList->length ) //修正，当前有空间，但插入的位置大于当前顺序表的长度
{
(*pos) = sList->length; //插入到尾部
}

for(i=sList->length; i>(*pos); i--) //移动元素
{
sList->node[i] = sList->node[i-1];
}

sList->node[i] = (TSeqListNode)node;//线性表元素的地址
sList->length++;
}

return ret;
}
//获取顺序表的元素
SeqListNode* SeqList_Get(SeqList* list, int pos) // O(1)
{
TSeqList* sList = (TSeqList*)list;
SeqListNode* ret = NULL;

if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
{
ret = (SeqListNode*)(sList->node[pos]);
}

return ret;
}
//删除顺序表的中的某个位置的元素
SeqListNode* SeqList_Delete(SeqList* list, int pos) // O(n)
{
TSeqList* sList = (TSeqList*)list;
SeqListNode* ret = SeqList_Get(list, pos);
int i = 0;

if( ret != NULL )
{
for(i=pos+1; i<sList->length; i++)
{
sList->node[i-1] = sList->node[i];
}

sList->length--;
}

return ret;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "SeqList.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//顺序表的元素为指向字符串的指针

int main(int argc, char *argv[])
{
SeqList* list = SeqList_Create(5);

int index = 0;
char *str1="ludong";
char *str2="shshs";
char *str3="lili";
char *str4="lala";
char* p=NULL;
int pos=0;
SeqList_Insert(list, str1, &pos);
SeqList_Insert(list, str2, &pos);
SeqList_Insert(list, str3, &pos);

pos=6;
SeqList_Insert(list, str4, &pos);

for(index=0; index<SeqList_Length(list); index++)
{
p = (char*)SeqList_Get(list, index);

printf("%s\n", p);
}

printf("\n");

while( SeqList_Length(list) > 0 )
{
p = (char*)SeqList_Delete(list, 0);

printf("%s\n", p);
}

SeqList_Destroy(list);

return 0;
}