C语言-链表的创建头插法和尾插法（有无头节点）

约定不等于承诺〃 2022-06-09 14:51 225阅读 0赞

### 文章目录 ###

*   *  结构声明
     *  1 头插法（有头节点）
     *  2 头插法（无头节点）
     *  3 尾插法（有头节点）
     *  4 尾插法（无头节点）

## 结构声明 ##

typedef int ElementType;
    
    typedef struct Node { 
    	ElementType data;
    	struct Node *Next;
    } *List;

## 1 头插法（有头节点） ##

/* 建立链表 - 头插法 - 有头节点 +------+ +------+ +------+ +------+ | head | => |node_1| -> |node_2| -> |node_3| -> NULL +------+ +------+ +------+ +------+ \ / +------+ | p | +------+ */
    List HeadCreate(void)
    { 
    	ElementType x; // 保存 Node 中的 data 数据
    	List p; // 临时指针，用于保存声明的节点
    	List head; // 整个链表的头结点;
    	head = (List)malloc(sizeof(struct Node));
    	head->Next = NULL;
    	head->data = 0; // 头节点的 data 域用于保存链表的长度
    	scanf("%d", &x);
    
    	while (x != -1) {  // 当 x 等于 -1 的时候，停止创建链表
    		p = (List)malloc(sizeof(struct Node));
    		p->data = x;
    		p->Next = head->Next;
    		head->Next = p;
    		head->data++; // 链表的长度加 1
    		
    		scanf("%d", &x); // 读取下一个节点的数据
    	}
    	return head;
    }

## 2 头插法（无头节点） ##

/* 建立链表 - 头插法 - 没有头节点 +------+ +------+ +------+ +------+ | head | -> |node_1| -> |node_2| -> |node_3| -> NULL ^ +------+ +------+ +------+ +------+ | +------+ | p | +------+ */
    List HeadCreate(void)
    { 
    	ElementType x; // 保存 Node 中的 data 数据
    	List p;
    	List head;
    	head = NULL;
    	scanf("%d", &x);
    
    	while (x != -1) { 
    		p = (List)malloc(sizeof(struct Node));
    		p->data = x;
    		if (head == NULL) { 	// 若第一次创建节点，则将该点设置为头节点
    			head = p;
    			p->Next = NULL;
    		} else {  // 若不是第一次创建节点，则直接将新节点接到链表头
    			p->Next = head;
    			head = p;
    		}
    		scanf("%d", &x);
    	}
    	return head;
    }

## 3 尾插法（有头节点） ##

/* 创建链表 - 尾插法 - 有头节点 +------+ +------+ +------+ | head | -> |node_1| -> |node_2| ____ +------+ +------+ +------+ | v +------+ +------+ | rear | -> | p | +------+ +------+ */
    List TailCreate(void)
    { 
    	ElementType x; // 保存 Node 中的 data 数据
    	List p;
    	List head; // 头结点
    	List rear; // 因为尾插法需要在尾部插入，所以要有个指针来保存尾的位置
    	head = (List)malloc(sizeof(struct Node));
    	head->Next = NULL;
    	rear = head; // 链表为空，头和尾指向同一个位置
    	scanf("%d", &x);
    
    	while (x != -1) { 
    		p = (List)malloc(sizeof(struct Node));
    		p->data = x;
    		rear->Next = p;
    		rear = p;
    	}
    	rear->Next = NULL; // 链表建立结束后将最后一个节点指向 NULL
    	return head;
    }

## 4 尾插法（无头节点） ##

/* 创建链表 - 尾插法 - 没有头节点 +------+ +------+ +------+ |node_1| -> |node_2| -> |node_3| ____ +------+ +------+ +------+ | v +------+ +------+ | rear | -> | p | +------+ +------+ */
    List TailCreate(void)
    { 
    	ElementType  x;
    	List p;
    	List head;
    	List rear;
    	head = NULL;
    	rear = NULL;
    	scanf(%d, &x);
    
    	while (x != -1) { 
    		p = (List)malloc(sizeof(struct Node));
    		p->data = x;
    		if (head == NULL) {  // 创建链表的第一个节点
    			head = p;
    			rear = p;
    			p->Next = NULL;
    		} else { 
    			rear->Next = p;
    			rear = p;
    		}
    		scanf("%d", &x);
    	}
    	rear->Next = NULL; // 链表建立结束后将最后一个节点指向 NULL（尾插法中不要遗漏）
    	return head;
    }