1、静态链表
这个给我的感觉就是数组加了索引，它的目的就是要融合顺序表和链表的优点，能够快速的访问元素，也能快速的增加或删除元素。
整个的组成如图所示，第一列的数据是位置，第二列是数据
2、双向链表
双向链表概念是区别于单链表而言的，就是多了一个前驱，组成示意图如下所示：
常见结构如下所示：
typedef struct line{
struct line *prior;
int data;
struct line *next;
}line;
下面创建双向链表，基本和单链表创建类似，跟着来
line *initLine(line *head)
{
head = (line*)malloc(sizeof(line));
head->prior=NULL;
head->next=NULL;
head->data=1;
line *list=head;
for(int i=2; i<=5; i++)
{
line *body=(line*)malloc(sizeof(line));
body->prior=NULL;
body->next=NULL;
body->data=i;
list->next=body; /*指向下一个节点*/
body->prior=list;/*body的prior指向前一个*/
list=list->next;/*更新当前list*/
}
return head;
}
基本操作的增删查改也类似，下面贴出完整代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct line{
struct line *prior;
int data;
struct line *next;
}line;
line *initLine(line *head)
{
head = (line*)malloc(sizeof(line));
head->prior=NULL;
head->next=NULL;
head->data=1;
line *list=head;
for(int i=2; i<=5; i++)
{
line *body=(line*)malloc(sizeof(line));
body->prior=NULL;
body->next=NULL;
body->data=i;
list->next=body; /*指向下一个节点*/
body->prior=list;/*body的prior指向前一个*/
list=list->next;/*更新当前list*/
}
return head;
}
void display(line *head)
{
line *temp = head;
while (temp)
{
if(temp->next == NULL)
printf("%d\n", temp->data);
else
printf("%d <-> ", temp->data);
temp = temp->next;
}
}
line *insertLine(line *head, int data, int add)
{
line *temp = (line*)malloc(sizeof(line));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
if(add == 1) /*插入到表头*/
{
temp->next = head;
head->prior = temp;
head=temp;
}
else{
line *body = head;
/*注册到插入位置的前一个节点*/
for(int i=1; i<add-1; i++)
{
body = body->next;
}
if(body->next == NULL) /*如果这个位置是尾部*/
{
body->next = temp;
temp->prior = body;
}
else{
body->next->prior = temp;
temp->next = body->next;
body->next = temp;
temp->prior = body;
}
}
return head;
}
line *delLine(line *head, int data)
{
line *temp = head;
while (temp)
{
if(temp->data == data)
{
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
return head;
}
temp = temp->next;
}
printf("链表中无该元素 \n");
return head;
}
int selectElem(line *head, int elem)
{
line *t = head;
int i = 1;
while (t)
{
if(t->data == elem)
{
return i;
}
i++;
t = t->next;
}
return -1;
}
line *amendElem(line *p, int add, int newElem)
{
line *temp = p;
for(int i=1; i < add; i++)
{
temp = temp->next;
}
temp->data = newElem;
return p;
}
int main()
{
line *head = NULL;
head = initLine(head);
display(head);
printf("链表中第 4 个节点的直接前驱是：%d\n",head->next->next->next->prior->data);
head=insertLine(head, 7, 3);
display(head);
//表中删除元素 2
head=delLine(head, 2);
display(head);
printf("元素 3 的位置是：%d\n",selectElem(head,3));
//表中第 3 个节点中的数据改为存储 6
head = amendElem(head,3,6);
display(head);
exit(0);
}
3、循环链表
也就是说，当链表里面的最后一个的指针指向头结点，这样就构成了一个循环的链表，当然就是说一个大链表内部也可能有小的环链。
下面看一个循环链表的创建：
typedef struct node
{
int number;
struct node *next;
}person;
person *initLink(int n)
{
person *head = (person*)malloc(sizeof(person));
head->number = 1;
head->next = NULL;
person *cyclic = head;
for(int i=2; i<=n; i++)
{
person *body = (person*)malloc(sizeof(person));
body->number = i;
body->next = NULL;
cyclic->next = body;
cyclic = cyclic->next;
}
cyclic->next = head;
return head;
}
完整的循环链表的增删查改的操作：
/*
2023 11 03 c语言中文网，数据结构-线性表
主要循环链表的创建
*/
#include <stdio.h>
#include <stdlib.h>
/*需要将表中最后一个节点的尾部指针指向头节点*/
typedef struct node
{
int number;
struct node *next;
}person;
person *initLink(int n)
{
person *head = (person*)malloc(sizeof(person));
head->number = 1;
head->next = NULL;
person *cyclic = head;
for(int i=2; i<=n; i++)
{
person *body = (person*)malloc(sizeof(person));
body->number = i;
body->next = NULL;
cyclic->next = body;
cyclic = cyclic->next;
}
cyclic->next = head;
return head;
}
void findAndKillK(person *head, int k, int m)
{
person *tail = head;
while (tail->next != head)
{
tail = tail->next;
}
person *p = head;
while (p->number != k)
{
tail = p;
p = p->next;
}
while (p->next != p)
{
for(int i=1; i<m; i++)
{
tail=p;
p=p->next;
}
tail->next = p->next;
printf("出列人的编号为%d \n", p->number);
free(p);
p = tail->next;
}
printf("出列人的编号为%d \n", p->number);
free(p);
}
int main()
{
printf("输入圆桌上的人数n:");
int n;
scanf("%d",&n);
person * head=initLink(n);
printf("从第k人开始报数(k>1且k<%d)：",n);
int k;
scanf("%d",&k);
printf("数到m的人出列：");
int m;
scanf("%d",&m);
findAndKillK(head, k, m);
exit(0);
}