C语言__链表相关知识

温州大学瓯江学院

程序设计基础 实验报告

实验名称： 综合实验二（1）：链表的应用

班 级： 14计算机 姓 名： 学 号：

实验地点： 7-714 日 期：

一、实验目的：

[1]理解单向链表的概念，理解链表和数组的区别；

[2]掌握动态开辟和释放函数；

[3]掌握结构体链表的创建方法；

[4]掌握结构体链表的遍历方法；

[5]掌握结构体链表的节点插入方法和节点删除方法；

[6]掌握结构体链表的排序方法；

[7]掌握结构体链表做函数传递方法；

[8]进一步熟悉模块化编程思想和原则，熟悉应用程序的基本开发过程。

二、实验环境：

CFree集成环境

三、实验内容、要求及实验步骤：

参考教材的例子8.13，编写函数完成单向动态链表的建立、输出各节点的值、插入或删除一个节点的功能。具体要求如下：

（1）调用mycreat函数建立一个单向动态链表，要求从小到大从键盘输入整数值；

（2）调用myinsert函数在已建立的链表中插入一个节点，新节点插入后，链表依旧有序；

（3）调用mydelete函数删除链表中值为m的节点。

（4）调用myprint输出链表中各节点的值。

最后，完成实验后，将实验报告命名为：学号姓名综合实验3.doc（如14219111201朱彦文综合实验3.doc），然后发到邮箱：zongda_c@，邮件标题也需命名为：学号姓名综合实验3。

四、实验结果与分析（含程序、数据记录及分析和实验总结等）：

#include

#include

struct lst

{ int num;

struct lst *next;

};

typedef struct lst LST;

LST *mycreat()

{

int m=0;

LST *head=NULL,*p=NULL,*q=NULL;

head=(LST*)malloc(sizeof(LST));

c语言链表解析

编程思想：

链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为next指针。最后一个单元的next指针指向NULL；该值由C定义并且不能与其它指针混淆。ANSI C规定NULL为零。

指针变量是包含存储另外某个数据的地址的变量。因此，如果P被声明为指向一个结构的指针，那么存储在P中的值就被解释为内存中的一个位置，在该位置能够找到一个结构。该结构的一个域可以通过P->FileName访问，其中FileName是我们要考察的域的名字。如图1所示，这个表含有五个结构，恰好在内存中分配给它们的位置分别是1000，800,712,992和692。第一个结构的指针含有值800，它提供了第二个结构所在的位置。其余每个结构也都有一个指针用于类似的目的。当然，为了访问该表，我们需要知道在哪里能够找到第一个单元。

图1

为了执行打印表PrinList（L）或查找表Find（L，key），只要将一个指针传递到该表的第一个元素，然后用一些Next指针穿越该表即可。

删除命令可以通过修改一个指针来实现。图2给出在原表中删除第三个元素的结果。

图2

插入命令需要使用一次malloc调用从系统得到一个新单元并在此后执行两次指针调整。想法通过图3给出，其中虚线表示原来的指针。

图3 程序设计：

上面的描述实际上足以使每一部分都能正常工作，但还是有几处地方可能会出问题：

1、并不存在从所给定义出发在表的前面插入元素的真正显性的方法。

2、从表的前面实行删除是一个特殊情况，因为它改变了表的起始端；编程的疏忽将会造成表的丢失。

3、在执行删除命令时，要求我们记住被删除元素前面的表元。

事实上，稍作一个简单的变化就能够解决所有这三个问题。做一个标志节点——表头（header）。图4表示一个带头头结点的链表。

[转载整理]C语⾔链表实例

C语⾔链表有单链表、双向链表、循环链表。单链表由数据域和指针域组成，数据域存放数据，指针域存放该数据类型的指针便于找到

下⼀个节点。双链表则含有头指针域、数据域和尾指针域，域单链表不同，双链表可以从后⼀个节点找到前⼀个节点，⼆单链表则不⾏。循

环链表就是在单链表的基础上，将头结点的地址指针存放在最后⼀个节点的指针域⾥以，此形成循环。此外还有双向循环链表，它同时具有

双向链表和循环链表的功能。

单链表如：

链表节点的数据结构定义

struct node

{

int num;

struct node *p;

} ;

在此链表节点的定义中，除⼀个整型的成员外，成员p是指向与节点类型完全相同的指针。

※在链表节点的数据结构中，⾮常特殊的⼀点就是结构体内的指针域的数据类型使⽤了未定义成功的数据类型。这是在C中唯⼀规定可以先使⽤后定

义的数据结构。

链表实例代码：

1 // 原⽂地址 /wireless-dragon/p/5170565.html

2 #include

3 #include

4 #include

5

6 typedef int elemType;//定义存⼊的数据的类型可以是int char

7

8 typedef struct NODE{ //定义链表的结构类型

9 elemType element;

10 struct NODE *next;

11 }Node;

12

13 /************************************************************************/

14 /* 以下是关于线性表链接存储（单链表）操作的19种算法 */

15

16 /* 1.初始化线性表，即置单链表的表头指针为空 */

17 /* 2.创建线性表，此函数输⼊负数终⽌读取数据*/

#include 〈stdio.h>

＃include

＃include 〈stdlib.h>

/＊

数据结构C语言版 线性表的单链表存储结构表示和实现

P28—31

编译环境：Dev-C++ 4。9。9。2

日期：2011年2月10日

＊/

typedef int ElemType;

// 线性表的单链表存储结构

typedef struct LNode

{

ElemType data; //数据域

struct LNode *next； //指针域

}LNode, ＊LinkList；

// typedef struct LNode *LinkList； // 另一种定义LinkList的方法

// 构造一个空的线性表L

int InitList（LinkList ＊L)

{

/＊

产生头结点L，并使L指向此头结点,头节点的数据域为空，不放数据的。

void ＊ malloc(size_t)

这里对返回值进行强制类型转换了,返回值是指向空类型的指针类型.

＊/

（＊L） = (LinkList）malloc（ sizeof（struct LNode) ）;

if( ！(＊L） )

exit（0）； // 存储分配失败

(＊L)-〉next = NULL； // 指针域为空

return 1；

}

// 销毁线性表L,将包括头结点在内的所有元素释放其存储空间。

int DestroyList（LinkList ＊L）

｛

LinkList q;

// 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放

while（ ＊L )

｛

q = (*L)—〉next;

free（ ＊L ）； //释放

*L = q;

}

return 1；

｝ /*

将L重置为空表,即将链表中除头结点外的所有元素释放其存