Question

数据结构 课程 编程练习题，C语言构造单链表

键盘输入一个正整数n(10-20之间)。
构造单链表, 单链表的结点数目为输入的n(不包括
head结点)。
每个结点的data域的内容是随机产生的整数。
显示单链表的内容。
编写函数listMax, 找出数值最大的结点, 并显示其
位置及数值。
bool listMax(List &L);

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef unsigned int uint;
#if defined(__cplusplus)
#define new_type(_T) (_T*)malloc(sizeof(_T));
#else
#define new_type(_T) malloc(sizeof(_T));
#endif
typedef struct node {
    int val;
    node* next;
} node;
// 构建链表，返回头结点，并创建数目为n的子结点
// gen_rand_value为true时为结点填充随机数
node* create_list(uint n, bool gen_rand_value)
{
    node* head = new_type(node);
    head->next = NULL;
    head->val = 0;
    node* p = head;
    for (uint i = 0; i < n; ++i)
    {
        p->next = new_type(node);
        p = p->next;
        p->val = (gen_rand_value ? (rand()%100000) : 0);    // 生成5位数就好了，不用太大
        p->next = NULL;
    }
    return head;
}
// 释放链表空间
void delete_list(node* head)
{
    while (head)
    {
        node* p = head;
        head = head->next;
        delete p;
    }
}
// 打印链表内容
void print_list(node* head)
{
    int i = 0;
    for (node* p = head->next; p != NULL; p = p->next)
    {
        printf("%-6d", p->val);
        // 每行打印10个
        if (9 <= (i++))
        {
            printf("\n");
            i = 0;
        }
    }
    printf("\n");
}
// 找到最大值
typedef node List;
bool listMax(List &L)
{
    node* head = &L;
    node* p = head->next;
    if (p == NULL)
        return false;
    int nMax = 0;
    int pos = 0;
    for (int i = 0; p; p = p->next, ++i)
    {
        if (nMax < p->val)
        {
            nMax = p->val;
            pos = i;
        }
    }
    printf("最大值为: %d, 位置(0为头结点之后的第一个位置): %d\n\n", nMax, pos);
    return true;
}
int main(int argc, char** argv)
{
    srand(time(NULL));
    int n = 0;
    printf("链表数量: ");
    scanf("%d", &n);
    if (n < 0 || n > (2 << 16))
        printf("数量不合法\n\n");
    else
    {
        node* head = create_list(n, true);
        print_list(head);
        listMax(*head);
        delete_list(head);
    }
    system("pause");
    return 0;
}

Answer 2

代码可以直接运行，具体要求自己可以详细再研究
start*************************list.c****************************
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int list_is_empty(struct node_info *head)
{
return head->next == head;
}

void list_add(struct node_info *head, elem_t data)
{
//MALLOC_NODE(struct node_info,new_node);
struct node_info * new_node = (struct node_info *)
malloc(sizeof(struct node_info));

if (new_node != NULL) {
new_node->data = data;
new_node->next = head->next;
head->next = new_node;
}else{
fprintf(stderr,"malloc failed\n");
}

}

void list_add_tail(struct node_info *head, elem_t data)
{
struct node_info * new_node = (struct node_info *)
malloc(sizeof(struct node_info));

struct node_info *cur = NULL;
if (new_node != NULL) {
new_node->data = data;
for (cur = head->next;
cur->next != head ;
cur = cur->next)
;

new_node->next = cur->next;
cur->next = new_node;
}else{
fprintf(stderr,"malloc failed\n");
}

}

void list_del(struct node_info *head, elem_t data);
void node_del(struct node_info *head, struct node_info *node)
{
struct node_info *cur = NULL;

for (cur = head;
cur->next != head && cur->next != node;
cur= cur->next) {
;
}
cur->next = node->next;
node->next = node;
free(node);
}

void list_for_each(struct node_info *head,
void (*todo)(struct node_info *head,
struct node_info *node))
{
struct node_info *cur = NULL;

for ( cur = head->next ; cur != head; cur = cur->next) {
todo(head, cur);
}
}

void list_for_each_safe(struct node_info *head,
void (*todo)(struct node_info *head,
struct node_info *node))
{
struct node_info *cur = NULL;
struct node_info *tmp = NULL;

for (cur = head->next; cur != head; cur = tmp ) {
tmp = cur->next;
todo(head, cur);
}
}

void list_init(struct node_info *head)
{
head->data = 0;
head->next = head;
}

void list_destroy(struct node_info *head)
{
list_for_each_safe(head,node_del);
#if 0
while (!list_is_empty(head)) {
node_del(head, head->next);
}
#endif
}

void print_node(struct node_info *head, struct node_info *node)
{
printf("%lu ",node->data);
}

#define LEN 10
int main(void)
{

struct node_info *head = (struct node_info *)
malloc(sizeof(struct node_info));

if (head != NULL) {
list_init(head);
}else{
fprintf(stderr,"malloc failed\n");
goto error;
}

size_t i;
for (i = 0; i < LEN; ++i) {
list_add_tail(head,i);
}

list_for_each(head, print_node);
printf("\n");
list_destroy(head);
free(head);
return 0;
error:
return -1;
}
end****************************list.c***************************

start************************list.h*****************************
#pragma once
typedef size_t elem_t;
struct node_info {
elem_t data;
struct node_info *next;
};

#define MALLOC_NODE(type,name) ((type *)(name) = (type *)\
malloc(sizeof(type)))
int list_is_empty(struct node_info *head);
void list_add(struct node_info *head, elem_t data);
void list_add_tail(struct node_info *head, elem_t data);
void list_del(struct node_info *head, elem_t data);
void node_del(struct node_info *head, struct node_info *node);
void list_for_each(struct node_info *head,
void (*todo)(struct node_info *head,
struct node_info *node));

void list_for_each_safe(struct node_info *head,
void (*todo)(struct node_info *head,
struct node_info *node));
void list_init(struct node_info *head);
void list_destroy(struct node_info *head);
end*************************list.h******************************