数据结构（C语言版本）

数据结构（C语言版本）

第1章 绪论

1.常用的数据结构类型：集合、线性、树形、图状。

3.算法是对特定问题求解步骤的一种描述，算法具有如下特性：有穷性、确定性、可行性、输入、输出。

第二章 线性表

3.线性表的顺序实现：满足LOC(A(i+l))=LOC(A(i))+l，LOC表示元素地址。特点：下标读取快O(1)，插入删除O(n)。

#include 
    #ifndef SEQUENCE_LINER_LIST_H #define SEQUENCE_LINER_LIST_H /* 线性表的顺序实现 */ #define LIST_INIT_SIZE 100 //初始分配量 #define LIST_INCREMENT 10 //增量 #define LIST_TYPE int //存储类型 typedef struct strSequenceLinerList { LIST_TYPE *elem; //存储空间基址 unsigned int length; //当前长度 unsigned int listSize; //当前存储容量 }SequnceLinerList; static enum Status { OK, FAILED, OVERFLOW }; /* 线性表初始化 */ Status initSequenceLinerList(SequnceLinerList& list) { list.elem = (LIST_TYPE *)malloc(sizeof(LIST_TYPE)*LIST_INIT_SIZE); if (!list.elem) { return OVERFLOW; } list.length = 0; list.listSize = LIST_INIT_SIZE; return OK; } /* 扩展 */ Status resizeSequenceLinerList(SequnceLinerList& list) { printf("Resize...\n"); list.elem = (LIST_TYPE*)realloc(list.elem, sizeof(LIST_TYPE)*(list.listSize + LIST_INCREMENT)); if (!list.elem) { return OVERFLOW; } list.listSize += LIST_INCREMENT; return OK; } /* 打印 */ void printSequnceLinerList(SequnceLinerList& list) { printf("Begin print list...\n"); printf("length=%d,listSize=%d.\n",list.length,list.listSize); unsigned int i = 0; for (; i < list.length-1;++i) { printf("%d,",list.elem[i]); } printf("%d\n", list.elem[i]); printf("End print list.\n"); } /* 线性表插入:position表示插入的位置，从1开始。第一个元素是list.elem[0] */ Status insertSequenceLinerList(SequnceLinerList& list, unsigned int position, LIST_TYPE value) { if (position<1 || position>list.length+1) { return FAILED; } if (list.length >= list.listSize) { Status res = resizeSequenceLinerList(list); if (OK != res) { return FAILED; } } LIST_TYPE* p = &list.elem[position -1]; LIST_TYPE* q = &list.elem[list.length]; for (; p != q; --q) { *(p + 1) = *p; } list.length++; *p = value; return OK; } /* 删除元素 */ Status deleteSequenceLinerList(SequnceLinerList& list, unsigned int position) { if (position<1 || position>list.length) { return FAILED; } LIST_TYPE* p = &list.elem[position - 1]; LIST_TYPE* q = &list.elem[list.length - 1]; for (; p != q; ++p) { *p = *(p+1); } --list.length; return OK; } /* 查找：第一个值的下标 */ unsigned int findSequenceLinerList(SequnceLinerList& list, int value) { for (unsigned int i = 0; i < list.length;++i) { if (value == list.elem[i]) { return i; } } return -1; } /* 排序(冒泡) */ void sortSequeceLinerList(SequnceLinerList& list) { unsigned int i = 0; unsigned int j = 0; for (; i < list.length-1;++i) { for (j = i + 1; j < list.length; ++j) { if (list.elem[i]>list.elem[j]) { LIST_TYPE tmp = list.elem[i]; list.elem[i] = list.elem[j]; list.elem[j] = tmp; } } } } /* 销毁 */ void destroySequenceLincerList(SequnceLinerList& list) { delete list.elem; list.elem = NULL; } #endif

4.线性表的链式实现：通过p=p.next查找具体位置的链表。特点：插入、删除快O(n)。

