作业解析-c语言数据结构

目录

1. 作业题目 ………………………………………………………………

2. 作业目的……………………………………………………………….

3. 运行效果……………………………………………………………….

4. 实现过程……………………………………………………………….

5. 知识点巩固 …………………………………………………………..

6 知识拓展………………………………………………………………..

7 学习建议………………………………………………………………..

作业辅导解析

CSC A48 – Assignment 1 – Collections, Linked Lists, and Data Processing

1.作业题目:

25th February, 2019

For those of us who like movies, but have the little tiny problem of spending most of our time at University (do you know anyone like that?), finding whether a movie is worth the time we spend on it or not is important.

Luckily, there’s a variety of sites that offer reviews and information about current and upcoming movies, so we can figure out what is worth spending time on.

For this assignment, we will implement a very simple movie review database that nevertheless provides the basic functionality that would allow you to decide whether or not you want to go see a particular movie from reviews posted by your friends, other UTSC students, or perhaps even your TAs and instructors.

Your little program, which from now on we will call MDB-c (for Movie DB in C) will allow you to:

Keep a collection of movie reviews that contains a movie title, movie studio, year, box-office total, and review information (more on that soon). Of course, you will be able to edit and update any of the data for any of the reviews, and you expect a user to search through your little database to find specific movies to get information about them.

2.作业目的:

1、 掌握 C 语言结构体的基本使用

2、 掌握 C 语言链表(linked list)的基本使用

3.运行效果:

image image

4.实现过程:

/*
  • CSC A48 – Winter 2019 – Assignment 1 starter *
  • (c) 2019 Marzieh Ahmadzadeh and Francisco Estrada
  • – No part of this code may be reproduced without written authorization *
  • This is the file where you will be doing most of your work. The
  • functionality you must provide for part 1 of the assignment is described
  • in the handout, and given in detail in the comments at the head of each
  • function below. *
  • Plan your work carefully, review the notes for Unit 3, and work carefully
  • to complete the functions in this file. At any point you can bring
  • questions to your TAs or instructors during office hours. But please
  • remember: *
  • – You should not post any assignment code on Piazza
  • – You should not share any part of your solution in any form
  • – You should definitely *help* other understand any ideas and
  • concepts regarding linked lists that you have already mastered,
  • but being careful not to give away parts of the solution, or
  • descriptions of how to implement functions below.
  • – If you are not sure whether you can or can not discuss some
  • particular aspect of the work to be done, remember it’s always
  • safe to talk with your TAs. *
  • All tasks to be completed by you are clearly labeled with a
  • ***** TO DO ****** comment block, which also gives you details
  • about what you have to implement. Look carefully and make sure
  • you don’t miss a thing! *
  • NOTE: This file contains no main() function! you can not compile
  • it on its own to create an executable. It’s meant to be used
  • together with Part1_driver.c – be sure to read that file carefully
  • to understand how to use the tests there – Any additional tests
  • you want to run on the code below should be added to Part1_driver.c *
  • Before you even get starter implementing, please complete the
  • student identification section below, and check that you are aware
  • of the policy on academic honesty and plagiarism.
*/ /* Student identification: *
  • Student Name (Last name, First name): Zhe Wang
  • Student Number: 1004928616
  • UTORid: wangz561
  • Your instructor’s name is: Paco Estrada
*/ /* Academic Integrity Statement: *
  • I hereby certify that the work contained in this file is my own, and
  • that I have not received any parts of my solution from other sources
  • including my fellow students, external tutoring services, the internet,
  • or algorithm implementations found online. *
  • Sign here with your name: Zhe Wang
*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define MAX_STR_LEN 1024

/* Compound data type declarations */

typedef struct MovieReview_struct

{

char movie_title[MAX_STR_LEN]; char movie_studio[MAX_STR_LEN]; int year;

float BO_total;

int score;

} MovieReview;

typedef struct ReviewNode_struct

{

MovieReview review;

struct ReviewNode_struct *next;

} ReviewNode;

ReviewNode *newMovieReviewNode()

{

the /*
  • This function allocates a new, empty ReviewNode, and initializes
  • contents of the MovieReview for this node to empty values.
  • The fields in the MovieReview should be set to:
  • movie_title=””
  • movie_studio=””
  • year = -1
  • BO_total = -1
  • score = -1 *
  • The *next pointer for the new node MUST be set to NULL *
    • The function must return a pointer to the newly allocated and initialized
    • node. If something goes wrong, the function returns NULL
*/

ReviewNode *node = (ReviewNode*)malloc(sizeof(ReviewNode));

if (node == NULL)

return NULL;

strcpy(node->review.movie_title, “”); strcpy(node->review.movie_studio, “”); node->review.year = -1;

node->review.BO_total = -1;

node->review.score = -1; node->next = NULL;

return node;

}

