Data structure Exercise - linked list (linear list, stack and queue) - delete elements greater than x and less than y in the linked list / local inversion of single linked list

Article launch and subsequent updates: https://mwhls.top/1034.html
For new updates, please go to mwhls.top see.
There is no picture / format error. Please check the first page of the article at the top.

Data structure Exercise directory

Single choice questions

  1. If the head of the single linked list that does not take the lead node is empty, the judgment condition is _.
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
  2. If the single linked list head of the leading node is empty, the judgment condition is _.
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
  3. The tail node (pointed by p) of the non empty cyclic single linked list head satisfies _.
    A. p—>next= =NULL B. p= =NULL
    C. p—>next= =head D. p= =head
  4. The operation of inserting the node indicated by s after the node indicated by p in the circular double linked list is _.
    A. p—>right=s; s—>left=p; p—>right—>left=s; s—>right=p—>right;
    B. p—>right=s; p—>right—>left=s; s—>left=p; s—>right=p—>right;
    C. s—>left=p; s—>right=p—>right; p—>right=s; p—>right—>left=s;
    D. s—>left=p; s—>right=p—>right; p—>right—>left=s; p—>right=s;
  5. In a single linked list, it is known that the node referred to by q is the precursor node of the node referred to by p. if the s node is inserted between q and p, execute __.
    A. s—>next=p—>next; p—>next=s;
    B. p—>next=s—>next; s—>next=p;
    C. q—>next=s; s—>next=p;
    D. p—>next=s; s—>next=q;
  6. In a single linked list, if the node indicated by p is not the last node and the node indicated by s is inserted after p, execute __.
    A. s—>next=p; p—>next=s;
    B. s—>next=p—>next; p—>next=s;
    C. s—>next=p—>next; p=s;
    D. p—>next=s; s—>next=p;
  7. In a single linked list, if the subsequent nodes of the node indicated by p are deleted, execute __.
    A. p—>next= p—>next—>next;
    B. p= p—>next; p—>next= p—>next—>next;
    C. p—>next= p—>next;
    D. p= p—>next—>next;
  8. When finding a single linked list with n nodes whose value is equal to x nodes, the average comparison is required when the search is successful____ Nodes.
    A. n B. n/2 C. (n-1)/2 D. (n+1)/2
  9. The time complexity of inserting a new node into an ordered single linked list with n nodes and still ordered is __.
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
  10. Given a vector with n elements, the time complexity of establishing an ordered single linked list is __.
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
  11. When a node indicated by s is inserted into a chain stack whose top pointer is HS, execute __. (without empty header node)
    A. HS—>next=s;
    B. s—>next= HS—>next; HS—>next=s;
    C. s—>next= HS; HS=s;
    D. s—>next= HS; HS= HS—>next;
  12. When deleting a node from a chain stack whose top pointer is HS, save the value of the deleted node with x, and execute __. (without empty header node)
    A. x=HS; HS= HS—>next;
    B. x=HS—>data;
    C. HS= HS—>next; x=HS—>data;
    D. x=HS—>data; HS= HS—>next;

Completion

  1. Single linked list is____ Link store representation of.
  2. Can use____ Represents a tree structure.
  3. In the double linked list, each node has two pointer fields, one pointing to __, The other one points to _.
  4. When inserting a node indicated by s before the node indicated by p in a single linked list, you can perform the following operations:
    ⑴ s—>next=____;
    ⑵ p—>next=s;
    ⑶ t=p—>data;
    ⑷ p—>data=____;
    ⑸ s—>data=____;
  5. When deleting the node indicated by p in a single linked list, you should perform the following operations:
    q= p—>next;
    p—>data= p—>next—>data;
    p—>next=____;
    free(q);
  6. The condition that the head of a single linked table with a head node is empty is _.
  7. When inserting a node indicated by s after the node indicated by p in a single linked list, execute s - > next=____ And p - > next=____ Operation of.
  8. The tail node of the non empty cyclic single linked list head (pointed by p) satisfies the condition _.
  9. In the chain stack whose top pointer is HS, the condition to determine whether the stack is empty is ___.
  10. For a single linked list with n nodes, the time complexity of inserting a new node after knowing the node referred to by p is __; The time complexity of inserting a new node after a node with a given value of x is __.

