Data Structures (C++ Version): Exercise Solutions and Practical Guidance: 21st Century University Planning Textbooks

Author: Li Genqiang
Publisher:
Publish Date: 2005-04-01
Features: "Data Structures" is an important foundational course for computer science and related majors, as well as a core required course. It has also become a popular elective for other science and engineering disciplines. In various fields of computer science, different data structures are used, such as stacks, hash tables, and syntax trees in compilers; queues, storage management tables, and directory trees in operating systems; linear lists, linked lists, and index trees in database systems; and general lists, search trees, and directed graphs in artificial intelligence. Similarly, in fields like object-oriented programming, computer graphics, software engineering, multimedia technology, and computer-aided design, various data structures are also employed. Therefore, mastering data structures is crucial for professionals in computer technology and related fields. It enables you to grasp common data structures and their algorithmic implementations, as well as analyze the time and space complexity of each algorithm. It also helps you determine the most suitable data structure for a given scenario, laying the foundation for future large-scale program development. The main tasks of data structures are: discussing the logical structures of various data in the real world (e.g., numbers, characters, strings, sound, graphics, and images); exploring various storage structures (storage representations) in computers; and implementing algorithms for non-numeric operations. Additionally, it analyzes the pros and cons of different algorithms and their appropriate applications. Through the study of data structures, students will develop the ability to solve practical problems using the learned data structures and evaluate the of algorithms, paving the way for further studies in subsequent computer science courses and careers in large-scale software development.
This book is divided into nine chapters. Chapter 1 introduces basic terms related to data structures and algorithms, provides a simple explanation of algorithm description and analysis, and introduces the main factors for evaluating algorithm performance: time complexity and space complexity. Chapters 2 to 4 cover the logical characteristics of linear structures (linear lists, stacks, queues, and strings), some common algorithm implementations, and basic applications. Chapters 5 to 7 discuss the logical characteristics of non-linear structures (multidimensional arrays, general lists, trees, binary trees, and graphs), their storage representations in computers, and some common algorithm implementations and basic applications. Chapters 8 to 9 focus on two widely used operations in computers: searching and sorting, providing detailed explanations of common searching and sorting methods, along with their implementations, time complexity, and space complexity analysis. Each chapter contains relatively independent sections, allowing different institutions and majors to organize teaching according to their needs. The book emphasizes the application of data structures and strives to combine teaching content with specific computer application examples to help students deepen their understanding and mastery of each chapter.
The greatest feature of this book is its use of an object-oriented programming language (C++ language) as the algorithm description language, with all algorithms having been tested and debugged. However, due to space constraints, most algorithms are presented as standalone functions. To run these algorithms, readers must provide variable declarations and a main function to call the given functions. Therefore, the algorithm descriptions in this book are more intuitive than those in traditional data structure textbooks, which use pseudocode or C-like languages, making them easier for students to understand and accept.
After teaching data structure courses for over a decade, the author has conducted thorough research and analysis of various algorithms in data structures, accumulating extensive experience in this area. As a result, the examples and exercises in this book are highly targeted, focusing on specific data structures to facilitate understanding and comprehension. They also serve as a bridge for more complex data structure algorithm descriptions.
All algorithms in this book have been tested and run in the VC++6.0 environment (due to space constraints, only functions implementing certain functionalities are provided). To facilitate teaching, the book offers free electronic teaching materials in PowerPoint for instructors, who can make necessary modifications as needed.
This book can be used as a textbook for data structure courses in computer science or information science programs at universities and colleges. It is recommended that the lecture time be 50 to 70 hours, with 20 to 30 hours of hands-on practice. Institutions and instructors can adjust the content according to their specific program requirements and student circumstances. Chapters marked with an asterisk in the table of contents can be considered optional.
This book is also suitable for engineers and technicians working in computer applications and as a self-study reference for university students. Accompanying this book is 《Data Structures (C++ Edition) Exercise Solutions and Practice Guidance》, which provides matching exercises and solutions, along with an experimental guide for data structures, serving as a study guide.
This book is edited by Li Genqiang, who is also responsible for the overall compilation, revision, and finalization. Xie Yue'e, Wu Ronghui, and Du Sichun serve as associate editors. Other contributors include Cao Yiwang, Yin Hongxia, Wang Wenbin, Liu Min, Li Hong, Du Jinghong, Wang Tao, and Li Hui, among others. Yin Haibo and Wang Zhangwei carefully debugged some of the source code. Due to the authors' limited expertise, inaccuracies or errors may inevitably exist in the book. We sincerely welcome experts and readers to provide feedback and corrections.
Editors, October 2004
This book is a supplementary guide to 《Data Structures (C++ Edition)》。 It consists of three parts: solutions to exercises and analysis of typical examples from the main textbook, hands-on practice guidance, and mock exams with reference answers. In addition to providing solutions to the exercises in the main textbook, this book also includes algorithm analysis and implementation of typical examples. The hands-on practice section offers 10 practice sessions, each containing multiple practice problems with objectives, algorithm hints, algorithm analysis, and implementation. Relevant personnel from different institutions can select according to their. Finally, as the concluding part of the book, it provides 10 mock exams with reference answers to assess students' understanding and mastery of data structures.
The book is rich in content, diverse in question types, broad in scope, and highly adaptable, closely aligning with the content of 《Data Structures (C++ Edition)》。 It can be used by undergraduate and graduate students in universities and colleges, as well as self-learners and professionals studying data structures.