单链表的建立

C实现头插法和尾插法来构建单链表（不带头结点）

链表的构建事实上也就是不断插⼊节点的过程。⽽节点的插⼊能够分为头插法和尾插法。

//

// main.c

// HeadInsertAndTailInsert

//

// Created by chenyufeng on 16/2/25.

// Copyright © 2016年 chenyufengweb. All rights reserved.

//

/**

* 分别使⽤头插法和尾插法建⽴单链表

*/

#include

#include "stdlib.h"

#include "string.h"

typedef int elemType;

//构造节点

typedef struct ListNode{

int element;

struct ListNode *next;

}Node;

//初始化链表

void initList(Node *pNode){

pNode = NULL;

printf("%s函数运⾏，头结点初始化完毕\n",__FUNCTION__);

}

//打印链表

void printList(Node *pNode){

if (pNode == NULL) {

printf("%s函数运⾏，链表为空，打印失败\n",__FUNCTION__);

}else{

while (pNode != NULL) {

printf("%d ",pNode->element);

pNode = pNode->next;

}

printf("\n");

}

}

//头插法

Node *HeadInsert(Node *pNode){

Node *pInsert;

pInsert = (Node*)malloc(sizeof(Node));

if (pInsert == NULL) {

printf("%s函数运⾏。内存分配失败，建⽴链表失败\n",__FUNCTION__);

return NULL;

实验一:线性表的基本操作

【实验目的】

学习掌握线性表的顺序存储结构、链式存储结构的设计与操作.对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】

1. 顺序表的实践

1） 建立4个元素的顺序表s=sqlist［］=｛1，2，3，4，5}，实现顺序表建立的基本操作.

2) 在sqlist ［]=｛1，2，3,4,5}的元素4和5之间插入一个元素9,实现顺序表插入的基本操作。

3) 在sqlist ［］=｛1,2，3，4，9，5}中删除指定位置(i=5）上的元素9，实现顺序表的删除的基本操作。

2. 单链表的实践

3. 1) 建立一个包括头结点和4个结点的(5，4，2，1）的单链表，实现单链表建立的基本操作。

2） 将该单链表的所有元素显示出来。

3) 在已建好的单链表中的指定位置（i=3)插入一个结点3，实现单链表插入的基本操作。

4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2)删除一个结点，实现单链表删除的基本操作。

5) 实现单链表的求表长操作.

【实验步骤】

1.打开VC++.

2.建立工程:点File->New,选Project标签，在列表中选Win32 Console

Application，再在右边的框里为工程起好名字，选好路径，点OK-〉finish。至此工程建立完毕.

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source

File.给文件起好名字,选好路径，点OK。至此一个源文件就被添加到了刚创建的工程之中.

4．写好代码

5．编译－＞链接－＞调试

1、#include "stdio。h”

＃include "malloc.h”

#define OK 1

＃define OVERFLOW -2

＃define ERROR 0

#define LIST_INIT_SIZE 100

实验一 链表的建立及基本操作方法实现

一、【实验目的】

1、理解和掌握单链表的类型定义方法和结点生成方法。

2、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。

3、掌握单链表的查找（按序号）算法。

4、掌握单链表的插入、删除算法。

二、【实验内容】

1、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。

2、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。

3、将测试数据结果用截图的方式粘贴在程序代码后面。

重点和难点：

尾插法和头插法建立单链表的区别。

建立带头结点和无头结点单链表的区别。

带头结点和无头结点单链表元素显示方法的区别

三、【算法思想】

1) 利用头插法和尾插法建立一个无头结点单链表

链表无头结点，则在创建链表时，初始化链表指针L=NULL。

当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给L,新结点next指向空，即L=p,p->next=NULL，若表中已经有元素了，则将新结点的next指向首结点，然后将新结点赋给L即（p->next=L,L=p）。

