线性表学习材质整理,求单向链表倒序第m个成分

by admin on 2019年8月29日

原题为某玩耍集团试题,大要如下: 
对于几个单向链表,试写出找到它的倒序第m个成分(m >=
1)的函数,注意变量命名、注释、时间复杂度、空间复杂度。注:要求写出可编写翻译并得以运作通过的程序代码。

数据结构练手02 双向链表达成,数据结构练手02完成

双向链表完结

前日夜晚用模板方法把双向链表达成了下,由于有一些小疏忽,在
insert中手抖了下,把tail->prev 打成了
tail->next,由于错误是发出在drop函数试行时,让自家直接去调drop函数,调了半天仍旧一直以来错误,最终自身系统在vs中监视了下值的浮动,终于看到是insert出错了。
看来技术员离不开调试呀。

除此以外,明日说的模板输出重载,作者说要在友元的兑现时拉长 <>,
但是前些天自身在gcc中测量试验了下,居然说找不到特出的函数,导致编译不经过,真心蛋疼,vs和g++的界别还真挚大,看来改天要美丽专研下模板输出重载,知道的朋友期待能够告诉下。


对数据结构的兑现,其实都很简短,思想就是:

1、定义结点结构类,蕴含数据域和指针域

2、定义
链表(树,图)结构,个中封装包蕴多少个结点,作为数据接口,因为节点定义指向自己类型的指针,由此而后有着的操作都围绕那一个数据接口实行。


对于双向链表来讲,结点定义很简单,三个数据域,二个next指针,表示现在她将针对下多个结点;
一个prev指针,表示它将指向前三个结点。

bf88必发唯一官网 1

template<typename T>

struct Node{

    T datum;

    Node* next;

    Node* prev;

};

bf88必发唯一官网 2

出于链式结构丰盛的结点都要new出来,且结点类蕴涵了数据域,因而要求对结点类举行构造函数的编辑,一般五个,带数据域的(今后new来做链表中结点),私下认可无参的(用于new给head和tail的);析构函数就无须了,因为其指针域所针对的东西是由表结构new出来的,操作应该留给表。

结点类定义好了后,大家定义下链表类,首要部分便是要含有下 head 指针,
tail 指针。

除此以外,全体的表(树,图结构)最佳富含个 “表示长度的数量”,如size,
那样求length()操作只要O(1)的复杂度,要否则将在遍历整个链表,复杂度正是O(n)了。

对此head指针,规定 head->next 指向首个结点,head->prev
指向自个儿或NULL;

对于tail指针,规定 tail->prev
指向最终二个结点,tail->next指向自己或NULL; 
这样规定了head,tail后,后边的操作就能够很顺利,大家就能够next/prev到底了,哈哈。

空的尺度为: size == 0 或然 head->next == NULL 或然 tail->prev ==
NULL ,看个人喜好。

剩余部分增加和删除改查操作,别手抖写错了指向关系就行,其他能够增进三个职责剖断,看看是发端或从尾早先,哪边移动的少。

函数写法能够给的提出是:

若只是探问不改造,成员函数为const;

若供给操作类类型,则用 & 或 const&;

好的,直接上代码:

先是头文件,注意末了一行;

bf88必发唯一官网 3 1
#ifndef MY_CHAIN_H 2 #define MY_CHAIN_H 3 #include
<ostream> 4 using namespace std; 5 template <class T> 6
struct Node{ 7 T datum; 8 Node* prev; 9 Node* next; 10 11 Node(const
T& x); 12 Node(); 13 }; 14 15 16 template<class T> 17 class dList{
18 public: 19 dList(); 20 ~dList(); 21 bool find(int pos,T& hold) const;
22 int search(const T& x) const; 23 int length() const; 24 bool
isEmpty() const; 25 dList<T>& drop(int pos, T& hold); 26
dList<T>& insert(int pos, const T& x); 27 dList<T>&
push_back(const T& x); 28 dList<T>& push_front(const T& x); 29
T& operator[](int pos); 30 void show(std::ostream& os) const; 31
friend ostream& operator<< <>(ostream& os, const dList& d);
32 protected: 33 Node<T>* head; 34 Node<T>* tail; 35 int
size; 36 }; 37 #endif 38 39 #include “chain.cpp” View Code

随着是落到实处公文:

bf88必发唯一官网 4#ifndef
MY_CHAIN_CPP #define MY_CHAIN_CPP #include “chain.h” #include
<ostream> #include <cassert> using std::ostream; //
节点类的协会 template<class T> Node<T>::Node(const T& x) :
datum(x){ next = prev = NULL; } template<class T>
Node<T>::Node(){ next = prev = NULL; datum = 0; } //
双向链表类的构造 template<class T> dList<T>::dList() { head
= new Node<T>(); // tail = new Node<T>(); head->next =
NULL; head->prev = head; tail = head; tail->next = tail;
tail->prev = NULL; size = 0; } // 析构 template<typename T>
dList<T>::~dList() { if(head){ //
一个建议,若类中数据成员是指针类型,且指向是由此new出来的,那么最棒这里丰盛二个肯定。
当然笔者这里是多余的,因为结构时必然new了。 Node<T>* p =
head->next; Node<T>* t; while(p != NULL){ t = p; p =
p->next; delete t; } delete head; head = NULL; // 最好删除后指向空
tail = NULL; } } template<class T> bool dList<T>::isEmpty()
const { return size == 0; } template<class T> bool
dList<T>::find(int pos,T& hold) const // 访谈不修改,成员函数const
{ if(pos < 1 || pos > size) return false; Node<T>* p;
if(pos <= (size>>1)){ // 从头开端比非常的慢 p = head; int count =
pos; while(count–){p = p->next;} // next 给 head }else{ p = tail; //
从尾开首相当慢 int count = size – pos; while(count–){p = p->prev;}
// 哈哈,中就是为什么把prev给tail, 代码是或不是很顺利? } hold =
p->datum; return true; } template<class T> int
dList<T>::search (const T& x) const { Node<T>* p =
head->next; int count = 1; while((p!= NULL) && (p->datum != x)){ p
= p->next; count++; } if (p == NULL) { return 0; } return count; }
template<class T> int dList<T>::length ()const { return
size; } template<class T> dList<T>&
dList<T>::push_front (const T& x) // 前插 { Node<T>* p =
new Node<T>(x); if (size == 0) { head->next = p; p->prev =
NULL; tail->prev = p; p->next = NULL; }else{ p->next =
head->next; head->next->prev = p; p->prev = NULL;
head->next = p; } ++size; return *this; } template<class T>
dList<T>& dList<T>::push_back (const T& x) // 尾插 {
Node<T>* p = new Node<T>(x); if (tail->prev == NULL) {
head->next = p; p->prev = NULL; tail->prev = p; p->next =
NULL; }else{ tail->prev->next = p; p->prev = tail->prev;
p->next = NULL; tail->prev = p; } ++size; return *this; }
template<class T> dList<T>& dList<T>::insert(int pos,
const T& x) // 钦命地点插入,范围[1,size+1]
注意,小编的代码中,1为下标起始;除了前面重载的[]操作符。 { if (pos ==
1) { return push_front (x); } if (pos == (size+1)) { return push_back
(x); } Node<T>* in = new Node<T>(x); Node<T>* p; if
(pos <= (size/2)) { p = head; int t = pos; while(t–){p =
p->next;} }else{ p = tail; int t = size – pos; while(t–){p =
p->prev;} } in->next = p; in->prev = p->prev; //
哎,这里正是自个儿万恶马虎的地点,Mark下,后一次要心细点。 p->prev->next
= in; p->prev = in; ++size; return *this; } template<class T>
dList<T>& dList<T>::drop(int pos, T& hold) { if (pos < 1
|| pos > size) { exit(1); } Node<T>* d = NULL; if(pos == 1){ d
= head->next; hold = d->datum; if(size == 1){ tail->prev =
NULL; head->next = NULL; }else{ head->next = d->next;
d->next->prev = NULL; } –size; delete d; d = NULL; return *this;
} if(pos == size){ d = tail->prev; hold = d->datum; tail->prev
= d->prev; d->prev->next = NULL; size–; delete d; d = NULL;
return *this; }else{ if(pos <= (size/2)){ int c=pos; d = head;
while(c–){d = d->next;} }else{ int c = size – pos; d = tail;
while(c–){d = d->prev;} } hold = d->datum; d->prev->next =
d->next; d->next->prev = d->prev; –size; delete d; d =
NULL; return *this; } } template<class T> T&
dList<T>::operator[](int pos) { pos = pos + 1; if(pos<1 ||
pos> size) { exit(1); } Node<T>* p = NULL; if (pos <=
(size>>1)) { int t = pos; p = head; while(t–){p = p->next;}
}else{ int t = size – pos; p = tail; while (t–) { p = p->prev;} }
return p->datum; } template<class T> void dList<T>::show
(ostream& os) const { Node<T>* p = head->next; int t = 0;
while(p != NULL){ os << p->datum << ” “; p = p->next;
t++; } assert(t==size); } template<class T> ostream&
operator<< <>(ostream& out, const dList<T>& x) {
x.show(out); return out; } #endif View Code

