Objective-C 数据结构面试题解析与代码实现
在Objective-C面试中，数据结构是一个重要的考察点。掌握常见的数据结构及其在Objective-C中的实现，对于面试官来说是一个基本要求。本文将围绕Objective-C语言中的数据结构，解析一些常见的面试题，并提供相应的代码实现。
1. 链表（LinkedList）
面试题1：实现一个单向链表，包括插入、删除、查找和打印操作。
解答思路：
1. 定义链表节点结构体（`ListNode`）。
2. 实现链表类（`LinkedList`），包含插入、删除、查找和打印方法。
代码实现：
objective-c
@interface ListNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong) ListNode next;
- (instancetype)initWithValue:(id)value;
@end
@implementation ListNode
- (instancetype)initWithValue:(id)value {
self = [super init];
if (self) {
_value = value;
_next = nil;
}
return self;
}
@end
@interface LinkedList : NSObject
@property (nonatomic, strong) ListNode head;
- (instancetype)init;
- (void)insertWithValue:(id)value;
- (void)deleteWithValue:(id)value;
- (ListNode )findWithValue:(id)value;
- (void)printList;
@end
@implementation LinkedList
- (instancetype)init {
self = [super init];
if (self) {
_head = nil;
}
return self;
}
- (void)insertWithValue:(id)value {
ListNode newNode = [[ListNode alloc] initWithValue:value];
if (!_head) {
_head = newNode;
} else {
ListNode current = _head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
}
- (void)deleteWithValue:(id)value {
ListNode current = _head;
ListNode previous = nil;
while (current && [current.value isEqual:value]) {
if (previous) {
previous->next = current->next;
} else {
_head = current->next;
}
ListNode temp = current;
current = current->next;
[temp release];
}
}
- (ListNode )findWithValue:(id)value {
ListNode current = _head;
while (current) {
if ([current.value isEqual:value]) {
return current;
}
current = current->next;
}
return nil;
}
- (void)printList {
ListNode current = _head;
while (current) {
NSLog(@"%@", current.value);
current = current->next;
}
}
@end
2. 栈（Stack）
面试题2：实现一个栈，包括入栈、出栈、判断是否为空和打印栈顶元素操作。
解答思路：
1. 定义栈节点结构体（`StackNode`）。
2. 实现栈类（`Stack`），包含入栈、出栈、判断是否为空和打印栈顶元素方法。
代码实现：
objective-c
@interface StackNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong) StackNode next;
- (instancetype)initWithValue:(id)value;
@end
@implementation StackNode
- (instancetype)initWithValue:(id)value {
self = [super init];
if (self) {
_value = value;
_next = nil;
}
return self;
}
@end
@interface Stack : NSObject
@property (nonatomic, strong) StackNode top;
- (instancetype)init;
- (void)pushWithValue:(id)value;
- (id)pop;
- (BOOL)isEmpty;
- (id)peek;
@end
@implementation Stack
- (instancetype)init {
self = [super init];
if (self) {
_top = nil;
}
return self;
}
- (void)pushWithValue:(id)value {
StackNode newNode = [[StackNode alloc] initWithValue:value];
newNode->next = _top;
_top = newNode;
}
- (id)pop {
if (_top) {
id value = _top.value;
StackNode temp = _top;
_top = _top->next;
[temp release];
return value;
}
return nil;
}
- (BOOL)isEmpty {
return (!_top);
}
- (id)peek {
if (_top) {
return _top.value;
}
return nil;
}
@end
3. 队列（Queue）
面试题3：实现一个队列，包括入队、出队、判断是否为空和打印队列元素操作。
解答思路：
1. 定义队列节点结构体（`QueueNode`）。
2. 实现队列类（`Queue`），包含入队、出队、判断是否为空和打印队列元素方法。
代码实现：
objective-c
@interface QueueNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong) QueueNode next;
- (instancetype)initWithValue:(id)value;
@end
@implementation QueueNode
- (instancetype)initWithValue:(id)value {
self = [super init];
if (self) {
_value = value;
_next = nil;
}
return self;
}
@end
@interface Queue : NSObject
@property (nonatomic, strong) QueueNode front;
@property (nonatomic, strong) QueueNode rear;
- (instancetype)init;
- (void)enqueueWithValue:(id)value;
- (id)dequeue;
- (BOOL)isEmpty;
- (id)peek;
@end
@implementation Queue
- (instancetype)init {
self = [super init];
if (self) {
_front = nil;
_rear = nil;
}
return self;
}
- (void)enqueueWithValue:(id)value {
QueueNode newNode = [[QueueNode alloc] initWithValue:value];
if (!_rear) {
_rear = newNode;
_front = newNode;
} else {
_rear->next = newNode;
_rear = newNode;
}
}
- (id)dequeue {
if (_front) {
id value = _front.value;
QueueNode temp = _front;
_front = _front->next;
if (!_front) {
_rear = nil;
}
[temp release];
return value;
}
return nil;
}
- (BOOL)isEmpty {
return (!_front);
}
- (id)peek {
if (_front) {
return _front.value;
}
return nil;
}
@end
4. 树（Tree）
面试题4：实现一个二叉树，包括插入、查找、遍历（前序、中序、后序）操作。
解答思路：
1. 定义树节点结构体（`TreeNode`）。
2. 实现二叉树类（`BinaryTree`），包含插入、查找、遍历方法。
代码实现：
objective-c
@interface TreeNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong) TreeNode left;
@property (nonatomic, strong) TreeNode right;
- (instancetype)initWithValue:(id)value;
@end
@implementation TreeNode
- (instancetype)initWithValue:(id)value {
self = [super init];
if (self) {
_value = value;
_left = nil;
_right = nil;
}
return self;
}
@end
@interface BinaryTree : NSObject
@property (nonatomic, strong) TreeNode root;
- (instancetype)init;
- (void)insertWithValue:(id)value;
- (TreeNode )findWithValue:(id)value;
- (void)preOrderTraversal;
- (void)inOrderTraversal;
- (void)postOrderTraversal;
@end
@implementation BinaryTree
- (instancetype)init {
self = [super init];
if (self) {
_root = nil;
}
return self;
}
- (void)insertWithValue:(id)value {
TreeNode newNode = [[TreeNode alloc] initWithValue:value];
if (!_root) {
_root = newNode;
} else {
TreeNode current = _root;
while (current) {
if ([current.value compare:value] == NSOrderedAscending) {
if (current->right) {
current = current->right;
} else {
current->right = newNode;
break;
}
} else {
if (current->left) {
current = current->left;
} else {
current->left = newNode;
break;
}
}
}
}
}
- (TreeNode )findWithValue:(id)value {
TreeNode current = _root;
while (current) {
if ([current.value isEqual:value]) {
return current;
}
if ([current.value compare:value] == NSOrderedAscending) {
current = current->right;
} else {
current = current->left;
}
}
return nil;
}
- (void)preOrderTraversal {
[self _preOrderTraversalWithNode:_root];
}
- (void)_preOrderTraversalWithNode:(TreeNode )node {
if (node) {
NSLog(@"%@", node.value);
[self _preOrderTraversalWithNode:node.left];
[self _preOrderTraversalWithNode:node.right];
}
}
- (void)inOrderTraversal {
[self _inOrderTraversalWithNode:_root];
}
- (void)_inOrderTraversalWithNode:(TreeNode )node {
if (node) {
[self _inOrderTraversalWithNode:node.left];
NSLog(@"%@", node.value);
[self _inOrderTraversalWithNode:node.right];
}
}
- (void)postOrderTraversal {
[self _postOrderTraversalWithNode:_root];
}
- (void)_postOrderTraversalWithNode:(TreeNode )node {
if (node) {
[self _postOrderTraversalWithNode:node.left];
[self _postOrderTraversalWithNode:node.right];
NSLog(@"%@", node.value);
}
}
@end
总结
本文针对Objective-C语言中的数据结构，解析了链表、栈、队列和二叉树等常见的数据结构面试题，并提供了相应的代码实现。通过学习和掌握这些数据结构，有助于提高在Objective-C面试中的竞争力。在实际开发过程中，灵活运用这些数据结构可以有效地提高代码质量和性能。
Comments NOTHING