数据结构与算法分析之单链表的建立,插入和删除操作。
程序员文章站
2024-03-06 08:44:01
...
- 序言
单链表:当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。具体形式如下图:
其中:data称为数据域,next称为指针域。在链表的最开头是头指针head,头指针顾名思义,不含有数据域;尾接点指向NULL的地方。注意,若head==NULL,为空表。
具体代码如下:
1、定义一个结构体,里面包含单链表的每个接点的数据域和指针域。
2、要注意指针域的定义方式。因为是指向下一个结点的指针,所以定义为结点类型的指针,名为Next。
3、最后申明*LinkList, 等同于 *LinkList==Node,定义为指向结构体的指针,名为 *LinkList。代码中是省略版,全称可以写成:typedef struct Node *LinkedList;
typedef struct Node
{
int data;
struct Node* Next;//指向结点类型的指针
}Node ,*LinkList;
- 单链表的建立操作
单链表的建立操作可以分成两种,一种是头插法,一种是尾插法。下面会分别进行讲解:
头插法:就是讲新增结点插入第一个结点之前的位置,示意图如下:
解析:
1、头插法建立单链表,首先需要建立一个媒介指针s,s用于传递新的结点插入链表的正确位置。
2、因为是创建单链表,而且链表的每个指针里面需要存放数据,因此需要先申请内存空间。申请方式如下:
*L=(LinkList)malloc(sizeof(LinkList)); 需要注意的是类型的强制转化,参照左边的类型。又因为是头插法,所以刚创建的链表头结点指向的下个结点应该是空结点,因为此时是空链表。
3、这里的随机生成方式调用的是srand函数。
4、用循环的方式依次插入每个结点。每次插入结点也需要申请空间,并分别赋予数据域和指针域的值。特别注意指针指向的结点就是原本链表的下个位置,这种方式就叫头插法。
5、最后把头指针指向插入的结点
void CreateListHead(LinkList *L,int n)
{
LinkList s;
int i;
srand(time(0));//和time函数配合使用,初始化随机数种子
*L=(LinkList)malloc(sizeof(LinkList));
(*L)->Next=NULL;
for(int i=0;i<n;i++)
{
s=(LinkList)malloc(sizeof(Node));
s->data=rand()%100+1;
s->Next=(*L)->Next;
(*L)->Next=s;
}
free(s);
}
- 尾插法:
是将新增结点插入最后一个结点之后,示意图如下:
解析:
尾插法和头插法在实现方式上大致相同,
区别在与:
1、尾插法需要申明两个指针r和s,r用来指向当前结点的位置,s用来传递插入节点,因此只有s需要申请空间。
2、把r的指针指向插入结点s,完成后把r指向s的位置。
3、完成建立后,把r指向空结点。
实现代码如下:
void CreateListLast(LinkList *L,int n)
{
LinkList r,s;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));
r=*L;
for(int i=0;i<n;i++)
{
s=(LinkList)malloc(sizeof(Node));
s->data=rand()%100+1;
r->Next=s;
r=s;
}
r->Next=NULL;
}
- 单链表的插入操作
在结点p之前插入一个新的结点q,由于q的位置的不同,插入操作有以下两种情况:
1)在链表的表头插入
1、创建一个新的结点q。
2、将此结点的数据域赋值e,并将它的Next指针指向第一个结点。
3、将头结点的指针指向新的结点q。
实现示意图如下:
2)在链表的中间插入
1、创建一个新结点q。
2、将此结点的数据域赋值为e,将next指针指向p.
3、查找p指针的先驱结点pre。
4、将pre的next指针指向q。
实现示意图如下:
解析:
1、插入操作需要
代码实现如下:
int ListInsert(LinkList * L, int i,int e)
{
int j;
LinkList p,s;
p=*L;
j=1;
while(p&&j<i)
{
p=p->Next;
j++;
}
if(!p||j>i)
return false;
s=(LinkList)malloc(sizeof( Node));//左边是结构体类型的指针,右边也需要强制转化为这种类型
p->data=e;
s->Next=p->Next;
p->Next=s;
return true;
}
- 单链表的删除操作
删除链表中的某个元素e,如果e在链表中出现不止一次,将删除第一次出现的e:
1)p是链表中的第一个结点
1、将L指向p->next。
2、释放p。
示意图如下:
2)p是链表中的其他结点
1、找到p的前驱结点pre。
2、将pre->next指向p->next。
3、释放p。
示意图如下:
具体实现代码如下:
int ListDelete(LinkList * L ,int i,int *e)
{
//查找到第i个位置
LinkList p,q;
int j=1;
p=*L;
while(p->Next&&j<i)//注意点,因为是删除,考虑的是链表的下一个元素是否为空
{
p=p->Next;
j++;
}
if(!(p->Next)||j>i)
return false;
q=p->Next;
p->Next=q->Next;
*e=q->data;
free(q);
return true;
}这里写代码片
资料参考
:http://blog.csdn.net/wp1603710463/article/details/50989500
上一篇: PHP 表单提交及处理表单数据详解及实例
下一篇: Android 图片缩放实例详解