数据结构链表代码

数据结构经典题目及c语言代码一、线性表1. 顺序表顺序表是一种利用连续存储空间存储元素的线性表。

以下是一个顺序表的经典题目及C语言代码实现：```c#define MaxSize 50typedef struct {int data[MaxSize]; // 存储元素的数组int length; // 顺序表的当前长度} SeqList;// 初始化顺序表void initList(SeqList *L) {L->length = 0;}// 插入元素到指定位置void insert(SeqList *L, int pos, int elem) {if (pos < 1 || pos > L->length + 1) {printf("插入位置无效\n");return;}if (L->length == MaxSize) {printf("顺序表已满，无法插入\n"); return;}for (int i = L->length; i >= pos; i--) { L->data[i] = L->data[i - 1];}L->data[pos - 1] = elem;L->length++;}// 删除指定位置的元素void delete(SeqList *L, int pos) {if (pos < 1 || pos > L->length) {printf("删除位置无效\n");return;}for (int i = pos - 1; i < L->length - 1; i++) {L->data[i] = L->data[i + 1];}L->length--;}// 获取指定位置的元素值int getElement(SeqList *L, int pos) {if (pos < 1 || pos > L->length) {printf("位置无效\n");return -1;}return L->data[pos - 1];}```2. 链表链表是一种利用非连续存储空间存储元素的线性表。

数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表） ⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。

⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。

三、⼆叉链表的C语⾔代码实现：#include "string.h"#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* ⽤于构造⼆叉树********************************** */int index=1;typedef char String[24]; /* 0号单元存放串的长度 */String str;Status StrAssign(String T,char *chars){int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}}/* ************************************************ */typedef char TElemType;TElemType Nil=''; /* 字符型以空格符为空 */Status visit(TElemType e){printf("%c ",e);return OK;}typedef struct BiTNode /* 结点结构 */{TElemType data; /* 结点数据 */struct BiTNode *lchild,*rchild; /* 左右孩⼦指针 */}BiTNode,*BiTree;/* 构造空⼆叉树T */Status InitBiTree(BiTree *T){*T=NULL;return OK;}/* 初始条件: ⼆叉树T存在。

数据结构代码
1.简介
- 介绍数据结构的定义、作用以及常见应用场景。

- 简要概述本文档内容与结构。

2.数组 (Array)
- 定义和特点
- 基本操作：插入、删除、查找、修改
- 数组的实现方式与优缺点
- 数组的常见问题与解决方法
3.链表 (Linked List)
- 单向链表、双向链表和循环链表的定义和特点 - 基本操作：插入、删除、查找、修改
- 链表的实现方式与优缺点
- 链表的常见问题与解决方法
4.栈 (Stack)
- 定义和特点
- 基本操作：入栈、出栈、获取栈顶元素、判断栈是否为空
- 栈的实现方式与优缺点
- 栈的常见问题与解决方法
5.队列 (Queue)
- 定义和特点
- 基本操作：入队、出队、获取队首元素、判断队列是否为空
- 队列的实现方式与优缺点
- 队列的常见问题与解决方法
6.树 (Tree)
- 二叉树、二叉搜索树和平衡二叉树的定义和特点
- 基本操作：插入、删除、查找
- 树的遍历方式：前序、中序、后序和层序遍历
- 树的实现方式与优缺点
- 树的常见问题与解决方法
7.图 (Graph)
- 有向图和无向图的定义和特点
- 图的表示方式：邻接矩阵和邻接表
- 图的遍历方式：深度优先搜索和广度优先搜索 - 图的常见问题与解决方法
附件：
- 相关示例代码文件
- 图片/图表文件
法律名词及注释：
- 1.法律名词A：解释A的含义和定义。

- 2.法律名词B：解释B的含义和定义。

