网站平台建设规划,wordpress tw,手机百度账号登录入口,wordpress手机版论坛顺序表是线性表的一种。
线性表是n个具有相同特性的数据元素的有限序列。
逻辑上#xff0c;它们是线性结构#xff0c;是一条连续的直线#xff1b;但是在物理上#xff0c;它们通常以数组和链式结构存储。
常见的线性表有顺序表、栈、队列、字符串等。
顺序表是用一段…顺序表是线性表的一种。
线性表是n个具有相同特性的数据元素的有限序列。
逻辑上它们是线性结构是一条连续的直线但是在物理上它们通常以数组和链式结构存储。
常见的线性表有顺序表、栈、队列、字符串等。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储在数组上完成数据的增删查改。
但是要注意动态顺序表的物理地址不一定连续它的物理地址是否连续困扰了我好长时间直到读到了这篇文章http://www.manongjc.com/detail/56-gahnkhbaweoyxwy.html
顺序表一般可以分为
1. 静态顺序表使用定长数组存储。
2. 动态顺序表使用动态开辟的数组存储。
以下是swarthmore对动态顺序表的解释 Dynamically allocated arrays are allocated on the heap at run time. The heap space can be assigned to global or local pointer variables that store the address of the allocated heap space (point to the first bucket). To dynamically allocate space, use calls to malloc passing in the total number of bytes to allocate (always use the sizeof to get the size of a specific type). A single call to malloc allocates a contiguous chunk of heap space of the passed size. 原文链接
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html#:~:textDynamically%20allocated%20arrays%20are%20allocated,point%20to%20the%20first%20bucket).
动态顺序表的基本形态
typedef struct SeqList
{SLDataType* a;int size; // 有效数据个数int capacity; // 空间容量
}SL;
下面是动态顺序表的接口实现
一、初始化
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLInit(SL* ps)
{ps-a (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}
使用malloc函数向系统申请一定数量的空间。
如果没有申请成功则a为NULL。
如果申请成功了那a就不是NULL了size将会被初始化为0。
由于已经成功申请了sizeof(SLDataType)* INIT_CAPACITY个空间那么capacity的值就为INIT_CAPACITY。
二、检查和扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}
}
当数据个数和空间容量相等时进行扩容。
这时要用到realloc函数了即从ps-a的位置开始向后申请sizeof(SLDataType)*ps-capacity*2个空间。
对的没错在这里申请的空间是原来空间的1倍。当然可以申请别的大小的空间。
然后让a指向新开辟的空间的地址将它们连接起来。
容量大小也相对应地乘2。
三、插入元素
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}
在插入元素之前要用断言看看要插入的位置有没有在有效数据个数之内。
如果等于size就相当于尾插如果等于0就相当于头插。
所以在这里0和size是有必要的。
然后不断循环将要插入的位置原来的元素以及它后边的元素向后移动直至endpos。
四、删除元素
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
删除元素本质上是将要删除的元素用循环从后向前覆盖 最后size自减1。
五、头插
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLPushFront(SL* ps, SLDataType x)
{SLInsert(ps, 0, x);
}
在插入元素的基础上实现头插。
六、头删
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLPopFront(SL* ps)
{SLErase(ps, 0);
}
在删除元素的基础上实现头删。
七、尾插
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLPushBack(SL* ps, SLDataType x)
{SLInsert(ps, ps-size, x);
}
在插入元素的基础上实现尾插。
八、尾删
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLPopBack(SL* ps)
{SLErase(ps, ps-size-1);
}
在删除元素的基础上实现尾删。
九、查找元素
int SLFind(SL* ps, SLDataType x)
{assert(ps);for(int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}
即遍历数组找到后返回数组下标。
十、打印数组
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}
遍历打印输出即可。
十一、销毁
typedef int SLDataType;
#define INIT_CAPACITY 4
void SLDestroy(SL* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}
