基础数据结构与算法之链表-C语言实现

结构定义：

将一个链表类型定义为一个指向一个链表节点LNode的指针，LNode分为数据域和指针域，代码实现如下：

typedef int ElementType;
typedef struct LNode* List;
struct LNode {
ElementType Data;
List Next;
};

求表长：

只要当前指针非空，就不断指向下一个节点，并将计数器++即可，最后返回计数器的值。易知该操作时间复杂度为O(n)，代码实现如下：

int Length(List PtrL) {
int j = 0;
List p = PtrL;
while (p) {
p = p->Next;
j++;
}
return j;
}

按序号查找：

跟求表长操作类似，只要当前指针非空并且计数器值<序号值，就不断指向下一个节点。检查跳出循环时计数器的值，如果等于序号，说明找到了，返回节点的指针；否则说明没找到，返回NULL。查找的时间复杂度为O(n)，代码实现如下：

List FindKth(List PtrL, int k) {
List p = PtrL;
int i = 1;
while (p != NULL && i < k) {
p = p->Next;
i++;
}
if (i == k)
return p;
else
return NULL;
}

按值查找：

循环过程中检查p指向的节点的数据是否等于被查找元素的值即可，时间复杂度为O(n)，代码实现如下：

List Find(ElementType x, List PtrL) {
List p = PtrL;
while (p != NULL && p->Data != x)
p = p->Next;
return p;
}

插入操作：

如果插入位置为1，说明插入位置在第一个：
首先申请节点空间，然后将数据x装填进去，最后令Next指向原来的链表，返回新申请的节点地址即可；

否则：
则需要用FindKth函数找到插入位置的前驱节点p，然后新申请一块空间s并装填数据，接着令s的Next指向p的Next，p的Next指向s，注意操作顺序，最后返回原链表指针即可。

插入操作的时间复杂度为O(n)，时间主要花在了FindKth查找插入位置上，代码实现如下：

List Insert(ElementType x, int i, List PtrL) {
List s, p;
if (i == 1) {
List s = (List)malloc(sizeof(struct LNode));
s->Data = x;
s->Next = PtrL;
return s;
}
p = FindKth(PtrL, i - 1);
if (!p) {
printf("参数i错n");
return NULL;
} else {
List s = (List)malloc(sizeof(struct LNode));
s->Data = x;
s->Next = p->Next;
p->Next = s;
return PtrL;
}
}

删除指定元素：

如果要删除第一个元素：
如果指针为空，则说明是空表，返回NULL即可；
否则，用s指向第一个节点，然后PtrL指向PtrL->Next，这样就跳过了第一个节点，最后释放掉第一个节点的内存，返回新的表头节点指针。

否则，找到第i个节点的前驱p：
如果p为空，说明前驱不存在，报错返回；
如果p的Next为空，说明前驱是最后一个节点，也就是要删除的节点不存在，报错返回。
否则，令s指向待删除的节点，p的Next指向s的Next，然后释放掉s的内存，返回原链表指针即可。

删除操作的时间复杂度也为O(n)，同样的，其时间也是花在了查找元素上。代码实现如下：

List Delete(int i, List PtrL) {
List s, p;
if (i == 1) {
if (!PtrL) {
return NULL;
} else {
s = PtrL;
PtrL = PtrL->Next;
free(s);
return PtrL;
}
}
p = FindKth(PtrL, i - 1);
if (p == NULL) {
printf("第%d节点不存在n", i - 1);
return NULL;
} else if (p->Next == NULL) {
printf("第%d节点不存在n", i);
return NULL;
} else {
s = p->Next;
p->Next = s->Next;
free(s);
return PtrL;
}
}

销毁链表：

为避免产生内存泄露，线性表不用了的话归还申请的空间，代码实现如下：

void Destory(List PtrL) {
List p = PtrL;
List s;
while (p) {
s = p;
p = p->Next;
free(s);
}
return;
}

最后

以上就是繁荣微笑为你收集整理的基础数据结构与算法之链表-C语言实现的全部内容，希望文章能够帮你解决基础数据结构与算法之链表-C语言实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。