C语言之线性表链式存储结构

文章目录

• C语言之线性表链式存储结构
• 前言
• 一、线性表链式存储结构定义
• 二、相关概念
• • 1.结点
  • 1.头指针
• 三、代码描述
• • 1.单链表结点定义
  • 1.单链表的创建
  • 2.单链表的查找
  • 3.在单链表中，替换某一个位置的数据
  • 4.在单链表中，某一个位置插入数据
  • 4.在单链表中，某一个位置删除数据

前言

线性表存在不足的解决办法：`
线性表最大的缺点就是插入和删除时需要移动大量元素，这需要耗费大量时间；因此就引出链式存储结构，用任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续。

一、线性表链式存储结构定义

定义：
以前顺序结构中，每个数据元素只需要存数据元素就可以了，但链式结构中，为了将链表连接起来，每个元素不仅要存储数据元素信息，还需要存储它的后继元素的存储地址。

二、相关概念

1.结点

链表结点由数据域（存放本身信息）和指针域（指向后继结点的指针）构成。如下图所示：

1.头指针

对于线性表来说，总得有个头有个尾，链表也不例外，我们把链表中的第一个结点的存储位置叫做头指针，整个链表的存取就必须是从头指针开始进行了。
最后一个结点的指针为空（NULL）。
有时候我们为了更方便的对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。
头结点的数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。

空链表：

带头结点的单链表：

不带头结点的单链表：

三、代码描述

1.单链表结点定义

typedef int ElemType;可以随着数据元素类型不用，自己定义
链表的结构体
struct Node
{ElemType data;struct Node* next;
}Node;typedef  struct Node* LinkList;链表指针别名

总这个结构定义中，我们也可以知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域，可以用p->data来表示，结点ai的指针域，可以用p->next来表示。p->next指向（意思就是存储第i个元素的地址）第i+1个元素。也就是说，如果p->data=ai，p->next->data=ai+1;

1.单链表的创建

单链表创建算法思路：

• 初始化空链表L-创建头结点
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 生成新的结点
• 新的结点指针指向头结点（指针）
• 头结点指针指向新结点

头插法
LinkList CreatListHead(int len)
{LinkList L = (LinkList)malloc(sizeof(Node));//创建个头节点LinkList temp=L;                   //声明一个中间变量，指向头结点，用于遍历链表（曾因没有这个中间变量而出错）temp->next = NULL;for (int i=0;i<len;i++){LinkList p= (LinkList)malloc(sizeof(Node)); scanf_s("%d",&p->data);p->next = temp->next;     //新结点的next指针,指向开始结点（temp->next是头结点的地址）temp->next = p;                //头结点的next指针指向新结点}return (LinkList)L;
}

解释说明：p->next是下一个结点指针的地址
p是结点指针

尾插法

链表的创建,建立带头节点的单链线性表L，随机产生Ｎ个元素值
LinkList CreatListTail(int len)
{LinkList L = (LinkList)malloc(sizeof(Node));创建个头节点LinkList temp = L;                   声明一个中间变量，指向头结点，用于遍历链表（曾因没有这个中间变量而出错）temp->next = NULL;for (int i = 0; i < len; i++){LinkList p = (LinkList)malloc(sizeof(Node));scanf_s("%d", &p->data);temp->next = p;   头结点指向新的结点（存储新结点地址）temp = p;                将新结点变成头结点等待下一个新结点插入}temp->next = NULL;将最后一个结点的NEXT结点为空，表示链表结束return (LinkList)L;
}

2.单链表的查找

因为链表不支持随机访问，即链表的存取方式是顺序存取的（注意“存储”与“存取”是两个不一样的概念），所以要查找某结点，必须通过遍历的方式查找。例如：如果想查找第3个结点，必须先遍历走过第1~2个结点，才能得到第3个结点。
单链表查找算法思路：

• 链表存在，输入要查找的值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表
• 将链表中与查找值相等的数据返回

int SearchList(LinkList L,int elem)
{LinkList temp;temp = L;int position = 0;用于返回数据在链表中的位置while (temp->next){   position++;temp = temp->next;指针后移遍历链表if (elem == temp->data){printf_s("Searchdata=%d,postion=%d\n", temp->data, position);}return position;}return 0;
}

3.在单链表中，替换某一个位置的数据

单链表替换算法思路：

• 链表存在，输入要替换的位置，要替换的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，到要替换的位置，跳出循环
• 将要替换的值，赋值到数据域
• 返回链表的头结点

LinkList  ReplaceList(LinkList L,int pos,int elem)
{LinkList temp = L;temp = temp->next;指向开始结点（注意头结点与开始结点区别）头结点的后继结点为开始结点for (int i = 0; i < pos; i++){temp = temp->next;}temp->data = elem;return L;
}

4.在单链表中，某一个位置插入数据

单链表插入算法思路：

• 链表存在，输入要插入的位置，要插入的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，找到插入位置前的结点
• 新建结点，将要插入的数据，赋值到新建结点的数据域
• 返回链表的头结点
  

LinkList InsertList(LinkList L,int pos,int elem)
{LinkList temp = L;int i = 0;temp = temp->next;指向开始结点for (i = 0; i < pos-1; i++){if ((temp == NULL) || (i > pos - 1)){printf("%s:Insert false!\n", __FUNCTION__);return L;}temp = temp->next;}LinkList new = (LinkList)malloc(sizeof(Node));new->data = elem;new->next = temp->next;新建结点指向插入的下个结点temp->next = new;插入位置的结点指针指向新建结点return L;}
第二种写法LinkList InsertList(LinkList L, int pos, int elem)
{LinkList temp = L;	//引入一个中间变量，用于循环变量链表int i = 0;/* 首先找到插入结点的上一结点，即第pos-1个结点 */while( (temp!=NULL)&&(i<pos-1) ){temp = temp->next;++i;}/* 错误处理：链表为空或插入位置不存在 */if( (temp==NULL)||(i>pos-1) )		{printf("%s:Insert false!\n",__FUNCTION__);return (LNode*)temp;}LinkList new = (LinkList)malloc(sizeof(Node));	//创建新结点newnew->data = elem;		插入的新结点的数据域new->next = temp->next; 新结点的next指针指向插入位置后的结点temp->next = new;		插入位置前的结点的next指针指向新结点return L;返回头结点

4.在单链表中，某一个位置删除数据

单链表插入算法思路：

• 链表存在，输入要插入的位置，要插入的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，找到插入位置前的结点
• 新建结点，将要插入的数据，赋值到新建结点的数据域
• 返回链表的头结点
  

LinkList DeleteList(LinkList L, int pos, int *elem)
{LinkList temp = L;int i = 0;temp = temp->next;指向开始结点LinkList del;新建结点for (i = 0; i < pos - 1; i++){if ((temp == NULL) || (i > pos - 1)){printf("%s:Insert false!\n", __FUNCTION__);return L;}temp = temp->next;}del = temp->next; 结点指向被删除结点*elem = del->data; 结点数据域存储到elem中temp->next = del->next;要删除位置前的结点指向要删除结点后的结点free(del);释放内存del = NULL;防止野指针return L;}
第二种写法LinkList Delete(LinkList L, int pos, int *elem)
{LinkList temp = L;	//引入一个中间变量，用于循环变量链表int i = 0;/* 首先找到删除结点的上一结点，即第pos-1个结点 */while( (temp!=NULL)&&(i<pos-1) ){temp = temp->next;++i;}/* 错误处理：链表为空或删除位置不存在 */if( (temp==NULL)||(i>pos-1) ){printf("%s:Delete false!\n",__FUNCTION__);return temp;}LinkList del = temp->next;	//定义一个del指针指向被删除结点*elem = del->data;			//保存被删除的结点的数据域temp->next = del->next;		/*删除结点的上一个结点的指针域指向删除结点的下一个结点，也可写为“temp->next = temp->next->next”*/free(del);					//手动释放该结点，防止内存泄露del = NULL;					//防止出现野指针return L;			

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！