Algorithm design problem

  1. It is known that the elements in the linear table are arranged in order with increasing values, and the single linked list is used as the storage structure. Try to write an algorithm to delete all elements greater than x and less than y in the table (if such elements exist in the table) and release the deleted node space at the same time.
  2. Try to write an algorithm to realize the local inversion of single linked list.
  3. Assuming that the queue is represented by the circular linked list of the leading node, and only one pointer is set to point to the element node at the end of the queue (note that the header pointer is not set), try to write the corresponding queue initialization, in queue and out of queue algorithms.

Analysis of single choice questions

  1. If the head of the single linked list that does not take the lead node is empty, the judgment condition is _.
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
    The single linked list head without the leading node saves the address of the first node in the linked list,
    If the linked list is empty, the first node is NULL, that is, head==NULL
    .
  2. If the single linked list head of the leading node is empty, the judgment condition is _.
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
    The single linked list head without the leading node stores the information of the linked list, or it is empty for indication only
    Head next is the address of the first node in the linked list,
    If the linked list is empty, the first node is NULL, that is, head next = = NULL
    .
  3. The tail node (pointed by p) of the non empty cyclic single linked list head satisfies _.
    A. p—>next= =NULL B. p= =NULL
    C. p—>next= =head D. p= =head
    In the circular linked list, the next of the last node p points to the head node,
    That is, P - > next = = head
    .
  4. The operation of inserting the node indicated by s after the node indicated by p in the circular double linked list is _.
    A. p—>right=s; s—>left=p; p—>right—>left=s; s—>right=p—>right;
    B. p—>right=s; p—>right—>left=s; s—>left=p; s—>right=p—>right;
    C. s—>left=p; s—>right=p—>right; p—>right=s; p—>right—>left=s;
    D. s—>left=p; s—>right=p—>right; p—>right—>left=s; p—>right=s;
    When inserting or deleting, if you only know one node address in the linked list and one node address to be inserted,
    The unknown node needs to be processed first to prevent the subsequent failure to find the location of the node.
    For example, in this problem, we know the p node in the circular double linked list and the s node to be inserted,
    The predecessor node of P - > right - > and the successor node of P - > right - > should be modified first,
    Because both are related to the p - > right node, once p - > right is modified, the node cannot be deduced from the known conditions, and the linked list will break,
    That is, the positions of S - > right = P - > right and P - > right - > left must be in front of P - > right = s,
    The operation of answer D is:
    1. Modify the precursor and successor of s, 2 Then modify the precursor of p - > next node, 3 Then modify the successor of the p node.
    .
  5. In a single linked list, it is known that the node referred to by q is the precursor node of the node referred to by p. if the s node is inserted between q and p, execute __.
    A. s—>next=p—>next; p—>next=s;
    B. p—>next=s—>next; s—>next=p;
    C. q—>next=s; s—>next=p;
    D. p—>next=s; s—>next=q;
    Different from the previous question, this question gives two nodes in the linked list, requiring new nodes to be inserted between them.
    That is to send sub questions. Because it is a single linked list, you can directly modify the follow-up, regardless of the order.
    .
  6. In a single linked list, if the node indicated by p is not the last node and the node indicated by s is inserted after p, execute __.
    A. s—>next=p; p—>next=s;
    B. s—>next=p—>next; p—>next=s;
    C. s—>next=p—>next; p=s;
    D. p—>next=s; s—>next=p;
    This question is similar to question 4. You need to execute the operations involving unknown nodes first,
    That is, first modify the successor of s to the successor of p, and then modify the successor of p to s.
    .
  7. In a single linked list, if the subsequent nodes of the node indicated by p are deleted, execute __.
    A. p—>next= p—>next—>next;
    B. p= p—>next; p—>next= p—>next—>next;
    C. p—>next= p—>next;
    D. p= p—>next—>next;
    The question is simple. Deleting p - > next means changing the successor of P to the successor of P - > next,
    .
  8. When finding a single linked list with n nodes whose value is equal to x nodes, the average comparison is required when the search is successful____ Nodes.
    A. n B. n/2 C. (n-1)/2 D. (n+1)/2
    The best case is to find the first node, and the worst case is to find the nth node,
    Therefore, the average is the sum of the two divided by two.
    .
  9. The time complexity of inserting a new node into an ordered single linked list with n nodes and still ordered is __.
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
    Inserting a new node in this question is to find the insertion position of the node, which is the result of the previous question
    However, because the time complexity generally does not retain the coefficient, it is O(n).
    .
  10. Given a vector with n elements, the time complexity of establishing an ordered single linked list is __.
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
    I think D is also OK,
    If you sort first and then create a linked list, it is the sorting time complexity + the time complexity of creating a linked list,
    The time complexity of establishing the linked list is n, which must be smaller than the sorting time complexity and can be omitted,
    Therefore, it is the time complexity of a sorting algorithm,
    If bubble sorting is used, it is O(n2), and if quick sorting is used, it is O(nlog2n),
    But there is also a possibility that he finds the smallest one first, and then adds it to the linked list one by one,
    Is to add the establishment of linked list to bubble sorting,
    That's O(n2).
    .
  11. When a node indicated by s is inserted into a chain stack whose top pointer is HS, execute __. (without empty header node)
    A. HS—>next=s;
    B. s—>next= HS—>next; HS—>next=s;
    C. s—>next= HS; HS=s;
    D. s—>next= HS; HS= HS—>next;
    The push and exit of the stack are executed at the top of the stack,
    The nodes in the chain stack include next successor and data data,
    Therefore, when inserting the s node, first modify the successor of s to the stack top pointer, and then point the stack top to s.
    .
  12. When deleting a node from a chain stack whose top pointer is HS, save the value of the deleted node with x, and execute __. (without empty header node)
    A. x=HS; HS= HS—>next;
    B. x=HS—>data;
    C. HS= HS—>next; x=HS—>data;
    D. x=HS—>data; HS= HS—>next;
    First handle the operations related to the node to be deleted, and then delete the node,
    Therefore, first save the data of the top node of the stack, and then exit the top node of the stack.

