临沂兰山建设局网站,百度风云榜各年度小说排行榜,官方网站下载安装qq,做灯箱片的设计网站目录
1. 为什么学习数据结构#xff1f;
2. 数据结构
2.1. 数据
2.2. 逻辑结构
2.3. 存储结构
2.4. 操作
3. 算法
3.1. 算法与程序
3.2. 算法与数据结构
3.3. 算法的特性
3.4. 如何评价一个算法的好坏
4. 线性表
4.1. 顺序表
4.2. 单向链表
4.3. 单向循环链表
2. 数据结构
2.1. 数据
2.2. 逻辑结构
2.3. 存储结构
2.4. 操作
3. 算法
3.1. 算法与程序
3.2. 算法与数据结构
3.3. 算法的特性
3.4. 如何评价一个算法的好坏
4. 线性表
4.1. 顺序表
4.2. 单向链表
4.3. 单向循环链表解决约瑟夫问题 1. 为什么学习数据结构
C语言学习的时如何写代码
数据结构教会我们高效简洁的写代码。
实现一个功能、写代码解决什么问题
1》数据与数据之间的逻辑规律和数据在计算机中如何表示(存储)
数据结构数据的逻辑结构存储结构及操作
数据不只是一个单独的数值、是一个集合的概念。 2》解决问题的方法(实现代码的逻辑思想)
算法
数据结构算法程序
2. 数据结构
概念 数据的逻辑结构存储结构及操作。
2.1. 数据
数据不只是一个单独的数值是一个集合的概念。
数据元素数据的最小单位由基本的数据项构成。
数据项是数据元素的基本单位描述数据元素拥有的信息。
节点就是数据元素
2.2. 逻辑结构
概念描述数据之间的逻辑规律和联系即元素与元素之间的关系
逻辑结构的分类
线性结构头节点无前驱尾节点无后缀 线性存储一对一的关系顺序表、链表
层次结构根节点无前驱叶子节点无后继 一对多的关系
网状结构 多对多的关系图 2.3. 存储结构
概念数据的逻辑结构在计算机中的具体实现
存储结构分类 顺序存储内存空间开辟是连续数组内存空间连续开辟数据元素类型相同链式存储通过地址将数据元素联系在一起索引存储通过索引表找到数据元素存放位置拿到数据散列存储结构 (哈希存储) 数据元素的存放和位置之间存在一个关系。存在一个关键字key和一个关系函数通过关键值key带入关系函数计算出数据存放的位置。对应位置存放、对应位置取值。
2.4. 操作
操作增 删 改 查
3. 算法
3.1. 算法与程序
算法解决问题的思想办法
程序用计算机语言对算法的具体实现
3.2. 算法与数据结构
算法数据结构程序
算法的设计依赖于逻辑结构
算法的实现依赖于存储结构
3.3. 算法的特性
有穷性算法的执行步骤是有限的确定性算法的每一个步骤无二义性 没有歧义可行性算法能够在有限的时间内完成输入和输出一个算法可以有一个或多个输入和输出
3.4. 如何评价一个算法的好坏
正确性保证算法能够正确的完成功能的实现易读性算法容易被解读健壮性错误处理高效性算法执行效率算法执行快慢容易受到计算机性能的低存储性算法占用空间小空间复杂度
4. 线性表
线性表 顺序表链表(单向链表 单向循环链表 双向链表 双向循环链表)栈队列
特点一对一的关系头节点没有前驱尾节点没有后继
4.1. 顺序表
特点内存空间是连续开辟(数组)逻辑结构线性结构存储结构顺序存储结构定义一个结构体表示顺序表
#define N 10
typedef int datatype_t;
typedef struct list_t{datatype_t data[N];//表int last ; //保存最后一个有效元素的下标 (-1 表为空)}seqlist_t,*seqlist_pj; 常见操作
#include stdio.h
#include stdlib.h#define N 10typedef int datatype_t;typedef struct list_t {datatype_t data[N]; // 表int last; // 保存最后一个有效元素的下标 (-1 表为空)
} seqlist_t, *seqlist_p;// 创建一个空的顺序表
seqlist_p createList() {seqlist_p list (seqlist_p)malloc(sizeof(seqlist_t));list-last -1;return list;
}// 向顺序表的指定位置插入数据
void insert(seqlist_p list, int pos, int value) {if (pos 0 || pos list-last 1 || list-last N - 1) {printf(插入位置无效或顺序表已满\n);return;}// 将插入位置之后的元素依次后移for (int i list-last; i pos; i--) {list-data[i1] list-data[i];}// 在指定位置插入新元素list-data[pos] value;list-last;
}// 判断顺序表是否满
int isFull(seqlist_p list) {return list-last N - 1;
}// 指定位置删除数据
void delete(seqlist_p list, int pos) {if (pos 0 || pos list-last) {printf(删除位置无效\n);return;}// 将删除位置之后的元素依次前移for (int i pos; i list-last; i) {list-data[i] list-data[i1];}list-last--;
}// 判断顺序表是否为空
int isEmpty(seqlist_p list) {return list-last -1;
}// 修改指定位置的数据
void modify(seqlist_p list, int pos, int value) {if (pos 0 || pos list-last) {printf(修改位置无效\n);return;}list-data[pos] value;
}// 删除指定的数据
void removeData(seqlist_p list, int value) {for (int i 0; i list-last; i) {if (list-data[i] value) {// 将删除位置之后的元素依次前移for (int j i; j list-last; j) {list-data[j] list-data[j1];}list-last--;i--; // i减1以继续判断下一个元素是否与value相等}}
}// 清空顺序表
void clearList(seqlist_p list) {list-last -1;
}// 删除顺序表
void deleteList(seqlist_p list) {free(list);
}// 遍历顺序表
void traverse(seqlist_p list) {if (isEmpty(list)) {printf(顺序表为空\n);return;}printf(顺序表数据);for (int i 0; i list-last; i) {printf(%d , list-data[i]);}printf(\n);
}int main() {seqlist_p list createList();insert(list, 0, 1);insert(list, 1, 2);insert(list, 2, 3);traverse(list);delete(list, 1);traverse(list);modify(list, 0, 5);traverse(list);removeData(list, 5);traverse(list);clearList(list);traverse(list);deleteList(list);return 0;
} 顺序表的特点
1.内存空间连续开辟
2.长度固定(保存的数据元素个数是固定的) #define N 10
3.插入和删除比较复杂查询操作或修改比较简单。
4.2. 单向链表
特点内存空间开辟不是连续、通过地址将多有的内存空间练习到一起逻辑结构线性结构存储结构链式存储分类 有头单向链表 链表中的头节点数据域无效指针域有效 无头单向链表 链表中所有节点的数据域和指针域都是有效的
定义链表节点结构体
typedef int datatype_t;
typedef struct node_t //node 节点
{datatype_t data; //数据域struct node_t *next; //指针域 保存下一个节点的地址
}linklist_t,*linklist_p; //link 链 有头单向链表
#include stdio.h
#include stdlib.htypedef int datatype_t;
typedef struct node_t
{datatype_t data; //数据域struct node_t *next; //节点域
}linklist_t, *linklist_p;// 创建空的有头单向链表
void createEmptyList(linklist_p *head)
{*head (linklist_p)malloc(sizeof(linklist_t));(*head)-next NULL;
}// 向链表的指定位置插入数据
void insertData(linklist_p head, int position, datatype_t data)
{linklist_p p head;int count 0;while (p count position){p p-next;count;}if (p count position){linklist_p newNode (linklist_p)malloc(sizeof(linklist_t));newNode-data data;newNode-next p-next;p-next newNode;}
}// 计算链表的长度
int calculateLength(linklist_p head)
{linklist_p p head-next;int length 0;while (p){length;p p-next;}return length;
}// 遍历链表
void traverseList(linklist_p head)
{linklist_p p head-next;while (p){printf(%d , p-data);p p-next;}printf(\n);
}// 删除链表指定位置的节点
void deleteNode(linklist_p head, int position)
{linklist_p p head;int count 0;while (p count position){p p-next;count;}if (p p-next count position){linklist_p temp p-next;p-next p-next-next;free(temp);}
}// 修改链表指定位置的数据
void modifyData(linklist_p head, int position, datatype_t data)
{linklist_p p head-next;int count 0;while (p count position){p p-next;count;}if (p count position){p-data data;}
}// 查询指定数据的位置
int findPosition(linklist_p head, datatype_t data)
{linklist_p p head-next;int position 0;while (p){if (p-data data){return position;}p p-next;position;}return -1;
}// 删除指定的数据
void deleteData(linklist_p head, datatype_t data)
{linklist_p p head;while (p-next){if (p-next-data data){linklist_p temp p-next;p-next p-next-next;free(temp);}else{p p-next;}}
}// 清空链表
void clearList(linklist_p head)
{linklist_p p head-next;while (p){linklist_p temp p;p p-next;free(temp);}head-next NULL;
}// 链表的倒置
void reverseList(linklist_p *head)
{linklist_p prev NULL;linklist_p current *head;linklist_p next NULL;while (current ! NULL){next current-next;current-next prev;prev current;current next;}*head prev;
}// 判断链表是否为空
int isEmpty(linklist_p head)
{return head-next NULL;
}int main()
{linklist_p head;createEmptyList(head);insertData(head, 0, 1);insertData(head, 1, 2);insertData(head, 2, 3);insertData(head, 3, 4);insertData(head, 4, 5);printf(List: );traverseList(head);printf(Length: %d\n, calculateLength(head));deleteNode(head, 2);printf(After deleting node at position 2: );traverseList(head);modifyData(head, 1, 10);printf(After modifying data at position 1: );traverseList(head);int position findPosition(head, 5);printf(Position of data 5: %d\n, position);deleteData(head, 1);printf(After deleting data 1: );traverseList(head);clearList(head);printf(After clearing the list: );traverseList(head);insertData(head, 0, 1);insertData(head, 1, 2);insertData(head, 2, 3);insertData(head, 3, 4);insertData(head, 4, 5);printf(List: );traverseList(head);reverseList(head);printf(After reversing the list: );traverseList(head);printf(Is list empty? %s\n, isEmpty(head) ? Yes : No);return 0;
} 无头单向链表
#include stdio.h
#include stdlib.h// typedef定义的数据类型
typedef int datatype_t;
typedef struct node_t {datatype_t data;struct node_t* next;
} linklist_t, * linklist_p;// 创建空的有头单向链表
void createEmptyList(linklist_p* head) {*head NULL;
}// 向链表的指定位置插入数据
int insertElement(linklist_p* head, int position, datatype_t value) {// 创建新节点linklist_p new_node (linklist_p)malloc(sizeof(linklist_t));if (new_node NULL) {return 0; // 内存分配失败}new_node-data value;new_node-next NULL;if (position 0) {new_node-next *head;*head new_node;}else {int count 0;linklist_p current *head;while (current ! NULL count position - 1) {current current-next;count;}if (current NULL) {return 0; // 指定位置无效}new_node-next current-next;current-next new_node;}return 1;
}// 计算链表的长度
int getLength(linklist_p head) {int length 0;linklist_p current head;while (current ! NULL) {length;current current-next;}return length;
}// 遍历链表
void traverse(linklist_p head) {linklist_p current head;while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);
}// 删除链表指定位置的数据
int deleteElement(linklist_p* head, int position) {if (*head NULL) {return 0; // 链表为空}if (position 0) {linklist_p temp *head;*head (*head)-next;free(temp);}else {int count 0;linklist_p current *head;linklist_p previous NULL;while (current ! NULL count position) {previous current;current current-next;count;}if (current NULL) {return 0; // 指定位置无效}previous-next current-next;free(current);}return 1;
}// 修改链表指定位置的数据
int modifyElement(linklist_p head, int position, datatype_t value) {int count 0;linklist_p current head;while (current ! NULL count position) {current current-next;count;}if (current NULL) {return 0; // 指定位置无效}current-data value;return 1;
}// 查询指定数据的位置
int findPosition(linklist_p head, datatype_t value) {int position 0;linklist_p current head;while (current ! NULL) {if (current-data value) {return position;}current current-next;position;}return -1; // 没有找到指定数据
}// 删除指定的数据
int deleteValue(linklist_p* head, datatype_t value) {if (*head NULL) {return 0; // 链表为空}if ((*head)-data value) {linklist_p temp *head;*head (*head)-next;free(temp);return 1;}linklist_p current *head;linklist_p previous NULL;while (current ! NULL current-data ! value) {previous current;current current-next;}if (current NULL) {return 0; // 没有找到指定数据}previous-next current-next;free(current);return 1;
}// 清空链表
void clearList(linklist_p* head) {linklist_p current *head;while (current ! NULL) {linklist_p temp current;current current-next;free(temp);}*head NULL;
}// 链表的倒置
void reverseList(linklist_p* head) {linklist_p previous NULL;linklist_p current *head;linklist_p next NULL;while (current ! NULL) {next current-next;current-next previous;previous current;current next;}*head previous;
}// 判断链表是否为空
int isListEmpty(linklist_p head) {return head NULL;
}int main() {linklist_p linked_list;createEmptyList(linked_list);insertElement(linked_list, 0, 1);insertElement(linked_list, 1, 2);insertElement(linked_list, 2, 3);insertElement(linked_list, 3, 4);traverse(linked_list); // 输出: 1 2 3 4printf(Length: %d\n, getLength(linked_list)); // 输出: 4deleteElement(linked_list, 2);traverse(linked_list); // 输出: 1 2 4modifyElement(linked_list, 1, 5);traverse(linked_list); // 输出: 1 5 4int position findPosition(linked_list, 5);printf(Position: %d\n, position); // 输出: 1deleteValue(linked_list, 1);traverse(linked_list); // 输出: 5 4clearList(linked_list);printf(Is empty: %s\n, isListEmpty(linked_list) ? Yes : No); // 输出: YesinsertElement(linked_list, 0, 1);insertElement(linked_list, 1, 2);insertElement(linked_list, 2, 3);insertElement(linked_list, 3, 4);traverse(linked_list); // 输出: 1 2 3 4reverseList(linked_list);traverse(linked_list); // 输出: 4 3 2 1return 0;
} 链表的特点
1.内存空间不连续通过地址将地址空间联系在一起
2.长度不固定
3.删除和插入简单查询和修改复杂
4.3. 单向循环链表解决约瑟夫问题
特点无头单向链表尾节点的指针域保存头节点的地址 就可以形成单向循环链表通过一定规律找到一个最终的值定义链表结构体
typedef struct node_t
{int data;struct node_t *next;
}link_t;
单向循环链表
#include stdio.h
#include stdlib.h
#define N 10
typedef struct node_t
{int data;struct node_t *next;
} link_t;int main()
{// 1.创建一个单向无头链表link_t *tail NULL;link_t *p (link_t *)malloc(sizeof(link_t));if (p NULL){puts(mallod error);return -1;}p-data 1;p-next NULL;tail p; // 指针tail指向了p// 创建接下来的节点for (int i 0; i N; i){tail-next (link_t *)malloc(sizeof(link_t));if (tail-next NULL){puts(mallod error);return -1;}tail tail-next;tail-data i 1;tail-next NULL;}tail-next p; // 尾节点指向头节点// 解决约瑟夫问题int start_num 3;int n 3;link_t *pdel NULL;// 1.将头指针移动到Kfor (int i 0; i start_num - 1; i){p p-next;}pdel p-next;while (p ! p-next){for (int i 0; i n - 1; i)p p-next;pdel p-next;p-next pdel-next;free(pdel);pdel NULL;}printf(king is %d\n, p-data);return 0;
}
顺序表和单向链表比较 顺序表 链表 空间 空间连续 通过指针链接 长度 固定 不固定 特点 查找方便但是插入和删除麻烦 插入方便查找麻烦
