数据结构-链表(1)

定义

链表是线性表的链接存储方式，相比于数组的连续存储

既然说到了线性表就来简单介绍一下，以便和后面的树，图等非线性结构区分开来

同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱元素。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继元素。

优缺点

优点

对于插入和删除元素，数组的时间复杂度为O(n)，而链表为O(1)
链表长度可变，而数组长度不可变

缺点

按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，时间复杂度为O(n)
存储密度（结点数据本身所占的存储量/结点结构所占的存储总量）<1
需要动态申请管理内存，处理不当会造成内存泄漏

分类

单链表
静态链表
循环链表
双向链表

专业术语

头节点：第一个有效节点之前的节点数据域不存放数据加头节点的目的主要是方便对链表的操作
首节点：第一个存放数据的节点
尾节点：最后一个存放数据的节点
头指针：指向头节点的指针
尾指针：指向尾节点的指针

单链表

每个元素由结点（Node）构成，它包括两个域，数据域和指针域
存储结构：链式存储，存储单元可以不连续
存储方式：顺序存取（意思是如果你要取出第5个元素，那么你必须从头节点向后顺序访问找到第五个结点）

单链表的实现

结点定义 

//
typedef struct ListNode
{
int val;
struct ListNode *pNext;
} NODE,*PNODE;
//

初始化

由于不带头节点的单链表操作不便，这里就不讲解了，直接来看带头节点的单链表实现
^代表空指针也就是NULL，来看一下如何创建链表 

//
PNODE createList(void)
{
    int len,val,i;
    //创建头节点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    pHead ->pNext =NULL;
    if(pHead == NULL)
    {
        printf("内存分配失败");
        exit(-1);
    }
    //添加数据
    PNODE pTail = pHead;
    PNODE pNew;

    printf("请输入要创建链表的长度：");
    scanf("%d",&len);
    for(i = 0; i< len; ++i)
    {
        pNew = (PNODE)malloc(sizeof(NODE));
        printf("请输入第%d个数的值：",i+1);
        scanf("%d",&val);
        pNew->val = val;
        pNew->pNext = NULL;
        pTail->pNext = pNew;//将新结点添加在尾部
        pTail = pNew;//pTail指向新结点
    }
    return pHead;
}
//

插入操作

我们只需要要插入位置的前一个结点的指针域指向新结点，新结点的指针域指向插入位置的后一个结点，这时我们就发现头节点的作用了，因为对于每一个存储数据的结点来说它都有前驱元素，即使是在首节点前面插入新结点，操作和在中间插入新结点并没有什么区别。而对于不带头节点的单链表来说我们还要判断它的插入位置，判断是否为空链表等等

//
bool insertList(PNODE pHead,int pos,int val)
{
    int i = 0;
    //我规定pos = 0就是在首结点前插入
    while(pHead!=NULL && i < pos)
    {
        pHead = pHead->pNext;
        i++;
    }
    //如果pos为负或者pHead指向空，插入位置不合理
    if(i > pos||pHead == NULL)
        return false;
    else
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->val = val;
        //新结点的指针域指向插入位置的后一个结点
        pNew->pNext = pHead->pNext;
        //插入位置的前一个结点的指针域指向新结点
        pHead->pNext = pNew;
        return true;
    }
}
//

删除操作

//
bool deleteList(PNODE pHead,int pos)
{
    int i = 0;
    while(pHead != NULL && i < pos)
    {
        pHead = pHead->pNext;
        i++;
    }
    if(i > pos||pHead == NULL)
        return false;
    else
    {
        PNODE p = pHead->pNext;
        pHead ->pNext= p->pNext;
        free(p);
    }
}
//

遍历操作

//
void traverseList(PNODE pHead)
{
    int i = 1;
    PNODE pNow = pHead ->pNext;
    while(pNow!=NULL)
    {
        printf("第%d个元素为%d\n",i,pNow->val);
        pNow = pNow->pNext;
        i++;
    }
    printf("遍历结束\n");
}
//

静态链表（链表的游标表示法）

用一维数组来描述线性链表（后面树的存储中也会看见类似的方式）

会出现游标表示法是因为有一些语言并没有指针

