002-线性表及其顺序结构存储实现
本帖最后由 moc 于 2018-9-23 11:43 编辑1、线性表的基本概念
1.定义
线性表（list）是由0个或多个元素组成的集合；
线性表中的数据元素之间是有顺序的；
线性表的数据元素个数是有限的；
线性表中数据元素的类型必须相同。
数学描述：
线性表是具有相同类型的n(n≥0)个数据元素的有限序列（a1, a2, a3, ... , an）,其中ai是表项，n是表的长度。
2.性质
a0为线性表的第一个元素，只有一个后继；
an为线性表的最后一个元素，只有一个前驱；
除了a0和an以外的元素，既有前驱又有后继；
线性表能够逐项访问和顺序存取。
3.线性表的操作
创建线性表；
销毁线性表；
清空线性表；
将元素插入到线性表；
将元素从线性表中删除；
获取线性表某个位置的元素；
获取线性表的长度等。
2、线性表的顺序存储结构
顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
这种存储结构需要提前根据存入元素的最大容量分配空间，一旦分配好，容量是固定的。
设计与实现：
#ifndef _MY_SEQLIST_H__
#define _MY_SEQLIST_H__
#include "stdio.h"
#include "stdlib.h"
#include "string.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);
// 在线性表的pos位置插入元素node
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
// 获取线性表pos位置的元素
SeqListNode* SeqList_Get(SeqList* list, int pos);
// 删除线性表pos位置的元素
SeqListNode* SeqList_Delete(SeqList* list, int pos);
#endif
1. 插入元素算法
判断线性表是否合法；
判断插入位置是否合法；
容错修正插入位置大于当前长度但小于链表容量，自动添加到尾部；
把最后一个元素到插入位置的元素一次向后移一个位置；
将新元素插入；
线性表长度加1.
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
int i = 0, ret = 0;
TseqList* tlist = NULL;
tlist = (TseqList*)list;
if (list == NULL || node == NULL || pos < 0)
{
ret = -1;
printf("Fun SeqList_Insert() error: %d \n", ret);
return ret;
}
if (pos >= tlist->capacity)
{
ret = -2;
printf("链表已满: %d \n", ret);
return ret;
}
// 容错修正插入位置大于当前长度但小于链表容量，自动添加到尾部
if (pos >= tlist->length)
{
pos = tlist->length;
}
//1.元素后移
for (i = tlist->length; i > pos; i--)
{
tlist->node = tlist->node;
}
//2. 插入元素
tlist->node = node;
tlist->length++;
return 0;
}
2. 获取元素操作
判断线性表是否合法；
判断位置是否合法；
直接通过数组下标的方式获取数组元素。
SeqListNode* SeqList_Get(SeqList* list, int pos)
{
int i = 0, ret = 0;
TseqList* tlist = NULL;
tlist = (TseqList*)list;
if (list == NULL || pos < 0 || pos > tlist->length)
{
ret = -1;
printf("Fun SeqList_Get() error: %d \n", ret);
return ret;
}
return tlist->node;
}
3. 删除元素算法
判断线性表是否合法；
判断删除位置是否合法；
将要删除的元素取出；
把删除位置后的元素分别向前移一个位置；
线性表长度减1.
注意：线性表的容量和实际长度是两个不同的概念。
SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
int i = 0, ret = 0;
SeqListNode* tmp;
TseqList* tlist = NULL;
tlist = (TseqList*)list;
if (list == NULL || pos < 0)
{
ret = -1;
printf("Fun SeqList_Insert() error: %d \n", ret);
return NULL;
}
// 缓存删除的结点
tmp = (SeqListNode*)tlist->node;
// 结点前移
for (i = pos + 1; i < tlist->length; i++)
{
tlist->node = tlist->node;
}
tlist->length--;
return tmp;
}
3、顺序存储优点和缺点
优点：
无需为线性表中的逻辑关系增加额外的空间；
可以快速获取表中合法位置的元素。
缺点：
插入和删除操作需要移动大量的元素；
当线性表长度变化较大时难以确定存储空间的容量。
完整代码：
页:
[1]