2.3 线性表的链式表示
知识总览https://img2023.cnblogs.com/blog/2224132/202310/2224132-20231020223353908-1209017488.png
2.3.1 单链表的定义
知识总览
https://img2023.cnblogs.com/blog/2224132/202310/2224132-20231020223431809-1565739540.png
单链表定义#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct LNode{
int data;
struct LNode *next;
};
int main(){
struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));
return 0;
}typedef重命名
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
等同于
struct LNode{
int data;
struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
头插法建立单链表
头插法#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode));//创建头节点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入节点的值
while(x!=9999){ //输出9999表示结束
s=(LNode*)malloc(sizeof(LNode));//创建新节点
s->data=x;
s->next=L->next;
L->next=s; //将新节点插入表中，L为头指针
scanf("%d",&x);
}
return L;
}
int main(){
LinkList L;
List_HeadInsert(L);
}强调这是一个单链表 ————使用LinkList
强调这是一个节点 ————使用LNode*
不带头节点的单链表#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L=NULL; //空表，//防止脏数据
return true;
}
//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL);
}
int main(){
LinkList L; //声明一个指向单链表的指针 //此处并没有创建一个节点
InitList(L);
Empty(L);
}带头结点的单链表#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个单链表 (带头结点)
bool InitList(LinkList &L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=NULL;
return true;
}
//判断单链表是否为空 (带头结点)
bool Empty(LinkList L){
if(L->next==NULL)
returntrue;
else
return false;
}
int main(){
LinkList L; //声明一个指向单链表的指针
InitList(L);
Empty(L);
} 总结https://img2023.cnblogs.com/blog/2224132/202310/2224132-20231020223308250-1291823529.png 2.3.2.1知识总览https://img2023.cnblogs.com/blog/2224132/202310/2224132-20231020223639440-905294241.png 按位序插入（带头结点）#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个单链表 (带头结点)
bool InitList(LinkList &L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=NULL;
return true;
}
//判断单链表是否为空 (带头结点)
bool Empty(LinkList L){
if(L->next==NULL)
returntrue;
else
return false;
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i,int e){
if(i<1)
return false;
LNode *p;//指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点，头结点是第0个结点(不存数据)
while(p!=NULL&&j<i-1){ //循环找到第i-1 个结点 //找位置
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s; //将结点s连到p之后
return true; //插入成功
}
int main(){
LinkList L; //声明一个指向单链表的指针
InitList(L);
Empty(L);
ListInsert(L,1,9);
} 不带头节点
LNode * GetElem(LinkList L ,int i){
int j=1;
LNode *p=L->next;
if(i==0)
return L;
if(i
页:
[1]