Data Structure(C)

字数统计: 4.7k阅读时长: 21 min

 2018/11/29   Share

Data Structure

概述基本概念

数据：是对客观事物的符号表示，所有能输入到计算机中，并背被算机程序处理的符号总称
数据元素：是数据的基本单位（有时，数据元素可由若干个数据项组成，例如一本书的书目信息作为一个数据元素，书目信息中的每一项，如书名、作者等为数据项）
数据结构：
- 集合
- 线性结构
- 树形结构
- 图形或者网状结构
数据结构的
- 逻辑结构：抽象的，与实现无关
- 物理结构（存储结构）：
  - 顺序映像：顺序存储结构（位置相邻）
  - 非顺序映像：链式存储结构，指针表示
数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。例如，C 语言中整形变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和取模等算术运算
抽象数据类型（ADT 描述）：ADT = （数据对象+数据关系+数据操作），abstract data type 是一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用
ADT细分为：原子类型、固定聚合类型、可变聚合类型
- 原子类型：其值是不可分解的
- 固定聚合类型：属该类型的变量，其值由确定数目的成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。
- 可变聚合类型：与固定聚合类型相比，构成可变聚合类型“值”的成分的数目不确定。
逻辑运算约定：
- 与运算 && ：对于 A&&B，当 A 的值不为0时，不再对 B 求值
- 或运算 ||：对于 A||B，当 A 的值为非0时，不再对 B 求值

算法

算法：算法是对特定问题求解步骤的一种描述，他是指令的有限序列，其中每一条指令表示一个或多个操作。
算法的特征：
- 有穷性：一个算法必须总是在执行有穷步骤之后结束，且每一步都可在有穷时间内完成
- 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性，并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出
- 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
- 输出：一个算法有一个或多个输出，这些输出是同输入有这某些特定的关系
算法设计的要求：
- 正确性（一般情况下，要求达到 C 层）
- 可读性
- 健壮性
- 效率与低存储量需求
算法的时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数 f（n），算法的时间度量记作： $T(n)=O(f(n))$ ，表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同
语句频度用归纳法进行计算
算法的空间复杂度：记作 $S(n) = O(f(n))$ 作为算法所需存储空间的量度

其中 n 为问题的规模（或大小）。

推导大O阶方法

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

时间复杂度例题：

例1：

1
2
3

int sum = 0,n = 100; /*执行1次*/  
sum = （1 + n） * n/2; /*执行1次*/  
printf（"%d", sum）; /*执行1次*/

时间复杂度为：根据推导大O阶方法第1条，用常数1取代运行时间中的所有加法常数。

所以时间复杂度为 O(1)

例2：

1 2	int i; /执行1次/ for(i=0;i<n;i++); /执行 n 次/

根据在修改后的运行次数函数中，只保留最高阶项法则。

所以时间复杂度为 O(n)

例3：

1
2
3

int i,j;				/*执行1次*/
for(i=0;i<n;i++)
    for(j=0;j<n;j++);	/*嵌套 for 循环执行 n*n 次*/

所以时间复杂度为 O($n^2$)

例4：

1
2
3

int i,j;				/*执行一次*/
  for(i=0;i<n;i++)
    for(j=i;j<n;j++);

int执行一次，下面的for执行了n+(n-1)+(n-2)+…+1次，所以Ｔ(n)=1+(1+n)*n/2=n2/2+n/2+1。

所以时间复杂度为 O($n^2$)

例5：

1
2
3

int i=1;
while(i<n)
    i*=2;

计算时间复杂度， int i = 1;执行一次，在 while 循环中，设需要执行的次数为 x。则：

i=2，每执行一次，i 的值都将会乘以2，即为1\2*2*2*2*2……所以第 x 次 i 的值为$2^x$，所以$2^x$>=n时，程序截止。所以 x=logn

所以时间复杂度为 O(logn)

线性表

线性表及其特点：

线性表是 n 个数据元素的有限序列
线性结构的特点：（在非空有限集中）
- 存在唯一的被称为“第一个”的数据元素
- 存在唯一的被称为“最后一个”的数据元素
- 除第一个外，集合中的每个元素均只有一个“前驱”
- 除第一个外，集合中的每个元素均只有一个“后继”
顺序表——线性表的顺序存储结构

