[数据结构与算法]【C补充】链表专题 - 单向链表

链表 —— 由一连串的结构(称为结点node)组成，每个结点都包含指向下一个结点的指针，最后一个为空指针。

一、声明结点类型

struct node{
	int value;
	struct node *next;			//指向下一个结点
};

struct node *first = NULL;		//始终指向表中第一个结点的变量, 初始化为空

• node 为结构标记，通常可使用结构标记或 typedef 来定义一种特殊的结构类型。但若在结构中有一个指向相同结构类型的指针成员时，要求使用结构标记。

二、创建结点

创建结点的步骤：
① 为新结点分配内存单元；
② 将数据存储到新结点中；
③ 将新节点插入到链表中。

//步骤1：
struct node *new_node;			//指向新结点的临时指针
new_node = (struct node*)malloc(sizeof(struct node));

//步骤2：
new_node->value = 10;			//等价于(*new_node).value = 10;

三、->运算符

-> —— 右箭头选择 (right arrow selection)

• 需要通过一个指向结构的指针访问该结构的某个成员时，可使用->运算符。
• 运算对象必须为指向结构的指针。

//下面两者等价
new_node->value = 10;
(*new_node).value = 10;

• ->运算符产生左值，可以在任何允许使用普通变量的地方使用它，例如：

scanf("%d", &new_node->value);

四、在链表中插入结点

链表的优势在于可以在链表的任何位置添加结点。

我们在链表中插入一个新结点之前，需要先确定插入位置，由于插入后需要重新拼接，为此需要确定两个位置，分别为插入位置，和其前一个结点的位置。

• 插入结点之前需要前确定插入位置是否为链表开头
• 插入步骤：
  • 创建新结点 new_node (分配内存，存入数据)；
  • 确定插入位置 cur，和插入位置的前一个结点位置 prev；
  • 链接：将 cur 、new_node 和 prev 链接起来。

//创建新结点, 并存储好数据
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->value = 10;

//确定插入位置
struct node *cur = fisrt, *prev = NULL;		//待插入位置和其前一个结点的位置, 初始化
...

//向链表中插入结点
new_node->next = cur;
if(prev == NULL)					//插入的是链表开头
	first = new_node;
else								//插入到非首个结点的位置
	prev->next = new_node;
	

往链表开头中插入结点：

• 参数1：指向旧链表首结点的指针；
• 参数2：需要存储在新结点的数据。
• 返回：新链表的首地址

struct node *add_to_list(struct node *list, int n)
{
	//创建新结点并存储数据
	struct node *new_node = (struct node*)malloc(sizeof(struct node));
	if(new_node == NULL){
		printf("Error: maloc failed in add_to_list.\n");
		exit(EXIT_FAILURE);					//结束进程
	}
	new_node->value = n;
	
	//结点添加至链表
	new_node->next = list;
	
	return new_node;
}

函数的使用：

first = add_to_list(first, 10);
first = add_to_list(first, 20);

五、链表的搜索

惯用法：

for(p = first; p != NULL; p = p->next){
	...
}

链表搜索函数：

//原始版本：
struct node *search_list(struct node *list, int n)
{
	struct node *p = NULL;
	for(p = list ; p != NULL; p = p->next){
		if(p->value == n) break;
	}
	return p;
}

//修改版1：
struct node *search_list(struct node *list, int n)
{
	for( ; list != NULL; list = list->next){
		if(list->value == n) break;
	}
	return list;					//若没找到,最后的list == NULL
}

• list 是原始链表指针的副本，也没有对其进行间接寻址，因此在函数内修改 list 的值不会造成任何影响。若要在函数内修改原始指针，需要传入指向该指针变量的指针，通过间接寻址的方式修改才能有效。

//修改版2：
struct node *search_list(struct node *list, int n)
{
	for( ; list != NULL && list->value != n; list=list->next)
		;
	return list;
}

//使用while版本：
struct node *search_list(struct node *list, int n)
{
	while(list ！= NULL && list->value != n)
		list = list->next;
	return list;
}

