网站定制费用,深圳电器公司邮编,免费网站搭建平台,网站建设项目工作分解结构1.版本一
由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错
#include stdio.h
#include stdlib.h
#include stdbool.h
// 节点类
typedef struct Node {// 数据域int data;// 指针域…1.版本一
由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错
#include stdio.h
#include stdlib.h
#include stdbool.h
// 节点类
typedef struct Node {// 数据域int data;// 指针域struct Node* next;struct Node* pre;
}Node;// 别名
// 初始化链表
Node* initList() {Node* list (Node*)malloc(sizeof(Node));list-data 0;list-next NULL;list-pre NULL;return list;
}
// 头插法
void headInsert(int data, Node* list) {Node* node (Node*)malloc(sizeof(Node));Node* pre list;Node* next list-next;node-data data;pre-next node;node-pre pre;node-next next;if (list-data ! 0) {next-pre node;}// 更新链表长度list-data;
}
// 尾插法
void tailInsert(int data, Node* list) {// 为待插入节点分配内存Node* node (Node*)malloc(sizeof(Node));// 获取待插入节点的前驱节点 前驱节点其实就是原来的尾节点Node* pre list-next;while (pre-next) {pre pre-next;}Node* next pre-next;node-data data;pre-next node;node-pre pre;node-next next;// 更新链表长度list-data;
}
// 删除方法
bool delete(int data, Node* list) {// 我们需要做的是删除指定节点值对应的第一个节点Node* cur list-next;while (cur) {// 如果一旦遇到符合指定节点值的节点的话 那么就执行相关操作if (cur-data data) {// 需要先考虑头删、尾删和中间删以及删除之后链表为空四种情况 总结之后 我们可以发现尾删和删除之后链表为空同属一种情况 都是只需要设置一条线即可 即前驱指向后继 但是其他情况需要设置两条线 即前驱指向后继 后继指向前驱cur-pre-next cur-next;if (cur-next) {cur-next-pre cur-pre;}free(cur);list-data--;return true;}cur cur-next;}return false;
}
// 打印链表方法
void printList(Node* list) {Node* cur list-next;while (cur) {printf(%d , cur-data);cur cur-next;}printf(\n);
}
int main() {Node* list initList();headInsert(1, list);headInsert(2, list);headInsert(3, list);tailInsert(4, list);tailInsert(5, list);printList(list);// 3 2 1 4 5if (delete(5, list) true) {printf(删除成功\n);}else {printf(删除失败\n);}printList(list);// 2 1 4 5
}2.版本二(mj版本的双向链表 带有虚拟头节点)
#include stdio.h
#include stdlib.h
#include stdbool.h
#define ELEMENT_NOT_FOUND -1
// 我们的设计理念就是引入一个虚拟头节点 但是不引入头节点的标识以及尾节点的标识
// 节点类
typedef struct Node {int data;// 数据域struct Node* pre;struct Node* next;// 指针域
}Node;
// 初始化链表
Node* initList() {Node* list (Node*)malloc(sizeof(Node));list-data 0;list-pre NULL;list-next NULL;return list;
}
// 索引越界的处理
void outOfBounds(int index) {printf(索引为%d 索引越界了\n, index);
}
// 边界检查
void rangeCheck(int index, Node* list) {if (index 0 || index list-data)outOfBounds(index);
}
// 针对添加方法的边界检查
void rangeCheckForAdd(int index, Node* list) {if (index 0 || index list-data)outOfBounds(index);
}
// 根据指定索引获取节点
Node* node(int index, Node* list) {// 对参数索引进行边界检查rangeCheck(index, list);Node* cur list-next;for (int i 0; i index; i) {cur cur-next;}return cur;
}
// 添加方法
void add(int index, int data, Node* list) {// 需要分成三种情况进行分析 一种情况是中间插入 需要设置四条线 一种情况是尾插 需要设置三条线 一种情况是头插 需要设置四条线 一种情况是对空链表进行插入操作 需要设置三条线 所以我们可以分成两种情况 一种是尾插的特殊情况 一中是其他位置插入// 对参数索引进行边界检查rangeCheckForAdd(index, list);// 为待插入节点分配内存Node* cur (Node*)malloc(sizeof(Node));// 获取待插入节点的前驱节点 如果是头插的话 那么就需要特殊处理了Node* pre index 0 ? list : node(index - 1, list);// 获取待插入节点的后继节点Node* next pre-next;cur-data data;// 四种情况都要设置三条线 pre-next cur;cur-pre pre;cur-next next;if (next)next-pre cur;// 无论执行的是哪一种情况 都需要更新链表长度list-data;
}
// 删除方法
int delete(int index, Node* list) {// 我们需要将问题分成三种情况去讨论 一种情况是中间删除 一种情况是尾删 一种情况是头删 如果是中间删除的话 那么我们需要操作的指针有两条 分别是前驱节点的后继节点还有后继节点的前驱节点 如果是尾删的话 那么就需要操作一条 即前驱节点指向后继节点 如果是头删的话 那么需要操作两条 同中间删除一样 如果是删除之后链表为空的话 那么就归结到尾删的情况中去考虑即可 并且复用尾删的代码Node* cur node(index, list);// 我们保存一下待删除节点的节点值int delete cur-data;// 通过待删除节点获取到他的前驱节点以及后继节点Node* pre cur-pre;Node* next cur-next;pre-next next;if (next)next-pre pre;// 我们还要去释放一下cur的内存 同时也解决了从cur指出的两条指针free(cur);// 更新一下链表的长度list-data--;// 返回待删除节点的节点值return delete;
}
// 定义一个方法 用于获取指定节点值对应的位置
int indexOf(int data, Node* list) {Node* cur list-next;for (int i 0; i list-data; i) {if (cur-data data)return i;cur cur-next;}// 如果上述循环没有返回值的话 那么说明没有找到指定的节点值对应的节点return ELEMENT_NOT_FOUND;
}
// 获取指定索引处的节点值
int get(int index, Node* list) {return node(index, list)-data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {int data node(index, list)-data;node(index, list)-data newData;return data;
}
// 清空方法
void clear(Node* list) {Node* cur list-next;Node* next;for (int i 0; i list-data; i) {next cur-next;free(cur);cur next;}// 清空链表之后链表长度为0list-data 0;
}
// 判断链表是否包含指定节点值
bool contains(int data, Node* list) {return indexOf(data, list) ! ELEMENT_NOT_FOUND;
}
// 判断链表是否为空
bool isEmpty(Node* list) {return list-data 0;
}
// 获取链表长度
int size(Node* list) {return list-data;
}
// 打印链表的方法
void printList(Node* list) {Node* cur list-next;while (cur) {printf(%d , cur-data);cur cur-next;}printf(\n);
}
// 定义一个主函数
int main() {// 创建一个链表Node* list initList();// 头部添加 尾部添加add(0, 1, list);// 1add(0, 2, list);// 2 1add(0, 3, list);// 3 2 1add(0, 4, list);// 4 3 2 1add(size(list), 5, list);// 4 3 2 1 5// 打印链表printList(list);// 4 3 2 1 5// 头部删除 尾部删除delete(0, list);// 3 2 1 5delete(size(list) - 1, list);// 3 2 1// 打印链表printList(list);// 3 2 1// 获取头部元素printf(%d\n, get(0, list));// 3// 重置头部元素printf(%d\n, set(0, 4, list));// 3// 打印链表printList(list);// 4 2 1printf(%d\n, contains(4, list));// trueprintf(%d\n, isEmpty(list));// false// 清空链表clear(list);printf(%d\n, size(list));// 0return 0;
}测试结果显示 这个代码符合预期
