《数据结构》-头插法建立单链表

#include "stdio.h"#include "stdlib.h"typedef struct List{int data;struct List *next; //指针域}List;void HeadCreatList (List *L) //头插法建立链表{List *s;L->next=NULL;for (int i=0;i<10;i++){s=(struct List*)malloc(sizeof(struct List));s->data=i;s->next=L->next; //将L指向的地址赋值给S;L->next=s;}}void TailCreatList(List *L) //尾插法建立链表{List *s,*r;r=L;for (int i=0;i<10;i++){s=(struct List*)malloc(sizeof(struct List));s->data=i;r->next=s;r=s;}r->next=NULL;}void DisPlay(List *L){List *p=L->next;while(p!=NULL){printf ("%d ",p->data);p=p->next;}printf("\n");}int main (){List *L1,*L2;L1=(struct List*)malloc(sizeof(struct List));L2=(struct List*)malloc(sizeof(struct List)); HeadCreatList(L1);DisPlay(L1);TailCreatList(L2);DisPlay(L2);}//头插法创建链表#include <stdio.h>#include <stdlib.h>struct node{int data;struct node * next;};//建立只含头结点的空链表struct node * create_list(){struct node * head = NULL;head = (struct node *)malloc(sizeof(struct node));if (NULL == head){printf("memory out of use/n");return NULL;}head->next = NULL;head->data = 0;return head;}//头插法建立链表int insert_form_head(struct node * head, int num){struct node * head_t = head->next;struct node * new_node = NULL;new_node = (struct node *)malloc(sizeof(struct node));if (NULL == new_node){printf("memory out of use/n");return -1;}//将新结点插入到链表的最后new_node->data = num;new_node->next = head_t;head->next = new_node;return 0;}//打印链表int show_list(struct node * head){struct node * temp;temp = head->next;while(temp){printf("%d/n",temp->data);temp = temp->next;}return 0;}// 按值删除结点，头结点不被删除int delete_node(struct node *head, int data){//head_t 保存要删除结点的上一个结点struct node * head_t = head;struct node * temp = NULL;if (head == NULL){printf("delete node from empty list!/n");return -1;}//查找删除的结点的前一个结点//如果此处查找的是删除的结点，则需要另加一个指针保存删除结点的前一个指针while(NULL != head_t->next){if (data == head_t->next->data)break;head_t = head_t->next;}//如果要删除的结点不存在，直接返回if (NULL==head_t->next){printf("node not found/n");return -1;}//删除操作temp = head_t->next;head_t->next = head_t->next->next;free(temp);return 0;}void main(int argc, char* argv[]){struct node * head;head = create_list();if (NULL == head)printf("create_list error/n");insert_form_head(head,123);insert_form_head(head,456);show_list(head);printf("delete once!/n");delete_node(head,123);show_list(head);printf("delete second!/n");delete_node(head,456);show_list(head);delete_node(head,0);show_list(head);}/*//尾插法创建链表#include<stdio.h>#include<stdlib.h>struct Node{int data;struct Node * next;};//建立只含头结点的空链表struct Node * create_list(){struct Node * head = NULL;head = (struct Node *)malloc(sizeof(struct Node));if (NULL == head){printf("memory out of use/n");return NULL;}head->next = NULL;head->data = 0;return head;//尾插法建立链表int insert_form_tail(struct Node * head, int num){struct Node * temp = head;struct Node * new_node = NULL;new_node = (struct Node *)malloc(sizeof(struct Node));if (NULL == new_node){printf("memory out of use/n");return -1;}//寻找尾结点while (temp->next != NULL){temp = temp->next;}//将新结点插入到链表的最后new_node->data = num;new_node->next = NULL;temp->next = new_node;return 0;}//打印链表int show_list(struct Node * head){struct Node * temp;temp = head->next;while(temp){printf("%d/n",temp->data);temp = temp->next;}return 0;}void main(int argc, char* argv[]){struct Node * head;head = create_list();if (NULL == head)printf("create_list error/n");insert_form_tail(head,123);insert_form_tail(head,456);show_list(head);*/。

目录1 选题背景 (1)2 方案与论证 (1)2。

1 链表的概念和作用 (1)2。

