顺序表:
即线性表的顺序存储结构, 其逻辑结构与物理存储结构一致.内存分配连续,需要考虑初始内存分配和内存追加的问题.
基础算法:
1.类型定义&宏定义
#define C_TRUE 0
#define C_FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct
{
int *elem; // 首地址指针
int length; // 长度
int listsize; // 当前分配的存储容量
}List;
2.创建空表
int ListInit(List *L) {
L->elem = (int *)malloc(LIST_INIT_SIZE *sizeof(int));
if (NULL == L->elem) exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
3.追加元素
int ListAdd(List *L, int e) {
if (L->length >= L->listsize) {
int *newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
if (!newbase) exit(OVERFLOW);
L->elem = newbase;
L->listsize += LISTINCREMENT;
}
L->elem[L->length] = e;
L->length++;
return OK;
}
4.插入元素
// 在第i个元素之前插入一个元素elem
int ListInsert(List *L, int i, int e) {
// 保证i合法, i可以插到最后一个元素后面, 假定插入最后一个元素后面一个元素前面
if (i<1 || i>L->length + 1) {
printf("位置不合法");
return ERROR;
}
if (L->length >= L->listsize) // 存储空间满, 增加分配
{
/* code */
int *newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
if (!newbase) exit(OVERFLOW); // OVERFLOW 内存溢出
L->elem = newbase; // 新基址
L->listsize += LISTINCREMENT;
}
// 插入的位置, 这里的位置不是数组元素下标, 而是实际物理地址,也可以用下标实现
int *q = &(L->elem[i - 1]);
for (int *p = &(L->elem[L->length - 1]); p >= q; --p) {
*(p + 1) = *p;
}
*q = e;
L->length++;
return OK;
}
5.遍历
void ListTraversal(List L) {
for (int i = 0; i<L.length; i++) {
printf("长度为:%d, 下标为%d的元素: %d\n", L.length ,i,L.elem[i]);
}
}
6.删除
int ListDelete(List * L, int pos) {
if (pos<0 || pos>L->length-1) {
printf("删除位置不合法\n");
return ERROR;
}
int *q = L->elem + pos;
int *p = L->elem + L->length - 1;
for (++q; q<=p; ++q) *(q-1) = *q;
--L->length;
return OK;
}
7.取元素
// 取出第 i 个元素并赋值给*pE;
int ListGeteElem(List p, int i, int *pE) {
if (i<1 || i>p.length) {
printf("取元素位置不合法\n");
return ERROR;
}
*pE = p.elem[i-1];
printf("第%d个元素为: %d\n", i,*pE);
return OK;
}
8.判断是否为空
int ListIsEmpty(List L) {
if (L.length==0) {
printf("表为空\n");
return C_TRUE;
} else {
printf("表不为空\n");
return C_FALSE;
}
}
9.归并
// La Lb 都是递增的, 归并后 pC 也需要递增
void ListMerge(List La, List Lb, List *pC) {
ListInit(pC);
int i, j;
i = j = 1;
int ai;
int bj;
while (i<=La.length && j<=Lb.length) { // 保证都不越界
ListGeteElem(La, i, &ai); ListGeteElem(Lb, j, &bj);
if (ai < bj) {
ListAdd(pC, ai); // 如果ai小, 把ai放进pC, j不能加, 继续与ai+1比较
i++;
} else {
ListAdd(pC, bj); // 同理
j++;
}
}
while (i<=La.length) {
ListGeteElem(La, i++, &ai);
ListAdd(pC,ai);
}
while (i<=Lb.length) {
ListGeteElem(Lb, i++, &ai);
ListAdd(pC,ai);
}
}
总结:
学习数据结构和算法的过程考虑到内存溢出, 数组越界等问题训练程序员所写代码的健壮性, 对比一些其他语言, C是直接操作内存的, 有些语言如OC在内存分配失败(即alloc失败)时一般不做任何处理, 虽然失败的概率很小, 但就代码的严谨性来说C语言更胜一筹.在学习过程中, 值得注意的两点, 一是什么时候参数传递指针, 什么时候直接传值, 我的总结是: 使用时传值, 修改时传递指针; 因为使用是使用值, 而改变则需要知道修改哪块内存对应的值.
