数据结构之链表

一、概念

（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）没有哨兵的情况

[cpp] view plain copy

print?

  1. //链表结点结构  
  2. struct node  
  3. {  
  4.     node *pre;  
  5.     node *next;  
  6.     int key;  
  7.     //构造函数  
  8.     node(int x):pre(NULL),next(NULL),key(x){}  
  9. };  
  10. //链表结构  
  11. struct List  
  12. {  
  13.     node *head;  
  14.     List():head(NULL){}  
  15. };  
  16. //打印  
  17. void List_Print(List *L)  
  18. {  
  19.     node *p = L->head;  
  20.     while(p)  
  21.     {  
  22.         cout<<p->key<<' ';  
  23.         p = p->next;  
  24.     }  
  25.     cout<<endl;  
  26. }  
  27. //搜索，找出L中第一个关键字为k的结点，没有则返回NULL  
  28. node *List_Search(List *L, int k)  
  29. {  
  30.     node *x = L->head;  
  31.     while(x != NULL && x->key!=k)  
  32.         x = x->next;  
  33.     return x;  
  34. }  
  35. //插入  
  36. void List_Insert(List *L, node *x)  
  37. {  
  38.     //插入到表的前端  
  39.     x->next = L->head;  
  40.     if(L->head != NULL)  
  41.         L->head->pre = x;  
  42.     L->head = x;  
  43.     x->pre = NULL;  
  44. }  
  45. //删除  
  46. void List_Delete(List *L, node* x)  
  47. {  
  48.     if(x->pre != NULL)  
  49.         x->pre->next = x->next;  
  50.     else  
  51.         L->head = x->next;  
  52.     if(x->next != NULL)  
  53.         x->next->pre = x->pre;  
  54.     delete x;  
  55. }  
//链表结点结构
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）有哨兵的情况

[cpp] view plain copy

print?

  1. //链表结点结构  
  2. struct node  
  3. {  
  4.     node *pre;  
  5.     node *next;  
  6.     int key;  
  7.     //构造函数  
  8.     node(int x):pre(NULL),next(NULL),key(x){}  
  9. };  
  10. //链表结构  
  11. struct List  
  12. {  
  13.     node *nil;//哨兵  
  14.     List()  
  15.     {  
  16.         nil = new node(0);  
  17.         nil->next = nil;  
  18.         nil->pre = nil;  
  19.     }  
  20. };  
  21. //打印  
  22. void List_Print(List *L)  
  23. {  
  24.     node *p = L->nil->next;  
  25.     while(p != L->nil)  
  26.     {  
  27.         cout<<p->key<<' ';  
  28.         p = p->next;  
  29.     }  
  30.     cout<<endl;  
  31. }  
  32. //搜索，找出L中第一个关键字为k的结点，没有则返回NULL  
  33. node *List_Search(List *L, int k)  
  34. {  
  35.     node *x = L->nil->next;  
  36.     while(x != L->nil && x->key!=k)  
  37.         x = x->next;  
  38.     return x;  
  39. }  
  40. //插入  
  41. void List_Insert(List *L, node *x)  
  42. {  
  43.     //插入到表的前端  
  44.     x->next = L->nil->next;  
  45.     L->nil->next->pre = x;  
  46.     L->nil->next = x;  
  47.     x->pre = L->nil;  
  48. }  
  49. //删除  
  50. void List_Delete(List *L, node* x)  
  51. {  
  52.     x->pre->next = x->next;  
  53.     x->next->pre = x->pre;  
  54.     delete x;  
  55. }  
//链表结点结构
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;
}

三、练习

[cpp] view plain copy

