搜索
查看: 1859|回复: 0

经典数据结构和算法回顾

[复制链接]

6

主题

0

回帖

29

积分

新手上路

积分
29
发表于 2016-10-22 14:53:03 | 显示全部楼层 |阅读模式
  最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉强整理了下面写的一些代码,这些代码有的有参考别人的代码,但都是自己曾经一点点敲的,挂出来,虽然很基础,但希望能对别人有帮助。

  链表

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

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

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

  单项链表的数据结构

  如下

  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;

  }

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

 
 
大数据行业交流
大数据行业交流
大数据求职招聘
大数据求职招聘
站长电话:
15010106923
微信联系:
hb-0310
站长邮箱:
ab12-120@163.com
大数据中国微信

QQ   

版权所有: Discuz! © 2001-2013 大数据.

GMT+8, 2024-3-29 19:49 , Processed in 0.071026 second(s), 24 queries .

快速回复 返回顶部 返回列表