数据结构顺序表的主要代码（LIZHULIN）1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***//***********单链表的初始化、建立、输出*****************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = NULL;}/*************建立一个带头结点的单链表，在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p,*q; int i;Initlist(L); /*单链表初始化*/q=L;printf("input the value\n");for(i = n;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));scanf("%d",&p->data); /*输入元素值*/q->next = p;p->next = NULL;q=p;/*插入到表尾*/}} /* Create_L *//*************建立一个带头结点的单链表，在表头插入**************Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化/*需要注意第一个数据插入时的情况/*Insert the Firset nodep = (LinkList*)malloc(sizeof(struct Lnode));printf("input the value\n");scanf("%d",&p->data); /*输入元素值L->next = p;p->next = NULL;/*将第二个及后面的数据插入for(i = n-1;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));printf("input a value\n");scanf("%d",&p->data); /*输入元素值p->next = L->next;L->next = p;/*插入到表头}} /* Create_L *//*************************求单链表的长度***********************/int Length_LinkList(LinkList *L){LinkList *p;int i=0;p=L->next;while(p!=NULL){i++;p=p->next;}return i;}/*Length_LinkList*//*************************在第i个结点前插入数据x *********************/ Insert_LinkList(LinkList *L, int i, int x){LinkList *p,*s;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*//*插入元素x */s=(LinkList *)malloc(sizeof(struct Lnode));s->data=x;s->next=p->next;p->next=s;}/*********************删除第i个元素，并用y将其值返回************************/ int Delete_LinkList(LinkList *L, int i){LinkList *p,*q;int y;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*/q=p->next;y=q->data;p->next=q->next;free(q) ;return y;} /*Delete_LinkList*//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int len;int n=0;int x=15;int y;int i=4;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =NULL;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);Insert_LinkList(L, i, x);/* y=Delete_LinkList(L,i);printf("the delete elment is y=%d\n",y);len=Length_LinkList(L);printf("the length of L is %d",len);*/display(L);getch();}2．/***无头结点的单链表建立、插入、求长度、插入、删除、输出*****/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;while(p!=NULL){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}3．/*********顺序表的建立、查找、插入运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/*******Creat SqList********/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input SqList.data\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Position Error");return;}elsereturn L->data[i-1];}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *L;/*printf("input the length of SqList\n");scanf("%d",&len);*/Create_SqList(L);Display_SqList(L);getch();}4．/*********顺序表的归并运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/************ Creat SqList*************/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input the data of SqList\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Getelem Position Error");return;}return L->data[i-1];}/************ Insert Operation *********/void ListInsert(SqList *L,int i, int x){SqList *q, *p;if(i<1 || i>L->length){printf("the insert position error");return ;}q = &(L->data[i-1]); /*q为插入位置*/for(p=&(L->data[L->length-1]); p>=q; --p)*(p+1) = *p;L->data[i-1] = x;++L->length;}/********* LA and LB Merged LC ***************/ void MergeList(SqList *LA,SqList *LB,SqList *LC) {int La_len,Lb_len,ai,bj;int i,j;int k;i=j=1;InitList(LC);La_len = ListLength(LA);Lb_len = ListLength(LB);LC->length = La_len+Lb_len;/*for(k=0;k<LC->length;k++)LC->data[k] = 0; */k=0;while((i<=La_len)&&(j<=Lb_len)){ai= GetElem(LA, i);bj= GetElem(LB, j);if(ai<bj){++k;ListInsert(LC,k,ai);++i;}elseif(ai==bj){++k;ListInsert(LC,k,ai);++k;ListInsert(LC,k,bj);++i;++j;}else{++k;ListInsert(LC,k,bj);++j;}}while(i<=La_len){/*Append the residual node into LA */ai= GetElem(LA, i);++i;++k;ListInsert(LC,k,ai);}while(j<=Lb_len){/*Append the residual node into LA */bj= GetElem(LB, j);++j;++k;ListInsert(LC,k,bj);}LC->length = La_len+Lb_len;}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *LA , *LB, *LC;Create_SqList(LA);Create_SqList(LB);MergeList(LA,LB,LC);Display_SqList(LC);getch();}5．/**** 用带头结点的循环单链表解决约瑟夫问题***********/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = L;}/*************建立一个带头结点的循环单链表，数据值为1,2,3,...n,在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化p=L;for(i = n;i>0;--i){q = (LinkList*)malloc(sizeof(struct Lnode));q->data = i; /*输入元素值p->next =qq->next = L;/*插入到表尾}} /* Create_L *//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p->next!=L){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int n;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =L;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);display(L);getch();}6．/******** 无头结点的循环单链表的建立**************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}p->next = L;/*尾结点指向第一个结点*/}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;printf("%d ",p->data);p=p->next;while(p->next !=L){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/ main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}。

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：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),因为可以与后继结点交换数据域，然后删除后继结点。

