Больше связанных списков в C

Question

Прежде чем я начну, я хочу прояснить, что я не хочу ответа на мою проблему HOMEWORK, я просто хотел бы, если бы кто-то мог на самом деле объяснить, что именно мой инструктор запрашивает в этом задании (предпочтительно дурацкая версия) и, возможно, полезный толчок в правильном направлении.У меня много проблем с этой темой, и всякий раз, когда я спрашиваю инструктора, я обнаруживаю, что он смущает меня больше всего на свете.

Итак, вот присваивание:

1.Добавить новую функцию insertN (список структур * x, int num, int pos, int n), которая будет вставлять n копий целого числа numв положении pos, если это возможно (если pos слишком велико, примите соответствующие меры).Главное, что меня здесь смущает, это то, что он подразумевает под позицией поз.

Вот код, с которым я работаю - он был написан моим учителем, и я должен изменить его.

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

struct list {
    int data;
    struct list * next;
        };

struct list *slist;

/*adds a node at the end of the linked list*/
void insert(struct list *x,int num){
  /*if the list is empty*/
  if(x==NULL){
    /*create first node*/
    slist=malloc(sizeof(struct list));
    slist->data=num; 
    slist->next=NULL;
    }
  else{
    /*go to the last node*/
    while(x->next!=NULL) x=x->next;
    /*add node at the end*/
      x->next=malloc(sizeof(struct list));
      x->next->data=num;
      x->next->next=NULL;

  }
}


void display(struct list *x){
  /*traverse the entire linked list*/
  while(x!=NULL){
    printf("%d->",x->data);
    x=x->next;
  }
  printf("NULL");
}

void reverse(struct list *x){
  struct list *prev,*rev,*temp;

  prev=x;
  rev=NULL;

  while(prev!=NULL){
    temp=rev;
    rev=prev;
    prev=prev->next;
    rev->next=temp;
  }
  slist=rev;
}

void search(struct list *x,int a){
struct list *runner;
int found=0;
  for(runner=x;runner!=NULL;runner=runner->next){
  if(runner->data==a){
    printf("data found"); 
    found=1;
break;
  }
  }
if(found==0) printf("data not found");

}

main(){
  int number,a;

  slist=NULL;/*empty linked list*/

  printf("Enter the element for data part:");
  scanf("%d",&number);
  insert(slist,10);
  insert(slist,number);

  insert(slist,20);

  display(slist);
  printf("\n");

  reverse(slist);

  display(slist);
  printf("\nEnter the element for searching:");
  scanf("%d",&a);
  search(slist,a);
  printf("\n");
  getchar();
  getchar();
}

Опять же, я не ожидаю ответа на проблему, простообъяснение и толчок в правильном направлении.

Answer 1

Говоря «в позиции 5», он означает, что он хочет, чтобы вы перебрали («пройдите») список из 5 шагов, а затем вставили туда.

Если у вас есть ссылка на список, подобный так:

struct list * current;

Один шаг можно сделать так:

current = current -> next;

Теперь вам нужно сделать это, пока вы не окажетесь в правильном положении, а затем вставить туда.

Answer 2

Допустим, в slist есть 3 элемента:

+---+    +----+    +---+
| 7 | -> | 48 | -> | 9 | -> NULL
+---+    +----+    +---+

которую вы создали, сделав что-то вроде:

slist=NULL;
insert(slist, 7);
insert(slist, 48);
insert(slist, 9);

Ваша задача - реализовать функцию с именем insertN(struct list *x, int num, int pos, int n), которая вставляет один или несколько повторяющихся элементов в список в заданной позиции.

Когда я использую эту функцию, я могу сказать:

insertN(slist, 69, 1, 2);

, что означает ", вставьте 2 элемента, содержащих 69, в слайс в позиции 1" .
Поэтому после звонка slist должно выглядеть так:

+---+    +----+    +----+    +----+    +---+
| 7 | -> | 69 | -> | 69 | -> | 48 | -> | 9 | -> NULL
+---+    +----+    +----+    +----+    +---+

Answer 3

Положение i можно найти с помощью указателей i next. Так что 0 - это начало списка, так как вы попадаете туда без указания next. Если список содержит n элементов, то позиция n относится к концу.

Вам придется изменить цикл после комментария go to the last node. Вам также придется обработать несколько угловых случаев, 0 из которых является одним из них. (Подсказка: это очень похоже на случай, когда список пуст.)

Answer 4

Ребята, ответ уже принят, но что нужно сделать, когда pos велико. Поскольку это будет в вычислительном отношении очень дорого.Я думаю, что было бы лучше оставить два указателя, один в начале списка и один в конце.

Но так как это один список, мы не можем перебрать его в обратном направлении. Так что, ребята, что мы должны делатьдля случая, когда pos большое, что является важным аспектом проблемы, которую каждый пропустил.

Answer 5

что-то вроде этого (это вставить только один узел, расширить его, чтобы вставить n элементов):

 function insertN(struct list *x, int num, int pos, int n){
    int k=0;
    struct list *nd=x,*tmp;
    while(nd){
        if(k==pos){           // position reached ?
            tmp=nd->next;
            nd->next= new_node(num); 
            nd->next->next=tmp;
            return 1;         // succedd node inserted
        }
        nd=nd->next;          //next node
        k++;                 // next position
    }
    // nd == null means pos is too large
    return 0; // failed to insert node at position pos;

}