没有合适的资源？快使用搜索试试~ 我知道了~

首页掌握C++数据结构与算法：深度解析与数学基础

掌握C++数据结构与算法：深度解析与数学基础

c++数据结构和算法分析

需积分: 50 4 下载量 191 浏览量更新于2024-08-02 收藏 3.1MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

试读

97页

《C++数据结构和算法分析》是一本深入讲解C++编程中数据结构与算法的经典著作，它对读者的数学基础有较高要求。作者Greg Tobin以其丰富的经验和深厚的专业知识，为读者提供了一个系统且详实的学习平台。该书旨在帮助读者理解并掌握C++语言中的核心数据结构（如数组、链表、栈、队列、树、图等）以及高效的算法设计技巧，这些都是软件开发中不可或缺的基础。书中涵盖了诸如排序算法（如冒泡排序、快速排序、归并排序）、搜索算法（二分查找、哈希查找）、数据结构的实现细节（如动态规划、递归等），以及复杂性分析，让读者能够理解算法的时间和空间效率。此外，作者还通过实例和练习题的形式，确保读者能够将理论知识转化为实际编程能力。在出版方面，该书由Pearson Education公司发行，由Michael Hirsch担任高级采购编辑，Lindsey Triebel负责编辑协助，Michele Brown和Dana Lopreato负责市场营销工作。数字化资产管理由Marianne Groth负责，而Windfall Software利用ZzT进行了排版。版权方面，本书享有Pearson Education公司的2006年版权，所有权利保留，未经许可，禁止任何形式的复制、存储或传输。为了获取关于Addison-Wesley计算机书籍的最新资讯，读者可以通过访问Pearson Education的官方网站http://www.aw-bc.com/computing获取更多信息。同时，对于想在作品中引用本书内容的请求，应提交书面申请至Pearson Education的权益和合同部门。《C++数据结构和算法分析》是一本深度学习C++编程技术的必备参考书籍，适合那些希望在算法设计和数据管理上提升技能的程序员，特别是那些数学基础扎实的开发者。通过阅读和实践书中的内容，读者将能提升编程水平，更好地应对各种IT挑战。

资源详情

资源推荐

10 Chapter 3 Lists, Stacks, and Queues

(b) Here is the code for doubly linked lists:

// p and afterp are cells to be switched. Error checks as before

{

Node *beforep, *afterp;

beforep = p->prev;

afterp = p->next;

p->next = afterp->next;

beforep->next = afterp;

afterp->next = p;

p->next->prev = p;

p->prev = afterp;

afterp->prev = beforep;

}

3.3 template <typename Iterator, typename Object>

Iterator find(Iterator start, Iterator end, const Object& x)

{

Iterator iter = start;

while ( iter != end && *iter != x)

iter++;

return iter;

}

3.4 // Assumes both input lists are sorted

template <typename Object>

list<Object> intersection( const list<Object> & L1,

const list<Object> & L2)

{

list<Object> intersect;

typename list<Object>:: const_iterator iterL1 = L1.begin();

typename list<Object>:: const_iterator iterL2= L2.begin();

while(iterL1 != L1.end() && iterL2 != L2.end())

{

if (*iterL1 == *iterL2)

{

intersect.push_back(*iterL1);

iterL1++;

iterL2++;

}

else if (*iterL1 < *iterL2)

iterL1++;

else

iterL2++;

}

return intersect;

}

Solutions 11

3.5 // Assumes both input lists are sorted

template <typename Object>

list<Object> listUnion( const list<Object> & L1,

const list<Object> & L2)

