链表基本操作

链表操作图书管理基本业务包括：1、对一种书的采编入库（类别、书名、作者、出版社、ISBN（唯一）、价格、数量）。

2、对一种书进行搜索（类别、ISBN、书名、作者）若有多个结果则同时显示出来。

3、对一种书进行清除库存（通过ISBN）。

4、对一种书实现借阅和归还，同时可以查看该学生借阅了几本书。

基本要求：采编入库：新购一种书，登记入册，若库存中已经有了，则总量增加。

（所有项均用英文单词和数字输入）例如入库某种书：Literature，Old Man and the Sea，Hemingway，Tsinghua University Press，978-7-5011-6964-1，35.6，10清除库存：某种书报损或无效了，将它从库存中删除（所有项都删除）。

借阅：如果一种书现存量大于0，则借出去，并登记借阅者的图书证号（自己定义6位数字字符串）。

通过对图书证号的查询，可以知道该学生已经借阅了几本书，并显示书名。

归还：注销对借阅者的登记，改变该书的现存量。

实现提示：1.1图书表可以采用链式或顺序存储结构实现。

图书的顺序表结构：typedef struct Book{char type[30]; //图书类别（文学、期刊、英语…..）char BookName[50]; //图书名称char Author[20]; //作者char Press[50]; //出版社char ISBN[20]; //ISBN编号（每一类书都有唯一编号，如：978-7-5011-6964-1）float Price; //图书价格int Number; //入库数量}Book;typedef struct BList{Book *elem;int length; //当前图书种类数量int listsize; //初始时可存放图书长度}BList;图书的链表结构：typedef struct Book{char BookName[50];char Author[20];char Press[50];char ISBN[20];float Price;int Number;}Book;typedef struct LNode{Book data;Struct LNode *next;}LNode,*LinkList;1.2、图书的入库则是顺序表或链表的插入操作（可以插入到最后一个位置）。

10）调用头插法的函数，分别输入10,20，分别回车：
11）调用尾插法的函数，分别输入30,40
12）查找单链表的第四个元素：
13）主函数中传入参数，删除单链表的第一个结点：
14）主函数传入参数，删除第0个未位置的元素，程序报错：
15）最后，输出单链表中的元素：
return 0;
}
6）编译，连接，运行源代码：
7）输入8，回车，并输入8个数，用空格分隔开，根据输出信息，可以看出，链表已经拆分为两个
五、实验总结
1.单链表采用的是数据+指针的表示形式，指针域总是指向下一个结
点（结构体）的地址，因此，在内存中的地址空间可以是不连续的，操作比顺序存储更加的方便
2.单链表使用时，需要用malloc函数申请地址空间，最后，删除元
素时，使用free函数释放空间。

c链表库函数全文共四篇示例，供读者参考第一篇示例：C语言是一种广泛应用于系统编程的高级语言，而链表（Linked List）是C语言中常用的数据结构之一。

在C语言中，链表并不像数组一样有现成的库函数可以直接调用，需要通过自定义函数来实现链表的操作。

为了方便使用链表，不少开发者封装了链表操作的库函数，提供了一些常用的链表操作接口，以供开发者使用。

本文将介绍一些常见的C链表库函数及其用法。

一、链表的概念及基本操作链表是一种线性表的存储结构，由若干节点（Node）组成，每个节点包含数据域和指针域。

数据域用于存放数据，指针域用于指向下一个节点。

链表的最后一个节点指针域为空（NULL），表示链表的末尾。

常见的链表操作包括创建链表、插入节点、删除节点、遍历链表、查找节点等。

下面我们来看看C语言中常用的链表库函数。

二、常见的C链表库函数1. 创建链表在C语言中，创建链表的函数通常包括初始化链表头节点和链表节点的操作。

```#include <stdio.h>#include <stdlib.h>//定义链表节点typedef struct node {int data;struct node* next;} Node;2. 插入节点插入节点是链表操作中的重要操作，可以在链表的任意位置插入新节点。

常见的插入方式包括头部插入和尾部插入。

```//头部插入节点void insertNodeAtHead(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head->next;head->next = newNode;}以上是常见的C链表库函数，这些函数可以帮助我们更方便地操作链表。

