链式存储结构【链表】的增 删 改 查 逆序输出 排序linkSeqlist
- 链表的特点
- 链表的描述
- 基本操作
-
- 创建空链表
- 第一种插入方式：头插
- 输出链表
- 求表长
- 查
- 第二种插入方式：任意位置插入新结点
- 删
- 逆序输出
- 排序
- 清空
- 销毁
此系列文主要用于自查、复习。所以行文、逻辑、思路是按照个人的思考方式来的，但也希冀能帮到一二三位初学者。
线性表的特点：
1.表头无前驱，表尾无后继
2.其他元素有且仅有一个直接前驱和一个直接后继
线性表有顺序存储结构和链式存储结构，下面介绍链式存储结构的单向链表。
链表的特点
优点： 删除和增加不会造成大量数据的移动
缺点： 查找、修改比较麻烦
链表的描述
描述： 数据域+指针域
typedef int datatype;
typedef struct node {
datatype data;//数据域
struct node * next;//保存下一个数据的地址
}linknode, * linklist;
基本操作
创建空链表
用malloc动态申请空间
linklist createLinkList()
{
//1.申请头结点的空间
linklist H = (linklist)malloc(sizeof(linknode));
if(NULL == H)
{
printf("创建头结点失败\n");
return NULL;
}
//2.给头结点赋值
H->data = 0;
H->next = NULL;
//3.返回头节点
return H;
}
第一种插入方式：头插
头插，新结点永远插入第一项（头结点不是第一项，头结点后面才是第一项）
int headInsertLinkList(linklist H, datatype x)
{
//1.申请新结点空间
linklist pnew = (linklist)malloc(sizeof(linknode));
if(NULL == pnew)
{
printf("申请新结点失败\n");
return -1;
}
//2.给新结点赋值
pnew->data = x;
//3.新结点先保存头结点下一个数据的地址
pnew->next = H->next;
//4.将新结点接入头结点后面
H->next = pnew;
return 0;
}
输出链表
void showLinkList(linklist H)
{
linklist p = H->next;
while(p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
求表长
int linkLength(linklist H)
{
linklist p = H;
int length = 0;
while(p->next != NULL)
{
p = p->next;
length++;
}
return length;
}
查
单链表中，取第i个元素必须从头结点出发寻找。
按位置查找，查找第pos项元素，返回其地址
linklist searchPos(linklist H, int pos)
{
int count = -1;//计数：记录遍历的次数
linklist p = H;
int length = linkLength(H);
if(pos<0 || pos>length)//1.判断位置是否合法
{
printf("位置不在表长范围内\n");
return NULL;
}
//2.依次遍历直到pos
while(count < pos)
{
p = p->next;
count++;
}
return p;
}
第二种插入方式：任意位置插入新结点
利用上面的查找函数searchPos()找到要插入的前一个位置
int insertLinklist(linklist H, int pos, datatype x)
{
//1.找到插入位置的前一项
linklist p;
if(0 == pos)
p = H;
else
p = search(H, pos-1);
if(NULL == p)
return -1;
//2.申请新结点
linklist pnew = (linklist)malloc(sizeof(linknode));
if(NULL == pnew)
{
printf("insert: 申请新结点失败\n");
return -1;
}
//3.给新结点赋值
pnew->data = x;
//“先连后断”
pnew->next = p->next;
p->next = pnew;
return 0;
}
删
删除结点
int deleteLinkList(linklist H, int pos)
{
//判空
if(NULL == H->next)
{
printf("链表为空\n");
return -1;
}
//p保存删除的前一个位置, q保存要删除的位置
linklist p = NULL, q = NULL;
if(pos>=0 && pos<=linkLength(H))//保证位置有效
{
if(pos == 0)
p = H;
else
p = searchPos(H, pos-1);
//保存删除结点
q = p->next;
//删除该结点
p->next = q->next;
//释放该结点
free(q);
q = NULL;
}
else
{
printf("deleteLinkList：the pos is error\n");
return -1;
}
return 0;
}
逆序输出
利用头插法
void reverseLinkList(linklist H)
{
//p保存无头链表的一个结点，q保存要接入头节点后面的结点
linklist p = NULL, q = NULL;
//1.一分为二，分为头结点和无头链表两部分
p = H->next;
H->next = NULL;
//2.依次从无头链表中取第一个结点出来头插
while(p != NULL)
{
//取无头链表的第一个结点
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
}
排序
void orderLinkList(linklist H)
{
linklist p = NULL;//保存无头链表的第一个结点
linklist q = NULL;//保存插入结点
linklist r = NULL;//保存要插入位置的前一个结点
//1.一分为二，分为头结点和无头链表两部分
p = H->next;
H->next = NULL;
//2.从无头链表中取第一个结点，有序插入到有头链表中
while(p != NULL)
{
//取无头链表的第一个结点
q = p;
p = p->next;
//从头开始找插入位置的前一个结点
r = H;
while(r->next && (r->next->data < q->data))
r = r->next;
//找到了，就插入该结点
q->next = r->next;
r->next = q;
}
}
清空
清空是将链表置空，头结点保留，表仍然可以用。
销毁不仅要将有效结点全部删除，头结点也要删除，表不再可用。
void clear(linklist H)
{
linklist p, q;
p = H->next;
while(p != NULL)
{
q = p;
p = p->next;
free(q);
}
}
销毁
void destroy(linklist H)
{
clear(H)；
free(H);
H = NULL;
}
测试
#include"linklist.h"
int main()
{
//1.调用函数创建一个空链表
linklist H = createLinkList();
if(NULL == H)
{
printf("创建空链表失败\n");
return -1;
}
//2.调用头插函数，向链表里新增数据
printf("head insert:\n");
headInsertLinkList(H, 111);
headInsertLinkList(H, 555);
headInsertLinkList(H, 333);
headInsertLinkList(H, 777);
headInsertLinkList(H, 666);
//3.调用打印函数，查看链表
showLinkList(H);
printf("search:\n");
linklist p = searchPos(H, 2);
printf("pos %d = %d\n", 2, p->data);
//4.任意位置插入数据
insertLinklist(H, 2, 777);
showLinkList(H);
//5.求表长
printf("length = %d\n", linkLength(H));
//6.删除结点
deleteLinkList(H, 0);
printf("delete: ");
showLinkList(H);
//7.逆序输出
reverseLinkList(H);
printf("reverse: ");
showLinkList(H);
//8.排序
printf("order: ");
orderLinkList(H);
showLinkList(H);
return 0;
}