C语言与数据结构：从基础到实战

C 语言：1.基本的C语法和简单算法

               2.面向过程的编程思想

数据结构：1.常用的数据存储结构

                  2.算法

                  3.面向对象的编程思想

1.什么是数据结构？

        数据结构：用来组织和存储数据

        程序=数据结构+算法

2.数据于数据之间的关系

（1）逻辑关系：数据元素与元素之间的关系

        集合：元素与元素之间平等的集合关系

        线性结构：数据元素与元素之间存在一对一的关系（顺序表，链表，队列，栈）

        树形结构：数据元素与元素之间存在一对多的关系（二叉树）

        图形结构：数据元素与元素之间存在多对多的关系（网状结构）

（2）物理结构：数据元素在计算机内存中的存储方式

        顺序结构：在内存中选用一段连续内存空间进行存储

        数据访问方便，插入和删除数据时需要移动大量数据，需要预内存分配，可能造成大量内存碎片

        链式结构：可以在内存中选用一段非连续的内存空间进行存储

        数据访问必须从头遍历（o（n）），插入和删除元素方便，不需要预内存分配，是一种动态存储的方式

        索引结构：将要存储的数据的关键字和存储位置之间构建一个索引表

        散列结构（哈希结构）：将数据的存储位置与数据元素之间的关键字建立起对应的关系（哈数关系），根据该关系进行数据存储和查找

3.基本功能：

1.指针

2.结构体（封装）

3.动态内存分配

4.数据结构内容

1.链式表

单向链表

双向链表

循环链表

内核链表        

2.栈

3.队列

4.二叉树

5.哈希表

6.常用算法

单项链表：

link.h

#ifndef _LINK_H_
#define _LINK_H_

typedef int Data_tape_t;

/*定义链表节点结构体*/
typedef struct node
{
    //节点存储的数据
    Data_tape_t data;
    //指向下一个节点的指针
    struct node *pnext;
}Node_t;

/*定义链表对象结构体*/
typedef struct link
{
    //链表首节点的指针
    Node_t phead;
    //节点的个数
    Data_tape_t clen;
}Link_t;

extern Link_t *create_link();

extern int insert_link_head(Link_t *plink,Data_type_t data);

extern void link_for_each(Link_t *plink);

extern int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata);

extern int is_empty_link(Link_t *plink);

extern int insert_link_tail(Link_t *plink, Data_type_t data);

extern int delete_link_tail(Link_t *plink);

extern void destroy_link(Link_t *plink);

#endif

liink.c

#include<stdio.h>
#include<stdlib.h>
#include"link.h"

/*创建单向链表*/
Link_t *create_link()
{
    Link_t *plink = malloc(sizeof(Link_t));
    if(NULL == plink)
    {
        printf("malloc erroe!\n");
        return NULL;
    }
    else
    {
        plink->phead = NULL;
        plink->clen = 0;
    }
    return plink;
}

/*头插函数*/
函数功能：向链表头部插入新节点（头插法）
参数：
    -plink：指向链表对象的指针
    -data：插入的具体数据
返回值：0表示插入成功，-1表示内存分配失败

int insert_link_haed(Link_t *plink, Data_type_t data)
{
    //malloc分配Node_t大小的空间，返回指向新节点的指针pnode
    Node_t *pnode = malloc(sizeof(Node_t));
    //判断内存分配是否成功
    if(NULL == pnode)
    {
        printf("malloc erroe\n");
        return -1;
    }
    else
    {
        //初始化新节点
        pnode->data = data;
        pnode->pnext = NULL;
    }
    //新节点的后继指针指向原链表的头节点
    plink->pnode = plink->phead;
    //链表的头指针指向新节点
    plink->phead = pnode;
    //节点数+1
    plink->clen++;
    
    return 0;
}

//遍历链表并输出所有节点的数据
void link_for_each(Link_t *plink)
{
    Node_t *ptmp = plink->phead; 
    while(ptmp != NULL)
    {
        printf("%d ",ptmp->data);
        ptmp = ptmp->pnext;       
    }
    printf("\n");
}