当用尾插法插入元素时，首先设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer和头指针一样即tailPointer=L。插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给L即L=p，若不为空，else将最后一个元素的next指向新结点即tailPointer->next=p，然后跳出这个if,else语句，将新结点next指向空，并且将tailPointer指向新结点即p->next=NULL,tailPointer=p。

2) 利用头插法和尾插法建立一个有头结点单链表

链表有头结点，则在创建链表时，初始化链表指针L->next = NULL。与无头结点区别在于，判断链表为空是根据L->next是否为空。

电脑知识与技术　．．．．．．数据库与信息管理．　

Ｃ中用指针动态建立单链表的几种方法　

廖远来　

（河源职业技术学院信息技术系，广东河源５１７０００）　

摘要：通常用数组可以实现线性表的顺序存储，但是，数组事先要定义固定的长度，并且所分配的存储空间是连续的。这样一来，就不　

能达到真正意义上的动态分配存储空间以及充分利用存储空间的目的；另外，用数组不利于实现线性表中结点的动态增加与删除。而用　链袁则可以弥补以上不足。本文主要以建立学生信息链表为例，分别介绍无头结点、有头结点单链表的逆序建立和顺序建立过程以及算　

法实现。　关键词：指针：链表：单链表；动态建立　

中图分类号：ＴＰ３１１　文献标识码：Ａ　文章编号：１００９－３０４４（２００６）２３－００２２－０２　Ｓｅｖｅｒａｌ　Ｍｅｔｈｏｄｓ　ｏｆ　Ｄｙｎａｍｉｃ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　Ｓｏｌｅ　Ｃｈａｉｎ　Ｌｉｓｔ　ｂｙ　Ｎｅｅｄｌｅ　ｗｉｔｈｉｎ　Ｃ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇｕａｇｅ　

ＬＩＡＯ　Ｙｕａｎｇ——ｌａｉ　（Ｈｅｙｕａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ，Ｈｅｙｕａｎ　５１７０００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｏｒｄｉｎａｒｉｌｙ，ｏｒｄｅｒ　ｓｔｏｒａｇｅ　ｏｆ　ｌｉｎｅａｒ　ｔａｂｌｅｓ　ｃａｎ　ｂｅ　ｒｅａｌｉｚｅｄ　ｔｈｒｏｕｇｈ　ａｒｒａｙｓ．Ｈｏｗｅｖｅｒ，ｅａｃｈ　ａｒｒａｙ　ｍｕｓｔ　ｐｒｅｖｉｏｕｓｌｙ　ｂｅ　ａｓｓｉｇｎｅｄ　ｇｉｖｅｎ　

ｌｅｎｇｔｈ　ａｎｄ　ｔｈｅ　ｓｔｏｒａｇｅ　ｓｐａｃｅｓ　ｄｉｓｔｒｉｂｕｔｅｄ　ａｒｅ　ｓｕｃｃｅ￣ｉｖｅ．Ａｓ，ｏｆ　ｃｏｕｍｅ，ｃａｎ　ｔ　ｆｕｌｌｙ　ｒｅａｃｈ　ｔｈｅ　ａｉｍｓ　ｏｆ　ｄｙｎａｍｉｃ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｓｔｏｒａｇｅ　ｓｐａｃｅｓ　ａｎｄ　ｃｏｍｐｌｅｔｅｌｙ　ｕｔｉｌｉｚｅ　ｔｈｅｍ．Ｍｏｒｅｏｖｅｒ，ｉｔ　ｓ　ｎｏｔ　ｉｎ　ｆａｖｏｒ　ｏｆ　ｒｅａｌｉｚｉｎｇ　ｔｈｅ　ｄｙｎａｍｉｃ　ａｄｄｉｎｇ　ａｎｄ　ｄｅｌｅｔｉｏｎ　ｏｆ　ｎｏｄｅ　ｉｎ　ｌｉｎｅａｒ　ｔａｂｌｅｓ　ｂｙ　ｕｓｉｎｇ　ａｒｒａｙｓ．Ｉｎ—