数据结构基础(三)

Chapter 2 Linear Table

List, Stacks, Queue

Abstract Data Type / ADT

$Data Type=\{Objects\}+\{Operations\}$

Characteratics of ADT

• Separated from the representation and implementation

 

List

ADT

Objects item
Operations Find, Print, Making an empty, Finding, Insert. Delete…

 

Array Implementation

array[i] = item_i

Advan.

• Find quickly

Disadvan.

• MaxSize has to be estimated
• Insertion and Deletion slowly

 

Linked List Implementation

LinkedListNode = { ptrToNextNode, item_i }

[Eg]

typedef struct listNode *listPtr;
typedef struct listNode {
  ElemType data;
  listPtr next;
};
listPtr head;
headNode = (listPtr*)malloc(sizeof(struct listNode));
headNode.data = None;
headNode.next = None;

tip Use Dummy Head Node to cut off extra codes!!
dummy: fake

Insert

tmp->next = node->next;
node->next = tmp;

Delete

curNode->next = node->next;
free(node);

tip Remember to free the trash node to save memory

 

Doubly Linked Circular Lists

[Eg]

typedef struct listNode *listPtr;
typedef struct listNode {
  ElemType data;
  listPtr pre, next;
};
listPtr head;
headNode = (listPtr*)malloc(sizeof(struct listNode));
headNode.data = None;
headNode.pre = head;
headNode.next = head; // here is difference

Let tail node’s next point to head node, while let head node’s pre point to tail node.

Applications

1. The Polynomial ADT
2. Cursor Implementation of Linked Lists (no pointer)
    

The Stack ADT

ADT

• Last-In-First-Out list
• insertions and deletions made at the top only

 

Implementations

Linked List Implementation

• Push

  Tmp -> Next = S -> Next;
  S -> Next = Tmp;

• Top

  return S -> Next -> Element;

• Pop

  Ret = S -> Next;
  S -> Next = S -> Next -> Next;
  free(Ret);

To keep an another recycle bin stack can reduce the expense of regular malloc() and free().

Array Implementation

struct StackRecord{
	int capacity;
	int topOfStack;	// -1 for empty stack
	ElementType *array;
};

• Push
• Top
• Pop

Note

1. The stack model must be well encapsulated.
2. Error check must be done before Push, Top and Pop.

 

Application

1. Balancing Symbols

2. Postfix Evaluation

   这个音效特别棒嗷

3. Infix to Postfix Conversion

4. Function Calls

 

The Queue ADT

ADT

Implementations

Array Implementation of Queues

struct QueueRecord{
  int capacity;
  int front;
  int rear;
  int size;
  ElementType *array;
}

 

Circular Queue