Analysis of blank filling questions

  1. A single linked list is a linked storage representation of a linear table.
    Write it down.
    .
  2. You can use a double linked list to represent a tree structure.
    Write it down.
    I have always felt that the linear structure of linked list can not represent the nonlinear structure of tree, which puzzles me.
    .
  3. In the double linked list, each node has two pointer fields, one pointing to the direct predecessor and the other pointing to the direct successor.
    Is the structure definition of double linked list.
    .
  4. When inserting a node indicated by s before the node indicated by p in a single linked list, you can perform the following operations:
    ⑴ s—>next=p->next;
    ⑵ p—>next=s;
    ⑶ t=p—>data;
    ⑷ p—>data=s->data;
    ⑸ s—>data=t;
    The solution to this problem is to insert s after p, and then exchange the data values of S and p,
    After all, only one node of the single linked list is given, and no pointer can point to the precursor of the node,
    Therefore, a similar effect can be achieved by exchanging node values.
    .
  5. When deleting the node indicated by p in a single linked list, you should perform the following operations:
    q= p—>next;
    p—>data= p—>next—>data;
    p—>next=p->next->next;
    free(q);
    This is the same as the above question. In order not to break the linked list, the address of p cannot be changed,
    Therefore, you can only exchange the data values of P and P - > next, and then delete p - > next.
    .
  6. If the head of a single linked table with a head node is empty, the condition is head - > next = = null.
    In the single linked list of the leading node, the successor node of the head node is the first node of the linked list.
    .
  7. When inserting a node indicated by s after the node indicated by p in a single linked list, the operations of S - > next = p - > next and p - > next=s should be performed.
    Same as multiple choice question 6.
    .
  8. The tail node of non empty cyclic single linked list head (pointed by P) meets the condition p - > next = = head.
    Circular single linked list, based on the single linked list, changes the successor of the tail node from NULL to head.
    But I think it's strange that P - > next = = null = = head in empty linked list also meets the conditions,
    Another point is that if the linked list is empty, the access of P - > next will report an error, because if P is empty, there will be no p - > next.
    I think the answer to this question can be judged by a single linked list,
    That is, head - > next with a header node= NULL,
    Headless node head= NULL.
    .
  9. In the chain stack whose top pointer is HS, the condition for determining the stack empty is HS==NULL.
    When the stack is empty, the pointer at the top of the stack is empty, and there is nothing similar to the head pointer in the stack (of course, it can also be set, but this question is asked like this, isn't it)
    .
  10. For a single linked list with n nodes, the time complexity of inserting a new node after knowing the node referred to by p is O(1); The time complexity of inserting a new node after a node with a given value of x is O(n).
    The insertion of linked list nodes only needs a fixed number of statements,
    However, finding the insertion position of the node will take varying amounts of time, which is the answer to question 8 of the multiple-choice question.

Analysis of the first and second problems of algorithm design

1. It is known that the elements in the linear table are orderly arranged with increasing values, and the single linked list is used as the storage structure. Try to write an algorithm to delete all elements greater than x and less than y in the table (if such elements exist in the table) and release the deleted node space at the same time.

void removeRangeInLink(lNode *head, int x, int y) {		//Remove values > x and < y from the linked list.
	lNode *node = head->next;
	while (node) {
		if (node->data >= y) return;
		else if (node->data > x) deleteLNode(node);
		else node = node->next;
	}
}

2. Try to write an algorithm to realize the local inversion of single linked list.

int getLinkNumber(lNode *head) {  //Used to calculate the number of nodes in the linked list, which is used by the inverse function
	lNode *node = head->next;
	int number = 0;
	while (node) {
		number++;
		node = node->next;
	}
	return number;
}

void reverseLink(lNode *head) {	  //Inverse function, double loop, exchange data between the ith node and num-i node
	lNode *node = head->next;
	lNode *rightNode;
	int number = getLinkNumber(head);
	int i, temp, i2;
	for (i = 1; i <= number / 2; ++i) {
		temp = node->data;
		rightNode = node;
		for (i2 = i; i2 <= number - i; ++i2) {
			rightNode = rightNode->next;
		}
		node->data = rightNode->data;
		rightNode->data = temp;
		node = node->next;
	}
}

Single linked list code: Simple introduction / review of data structure (I) - linear linked list (C language)
It can be realized after adding the function. After integration, the code is as follows:

/*1.It is known that the elements in the linear table are arranged in order with increasing values, and the single linked list is used as the storage structure. Try to write an algorithm,
 *Delete all elements greater than x and less than y in the table (if such elements exist in the table) and release the deleted node space at the same time.

 *2.Try to write an algorithm to realize the local inversion of single linked list.

*/

#include <stdio.h>
#include <stdlib.h>

typedef struct lNode{
	int data;
	struct lNode *next;
}lNode;

lNode *createLink();
void insertLNode(lNode *node, int newData);
void deleteLNode(lNode *node);
void printLink(lNode *head);
void removeRangeInLink(lNode *head, int x, int y);
int getLinkNumber(lNode *head);
void reverseLink(lNode *head);

int main() {
	lNode *head = createLink();
	printf("Output the contents of the original linked list:");
	printLink(head);
	//printf("output linked list content after removal:");
	//removeRangeInLink(head, 2, 8);
	//printLink(head);

	printf("Contents of reverse linked list:");
	reverseLink(head);
	printLink(head);


	system("PAUSE");
	return 0;
}

int getLinkNumber(lNode *head) {	//Used to calculate the number of nodes in the linked list, which is used by the inverse function
	lNode *node = head->next;
	int number = 0;
	while (node) {
		number++;
		node = node->next;
	}
	return number;
}

void reverseLink(lNode *head) {		//Inverse function, double loop, exchange data between the ith node and num-i node
	lNode *node = head->next;
	lNode *rightNode;
	int number = getLinkNumber(head);
	int i, temp, i2;
	for (i = 1; i <= number / 2; ++i) {
		temp = node->data;
		rightNode = node;
		for (i2 = i; i2 <= number - i; ++i2) {
			rightNode = rightNode->next;
		}
		node->data = rightNode->data;
		rightNode->data = temp;
		node = node->next;
	}
}

void removeRangeInLink(lNode *head, int x, int y) {		//Remove values > x and < y from the linked list.
	lNode *node = head->next;
	while (node) {
		if (node->data >= y) return;
		else if (node->data > x) deleteLNode(node);
		else node = node->next;
	}
}

lNode *createLink() {		//Create a linked list and return a linked list of the leading node.
	lNode *head = (lNode*)malloc(sizeof(lNode));
	lNode *node = head;
	head->next = NULL;
	int i = 0;
	for (i = 1; i <= 8; i++) {	//Linked list nodes are automatically generated for testing
		insertLNode(node, i);
		node = node->next;
	}
	return head;
}

void insertLNode(lNode *node, int newData) {	//Insert Knot 
	if (node->next == NULL) {
		node->next = (lNode*)malloc(sizeof(lNode));
		node->next->next = NULL;
		node->next->data = newData;
	}
	else {
		lNode *temp = (lNode*)malloc(sizeof(lNode));
		temp->next = node->next;
		temp->data = newData;
		node->next = temp;
	}
}

void deleteLNode(lNode *node) {		//Delete Vertex 
	if (node->next == NULL) {
		free(node);
	}
	else {
		lNode *temp;
		temp = node->next;
		node->data = temp->data;
		node->next = temp->next;
		free(temp);
	}
}

void printLink(lNode *head) {		//Print the linked list of the leading node. If the leading node is not used, change the first line head - > next to head.
	lNode *node = head->next;
	while (node) {
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\n");
}

Analysis of the third problem of algorithm design

3. Suppose that the queue is represented by the circular linked list of the leading node, and only one pointer is set to point to the element node at the end of the queue (note that the header pointer is not set), try to write the corresponding queue initialization, in queue and out of queue algorithms.

I don't quite understand this question, because the circular linked list of the leading node, whether the linked list is empty or not, has a head node as an indication,
In the queue, the head and tail of the empty queue point to the same node,
The linked list is used as a queue. According to the characteristics of the circular linked list, the tail of the linked list will point to the chain header, that is, the tail of the queue will point to the head of the queue,
Then there is a problem, an empty queue, with these things:
A chain header used only as an indication, and a queue tail (tail of Chain Watch) with no value but subsequent points to the chain header.
It is very strange that before inserting into the queue, there will be a node, and the node is still worthless.

But I managed to write it out, but I will also print out this redundant and worthless tail node,
And when exiting the queue, although they all exit, the value of the end of the queue will become the last exit value (that is, although the node exits, the end of the queue with null value will become this value).

Therefore, the code is for reference only.

/*
 * 3.Suppose that the queue is represented by the circular linked list of the leading node, and only one pointer is set to point to the element node at the end of the queue (note that the header pointer is not set),
 * Try to write the corresponding queue initialization, in queue and out of queue algorithms.
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct qNode {
	int data;
	struct qNode *next;
}qNode;

typedef struct queue{
	qNode *rear;
}queue;

queue *initQueue();
void enQueue(queue *q, int enData);
int deQueue(queue *q);
void printQueue(queue *q);

int main() {
	queue *q = initQueue();
	int i;
	for (i = 1; i <= 10; i++) {
		enQueue(q, i);
	}
	printQueue(q);

	for (i = 1; i <= 5; i++) {
		printf("%d", deQueue(q));
	}
	printQueue(q);

	system("PAUSE");
	return 0;
}

queue *initQueue() {	//Initialize an empty queue.
	queue *q = (queue*)malloc(sizeof(queue));
	q->rear = (qNode*)malloc(sizeof(qNode));	//Team tail
	q->rear->next = (qNode*)malloc(sizeof(qNode));	//Team leader
	q->rear->next->next = q->rear;	//The next one at the head of the team points to the end of the team
	return q;
}

void enQueue(queue *q, int enData) {
	qNode *newNode = (qNode*)malloc(sizeof(qNode));
	newNode->next = q->rear->next;
	newNode->data = enData;
	q->rear->next = newNode;
	q->rear = newNode;
}

int deQueue(queue *q) {
	qNode *temp = q->rear->next->next;	
	int returnData = temp->next->data;
	q->rear->next->next = q->rear->next->next->next;
	free(temp);
	return returnData;
}

void printQueue(queue *q) {
	qNode *node = q->rear->next->next;
	int i = 1;
	while (node !=q->rear->next){
		printf(" %d", node->data);
		node = node->next;
	}
	printf("\n");
}

Tags: C data structure linked list queue

Posted by james182 on Tue, 03 May 2022 16:20:34 +0300