Puz*_*ane 5 c iteration linked-list nodes
我目前正在编写一个程序,它具有反向打印链表的功能.
我需要使用迭代方法打印此代码打印的反向.
编辑:这是一个单一的链表.
提前致谢.
void print_backward_iteration(NODE *ptr) {
NODE *last, *current;
last = NULL;
printf("\n");
while (ptr != last) {
current = ptr;
while (current -> next != last) {
current= current -> next;
}
printf("%d ", current -> data);
last = current;
}
printf("\n");
}
这是我的完整代码:
#include <stdio.h>
#include <stdlib.h>
/* declaration of structure */
typedef struct node {
int data;
struct node *next;
} NODE;
/* declaration of functions */
NODE* insert_node(NODE *ptr, NODE *new);
NODE* find_node(NODE *ptr, int n);
NODE* delete_node(NODE *ptr, int n, int *success_flag_ptr);
void print_backward_iteration(NODE *ptr);
void print_backward_recursion(NODE *ptr);
int main(int argc, char *argv[]) {
int choice, x, flag_success;
NODE *ptr, *new, *result;
ptr = NULL;
do {
printf("\n1.\tInsert Integer into linked list\n");
printf("2.\tFind integer in linked list\n");
printf("3.\tDelete integer from linked list\n");
printf("4.\tPrint out integers backward using the iterative strategy\n");
printf("5.\tPrint out integers backward using the recursive strategy\n");
printf("6.\tQuit\n");
printf("\nEnter 1,2,3,4,5, or 6: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("\nPlease enter an integer: ");
scanf("%d", &x);
new = (NODE *)malloc(sizeof(NODE));
new->data = x;
ptr = insert_node(ptr, new);
printf("\nNode Inserted with value of %d.\n", ptr->data);
break;
case 2:
printf("\nPlease enter an integer: ");
scanf("%d", &x);
result = find_node(ptr, x);
if (result == NULL) {
printf("\nValue could not be found.\n");
} else {
printf("\nValue %d was found.\n", x);
}
break;
case 3:
printf("\nPlease enter an integer: ");
scanf("%d", &x);
ptr = delete_node(ptr, x, &flag_success);
if (result == NULL) {
printf("\nValue could not be found.\n");
} else {
printf("\nValue %d was deleted.\n", x);
}
break;
case 4:
print_backward_iteration(ptr);
break;
case 5:
printf("\n");
print_backward_recursion(ptr);
printf("\n");
break;
case 6:
printf("\nThank you for using this program.\n");
break;
default:
printf("\nInvalid Choice. Please try again.\n");
break;
}
}
while (choice != 6);
printf("\n*** End of Program ***\n");
return 0;
}
/* definition of function insert_node */
NODE* insert_node(NODE *ptr, NODE *new) {
new -> next = ptr;
return new;
}
/* definition of function find_node */
NODE* find_node(NODE *ptr, int n) {
while (ptr != NULL) {
if (ptr->data == n) {
return ptr;
} else {
ptr = ptr->next;
}
}
return NULL;
}
/* definition of function delete_node */
NODE* delete_node(NODE *ptr, int n, int *success_flag_ptr) {
NODE *temp = NULL;
if (ptr == NULL) {
*success_flag_ptr = 0;
return NULL;
}
if (ptr -> data == n) {
temp = ptr->next;
free(ptr);
*success_flag_ptr = 1;
return temp;
} else
ptr->next = delete_node(ptr->next,n,success_flag_ptr);
return ptr;
}
/* definition of function print_backward_iteration */
void print_backward_iteration(NODE *ptr) {
NODE *last, *current;
last = NULL;
printf("\n");
while (ptr != last) {
current = ptr;
while (current != last) {
current = current -> next;
}
printf("%d ", current -> data);
last = current -> next;
}
printf("\n");
}
/* definition of function print_backward_recursion */
void print_backward_recursion(NODE *ptr) {
NODE *last, *current;
last = NULL;
while (ptr != last) {
current = ptr;
printf("%d ", current -> data);
print_backward_recursion(current -> next);
last = current;
}
}
更新 - 我将下面的代码保留在一个偶然的机会,有人希望使用提供的任何方法实际反向打印链接列表sans-recursion可以从中获得一些使用.与此同时,OP的真正问题是:
"如何以头对尾的顺序打印链表？"
谁看到了那个？无论如何,
void print_node_list(const NODE* p)
{
printf("\n");
for (;p;printf("%d ",p->data),p=p->next);
printf("\n");
}
是的,就这么简单.
现在 - 近乎无价值的反向印刷讨论
符合您对迭代解决方案的要求,更重要的是,假设您的列表顺序在此操作完成后保持不变,您可以:
在迭代中管理节点指针堆栈,在单个传递列表时推送指针,然后从堆栈弹出指针以打印反向.需要两次传递(一次通过列表,一次通过堆栈).管理这样的堆栈有多种选择; 两个呈现如下.
执行简单的反向/打印/反向.需要三次传递(一次用于反向,一次用于打印,一次用于撤消 - 反向).
前者提供了以管理堆栈所需空间的价格保持列表不变(没有完成节点反转)的优点.后者提供了无需额外空间要求的好处,但是以列表中的三遍为代价,并且要求允许修改列表,尽管是暂时的.
你选择哪一个取决于你.
本地堆栈实现:(2遍,2*N*sizeof(指针)空间)
void print_reverse_node_list(const NODE* head)
{
struct stnode
{
struct stnode* next;
const NODE* node;
} *st = NULL;
while (head)
{
struct stnode* p = malloc(sizeof(*p));
if (p)
{
p->next = st;
p->node = head;
st = p;
head = head->next;
}
else
{
perror("Could not allocate space for reverse-print.");
exit(EXIT_FAILURE);
}
}
// walks stack, popping off nodes and printing them.
printf("\n");
while (st)
{
struct stnode* p = st;
st = st->next;
printf("%d ", p->node->data);
free(p);
}
printf("\n");
}
另一个本地堆栈实现(2遍,N*sizeof(指针)空间)
void print_reverse_node_list(const NODE* head)
{
NODE const **ar = NULL;
size_t i=0;
while (head)
{
// reallocate pointer array
NODE const **tmp = realloc(ar, ++i * sizeof(*tmp));
if (tmp)
{
ar = tmp; // remember new array
ar[i-1] = head; // last index gets the ptr
head = head->next; // advance to next node
}
else
{
perror("Could not allocate space for reverse-print.");
exit(EXIT_FAILURE);
}
}
// print nodes from [i-1] to [0]
printf("\n");
for (; i!=0; printf("%d ", ar[--i]->data));
printf("\n");
// don't forget to release the block (NULL is ok)
free(ar);
}
反向/打印/反向执行:(3次通过,无额外空间)
// print a node list.
void print_node_list(const NODE* p)
{
printf("\n");
for (;p;printf("%d ",p->data),p=p->next);
printf("\n");
}
// reverses a linked list in-place.
void reverse_node_list(NODE **headp)
{
if (!headp || !*headp)
return;
NODE *ptr = *headp, *next = NULL, *prev = NULL;
while (ptr)
{
next = ptr->next; // remember next node (1)
ptr->next = prev; // wire next to prev
prev = ptr; // set prev to current
ptr = next; // move to remembered next (see 1)
}
*headp = prev;
}
void print_reverse_node_list(NODE* head)
{
reverse_node_list(&head);
print_node_list(head);
reverse_node_list(&head);
}
小智 2
void print_Linked_List_iteration(NODE *ptr)
{
printf("\n");
while (ptr != NULL)
{
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}