/*查找链表中包含指定数据的节点*/
Node_t *find_link(Link_t *plink,Data_type_t mydata)
{
	Node_t *ptmp = plink->phead;
	while(ptmp != NULL)
	{
		//比较当前节点的数据与指定的数据是否相等
		if(ptmp->data == mydata)
		{
			//找到对应节点，返回该节点的指针
			return ptmp; 
		}
		ptmp = ptmp->pnext;
	}
		return NULL;
}

/*更新数据*/
//函数功能：在链表中查找旧数据对应节点并更新为新数据
//参数说明：
//-plink ：指向链表结构体Link_t的指针
//-olddata：旧数据
//-newdata：新数据
//返回值：0 表示更新成功，-1 表示更新失败
int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata)
{
	//调用find_link函数查找存储olddata的节点，返回指向该节点的指针
	Node_t *ptmp = find_link(plink,olddata);
	if(ptmp != NULL)
	{
		//将找到的节点的数据域更新为新数据newdata
		ptmp->data = newdata;
		return 0;
	}
	return -1;
}

/*判断链表是否为空链表*/
int is_empty_link(Link_t *plink)
{
	return NULL == plink->phead;
}

/*首删*/
/*删除链表的头节点*/
int delete_link(Link_t *plink, Data_type_t data)
{
	if(is_empty_link(plink))
	{
		return -1;
	}
	Node_t *ptmp = plink->phead;//保存当前头节点到临时指针ptmp
	plink->phead = ptmp->pnext;//更新链表头节点为原头节点的下一个节点
	free(ptmp);//释放原头节点的内存
	//链表节点数减一
	plink->clen--;
	
	return 0;
}

/*尾插*/
int insert_link_tail(Link_t *plink, Data_type_t data)
{
    Node_t *pnode = malloc(sizeof(Node_t));
    
    if(NULL = pnode)
    {
		printf("malloc erroe!\n");
		return -1;
	}
	pnode->data = data;
	pnode->pnext = NULL;
    
    if(is_empty_link(plink))
	{
		plink->phead = pnode;
	}
	else
	{
		Node_t *tail = plink->phead;
		while(tail->pnext != NULL)
		{
			tail = tail->pnext;
		}
		tail->pnext = pnode;
	}
	plink->clen++;
	return 0;
}

/*尾删*/
int delete_link_tail(Link_t *plink)
{
	if(is_empty_link(plink))
	{
		return -1;
	}
	if(plink->phead->pnext == NULL)
	{
		free(plink->phead);
		plink->phead = NULL;
		plink->clen--;
		return 0;
	}
	Node_t *ptmp = plink->phead;
	while(ptmp->pnext->pnext != NULL)
	{
		ptmp = ptmp->pnext;
	}
		free(ptmp->pnext);
		ptmp->pnext = NULL;
		plink->clen--;
		return 0;
}

/*销毁链表*/
//函数功能：释放链表占用的所有内存空间，包括链表节点和链表对象
//参数：-plink是指向链表对象的指针
void destroy_link(Link_t *plink)
{	
	//若plink为NULL，则说明没有链表对象，直接返回
	if(plink == NULL)
	{
		return ;
	}
	//定义临时指针ptmp，初始化为链表的头节点的指针
	Node_t *ptmp = plink->phead;
	//若ptmp为NULL，则说明链表为空，直接释放链表对象的内存，返回
	if(ptmp == NULL)
	{
		free(plink);
		return ;
	}
	Node_t *temp;
	while(ptmp->pnext != NULL)
	{
		//暂存当前节点的下一个节点指针，防止释放当前节点后丢失后续节点
		temp = ptmp->pnext;
		//释放当前节点
		free(ptmp);
		//将下一个节点的指针赋值给当前节点
		ptmp = temp;
	}
	//释放最后一个节点
	free(ptmp);
	//释放链表对象
	free(plink);
	printf("YES\n");
}