实现的一下基本数据结构
- 时间:
- 浏览:2
- 来源:跟我学网络
重新整理了一下基本的数据结构,自己在C下实现了基本的东西，这里只包括单链表，双链表，单链表实现的队列和栈，想想自己写了，还是要整理一下，第一学习一下重构，第二补上大学不知到是自己荒废的东西还是大学让我本身荒废的东西。一点点整理，更新持续中。
关于树和图，后面会加上
资源:http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
一个可视化数据结构的，很有意思
测试结构
环境 Ubuntu 10.10
gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
1. 单链表
头节点，下一个节点，以线性方式串联一起，此种结构的删除和增加数据的效率高，查询效率需要按节点一个一个的遍历，按线性查找。
a.头文件 slinkh.h
------------------------------------------------------------slinkh.h
#define TRUE 1#define FALSE 0
typedef struct NODE {
struct NODE *link;
char *name;
}Node;
/*
** 创建一个节点
**
*/
Node* create_node();
/*
** 打印一个函数的节点所带信息
**
*/
void printf_node(Node *head,char *name);
/*
** 释放内存 回收
*/
void free_node(Node *head,char *name);
/*
** 插入节点
**
*/
int insert_node(Node *head,char *name);
/*
** 删除节点 释放内存
*/
int dele_node(Node *head,char *name);
/*
** 遍历所有节点 采用回调函数的方式 处理数据
**
*/
void foreach_node(Node *head,void (*fuction)(Node *curr, char *name));
/*
** 查找节点
*/
Node* search_list(Node *node,char *name);
b.具体实现 slink.c
--------------------------------------------------------slink.c
#include "slinkh.h"#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NAME_LENGTH 10
#define FALSE 0
#define TRUE 1
/*
** author:srgzyq
** email:srgzyq@gmail.com
*/
/*
** 创建一个节点实现 支持的name字符的长队为10
**
*/
Node* create_node()
{
Node *new = (Node *)malloc(sizeof(Node));
if(new == NULL)
return NULL;
// 开辟数组
char *name = (char *)calloc(NAME_LENGTH,sizeof(char));
if(!name)
{
free((Node *)new);
return NULL;
}
new->name = name;
return new;
}
void printf_node(Node *pNode,char *name)
{
printf("name: %s\n",pNode->name);
}
void free_node(Node *pNode, char *name)
{
Node *curNode = pNode;
free((Node *)curNode);
printf("free node: %s\n",name);
}
/*
** 遍历所有节点
** @param head 头节点
** @param fuction 为回调函数
*/
void foreach_node(Node *head,void (*fuction)(Node *curr,char *name))
{
Node *currNode = head->link;
Node *nextNode;
while(currNode != NULL)
{
nextNode = currNode->link;
fuction(currNode,currNode->name);
currNode = nextNode;
}
}
/**
** 插入函数没有走foreach_node回调，主要是自己懒，不想改了
*/
int insert_node(Node *head,char *name)
{
Node *currNode = head->link;
Node *preNode = head;
Node *new = create_node();
if(new == NULL)
return FALSE;
new->name = name;
while((currNode != NULL && compare_name(currNode->name,name) < 0))
{
preNode = currNode;
currNode = currNode->link;
}
preNode->link = new;
new->link = currNode;
return TRUE;
}
/*
** 删除函数没有走foreach_node回调，主要是自己懒，不想改了
**
*/
int dele_node(Node *head,char *name)
{
Node *currNode = head->link;
Node *preNode = head;
while(currNode != NULL && compare_name(currNode->name,name) != 0)
{
preNode = currNode;
currNode = currNode->link;
}
if(currNode != NULL)
{
preNode->link = currNode->link;
free_node(currNode,currNode->name);
}
return TRUE;
}
int compare_name(char const *name,char const *key_name)
{
return strcmp(name,key_name);
}
Node* search_list(Node *node,char *name)
{
node = node->link;
while(node != NULL)
{
if(compare_name(node->name,name) == 0)
break;
node = node->link;
}
return node;
}
c.测试代码slinktest.c (注:用了兄弟伙的名字）
---------------------------------------------------------------------------slinktest.c
#include "slinkh.h"#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARR_LEN 5
char data_arr[][10] = {"wangbo","raodie","niba","bobo","pengdui"};
int main()
{
Node *head = create_node();
head->link = NULL;
int index;
for(index = 0; index <ARR_LEN; index++)
{
insert_node(head,data_arr[index]);
}
dele_node(head,data_arr[1]);
foreach_node(head,printf_node);
Node *keynode = search_list(head,data_arr[4]);
if(keynode != NULL)
printf_node(keynode,keynode->name);
foreach_node(head,free_node);
return EXIT_SUCCESS;
}
d.编译输出
gcc -o2 -o slinktest slink.c slinktest.c
./ slinktest
free node: raodi
name: bobo
name: niba
name: pengdui
name: wangkun
name: pengdui
free node: bobo
free node: niba
free node: pengdui
free node: wangkun
（ok 未完待述）
回想在交大大二学习这些东西的时候，相当的痛苦，不知到老师讲什么，即使知道了也无法去下手实现，当年就这样浑浑噩噩的过了这门课。想想当时的心境，其实蛮可悲的，一方面想学好，可以没有入门，老师，飞快的说着XXXX，其实当时自己的水平，真想老师把我当成初中生来教，结果每次的声音你们不会啊，这不是我的责任，是XXXX，有点感叹大学的教育，花了钱却买不到服务，自己很是尴尬，顾客是上帝，但大学不是走这条商业法则，调侃一下大学这东西，像公司像工厂像机关，其结果是四不像，所以大家都是混，混玩了四年，出来不想在进去了，要进去也要去试试西方所谓的腐朽的文化教育。