book

Data structures based on linear relations

Name: Data structures based on linear relations
ISBN: 9783110593181

by Xingni Zhou, Zhiyuan Ren, Yanzhuo Ma, Kai Fan, Xiang Ji

May 2020

Intermediate to advanced

308 pages

9h 14m

English

De Gruyter

Read now

Unlock full access

Preface
My experience in teaching and learning data structuresThe cruxes in learning data structuresThe relationship between program design and data structuresThe relationship between data structures and other coursesThe importance of data structuresWill data structures be outdatedAdditional contents in this book about the implementation of algorithms and programsDescription of the algorithmsA brief introduction to the course “data structures”Basic aimsOrganizational structure of this bookAcknowledgments
1 Introduction
1.1 Let’s begin with programming1.2 The data to be processed by the program1.3 The introduction of data structures1.4 Basic concepts of data structures1.4.1 Basic terminologies of data structures1.4.2 The three key elements of data structures1.5 How to design algorithms1.5.1 The definition of algorithm and representation methods1.5.2 The relation between algorithm design and function design1.5.3 Software design method1.5.4 General steps of algorithm design1.6 How to evaluate algorithms1.6.1 The design requirements of algorithms1.6.2 Measurement methods of algorithm efficiency1.7 The pre-execution analysis methods of algorithm efficiency1.7.1 The size of the problem and the strategy of the algorithm1.7.2 The upper and lower bounds of algorithm efficiency1.7.3 The asymptotic upper bound – the time complexity of the algorithm1.7.4 The comprehensive discussion on the time complexity of algorithms1.7.5 The analysis methods on the space efficiency of the algorithm1.8 Comprehensive evaluation of algorithm performance1.9 Chapter summary1.10 Exercises1.10.1 Multiple-choice questions1.10.2 Practical problems
2 The data structure whose nodes share a linear logical relation – linear list
2.1 Viewing the linear list from the perspective of logical structure2.1.1 The sequential relations that exist in practical problems2.1.2 The logical structure of linear lists2.2 One of the storage structures of linear lists – sequential list2.2.1 The design of storage structure of a sequential list2.2.2 The operations on sequential list2.2.3 Discussion on the sequential storage structure2.3 The second storage method for linear list – linked list2.3.1 Introduction 1 – the story of word2.3.2 Introduction 2 – linked lists in mobile phones2.3.3 The storage of singly linked lists2.3.4 Operations on the singly linked list2.3.5 Discussion of singly linked lists2.3.6 Circular linked lists2.3.7 Doubly linked list2.3.8 Summary on linked lists2.4 Examples of the application of linear lists2.4.1 Algorithm design2.4.2 Program implementation2.5 Comparisons between sequential list and linked list2.5.1 Considerations based on storage2.5.2 Considerations based on operations2.5.3 Considerations based on the environment2.6 Summary of the chapter2.7 Exercises2.7.1 Multiple-choice questions2.7.2 Algorithm design exercises
3 Linear list with restricted operations – stack and queue
3.1 Stack – a linear list managed in a first-in–last-out manner3.1.1 Introduction to the operation pattern of stack3.1.2 The logic structure of stack3.1.3 The design of the storage structure of stacks3.1.4 Operations on stack3.1.5 Comparison of various stack structures3.1.6 Examples of the application of stack3.1.6.1 Base conversion3.1.6.2 Implement recursive functions with stack3.1.6.3 Evaluating expressions3.1.7 Recursion – a “first-in–last-out” process3.1.7.1 The concept of recursion and its key elements3.1.7.2 Analysis of features of recursion3.1.7.3 Summary of recursion3.2 Queue – linear list managed in a “FIFO” manner3.2.1 Introduction to the queue processing model3.2.2 The logical structure of queue3.2.3 The sequential storage structure of queue3.2.3.1 Sequential queue3.2.4 Basic operations on sequential queue3.2.4.1 Basic operation on sequential queue – set queue as empty3.2.4.2 Basic operation on sequential queue – check emptiness of queue3.2.4.3 Basic operation on sequential queue – get the head element3.2.4.4 Basic operation on sequential queue – insert element3.2.4.5 Basic operation on sequential queue – delete element3.2.5 Linked storage structure of queue3.2.6 Basic operations on linked queue3.2.6.1 Basic operations on linked queue – initialize and set the queue as empty3.2.6.2 Basic operation on linked queue – checking emptiness of queue3.2.6.3 Basic operation on linked queue – retrieve the head node3.2.6.4 Basic operation on linked queue – enqueuing3.2.6.5 Basic operation on linked queue – dequeuing3.2.6.6 Destroying the linked queue3.2.7 Comparison of different queue structures3.2.8 Examples of the application of queue3.2.8.1 Application of queue 1 – radix sort3.2.8.2 Application of queue 2 – card game3.3 Chapter summary3.4 Exercises3.4.1 Multiple choice questions3.4.2 Practical questions3.4.3 Algorithm design
4 Sequential list with special contents – multidimensional arrays and strings
4.1 Multidimensional arrays4.1.1 The concept of arrays4.1.2 The storage structure of arrays4.2 The compressional storage of matrices4.2.1 The compressional storage of symmetric matrix4.2.2 The compressional storage of triangular matrix4.2.3 The compressional storage of diagonal matrix4.2.4 Compressional storage of sparse matrix4.3 String4.3.1 The definition of string4.3.2 The storage structure of string4.3.3 Search on strings – pattern matching4.4 Chapter summary4.5 Exercises4.5.1 Multiple-choice questions4.5.2 Applied problems4.5.3 Algorithm design
Appendix A Relation graph of data
Appendix B How to add custom header files
Appendix C Format of software design manual
Steps to writing huge and complex applicationsAspects to consider for program implementationFormat of software design manual
Appendix D Answers to selected exercises
Chapter 1 IntroductionChapter 2 The data structure whose nodes share a linear logical relation – linear listChapter 3 Linear list with restricted operations – stack and queueChapter 4 Sequential list with special contents – multidimensional arrays and strings
References

Index

Content preview from Data structures based on linear relations

3 Linear list with restricted operations – stack and queue

Main Contents

The logic structure definition of stack
The storage structure of stack and the implementation of its operations
The logic structure definition of queue
The storage structure of queue and the implementation of its operations

Learning Aims

Comprehend the features and operation methods of stacks and queues
Correctly choose them in actual applications

3.1 Stack – a linear list managed in a first-in–last-out manner

The notion of “stack” in data structures comes from the meaning of “stack” in daily lives, which has the characteristic of “first-in–last-out.” See Fig. 3.1. For things that can be stacked together, we always put the ones below first, and then ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9783110593181

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data structures based on linear relations

by Xingni Zhou, Zhiyuan Ren, Yanzhuo Ma, Kai Fan, Xiang Ji

3 Linear list with restricted operations – stack and queue

3.1 Stack – a linear list managed in a first-in–last-out manner

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.