特点：
- 逻辑上相邻的元素在物理位置上相邻
- 随机访问

线性表的抽象数据类型（ADT 描述）：

ADT List{
    数据对象：D={ai|ai属于 ElemSet，i=1,2,…,n,n≥0}
    数据关系：R1={<ai-1,ai> | ai-1,ai 属于 D，i=2,…,n}
    基本操作：
        Initlist(&L)
        	操作结果：构造一个空的线性表 L
        DestroyList(&L)
        	初始条件：线性表 L 已经存在
        	操作结果：销毁线性表 L
        ClearList(&L)
    		初始条件：线性表 L 已经存在
            操作结果：将 L 重置为空表
        ListEmpty(L)
        	初始条件：线性表 L 已经存在
        	操作结果：判断 L 是否为空，若空返回 TRUE，否则返回 FALSE
        ListLength(L)
        	初始条件：线性表已经存在
        	操作结果：返回 L 中元素的个数
        GetList(L,i,&e)
        	初始条件：线性表 L 已经存在，1≤i≤ListLength(L)
        	操作结果：用 e 返回 L 中第 i 个数据元素的值
        LocateElem(L,e,compare())
        	初始条件：线性表 L 已经存在，compare()是数据元素判定函数
        	操作结果：返回 L 中第1个与 e 满足关系 compare()的元素的位					 序。若这个元素不存在，则返回值为0.
        ListInsert(&L,i,e)
        	初始条件：线性表 L 已经存在，1≤i≤Listlength(L)+1
        	操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度						加1
        ListDelete(&L,i,&e)
        	初始条件：线性表已经存在且非空，1≤i≤ListLength(L)
        	操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度					减1
       
}

首先，定义顺序表存储结构体：

typedef int datatype;
  
       typedef struct{
       datatype a[maxsize];
       int len;                //the length of the sequence 
   }list;

线性表初始化算法

void initlist(list *l)
{
    l->len = 0;
}

线性表 addlist 添加算法

条件：表未满

void addlist(list *, datatype x)
{
    if(l->len == MAXSIZE)
    {
        printf("The list is full!")
    }
    l->a[l->len] = x;
    l->len = l->len + 1;
}

线性表的插入算法

条件：

表未满
合理的插入范围 1≤i≤L.length+1（即从表的第一个到最后之后的一个是可以插入的范围，因为最后一个之后还可以继续相连，也就是挨着这也符合顺序表的定义特点）

步骤：

第 i 至最后所有的元素后移一个元素
在第 i 个位置插入元素 x
表长增加1

算法（注意到：从 i 到最后一个元素后移一个元素的时候联想排座位后移，需要先从最后一个开始移动）

bool insertlist(list *l, int i, datatype x)
{
    if(l->len == MAXSIZE)
    {
        printf("The list is full!")
    }
    if(i >= 1 || i <= l->len + 1 )
    {
        for(int j = l->len-1;j >= i-1;j--)
        {
            l->a[j+1] = l->a[j];
        }
        l->a[i-1] = x;
        l->len++;
    }
    return true;
}

线性表的删除算法

条件：

表非空
合理的删除范围（1≤i≤L.length）

步骤：

取出第 i 个元素
将第 i 个元素之后的所有元素向前移动一个位置

算法：

void deletelist(list *l, int i, datatype e)
{
    if(l->len == 0)
    {
        printf("The list is none!");
    }
    if(i < 0 || i > l->len)
    {
        printf("Position is wrong!");
    }
    for(int j = i; j <= l->len - 1; j++)
    {
        l->a[j-1] = l->a[j];
    }
    l->len--;
    return true;
}

线性表的打印算法

条件：

线性表非空

算法：

void printlist(list l)
{
    if(l.len == 0);
    {
        printf("The list is none!");
        return;
    }
    for(int i = 0; i < l.len; i++)
    {
        printf("%5d", l.a[i]);
    }
}