最终是测试文件:

bf88必发唯一官网 5 1
#include “chain.h” 2 #include <iostream> 3 using namespace std;
4 5 int main() 6 { 7 dList<int> dl; 8 int x=0; 9 dl.insert (1,5);
10 cout << “insert pos1 5: ” << dl << endl; 11 cout
<< “length: ” << dl.length() << endl; 12
dl.push_front (3); 13 cout << “push front 3: ” << dl
<< endl; 14 cout << “length: ” << dl.length() <<
endl; 15 dl.push_back (6); 16 cout << “push back 6: ” << dl
<< endl; 17 cout << “length: ” << dl.length() <<
endl; 18 dl.insert(4,8); 19 cout << “insert pos4 8: ” << dl
<< endl; 20 cout << “length=” << dl.length () <<
endl; 21 dl.find (3,x); 22 dl.drop(2,x); 23 cout << “drop pos 2: ”
<< dl << endl; 24 cout << “length=” << dl.length
() << endl; 25 cout << “dl[0]=” << dl[0] <<
endl; 26 dl[0] = 10; 27 cout << “dl[0]=” << dl[0]
<< endl; 28 cout << dl << endl; 29 } View Code

结果如下图所示:

bf88必发唯一官网 6

补给:
其实还足以重载越来越多的操作符,有情怀的爱侣能够和煦增多下,比方++(int),
++操作等。以致,能够加入个迭代器类,那样更方便使用,有的时候间能够实现下哦。

另外,心细,心细,手别抖。 自勉下!

双向链表完成,数据结构练手02达成双向链表完成 前日晚上用模板方法把双向链表达成了下,由于有一点小大意,在
insert中…

一.线性表

线性表是最大旨、最简易、也是最常用的一种数据结构。线性表中数据成分之间的涉嫌是一对一的涉嫌,即除去第二个和结尾三个数量成分之外,其它数据元素都以首尾相接的。线性表的逻辑结构轻易,便于达成和操作。因而,线性表这种数据结构在实质上采取中是遍布采纳的一种数据结构。

  数据结构中的链表的本性是因素都以FIFO(First In First
Out),当中链表又分单向链表与双向链表。

 
那道题的平常做法大概说首先想到直觉的思绪是先求得链表的尺寸,即成分总个数n,然后难题转化为求顺序第n-m+1个因素。不过出于这种办法要先总括长度,多了叁遍遍历,成效不高,并且也不高内聚,因为依赖于求长度这么些运算,而那么些运算完全可单独出来,为了尽恐怕高内聚,裁减对另外运算的重视,要求进一步怀恋以求得更方便人民群众快速的算法,其实能够这么做,先求得顺序第m个成分,用一指针P指向这些因素,用另一指针POdyssey指向链表的尾部,以后好了,P和PQashqai同一时间向右移动,直到P为空,则P揽胜就是须要的倒序第m个因素,倘若因m超越界限,则PRubicon为空,表示没找到,那样一来,只需一次遍历就够了。C++代码描述如下
 1template<typename T>
 2struct Node
 3{ 
 4    T  data;    /**////< 数据
 5    Node* next;  ///< 指向下一结点的指针
 6} ;
 7
 8template<typename T>
 9Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++n == m)
16        {
17            pR = head;
18            continue;
19        }
20        if (pR)
21        {
22            pR = pR->next;
23        }
24    }
25    return pR;
26}

1.1结构

线性表是一种常用的数据结构,以下介绍线性表及其顺序存款和储蓄,并对栈和队列及它们的依次落成给出了详尽的规划描述。

在实质上选用中,线性表都以以栈、队列、字符串等特殊线性表的样式来采纳的。由于那几个特种线性表都具备各自的天性,因而,精晓这一个特殊线性表的特色,对于数据运算的可相信性和拉长操作成效皆以注重的。

线性表是三个线性结构,它是三个暗含n≥0个结点的星星种类,对于当中的结点,有且独有二个上马结点未有前人但有三个后继结点,有且唯有一个终端结点未有后继但有多少个前任结点,别的的结点都有且唯有二个先驱和一个后继结点。一般地,多个线性表能够象征成一个线性种类:k1,k2,…,kn,个中k1是起初结点,kn是终极结点。

是三个数量成分的不改变(次序)集

单向链表中种种成分都有叁个对准下一成分的指针,而双向链表在单向链表的根基上,扩大了一个指向前三个因素的指针。

对于叁个单向链表,试写出找到它的倒序第m个成分(m =
1)的函数,注意变量命名、注释、时间复杂度、…

1.2特征

线性结构的基本特征为:

1.集聚中必存在独一的二个”第一因素”;

2.聚众中必存在唯一的四个 “最终元素” ;

3.除终极二个因素之外,均有 唯一的后继(后件);

4.除率先个因素之外,均有 唯一的先驱者(前件)。

由n(n≥0)个数据成分(结点)a1,a2,…,an组成的少数体系。

数量成分的个数n定义为表的长短。

当n=0时称之为空表。

一再将非空的线性表(n>0)记作:

(a1,a2,…an)

数量成分ai(1≦i≦n)只是多个浮泛的符号,其现实意思在分化的气象下能够分化。

线性表的基本操作

1)MakeEmpty(L) 那是一个将L变为空表的法子

2)Length(L) 再次回到表L的长度,即表瓜时素个数

3)Get(L,i) 那是三个函数,函数值为L中地方i处的成分(1≤i≤n)

