Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include<stdlib.h>
- struct node {
- int data;
- struct node* next;
- };
- struct node* BuildOneTwoThree() {
- struct node* head = NULL;
- struct node* second = NULL;
- struct node* third = NULL;
- head = (struct node*) malloc(sizeof(struct node)); // allocate 3 nodes in the heap
- second = (struct node*) malloc(sizeof(struct node));
- third = (struct node*) malloc(sizeof(struct node));
- head->data = 1; // setup first node
- head->next = second; // note: pointer assignment rule
- second->data = 2; // setup second node
- second->next = third;
- third->data = 3; // setup third link
- third->next = NULL;
- // At this point, the linked list referenced by "head"
- // matches the list in the drawing.
- return head;
- }
- /*
- Takes a list and a data value.
- Creates a new link with the given data and pushes
- it onto the front of the list.
- The list is not passed in by its head pointer.
- Instead the list is passed in as a "reference" pointer
- to the head pointer -- this allows us
- to modify the caller's memory.
- */
- void Push(struct node** headRef, int data) {
- struct node* newNode = (struct node*) malloc(sizeof(struct node));
- newNode->data = data;
- newNode->next = *headRef; // The '*' to dereferences back to the real head
- *headRef = newNode; // ditto
- }
- void PushTest() {
- struct node* head = BuildOneTwoThree();// suppose this returns the list {2, 3}
- Push(&head, 1); // note the &
- Push(&head, 13);
- // head is now the list {13, 1, 2, 3}
- }
- // Return the number of nodes in a list (while-loop version)
- int Length(struct node* head) {
- int count = 0;
- struct node* current = head;
- while (current != NULL) {
- count++;
- current = current->next;
- }
- return(count);
- }
- void displayList(struct node* head){
- for(struct node* current = head;current!=NULL;current = current->next)
- printf("%d ", current -> data);
- printf("\n");
- }
- //#1
- /*
- Given a list and an int, return the number of times that int occurs
- in the list.
- */
- int Count(struct node* head, int searchFor) {
- int count = 0;
- struct node *current;
- for(current = head;current !=NULL;current = current->next){
- if (current->data == searchFor)
- count++;
- }
- return count;
- }
- int CountTest() {
- struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
- return Count(myList, 2); // returns 1 since there's 1 '2' in the list
- }
- //#2
- // Given a list and an index, return the data
- // in the nth node of the list. The nodes are numbered from 0.
- // Assert fails if the index is invalid (outside 0..lengh-1).
- int GetNth(struct node* head, int index) {
- int count = 0;
- struct node* current;
- for(current =head;current!=NULL;current=current->next){
- if (count == index)
- return current->data;
- count++;
- }
- return -1;
- }
- //#3
- void DeleteList(struct node** headRef) {
- struct node* current = *headRef;
- struct node* temp;
- while(current!=NULL){
- temp= current;
- current = current->next;
- free(temp);
- }
- *headRef = NULL;
- }
- void DeleteListTest() {
- struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
- DeleteList(&myList); // deletes the three nodes and sets myList to NULL
- }
- //#4
- /*
- The opposite of Push(). Takes a non-empty list
- and removes the front node, and returns the data
- which was in that node.
- */
- int Pop(struct node** headRef) {
- if (*headRef==NULL)
- return -1;
- struct node* current = *headRef;
- int result = current->data;
- *headRef = (*headRef)->next;
- free(current);
- return result;
- }
- void PopTest() {
- struct node* head = BuildOneTwoThree(); // build {1, 2, 3}
- int a = Pop(&head); // deletes "1" node and returns 1
- int b = Pop(&head); // deletes "2" node and returns 2
- int c = Pop(&head); // deletes "3" node and returns 3
- int len = Length(head); // the list is now empty, so len == 0
- }
- //#5
- /*
- A more general version of Push().
- Given a list, an index 'n' in the range 0..length,
- and a data element, add a new node to the list so
- that it has the given index.
- */
- void InsertNth(struct node** headRef, int index, int data) {
- if(index==0){
- Push(headRef, data);
- return;
- }
- struct node* current = *headRef;
- struct node* newNode;
- newNode = (struct node*) malloc(sizeof(struct node));
- newNode->data = data;
- int count =0;
- while(current!=NULL){
- if (count==index-1){
- newNode->next = current->next;
- current->next = newNode;
- return;
- }
- count++;
- current = current->next;
- }
- }
- void InsertNthTest() {
- struct node* head = NULL; // start with the empty list
- InsertNth(&head, 0, 13); // build {13)
- InsertNth(&head, 1, 42); // build {13, 42}
- InsertNth(&head, 1, 5); // build {13, 5, 42}
- displayList(head);
- DeleteList(&head); // clean up after ourselves
- }
- //#6
- void SortedInsert(struct node** headRef, struct node* newNode) {
- if (*headRef == NULL || (*headRef)->data >= newNode -> data){
- newNode->next = *headRef;
- *headRef = newNode;
- }
- struct node* current = *headRef;
- //struct node* temp;
- while(current->next!=NULL){
- if (current->data <= newNode->data && current->next->data >= newNode->data){
- newNode->next = current->next;
- current->next = newNode;
- return;
- }
- current = current->next;
- }
- current->next = newNode;
- newNode->next=NULL;
- }
- //#7
- // Given a list, change it to be in sorted order (using SortedInsert()).
- void Sort(struct node** headRef) {
- struct node* result = NULL;
- struct node* current = *headRef;
- struct node* temp;
- while(current!=NULL){
- temp = current->next;
- SortedInsert(&result, current);
- current = temp;
- }
- *headRef = result;
- }
- //#8
- // Append 'b' onto the end of 'a', and then set 'b' to NULL.
- void Append(struct node** aRef, struct node** bRef) {
- if (*aRef==NULL){
- *aRef= *bRef;
- free(bRef);
- return;
- }
- struct node* current = *aRef;
- while(current!= NULL){
- current = current->next;
- }
- current = *bRef;
- free(bRef);//? *bRef=NULL;
- }
- //#9
- /*
- Split the nodes of the given list into front and back halves,
- and return the two lists using the reference parameters.
- If the length is odd, the extra node should go in the front list.
- */
- void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef) {
- struct node* current;
- int length = 0;
- for(current = source;current!=NULL;current=current->next)
- length++;
- if (length%2==0){
- length/=2;
- *frontRef = source;
- current = *frontRef;
- for(int i =0;i<length;i++){
- current = current->next;
- }
- *backRef= current->next;
- current->next = NULL;
- }
- }
- //#10
- /*
- Remove duplicates from a sorted list.
- */
- void RemoveDuplicates(struct node* head) {
- // Your code...
- }
- int main (){
- //#1
- printf("Q1 : %d\n", CountTest());
- //#2
- struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
- displayList(myList);
- InsertNth(&myList, 0, 20);
- displayList(myList);
- InsertNth(&myList, 4, 1);
- displayList(myList);
- Sort(&myList);
- displayList(myList);
- return 0;
- }
Add Comment
Please, Sign In to add comment