判断线性表是否为空

算法：

int empty(list l,)
{
    return(l.len == 0 ? 1 : 0);
}

单链表：线性表的链式存储结构之一

malloc()和 free()分别实现内存空间的动态分配和回收，所有一般用户不必知道某个结点具体地址值是多少。

概念：

线性链表、单链表、结点；数据域，指针域；头指针，头结点；

特点：

用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）

类型定义：

“数据+指针”

空的单链表和非空的单链表

结点：包括数据域和指针域

指针域中存储的信息称作指针或者链。

n 个结点（1≤i≤n）的存储镜像链结成一个链表，即为线性表（a1，a2，…，an）的链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称 线性链表 或 单链表 。

整个链表的存取必须从头指针开始进行，头指针指示链表中第一个借点（即第一个数据元素的存储映像）的存储位置。同时，由于最后数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）

单链表的类型描述

ADT link_list{
    数据集合 K:K = {k1,k2,…,kn},n≥0,k 中的元素是 datatype 类型；
    数据关系 R:R = {r}
    		r = {<Ki,Ki+1> | i=1,2,…,n-1 }
    操作集合如下：
    (1)node *init()建立一个空的单链表
    (2)void display(node *head) 输出单链表中各个结点的值
    (3)node *find (node *head, int i) 在单链表中查找第 i 个结点
    (4)node *insert (node *head, datatype x, int i) 在单链表中第i 个结点后插入一个值为x 的新结点
    (5)node *delete (node *head, datatype x)在单链表中删除一个值为 x 的结点
        
    
}ADT link_list

单链表的 C 语言描述

typedef int datatype;
typedef struct LNode{
    datatype data;
    struct LNode *next;
}node,

初始化

node *init()
{
    return NULL;
}

初始化带头结点的单链表

node *init()
{
    node *head;
    head = (node *)malloc(sizeof(node));
    head->next = NULL;
    return head;
}

打印各个元素的值

void printlinklist(node *head)
{
    node *p;
    p = head;
    if(!p) printf("\n The linklist is none!");
    else
    {
     	printf("\n The value of every node in linklist is: \n");
        while(p)
        {
            printf("%5d", p->data);
            p = p->next;
        }
    }
}

在链表中查找第 i 个元素

node *find(node *head, int i)
{
    int j = 1;
    node *p = head;
    if(i < 1)
    {
        printf("The position is wrong!");
        return NULL;
    }
    while(p && i != j)
    {
        p = p->next;
        j++;
    }
    return p;
}

在链表中查找值为 x 的元素

node *findxlist(node *head, datatype x)
{
    node *p = head;
    while(p && p->data != x)
    {
        p = p->next;
    }
    return p;
}

插入算法 listinsert（带头结点的链表）

技巧：画图辅助分析

思路：现查找第 i-1 个元素，若找到，在其后插入新元素

static listinsert(node *l, int i, datatype x)
{
    node *p = l, *s = NULL;
    int j = 0;
    while(p&&j<i-1)
    {
        p=p->next;j++;
    }
    if(p&&j = i-1)
    {
        s = (node *)malloc(sizeof(node));
        s->data = x;
        s->next = p->next;
        p->next = s;
        return true;
    }
    else
        return false;
}

node *insertllist1(node*head,datatype x,int i)
{
	node *p = head;
	node *s = NULL;
	int j = 0;
	while(p&&j<i-1)
	{
		p=p->next;j++;
	}
	if(p&&j==i-1)
	{
		*s = (node *)malloc(sizeof(node));
		s->info = x;
		s->next = p->next;
		p->next = s;
		return head;
	}
}

删除算法 ListDelete（带头结点的链表）

思路

先查找第 i-1个元素，若找到且其后存在第 i 个元素，则用 x 返回数据，并删除之

static listdelete(node *l, inti, datatype *x)
{
    node *p = l;
    node *s = NULL;
    int j = 0;
    while(p&&j < i-1)
    {
        p = p->next;
        j++;
    }
    if(p && j == i-1 && p->next )
    {
        s = p->next;
        p->next = s->next;
        x = s->data;
        free(s);
        return true;
    }
    else
        return false;
}

