最近又重学了一遍链表,记得大一学链表时也是很迷,指来指去没指明白哈哈哈。这一次学也是通透多了。
单链表
基本概念
定义
typedef struct Lnode{
int data ;
struct Lnode *next ;
}Lnode , *Linklist ;
- 结构体内两个元素
data、next data是int型,可修改为其他,例如char、doublenext是类型为struct Lnode的指针,可指向struct Lnode这种结构体,在链表中next指向下一个结点,例如1号结点的next=2号结点的地址Lnode是struct Lnode的别名 ,Linklist是struct Lnode *的别名
声明一个链表
Linklist HEAD = new Lnode ;
HEAD->next = NULL ;
Linklist HEAD与Lnode *HEAD等价,但我们一般用Linklist HEAD来定义链表(定义链表头结点,链表头结点即代表该链表)。用Lnode *p定义一个结点Linklist HEAD = new Lnode ;为头结点(头指针)分配一个大小为Lnode的空间。- 目前链表为空,头指针指向
NULL.HEAD->next表示HEAD下一个结点地址。 - 头指针
HEAD不能严格算一个结点,HEAD->data未定义。
加入结点
Lnode *p = new Lnode ;//第一个结点p
cin >> p->data ; //输入该结点存储的数据data
HEAD->next = p ;
p->next = NULL ;
- 再加一个结点
Lnode *q = new Lnode ;//第二个结点q
cin >> q->data ;
p->next = q ;
q->next = NULL ;
- 注意最后一个结点的
next应该指向NULL,否则q->next这个野指针无穷无尽。
常用函数操作
- 初始化链表(初始化头指针)
void InitList(Linklist &HEAD){
//调用InitList前得先声明HEAD,例如 Linklist linkedlist_1 ,linkedlist_1即是该链表的名称(用头指针来代表链表名称,类似于用地址a来代表数组)
HEAD = new Lnode ; //为HEAD声明一块Lnode大小的空间
HEAD->next = NULL ;
}
- 判断链表是否为空
int IsEmpty(Linklist &HEAD){
if(HEAD->next) return 0 ;//非空
return 1 ; //为空
}
- 销毁链表
void DestroyList(Linklist &HEAD){
Lnode *p ;
while(HEAD){
p = HEAD ;
HEAD = HEAD->next ;
delete p ;
}
}
- 清空链表
void ClearList(Linklist &HEAD){
Lnode *p , *q ;
p = HEAD ->next ;
HEAD->next = NULL ;
while(p){
q = p->next ;
delete p ;
p = q ;
}
}
tips:清空链表不释放头指针空间
- 获取链表长度
int GetLength(Linklist &HEAD){
Lnode *p = HEAD->next ;
int length = 0 ;
while(p){
length++ ;
p = p->next ;
}
return length ;
}
- 根据索引获取链表元素
int GetElem(Linklist &HEAD , int i){
if(i < 0 || i >= GetLength(HEAD)) {cout << "the index is invalid" << endl ; return 0 ;}
Lnode *p = HEAD->next ;
int j = 0 ;
while(j != i){
j++ ;
p = p->next ;
}
return p->data ;
}
- 根据值确定结点索引
int LocateElem(Linklist &HEAD , int value){
Lnode *p = HEAD->next ;
int i = 0 ;
while(p){
if(value == p->data) return i ;
p = p->next ;
i++ ;
}
cout << value << "not in this linkedlist" << endl ;
return -1 ;
}
- 插入结点
void ListInsert(Linklist &HEAD , int i , int data){
if(i < 0 || i > GetLength(HEAD)) {cout << "the index is invalid" << endl ; exit(0) ;}
Lnode *p = HEAD ;
int j = -1 ;
while(p && (j!=i-1)){
p = p->next ;
j++ ;
}
Lnode *s = new Lnode ;
s->data = data ;
s->next = HEAD->next ;
HEAD->next = s ;
cout << "Insert " << data << " in the index " << '[' << i << "] successfully !" << endl ;
}
tips: 此处p = HEAD从HEAD开始,j=-1 j从-1开始,是为了i=0的特殊情况。
- 删除元素
void DeleteElem(Linklist &L , int i){
if(i < 0 || i >= GetLength(L)) {cout << "the index i is invalid" << endl ; exit(0) ;}
Lnode *p = L ;
int j = -1 ;
while(p && (j!=i-1)){
p = p->next ;
j++ ;
}
Lnode *s = p->next ;
p->next = s->next ;
delete s ;
}
- 打印链表所有元素
void PrintList(Linklist &L){
Lnode *p = L->next ;
while(p){
cout << p->data << " " ;
p = p->next ;
}
cout << endl ;
}
- 头插法创建链表
void CreateList_H(Linklist &L , int n){
//insert the nodes from the head of linkedlist
L = new Lnode ;
L->next = NULL ;
for(int i = n - 1 ; i >= 0 ; i--){
Lnode *p = new Lnode ;
cin >> p->data ;
p->next = L->next ;
L->next = p ;
}
}
- 尾插法创建链表
void CreateList_T(Linklist &L , int n ){
//Insert elements from the tail of linkedlist
L = new Lnode ;
L->next = NULL ;
Lnode *T = L ;
for(int i = 0 ; i < n ; i++){
Lnode *p = new Lnode ;
cin >> p->data ;
T->next = p ;
T = T->next ;
p->next = NULL ;
}
双向链表
#include<iostream>
using namespace std ;
typedef struct DoubleLinkedList
{
int data ;
struct DoubleLinkedList *prior , *next ;
}DLNode , *DLList;
void InitDLList (DLList &HEAD){
HEAD = new DLNode ;
HEAD->next = NULL ;
HEAD->prior = NULL ;
}
void CreateList_DL(DLList &HEAD , int n){
for(int i = 0 ; i < n ; i++){
DLNode *p = new DLNode ;
cin >> p->data ;
p->next = HEAD->next ;
if(HEAD->next){
HEAD->next->prior = p ;
}
//i = 0 时,插入第一个元素时,HEAD->next 为NULL, NULL是没有的,即NULL->prior是访问不到的,segmentation fault
//因此当HEAD->next不为NULL时,才会执行HEAD->next->prior = p
//当HEAD->next 为NULL,也就是创建第一个结点时,不要让(也没法让)NULL->prior = p
HEAD->next = p ;
p->prior = HEAD ;
}
}
int GetLength_DL(DLList &HEAD){
int length = 0 ;
DLNode *p = HEAD->next;
while(p){
length++ ;
p = p->next ;
}
return length ;
}
void PrintList_DL(DLList &HEAD){
DLNode *p = HEAD->next ;
for(int i = 0 ; i < GetLength_DL(HEAD) ; i++){
cout << p->data << " " ;
p = p->next ;
}
cout << endl ;
}
void InsertList_DL(DLList &HEAD , int i , int data){
if( i < 0 || i > GetLength_DL(HEAD)) {cout << "the index is invalid" << endl ; exit(0) ;}
DLNode *p = HEAD ;
for(int j = 0 ; j < i ; j++){
p = p->next ;
}
DLNode *s = new DLNode ;
s->data = data ;
s->next = p->next ;
if(p->next){
p->next->prior = s ;
}
p->next = s ;
s->prior = p ;
}
void DeleteElem_DL(DLList &HEAD , int i){
if(i < 0 || i >= GetLength_DL(HEAD)) {cout << "the index is invalid " << endl ; exit(0) ;}
DLNode *p = HEAD->next ;
while(i--){
p = p->next ;
}
p->prior->next = p->next ;
p->next->prior = p->prior ;
delete p ;
}
int main(){
DLList HEAD ;
InitDLList(HEAD) ;
CreateList_DL(HEAD , 6) ;
PrintList_DL(HEAD) ;
InsertList_DL(HEAD , 2 , 821) ;
PrintList_DL(HEAD) ;
DeleteElem_DL(HEAD , 1) ;
PrintList_DL(HEAD) ;
return 0 ;
}