数据结构之链表

xiangzhihong

发布于 2018-02-01 16:34:28

5580

发布于 2018-02-01 16:34:28

文章被收录于专栏：向治洪向治洪

一、概念

（1）数组的线性序是由数组的下标决定的，链表中的顺序是由各对象中的指针所决定的

（2）链表结点结构

node *prev;

node *next;

int key;

（3）链表结点

node *head;

node *nil;//哨兵

（4）对链表的操作

LIST-SEARCH(L, k)

LIST-INSERT(L, x)

LIST-DELETE(L, x)

（5）哨兵是个哑对象，可以简化边界条件

二、代码

（1）没有哨兵的情况

//链表结点结构 
struct node  
{  
    node *pre;  
    node *next;  
 int key;  
 //构造函数 
    node(int x):pre(NULL),next(NULL),key(x){}  
};  
//链表结构 
struct List  
{  
    node *head;  
    List():head(NULL){}  
};  
//打印 
void List_Print(List *L)  
{  
    node *p = L->head;  
 while(p)  
    {  
        cout<<p->key<<' ';  
        p = p->next;  
    }  
    cout<<endl;  
}  
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL 
node *List_Search(List *L, int k)  
{  
    node *x = L->head;  
 while(x != NULL && x->key!=k)  
        x = x->next;  
 return x;  
}  
//插入 
void List_Insert(List *L, node *x)  
{  
 //插入到表的前端 
    x->next = L->head;  
 if(L->head != NULL)  
        L->head->pre = x;  
    L->head = x;  
    x->pre = NULL;  
}  
//删除 
void List_Delete(List *L, node* x)  
{  
 if(x->pre != NULL)  
        x->pre->next = x->next;  
 else 
        L->head = x->next;  
 if(x->next != NULL)  
        x->next->pre = x->pre;  
 delete x;  
}

//链表结点结构
struct node
{
	node *pre;
	node *next;
	int key;
	//构造函数
	node(int x):pre(NULL),next(NULL),key(x){}
};
//链表结构
struct List
{
	node *head;
	List():head(NULL){}
};
//打印
void List_Print(List *L)
{
	node *p = L->head;
	while(p)
	{
		cout<<p->key<<' ';
		p = p->next;
	}
	cout<<endl;
}
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL
node *List_Search(List *L, int k)
{
	node *x = L->head;
	while(x != NULL && x->key!=k)
		x = x->next;
	return x;
}
//插入
void List_Insert(List *L, node *x)
{
	//插入到表的前端
	x->next = L->head;
	if(L->head != NULL)
		L->head->pre = x;
	L->head = x;
	x->pre = NULL;
}
//删除
void List_Delete(List *L, node* x)
{
	if(x->pre != NULL)
		x->pre->next = x->next;
	else
		L->head = x->next;
	if(x->next != NULL)
		x->next->pre = x->pre;
	delete x;
}

（2）有哨兵的情况

//链表结点结构 
struct node  
{  
    node *pre;  
    node *next;  
 int key;  
 //构造函数 
    node(int x):pre(NULL),next(NULL),key(x){}  
};  
//链表结构 
struct List  
{  
    node *nil;//哨兵 
    List()  
    {  
        nil = new node(0);  
        nil->next = nil;  
        nil->pre = nil;  
    }  
};  
//打印 
void List_Print(List *L)  
{  
    node *p = L->nil->next;  
 while(p != L->nil)  
    {  
        cout<<p->key<<' ';  
        p = p->next;  
    }  
    cout<<endl;  
}  
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL 
node *List_Search(List *L, int k)  
{  
    node *x = L->nil->next;  
 while(x != L->nil && x->key!=k)  
        x = x->next;  
 return x;  
}  
//插入 
void List_Insert(List *L, node *x)  
{  
 //插入到表的前端 
    x->next = L->nil->next;  
    L->nil->next->pre = x;  
    L->nil->next = x;  
    x->pre = L->nil;  
}  
//删除 
void List_Delete(List *L, node* x)  
{  
    x->pre->next = x->next;  
    x->next->pre = x->pre;  
 delete x;  
}

//链表结点结构
struct node
{
	node *pre;
	node *next;
	int key;
	//构造函数
	node(int x):pre(NULL),next(NULL),key(x){}
};
//链表结构
struct List
{
	node *nil;//哨兵
	List()
	{
		nil = new node(0);
		nil->next = nil;
		nil->pre = nil;
	}
};
//打印
void List_Print(List *L)
{
	node *p = L->nil->next;
	while(p != L->nil)
	{
		cout<<p->key<<' ';
		p = p->next;
	}
	cout<<endl;
}
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL
node *List_Search(List *L, int k)
{
	node *x = L->nil->next;
	while(x != L->nil && x->key!=k)
		x = x->next;
	return x;
}
//插入
void List_Insert(List *L, node *x)
{
	//插入到表的前端
	x->next = L->nil->next;
	L->nil->next->pre = x;
	L->nil->next = x;
	x->pre = L->nil;
}
//删除
void List_Delete(List *L, node* x)
{
	x->pre->next = x->next;
	x->next->pre = x->pre;
	delete x;
}

三、练习