{

list<Object> result;

typename list<Object>:: const_iterator iterL1 = L1.begin();

typename list<Object>:: const_iterator iterL2= L2.begin();

while(iterL1 != L1.end() && iterL2 != L2.end())

{

if (*iterL1 == *iterL2)

{

result.push_back(*iterL1);

iterL1++;

iterL2++;

}

else if (*iterL1 < *iterL2)

{

result.push_back(*iterL1);

iterL1++;

}

else

{

result.push_back(*iterL2);

iterL2++;

}

return result;

}

3.6 This is a standard programming project. The algorithm can be sped up by setting M



= M mod N,

so that the hot potato never goes around the circle more than once. If M



>N/2, the potato should

be passed in the reverse direction. This requires a doubly linked list. The worst case running time

is clearly O(N min(M , N)), although when the heuristics are used, and M and N are comparable,

the algorithm might be signiﬁcantly faster. If M =1, the algorithm is clearly linear.

#include <iostream>

#include <list>

using namespace std;

int main()

{

int i,j, n, m, mPrime, numLeft;

list <int > L;

list<int>::iterator iter;

//Initialization

cout<<"enter N (# of people)&M(#ofpasses before elimination):";

cin>>n>>m;

numLeft = n;

12 Chapter 3 Lists, Stacks, and Queues

mPrime=m%n;

for(I=1;I<=n;i++)

L.push_back(i);

iter = L.begin();

// Pass the potato

for(I=0;I<n;i++)

{

mPrime = mPrime % numLeft;

if (mPrime <= numLeft/2) // pass forward

for (j = 0; j < mPrime; j++)

{

iter++;

if (iter == L.end())

iter = L.begin();

}

else // pass backward

for (j = 0; j < mPrime; j++)

{

if (iter == L.begin())

iter = --L.end();

else

iter--;

}

cout<<*iter<<" ";

iter= L.erase(iter);

if (iter == L.end())

iter = L.begin();

}

cout<<endl;

return 0;

}

3.7 // if out of bounds, writes a message (could throw an exception)

Object & operator[]( int index )

{ if (index >=0 && index <size() )

return objects[ index ];

else

cout<<"index out of bounds\n";

return objects[0];

}

const Object & operator[]( int index ) const

{ if (index >=0 && index <size() )

return objects[ index ];

else

cout<<"index out of bounds\n";

return objects[0];

}

Solutions 13

3.8 iterator insert(iterator pos, const Object& x)

{

Object * iter = &objects[0];

Object *oldArray = objects;

theSize++;

int i;

if (theCapacity < theSize)

theCapactiy = theSize;

objects = new Object[ theCapacity ];

while(iter != pos)

{

objects[i]= oldArray[i];

iter += sizeOf(Object);

pos += sizeOf(Object);

i++;

}

objects[pos] = x;

for (int k = pos+1; k < theSize; k++)

objects[k] = oldArray[ k ];

delete [ ] oldArray;

return & objects[pos];

}

3.9

All the aforementioned functions may require the creation of a new array to hold the data. When

this occurs all the old pointers (iterators) are invalid.

3.10 The changes are the const_iterator class, the iterator class and changes to all Vector functions that

use or return iterators. These classes and functions are shown in the following three code examples.

Based on the Vector deﬁned in the text, only changes includes

begin() and end().

(a)

class const_iterator

{

public:

//const_iterator( ) : current( NULL )

// { } Force use of the safe constructor

const Object & operator* ( ) const

{ return retrieve( ); }

const_iterator & operator++ ( )

{

current++;

return *this;

}

const_iterator operator++ ( int )

{

const_iterator old = *this;

++( *this );

return old;

}

14 Chapter 3 Lists, Stacks, and Queues

bool operator== ( const const_iterator & rhs ) const

{ return current == rhs.current; }

bool operator!= ( const const_iterator & rhs ) const

{ return !( *this == rhs ); }

protected:

Object *current;

const Vector<Object> *theVect;

Object & retrieve( ) const

{

assertIsValid();

return *current;

}

const_iterator( const Vector<Object> & vect, Object *p )

:theVect (& vect), current( p )

{}

void assertIsValid() const

{

if (theVect == NULL || current == NULL )

throw IteratorOutOfBoundsException();

}

friend class Vector<Object>;

};

(b)

class iterator : public const_iterator

{

public:

//iterator( )

// { } Force use of the safe constructor

Object & operator* ( )

{ return retrieve( ); }

const Object & operator* ( ) const

{ return const_iterator::operator*( ); }

iterator & operator++ ( )

{

cout<<"old "<<*current<<" ";

current++;

cout<<" new "<<*current<<" ";

return *this;

}

剩余96页未读，继续阅读

粉丝: 38
资源: 17

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

掌握C++数据结构与算法：深度解析与数学基础

数据结构和算法分析 C++版 第三版

数据结构与算法分析C++语言描述第四版参考答案

c++数据结构与算法推荐书籍

数据结构与算法分析c++描述

数据结构与算法分析 c++王立柱pdf

c++数据结构与算法 书记

基本数据结构和算法分析的初学资料

数据结构和算法分析c++第四版答案

数据结构与算法分析c++第四版答案

数据结构与算法分析c++电子版

数据结构与算法分析 c++语言描述 课后答案

数据结构与算法分析c++版第四版答案

数据结构与算法分析c++版答案

数据结构与算法分析–c++描述(第2版,weiss著,含习题答案)

数据结构与算法分析c++第四版电子版

c++数据结构与算法pdf

数据结构与算法分析c++语言描述答案

C++数据结构与算法 面试题

数据结构与算法分析c

数据结构 查找算法 c++

最新资源

数据结构和算法分析 C++版第三版

c++数据结构与算法书记

数据结构与算法分析 c++语言描述课后答案

C++数据结构与算法面试题

数据结构查找算法 c++