• 售前

  • 售后

热门帖子
入门百科

数据布局-线性表-链式存储布局-单链表

[复制链接]
真好210 显示全部楼层 发表于 2022-1-16 14:09:59 |阅读模式 打印 上一主题 下一主题


 
一、前言

二、次序表知识点回顾

三、单链表

1.链表的界说

2.单链表的分类

3.单链表尾结点分析

4.单链表根本运算算法

5.快速创建链表

6.循环单链表

四、总结



   一、前言
  通过上篇文章(线性表中次序表_m0_50708613的博客-CSDN博客),相识到了数据布局中的线性表有次序存储和链式存储两种布局,本章重要解说链式存储布局中单链表和双链表。

   二、次序表知识点回顾
  次序表在逻辑上相邻两个元素在物理上也是相邻的,在存取某一个元素时很轻易,而在插入和删除元素时,须要移动大量元素的位置,导致算法的运算量大,时间复杂度大,但是线性表是链式存储布局却可以办理此题目。
次序表知识点增补——团体创建链表
  1. <code>
  2. //整体创建顺序表
  3. void CreateList(SqList &L,ElemType a[],int n)
  4. {
  5.         int j=0;
  6.         for(int i=0;i<n;++i)
  7.         {
  8.                 L.data[k]=a[i];
  9.                 j++;
  10.         }
  11.         L.length=j;
  12. }
复制代码
(2)效果演示

(3) 单链表根本运算算法时间复杂度分析
根本运算算法时间复杂度
void InitList(LNode *&L)——初始化O(1)
void DestroyList(LNode *&L)——烧毁O(n)
int GetLength(LNode *L)——求单链表的长度O(n)
求单链表中第i个元素
int GetElem(LNode *L,int i,ElemType &e)
O(n)
int Locate(LNode *L,ElemType e)——查找O(n)
int InsElem(LNode * &L,ElemType x,int i) ——插入O(n)
int DelElem(LNode *&L,int i)——删除O(n)
void DispList(LNode *L)——输出单链表O(n)
5.快速创建链表
a:头插法
  1. <code>#include <stdio.h>
  2. #include <malloc.h>
  3. //结点类型声明
  4. typedef int ElemType;
  5. typedef struct node
  6. {
  7.         ElemType data;     //数据域data
  8.         struct node *next;   //指针域
  9. }LNode;                 //单链表结点类型
  10. //初始化单链表运算算法
  11. void InitList(LNode *&L)             //L为引用型参数
  12. {
  13.         L=(LNode*)malloc(sizeof(LNode));  //申请空间,创建头结点L
  14.         L->next=NULL;                     //头结点的指针域(next)指向NULL,表示空链表
  15. }
  16. //销毁单链表的运算算法
  17. void DestroyList(LNode *&L)
  18. {
  19.         LNode *p1=L,*p=p1->next;
  20.         while(p!=NULL)
  21.         {
  22.                 free(p1);        //释放p1结点空间
  23.                 p1=p;p=p->next;  //p1,p同步后移
  24.         }
  25.         free(p1);           //释放p1指向的尾结点空间
  26. }
  27. //求单链表的长度运算算法
  28. int GetLength(LNode *L)
  29. {
  30.         int i=0;
  31.         LNode *p=L->next;         //p指向头结点,i为1
  32.         while(p !=NULL)
  33.         {
  34.                 i++;
  35.                 p=p->next;           //p移到下一个结点,i++
  36.         }
  37.         return i;                //p为空时,i即为数据结点个数
  38. }
  39. //求单链表中第i个元素运算算法
  40. int GetElem(LNode *L,int i,ElemType &e)
  41. {
  42.         int j=0;
  43.         LNode *p=L;     //p指向头结点,计数器j值为0
  44.         if(i<0)
  45.                 return 0;   //参数i错误返回0
  46.         while(p!=NULL && j<i)
  47.         {
  48.                 j++;
  49.                 p=p->next;
  50.         }
  51.         if(p==NULL)
  52.                 return 0;    //未找到返回0
  53.         else
  54.         {
  55.                 e=p->data;
  56.                 return 1;   //找到后返回1
  57.         }
  58. }
  59. //按值查找运算算法
  60. int Locate(LNode *L,ElemType e)
  61. {
  62.         LNode *p=L->next;
  63.         int j=1;               //p指向头结点,j置为序号1
  64.         while(p!=NULL && p->data!=e)
  65.         {
  66.                 p=p->next;
  67.                 j++;
  68.         }
  69.         if(p==NULL)
  70.                 return(0);           //未找到返回0
  71.                 else
  72.                 return (j);         //找到后返回其序号
  73. }
  74. //插入元素运算算法
  75. int InsElem(LNode * &L,ElemType x,int i)  //插入结点值为X的结点
  76. {
  77.         int j=0;
  78.         LNode *p=L,*s;
  79.         if(i<=0)
  80.                 return 0;         //参数i错误返回0
  81.         while(p!=NULL && j<i-1) //查找第i-1个结点p
  82.         {
  83.                 j++;
  84.                 p=p->next;
  85.         }
  86.         if(p==NULL)
  87.                 return 0;          //未找到第i-1个结点是返回0
  88.         else                    //找到第i-1个结点p
  89.         {
  90.                 s=(LNode*)malloc(sizeof(LNode));
  91.                 s->data=x;         //创建存放元素x的新结点s
  92.                 s->next=p->next;   //将s结点插入到P结点之后
  93.                 p->next=s;
  94.                 return 1;          //插入成功,返回1
  95.         }
  96. }
  97. //删除结点运算算法
  98. int DelElem(LNode *&L,int i)
  99. {
  100.         int j=0;
  101.         LNode *p=L,*q;
  102.         if(i<=0)
  103.                 return 0;             //参数i错误返回0
  104.         while(p!=NULL && j<i-1)   //查找第i-1个结点
  105.         {
  106.                 j++;
  107.                 p=p->next;
  108.         }
  109.         if(p==NULL)
  110.                 return 0;            //未找到第i-1个结点是返回0
  111.         else                     //找到第i-1个结点p
  112.         {
  113.                 q=p->next;          //q指向被删除的结点
  114.                 if(q==NULL)
  115.                         return 0;       //没有第i个结点是返回0
  116.                 else
  117.                 {
  118.                         p->next=q->next; //从单链表中删除q结点
  119.                         free(q);         //释放其空间
  120.                         return 1;
  121.                 }
  122.         }
  123. }
  124. //输出单链表
  125. void DispList(LNode *L)
  126. {
  127.         LNode *p=L->next;
  128.         while(p!=NULL)
  129.         {
  130.                 printf("%d",p->data);
  131.                 p=p->next;
  132.         }
  133.         printf("\n");
  134. }
  135. void main()
  136. {
  137.         int i;
  138.         ElemType e;
  139.         LNode *L;
  140.         InitList(L);
  141.         InsElem(L,6,1);
  142.         InsElem(L,4,2);
  143.         InsElem(L,4,3);
  144.         InsElem(L,7,4);
  145.         InsElem(L,1,5);
  146.         InsElem(L,9,6);
  147.         InsElem(L,8,7);
  148.         InsElem(L,3,8);
  149.         InsElem(L,2,9);
  150.         InsElem(L,7,10);
  151.         printf("单链表: ");
  152.         DispList(L);
  153.         printf("长度: %d\n",GetLength(L));
  154.         i=6;
  155.         GetElem(L,i,e);
  156.         printf("第%d个元素: %d\n",i,e);
  157.         e=3;
  158.         printf("元素%d是第%d个元素\n",e,Locate(L,e));
  159.         i=7;
  160.         printf("删除第%d个元素\n",i);
  161.         DelElem(L,i);
  162.         printf("单链表:");
  163.         DispList(L);
  164.         DestroyList(L);
  165. }