注：

要求先找到第 i-1个元素
能够进行删除的条件：p&&j=i-1&&p->next。条件中的 p->next 保证了第 i 个元素的存在，否则也是无法删除的。

将两个有序链表并为一个有序链表

void mergelist(node *la, node *lb, node *lc)
{
    node *pa = la->next;	//pa；pb 分别为当前待比较插入的结点；
    node *pb = lb->next;
    node *pc = la->next;	//pc 指向当前结点的最后一个元素；lc 一开始为空；将 la 的头结点作为 lc 的头结点
    while(pa && pb)			//当 pa 和 pb 都存在时；即为非空表时
    {
        if(pa->data <= pb->data)
        {
            pc->next = pa; 	//将 pa 指向的结点插入 lc 表
            pc = pa;
            pa=pa->next;	//pa 继续指向下一个待比较插入的结点
        }
        else				//同理可得 pb 的情况
        {
         	pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pb:pa	//如果 la 先为空；那么 pc = pa->next; 此时 pc = NULL；条件假；则插入剩余的 lb 部分
    free(lb);				//释放 lb 的头结点
    
}

建立链表的方式

顺序建表

void createlinklist(node *l, int n)
{
    l = (node *)malloc(sizeof(node));
    l->next = NULL;		//空表
    node *p;
    p = l;				//p 指向表尾
    //插入元素
    for(i = 0; i < n; i++)
    {
        scanf(x);
        node * s = (node *)malloc(sizeof(node));
        s->data = x;
        s->next = p->next;
        p->next = s;
        p = s;			//重置 p 为刚插入的 s;重新指向表尾
    }
}

逆序建表

void createlinklist(node *l, int n)
{
    node *s = NULL;
    *l = (node *)malloc(sizeof(node));
    l->next = NULL;		//空表
    //插入元素
    for(i = 0; i < n; i++)
    {
        scanf(x);
        s = (node *)malloc(sizeof(node));
        s->data = x;
        s->next = l->next;
        l->next = s;
    }
}

循环链表

循环单链表

初始化一个循环单链表

node *init()
{
    return NULL;
}

获得循环单链表最后一个结点的存储地址

node *rear(node *head)
{
    node *p;
    if(!head)
        p = NULL;
    else
    {
        p = head;
        while(p->next != head)
        {
            p = p->next;
        }
    }
    return p;
}

双向链表

类型定义

typedef struct dlink_node{
    datatype date;
    struct dlink_node *llink,rlink;
}dnode;

初始化

dnode *init()
{
    return NULL;
}

输出各个结点的值

void display(dnode *head)
{
    dnode *p;
    printf("\n");
    p = head;
    if(!p)
        printf("\n The list is empty!");
    else
    {
    	printf("\n The list is:");
        while(p)
        {
            printf("%5d",p->data);
            p=p->llink;
        }
    }
}

查找第 i 个结点的存储地址

dnode *find(dnode *head; int i)
{
    int j = 1;
    dnode *p = head;
    if(i<1)
    {
        printf("The position is wrong!\n");
        return NULL;
    }
    while(p&&j!=i)
    {
        p = p->llink;
        j++;
    }
    if(!p)
    {
        printf("The positon don't exist!\n");
    }
    return p;
}

插入操作

dnode *insert(dnode *head, int i,datatype x)
{
    dnode *p,*q;
    p = (dnode *)malloc(sizeof(dnode));
    p->data = x;
    if(i==0)
    {
        p->llink = NULL;
        p->rlink = head;
        if(!head)	//原表为空
        {
            head = p;
        }
        else
        {
            head->llink = p;
            head = p;
        }
        return head;
    }
    //当 i!=0时
    q = find(head, i);
    if(!q)
    {
        printf("The position don't exist!\n");
        return head;
    }
    
    //如果在最后一个结点后插入
    if(q->rlink == NULL)
    {
        p->rlink = q->rlink;
        p->llink = q;
        q->rlink = p;
    }
    else
    {
        p->rlink = q->rlink;
        p->llink = q;
        q->rlink->llink = p;
        q->rlink = p;
    }
    return head;
}

删除操作（删除一个值为 x 的结点）

dnode *delete(dnode *head, datatype x)
{
    dnode *q;
    if(!head)
    {
        printf("The list is none!\n");
        return head;
    }
    //寻找值为 x 的结点，设为 q
    q = head;
    while(q&&q->data != x)
    {
        q = q->rlink;
    }
    if(!q)
    {
        printf("x doesn't exist!\n");
    }
    if(q==head && head->rlink)	//被删除的结点是第一个且不止这一个
    {
        head = head->rlink;	//head = NULL;
        head->llink = NULL;
        free(q);
        return head;
    }
    if(q==head && !head->rlink)	//被删除的结点是第一个且只有这一个
    {
        free(q);
        return NULL
    }
    else
    {
        if(!q->rlink)			//被删除的是最后一个结点
        {
            q->llink->rlink = NULL;
            free(q);
            return head;
        }
        else					//被删除的是2个结点以上的链表非开始、亦非结尾的结点
        {
            q->llink->rlink = q->rlink;
            q->rlink->llink = q->llink;
            free(q);
            return head;
        }
    }
    
    
}

带头结点的双向链表的初始化

dlink *init()
{
    dlink *head;
    head = (dnode *)malloc(sizeof(dnode));
    head->prior = NULL;
    head->next  = NULL;
    return head;
}

带头结点双向链表的插入算法

条件： i范围为 1≤i≤ 表长+1

dlink *insertlist(dlink *head, int i, datatype x)
{
    dlink *p, *q;
    int j=0;
    p = head;
    if(i<0)
    {
        printf("The position is wrong!\n");
        return head;
    }
    while(p&&j<i-1)
    {
        p = p->next;
        j++;
    }
    if(p&&j=i-1)
    {
        q = (dlink *)malloc(sizeof(dlink));
        q->data = x;
        q->next = p->next;
        p->next->prior = q;
        p->next = q;
        q->prior = p;
    }
    return head;
}

带头结点的双向链表的删除算法

条件：i范围为1≤i≤ 表长

dlink *delete(dlink *head; int i, datatype x)
{
    dlink *p, *q;
    p = head;
    int j = 1;
    if(i<0)
    {
        printf("The position is wrong!\n");
        return head;
    }
    while(p&&j!=i)
    {
        p = p->next;
        j++;
    }
    if(p&&j=i)
    {
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
        return head;
    }
}

栈

基本概念及描述：

栈是一种特殊的线性表，规定它的插入运算和删除运算均在线性表的同一端进行，进行插入的和删除的那一端称为栈顶，另一端称为栈底。

栈的插入和删除操作分别简称为：入栈、出栈

栈的特点：先进后出

Next Post

Linux_learning_record
Previous Post

Cortex-M3(STM32F107)_Learning_Notes

CATALOG

1. Data Structure
1.6. 栈
1. 1.6.1. 基本概念及描述：
1.7.



Data Structure(C)

Data Structure

概述 基本概念

算法

线性表

线性表及其特点：

首先，定义顺序表存储结构体：

线性表初始化算法

线性表 addlist 添加算法

线性表的插入算法

线性表的删除算法

线性表的打印算法

判断线性表是否为空

单链表：线性表的链式存储结构之一

概念：

特点：

类型定义：

初始化

初始化带头结点的单链表

打印各个元素的值

在链表中查找第 i 个元素

在链表中查找值为 x 的元素

插入算法 listinsert（带头结点的链表）

删除算法 ListDelete（带头结点的链表）

将两个有序链表并为一个有序链表

建立链表的方式

循环链表

循环单链表

初始化一个循环单链表

获得循环单链表最后一个结点的存储地址

双向链表

类型定义

初始化

输出各个结点的值

查找第 i 个结点的存储地址

插入操作

删除操作（删除一个值为 x 的结点）

带头结点的双向链表的初始化

带头结点双向链表的插入算法

带头结点的双向链表的删除算法

栈

基本概念及描述：

概述基本概念