#include <stdio.h> #include <stdio.h> #ifndef LINK_LINER_LIST_H #define LINK_lINER_LIST_H #define LINK_LIST_TYPE int /* 线性表的链表实现 */ typedef struct strLinkLinerList { LINK_LIST_TYPE data; struct strLinkLinerList* pNext; }LinkLinerList; LinkLinerList* head = NULL; /* 链表初始化 */ Status initLinkLinerList() { if (NULL == head) { head = (LinkLinerList*)malloc(sizeof(LinkLinerList)); if (!head) { return OVERFLOW; } head->pNext = NULL; return OK; } else { return FAILED; } } /* 添加元素 */ Status insertLinkLinerList(LINK_LIST_TYPE value) { if (NULL == head) { return FAILED; } LinkLinerList* p = head; while (p->pNext) { p = p->pNext; } LinkLinerList* tmp = (LinkLinerList*)malloc(sizeof(LinkLinerList)); if (!tmp) { return OVERFLOW; } tmp->data = value; tmp->pNext = NULL; p->pNext = tmp; return OK; } /*打印*/ void printLinkLinerList() { printf("Begin print...\n"); if (NULL == head || NULL == head->pNext) { printf("List is null."); } LinkLinerList* p = head->pNext; while (p->pNext) { printf("%d,",p->data); p = p->pNext; } printf("%d\n", p->data); printf("End print.\n"); } /* 排序 */ Status sortLinkLinerList() { if (NULL == head || NULL == head->pNext) { return FAILED; } LinkLinerList* p = head->pNext; LinkLinerList* q = p->pNext; while (p) { q = p->pNext; while (q) { if (p->data > q->data) { LINK_LIST_TYPE tmp = p->data; p->data = q->data; q->data = tmp; } q = q->pNext; } p = p->pNext; } return OK; } /* 长度 */ unsigned int lengthLinkLinerList() { if (head == NULL || head->pNext == NULL) { return 0; } LinkLinerList* p = head->pNext; unsigned int length = 0; while (p) { p = p->pNext; length++; } return length; } /* 删除 */ Status deleteLinkLinerList(unsigned int position) { if (position > lengthLinkLinerList() || position < 1) { return FAILED; } else { LinkLinerList* p = head; LinkLinerList* q = p->pNext; if (NULL == p || NULL == q) { return FAILED; } while (--position) { p = p->pNext; q = p->pNext; } p->pNext = q->pNext; free(q); return OK; } } /* 销毁 */ void destroyLinkLinerList() { if (NULL == head) { return; } else { LinkLinerList* p = head->pNext; LinkLinerList* q = p; while (p) { p = p->pNext; free(q); q = p; } } } #endif

第3章 栈和队列

1.栈和队列是特殊的线性表。

2.栈是先进后出的线性表，其表示：typedef struct{Type *base;Type *top; int stacksize;}SqStack；其中base始终指向栈底，top随元素的添加一直指向栈顶。可以有顺序实现和链表实现。

3.队列是先进先出的线性表。可以由链表实现和顺序实现。

第四章 串

1.串是由零到多个字符组成的字符序列。

第五章 数组和广义表

1.广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

第六章 树和二叉树

7.二叉树的遍历可以使用递归实现，其非递归中根遍历的算法是（使用栈操作）：

8.二叉树从根开始分层从左至右遍历算法是（使用队列操作）：

9.线索二叉树：指向前驱或者后继的节点的链成为线索。线索二叉树使用的节点结构为：data、left、right、ltag、rtag。其中ltag(rtag)=0表示子树，=1表示前驱（后继）节点。

10.赫夫曼树又称最优树，是一类带权路径长度（子叶到根的路径个数）最短的树。赫夫曼树的构造算法：赫夫曼算法：
– (1)以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
– (2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi）
– (3)从F中删除这两棵二叉树，同时将新二叉树加入到F中;
– (4)重复(2)、(3)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。

第七章 图

第八章 动态管理内存

略

第九章 查找

1.查找算法(详见https://www.cnblogs.com/yw09041432/p/5908444.html)。平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。Pi：查找表中第i个数据元素的概率。Ci：找到第i个数据元素时已经比较过的次数。
– (1)顺序表查找：顺序查找：
– 要求：存储结构为顺序存储或者链表存储
– 思想：顺序依次查找
– ASL:(1/n)*(1+2+…+n)=(n+1)/2
– 时间复杂度：O(n)
– (2)二分查找、折半查找：
– 要求：有序顺序存储列表
– 思想：先将查找值与中间值比较，查找不成功折半查找区间
– ASL:log2(n+1)
– 时间复杂度：O(log2n)
– (3)插值查找:
– 要求：有序顺序存储列表
– 思想：基于二分查找算法，将查找点的选择改进为自适应选择(由mid=low+1/2*(high-low)改为mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，)，可以提高查找效率。
– 时间复杂度：O(log2n)
– (4)斐波那契额查找：
– 要求：有序顺序存储列表
– 思想：依然是对查找点的优化，采用Fibonacci数组，找到对于当前长度的有序表的黄金分割点，作为每次的中间值。
– 时间复杂度：O(log2n)。平均性能，菲波那切查找优于折半查找，最坏情况低于折半查找。
– (5)二叉查找树：
– 要求：需要首先二叉查找树(左子树
<根<右子树)
– 思想：先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围

– 时间复杂度:O(log2n)，最坏O(n)，原因是没有保持平衡，形成单支树
– (6)平衡二叉树AVL：
– 要求：二叉查找树的基础上，需要进行树的平衡
– 时间复杂度：一直是O(log2n)
– 此外，在此基础上还有2-3树，2-3-4树，B+树，红黑树等。

第十章 第十一章 排序

1.排序算法的稳定性：经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。例如冒泡排序是稳定的，但是如果交换条件改为a[j].key>=a[j+1].key，就是不稳定的。

2.排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

3.常见的8种内部排序算法有(详见https://www.cnblogs.com/RainyBear/p/5258483.html)：
– 插入排序:将第一个元素看成是有序的序列，之后的元素看成是未排序的序列，然后遍历未排序的序列，将其插入到有序序列中
– 希尔排序：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
– 选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
– 冒泡排序:比较相邻元素，如果前面的大就交换
– 归并排序
– 快速排序
– 堆排序
– 基数排序

第十二章 文件

略