在实际开发中，可以根据需要自定义更多的链表操作函数，以满足具体的需求。

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：InitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

最坏是O(n),即从头查找p之前的结点,然后删除p所指结点LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针时间复杂度O(n)代码：/*Project: single linkeed list (数据结构单链表)Date: 2018/09/14Author: Frank YuInitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

单向链表单向链表的基本操作,创建一个由6个节点组成的单向链表，显示链表中每个节点的数据，并且做增加、删除、查找节点以及计算单链表的长度等处理。

➢需求分析：1.功能（1）用尾插法创建一带头结点的由6个节点组成的单向链表：从键盘读入一组整数，作为单链表中的元素，输入完第6个结点后结束;将创建好的单链表元素依次输出到屏幕上。

（2）显示链表中每个节点的数据（3）从键盘输入一个数,查找在以上创建的单链表中是否存在该数；如果存在,显示它的位置，即第几个元素;如果不存在，给出相应提示如“No found node!”。

（4）在上述的单链表中的指定位置插入指定数据，并输出单链表中所有数据。

(5）删除上述单链表中指定位置的结点，并输出单链表中所有数据。

(6）求单链表的长度并输出.2．输入要求先输入单链表中结点个数n,再输入单链表中所有数据，在单链表中需查找的数据，需插入的数据元素的位置、值，要删除的数据元素的位置。

3。

测试数据单链表中所有数据：12，23,56，21，8，10在单链表中需查找的数据：56；24插入的数据元素的位置、值：1，28；7,28；0，28要删除的数据元素的位置:6➢概要设计：1.算法思想：由于在操作过程中要进行插入、删除等操作，为运算方便，选用带头结点的单链表作数据元素的存储结构.对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。

2.数据结构：单链表结点类型:typedef struct Liistnode ｛int data；struct Listnode *next;｝NODE;3.模块划分：a)用尾插法建立带头结点的单链表＊CreateList函数；b)显示链表中每个结点的数据PrintList函数;c)从键盘输入一个数，查找单链表中是否存在该数FoundList函数；d)在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList函数;e)删除单链表中指定位置的结点并输出单链表中所有数据DeleteList函数；f)计算单链表的长度并在屏幕上输出LengthList函数;g)主函数main()，功能是给出测试数据值，建立测试数据值的带头结点的单链表,调用PrintList函数、FoundList函数、InsertList函数、DeleteList函数、LengthList函数实现问题要求。

实验二单链表基本操作一实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。

2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。

二实验要求1．预习C语言中结构体的定义与基本操作方法。

2．对单链表的每个基本操作用单独的函数实现。

3．编写完整程序完成下面的实验内容并上机运行。

4．整理并上交实验报告。

三实验内容1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。

(2)在La中第i个元素之前插入一个新结点。

(3)删除La中的第i个元素结点。

(4)在La中查找某结点并返回其位置。

(5)打印输出La中的结点元素值。

2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。

依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。

3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。

（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。

）四思考与提高1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。

(2)在La中第i个元素之前插入一个新结点。

(3)删除La中的第i个元素结点。

(4)在La中查找某结点并返回其位置。

(5)打印输出La中的结点元素值。

#include<stdio.h>#include<stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;//定义存储结构typedef struct Lnode{int data; /*每个元素数据信息*/struct Lnode *next; /*存放后继元素的地址*/} LNode,*LinkList;int main(){void Create_L(LinkList &L,int n);void Print_L(LinkList L);Status ListInsert_L(LinkList &L,int i,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);Status Find_L(LinkList L,int e);LinkList La;//创建单链表Laint n;printf("请输入链表La中的元素个数:\n");scanf("%d",&n);Create_L(La,n);//初始化单链表printf("现在La中的元素为:\n");Print_L(La);printf("-------------------------------------\n\n");printf("现在准备插入元素，请输入插入位置及所插入元素的值\n");int i,e;scanf("%d %d",&i,&e);ListInsert_L(La,i,e);printf("插入后La中的元素为:\n");Print_L(La);printf("-------------------------------------\n\n");printf("现在准备删除元素，请输入删除位置\n");scanf("%d",&i);ListDelete_L(La,i,e);printf("删除后La中的元素为:\n");Print_L(La);printf("-------------------------------------\n\n");printf("请输入所要查找元素的值:\n");scanf("%d",&e);Find_L(La,e);printf("所要查找元素的位置为:%d\n",Find_L(La,e)); }void Create_L(LinkList &L,int n){int j=1;L=(LinkList)malloc(sizeof(Lnode));L->next =NULL;//先建立一个带头结点的单链线性表L for(int i=n;i>0;--i){LinkList p=(LinkList)malloc(sizeof(Lnode));printf("请输入链表La中的第%d个元素:\n",j++);scanf("%d",&p->data);p->next=L->next;L->next =p;}//(逆序实现)/*LinkList q=L;for(int i=1;i<=n;i++){LinkList p=(LinkList)malloc (sizeof(Lnode));q->next=p;p->next=NULL;q=q->next ;printf("请输入链表La中的第%d个元素:\n",i);scanf("%d",&p->data);}//(正序实现)*/}//初始化单链表//输出单链表void Print_L(LinkList L){LinkList p;p=L->next;while(p){printf("%d ",p->data );p=p->next;}printf("\n");}//在单链表L的第i个位置前插入元素eStatus ListInsert_L(LinkList &L,int i,ElemType e) {LinkList p=L;int j=0;while(p&&j<i-1){p=p->next; ++j;}if(!p||j>i-1) return ERROR;LinkList s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next=p->next;p->next=s;return OK;} //ListInsert_L//删除单链表L中第i个位置上的元素Status ListDelete_L(LinkList &L,int i,ElemType &e) {LinkList p=L;int j=0;while( p->next && j<i-1){p=p->next; ++j;}if(!p->next||j>i-1) return ERROR;LinkList q=p->next; p->next=q->next;e=q->data;free(q);return OK;}//LinkDelete_L/*查找元素并返回位置*/Status Find_L(LinkList L,int e){LinkList p=L->next;int j=1;while(p->data!=e&&p->next){p=p->next;j++;}if(p->data==e) return j;else{printf("无当前元素\n");return ERROR;}if(!p){printf("无当前元素\n");return ERROR;}}//定位2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

数据结构链表的基本操作一、引言链表是计算机科学中的一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表可以用于实现栈、队列和其他数据结构。

本文将详细介绍链表的基本操作。

二、链表的基本概念1. 节点：链表中的每个元素称为节点，它包含两部分：数据和指向下一个节点的指针。

2. 头结点：链表中第一个节点称为头结点，它不包含实际数据，只有指向第一个真正节点的指针。

3. 尾节点：链表中最后一个节点称为尾节点，它的指针为空。

4. 空链表：不包含任何元素的链表称为空链表。

三、链表的基本操作1. 创建链表创建一个空链表很简单，只需要让头结点指针为空即可。

如果需要创建带有多个元素的非空链表，则需要依次创建每个节点，并将前一个节点的指针指向当前节点。

2. 插入元素在插入元素时，需要先找到要插入位置前面的那个节点。

然后新建一个要插入的节点，并将其指针指向原来位置上后面那个节点。

最后将前面那个节点的指针改为新建立的节点。

3. 删除元素在删除元素时，需要先找到要删除的那个节点。

然后将前一个节点的指针指向后一个节点，从而跳过要删除的那个节点。

最后释放要删除的节点。

4. 遍历链表遍历链表是指依次访问链表中每个元素。

可以使用循环结构来实现遍历操作。

从头结点开始，依次访问每个节点，并将其数据输出即可。

5. 查找元素查找元素时，需要从头结点开始依次遍历每个节点，直到找到目标元素或者遍历完整个链表为止。

6. 反转链表反转链表是指将原来的链表顺序倒置。

可以使用三个指针分别表示当前节点、前一个节点和后一个节点，依次修改它们之间的指针即可实现反转操作。

四、链表的应用举例1. 栈和队列：栈和队列都可以用链表来实现。

栈是一种先进后出（FILO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。

2. 链式存储文件系统：文件系统中通常采用基于树或者基于哈希表的存储方式。

但是在某些情况下，也可以采用基于链式存储方式来实现文件系统。

数据结构实验报告之链表顺序表的操作1、编写程序实现顺序表的各种基本运算：初始化、插⼊、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计⼀个主程序完成如下功能：（1）初始化顺序表L；（2）依次在表尾插⼊a，b，c，d，e五个元素；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插⼊元素f，之后输出顺序表L；（9）删除L的第2个元素，之后输出顺序表L；（10）销毁顺序表L。

2、编写程序实现单链表的各种基本运算：初始化、插⼊、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计⼀个主程序完成如下功能：（1）初始化单链表L；（2）依次在表尾插⼊a，b，c，d，e五个元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插⼊元素f，之后输出单链表L；（9）删除L的第2个元素，之后输出单链表L；（10）销毁单链表L。

1顺序表2 #include<stdio.h>3 #include<malloc.h>4 #include<stdlib.h>56#define TRUE 17#define FALSE 08#define OK 19#define ERROR 010#define INFEASIBLE -111#define OVERFLOW -212 typedef int Status;13 typedef char ElemType;1415#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量16#define LISTINCREMENT 10 //线性表存储空间的分配增量17 typedef struct {18 ElemType *elem; //存储空间基地址19int length; //当前长度20int listsize; //当前分配的存储容量21 } SqList;2223 Status InitList_Sq(SqList &L) { //算法2.324 L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));25if (!L.elem) exit(OVERFLOW); //存储分配失败26 L.length = 0; //空表长度为027 L.listsize = LIST_INIT_SIZE; //初始存储容量28return OK;29 }//InitList_Sq3031 Status ListInsert_Sq(SqList &L, int i, ElemType e) { //算法2.432 ElemType *newbase, *p, *q;33if (i<1 || i>L.length + 1) return ERROR; //i值不合法34if (L.length >= L.listsize)35 { //当前存储空间已满，增加分配36 newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));37if (!newbase) exit(OVERFLOW); //存储分配失败38 L.elem = newbase; //新基址39 L.listsize += LISTINCREMENT; //增加存储容量40 }41 q = &(L.elem[i - 1]); //q为插⼊位置42for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; //元素右移43 *q = e; //插⼊e44 ++L.length; //表长增145return OK;46 }4748void DispSqList(SqList L)49 {50int i;51for (i = 0; i < L.length; i++)52 printf("%c ", L.elem[i]);53 }5455 Status ListDelete(SqList &L, int i, ElemType &e)56 {57 ElemType *p,*q;58if ((i < 1) || (i > L.length)) return ERROR;59 p = &(L.elem[i - 1]);60 e = *p;61 q = L.elem + L.length - 1;62for (++p; p <= q; ++p)63 *(p - 1) = *p;64 --L.length;65return OK;66 } //ListDelete_Sq6768 Status GetElem(SqList L, int i, ElemType &e)69 {70if (L.length == 0 || i<1 || i>L.length)71return ERROR;72 e = L.elem[i - 1];73return OK;74 }7576int ListLength(SqList L)77 {78return(L.length);79 }8081 Status DestroyList(SqList &L)82 {83 free(L.elem);84 L.length = 0;85return OK;86 }8788 Status ListEmpty(SqList L)89 {90return(L.length == 0);91 }9293int LocateElem(SqList L, ElemType e)94 {95int i = 0;96while (i < L.length && L.elem[i] != e) i++;97if (i >= L.length) return0;98else return i + 1;99 }100101void main()102 {103 SqList h;104 ElemType e;105 InitList_Sq(h);106 ListInsert_Sq(h, h.length + 1, 'a');107 ListInsert_Sq(h, h.length + 1, 'b');108 ListInsert_Sq(h, h.length + 1, 'c');109 ListInsert_Sq(h, h.length + 1, 'd');110 ListInsert_Sq(h, h.length + 1, 'e');111 DispSqList(h);112 printf("%d\n\n",ListLength(h));113 ListEmpty(h);114if (ListEmpty(h))116 printf("Empty\n\n");117 }118else119 {120 printf("Not empty\n\n");121 }122 GetElem(h, 4, e);123 printf("%c\n", e);124 printf("%d\n",LocateElem(h, 'c'));125 ListInsert_Sq(h,3,' f');126 DispSqList(h);127 ListDelete(h, 2, e);128 DispSqList(h);129 DestroyList(h);130 }131132133134135136单链表137138139140 #include<stdio.h>141 #include<malloc.h>142 #include<stdlib.h>143144#define TRUE 1145#define FALSE 0146#define OK 1147#define ERROR 0148#define INFEASIBLE -1149#define OVERFLOW -2150 typedef int Status;151152 typedef char ElemType;153154155 typedef struct LNode {156 ElemType data;157int length;158struct LNode *next;159 }LNode, *LinkList;160161162 Status InitList_L(LinkList &L) {163 L = (LinkList)malloc(sizeof(LNode));164 L->next = NULL;165return OK;166 }167168 Status ListInsert_L(LinkList L, int i, ElemType e) { 169 LinkList p = L,s;170int j = 0;171while (p && j < i - 1)172 {173 p = p->next;174 ++j;175 }176if (!p || j > i - 1)177 {178return ERROR;179 }180else181 {182 s = (LinkList)malloc(sizeof(LNode));183 s->data = e;184 s->next = p->next;185 p->next = s;186return OK;187 }188 }189190void DispList_L(LinkList L)191 {192 LinkList p = L->next;193while (p != NULL)194 {195 printf("%c\n", p->data);196 p = p->next;197 }198200201void DestoryList(LinkList &L)202 {203 LinkList p = L, q = p->next;204while (q != NULL)205 {206 free(p);207 p = q;208 q = p->next;209 }210 free(p);211 }212213 Status ListLength_L(LinkList L) {214 LinkList p = L; int n = 0;215while (p->next != NULL)216 {217 n++;218 p = p->next;219 }220return (n);221 }222223 Status ListDelete(LinkList L, int i, ElemType &e){ 224int j;225 LinkList p, q;226 p = L;227 j = 1;228while (p->next && j < i)229 {230 p = p->next;231 ++j;232 }233if (!(p->next) || j > i)234 {235return ERROR;236 }237 q = p->next;238 p->next = q->next;239 e = q->data;240 free(q);241return OK;242 }243244 Status ListEmpty_L(LinkList L)245 {246return(L->length == 0);247 }248249 Status GetElem(LinkList L, int i, ElemType &e) 250 {251int j;252 LinkList p;253 p = L->next;254 j = 1;255while (p&&j<i)256 {257 p = p->next;258 ++j;259 }260if (!p || j > i)261 {262return ERROR;263 }264 e = p->data;265return OK;266 }267268 Status LocateElem(LinkList L, int e)269 {270 LinkList p = L;271int n=0;272//p->length = 0;273while (p != NULL)274 {275if(p->data != e)276 {277 p = p->next;278 n++;279 }280else281 {282break;283 }284 }285if(p != NULL)286 {287return n;288 }289else290 {291return ERROR;292 }293 }294295void main()296 {297 LinkList h;298 ElemType e;299 InitList_L(h);300 ListInsert_L(h, 1, 'a');301 ListInsert_L(h, 2, 'b');302 ListInsert_L(h, 3, 'c');303 ListInsert_L(h, 4, 'd');304 ListInsert_L(h, 5, 'e');305 DispList_L(h);306 printf("%d\n", ListLength_L(h)); 307if (ListEmpty_L(h))308 {309 printf("Empty\n\n");310 }311else312 {313 printf("Not empty\n\n");314 }315 GetElem(h, 4, e);316 printf("%c\n", e);317 printf("%d\n", LocateElem(h, 'c')); 318 ListInsert_L(h, 3, 'f');319 DispList_L(h);320 ListDelete(h, 2, e);321 DispList_L(h);322 DestoryList(h);323 }。