数据结构——单链表的定义和实现_结合课本和课件,实现结点、单链表的类定义,单链表类定义中,实现首端加入元素

单链表的定义

• 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名
• 若头指针名是L，则把链表称为表L

单链表的存储结构定义

typedef struct LNode{
     ElemType   data;       // 数据域
     struct LNode  *next;   // 指针域
}LNode,*LinkList;   // *LinkList为Lnode类型的指针
1
2
3
4

其中，LNode,*LinkList是等价的
在定义指针类型时候就可以直接用LinkList

注意区分指针变量和结点变量两个不同的概念

指针变量p：表示结点地址
结点变量*p：表示一个结点

单链表的实现

1.初始化(构造一个空表 )

【算法步骤】

1. 生成新结点作头结点，用头指针L指向头结点。
2. 头结点的指针域置空。

【算法描述】

Status InitList_L(LinkList &L){ 
   L=new LNode;                    	
   L->next=NULL;　　　　　
   return OK; 
} 
1
2
3
4
5

求链表长度

指针p依次指向各个结点
从第一个元素开始“数”
一直“数”到最后一个结点

int  ListLength_L(LinkList L){
//返回L中数据元素个数
    LinkList p;
    p=L->next;  	//p指向第一个结点
     i=0;             
     while(p){	//遍历单链表,统计结点数
           i++;
           p=p->next;    } 
    return i;                             
 }
1
2
3
4
5
6
7
8
9
10

判断链表是否为空

//判断表是否为空
int ListEmpty(LinkList L){ 
//若L为空表，则返回1，否则返回0 
   if(L->next)   //非空 
     return 0;
   else
     return 1;
 }
1
2
3
4
5
6
7
8

2. 取值

链表的查找：
要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

【算法步骤】

1. 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
2. j做计数器，累计当前扫描过的结点数，j初值为1。
3. 当p指向扫描到的下一结点时，计数器j加1。
4. 当j = i时，p所指的结点就是要找的第i个结点。

【算法描述】

//获取线性表L中的某个数据元素的内容
Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;
    j=1; 		//初始化
    while(p&&j<i){		//向后扫描，直到p指向第i个元素或p为空 
       p=p->next; 
       ++j; 
    } 
    if(!p || j>i)
     	return ERROR; 	//第i个元素不存在 
    e=p->data; 		//取第i个元素 
    return OK; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.查找

【算法描述】

1. 从第一个结点起，依次和e相比较。
2. 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址;
3. 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。.

【算法描述】

返回该链表

//在线性表L中查找值为e的数据元素
LNode *LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的地址，查找失败返回NULL
  p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	
} 
1
2
3
4
5
6
7
8

返回该结点的索引值

//在线性表L中查找值为e的数据元素
int LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的位置序号，查找失败返回0 
  p=L->next; j=1;
  while(p &&p->data!=e)  
        {p=p->next;  j++;}          		
  if(p) return j; 
  else return 0;
} 
1
2
3
4
5
6
7
8
9

4. ※ 插入（插在第 i 个结点之前）

将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间

1. 找到ai-1存储位置p
2. 生成一个新结点*s
3. 将新结点*s的数据域置为x
4. 新结点*s的指针域指向结点ai
5. 令结点p的指针域指向新结点s

//在L中第i个元素之前插入数据元素e 
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i−1)
      {
	      p=p->next;
	      ++j;
      }	//寻找第i−1个结点 
      if(!p||j>i−1)
      	return ERROR;			//i大于表长 + 1或者小于1  
      s=new LNode;				//生成新结点s 
      s->data=e;      		    //将结点s的数据域置为e 
      s->next=p->next;	   	    //将结点s插入L中 
      p->next=s; 
      return OK; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5. 删除（删除第 i 个结点）

1. 找到ai-1存储位置p
2. 保存要删除的结点的值
3. 令p-＞next指向ai的直接后继结点
4. 释放结点ai的空间

//将线性表L中第i个数据元素删除
 Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){			//寻找第i个结点，并令p指向其前驱 
        p=p->next; 
        ++j; 
    } 
    if(!(p->next)||j>i-1)
    	 return ERROR; 	//删除位置不合理 
    q=p->next; 				//临时保存被删结点的地址以备释放 
    p->next=q->next; 			//改变删除结点前驱结点的指针域 
    e=q->data; 				//保存删除结点的数据域 
    delete q; 				//释放删除结点的空间 
 	return OK; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表的运算时间效率分析

1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，
   查找的时间复杂度为O(n)。
2. 插入和删除: 因线性链表不需要移动元素，只要修改指针，一般
   情况下时间复杂度为 O(1)。

但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。