10.2-1  
能，能  
10.2-2  
//结点 
struct node  
{  
    node *pre;//为了方便实现出栈操作 
    node *next;  
 int key;  
    node(int x):pre(NULL),next(NULL),key(x){}  
};  
//链式栈 
struct list  
{  
    node *Head;//栈的起始结点 
    node *Top;//栈顶指针 
    list(){Head = new node(0);Top = Head;}  
};  
//打印栈中的元素 
void Print(list *L)  
{  
    node *p = L->Head->next;  
 while(p)  
    {  
        cout<<p->key<<' ';  
        p = p->next;  
    }  
    cout<<endl;  
}  
//入栈 
void Push(list *L, int x)  
{  
 //构造一个新的结点 
    node *A = new node(x);  
 //链入到栈顶位置，修改指针 
    L->Top->next = A;  
    A->pre = L->Top;  
    L->Top = A;  
}  
//出栈 
int Pop(list *L)  
{  
 if(L->Head == L->Top)  
    {  
        cout<<"error:underflow"<<endl;  
 return -1;  
    }  
 //取出栈顶元素 
 int ret = L->Top->key;  
 //修改指针 
    node *A = L->Top;  
    L->Top = A->pre;  
    L->Top->next = NULL;  
 delete A;  
 return ret;  
}  
10.2-3  
//结点 
struct node  
{  
    node *next;  
 int key;  
    node(int x):next(NULL),key(x){}  
};  
//链式队列 
struct list  
{  
    node *Head;//头指针 
    node *Tail;//尾指针 
    list(){Head = new node(0);Tail = Head;}  
};  
//打印 
void Print(list *L)  
{  
    node *p = L->Head->next;  
 while(p)  
    {  
        cout<<p->key<<' ';  
        p = p->next;  
    }  
    cout<<endl;  
}  
//入队列 
void Enqueue(list *L, int x)  
{  
 //构造一个新的结点 
    node *A = new node(x);  
 //链入尾部，修改指针 
    L->Tail->next = A;  
    L->Tail = A;  
}  
//出队列 
int Dequeue(list *L)  
{  
 if(L->Head == L->Tail)  
    {  
        cout<<"error:underflow"<<endl;  
 return -1;  
    }  
 //取出队头结点，修改指针 
    node *A = L->Head->next;  
 int ret = A->key;  
    L->Head->next = A->next;  
 if(A == L->Tail)  
        L->Tail = L->Head;  
 delete A;  
 return ret;  
}  
10.2-4  
把哨兵的值置为一个不可能与x相等的值

10.2-1
能，能
10.2-2
//结点
struct node
{
	node *pre;//为了方便实现出栈操作
	node *next;
	int key;
	node(int x):pre(NULL),next(NULL),key(x){}
};
//链式栈
struct list
{
	node *Head;//栈的起始结点
	node *Top;//栈顶指针
	list(){Head = new node(0);Top = Head;}
};
//打印栈中的元素
void Print(list *L)
{
	node *p = L->Head->next;
	while(p)
	{
		cout<<p->key<<' ';
		p = p->next;
	}
	cout<<endl;
}
//入栈
void Push(list *L, int x)
{
	//构造一个新的结点
	node *A = new node(x);
	//链入到栈顶位置，修改指针
	L->Top->next = A;
	A->pre = L->Top;
	L->Top = A;
}
//出栈
int Pop(list *L)
{
	if(L->Head == L->Top)
	{
		cout<<"error:underflow"<<endl;
		return -1;
	}
	//取出栈顶元素
	int ret = L->Top->key;
	//修改指针
	node *A = L->Top;
	L->Top = A->pre;
	L->Top->next = NULL;
	delete A;
	return ret;
}
10.2-3
//结点
struct node
{
	node *next;
	int key;
	node(int x):next(NULL),key(x){}
};
//链式队列
struct list
{
	node *Head;//头指针
	node *Tail;//尾指针
	list(){Head = new node(0);Tail = Head;}
};
//打印
void Print(list *L)
{
	node *p = L->Head->next;
	while(p)
	{
		cout<<p->key<<' ';
		p = p->next;
	}
	cout<<endl;
}
//入队列
void Enqueue(list *L, int x)
{
	//构造一个新的结点
	node *A = new node(x);
	//链入尾部，修改指针
	L->Tail->next = A;
	L->Tail = A;
}
//出队列
int Dequeue(list *L)
{
	if(L->Head == L->Tail)
	{
		cout<<"error:underflow"<<endl;
		return -1;
	}
	//取出队头结点，修改指针
	node *A = L->Head->next;
	int ret = A->key;
	L->Head->next = A->next;
	if(A == L->Tail)
		L->Tail = L->Head;
	delete A;
	return ret;
}
10.2-4
把哨兵的值置为一个不可能与x相等的值

10.2-5

见算法导论 10.2-5 环形链表实现字典操作INSERT、DELETE、SEARCH

10.2-6

使用带尾指针的链表，令A的尾指针为tail，tail->next=B

10.2-7

//逆转 
void Reverse(list *L)  
{  
    node *p = NULL, *q = L->Head, *r;  
 //依次修改指针，让q是p->next,令q->next=p 
 while(1)  
    {  
        r = q->next;  
        q->next = p;  
 if(r == NULL)  
        {  
            L->Head = q;  
 break;  
        }  
        p = q;  
        q = r;  
    }  
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-06-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

数据结构

编程算法

登录后参与评论

0 条评论

热度

数据结构之链表

数据结构之链表

一、概念

二、代码

（1）没有哨兵的情况

（2）有哨兵的情况

三、练习

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