这几天复习数据结构，打算把所有数据结构的代码和伪代码整理出来，以备查阅。

实现代码来自于实验楼，因学校的教材《数据结构（c语言版）》上面竟然出现了new关键字以及引用&，让人搞不清是c还是c++，虽然自己换成malloc也能用，但是还是实验楼直接malloc的版本比较顺眼。

一，顺序存储

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INIT_SIZE 10 //初始化表长 #define INCREMENT_SIZE 5 //分配增量 typedef int Status; typedef int Elemtype; /* * 存储结构 */ typedef struct { Elemtype *elem; //存储空间基址 int length; //当前长度 int size; //当前分配的表长大小 }SqList; /* * 初始化一个空的线性表 */ Status InitList(SqList *L) { L->elem = (Elemtype *) malloc(INIT_SIZE * sizeof(Elemtype)); if (!L->elem) { return ERROR; } L->length = 0; L->size = INIT_SIZE; return OK; } /* * 销毁线性表 */ Status DestroyList(SqList *L) { free(L->elem); L->length = 0; L->size = 0; return OK; } /* * 清空线性表 */ Status ClearList(SqList *L) { L->length = 0; return OK; } /* * 判断线性表是否为空 */ Status isEmpty(const SqList L) { if (0 == L.length) { return TRUE; } else { return FALSE; } } /* * 获取长度 */ Status getLength(const SqList L) { return L.length; } /* * 根据位置获取元素 */ Status GetElem(const SqList L, int i, Elemtype *e) { if (i < 1 || i > L.length) { return ERROR; } *e = L.elem[i-1]; return OK; } /* * 比较两个元素是否相等 */ Status compare(Elemtype e1, Elemtype e2) { if (e1 == e2) { return 0; } else if (e1 < e2) { return -1; } else { return 1; } } /* * 查找元素 */ Status FindElem(const SqList L, Elemtype e, Status (*compare)(Elemtype, Elemtype)) { int i; for (i = 0; i < L.length; i++) { if (!(*compare)(L.elem[i], e)) { return i + 1; } } if (i >= L.length) { return ERROR; } } /* * 查找前驱元素 */ Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e) { int i; for (i = 0; i < L.length; i++) { if (cur_e == L.elem[i]) { if (i != 0) { *pre_e = L.elem[i - 1]; } else { return ERROR; } } } if (i >= L.length) { return ERROR; } } /* * 查找后继元素 */ Status NextElem(const SqList L, Elemtype cur_e, Elemtype *next_e) { int i; for (i = 0; i < L.length; i++) { if (cur_e == L.elem[i]) { if (i < L.length - 1) { *next_e = L.elem[i + 1]; return OK; } else { return ERROR; } } } if (i >= L.length) { return ERROR; } } /* * 插入元素 */ Status InsertElem(SqList *L, int i, Elemtype e) { Elemtype *new; if (i < 1 || i > L->length + 1) { return ERROR; } if (L->length >= L->size) { new = (Elemtype*) realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype)); if (!new) { return ERROR; } L->elem = new; L->size += INCREMENT_SIZE; } Elemtype *p = &L->elem[i - 1]; Elemtype *q = &L->elem[L->length - 1]; for (; q >= p; q--) { *(q + 1) = *q; } *p = e; ++L->length; return OK; } /* * 删除元素并返回其值 */ Status DeleteElem(SqList *L, int i, Elemtype *e) { if (i < 1 || i > L->length) { return ERROR; } Elemtype *p = &L->elem[i - 1]; *e = *p; for (; p < &L->elem[L->length]; p++) { *(p) = *(p + 1); } --L->length; return OK; } /* * 访问元素 */ void visit(Elemtype e) { printf("%d ", e); } /* * 遍历线性表 */ Status TraverseList(const SqList L, void (*visit)(Elemtype)) { int i; for(i = 0; i < L.length; i++) { visit(L.elem[i]); } return OK; } /* * 主函数测试 */ int main() { SqList L; if (InitList(&L)) { Elemtype e; printf("init_success\n"); int i; for (i = 0; i < 10; i++) { InsertElem(&L, i + 1, i); } printf("length is %d\n", getLength(L)); if (GetElem(L, 1, &e)) { printf("The first element is %d\n", e); } else { printf("element is not exist\n"); } if (isEmpty(L)) { printf("list is empty\n"); } else { printf("list is not empty\n"); } printf("The 5 at %d\n", FindElem(L, 5, *compare)); PreElem(L, 6, &e); printf("The 6's previous element is %d\n", e); NextElem(L, 6, &e); printf("The 6's next element is %d\n", e); DeleteElem(&L, 1, &e); printf("delete first element is %d\n", e); printf("list:"); TraverseList(L,visit); if (DestroyList(&L)) { printf("\ndestroy_success\n"); } } }

以上代码已经在Linux环境下用gcc编译，运行验证无误。

下面把代码分块整理成伪代码，因为数据结构这边的函数太多，看上去很不直观不利于分解复习。