4)Prev(L,i) 取i的前任成分

5)Next(L,i) 取i的后继成分

6)Locate(L,x) 那是一个函数,函数值为要素x在L中的地点

7)Insert(L,i,x)在表L的岗位i处插入成分x,将原攻下地点i的因素及末端的因素都向后推贰个职位

8)Delete(L,p) 从表L中剔除地方p处的成分

9)IsEmpty(L) 即使表L为空表(长度为0)则赶回true,否则重临false

10)Clear(L)清除全体因素

11)Init(L)同第贰个,开端化线性表为空

12)Traverse(L)遍历输出全部因素

13)Find(L,x)查找并赶回成分

14)Update(L,x)修改成分

15)Sort(L)对具有因素重新按给定的原则排序

16) strstr(string1,string2)用于字符数组的求string第11中学冒出string2的首地址

    前段时间假日,作者一而再造轮子,重新达成了一晃双向链表。

1.3协会本性

 

线性表具备如下的结构特征:

1.均匀性:纵然分裂数据表的数量成分得以是美妙绝伦的,但对于同一线性表的各数据成分必定具有一样的数据类型和长度。

2.有序性:各数据成分在线性表中的任务只在于它们的序号,数据元素以前的周旋地方是线性的,即存在独一的”第一个”和”最终一个”的多少成分,除了第两个和尾声二个外,其余成分前边均独有一个数码成分间接前驱和前边均独有三个数额成分(直接后继)。

在贯彻线性表数据成分的仓库储存方面,一般可用顺序存款和储蓄结会谈链式存款和储蓄结构二种艺术。链式存款和储蓄结构就要本网址线性链表中牵线,本章重要介绍用数组完成线性表数据成分的顺序存款和储蓄及其使用。别的栈、队列和串也是线性表的独具匠心景况,又叫做受限的线性结构。

附一道选拔题:

下列哪个不是线性表(D)

A. 链表 B. 队列 C.栈 D.关联数组

    首先是链表节点数据的概念,见如下代码:

1.4线性表的拓展

 

日子不改变表、排序表、和频率有序表都能够看做是线性表的加大。如若依照结点达到结构的时日顺序,作为鲜明结点之间关系的,这样一种线性结构称之为时间有序表。比方,在红灯前停下的一长串小车,最初达到的为首结点,最终达到的为尾结点;在离开时最初达到的小车将第一离开,最终达到的将最后离开。这一个汽车构成理三个种类,实际上正是一个小时有序表。栈和队列都以光阴有序表。频率有序表是依据结点的选取作用分明它们中间的相互关系的,而排序表是基于结点的重要性字值来加以规定的。

 

template <class T>
class Node
{
public:
    Node<T>* next;
    Node<T>* prior;
    T data;

二.顺序存款和储蓄结构

public:
    Node(){};
    ~Node(){};
    Node<T>* GetNext();
    Node<T>* GetPrior();
    void GetData(T& data);
    void ChangeData(T data);
};

2.1介绍

在管理器中用一组地方接二连三的存款和储蓄单元次第存款和储蓄线性表的相继数码成分,称作线性表的顺序存款和储蓄结构.

顺序存款和储蓄结构是积攒结构类型中的一种,该组织是把逻辑上相邻的节点累积在大意地方上相邻的存储单元中,结点之间的逻辑关系由存储单元的分界关系来展示。因此获得的囤积结构为顺序存款和储蓄结构,常常顺序存款和储蓄结构是凭仗于计算机程序设计语言(例如c/c++)的数组来说述的。

顺序存款和储蓄结构的根本优点是节省存款和储蓄空间,因为分红给多少的存款和储蓄单元全用存放结点的多少(不考虑c/c++语言中数组需点名大小的景况),结点之间的逻辑关系未有据为己有额外的积攒空间。选用这种格局时,可达成对结点的随机存取,即每贰个结点对应三个序号,由该序号能够一向总括出来结点的积累地方。但顺序存款和储蓄方法的严重性瑕玷是不便于修改,对结点的插入、删除运算时,大概要运动一文山会海的结点。

可取:随机存取表巧月素。短处:插入和删除操作须要活动成分。

 

template<class T>
void Node<T>::GetData(T& _data)
{
    _data = data;
}

2.2C#言语情况顺序存款和储蓄结构对象举个例子:

  1. Array

    1. 引用类型(托管堆)

    2. 起首化时会设置暗许

  2. 自定义Array的代码实现

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication2

{

class MyArrayList

{

//容量

private const int _defaultCapacity = 4;

//寄放数组成分

private object[] _items;

//数组大小

private int _size;

//成分个数为0的数组状态

private static readonly object[] emptyArray = new object[0];

 

public MyArrayList()

{

this._items = emptyArray;

}

 

public MyArrayList( int capacity)

{

if (capacity<0)

{

throw new
ArgumentOutOfRangeException(“capacity”,”ArrayList的容积不足为负数!”);

}

this._items = new object[capacity];

}

 

//索引器

public virtual object this[int index]

{

get

{

if (index<0||index>=this._size)

{

throw new ArgumentOutOfRangeException(“index”,”索引超越范围!”);

}

return this._items[index];

}

 

set

{

if (index < 0 || index >= this._size)

{

throw new ArgumentOutOfRangeException(“index”, “索引逾越范围!”);

}

this._items[index] = value;

}

 

}

 

//当前数组成分个数

public virtual int Count

{

get {return this._size ;}

}

 

//数组的体量

public virtual int Capacity

{

get { return this._items.Length; }

set

{

if (value!=this._items.Length)

{

if (value<this._size)

{

throw new ArgumentOutOfRangeException(“value”,”容积太小”);

}

if (value > 0)

{//开垦新内部存款和储蓄器空间存储元素

object[] dest = new object[value];

if (this._size > 0)

{//搬动成分

Array.Copy(this._items, 0, dest, 0, this._size);

}

this._items = dest;

}

else//数组最小的半空中为4

{

this._items=new object[_defaultCapacity];

}

}

}

}

 

//成分的拉长

public virtual int Add(object value)

{//当空间已满

if (this._size==this._items.Length)

{

this.EnsureCapacity(this._size+1);

}

this._items[this._size] = value;

return this._size++;

}

 

//扩容

private void EnsureCapacity(int p)

{

if (this._items.Length<p)

{//空间加倍

int num = (this._items.Length == 0) ? _defaultCapacity :
(this._items.Length * 2);

if (num < p)

{

num = p;

}

this.Capacity = num;

}

}

 

//钦赐地点插入成分

public virtual void Insert( int index,object value)

{

if (index<0||index>this._size)

{

throw new ArgumentOutOfRangeException(“index”,”索引凌驾范围!”);

}

if (this._size==this._items.Length)

{

this.EnsureCapacity(this._size + 1);

}

if (index<this._size)

{

Array.Copy(this._items, index, this._items, index + 1, this._size –
index);

}

this._items[index] = value;

this._size++;

}

 

//移除钦定索引的因素

public virtual void Remove(int index)

{

if (index < 0 || index > this._size)

{

throw new ArgumentOutOfRangeException(“index”, “索引高出范围!”);

}

this._size–;

if (index<this._size)

{

Array.Copy(this._items,index+1,this._items,index,this._size-index);

}

this._items[this._size]=null;

}

 

//裁剪空间

public virtual void TrimToSize()

{

this.Capacity = this._size;

}

}

}

