如果要对链表进行插入删除操作,用顺序结构需要找到目标位置然后移动大量元素,复杂度为O(n),此时就需要考虑线性表的链式存储结构。
链式线性表由n个结点通过指针域连接而成。最简单的链表为单链表。如图:
单链表的抽象数据类型描述:
数据对象集合:
{a1,a2,a3,... ,an},每个元素类型为DataType,除了a1和an外每个元素都只有一个前驱元素一个后继元素,数据元素之间的关系是一对一
基本操作集合:
(1)void InitList(LinkList *L):初始化单链表L。
(2)void Insert(LinkList *L, int i, DataType e):把元素e插入到单链表L的第i个位置。
(3)int ListLength(LinkList *L):返回单链表L的长度。
(4)void Delete(LinkList *L, int i, DataType *e):删除链表中位置i的元素,保存到e中。
(5)DataType GetElem(LinkList *L, int i):返回链表中第i个位置的元素。
(6)int LocateElem(LinkList L, DataType e):返回链表中第一个与e相同的元素的下标。
(7)void DestroyList(LinkList *L):摧毁单链表。
代码:
PS:下面代码没有下标0,头结点在main函数中malloc
#include <cstdio>
#include <cstdlib>
typedef int DataType;
struct LinkList
{
DataType data;
struct LinkList *next;
};
//初始化单链表(将头结点的指针域设置为空,数据域设置为0,数据域代表链表长度)
void InitList(LinkList *L)
{
L->next = NULL;
L->data = 0;
return;
}
int ListLength(LinkList *L)
{
return L->data;
}
void Insert(LinkList *L, int i, DataType e)
{
LinkList *p, *q;
p = L;
int len = L->data;
//i最大为链表长度+1(插到末尾),最小为1
if(i > len + 1 || i < 1)
printf("Wrong place!\n");
//将指针p移动到i的前一个位置
for(int j = 1; j < i;j++)
{
p = p->next;
}
//找到位置后,新建一个结点,数据域为e
q = (LinkList*)malloc(sizeof(LinkList));
q->data = e;
q->next = p->next;
p->next = q;
L->data++;
return;
}
DataType GetElem(LinkList *L, int i)
{
LinkList *p;
p = L->next;
for(int j = 1; j < i; j++)
{
p = p->next;
}
return p->data;
}
int LocateElem(LinkList *L, DataType e)
{
LinkList *p;
int i = 1;
p = L->next;
while(p->data != e && i < L->data)
{
p = p->next;
i++;
}
if(p->data == e)
{
return i;
}
if(i == L->data)
{
printf("No such element!\n");
return -1;
}
}
void Delete(LinkList *L, int i, DataType *e)
{
if(i < 1 || i > L->data)
{
printf("Wrong place!\n");
return;
}
if(L->data == 0)
{
printf("List is empty!\n");
return;
}
LinkList *p, *q;
p = L;
//p移动到要删除位置的前面
for(int j = 1; j < i; j++)
{
p = p->next;
}
//要删除元素赋值给q
q = p->next;
*e = q->data;
//如果q的下一位存在
if(q->next)
{
p->next = q->next;
}
else
p->next = NULL;
free(q);
L->data--;
return;
}
void PrintList(LinkList *L)
{
for(int i = 1; i <= L->data; i++)
printf("%d ", GetElem(L, i));
printf("\n");
}
//销毁链表,包括头结点
void DestroyList(LinkList *L)
{
LinkList *p;
while(L)
{
p = L;
L = L->next;
free(p);
}
return;
}
//测试代码
int main()
{
LinkList *L = (LinkList*)malloc(sizeof(LinkList));
InitList(L);
for(int i = 0; i <= 10; i++)
Insert(L, i + 1, i);
DestroyList(L);
InitList(L);
Insert(L, 0, 1);
Insert(L, 2, 2);
Insert(L, 1, 100);
PrintList(L);
int locate = LocateElem(L, 600);
printf("Element 6's place: %d\n", locate);
printf("%d\n", L->data);
DataType delete_e;
Delete(L, 2, &delete_e);
PrintList(L);
printf("%d\n", L->data);
DestroyList(L);
printf("%d",GetElem(L, 1));
return 0;
}