//顺序存储线性表 包含头文件 预定义 状态常数 预定义 初始表长，表增量 别名 int 状态 别名 int 表元素：ElemType 别名 { ElemType *elem 存储空间基址 int length 当前长度 int size 表长度 }存储结构：SqList 初始化线性表（SqList *L） { L的基址 = （表元素 *） 动态分配malloc（初始表长 * sizeof（表元素）） 检测分配是否成功 初始化当前长度，表长 } 销毁线性表（SqList *L） { 释放 L的基址 初始化当前长度，表长 } 清空线性表（SqList *L） { 当前长度 = 0 } 判断线性表是否为空（const SqList L） { 返回（ 当前长度 == 0 ） } 获取当前长度（const SqList L） { 返回 当前长度 } 按位置获取元素（const SqList L，位置 int i，表元素指针 ElemType *e） { 判断位置是否合法 *e = L.elem[i - 1] //*(L.elem + i - 1)编译器自动转换，并非数组 } 比较表元素（表元素 e1，e2） { 相等 返回 0 e1 < e2 返回 -1 e1 > e2 返回 1 } 查找表元素（const SqList，表元素e，比较函数指针（表元素e1，e2）） { 遍历线性表 找到与e匹配的L.elem[i] 返回 i+1 未找到 返回 ERROR } //感觉这个查找前驱有问题，不能判断重复元素，而且遍历后始终返回ERROR，已修改伪代码 查找前驱 (const SqList L, 表元素cur_e, 表元素*pre_e) { 遍历线性表 判断 L.elem[i]与cur_e匹配 判断 L.elem[i]非表头 则cur_e前驱为L.elem[i - 1] 返回 OK 否则 返回 ERROR 如果遍历次数等于当前表长 返回 ERROR } 查找后继 (const SqList L, 表元素cur_e, 表元素*next_e) { 遍历线性表 判断 L.elem[i]与cur_e匹配 判断 L.elem[i]非表尾 则cur_e后继为L.elem[i + 1] 返回 OK 否则 返回 ERROR 如果遍历次数等于当前表长 返回 ERROR } 插入表元素（const SqList L，位置 int i，表元素 ElemType e） { 判断位置是否合法 判断当前表长是否填满表长度 重新动态分配realloc（L->表基址,（表长度 + 表增量）* sizeof（表元素）） 重新设定表长度 将elem[i - 1]处开始的所有元素向后移位 elem[i - 1] = e 当前长度增加 } 删除并返回表元素（const SqList L，位置 int i，表元素指针 ElemType *e） { 判断位置是否合法 找到elem[i - 1]位置的表元素p *e = *p 将elem[i - 1]处开始的所有元素向前移位 当前长度减少 } 输出元素到屏幕（表元素） 遍历输出表元素（const SqList L，（函数指针）） 测试主函数 { 声明表结构 判断 初始化 循环添加表元素 输出 当前长度 输出 获取位置1元素 输出 判断表为空 输出 元素5的位置 输出 元素6的前驱 输出 元素6的后继 输出 删除位置1的元素 遍历输出表 输出 销毁表 }

个人觉得这个线性表的查找前驱后继的部分还是有些问题的，处理不了有重复元素的情况。