template<class T>
Node<T>* Node<T>::GetNext()
{
    return next;
}

三.链式存款和储蓄结构

template<class T>
Node<T>* Node<T>::GetPrior()
{
    return prior;
}

3.1介绍

bf88必发唯一官网,在Computer中用一组随机的存款和储蓄单元积累线性表的数码元素(那组存储单元可以是连连的,也能够是不总是的).

它不供给逻辑上紧邻的要素在物理位置上也相邻.由此它从不顺序存储结构所具有的症结,但也还要失去了顺序表可随机存取的优点.

bf88必发唯一官网 7

template<class T>
void Node<T>::ChangeData(T _data)
{
    data = _data;
}

3.2链式存款和储蓄结构特征

1、比顺序存款和储蓄结构的存款和储蓄密度小
(每一个节点都由数据域和指针域组成,所以一律空间内若是全存满的话顺序比链式存储越多)。

2、逻辑上相邻的节点物理上不要相邻。

3、插入、删除灵活
(不必移动节点,只要退换节点中的指针)。

4、查找结点时链式存款和储蓄要比顺序存款和储蓄慢。

5、每种结点是由数据域和指针域组成。

  Node结点类是三个模板类,具体最基本链表访谈的章程。

3.3链式存款和储蓄结构分类介绍

  接下去,才是最着重链表类:

3.3.1单向链表

bf88必发唯一官网 8

 

3.3.1.1.概念

bf88必发唯一官网 9

单向链表(单链表)是链表的一种,其性状是链表的链接方向是单向的,对链表的访谈要通过逐个读取从头顶初始;链表是采取指针扩充组织的列表;又叫做结点列表,因为链表是由多个个结点组装起来的;当中各类结点都有指针成员变量指列表中的下一个结点;

列表是由结点构成,由head指针本着第一个产生表头的结点而止住于最后贰个针对nuLL的指针;

bf88必发唯一官网 10bf88必发唯一官网 11链表注脚

3.3.1.2.单向链表C语言实例:

/*

===============================================

目标:学习单向链表的创导、删除、

插入(无序、有序)、输出、

排序(选择、插入、冒泡)、反序

排序(选择、插入、冒泡)

插入(有序)

================================================

*/

/*

单向链表的图示:

—->[NULL]

head

图1:空链表

—->[p1]—->[p2]…—->[pn]—->[NULL]

head p1->next
p2->next pn->next

图2:有N个结点的链表

*/

#include
<stdlib.h>

#include
<stdio.h>

#define NULL 0

#define LEN
sizeof(struct student)

struct student

{

long num; /*学号 */

float score;
/*分数,其他音信方可持续在下边扩张字段 */

struct student *next;
/*针对下一结点的指针 */

};

int n; /*结点总量 */

/*

==========================

作用:创立结点

回来:指向链表表头的指针

==========================

*/

struct student *

线性表学习材质整理,求单向链表倒序第m个成分。Create ()

{

struct student *head;
/*头结点 */

struct student *p1 =
NULL; /*p1保存成立的新结点的地址 */

struct student *p2 =
NULL; /*p2保存原链表最终二个结点的地址 */

n = 0;
/*创建前链表的结点总量为0:空链表 */

p1 = (struct student
*) malloc (LEN); /*开垦二个新结点 */

p2 = p1;
/*万一结点开垦成功,则p2先把它的指针保留下来以备后用
*/

if (p1 == NULL)
/*结点开拓不成事 */

{

printf (“\nCann’t
create it, try it again in a moment!\n”);

return NULL;

}

else /*结点开发成功
*/

{

head = NULL;
/*开始head指向NULL */

printf (“Please input
%d node — num,score: “, n + 1);

scanf (“%ld,%f”,
&(p1->num), &(p1->score)); /*录入数据 */

}

while (p1->num != 0)
/*假若学号不为0,就继续录入下一个结点 */

{

n += 1;
/*结点总量扩大1个 */

if (n == 1)
/*假若结点总的数量是1,则head指向刚创设的结点p1 */

线性表学习材质整理,求单向链表倒序第m个成分。{

head = p1;

/*

注意:

此时的p2就是p1,也就是p1->next指向NULL。

如此写目标是与上边else保持一致。

*/

p2->next = NULL;

}

else

{

p2->next = p1;
/*针对上次上边刚开荒的结点 */

}

p2 = p1;
/*把p1的地址给p2保留,然后p1去产生新结点 */

p1 = (struct student
*) malloc (LEN);

printf (“Please input
%d node — num,score: “, n + 1);

scanf (“%ld,%f”,
&(p1->num), &(p1->score));

}

p2->next = NULL;
/*此句正是依靠单向链表的末尾多个结点要本着NULL */

free (p1);
/*释放p1。用malloc()、calloc()的变量都要free()
*/

p1 = NULL;
/*专程不要遗忘把自由的变量清空置为NULL,不然就改成”野指针”,即地址不鲜明的指针。
*/

return head;
/*再次来到创设链表的头指针 */

}

/*

===========================

效用:输出结点

返回: void

===========================

*/

void

Print (struct student
*head)

{

struct student *p;

printf (“\nNow , These
%d records are:\n”, n);

p = head;

if (head != NULL)
/*要是还是不是空链表,就输出链表中有所结点 */

{

printf (“head is
%o\n”, head); /*输出头指针指向的地点 */

do

{

/*

输出相应的值:当前结点地址、各字段值、当前结点的下一结点地址。

如此输出便于读者形象看到一个单向链表在管理器中的积存结构,和我们

统一筹算的图示是毫无二致的。

*/

printf (“%o %ld %5.1f
%o\n”, p, p->num, p->score, p->next);

p = p->next;
/*移到下三个结点 */

}

while (p != NULL);

}

}

/*

==========================

效率:删除钦赐结点

(此例中是剔除钦点学号的结点)

归来:指向链表表头的指针

==========================

*/

/*

单向链表的删除图示:

—->[NULL]

head

图3:空链表

从图3可见,空链表明显无法去除

—->[1]—->[2]…—->[n]—->[NULL](原链表)

head 1->next
2->next n->next

—->[2]…—->[n]—->[NULL](删除后链表)

head 2->next
n->next

图4:有N个结点的链表,删除第叁个结点

重组原链表和删除后的链表,就很轻巧写出相应的代码。操作方法如下:

1、你要通晓head正是首个结点,head->next就是第4个结点;

2、删除后head指向第三个结点,便是让head=head->next,OK那样就行了。

—->[1]—->[2]—->[3]…—->[n]—->[NULL](原链表)

head 1->next
2->next 3->next n->next

—->[1]—->[3]…—->[n]—->[NULL](删除后链表)

head 1->next
3->next n->next

图5:有N个结点的链表,删除中间多个(这里图示删除第二个)

重组原链表和删除后的链表,就很轻便写出相应的代码。操作方法如下:

1、你要了然head正是第四个结点,1->next正是首个结点,2->next正是第一个结点;

2、删除后2,1指向第3个结点,就是让1->next=2->next。

*/

struct student *

Del (struct student
*head, long num)

