目录
一、单链表的定义及初始化
1、定义
2、初始化
1)不带头结点的单链表
2)带头节的单链表
二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
2、按位插入（不带头结点）
3、指定结点的后插操作
4、指定结点的前插操作
2）删除
1、按位序删除（带头结点）
2、指定结点删除
3、指定最后结点的删除
三、查找
1）按位查找
2）按值查找
四、建立
1）头插法
2）尾插法
六、补充求单链表长度
一、单链表的定义及初始化
首先介绍一个关键字typedef ——数据类型重命名
typedef < 数据类型> <别名>
typedef struct LNode LNode
1、定义
typedef sturct LNode{ //定义单链表结点类型 ElemType date ; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点 }LNode, *LinkList; typedef LNode{ //定义单链表结点类型 ElemType date ; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点 }; typedef struct LNode LNode; typedef struct LNOde *LinkList; //上面俩个是等价的 struct LNode *p = (struct LNode*) malloc(sizeof(struct LNode)); /*增加一个新结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 */
要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个节点
LNode *L ; //声明一个指向单链表第一个结点的指针 （强调这是一个结点用LNode*）
或： LinkList L； //声明一个指向单链表的第一个结点的指针 （强调这是一个单链表LinkList）
2、初始化
1)不带头结点的单链表
bool InitList(LinkList &L) //初始化空链表 { L = NULL; //空表没有任何结点 return true; } void test() { LinkList L ; //声明一个指向单链表的指针 //初始化一个空表 InitList (L); }
判断是否为空
bool Empty(LinkList L){ if(L == NULL) return true; else return false; } //或： bool Empty(LinkList L){ return (L == NULL); }
2)带头节的单链表
//初始化一个单链表（带头结点） 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; }
二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
//在第i个位置插入元素e bool ListInsert(LinkList &L, int i,,ElemType 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->date = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true; }
2、按位插入（不带头结点）
bool ListInsert(LinkList &L, int i,,ElemType e){ if( i < 1) return false; if(i == 1){ LNode *s = (LNode *s)malloc(sizeof(LNode)); s->date = e; s->next = L; L = s; return true; } 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->date = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true; }
3、指定结点的后插操作
bool InsertNextNode (LNode *p ,Elemtype e){ if( p == NULL) return false； LNode *s = (LNode *) malloc(sizeof(LNode)); if (s == NULL) //内存分配失败 return false; s->date = e; //用结点s保存数据元素e s->next = p->next; p->next = s; //将结点s连接到p之后 return true; }
4、指定结点的前插操作
bool InsertPriorNode (LNode *p,ElemType e){ if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL) return false; s->next = p->next; p->next = s; //新节点s连到p之后 s->date = p->date; //将p之中元素复制到s中 p->date = e; //p中元素覆盖W为e } //时间复杂度为O(1)
2）删除
1、按位序删除（带头结点）
//按位序删除（带头结点） bool ListDelete(LinkList &L,int i,ElemType &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) return false; //i值不合法 if(p->next == NULL) return false; //第i-1个节点之后没有其他节点 LNode *q = p->next; //q指向被删除的节点 e = q->data; p->next = q->next; free(q); return true; }
2、指定结点删除
//指定节点的删除 bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *q = p->next; //q指向*p的后继节点 p->data = p->next->data; //p的后继节点数据赋值给p p->next = q->next; //q节点从链中断开 free(q); //释放 return true; }
3、指定最后结点的删除
//指定节点的删除 bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *q = p->next; //q指向*p的后继节点 p->data = p->next->data; //p的后继节点数据赋值给p p->next = q->next; //q节点从链中断开 free(q); //释放 return true; }
三、查找
1）按位查找
//按位查找，返回第i各元素带头节点 LNode * GetElem(LinkList L,int i){ if(i<0){ return NULL; } LNode *p; // 指针p指向当前扫描到的结点 int j = 0; p = L; //L指向头结点 , L是第0个结点（不存放数据） while(p!=NULL && j < i){ //循环到第i个结点 p = p->next; j++; } return p; }
2）按值查找
//按值查找，返回e元素 //带头节点 LNode * GetElem(LinkList L,ElemType e){ LNode *p = L->next; //从第一个结点开始查找数据域为e的结点 while(p!=NULL && p->data != e){ p = p -> next; } return p; }
四、建立
1）头插法
//头插法 LinkList List_HeadInsert(LinkList &L){ int x; //假设ElemType为整型 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s; //r为表尾指针 L->next = NULL; //初始尾空链表 （必须初始化） scanf("%d",&x); while(x!=9999) { s = (LNode*)malloc(sizeof(LNode)); s->next = L->next; s->data = x; L->next = s; //头结点指向新的结点 scanf("%d",&x); } return L; }
2）尾插法
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; } //尾插法建立单链表： 初始化单链表长度 /* while 循环{ 每次取一个数据元素e ListInsert(L,length+1,e) ; length++; } 时间复杂度：O（n2） */ LinkList List_TailInsert(LinkList &L){ int x; //假设ElemType为整型 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s,*r=L; //r为表尾指针 scanf("%d",&x); while(x!=9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; //r始终指向表尾 scanf("%d",&x); } r->next = NULL; //尾结点置空 return L; } int main(){ LinkList L; //声明一个指向单链表的指针 InitList(L);//初始化一个空表 List_TailInsert(L); return 0; }
六、补充求单链表长度
//求单链表的长度 int Length (LinkList L){ int len = 0; //统计表长 LNode *p = L; while(p->next != NULL){ p = p->next; len++; } return len; }
