DS:链表(详解+实例)_ds sd串链

链表

• 逻辑上线性的，物理上不一定连续存储的存储单元；

分类

• 单向||双向
• 带头||不带头

1. 带头当链表为空时头还在；
2. 相同长度带头比不带头少一个元素

• 循环||不循环

1. 尾指向NULL为不循环；
2. 尾指向链表上元素；

单向不带头不循环链表

定义

typedef int SLDataType

typedef struct SLNode
{
    SLDataType value;
    struct SLNode* next;//指向下一个这样的结构体；
} SLNode;

typedef struct SList//链表的首节点
{
   SLNode *first;//SLNode *first；第一个节点地址
} SList；
1
2
3
4
5
6
7
8
9
10
11
12

初始化

• 单链表的空链表形式 first->NULL

void SListInit(SList*list)
{
   asser(list!=NULL);
   list->first = NULL;
}
1
2
3
4
5

销毁

void SListDestroy(SList*list)
{
  assert(list!=NULL);
  SLNode * go = list->first;//找到一个，把下一个的地址存起来，然后把当前这个释放掉；
  SLNode * next;
  while(go!=NULL)
  {
     next = go->next;
     free(go);
     go = next;
  }
  list->first = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

增加数据

void SListPushFront(SList*list,SLDataType value)
{
    assert(list!=NULL);
    SListNode *node = (SLiztNode*)malloc(sizeof(SListNode));
    assert(node);
    node->value = value;
    node->next = list->first;
    list->first = node;
}//头插

void SListPushBack(SList*list,SLDataType value)
{
    assert(list!=NULL);//判断链表是否存在
    SLNode* find_last;
    if(list->first==NULL)//没有元素就调用头插；
    {
       SListPushFront(list,value);
       return;
    }
    for(find_last=list->first;find_last->next!=NULL;find_last = find_last->next){
    }
    SListNode *node = (SLiztNode*)malloc(sizeof(SListNode));
    assert(node);
    node->value = value;
    find_last->next = node;
    node->next = NULL;
    
}//尾插

void SListInsertAfter(SLNode *pos,SLDataType value)
{
  SLNode*node = (SLiztNode*)malloc(sizeof(SListNode));
  assert(node);
  node->value = value;
  node->next = pos->next;
  pos->next = node;
}//在目标位置之后插入；

void SListInsertBefore(SList*list,SLNode*pos,SLDataType value)
{
   assert(list);
   SLNode*node = (SLiztNode*)malloc(sizeof(SListNode));
   assert(node);
   node->value = value;
   for(SLNode*go = list->first;go->next!=pos&&go->next!=NULL;go = go->next)
   {
      ;
   }
   if(go->next==pos)
   {
      node->next = pos;
      go->next = node;
   }
   else
   {
     printf("没有找到该位置\n");
   }
}//在目标前面插入；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

删除数据

void SListPopFront(SList*list)
{
   assert(list!=NULL);//表示链表存在；
   assert(list->first  !=NULL );//表示链表不为空；
   SLNode*free_frist = list->first;
   list->first = list->first->next;
   free(free_frist);
}//头删

void SListPopBack(SList*list)
{
   assert(list!=NULL);//表示链表存在；
   assert(list->first  !=NULL );//表示链表不为空；
   if(list->first->next==NULL)
   {
     SListPopFront(list)
   }//特殊情况只有一个节点；
   SLNode* find_2last;
   for(find_2last=list->first;find_2last->next->next!=NULL;find_2last = find_last->next){
    }//找到倒数第二个节点；
    free(find_2last->next)
    find_2last->next = NULL;
}//尾删

void SLiztEraseAfter(SLNode*pos)
{
  SLNode*next = pos->next;
  pos->next = next->next;
  free(next);
}//删除任意一个节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

打印

void SListPrint(const SList*list)
{
    for(SLNode*go = list->first;go!=NULL;go = go->next)
    {
       printf("%d->",go->value);
    }
    printf("NULL\n");
}
1
2
3
4
5
6
7
8

查找

SLNode* SListFind(const SList*list,SLDataType value)
{
 for(SLNode *go = list->first;go!=NULL;go = go->next)
 { 
    if(go->value==value)
    {
      return go;
    }
 }
 return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

修改

void SListModify(SLNode*nodet,SLDataType value )
{
  node->value = value;
}
1
2
3
4

双向带头循环链表

定义

typedef int DLDataType

typedef struct DLNode
{
    DLDataType value;
    struct DLNode* prev;
    struct DLNode* next;//指向下一个这样的结构体；
} DLNode;

typedef struct DList//链表的头节点
{
   DLNode *head;//头
} DList；
1
2
3
4
5
6
7
8
9
10
11
12
13

初始化

DLNode * DLBuyNode(DLDataType value)
{ 
     DLNode*node = (DLNode*)malloc(sizeof(DLNode));
     node->value = value;
     node->next = node->prev = NULL;
     return node;
}
void DListInit(DList*list)
{
   asser(list!=NULL);
   list->head = DLBuyNode(0);
   list->head->next = list->head;//构成前环；
   list->head->prev = list->head;//构成后环；
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

销毁

void DListClear(DList*list)//先清空
{
   DLNode* go,*self ;
   go = list->head->next;
  while(go!=list->head)
  {
      self = go;
      go = go->next;
      free(self);
  }
  list->head->next = list->head->prev = list->head;//注意只剩一个head也得让它成环；
}
void DListDestroy(DList*list)
{
    DListClear(list);
    free(list->head);//?
    list->head = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

增加数据

void DListPushFront(DList*list,DLDataType value)
{
    assert(list!=NULL);
  #if 0
    DListNode *node =DLBuyNode(value);
    node->prev = list->head;
    node->next = list->head->next;
    list->head->next->prev = node;
    list->head->next = node;
  #endif
    DListInsertFront(list->head->next,value);
}//头插

void DListPushBack(DList*list,DLDataType value)
{
    assert(list!=NULL);
  #if 0
    DListNode *node =DLBuyNode(value);
    node->prev = list->head->prev;
    node->next = list->head;
    list->head->prev->next = node;
    list->head->prev = node;
  #endif
    DListInsertFront(list->head,value);
}//尾插

void DListInsertFront(DLNode*pos,DLDataType value)
{
   DLNode*node = DLBuyNode(value);
   node->prev = pos->prev;
   node->next = pos;
   pos->prev = node;
   node->prev->next = node;
}//指定位置前插入；
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

删除数据

void DListPopFront(DList*list)
{
   assert(list!=NULL);//表示链表存在；
   assert(list->head->next !=list->head );//表示链表不为空；不是一个节点在哪里环；
   DLNode* go = list->head->next ;
   list->head->next = go->next;
   go->next->prev = list->head;
   free(go);
}//头删

void DListPopBack(DList*list)
{
   assert(list!=NULL);//表示链表存在；
   assert(list->head->next !=list->head );
   SLNode*get = list->head->prev;
   list->head->prev = get->prev;
   get->prev->next = list->head;
   free(get);
}//尾删

void DListErase(DLNode*pos)
{
   DLnode*get = pos;
   pos->prev->next = pos->next;
   pos->next->prev = pos->prev;
   free(pos);
}//指定位置删除；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

打印

void DListPrint(const DList*list)
{
    for(SLNode*go = list->head->next;go!=list->head;go = go->next)
    {
       printf("%d->",go->value);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8

查找

DLNode* DListFind(const DList*list,DLDataType value)
{
  DLNode* go ;
  for(go = list->head->next;go!=list->head;go = go->next)
  {
    if(go->value == value)
    { 
       return go;
    }
  }
  return NULL:
}
1
2
3
4
5
6
7
8
9
10
11
12

修改

void SListModify(DLNode*node,DLDataType vale )
{
  node->vale = vale;
}
1
2
3
4

• 地址:一段空间的起始位置;
• 指针:是个变量，存放内存单元的地址;制定了内存的长度；

链表的相关题目:

反转链表