3 算法的设计思想 (2)2。

4 相关图例 (3)2.4.1 单链表的结点结构 (3)2.4。

2 算法流程图 (3)3 实验结果 (4)3.1 链表的建立 (4)3.2 单链表的插入 (4)3.3 单链表的输出 (5)3.4 查找元素 (5)3。

5 单链表的删除 (5)3。

6 显示链表中的元素个数（计数) (5)4 结果分析 (6)4。

1 单链表的结构 (6)4。

2 单链表的操作特点 (6)4。

2。

1 顺链操作技术 (6)4.2。

2 指针保留技术 (6)4。

3 链表处理中的相关技术 (6)5 设计体会及今后的改进意见 (6)参考文献 (8)附录代码： (8)1 选题背景陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代-—--信息时代,形成一个新产业-—-—信息产业,产生一个新科学—---计算机科学与技术，开创一种新的科研方法-—--计算方法，开辟一种新文化---—计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。

数据结构和算法是计算机求解问题过程的两大基石。

著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”.计算机科学就是“一种关于信息结构转换的科学”.信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。

2 方案与论证2。

1 链表的概念和作用链表是一种链式存储结构，链表属于线性表,采用链式存储结构，也是常用的动态存储方法。

链表中的数据是以结点来表示的，每个结点的构成:元素（数据元素的映象） + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

以“结点的序列”表示线性表称作线性链表（单链表)单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。

描述单链表的创建过程
单链表是一种常用的线性数据结构，它由一系列节点组成，每个节点包含数据元素和一个指向下一个节点的指针。

创建单链表的过程可以分为以下几个步骤：
定义节点结构：首先，需要定义节点的结构。

每个节点通常包含数据元素和一个指向下一个节点的指针。

在许多编程语言中，可以使用结构体或类来定义节点。

例如，在C++中，可以定义一个结构体来表示节点：
cpp
struct Node {
int data; // 数据元素
Node* next; // 指向下一个节点的指针
};
创建第一个节点：创建一个头节点，它是单链表的第一个节点。

头节点通常用于存储指向第一个节点的指针，以及执行一些额外的操作，如插入和删除。

头节点可以静态创建或动态创建。

插入节点：在单链表中插入新的节点涉及到在链表中找到正确的位置并将新节点添加到该位置。

有两种常见的插入方法：在头部插入和在尾部插入。

在头部插入时，新节点成为链表的第一个节点；在尾部插入时，新节点成为链表的最后一个节点。

删除节点：从单链表中删除节点需要找到要删除的节点，并将其从链表中移除。

这通常涉及到更新被删除节点的上一个节点的指针，使其指向被删除节点的下一个节点。

c语言单链表头插法实现链表逆置链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在C语言中，我们可以使用单链表来实现各种操作，如插入、删除和查找等。

本文将介绍如何使用头插法实现链表的逆置。

首先，我们需要定义一个链表节点的结构体，包含数据和指向下一个节点的指针。

代码如下：```ctypedef struct Node {int data;struct Node* next;} Node;```接下来，我们需要实现链表的创建和逆置函数。

首先，创建一个空链表，并将头节点指针指向NULL。

代码如下：```cNode* createList() {Node* head = NULL;return head;}```然后，我们可以实现链表的插入函数，使用头插法将新节点插入到链表的头部。

代码如下：```cNode* insertNode(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head;head = newNode;return head;}```接下来，我们可以实现链表的逆置函数，通过遍历链表，将每个节点插入到头部，从而实现链表的逆置。

代码如下：```cNode* reverseList(Node* head) {Node* newHead = NULL;Node* temp = NULL;while (head != NULL) {temp = head->next;head->next = newHead;newHead = head;head = temp;}return newHead;}```最后，我们可以编写主函数，测试链表的逆置功能。

代码如下：```cint main() {Node* head = createList();head = insertNode(head, 1);head = insertNode(head, 2);head = insertNode(head, 3);head = insertNode(head, 4);head = insertNode(head, 5);printf("原链表：");Node* temp = head;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}printf("\n");head = reverseList(head);printf("逆置后的链表：");temp = head;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}printf("\n");return 0;}```运行以上代码，输出结果如下：```原链表：5 4 3 2 1逆置后的链表：1 2 3 4 5```通过以上代码，我们成功地使用C语言的单链表头插法实现了链表的逆置。