/* 线性表的顺序表示：类型和界面定义*//* 线性表的顺序表示：函数实现*//* 线性表的单链表表示：类型和界面函数定义*//* 线性表的单链表表示：函数实现*//* 线性表的顺序表示：类型和界面定义*//* 线性表的顺序表示：函数实现*//* 用顺序表解决josephus问题的算法*//* 用循环单链表解决josephus问题的算法*//*字符串的顺序表示*//* 字符串的链接表示 *//* 顺序栈表示：类型和界面函数声明 *//* 顺序栈表示：函数定义 *//* 栈链接表示：类型和界面函数声明 *//*栈链接表示：函数定义*//* 简化背包问题的递归算法*//* 简化背包问题的非递归算法*//* 迷宫问题的递归算法*//* 迷宫问题的非递归算法(栈实现)*//* 队列的顺序表示：类型和函数声明 *//* 队列的顺序表示：函数定义 *//*队列链接表示：类型和界面函数声明*//*队列链接表示：函数定义*//* 用队列解决农夫过河问题的算法*//* 树的长子-兄弟表示法*//* 树的父指针表示法*//* 树的子表表示法*//* 树的后根周游的递归算法*//* 树的先根周游的非递归算法*//* 树的中根周游的递归算法*//* 树的后根周游的递归算法*//* 树的广度优先周游算法*//* 二叉树的链接表示*//* 二叉树的顺序表示*//* 线索二叉树的定义,构造算法和中根周游算法*//* 二叉树前根周游的递归算法*//* 二叉树对称根周游的递归算法*//* 二叉树后根周游的递归算法*//* 二叉树后根周游的非递归算法*//* 本程序提供了用顺序表实现字典的存储表示定义*//* 本程序是用开地址法解决碰撞的散列表示方法,提供了字典的一些基本操作*//* 字典的二叉排序树实现,本程序实现了二叉排序树的基本操作的算法*/ /* 字典的AVL树实现*//* 本程序提供了用顺序表实现字典的情况下的顺序检索算法*//* 本程序提供了用顺序表实现字典的情况下的二分法检索算法*//* 本程序是用开地址法实现散列的检索算法*//* 二叉排序树的检索算法*//* AVL树的检索算法*//* 最佳二叉排序树是具有最佳检索效率的二叉排序树, 本程序提供了最佳二叉排序树的构造方法*//* 直接插入排序的算法源程序*//* 二分法插入排序的算法源程序*//* 表插入排序的算法源程序*//* shell排序的算法源程序 *//* 直接选择排序的算法源程序*//* 堆排序的算法源程序*//* 起泡排序的算法源程序*//* 快速排序的算法源程序*//* 基数排序的算法源程序*//* 二路归并排序算法的源程序*//* 用图邻接矩阵表示实现的一些基本运算*//* 用图邻接表表示实现的一些基本运算*//* 用邻接矩阵表示的图的广度优先周游算法*//* 用邻接表表示的图的广度优先周游算法*//* 用邻接矩阵表示的图的深度优先周游的递归算法*/ /* 用邻接矩阵表示的图的深度优先周游的非递归算法*/ /* 用邻接表表示的图的深度优先周游的非递归算法*/ /* 用邻接矩阵表示的图的Kruskal算法的源程序*//* 用邻接矩阵表示的图的prim算法的源程序*//* 用邻接矩阵表示的图的Dijkstra算法的源程序*//* 用邻接矩阵表示的图的Floyd算法的源程序*//* 用邻接表表示图的拓扑排序算法*//* 用邻接矩阵表示图的拓扑排序算法*//* 图的关键路径问题的算法*//* 背包问题的贪心法算法*//* 用动态规划法求组和数的算法*//* 用回溯法解决骑士周游问题的算法*//* 0/1背包问题的回溯法算法*//* 0/1背包问题的动态规划法算法*//* 0/1背包问题的分支定界法算法*//* 线性表的顺序表示：类型和界面定义*/#define TRUE 1#define FALSE 0#define SPECIAL -1/* 定义顺序表的大小。

