链表,算法

た入场券 2022-01-05 05:57 269阅读 0赞

链表

## 算法 ##

1, 通俗定义  
解题的方法和步骤  
  
  
2, 狭义定义  
对存储数据的操作  
对不同的存储结构,要完成某一个功能所执行的操作是不一样的  
比如:  
输出所有元素的操作,数组和链表是不一样的.  
这说明:  
算法是依附于存储结构的  
不同的存储结构,实现的算法是不一样的  
  
  
3, 广义定义  
广义的算法也叫做泛型  
无论数据是如何存储,对该数据的操作都是一样的.

## 两种基本结构来存储数据 ##

1, 数组  
优点:  
存取速度快  
缺点:  
1) 连续的很大的存储空间  
2) 删除, 效率低  
3) 插入, 效率低  
  
2, 链表  
专业术语  
首结点  
存放第一个有效数据的结点  
尾结点  
存放最后一个有效数据的结点  
头结点  
1)头结点的数据类型与首结点类型一模一样  
2)头结点是首结点前面的结点  
3)头结点不存放有效数据  
4)作用是方便对链表的操作  
头指针  
存放头结点地址的指针变量  
可确定一个链表  
优点  
解决数组的缺点  
1) 不需要一块连续的很大的内存  
2) 插删速度快  
缺点

查找某个位置的元素效率低

## 链表及其操作 ##

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

## 创建与遍历链表 ##

#include <stdio.h>
    #include <malloc.h>
    
    // 链表中的一个元素(节点)
    struct Node 
    {
        int data;   // 数据域
        struct Node * pNext;    // 指针域,指向下一个节点
    };
    
    // 创建链表
    struct Node * CreateList();
    
    // 遍历链表
    void TraverseList(struct Node *);
    
    int main(void) 
    {
        struct Node * pHead; // 头指针,头结点的地址
    
        // 创建链表
        pHead = CreateList();
    
        // 遍历链表
        TraverseList(pHead);
    
        return 0;
    }
    
    struct Node * CreateList() 
    {
        int len; // 有效结点的个数
        int val; // 临时存放用户输入的结点的值
        int i;   // for循环使用的参数
    
        // 头结点, 分配一个不存放有效数据的头结点  
        struct Node * pHead = (struct Node *) malloc( sizeof( struct Node ) );
    
        if ( NULL == pHead ) {
            printf( "分配失败, 程序终止!" );
            exit( -1 );
        }
        // 此时, 尾结点就是头结点
        struct Node * pTail = pHead;
        pTail->pNext = NULL;
    
        // 结点个数
        printf( "链表结点的个数 len = " );
        scanf( "%d", &len );
    
        // 给每个结点赋值
        for ( i = 0; i < len; ++i ) 
        {        
            // 创建新结点
            struct Node * pNew = ( struct Node * ) malloc( sizeof( struct Node ) );
            if ( NULL == pNew ) 
            {
                printf( "分配失败, 程序终止!!" );
                exit( -1 );
            }
            // 给新结点赋值
            printf( "结点%d的值:", i+1 );
            scanf( "%d", &val );   
            pNew->data = val;
    
            // 将新结点追加到链表末尾,即新结点成为尾结点
            pTail->pNext = pNew;
            pNew->pNext = NULL;
    
            pTail = pNew;   // 如果掉了此句,链表永远只有一个元素pNew
        }
    
        return pHead;
    }
    
    void TraverseList(struct Node * pHead) {
        struct Node * p = pHead->pNext; // 获取首结点的地址
        
        // 遍历节点, 直到尾结点
        while ( NULL != p ) 
        {
            printf( "%d ", p->data );
            p = p->pNext;   // 移向下一个结点
        }
    
        printf("\n");
    
        return;
    }

[SouthEast]: /images/20211229/eef8ea6eda68409d82f358fe928e2b44.png
[SouthEast 1]: /images/20211229/9119d91b2dc944769cf212fbe72de3bd.png
[SouthEast 2]: /images/20211229/c9cf300b6dc8474ab0753fa91b28a398.png
[SouthEast 3]: /images/20211229/ad79e980ed104a819425961c077e5692.png