Linear_Linked_list

发表于

#线性链表

##基础概念

  • 顺序存储：
    用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；
  • 链式存储：用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。

##单链表初始化
结点中只含一个指针域的链表叫线性链表，也叫单链表

1
2
3
4
5
6
7
8
typedef struct LNode {
ElemType data;
struct LNode  *next;
}LNode,*LinkList;


LNode   *p;
LinkList  L；
  • (*p)表示L所指向的结点
  • (*p).datap->data表示p指向结点的数据域
  • (*p).nextp->next表示p指向结点的指针域
  • 生成新结点：p=(LinkList )malloc(sizeof(LNode));
  • 系统回收p结点：free(p)

##插入

###算法思想：

  • 寻找第i-1个元素结点（顺指针向后查找，直到p指向第i-1个元素或p为空）
  • 分配新结点
  • 插入新结点
1
2
3
4
5
6
7
8
9
10
11
12
Status ListInsert_L(LinkList &L, int i, ElemType e){
//在带头结点的线性链表L中第i元素结点之前插入元素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  则 j>i-1
// i大于表长+1 则p为空
s=(LinkList)malloc(sizeof(LNode)); //分配新结点
s->data=e;
s->next=p->next; p->next=s;   //插入新结点
return OK;
}//LinstInsert_L

##删除

###算法思想：

  • 寻找第i-1个结点
    (顺指针向后查找，直到p指向第i-1个元素或p->next为空)
  • 删除结点(修改其后继指针)
  • 回收（释放）结点空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
删除操作算法：
Status ListDelete_L(LinkList &L, int i, ElemType &e){
//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
p=L; j=0;
while (p->next&&j<i-1){  //寻找第i-1个结点
p=p->next; ++j;
}
if(!p->next)||j>i-1)return ERROR; //  表中无第i个结点(i不合法)
//  i<1        则 j>i-1
//   i>表长  则 p->next为空
q=p->next;p->next=q->next;   //删除结点
e =q->data; free(q);                //  回收（释放）结点空间
return OK;
}//LinstDelete_L

##逆置线性链表

###算法思想：

  • 标志后继结点为空)
  • 修改指针（将*p插入在头结点之后）
  • 重置结点*p（p重新指向原表中后继）
1
2
3
4
5
6
7
8
9
10
void  inverse(LinkList &L) {
// 逆置带头结点的单链表 L
p=L->next;  L->next=NULL;
while ( p) {
succ=p->next;    // succ指向*p的后继
p->next=L->next;
L->next=p;       // *p插入在头结点之后
p = succ;
}
}