单链表的头插法和尾插法c语⾔实现/*单链表的头插法和尾插法c语⾔实现*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define SIZE 100/*简单的定义⼀个链表节点的数据单元*/typedef struct student_t{int num;char name[SIZE];struct student_t* pNext;}studentList, *pStudentList;/*定义⼀个全局的静态的链表头节点指针*/static pStudentList g_pstStudentList = NULL;/*创建⼀个学⽣信息的链表节点*/pStudentList createaOneStudentListNode(){pStudentList pNewNode = NULL;pNewNode = (pStudentList)malloc(sizeof(studentList));return pNewNode;}/*在链表头插⼊数据节点*/int addOneStudentToListHead(int num, char* name){pStudentList pNewNode = NULL;int result = 0;if ((num < 0) || (name == NULL)){result = -1;printf("error inoput parameter!\n");return result;}pNewNode = createaOneStudentListNode();pNewNode->num = num;memcpy(pNewNode->name, name, strlen(name));pNewNode->pNext = g_pstStudentList;g_pstStudentList = pNewNode;return result;}/*在链表尾部插⼊数据节点*/int addOneStudentToListTail(int num, char* name){pStudentList pTempHead = NULL;pStudentList pTailNode = NULL;pStudentList pNewNode = NULL;int result = 0;if ((num < 0) || (name == NULL)){result = -1;printf("error input parameter!\n");return result;}pTempHead = g_pstStudentList;while(pTempHead){if (pTempHead->pNext == NULL){pTailNode = pTempHead;}pTempHead = pTempHead->pNext;}pNewNode = createaOneStudentListNode();pNewNode->num = num;memcpy(pNewNode->name, name, strlen(name));pNewNode->pNext = NULL;pTailNode->pNext = pNewNode;return result;}/*输出整个链表中的学号信息，检查插⼊的是否正确，插⼊时没有考虑是否有相同学号*/ void printList(){pStudentList pTempHead = NULL;pTempHead = g_pstStudentList;while(pTempHead){printf("studnet num = %d\n", pTempHead->num);pTempHead = pTempHead->pNext;}}/*释放整个链表的资源*/void freeList(){pStudentList pTempHead = NULL;pStudentList pFree = NULL;int i = 0;pTempHead = g_pstStudentList;pFree = g_pstStudentList;while(pTempHead){pFree = pTempHead;printf("free studnet num = %d\n", pTempHead->num);pTempHead = pTempHead->pNext;if (pFree != NULL){printf("i = %d\n", i);/*测试是否正确释放资源*/free(pFree);}++i;}}int main(){/*构建头节点*/char* cName = "allan";g_pstStudentList = createaOneStudentListNode();g_pstStudentList->num = 0;memcpy(g_pstStudentList->name, cName, strlen(cName));g_pstStudentList->pNext = NULL;/*使⽤尾插法插⼊数据*/char* cName1 = "allan1";addOneStudentToListTail(1,cName1);/*使⽤尾插法插⼊数据*/char* cName2 = "allan2";addOneStudentToListTail(2,cName2);/*使⽤头插法插⼊数据*/char* cName3 = "allan3";addOneStudentToListHead(3,cName3);/*输出当前链表中存储的学号，没有考虑学号的唯⼀性，假设输⼊的都是不同数字*/ printList();/*使⽤完资源后进⾏释放资源，防⽌内存泄漏*/freeList();return 0;}使⽤VS2008运⾏结果如下图所⽰：。

带头结点的单链表的插入算法在计算机科学中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表有多种形式，其中一种是带头结点的单链表。

带头结点的单链表是在普通的单链表的基础上添加了一个头结点，头结点不存储数据，只用来标识链表的开始。

带头结点的单链表的插入算法是指在链表中插入新的节点的操作。

下面将详细介绍带头结点的单链表的插入算法。

带头结点的单链表的插入算法包括以下几个步骤：1. 首先，创建一个新的节点，该节点包含要插入的数据。

2. 然后，找到插入位置的前一个节点，可以从头结点开始遍历链表，直到找到插入位置的前一个节点为止。