数据结构c语言版创建单链表的代码单链表作为常用的线性结构之一，常常用于解决以链式方式存储数据的问题。

创建单链表需要掌握一些基础的数据结构知识以及对C语言的熟练运用。

接下来，本文将分步骤地阐述数据结构C语言版创建单链表的代码。

第一步，定义单链表结构体并定义节点类型。

在C语言中，我们可以通过结构体的方式定义单链表，其中结构体中包含两个成员变量，分别为存储数据的data和指向下一个节点的指针next。

对于节点类型，我们可以使用typedef对节点类型进行定义，例如：```struct ListNode {int data;struct ListNode *next;};typedef struct ListNode ListNode;```在以上代码中，我们首先定义了一个结构体ListNode作为单链表的元素类型，其中包含存储数据的data和指向下一个元素的指针next。

接着我们使用typedef将结构体ListNode定义为仿函数ListNode，从而使其更加方便使用。

第二步，初始化单链表。

在创建单链表之前，我们需要先将单链表的头指针初始化为NULL，表示当前链表为空。

具体代码如下：```ListNode *createLinkedList() {ListNode *head = NULL;return head;}```以上代码中，函数createLinkedList用于创建并初始化单链表，其中head表示单链表头指针，我们将其初始化为NULL。

第三步，向单链表中添加元素。

在单链表中添加元素需要借助于指针的指向关系。

具体来说，我们需要先创建新的节点，将其数据添加到节点中，然后将新节点的next指针指向之前的头节点，最后将头指针指向新节点。

具体过程如下：```ListNode *addListNode(ListNode **head, int val) {ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); newNode->data = val;newNode->next = *head;*head = newNode;return *head;}```在以上代码中，函数addListNode接收一个指向头指针的指针head，以及需要添加的元素值val。

C#数据结构之单链表（LinkList）实例详解本⽂实例讲述了C#数据结构之单链表(LinkList)实现⽅法。

分享给⼤家供⼤家参考，具体如下：这⾥我们来看下“单链表(LinkList)”。

在上⼀篇《》的最后，我们指出了：顺序表要求开辟⼀组连续的内存空间，⽽且插⼊/删除元素时，为了保证元素的顺序性，必须对后⾯的元素进⾏移动。

如果你的应⽤中需要频繁对元素进⾏插⼊/删除，那么开销会很⼤。

⽽链表结构正好相反，先来看下结构：每个元素⾄少具有⼆个属性：data和next。

data⽤来存放数据，⽽next⽤来指出它后⾯的元素是谁(有点“指针”的意思)。

链表中的元素，通常也称为节点Node，下⾯是泛型版本的Node.csnamespace 线性表{public class Node<T>{private T data;private Node<T> next;public Node(T val, Node<T> p){data = val;next = p;}public Node(Node<T> p){next = p;}public Node(T val){data = val;next = null;}public Node(){data = default(T);next = null;}public T Data{get { return data; }set { data = value; }}public Node<T> Next{get { return next; }set { next = value; }}}}链表在存储上并不要求所有元素按顺序存储，因为⽤节点的next就能找到下⼀个节点，这好象⼀根“⽤珠⼦串成的链⼦”，要找到其中的某⼀颗珠⼦，只要从第⼀颗节点(通常称为Head节点)开始，不断根据next指向找到下⼀个，直到找到需要的节点为⽌。

