经典数据结构和算法回顾

柠檬墨绿色

　　最近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。

　　链表

　　链表是一种非常基本的数据结构，被广泛的用在各种语言的集合框架中。

　　首先链表是一张表，只不过链表中的元素在内存中不一定相邻，并且每个元素都可带有指向另一个元素的指针。

　　链表有，单项链表，双向链表，循环链表等。

　　单项链表的数据结构

　　如下

　　typedef struct NODE{

　　struct NODE * link;

　　int value;

　　} Node;

　　对链表的操作

　　主要有增删查

　　Node * create（）{

　　Node * head,* p,* tail;

　　//  这里创建不带头节点的链表

　　head=NULL;

　　do

　　{

　　p=（Node*）malloc（LEN）；

　　scanf（"%ld",&p->value）；

　　if（p->value ==0） break;

　　//  第一次插入

　　if（head==NULL）

　　head=p;

　　else

　　tail->link=p;

　　tail=p;

　　}

　　while（1）；

　　tail->link=NULL;

　　return head;

　　}

　　int delet（Node **linkp,int del_value）{

　　register Node * current;

　　Node * m_del;

　　//寻找正确的删除位置，方法是按顺序访问链表，直到到达等于的节点

　　while（（current = *linkp）！=NULL  &&  current->value != del_value）

　　{

　　linkp = &current->link;

　　}

　　if（NULL==current）

　　return FALSE;

　　else

　　{

　　//把该节点删除，返回TRUE

　　m_del=current->link;

　　free（current）；

　　*linkp=m_del;

　　}

　　return TRUE;

　　}

　　//需要形参为链表头指针的地址和要插入的值

　　int insert（Node **linkp,int new_value）{

　　register Node * current;

　　Node * m_new;

　　//寻找真确的插入位置，方法是按顺序访问链表，直到到达其值大于或等于新插入值的节点

　　while（（current = *linkp）！=NULL  &&  current->value < new_value）

　　{

　　linkp = &current->link;

　　}

　　//为新节点分配内存，并把新值存到新节点中，如果分配失败，返回FALSE

　　m_new =（Node*）malloc（LEN）；

　　if（NULL==m_new）

　　return FALSE;

　　m_new->value = new_value;

　　//把新节点放入链表，返回TRUE

　　m_new->link = current;

　　*linkp=m_new;

　　return TRUE;

　　}

　　仅仅只需要将尾指针指向头节点，就可以构成单项循环链表，即tail->link=head;，有的时候，可能需要将链表逆置，当然，如果需要逆置，最好一开始就做双向链表。

　　Node * reverse（Node * head）{

　　Node * p,*q;

　　q= head;

　　p = head->link;

　　head = NULL;

　　while（p）

　　{

　　//  接到新链表里面去

　　q->link = head;

　　head  = q;

　　//  继续遍历原来的链表

　　q = p;

　　p = p->link;

　　}

　　q->link = head;

　　head  = q;

　　return  head;

　　}

　　删除链表中所有值为x的节点，以及清除链表中重复的节点

　　//    功能：    删除链表中所有值为x的节点

　　//    形参：    1、若不带头结点，便是链表头指针的地址，即&head

　　//            2、若带头结点，便是链表头节点的next域的地址，即&head->next

　　//    形参：    为链表头指针的地址和要删除的值

　　void del_link（Node ** plink,int x）{

　　register Node * current;

　　while（（current = *plink）！=NULL）

　　{

　　// 处理连续出现x的情况

　　while（current && current->data == x）{

　　//  保留指向下一个节点的指针

　　Node * temp = current;

　　* plink = current = current->next;

　　//  删除当前节点

　　free（temp）；

　　}

　　//向下遍历链表

　　if （current）

　　{

　　plink = &current->next;

　　}

　　}

　　}

　　//    功能：    删除链表中重复多余的节点

　　//    形参：    1、若不带头结点，便是链表头指针的地址，即&head

　　//            2、若带头结点，便是链表头节点的next域的地址，即&head->next

　　void del_linkAll（Node ** plink）{

　　register Node * current;

　　while（（current = *plink） != NULL）{

　　//注意，这里取指向下一个元素的指针的地址，这样删除是会保留这一个节点

　　del_link（&current->next,current->data）；

　　plink = &current->next;

　　}

　　}

　　对于双向链表，也就是在节点中再添加一个节点，让它与另一个指针指向的方向相反。当然，当节点有了两个节点之后，就可以构成更复杂的比如树图等复杂结构了，双向链表可像如下定义

　　#ifndef __LINKLISTEX_H__

　　#define __LINKLISTEX_H__

　　#include <string>

　　using std::string;

　　//================双向链表的定义===============

　　template<class T>

　　class DulLinkList

　　{

　　private:

　　typedef struct DulNode{

　　struct DulNode * prior;

　　T    data;

　　struct DulNode * next;

　　}DulNode;

　　DulNode * frist;

　　void Init（）；

　　void Del（DulNode * delNode）；

　　public:

　　DulLinkList（）；

　　~DulLinkList（）；

　　void AddElem（const T &  data）；

　　void DelElem（const T & data）；

　　string ToString（）const;

　　protected:

　　};

　　#endif//__LINKLISTEX_H__

　　对双向链表的操作也无外乎增删改

　　#include "LinkListEx.h"

　　#include <iostream>

　　using namespace  std;

　　template<class T>

　　DulLinkList<T>::DulLinkList（）{

　　Init（）；

　　}

　　template<class T>

　　void DulLinkList<T>::Init（）{

　　// 初始化第一个结点

　　this->frist = new DulNode;

　　this->frist->prior = NULL;

　　this->frist->next = NULL;

　　}

　　template<class T>

　　void DulLinkList<T>::AddElem（const T & data）{

　　// 直接头部插入节点

　　DulNode * newNode = new DulNode;

　　newNode->data = data;

　　newNode->next = this->frist;

　　newNode->prior = NULL;

　　this->frist->prior = newNode;

　　this->frist = newNode;

　　}

　　template<class T>

　　void DulLinkList<T>::DelElem（const T & data）{

　　DulNode * current = this->frist->next;

　　while （current  != NULL  && current->data != data） {

　　current = current->next;

　　}

　　if （！current）

　　{

　　return;

　　}

　　Del（current）；

　　}

　　template<class T>

　　void DulLinkList<T>::Del（DulNode * delNode）{

　　// 调整当前节点两端的节点的指针

　　delNode->prior->next = delNode->next;

　　delNode->next->prior = delNode->prior;

　　delete delNode;

　　}

　　template<class T>

　　DulLinkList<T>::~DulLinkList（）{

　　DulNode * current = this->frist;

　　while （current）

　　{

　　DulNode * old = current;

　　current = current->next;

　　delete old;

　　}

　　}

　　template<class T>

　　string DulLinkList<T>::ToString（）const{

　　string res;

　　DulNode * current = this->frist->next;

　　while （current）

　　{ www.9ask.cn/xiamen/

　　res.append（1,current->data）；

　　current = current->next;

　　}

　　return res;

　　}