print?

  1. 10.2-1  
  2. 能，能  
  3. 10.2-2  
  4. //结点  
  5. struct node  
  6. {  
  7.     node *pre;//为了方便实现出栈操作  
  8.     node *next;  
  9.     int key;  
  10.     node(int x):pre(NULL),next(NULL),key(x){}  
  11. };  
  12. //链式栈  
  13. struct list  
  14. {  
  15.     node *Head;//栈的起始结点  
  16.     node *Top;//栈顶指针  
  17.     list(){Head = new node(0);Top = Head;}  
  18. };  
  19. //打印栈中的元素  
  20. void Print(list *L)  
  21. {  
  22.     node *p = L->Head->next;  
  23.     while(p)  
  24.     {  
  25.         cout<<p->key<<' ';  
  26.         p = p->next;  
  27.     }  
  28.     cout<<endl;  
  29. }  
  30. //入栈  
  31. void Push(list *L, int x)  
  32. {  
  33.     //构造一个新的结点  
  34.     node *A = new node(x);  
  35.     //链入到栈顶位置，修改指针  
  36.     L->Top->next = A;  
  37.     A->pre = L->Top;  
  38.     L->Top = A;  
  39. }  
  40. //出栈  
  41. int Pop(list *L)  
  42. {  
  43.     if(L->Head == L->Top)  
  44.     {  
  45.         cout<<"error:underflow"<<endl;  
  46.         return -1;  
  47.     }  
  48.     //取出栈顶元素  
  49.     int ret = L->Top->key;  
  50.     //修改指针  
  51.     node *A = L->Top;  
  52.     L->Top = A->pre;  
  53.     L->Top->next = NULL;  
  54.     delete A;  
  55.     return ret;  
  56. }  
  57. 10.2-3  
  58. //结点  
  59. struct node  
  60. {  
  61.     node *next;  
  62.     int key;  
  63.     node(int x):next(NULL),key(x){}  
  64. };  
  65. //链式队列  
  66. struct list  
  67. {  
  68.     node *Head;//头指针  
  69.     node *Tail;//尾指针  
  70.     list(){Head = new node(0);Tail = Head;}  
  71. };  
  72. //打印  
  73. void Print(list *L)  
  74. {  
  75.     node *p = L->Head->next;  
  76.     while(p)  
  77.     {  
  78.         cout<<p->key<<' ';  
  79.         p = p->next;  
  80.     }  
  81.     cout<<endl;  
  82. }  
  83. //入队列  
  84. void Enqueue(list *L, int x)  
  85. {  
  86.     //构造一个新的结点  
  87.     node *A = new node(x);  
  88.     //链入尾部，修改指针  
  89.     L->Tail->next = A;  
  90.     L->Tail = A;  
  91. }  
  92. //出队列  
  93. int Dequeue(list *L)  
  94. {  
  95.     if(L->Head == L->Tail)  
  96.     {  
  97.         cout<<"error:underflow"<<endl;  
  98.         return -1;  
  99.     }  
  100.     //取出队头结点，修改指针  
  101.     node *A = L->Head->next;  
  102.     int ret = A->key;  
  103.     L->Head->next = A->next;  
  104.     if(A == L->Tail)  
  105.         L->Tail = L->Head;  
  106.     delete A;  
  107.     return ret;  
  108. }  
  109. 10.2-4  
  110. 把哨兵的值置为一个不可能与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

[cpp] view plain copy

print?

  1. //逆转  
  2. void Reverse(list *L)  
  3. {  
  4.     node *p = NULL, *q = L->Head, *r;  
  5.     //依次修改指针，让q是p->next,令q->next=p  
  6.     while(1)  
  7.     {  
  8.         r = q->next;  
  9.         q->next = p;  
  10.         if(r == NULL)  
  11.         {  
  12.             L->Head = q;  
  13.             break;  
  14.         }  
  15.         p = q;  
  16.         q = r;  
  17.     }  
  18. }  
时间： 2024-09-27 02:12:06

数据结构之链表的相关文章

数据结构 单链表-求大神给我讲讲数据结构单链表和队列

问题描述 求大神给我讲讲数据结构单链表和队列 帮我彻底分析下两种结构,感激不尽多谢大神了 解决方案 单链表和队列是两个层次的事情. 单链表是一种基本的表示一个线性表的方式,它记录下当前节点的数据和指向下一个节点的指针.因此一环一环可以得到整个数据.除了单链表,我们还有数组.双向链表.循环链表等. 队列是一种先进先出的数据结构,它高于链表一个层次,这是说,你可以用链表实现队列(当然也可以用数组或者别的).另外还有先进后出的数据结构(堆栈)等. 解决方案二: 具体你可以google下wikipedi