二，单链存储

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; typedef int Status; /* * 存储结构 */ typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; /* * 初始化线性表 */ void InitList(LinkList *L) { *L = (LinkList) malloc(sizeof(LNode)); if (!L) { exit(OVERFLOW); } (*L)->next = NULL; } /* * 销毁线性表 */ void DestroyList(LinkList *L) { LinkList temp; while (*L) { temp = (*L)->next; free(*L); *L = temp; } } /* * 清空线性表 */ void ClearList(LinkList L) { LinkList p = L->next; L->next = NULL; DestroyList(&p); } /* * 判断是否为空 */ Status isEmpty(LinkList L) { if (L->next) { return FALSE; } else { return TRUE; } } /* * 获取长度 */ int GetLength(LinkList L) { int i = 0; LinkList p = L->next; while (p) { i++; p = p->next; } return i; } /* * 根据位置获取元素 */ Status GetElem(LinkList L, int i, ElemType *e) { int j = 1; LinkList p = L->next; while (p && j < i) { j++; p = p->next; } if (!p || j > i) { return ERROR; } *e = p->data; return OK; } /* * 比较两个元素是否相等 */ Status compare(ElemType e1, ElemType e2) { if (e1 == e2) { return 0; } else if (e1 < e2) { return -1; } else { return 1; } } /* * 查找指定元素的位置 */ int FindElem(LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)) { int i = 0; LinkList p = L->next; while (p) { i++; if (!compare(p->data, e)) { return i; } p = p->next; } return 0; } /* * 获取前驱元素 */ Status PreElem(LinkList L, ElemType cur_e, ElemType *pre_e) { LinkList q, p = L->next; while (p->next) { q = p->next; if (q->data == cur_e) { *pre_e = p->data; return OK; } p = q; } return ERROR; } /* * 获取后继元素 */ Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { LinkList p = L->next; while (p->next) { if (p->data == cur_e) { *next_e = p->next->data; return OK; } p = p->next; } return ERROR; } /* * 插入元素 */ Status InsertElem(LinkList L, int i, ElemType e) { int j = 0; LinkList s, p = L; while (p && j < i - 1) { j++; p = p->next; } if (!p || j > i - 1) { return ERROR; } s = (LinkList) malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return OK; } /* * 删除元素并返回值 */ Status DeleteElem(LinkList L, int i, ElemType *e) { int j = 0; LinkList q, p = L; while (p->next && j < i - 1) { j++; p = p->next; } if (!p->next || j > i - 1) { return ERROR; } q = p->next; p->next = q->next; *e = q->data; free(q); return OK; } /* * 访问元素 */ void visit(ElemType e) { printf("%d ", e); } /* * 遍历线性表 */ void TraverseList(LinkList L, void (*visit)(ElemType)) { LinkList p = L->next; while (p) { visit(p->data); p = p->next; } } int main() { LinkList L; InitList(&L); ElemType e; int i; if (L) { printf("init success\n"); } if (isEmpty(L)) { printf("list is empty\n"); } for (i = 0; i < 10; i++) { InsertElem(L, i + 1, i); } if (GetElem(L, 1, &e)) { printf("The first element is %d\n", e); } printf("length is %d\n", GetLength(L)); printf("The 5 at %d\n", FindElem(L, 5, *compare)); PreElem(L, 6, &e); printf("The 6's previous element is %d\n", e); NextElem(L, 6, &e); printf("The 6's next element is %d\n", e); DeleteElem(L, 1, &e); printf("delete first element is %d\n", e); printf("list:"); TraverseList(L,visit); DestroyList(&L); if (!L) { printf("\ndestroy success\n"); } }

同样，也在linux测试过了。

//单链存储 包含头文件 预定义 状态常数 预定义 初始表长，表增量 别名 int 状态 别名 int 表元素：ElemType 别名 { ElemType data 数据 struct LNode *next 下一个元素的地址 }存储结构：LNode,*LinkList //头指针*L 初始化线性表（LinkList *L） { *L = （LinkList） 动态分配malloc（sizeof（LNode）） 检测分配是否成功 头节点（**L）的指针域next设为NULL } 销毁线性表（LinkList *L） { LinkList临时变量temp 遍历单链表L temp = 节点指针域next 释放该指针 指向下一个节点的指针 } //就是头节点不销毁，把next设为NULL以后删除next开始的链表 清空线性表（LinkList *L） { LinkList临时变量p指向next 头节点的指针next设为NULL 销毁（&p） } 判断线性表是否为空（LinkList L） { 判断头节点的指针域是否为空 } 获取当前长度（LinkList L） { 遍历链表 i++ 返回i } 按位置获取元素（LinkList L，位置 int i，表元素指针 ElemType *e） { 遍历链表i次 *e = data } 比较表元素（表元素 e1，e2） { 相等 返回 0 e1 < e2 返回 -1 e1 > e2 返回 1 } 查找表元素（LinkList L，表元素e，比较函数指针（表元素e1，e2）） { 遍历链表 判断是否相等 返回遍历次数 返回i位置 } 查找前驱 (LinkList L, 表元素cur_e, 表元素*pre_e) { 遍历链表 记录元素 和next指向的元素比较 返回该元素 } 查找后继 (LinkList L, 表元素cur_e, 表元素*next_e) { 遍历链表 记录元素 和next指向的元素比较 返回下一个元素 } 插入表元素（LinkList L，位置 int i，表元素 ElemType e） { 找到位置i-1的指针p 创建节点指针S并分配内存 把p的后继给s p后继指向s 给s的data赋值e } 删除并返回表元素（LinkList L，位置 int i，表元素指针 ElemType *e） { 找到位置i-1的指针p 把位置i的next给p的next 保存i位置的data 释放i位置的节点 } 输出元素到屏幕（表元素） 遍历输出表元素（LinkList L，（函数指针）） 测试主函数 { 声明表结构 判断 初始化 循环添加表元素 输出 当前长度 输出 获取位置1元素 输出 判断表为空 输出 元素5的位置 输出 元素6的前驱 输出 元素6的后继 输出 删除位置1的元素 遍历输出表 输出 销毁表 }

三，总结

都是线性表，功能上没有差异。区别在于顺序存储的结构类似与数组可以随机存取，而链表需要遍历。而增删元素时，顺序要移位而链表只要修改前后节点的指针域就可以了。

主要功能有：

初始化线性表 销毁线性表 清空线性表 判断线性表是否为空 获取当前长度 按位置获取元素 比较表元素 查找表元素 查找前驱 查找后继 插入表元素 删除并返回表元素 输出元素到屏幕 遍历输出表元素