至今头条

2.3 线性表的链式表示

2023-10-20 19:39 由 abandon11 发表于 #后端开发

知识总览

2.3.1 单链表的定义

知识总览

单链表定义 
#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)
	   return  true;
	else
	   return false;
} 
int main(){
	LinkList L; //声明一个指向单链表的指针 
	InitList(L);
	Empty(L); 
}
 
总结
 
 
 
2.3.2.1
知识总览
 
 
 
 
按位序插入（带头结点） 
#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)
	   return  true;
	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)
   return NULL;
  while(p!=NULL&&j<i){
   p=p->next;
   j++;
}

热门相关：重生之女将星   我是仙凡   紫府仙缘   慕少，你老婆又重生了   重生之将门毒后