ReviewNode *findMovieReview(char title[MAX_STR_LEN], char

studio[MAX_STR_LEN], int year, ReviewNode *head)

{

/*
  • This function searches through the linked list for a review that matches the input query.
  • In this case, the movie review must match the title, studio, and year provided in the
  • parameters for this function. *
  • If a review matching the query is found, this function returns a pointer to the node that
  • contains that review. *
  • If no such review is found, this function returns NULL
*/

ReviewNode *node = head;

while (node)

{

if (strcmp(node->review.movie_title, title) == 0 && strcmp(node->review.movie_studio, studio) == 0 && node->review.year == year)

{

return node;

}

else

{

node = node->next;

}

}

return NULL;

}

ReviewNode *insertMovieReview(char title[MAX_STR_LEN], char

studio[MAX_STR_LEN], int year, float BO_total, int score, ReviewNode

*head)

{

/*
  • This function inserts a new movie review into the linked list. *
  • The function takes as input parameters the data neede to fill-in the review,
  • as well as apointer to the current head of the linked list. *
  • If head==NULL, then the list is still empty. *
  • The function inserts the new movie review *at the head* of the linked list,
  • and returns the pointer to the new head node. *
  • The function MUST check that the movie is not already in the list before
  • inserting (there should be no duplicate entries). If a movie with matching
  • title, studio, and year is already in the list, nothing is inserted and the
  • function returns the current list head.
*/

if (findMovieReview(title, studio, year, head) != NULL)

{

printf(“Sorry, that movie already exists\n”);

return head;

}

else

{

ReviewNode *node = newMovieReviewNode();

strcpy(node->review.movie_title, title); strcpy(node->review.movie_studio, studio); node->review.year = year;

node->review.BO_total = BO_total; node->review.score = score;

node->next = head;

return node;

}

}

int countReviews(ReviewNode *head)

{

/*
  • This function returns the length of the current linked list. This requires
  • list traversal.
*/

int length = 0; ReviewNode *node = head; while (node)

{

length += 1;

node = node->next;

}

return length;

}

void updateMovieReview(char title[MAX_STR_LEN], char

studio[MAX_STR_LEN], int year, float BO_total, int score, ReviewNode

*head)

{

/*
  • This function looks for a review matching the input query [title, studio, year].
  • If such a review is found, then the function updates the Box- office total, and the score.
  • If no such review is found, the function prints out
  • “Sorry, no such movie exists at this point”
*/

ReviewNode *node = findMovieReview(title, studio, year, head);

if (node == NULL)

{

printf(“Sorry, no such movie exists at this point\n”);

}

else

{

node->review.BO_total = BO_total; node->review.score = score;

}

}

ReviewNode *deleteMovieReview(char title[MAX_STR_LEN], char

studio[MAX_STR_LEN],int year, ReviewNode *head)

{

/*
  • This function removes a review matching the input query from the linked list. If no such review can
  • be found, it does nothing. *
  • The function returns a pointer to the head of the linked list (which may have changed as a result
  • of the deletion process)
*/

ReviewNode *node = head;

if (node == NULL)

return NULL;

if (strcmp(node->review.movie_title, title) == 0 &&

strcmp(node->review.movie_studio, studio) == 0 && node->review.year == year)

{

head = node->next;

free(node);

}

else

{

while (node->next)

{

if (strcmp(node->next->review.movie_title, title) == 0 &&

strcmp(node->next->review.movie_studio, studio) == 0 && node->next->review.year == year)

{

ReviewNode *remove = node->next; node->next = node->next->next;

free(remove);

break;

}

else

{

node = node->next;

}

}

}

return head;

}

void printMovieReviews(ReviewNode *head)

{

/*
  • This function prints out all the reviews in the linked list, one after another.
  • Each field in the review is printed in a separate line, with *no additional text*
  • (that means, the only thing printed is the value of the corresponding field). *
  • Reviews are separated from each other by a line of * “*******************” *
  • See the Assignment handout for a sample of the output that should be produced
  • by this function
*/

ReviewNode *node = head;

while (node)

{

printf(“%s\n%s\n”, node->review.movie_title, node->review.movie_studio);

printf(“%d\n%.6f\n%d\n”, node->review.year, node->review.BO_total, node->review.score);

printf(“**********************\n”); node = node->next;

}

}