{

struct student *p1;
/*p1保存当前供给检查的结点的地点 */

struct student *p2;
/*p2保存当前检查过的结点的地址 */

if (head == NULL)
/*是空链表(结合图3清楚) */

{

printf (“\nList is
null!\n”);

return head;

}

/*稳固要去除的结点 */

p1 = head;

while (p1->num !=
num && p1->next != NULL)
/*p1指向的结点不是所要查找的,而且它不是最终一个结点,就三回九转往下找 */

{

p2 = p1;
/*保留当前结点的地点 */

p1 = p1->next;
/*后移二个结点 */

}

if (num == p1->num)
/*找到了。(结合图4、5理解) */

{

if (p1 == head)
/*若是要去除的结点是率先个结点 */

{

head = p1->next;
/*头指针指向第多少个结点的后二个结点,也正是第四个结点。那样第二个结点就不在链表中,即除去。
*/

}

else
/*若果是别的结点,则让原先指向当前结点的指针,指向它的下三个结点,完结删除
*/

{

p2->next =
p1->next;

}

free (p1);
/*出狱当前结点 */

p1 = NULL;

printf (“\ndelete %ld
success!\n”, num);

n -= 1;
/*结点总数减1个 */

}

else /*向来不找到 */

{

printf (“\n%ld not
been found!\n”, num);

}

return head;

}

/*

==========================

功用:插入钦赐结点的前面

(此例中是钦定学号的结点)

回去:指向链表表头的指针

==========================

*/

/*

单向链表的插入图示:

—->[NULL](原链表)

head

—->[1]—->[NULL](插入后的链表)

head 1->next

图7 空链表插入三个结点

重组原链表和插入后的链表,就很轻易写出相应的代码。操作方法如下:

1、你要掌握空链表head指向NULL便是head=NULL;

2、插入后head指向第三个结点,就是让head=1,1->next=NULL,OK那样就行了。

—->[1]—->[2]—->[3]…—->[n]—->[NULL](原链表)

head 1->next
2->next 3->next n->next

—->[1]—->[2]—->[x]—->[3]…—->[n]—->[NULL](插入后的链表)

head 1->next
2->next x->next 3->next n->next

图8:有N个结点的链表,插入多个结点(这里图示插入第三个前面)

结合原链表和插入后的链表,就很轻便写出相应的代码。操作方法如下:

1、你要领悟原1->next就是结点2,2->next正是结点3;

2、插入后x指向第3个结点,2指向x,就是让x->next=2->next,1->next=x。

*/

struct student *

Insert (struct student
*head, long num, struct student *node)

{

struct student *p1;
/*p1保存当前急需检查的结点的地方 */

if (head == NULL)
/*(结合图示7领悟) */

{

head = node;

node->next = NULL;

n += 1;

return head;

}

p1 = head;

while (p1->num !=
num && p1->next != NULL)
/*p1指向的结点不是所要查找的,何况它不是最终一个结点,继续往下找 */

{

p1 = p1->next;
/*后移二个结点 */

}

if (num == p1->num)
/*找到了(结合图示8接头) */

{

node->next =
p1->next; /*断定node的下一结点是原p1的next */

p1->next = node;
/*布署后,原p1的下一结点正是要插入的node */

n += 1;
/*结点总量扩大1个 */

}

else

{

printf (“\n%ld not
been found!\n”, num);

}

return head;

}

/*

==========================

效能:反序结点

(链表的头酿成链表的尾,链表的尾产生头)

重临:指向链表表头的指针

==========================

*/

/*

单向链表的反序图示:

—->[1]—->[2]—->[3]…—->[n]—->[NULL](原链表)

head 1->next
2->next 3->next n->next

[NULL]<—-[1]<—-[2]<—-[3]<—-…[n]<—-(反序后的链表)

1->next 2->next
3->next n->next head

图9:有N个结点的链表反序

组成原链表和插入后的链表,就很轻松写出相应的代码。操作方法如下:

1、大家必要多个读原链表的指针p2,存反序链表的p1=NULL(刚好最终三个结点的next为NULL),还大概有三个一时存款和储蓄变量p;

2、p2在原链表中读出贰个结点,大家就把它内置p第11中学,p正是用来拍卖结点放置顺序的主题素材;

3、比如,今后大家赢得叁个2,为了大家承袭往下取结点,大家亟须保留它的next值,由原链表可见p=2->next;

4、然后由反序后的链表可知,反序后2->next要指向1,则2->next=1;

5、好了,将来早已反序叁个结点,接着管理下二个结点就要求保留此时的音信:

p1造成刚刚参预的2,即p1=2;p2要成为它的下一结点,便是地点我们保留的p,即p2=p。

*/

struct student *

Reverse (struct student
*head)

{

struct student *p;
/*临时存款和储蓄 */

struct student *p1;
/*积累重返结果 */

struct student *p2;
/*源结果结点多个三个取 */

p1 = NULL;
/*起来颠倒时,已颠倒的一部分为空 */

p2 = head;
/*p2指向链表的头结点 */

while (p2 != NULL)

{

p = p2->next;

p2->next = p1;

p1 = p2;

p2 = p;

}

head = p1;

return head;

}

/*

==========================

功能:选料排序(由小到大)

回来:指向链表表头的指针

==========================

*/

/*

分选排序的着力观念正是几度从还未排好序的那多少个结点中,

选出键值(正是用它排序的字段,大家取学号num为键值)最小的结点,

依次重新组合成叁个链表。

自己感觉写链表那类程序,关键是明亮:

head存款和储蓄的是第一个结点的地点,head->next存款和储蓄的是第四个结点的地址;

放肆八个结点p的地方,只好通过它前一个结点的next来求得。

单向链表的选拔排序图示:

—->[1]—->[3]—->[2]…—->[n]—->[NULL](原链表)

head 1->next
3->next 2->next n->next

—->[NULL](空链表)

first

tail

—->[1]—->[2]—->[3]…—->[n]—->[NULL](排序后链表)

first 1->next
2->next 3->next tail->next

图10:有N个结点的链表选取排序

1、先在原链表中找小小的,找到七个后就把它内置另三个空的链表中;

2、空链表中放到第四个步向的结点,发生二个墨守成规链表,并且让它在原链表中分离出来(此时要留意原链表中出来的是第贰个结点依然中等任何结点);

3、继续在原链表中找下二个相当小的,找到后把它归入有序链表的尾指针的next,然后它变成其尾指针;

*/

struct student *

SelectSort (struct
student *head)