同样是每个结点有两个域，一个存放数据，一个存放下一个结点的下标，对于最后一个结点它存放的不再是NULL，而是-1，我们同样空出第一个位置作为头结点

结构定义

//
const int MaxSize = 100;
typedef struct node {           //静态链表结点
    int data;
    int link;
} SNode;

typedef struct {                    //静态链表
    SNode Nodes[MaxSize];  //大小自定
    int newptr;	   //当前可分配空间首地址
} SLinkList;
//

初始化

初始化时，我们不但要初始化头结点，还要把空闲结点初始化，使他们都指向下一个结点，所以空表是下面这个样子的，而newptr指向空闲表的开头，在插入和删除操作中都会用到newptr，至于为什么，后面会讲到

//
void InitList ( SLinkList* SL ) {
    SL->Nodes[0].link = -1;    
    SL->newptr = 1;   //当前可分配空间从 1 开始
    //建立带表头结点的空链表
    for ( int i = 1; i < MaxSize-1; i++ )
        SL->Nodes[i].link = i+1; //构成空闲链表
     SL->Nodes[MaxSize-1].link = -1;
        //链表收尾
}
//

查找第i个结点

int Locate ( SLinkList SL, int i ) {
     if ( i < 0 ) return -1;//参数不合理
     int j = 0, p = SL.Nodes[0].link; 
     while ( p != -1 && j < i ) {//循环查找第 i 号结点
		p = SL.Nodes[p].link;
          j++;
     }
     if ( i == 0 ) return 0;
     return p;           
}

插入操作

这里新结点并不是动态分配的，而是从空闲链表中取出来的，也就是newptr

//
int Insert ( SLinkList* SL, int i, ListData x ) {
     int p = Locate ( SL, i-1 ); //找它的前驱元素
     if ( p == -1 ) return 0;           //找不到结点
     int q = SL->newptr;                  //分配结点
     SL->newptr = SL->Nodes[SL->newptr].link;//newptr后移
     SL->Nodes[q].data = x;
     SL->Nodes[q].link = SL.Nodes[p].link;
     SL->Nodes[p].link = q;             //插入
     return 1;
}
//

删除操作

//
int Remove ( SLinkList* SL, int i ) {
     int p = Locate ( SL, i-1 ); 
     if ( p == -1 ) return 0;       //找不到结点
     int q = SL->Nodes[p].link;    //第 i 号结点
     SL->Nodes[p].link = SL->Nodes[q].link;
     SL->Nodes[q].link = SL->newptr; //该节点添加到空闲链表
     SL->newptr = q;
     return 1;
}
//

现在我们再来看看空闲链表的作用，空闲链避免了我们每次插入新结点时需要在在数组内寻找空闲结点的操作，我们只需要取出空闲链（备用链）的第一个结点即可。我们会发现一个有趣的地方，实际上空闲链是一个栈结构，最后放入空闲链的结点会最早被调用。

《数据结构-链表(1)》有27个想法

  2. KelErex说：
    回复

    Sibutramina And Amoxil Viagra Tablets Price India Priligy Generico Chile [url=http://cialibuy.com]Buy Cialis[/url] Amoxicillin 850 Mg Side Effects Medicina Propecia

  11. read acim online说：
    回复

    An impressive share, I just given this onto a colleague who was doing a little bit evaluation on this. And he in fact purchased me breakfast because I found it for him.. smile. So let me reword that: Thnx for the treat! However yeah Thnkx for spending the time to debate this, I feel strongly about it and love studying extra on this topic. If attainable, as you turn out to be experience, would you mind updating your weblog with more details? It’s highly helpful for me. Huge thumb up for this blog publish!

  14. best CBD Oil说：
    回复

    Can I simply say what a relief to find somebody who really knows what they’re discussing on the web. You definitely realize how to bring an issue to light and make it important. More people have to look at this and understand this side of your story. I was surprised that you’re not more popular since you surely possess the gift.|

  17. grolyrto lemcs说：
    回复

    I discovered your weblog website on google and verify just a few of your early posts. Continue to keep up the very good operate. I just further up your RSS feed to my MSN Information Reader. Looking for ahead to studying more from you afterward!…

发表评论

电子邮件地址不会被公开。 必填项已用*标注