void queryReviewsByStudio(char studio[MAX_STR_LEN], ReviewNode *head)

{

/*
  • This function looks for reviews whose studio matches the input query.
  • It prints out the contents of all reviews matching the query in exactly
  • the same format used by the printMovieReviews() function above.
*/

ReviewNode *node = head;

while (node)

{

if (strcmp(node->review.movie_studio, studio) == 0)

{

printf(“%s\n%s\n”, node->review.movie_title, node->review.movie_studio);

printf(“%d\n%.6f\n%d\n”, node->review.year, node->review.BO_total, node->review.score);

printf(“**********************\n”);

}

node = node->next;

}

}

void queryReviewsByScore(int min_score, ReviewNode *head)

{

/*
  • This function looks for reviews whose score is greater than, or equal to
  • the input ‘min_score’.
  • It prints out the contents of all reviews matching the query in exactly
  • the same format used by the printMovieReviews() function above.
*/

ReviewNode *node = head;

while (node)

{

if (node->review.score >= min_score)

{

printf(“%s\n%s\n”, node->review.movie_title, node->review.movie_studio);

printf(“%d\n%.6f\n%d\n”, node->review.year, node->review.BO_total, node->review.score);

printf(“**********************\n”);

}

node = node->next;

}

}

ReviewNode *deleteReviewList(ReviewNode *head)

{

/*
  • This function deletes the linked list of movie reviews, releasing all the
  • memory allocated to the nodes in the linked list. *
  • Returns a NULL pointer so that the head of the list can be set to NULL
  • after deletion.
*/

ReviewNode *node = head;

while (node)

{

ReviewNode *remove = node; node = node->next; free(remove);

}

return NULL;

}

ReviewNode *sortReviewsByTitle(ReviewNode *head)

{

/*
  • This function sorts the list of movie reviews in ascending order of movie
  • title. If duplicate movie titles exist, the order is arbitrary (i.e. you
  • can choose which one goes first). *
  • However you implement this function, it must return a pointer to the head
  • node of the sorted list.
*/

if (head == NULL)

return NULL;

ReviewNode *node_left = head, *node_right = NULL;

while (1)

{

int flag = 0;

while (node_left->next != node_right)

{

if (strcmp(node_left->review.movie_title, node_left->next->review.movie_title) > 0)

{

flag = 1;

MovieReview tmp_review = node_left->review; node_left->review = node_left->next->review; node_left->next->review = tmp_review;

}

node_left = node_left->next;

}

if (flag == 1)

{

return head;

}

else

{

node_right = node_left; node_left = head;

}

}

}

5.知识点巩固:

结构体 结构体就是将不同类型的数据组合成一个有机的整体,以便于引用。如定义一个学生的信息: struct student {

int num;

char name[20]; int score;

};

struct 为结构体关键字,student 就是这结构体的类型名,而 num,name, score 就是该结 构体的成员,他们可以是不同类型的,注意在定义类型的时候不要对结构体成员 num,name, score 赋初值。其次就是在大括号后面要有分号“;”。 定义变量的方式都是大同小异的,都为数据类型+变量名这样一种方式,比如 int 型,首先

得有 int 这样一个数据类型,然后再用 int 这个数据类型去定义一个变量,同样的,我们要 定义一个结构体变量,必须要有一个结构体类型,然后用这个类型去定义一个变量。

6.知识拓展:

链表 链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的 进行存储分配,也就是说,链表是一个功能极为强大的数组,可以在节点中定义多种数据 类型,还可以根据需要随意增添,删除,插入节点。链表都有一个头指针,一般以 head 来

表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数 据域的。链表中每个节点都分为两部分,一个数据域,一个是指针域。说到这里你应该就 明白了,链表就如同车链子一样,head 指向第一个元素:第一个元素又指向第二个元 素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部 分放一个“NULL”(表示“空地址”),链表到此结束。 链表的操作有许多,比如:链表的创建,修改,删除,插入,输出,排序,反序,清空链 表的元素,求链表的长度等等。

7.学习建议:

1、 结构体是 C 语言学习的基础课程需要务必巩固

2、 本次作业涉及到单向链表的建立、修改、删除、遍历、排序等

3、 在后续巩固中可以加强链表的学习,并通过编写链表遍历、修改的示例程序以达到举一 反三