六、从链表中删除结点

链表的优势之一就是可以轻松地删除链表中不需要的结点。

删除结点的步骤：
① 定位需删除的结点；
② 改变前一个结点，使它跳过删除结点，链接到后一个结点上；
③ 释放回收删除结点的内存空间。

由于需要对前一个结点进行修改，因此在定位待删除结点时，也需要存储前一个结点的位置。

共有3种情况：
- 常规情况：目标结点存在且不是链表的首结点
- 特殊情况1：没找到目标结点(不需要删除)
- 特殊情况2：链表首结点就是目标结点

struct node *delete_from_list(struct node *list, int n)
{
	struct node *prev, *cur;
	//定位目标结点
	for(prev=NULL,cur=list; cur!=NULL,cur->value!=n; prev=cur,cur=cur->next)
		;
	if(cur == NULL) return list;					//没找到
	
	//跳过结点
	if(prev == NULL) 								//n在第一个结点
		list = list->next;
	else
		prev->next = cur->next;
	
	//释放结点内存
	free(cur);
	
	return list;
}

七、有序链表

有序链表的结点是有序的，各个结点按该节点中的数据排序。
有序链表的插入更加困难，但搜索会更快。

内容详见下一节。

八、 综合举例：维护零件数据库 (插入/删除/修改/搜索)

要求实现的功能：

• 添加新零件编号、名称和初始的现货数量；若零件已在数据库中，或数据库已满，则显示出错信息
• 给定零件编号，删除该零件的数据；
• 给定零件编号，显示零件信息；
• 给定零件编号，改变现有的零件数量；
• 显示列出数据库中全部信息的表格；
• 终止程序的执行。
  各个功能中，若给定的零件编号非法(不是单个有效整数)，或零件不再数据库中，需要显示出错信息。

由于零件名不一定是连续的字符串，例如 Disk Drive ，而 scanf 遇到空白字符会停止读取，因而必须使用逐字符读取字符串的方法。
需要读取单个数字时，也需要考虑到用户输出非法的问题，也需要创建一个单独的函数来读取。

使用操作符：i (插入)、d (删除)、s (搜索查看)、u (更新数据)、p (全显示)、q (退出)

程序完整代码：

#include <stdio.h>
#include <stdlib.h>					   //malloc函数, free函数
#include <ctype.h>                     //isspace函数

#define NAME_LEN 25                    //零件名最大长度

struct part{
    int number;						   //零件编号
    char name[NAME_LEN + 1];		   //零件名称
    int on_hand;					   //存货数量
    struct part *next;
};

struct part *inventory = NULL;         //链表起始地址, 并初始化

int read_a_number(void);               //读取有效的单个数字
int readline(char *str, int n);        //逐字符读取字符串
struct part *find_part(int number);    //通过零件序号定位结点
void insert(void);          //插入
void delete(void);          //删除
void update(void);          //修改
void search(void);          //单项搜索并查看
void print(void);           //全打印

int main(){

    char code;				//操作码
    for(;;){
        printf("---- i-insert, d-delete, s-search, u-update, p-print, q-qiut ----\n");
        printf("Enter operation code: ");
        scanf(" %c", &code);                    //加空格符,跳过输入的空白字符,否则可能会读取到前一行的换行符
        while(getchar() != '\n')                //保证读取单个字符,清空缓存区,不影响后面的读取
            ;
        switch (code){
            case 'i' : insert(); break;
            case 'd' : delete(); break;
            case 's' : search(); break;
            case 'u' : update(); break;
            case 'p' : print(); break;
            case 'q' : return 0;
            default : printf("Illegal code! Please enter correct code.\n");
        }
        printf("\n\n\n");
    }

    return 0;
}

 /******************************
  *          定位结点           *
  ******************************/
struct part *find_part(int number)
{
    struct part *p;
    for(p = inventory; p != NULL && p->number < number; p = p->next)        //有序链表,使用>=number作为结束条件更省时间
        ;
    if(p != NULL && p->number == number) return p;
    return NULL;
}

