2.3 线性表的链式表示

abandon11 C语言 2023-10-20 20 0 原文

知识总览

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++;
}