3. 接下来，将新节点的指针指向插入位置的后一个节点。

4. 最后，将插入位置的前一个节点的指针指向新节点。

下面通过一个具体的例子来说明带头结点的单链表的插入算法。

假设有一个带头结点的单链表，初始状态下只有一个头结点。

现在要在链表中插入一个新节点，该节点的数据为10。

1. 首先，创建一个新的节点，节点的数据为10。

2. 然后，从头结点开始遍历链表，直到找到插入位置的前一个节点。

在这个例子中，由于链表只有一个头结点，所以插入位置的前一个节点就是头结点。

3. 接下来，将新节点的指针指向插入位置的后一个节点。

由于链表只有一个头结点，所以插入位置的后一个节点为空。

4. 最后，将插入位置的前一个节点的指针指向新节点。

在这个例子中，将头结点的指针指向新节点。

经过以上操作，新节点就成功地插入到了链表中。

带头结点的单链表的插入算法的时间复杂度为O(n)，其中n为链表的长度。

这是因为在最坏情况下，需要遍历整个链表找到插入位置的前一个节点。

带头结点的单链表的插入算法在实际应用中有着广泛的应用。

例如，在图算法中，可以使用带头结点的单链表来表示图的邻接表。

插入节点的操作可以用来添加新的边或顶点。

带头结点的单链表的插入算法是一种常见的数据操作，它可以在链表中插入新的节点。

实验一线性表一、实验目的线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。

通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。

（1）掌握线性表的顺序存储结构；（2）验证顺序表及其基本操作的实现；（3）掌握数据结构及算法的程序实现的基本方法。

（4）掌握线性表的链接存储结构；（5）验证单链表及其基本操作的实现；（6）进一步掌握数据结构及算法的程序实现的基本方法。

二、实验示例学习——顺序表操作实验要求：（1）建立含有若干个元素的顺序表；（2）对已建立的顺序表实现插入、删除、查找等基本操作。

实现提示：首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

const int MaxSize=10;template <class T> //定义模板类SeqListclass SeqList{public:SeqList( ){length=0;} //无参构造函数SeqList(T a[ ], int n);//有参构造函数void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素T Delete(int i); //删除线性表的第i个元素int Locate(T x ); //按值查找，求线性表中值为x的元素序号void PrintList( ); //遍历线性表，按序号依次输出各元素private:T data[MaxSize]; //存放数据元素的数组int length; //线性表的长度};其次，建立含有n个数据元素的顺序表，即设计构造函数。

算法如下：template <class T>SeqList:: SeqList(T a[ ], int n){if (n>MaxSize) throw "参数非法";for (i=0; i<n; i++)data[i]=a[i];length=n;}最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。

2016级数据结构实验报告实验名称：实验一线性表——题目1学生姓名：李文超班级：2015661131班内序号：15学号：2015522147日期：2016年11月13日1.实验要求实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2.程序分析2.1 存储结构单链表的存储：（1）链表用一组任意的存储单元来存放线性表的结点。

这组存储单元既可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置。

（2）链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。

结点结构┌──┬──┐ data 域---存放结点值的数据域│data │next │ next 域---存放结点的直接后继的地址的指针域└──┴──┘单链表在内存中的存储示意地址 内存单元1000H头指针 1020H1080H10C0H2.2 关键算法分析1、关键算法：（1）头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。

将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s（2）尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s（3）遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述a: If front->next==NULL①Throw ”an empty list ”②Node<T>* temp=front->next;b:while(temp->next)c:cout<<temp->data<<" ";d:temp=temp->next;(4) 获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return ne: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述a:if ront->next==NULLb:Node<T>* temp=front->next;c:while(temp->next)d:temp=temp->next;（5）析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front（6）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1①：p指向下一个结点②：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)①:p=p->next②:j++c:if(!p) throw ”error”d:return p（7）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点①：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)①: if(p->next==x) return jp=p->nextj++c:return “error”（8）插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x（9）删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q2、代码详细分析（插入）：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) { p=p->next;}（2）新建一个节点s，把p的数据赋给s：s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示xp->datas3、关键算法的时间复杂度：O（1)3.程序运行结果1. 流程图：2、结果截图3.测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。