/*******************************
 *         读取单个整数         *
 *******************************/
int read_a_number(void)
{
    int number;
    //保证输入的单个整数
    while( !(scanf("%d", &number) && getchar() == '\n') ){
        //无效输入, 清空缓存区
        while( getchar() != '\n')
            ;
        printf("Invalid input, please re-enter a number: ");
    }

    return number;
}

/***********************************
 *         逐字符读取字符串         *
 ***********************************/
int readline(char *str, int n)
{
    int ch, i = 0;              //getchar函数返回int类型
    //跳过空白字符
    while( isspace(ch = getchar()) )
        ;
    //开始读取字符串
    while( ch != '\n' && ch != EOF){
        if(i < n) str[i++] = ch;
        ch = getchar();
    }
    str[i] = 0;
    return i;
}

/***********************************
 *            链表的插入            *
 ***********************************/
void insert(void)
{
    struct part *prev, *cur, *new_node;
    new_node = (struct part*)malloc(sizeof(struct part));
    //判断是否有可用空间
    if(new_node == NULL){
        printf("Datebase is full, cannot add more parts.\n");
        return;
    }

    printf("Enter part number: ");
    new_node->number = read_a_number();

    //需要使用双指针, 因而无法调用find_part函数
    for(prev = NULL, cur = inventory; cur != NULL && cur->number < new_node->number; prev = cur, cur = cur->next)
        ;
    //若零件已存在,释放内存并退出
    if(cur != NULL && cur->number == new_node->number){
        printf("Part already exist.\n");
        free(new_node);
        return;
    }

    printf("Enter part name: ");
    readline(new_node->name, NAME_LEN);               //读取零件名
    printf("Enter quantity on hand: ");
    new_node->on_hand = read_a_number();

    new_node->next = cur;
    if(prev == NULL)
        inventory = new_node;
    else
        prev->next = new_node;

}

/***********************************
 *          链表结点的删除          *
 ***********************************/
void delete(void)
{
    int number;
    printf("Enter part number: ");
    number = read_a_number();

    struct part *prev, *cur;
    for(prev = NULL, cur = inventory; cur != NULL && cur->number < number; prev = cur, cur = cur->next)
        ;
    if(cur != NULL && cur->number == number){
    	//目标结点在链表开头
        if(prev == NULL)
            inventory = cur->next;
        else
            prev->next = cur->next;
        free(cur);
        printf("Part has been deleted.\n");
    }
    //目标结点不存在
    else
        printf("Part not exist, no need to delete.\n");
    
}

/***********************************
 *          链表的数据修改          *
 ***********************************/
void update(void)
{
    int number, change_option, change;
    printf("Enter part number: ");
    number = read_a_number();

    struct part *p;
    p = find_part(number);
    if(p != NULL){
        printf("Change option(1-part name, 2-quantity on hand): ");
        for(;;){
            change_option = read_a_number();
            //更新零件名
            if(change_option == 1){
                printf("Enter a new name: ");
                readline(p->name, NAME_LEN);
                break;
            }
            //更新零件数量
            else if(change_option == 2){
                printf("Enter change in quantity on hand: ");
                change = read_a_number();
                p->on_hand += change;
                break;
            }
            else
                printf("Invalid input, please enter correct number(1 or 2): ");

        }
        
    }
    else
        printf("Part not found.\n");
    
}

/***********************************
 *          链表的搜索查看          *
 ***********************************/
void search(void)
{
    int number;
    printf("Enter part number: ");
    number = read_a_number();

    struct part *p;
    p = find_part(number);
    if(p != NULL){
        printf("Part name: %s\n", p->name);
        printf("Quantity on hand: %d\n", p->on_hand);
    }
    else
        printf("Part not found.\n");
    
}

/***********************************
 *           链表的全打印           *
 ***********************************/
void print(void)
{
    struct part *p;
    printf("Part Number   Part Name                  Quantity on hand\n");
    for(p = inventory; p != NULL; p = p->next){
        printf("%7d       %-25s%11d\n", p->number, p->name, p->on_hand);
        
    }
}