插入删除-数据结构单链表的插入与删除

问题描述 数据结构单链表的插入与删除 设单链表某一节点为p,怎样在p节点前插入一个结点?怎样删除p节点自身?(要求:用Java语言写出具体程序语言) 解决方案 这个主要是定位问题,只要能定到节点p的位置就好. List list = new LinkedList(); list.add(list.indexOf(p), "插入内容");//由于是链表结构,所以数据插入位置的后方下标自动后移 list.remove(list.indexOf(p));//删除p节点 就是这个思路,不知道对

浅谈PHP链表数据结构(单链表)_php实例

链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表 单向链表,双向链表,环形链表 PHP的底层是C,当一个程序运行时,内存分成五个区(堆区,栈区,全局区,常量区,代码区) 规定:基本数据类型,一般放在栈区 复合数据类型,比如对象,放在堆区 定义一个类Hero 定义成员属性排名 $no 定义成员属性姓名 $name 定义成员属性昵称 $nickname 定义成员属性 $next,是一个引用,指向下一个Hero对象 定义构造函数,传递参数:

用C语言实现数据结构的链表创建时出错

问题描述 用C语言实现数据结构的链表创建时出错 请教大家,下面的程序哪里有错啊?十分感谢 #include "stdio.h" #include "malloc.h" #include "stdlib.h" #define NULL 0 #define OK 1 typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *

c语言-C语言（数据结构）链表创建问题

问题描述 C语言(数据结构)链表创建问题 #include #include//含malloc.h #define LEN sizeof( Faction) //一元多项式结构体 typedef struct Faction{ int coefficient;//系数 int exponent;//指数 struct Faction next; }Faction; //创建链表 Faction *creat() { Faction *head, *p1, *p2; head = NULL; p1

用java学习数据结构--单链表

数据|数据结构 /* * Created on 2004-9-10 * * 单链表中的结点类型声明. */package org.arliang;/** * @author 李梁 * * 单链表中的结点. */public class node{ private int data; //存放数据 private node link; //链接的下一个接点. public static void main(String[]args) { } /** * @return Returns the da

数据结构 单链表-帮我看看下面的程序哪里出错了，刚从数据结构学的单链表，运行不了

问题描述 帮我看看下面的程序哪里出错了,刚从数据结构学的单链表,运行不了 就简单的取值 插入 删除 合并 #include #include #include typedef struct LNode { int num; struct LNode *next; }LNode,*LinkList; void InitiList(LinkList L) { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; } void LocateElem(Link

数据结构 单链表-单链表的连接..数据结构..帮忙看一下。第一个表出来正确，但第二个练上去是一窜数字

问题描述 单链表的连接..数据结构..帮忙看一下.第一个表出来正确,但第二个练上去是一窜数字 #include #include using namespace std; typedef struct node { char data; node *next; }Node; int init(Node *&L) { L=(Node *)malloc(sizeof(Node)); L->next=NULL; return 0; } int crete(Node *&L,int a[],

数据结构 单链表-数据结构函数的问题求解

问题描述 数据结构函数的问题求解 如果这是一个一个结构体. typedef struct list { struct list *prior ; struct list *next; int num; } list,*dlist; 问题1:比如我写一个创建函数,我通常是void create_list(dlist L,int n); 但是我看有的地方括号里面的第一个形参不是星号,而是&,麻烦跟我讲一下.是不是传递的不是指针,是一个对象名的引用?是不是对顺序链表这么做好一点? 问题2:上次还有人跟

c 数据结构 静态链表-C语言静态链表问题，vc下为什么会编译不通过呢？

问题描述 C语言静态链表问题,vc下为什么会编译不通过呢? #include #include #include #define NULL 0 #define Maxsize 100 typedef int elemtype,status; typedef struct { int cur; elemtype data; }component,SLinkList[Maxsize];/*SLinkList是一个结构体数组*/ void Initspace_SL(SLinkList &space)/