Python数据结构之链表详解⽬录0.学习⽬标1.线性表的链式存储结构1.1指针相关概念1.2指针结构1.3结点1.4结点类2.单链表的实现2.1单链表的初始化2.2获取单链表长度2.3读取指定位置元素2.4查找指定元素2.5在指定位置插⼊新元素2.6删除指定位置元素2.7其它⼀些有⽤的操作3.单链表应⽤3.1单链表应⽤⽰例3.2利⽤单链表基本操作实现复杂操作0. 学习⽬标在顺序存储⽅式中，根据数据元素的序号就可随机存取表中任何⼀个元素，但同时在插⼊和删除运算需要移动⼤量的元素，造成算法效率较低。

解决此缺陷的⼀个办法是：对线性表采⽤链式存储⽅式。

在链表存储⽅式中，在逻辑上相邻的数据元素在存储空间中不⼀定相邻，数据元素的逻辑次序是通过链表中指针链接实现的。

本节将介绍链式存储结构的特点以及各种基本操作的实现。

通过本节学习，应掌握以下内容：线性表的链式存储及实现⽅法链表基本操作的实现利⽤链表的基本操作实现复杂算法1. 线性表的链式存储结构链式存储结构⽤于存放线性表中的元素的存储单元在内存中可以是连续的，也可以是零散分布的。

由于线性表中各元素间存在着线性关系，为了表⽰元素间的这种线性关系，链式存储结构中不仅要存储线性表中的元素，还要存储表⽰元素之间逻辑关系的信息。

所以⽤链式存储结构表⽰线性表中的⼀个元素时⾄少需要两部分信息，除了存储每⼀个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。

采⽤链式存储结构表⽰的线性表简称链表 (Linked List)。

1.1 指针相关概念在继续进⾏讲解前，我们⾸先来了解指针的相关概念，以便更好的理解链表。

假设我们需要处理⼀个⼤型数据⽂件，这⼀⽂件已经被读取保持在内存中，当我们在函数间传递⽂件时，并不会直接传递整个⽂件，我们需要创建变量来保存⽂件在内存中的位置，这些变量很⼩，很容易在不同的函数之间传递。

使⽤指针的好处之⼀就是可以⽤⼀个简单的内存地址就可以指向⼀个更⼤的内存地址段。

【数据结构】链表的实现//111111111111111111111111111第一部分1111111111111111111111111#include <stdio.h>#define ERROR -1;#define OK 1;//用户自定义类型//原来我们定义一个int类型的ElemType，//这次我们定义一个char类型的ElemType，更加深大家的理解typedef int ElemType;typedef int Status;//链表是以结点为基础进行存储的，//这里就是定义一个结点类型的结构体typedef struct LNode{ElemType data;//结点的数据域struct LNode *next; //结点的指针域}LNode;//注意，这里面没有加*LinkList，如果你想加，也可以。

//111111111111111111111111111第一部分结束1111111111111111111111111//222222222222222222222222222第二部分2222222222222222222222222222 //链表的操作//1、头插入法建立单链表，给大家换一种方法，多掌握一种。