{

struct student *first;
/*排列后有序链的表头指针 */

struct student *tail;
/*排列后有序链的表尾指针 */

struct student
*p_min;
/*保留键值更加小的结点的先行者结点的指针
*/

struct student *min;
/*积攒最小结点 */

struct student *p;
/*如今比较的结点 */

first = NULL;

while (head != NULL)
/*在链表中找键值最小的结点。 */

{

/*注意:这里for语句正是反映挑选排序合计的地点
*/

for (p = head, min =
head; p->next != NULL; p = p->next)
/*循环遍历链表中的结点,搜索此时小小的结点。 */

{

if (p->next->num
< min->num) /*找到三个比近日min小的结点。 */

{

p_min = p;
/*封存找到结点的先行者结点:鲜明p->next的先辈结点是p。 */

min = p->next;
/*封存键值更加小的结点。 */

}

}

/*上边for语句停止后,将要做两件事;一是把它放入有序链表中;二是依附对应的原则推断,安顿它离开原先的链表。
*/

/*率先件事 */

if (first == NULL)
/*比方有序链表近来依旧二个空链表 */

{

first = min;
/*率先次找到键值最小的结点。 */

tail = min;
/*注意:尾指针让它指向最后的贰个结点。
*/

}

else
/*不改变链表中曾经有结点 */

{

tail->next = min;
/*把刚找到的微小结点放到最后,即让尾指针的next指向它。
*/

tail = min;
/*尾指针也要指向它。 */

}

/*其次件事 */

if (min == head)
/*即使找到的细小结点正是率先个结点 */

{

head = head->next;
/*明朗让head指向原head->next,即第一个结点,就OK */

}

else
/*若果不是第三个结点 */

{

p_min->next =
min->next;
/*前次极小结点的next指向当前min的next,那样就让min离开了原链表。 */

}

}

if (first != NULL)
/*循环甘休获得稳步链表first */

{

tail->next = NULL;
/*单向链表的结尾多少个结点的next应该本着NULL */

}

head = first;

return head;

}

/*

==========================

功能:间接插入排序(由小到大)

归来:指向链表表头的指针

==========================

*/

/*

直接插入排序的主导观念正是假使链表的前面n-1个结点是现已按键值

(便是用它排序的字段,大家取学号num为键值)排好序的,对于结点n在

这一个行列中找插入地点,使得n插入后新体系依旧雷打不动。根据这种思索,依次

对链表原原本本推行二次,就足以使严节链表变为有序链表。

单向链表的直接插入排序图示:

—->[1]—->[3]—->[2]…—->[n]—->[NULL](原链表)

head 1->next
3->next 2->next n->next

—->[1]—->[NULL](从原链表中取第2个结点作为唯有三个结点的静止链表)

head

图11

—->[3]—->[2]…—->[n]—->[NULL](原链表剩下用于直接插入排序的结点)

first 3->next
2->next n->next

图12

—->[1]—->[2]—->[3]…—->[n]—->[NULL](排序后链表)

head 1->next
2->next 3->next n->next

图13:有N个结点的链表直接插入排序

1、先在原链表中以第二个结点为三个稳步链表,别的结点为待定结点。

2、从图12链表中取结点,到图11链表中固定插入。

3、下边图示虽说画了两条链表,其实唯有一条链表。在排序中,实质只扩大了多少个用于指向剩下须求排序结点的头指针first罢了。

那或多或少请读者必须搞精晓,要不然就恐怕认为它和地点的选拔排序法一样了。

*/

struct student *

InsertSort (struct
student *head)

{

struct student *firs

 

template <class T>
class DoubleLinkedList:public Node<T>
{
public:
    Node<T>* start;
    Node<T>* end;

3.3.2.循环链表

bf88必发唯一官网 12

循环链表是另一种样式的链式存贮结构。它的特点是表中最终四个结点的指针域指向头结点,整个链表产生八个环。

public:
    DoubleLinkedList();
    ~DoubleLinkedList();
    void ForwardList();
    void BackwardList();
    bool Remove(Node<T>* node);
    void Add(T data);
    Node<T>* Search(T data);
    Node<T>* GetStart();
};

3.3.2.1分类

bf88必发唯一官网 13

  循环链表

(1)单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或起头结点就可以。

(2)多种链的循环链表——将表中结点链在三个环上。

    链表证明类中有贰个start 和 end结点,便于遍历链表,
小编先写上增添链表结点的格局,

3.3.2.22领头结点

认清空链表的条件是head==head->next;

bf88必发唯一官网 14bf88必发唯一官网 15加多结点

3.3.2.3尾指针

用尾指针rear表示的单循环链表对最早结点a1和终端结点an查找时间都以O(1)。而表的操作平日是在表的全进程地方上开展,由此,实用中多选用尾指针表示单循环链表。带尾指针的单循环链表可知下图。

在意:判断空链表的准绳为rear==rear->next;

template<class T>
void DoubleLinkedList<T>::Add(T data)
{
    Node<T>* node = new Node<T>();
    if(!node)
    {
        cout << “assign memeory failure!”<<endl;
        exit(0);
    }
    node->data = data;
    if(!start)       //add first node
    {
        start = end = node;
        start->prior = NULL;
    }
    else
    {
        node->prior= end;
        end->next = node;
        node->next = NULL;
        end = node;
    }
}

3.3.2.4特点

循环链表的天性是毫不增添存储量,仅对表的链接格局稍作改动,就能够使得表管理特别实惠灵活。

【例】在链表上贯彻将多少个线性表(a1,a2,…,an)和(b1,b2,…,bm)连接成三个线性表(a1,…,an,b1,…bm)的演算。

分析:若在单链表或头指针表示的单循环表上做这种链接操作,都亟需遍历第一个链表,找到结点an,然后将结点b1链到an的背后,其实践时间是O(n)。若在尾指针意味着的单循环链表上落实,则只需修改指针,无须遍历,其试行时间是O(1)。

相应的算法如下:

LinkListConnect(LinkListA,LinkListB)

{//如果A,B为非空循环链表的尾指针

LinkListp=A->next;//①保存A表的头结点位置

A->next=B->next->next;//②B表的初叶结点链接到A表尾

free(B->next);//③释放B表的头结点

B->next=p;//④

returnB;//重返新循环链表的尾指针

}

注意:

①循环链表中平昔不NULL指针。涉及遍历操作时,其停止条件就不再是像非循环链表那样推断p或p->next是还是不是为空,而是判断它们是还是不是等于某一点名指针,如头指针或尾指针等。

②在单链表中,从一已知结点出发,只好访问到该结点及其后续结点,无法找到该结点之前的别的结点。而在单循环链表中,从任一结点出发都可访谈到表中装有结点,这一亮点使有些运算在单循环链表上易于完结。

 

  
起头结点的上叁个结实指针为NULL,同理最终三个结点的下一个结点的指针也为NULL。

3.3.3.双向链表

双向链表也叫双链表,是链表的一种,它的每种数据结点中都有五个指针,分别指向直接后继和直接前驱。所以,从双向链表中的大肆叁个结点早先,都得以很有益地拜候它的四驱结点和后继结点。一般我们都组织双向循环链表。

 

bf88必发唯一官网 16bf88必发唯一官网 17遍历链表

3.3.3.1链表的操作

template<class T>
void DoubleLinkedList<T>::ForwardList()
{
    Node<T>* p = start;
    if(!p)
    {
        cout << “the double linked list is empty” << endl;
        return;
    }
    cout << “forward double linked list:”;
    while(p)
    {
        cout << p->data << ”  “;
        p = p->GetNext();
    }
    cout << endl;
}

1.线性表的双向链表存款和储蓄结构

 

typedef struct DuLNode

{

ElemType data;

struct DuLNode
*prior,*next;

}DuLNode,*DuLinkList;

领衔结点的双向循环链表的基本操作

void InitList(DuLinkList
*L)

{ /*
产生空的双向循环链表L */

L=(DuLinkList)malloc(sizeof(DuLNode));

if(*L)

(*L)->next=(*L)->prior=*L;

else

exit(OVERFLOW);

}

template<class T>
void DoubleLinkedList<T>::BackwardList()
{
    Node<T>* p = end;
    if(!p)
    {
        cout << “the double linked list is empty” << endl;
        return;
    }
    cout << “backward double linked list:”;
    while(p)
    {
        cout << p->data << ”  “;
        p = p->prior;
    }
    cout << endl;
}

2.销毁双向循环链表L

 

void DestroyList(DuLinkList *L)

{

DuLinkList q,p=(*L)->next; /* p指向第一个结点 */

while(p!=*L) /* p没到表头 */

{

q=p->next;

free(p);

p=q;

}

free(*L);

*L=NULL;

}

 
我分别实现了从开头结点向后遍历以及从尾结点向前遍历的两种艺术。在那之中就应用到链表中的start结点指针与end结点指针。

3.复位链表为空表

 

void ClearList(DuLinkList L) /* 不改变L */

{ DuLinkList q,p=L->next; /* p指向第二个结点 */

while(p!=L) /* p没到表头 */

{

q=p->next;

free(p);

p=q;

}

L->next=L->prior=L;
/*头结点的两个指针域均指向本身
*/

}

 

4.验证是不是为空表

 

Status ListEmpty(DuLinkList L)

{ /* 开首条件:线性表L已存在

if(L->next==L&&L->prior==L)

return TRUE;

else

return FALSE;

}

bf88必发唯一官网 18bf88必发唯一官网 19移除结点

3.3.3.2要素的操作

template<class T>
bool DoubleLinkedList<T>::Remove(Node<T>* node)
{
    if(!node)
    {
        cout << “the node wanted to deleted is null” << endl;
        return 0;
    }
    if(node->next)
    {
        if(node->prior)  //remove the middle node
        {
            node->next->prior = node->prior;
            node->prior->next = node->next;
        }
        else      //remove first node;
        {
            node->next->prior = NULL;
            start = node->next;
        }
    }
    else
    {
        if(node->prior)  //remove the last node
        {
            node->prior->next = NULL;
            end = node;
        }
        else        //remove the only node
        {
            start = end = NULL;
        }
    }
}

1.划算表内成分个数

 

int ListLength(DuLinkList L)

{ /* 起首条件:L已存在。操作结果: */

int i=0;

DuLinkList p=L->next; /* p指向第一个结点 */

while(p!=L) /* p没到表头 */

{

i++;

p=p->next;

}

return i;

}

    移除结点稍微要麻烦点,要思念要去除的结果是还是不是为发端结点。

2.赋值

 

Status GetElem(DuLinkList L,int i,ElemType *e)

{ /* 当第i个因素存在时,其值赋给e并赶回OK,否则重回E路虎极光RO景逸SUV */

int j=1; /* j为计数器 */

DuLinkList p=L->next; /* p指向第三个结点 */

while(p!=L&&j<i)

{

p=p->next;

j++;

}

if(p==L||j>i) /* 第i个因素海市蜃楼 */

return ERROR;

*e=p->data; /* 取第i个元素 */

return OK;

}

    到此大概就到位了链表所效劳,包罗查询、增多、修改以及移除成效。

3.查找成分

 

int LocateElem(DuLinkList L,ElemType
e,Status(*compare)(ElemType,ElemType))

{ /*
开首条件:L已存在,compare()是多少成分推断函数
*/

/*
操作结果:重临L中第四个与e满意关系compare()的数量成分的位序。
*/

/*
若那样的多少元素不设有,则再次来到值为0
*/

int i=0;

DuLinkList p=L->next; /* p指向第1个元素 */

while(p!=L)

{

i++;

if(compare(p->data,e)) /*
找到这么的数据成分*/

return i;

p=p->next;

}

return 0;

}

    最后只剩余测量检验程序了。

4.查找成分四驱

 

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)

