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大小的空间,返回指向新节点的指针pnodeNode_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;//节点数+1plink->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){//将找到的节点的数据域更新为新数据newdataptmp->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;//保存当前头节点到临时指针ptmpplink->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");
}