编程语言爱好者程序猿阵线联盟-汇总各类技术干货

数据结构(C语言版本)

2018-04-22  本文已影响27人  GunnerAha

数据结构(C语言版本)

第1章 绪论

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

2.数据结构:

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

4.算法的度量:

第二章 线性表

1.线性表的定义:

2.线性表合并的方法:

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

#include <stdlib.h>
#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

上面实现的是线性表的链式结构。此外,线性表通过链表还可以实现:

5.线性表的用途:

第3章 栈和队列

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

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

3.栈的应用举例:

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

第四章 串

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

2.串的模式匹配算法(查找子串):

第五章 数组和广义表

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

第六章 树和二叉树

1.树的相关概念:

2.二叉树子节点至多有两个,且有左右之分。二叉树有五种基本形态:空、根、右子树为空、左右子树非空、左子树为空。二叉树的性质:

3.二叉树分类:

4.二叉树的存储结构:

5.二叉树的遍历:

6.二叉树的确定:

7.二叉树的遍历可以使用递归实现,其非递归中根遍历的算法是(使用栈操作):

[图片上传失败...(image-5f478f-1524397579659)]

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

image

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

10.赫夫曼树又称最优树,是一类带权路径长度(子叶到根的路径个数)最短的树。赫夫曼树的构造算法:赫夫曼算法:

image

11.赫夫曼树的应用:

第七章 图

1.图的遍历算法:

第八章 动态管理内存

第九章 查找

1.查找算法(详见https://www.cnblogs.com/yw09041432/p/5908444.html)。平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。Pi:查找表中第i个数据元素的概率。Ci:找到第i个数据元素时已经比较过的次数。

2.上述算法中:

第十章 第十一章 排序

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):

排序算法.jpg

第十二章 文件

上一篇 下一篇

猜你喜欢

热点阅读