{ /*
操作结果:若cur_e是L的数量成分,且不是首先个,则用pre_e重临它的先行者,
*/

/* 不然操作败北,pre_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

while(p!=L) /* p没到表头 */

{

if(p->data==cur_e)

{

*pre_e=p->prior->data;

return TRUE;

}

p=p->next;

}

return FALSE;

}

   

5.查找成分后继

 

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)

{ /*
操作结果:若cur_e是L的多寡成分,且不是终极二个,则用next_e重临它的后继,
*/

/* 不然操作退步,next_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

while(p!=L) /* p没到表头 */

{

if(p->prior->data==cur_e)

{

*next_e=p->data;

return TRUE;

}

p=p->next;

}

return FALSE;

}

bf88必发唯一官网 20bf88必发唯一官网 21测量检验程序

6.查找成分地址

 

DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */

{ /*
在双向链表L中回到第i个要素的地点。i为0,重临头结点的地方。若第i个因素空头支票,*/

/* 返回NULL */

int j;

DuLinkList p=L; /* p指向头结点 */

if(i<0||i>ListLength(L)) /* i值非法 */

return NULL;

for(j=1;j<=i;j++)

p=p->next;

return p;

}

#include “stdafx.h”
#include <iostream>
#include <string>
#include “DoubleLinkedList.h”
using namespace std;

7.成分的插入

 

Status ListInsert(DuLinkList L,int i,ElemType e)

{ /*
在带头结点的双链循环线性表L中第i个地方在此之前插入元素e,i的合法值为1≤i≤表长+1
*/

/* 革新算法2.18,不然无法在第表长+1个结点此前插入成分 */

DuLinkList p,s;

if(i<1||i>ListLength(L)+1) /* i值不合规 */

return ERROR;

p=GetElemP(L,i-1); /*
在L中规定第i个要素四驱的地方指针p
*/

if(!p) /*
p=NULL,即第i个因素的先行者空中楼阁(设头结点为第2个成分的四驱)
*/

return ERROR;

s=(DuLinkList)malloc(sizeof(DuLNode));

if(!s)

return OVERFLOW;

s->data=e;

s->prior=p; /* 在第i-1个因素之后插入 */

s->next=p->next;

p->next->prior=s;

p->next=s;

return OK;

}

int _tmain(int argc, _TCHAR* argv[])
{
    //test double linked list
    //Node<int> a;
    DoubleLinkedList<int> list;
    for(int i=0;i<10;i++)
    {
       list.Add(i+1);
    }
    list.ForwardList();
    list.BackwardList();

8.成分的去除

 

Status ListDelete(DuLinkList L,int i,ElemType *e)

{ /* 删除带头结点的双链循环线性表L的第i个因素,i的合法值为1≤i≤表长 */

DuLinkList p;

if(i<1) /* i值非法 */

return ERROR;

p=GetElemP(L,i); /*
在L中规定第i个成分的任务指针p
*/

if(!p) /* p=NULL,即第i个因素一纸空文 */

return ERROR;

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

return OK;

}

    //add new node
    list.Add(12);
    list.ForwardList();

9.正序查找

 

void ListTraverse(DuLinkList L,void(*visit)(ElemType))

{ /*
由双链循环线性表L的头结点启程,正序对每种数据成分调用函数visit()
*/

DuLinkList p=L->next; /* p指向头结点 */

while(p!=L)

{

visit(p->data);

p=p->next;

}

printf(“\n”);

}

void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))

    //find the first node
    cout << “search node 3:” <<endl;
    Node<int>* midNode = list.Search(3);
    if(midNode)
    {
        //remove middle node
        cout << “remove middle node:”<<endl;
        list.Remove(midNode);
        list.ForwardList();
    }
    else
    {
        cout << “can not find”<<endl;
    }