复制代码
注:建成 的单链表结点序次与插入序次相反。
b:尾插法
  1. <code>#头插法
  2. void CreateListF(LNode *&L,ElemType a[],int n)
  3. {
  4.         LNode *s;
  5.         L=(LNode*)malloc(sizeof(LNode));   //申请空间
  6.         L->next=NULL;                      //创建一个空单链表
  7.         for(int i;i<n;i++)                 //遍历a[]所有元素
  8.         {
  9.                 s=(LNode*)malloce(sizeof(LNode));
  10.                 s->data=a[i];                 //将创建存放a[i]元素的新节点s
  11.                 s->next=L->next;              //将s结点插入到头结点
  12.                 L->next=s;
  13.         }
  14. }
复制代码
注:建成 的单链表结点序次与插入序次类似。
6.循环单链表
循环单链表与平凡单链表非常相似,只是将单链表中尾结点的next域有原来的NULL改为指向头结点,其根本运算算法极其相似。下面给出循环单链表的根本运算算法。
  1. <code>//尾插法
  2. void CreateListR(LNode *&L,ElemType a[],int n)
  3. {
  4.         LNode *s,*d;
  5.         L=(LNode *)malloc(sizeof(LNode));  //创建头结点
  6.         d=L;                              //d始终指向尾结点,初始时指向头结点
  7.         for(int i=0;i<n;++i)
  8.         {
  9.                 s=(LNode *)malloc(sizeof(LNode));
  10.                 s->data=a[i];                 //创建存放a[i]元素的新节点s
  11.                 d->next=s;                  
  12.                 d=s;                         //结点s变成新的尾结点,
  13.         }
  14.         d->next=NULL;                    //由于是普通的单链表,故尾结点next域置为NULL
  15. }
复制代码
  四、总结
  单链表的物理存储位置是随机的,没有逐一对应的逻辑关系,在插入和删除运算时,必备大量的移动数据域的位置,只要筹划一个新指针举行遍历便好。而且创建链表有两种快速的方法,可选择性进步了,可根据情况选择对应的方法创建链表办理题目。

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作