线性表的链式存储结构-单链表(c语言版)
温馨提示:
本文最后更新于 2021年02月24日,已超过 1,380 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我。
什么是链式存储?
借助元素存储地址的指针表示数据元素之间的逻辑关系。
什么是线性表的链式存储结构?
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
线性表(链式存储)的基本操作
1.初始化
2.销毁
3.清空
4.获取长度
5.判空
6.取值
7.插入
8.删除
定义结构体
//定义一个链表的结点(元素)
typedef struct LNode{
int data;//数据域
struct LNode *next;//指向自己类型的指针域
}LNode,*LinkList;//LinkList 为LNode类型的指针
初始化单链表
//(1)初始化操作
int InitList_L(LinkList &L) {
L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点
L->next=NULL;
return 0;
}
销毁单链表
//(2)销毁链表
int DestroyList_L(LinkList &L){
LinkList p;
while(L){
p = L;
L = L->next;
free(p);
}
return 0;
}
清空单链表
//(3)清空链表
int ClearList_L(LinkList &L){
LinkList p,q;
p=L->next; //指向第一个结点
while(p){
q=p->next;
free(p);
p=q;
}
L->next = NULL;//头结点的指针域指向NULL
return 0;
}
获取单链表的长度
//(4)获取链表的长度
int GetListLength_L(LinkList L){
LinkList p = L->next;
int j = 0;
while(p){
p = p->next;
j++;
}
return j;
}
判断单链表是否为空
//(5)判断链表是否为空
int IsEmpty(LinkList L){
if(L->next){
return 0;
}else{
return 1;
}
}
获取单链表中指定位置的元素
//(6)取值(获取链表指定位置的数据)
int GetElem_L(LinkList L,int i){
int j=0;
LinkList p=L->next;
while(p&&j<i-1){
p = p->next;
j++;
}
return p->data;
}
向单链表中插入一个元素
//(7)插入 在链表的指定位置插入元素
int InsertList_L(LinkList &L,int i,int data) {
LinkList p = L ;int j = 0;
while(p&&j<i-1){ //寻找插入结点的位置
p = p->next;
++j;
}//当j>=i时 p 所指的位置为需要插入的位置
if(!p) return 1; //链表为空 或 插入位置大于表长
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = data;
s->next = p->next;
p->next = s;
return 0;
}
删除单链表中指定位置的元素
//(8)删除 删除指定位置的元素
int DeleteList_L(LinkList &L,int i){
LinkList p = L;
int j=0;
while(p&&j<i-1){
p = p->next;
++j;
}
if(!(p->next)) return 1;
LinkList q = p->next;//临时保存需要删除的结点
p->next = q->next;
free(q);
return 0;
}
完整代码
#include <stdio.h>
#include <stdlib.h>
//定义一个链表的结点(元素)
typedef struct LNode{
int data;//数据域
struct LNode *next;//指向自己类型的指针域
}LNode,*LinkList;//LinkList 为LNode类型的指针
//(1)初始化操作
int InitList_L(LinkList &L) {
L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点
L->next=NULL;
return 0;
}
//(2)销毁链表
int DestroyList_L(LinkList &L){
LinkList p;
while(L){
p = L;
L = L->next;
free(p);
}
return 0;
}
//(3)清空链表
int ClearList_L(LinkList &L){
LinkList p,q;
p=L->next;//指向第一个结点
while(p){
q=p->next;
free(p);
p=q;
}
p->next = NULL;//头结点的指针域指向NULL
return 0;
}
//(4)获取链表的长度
int GetListLength_L(LinkList L){
LinkList p = L->next;
int j = 0;
while(p){
p = p->next;
j++;
}
return j;
}
//(5)判断链表是否为空
int IsEmpty(LinkList L){
if(L->next){
return 0;
}else{
return 1;
}
}
//(6)取值(获取链表指定位置的数据)
int GetElem_L(LinkList L,int i){
int j=0;
LinkList p=L->next;
while(p&&j<i-1){
p = p->next;
j++;
}
return p->data;
}
//(7)插入 在链表的指定位置插入元素
int InsertList_L(LinkList &L,int i,int data) {
LinkList p = L ;int j = 0;
while(p&&j<i-1){ //寻找插入结点的位置
p = p->next;
++j;
}//当j>=i时 p 所指的位置为需要插入的位置
if(!p) return 1; //链表为空 或 插入位置大于表长
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = data;
s->next = p->next;
p->next = s;
return 0;
}
//(8)删除 删除指定位置的元素
int DeleteList_L(LinkList &L,int i){
LinkList p = L;
int j=0;
while(p&&j<i-1){
p = p->next;
++j;
}
if(!(p->next)) return 1;
LinkList q = p->next;//临时保存需要删除的结点
p->next = q->next;
free(q);
return 0;
}
main(){
LinkList L;
//初始化
int initStatus;//初始化状态
int isEmpty;//是否为空
int insertStatus;//插入状态
int deleteStatus;//删除状态
int listLength;//链表长度
int destroyStatus;//销毁状态
initStatus = InitList_L(L);
if(initStatus==0){
printf("初始化成功!\n");
} else{
printf("初始化失败!\n");
}
isEmpty = IsEmpty(L);
if(isEmpty==0){
printf("链表不为空\n");
} else{
printf("链表为空\n");
}
insertStatus = InsertList_L(L,1,1); //插入元素 1
insertStatus = InsertList_L(L,2,2); //插入元素 2
insertStatus = InsertList_L(L,2,3); //插入元素 3
if(insertStatus==0){
printf("插入成功!\n");
}else{
printf("插入失败!\n");
}
listLength = GetListLength_L(L);
printf("插入后链表长度: %d\n",listLength);
isEmpty = IsEmpty(L);
if(isEmpty==0){
printf("链表不为空\n");
} else{
printf("链表为空\n");
}
int t5 = GetElem_L(L,3);
printf("第三个位置元素为: %d\n",t5);
deleteStatus = DeleteList_L(L,2);
if(deleteStatus==0){
printf("删除成功\n");
}else{
printf("删除失败\n");
}
listLength = GetListLength_L(L);
printf("删除后链表长度: %d\n",listLength);
destroyStatus = DestroyList_L(L);
if(destroyStatus==0){
printf("销毁成功\n");
} else{
printf("销毁失败\n");
}
}
正文到此结束
- 本文标签: c语言 数据结构 线性表
- 本文链接: https://www.it1997.com/article/36
- 版权声明: 本文由小陈没烦恼原创发布,转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权