10.逆序搜索

 

{ /*
由双链循环线性表L的头结点出发,逆序对种种数据成分调用函数visit()。另加
*/

DuLinkList p=L->prior; /* p指向尾结点 */

while(p!=L)

{

visit(p->data);

p=p->prior;

}

printf(“\n”);

}

    Node<int>* firstNode = list.Search(1);
    if(midNode)
    {
        //remove middle node
        cout << “remove fist node:”<<endl;
        list.Remove(firstNode);
        list.ForwardList();
    }
    else
    {
        cout << “can not find”<<endl;
    }

3.3.3.3双向链表模板

/*****************************************************

*文件名:LinkedList.h

*职能:达成双向链表的基本效能

*专心:为了使末段程序试行得更加快,仅在Debug情势下检验操作合法性。

*其它不对内存分配停业作管理,因为相似景色下应用程序有近2GB真正可用的上空

*********************************************************/

#pragma once

#include <assert.h>

template<class T>

class LinkedList

{

private:

class Node

{

public:

T data;
//数据域,不要求泛型T的实例类有无参构造函数

Node* prior; //指向前一个结点

Node* next; //指向下三个结点

Node(const T& element,Node*& pri,Node*&
nt):data(element),next(nt),prior(pri){}

Node():data(data){}//泛型T的实例类的复制构造函数将被调用.在Vc二零零六测验可行

};

Node* head; //指向第八个结点

public:

//起始化:构造三个空结点,搭建空链

LinkedList():head(new Node()){head->prior=head->next=head;}

//获取成分总的数量

int elementToatal()const;

//剖断是还是不是为空链

bool isEmpty()const{return head==head->next?true:false;}

//将成分加多至最终,注意node的指针设置

void addToLast(const T& element){Node* ne=new
Node(element,head->prior,head);head->prior=head->prior->next=ne;}

//获取最后一个成分

T getLastElement()const{assert(!isEmpty());return
head->prior->data;}

//删除最终一个因素,注意node的指针设置

void delLastElement(){assert(!isEmpty());Node*
p=head->prior->prior;delete
head->prior;head->prior=p;p->next=head;}

//修改最终二个成分

void alterLastEmlent(const T&
newElement){assert(!isEmpty());head->prior->data=newElement;}

//插入成分

void insertElement(const T& element,int position);

//获取成分

T getElement(int index)const;

//删除成分

T delElement(int index);

//修改元素

void alterElement(const T & Newelement,int index);

//查找成分

int findElement(const T& element) const;

//正序遍历

void Traverse(void (*visit)(T&element));

//逆序遍历

void TraverseBack(void (*visit)(T&element));

//重载[]函数

T& operator [](int index);

//清空链表

void clearAllElement();

//销毁链表

~LinkedList();

};

/***************************************

*重回成分总量

****************************************/

template<class T>

int LinkedList<T>::elementToatal()const

{

int Total=0;

for(Node* p=head->next;p!=head;p=p->next) ++Total;

return Total;

}

/**********************************************

*在position钦点的职位插入成分。原本position及末端的元

*素后移

***********************************************/

template<class T>

void LinkedList<T>::insertElement(const T& element,int position)

{

assert(position>0 && position<=elementToatal()+1);

Node* p=head;

while(position)

{

p=p->next;

position–;

}

//此时p指向要插入的结点

Node* pNew=new Node(element,p->prior,p);

p->prior=p->prior->next=pNew;

}

/***************************************

*回来找到的成分的副本

***************************************/

template<class T>

T LinkedList<T>::getElement(int index)const

{

assert(index>0 && index<=elementToatal() &&
!isEmpty());//地方索引是或不是合法,链表是还是不是空

Node* p=head->next;

while(–index) p=p->next;

return p->data;

}

/**********************************

*去除钦定成分,并再次来到它

**********************************/

template<class T>

T LinkedList<T>::delElement(int index)

{

assert(index>0 && index<=elementToatal() &&
!isEmpty());//地方索引是不是合法,链表是或不是空

Node* del=head->next;

while(–index) del=del->next;

//此时p指向要去除元素

del->prior->next=del->next;

del->next->prior=del->prior;

T delData=del->data;

delete del;

return delData;

}

/****************************************

*用Newelement替代索引为index的要素

*****************************************/

template<class T>

void LinkedList<T>::alterElement(const T & Newelement,int index)

{

assert(index>0 && index<=elementToatal() &&
!isEmpty());//地方索引是或不是合法,链表是或不是空

Node* p=head->next;

while(–index) p=p->next;

p->data=Newelement;

}

/********************************

*找到重临成分的目录,不然重回0

********************************/

template<class T>

int LinkedList<T>::findElement(const T& element) const

{

Node* p=head->next;

int i=0;

while(p!=head)

{

i++;

if(p->data==element) return i;

p=p->next;

}

return 0;

}

/***************************************

*正向遍历,以链表中种种成分作为参数调用visit函数

*****************************************/

template<class T>

void LinkedList<T>::Traverse(void (*visit)(T&element))

{

Node* p=head->next;

while(p!=head)

{

visit(p->data);//注意此时外界visit函数有权力修改LinkedList<T>的私人民居房数据

p=p->next;

}

}

/*************************************************

*反向遍历,以链表中每种成分作为参数调用visit函数

*************************************************/

template<class T>

void LinkedList<T>::TraverseBack(void (*visit)(T&element))

{

Node* p=head->prior;

while(p!=head)

{

visit(p->data);//注意此时外界visit函数有权力修改LinkedList<T>的私家数据

p=p->prior;

}

}

/**************************************************

*归来链表的成分征引,并可读写.实际上链表没有[]意思上的保有机能

*因此[]函数是有限定的.重载它是为着客户端代码简洁,因为从链表读写

*多少是最常用的

***************************************************/

template<class T>

T& LinkedList<T>::operator [](int index)

{

assert(index>0 && index<=elementToatal() &&
!isEmpty());//[]函数使用前提条件

Node* p=head->next;

while(–index) p=p->next;

return p->data;

}

/***************************

*清空链表

***************************/

template<class T>

void LinkedList<T>::clearAllElement()

{

Node* p=head->next,*pTemp=0;

while(p!=head)

{

pTemp=p->next;

delete p;

p=pTemp;

}

head->prior=head->next=head;//收尾专业

}

/******************************

*析构函数,若内存丰富没必要调用该函数

*******************************/

template<class T>

LinkedList<T>::~LinkedList()

{

if(head)//制止客商显式析构后,对象又凑巧超过作用域再调用该函数

{

clearAllElement();

delete head;

head=0;

}

}

bf88必发唯一官网 22

    Node<int>* lastNode = list.Search(12);
    if(midNode)
    {
        //remove middle node
        cout << “remove last node:”<<endl;
        list.Remove(lastNode);
        list.ForwardList();
    }
    else
    {
        cout << “can not find”<<endl;
    }

    cout << “chaged node data from 10 to 11:” <<endl;
    Node<int>* changedNode  = list.Search(10);
    if(changedNode)
    {
        changedNode->ChangeData(11);
        list.ForwardList();
    }

    
    int wait;
    cin >> wait;
    return 0;
}

  在自家本机上测量检验通过!
附带附上下载地址:下载

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图