线性表的基本概念
除了第一个元素无直接前驱，最后一个元素无直接后续之外，其他每个数据元素都有个一个前驱或后继。
线性表的基本特点
空表：如果线性表中的长度为0，则为空表
非空线性表和线性结构：
1.存在唯一一个被称作“第一个”的数据元素
2.存在唯一一个被称作“最后一个”的数据元素
3. 除了第一个之外，结构中每个数据元素均有一个前驱
4. 除了最后一个之外，结构中的每个元素均有一个后继
下面我们实现一个单向循环链表
1.定义结点
定义结点
2.初始化
初始化
3.插入元素
循环链表插入数据
```
StatusListInsert(LinkList*L,intplace,intnum){
LinkListtemp ,target;
inti;
if(place ==1) {
//如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 找到链表最后的结点_尾结点,
//3. 让新结点的next 执行头结点.
//4. 尾结点的next 指向新的头结点;
//5. 让头指针指向temp(临时的新结点)
temp = (LinkList)malloc(sizeof(Node));
if(temp ==NULL) {
returnERROR;
}
temp->data= num;
for(target = *L; target->next!= *L; target = target->next);
temp->next= *L;
target->next= temp;
*L = temp;
}else
{
//如果插入的位置在其他位置;
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
//3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
//4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
temp = (LinkList)malloc(sizeof(Node));
if(temp ==NULL) {
returnERROR;
}
temp->data= num;
for( i =1,target = *L; target->next!= *L && i != place -1; target = target->next,i++) ;
temp->next= target->next;
target->next= temp;
}
returnOK;
}
```
4.循环链表删除元素
```
Status LinkListDelete(LinkList*L,intplace){
LinkListtemp,target;
inti;
//temp 指向链表首元结点
temp = *L;
if(temp ==NULL)returnERROR;
if(place ==1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next== (*L)){
(*L) =NULL;
returnOK;
}
//②.链表还有很多数据,但是删除的是首结点;
//1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
//2. 新结点做为头结点,则释放原来的头结点
for(target = *L; target->next!= *L; target = target->next);
temp = *L;
*L = (*L)->next;
target->next= *L;
free(temp);
}else
{
//如果删除其他结点--其他结点
//1. 找到删除结点前一个结点target
//2. 使得target->next 指向下一个结点
//3. 释放需要删除的结点temp
for(i=1,target = *L;target->next!= *L && i != place -1;target = target->next,i++) ;
temp = target->next;
target->next= temp->next;
free(temp);
}
returnOK;
}
```
5.循环链表查询值
```
int findValue(LinkListL,intvalue){
inti =1;
LinkList p;
p = L;
//寻找链表中的结点 data == value
while(p->data!= value && p->next!= L) {
i++;
p = p->next;
}
//当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if(p->next== L && p->data!= value) {
return -1;
}
return i;
}
```
网友评论