Status CreateList_first(LNode *L){//大家在理解尾插法的基础上，试试头插法，作为一个思考题return OK;}//2、尾插入法建立单链表(参考教材)LNode *CreateList_last(LNode *L,int n){int i = 0;LNode *p,*q;p = L;//将头结点赋给新结点pprintf("请输入元素：\n");for(i = n;i > 0;--i){q = (LNode*)malloc(sizeof(LNode));scanf("%d",&(q->data));q->next = NULL; //新申请的结点中的指针域为空p->next = q; //将头结点的地址赋给新申请结点的指针域p = q; //将p的指针后移}return L;}//3、获取链表长度，同时输出链表结点元素int getLength(LNode *L){int length=0;LNode *s;if(L->next == NULL) //头结点值为空{printf("链表为空\n");}s=L->next; //让s指向第一个结点，即首元结点printf("链表数据域中元素值为：\n");while(s != NULL){printf("%d ",s->data); //输出首元结点数据域的值s=s->next; //将s的指针后移length = length + 1; //长度加1}//输出完毕后，跳转到下一行printf("\n现在链表的长度是：%d\n",length);//大家可以思考，可以将链表的长度存入length头结点中的数据域，自己试试return length;}//4、获取单链表中指定位置i的元素e，如果不存在返回error (参考教材29页)Status GetElem(LNode *L,int i,ElemType *e){LNode *p;int j = 1;p = L->next;while(p && j < i){p = p->next;j = j + 1;}if(!p || j > i)return ERROR;*e = p->data;//这里的e是一个指针，因此，要将p中数据域的值给了e这个指针指向的空间，//*e，代表的是e指向的空间中的元素值return OK;}//5、在指定的位置i之前插入一个元素（参考教材29页）Status ListInsert_L(LNode *L,int i,ElemType e){LNode *p,*s;int j = 0;p = L; //将头结点给了新申请的结点p//找到第i-1个结点while(p && j < i-1){p = p->next;j = j + 1;}if(!p || j > i)return ERROR;s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return OK;}//6、删除指定位置i的元素Status ListDelete_L(LNode* L,int i,ElemType *e){LNode *p,*q;int j = 0;p = L; //将头结点给了新申请的结点p//找到第i-1个结点while(p->next && j < i-1){p = p->next;j = j + 1;}if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;}//222222222222222222222222222第二部分结束2222222222222222222222222222//33333333333333333333333333333第三部分3333333333333333333333333333void main(){struct LNode *L;//定义一个头指针ElemType e;int temp;int i = -1;int length = 0;int k = 0;//在主函数中申请一个头结点，struct LNode *TOU_Ndoe;TOU_Ndoe=(LNode*)malloc(sizeof(LNode));//申请头结点空间if(TOU_Ndoe == NULL) //如果头结点申请失败，退出{printf("内存分配失败\n");exit(0);}TOU_Ndoe->next = NULL; //将头结点的指针域赋为空//将头结点的数据域给个-1，头结点数据域中的值，不作为链表的值，这个随便给，只是为了方便TOU_Ndoe->data = -1;L = TOU_Ndoe; //将头指针指向头结点printf("1:头插法建立链表------------------------------2：尾插法建立链表\n");printf("3:获取链表长度，并输出元素-------------------4：获取指定位置的链表元素\n");printf("5:在指定的位置i之前插入一个元素---------------6：删除指定位置i的元素\n");printf("7：退出\n");while(1){printf("请输入要操作的编号：\n");scanf("%d",&temp);//如果是1表示头插法建立链表if(temp == 1){printf("头插法需要你们自己实现，给个思考题！:\n");}//如果是2尾插法建立链表if(temp == 2){printf("请输入要插入的元素个数：\n");scanf("%d",&length);L = CreateList_last(L,length);getLength(L);}//如果是3获取链表长度，并输出元素if(temp == 3){getLength(L);}//如果是4获取指定位置的链表元素if(temp == 4){printf("请输入要获取元素的位置：\n");scanf("%d",&k);GetElem(L,k,&e);printf("在第%d个位置获取的元素值为：%d\n",k,e);}//如果是5在指定的位置i之前插入一个元素if(temp == 5){printf("请输入要在第几个位置插入：\n");scanf("%d",&k);printf("请输入要插入元素的值：\n");scanf("%d",&e);ListInsert_L(L,k,e);//插入完毕之后，将线性表刷新（即重新输出长度）getLength(L);}//如果是6删除指定位置i的元素if(temp == 6){printf("请输入要删除元素的位置：\n");scanf("%d",&k);ListDelete_L(L,k,&e);printf("你删除的元素为：%d\n",e);//删除完毕之后，将线性表刷新（即重新输出长度）getLength(L);}//操作结束if(temp == 7){exit(1);}}}。