C语言基础（九）- 链表

KinglyJn      2013-02-26

数组和链表的比较

数组

优点：

  • 存取速度快，并且每个元素有标号，方便找到

缺点：

  • 只能够连续存储，如果需要存数的信息量特别大，可能就会定义数组失败！
  • 当删除数据或增加数据时，数组也不能够做到自动做到将分配空间迁移。

链表

优点：

  • 每个结点包括存储的数据和指针两部分，插入和删除元素效率高，且它的元素之间可以不连续

缺点：

  • 没有编号，所以找到某个位置的链表的元素效率低，只能一个个挨个的找

相关术语：

  • 首结点：存放第一个有效数据的结点；
  • 尾结点：存放最后一个有效数据的结点；
  • 头结点：首结点前面的那个结点，头结点和首结点的数据类型是一摸一样的，设置头结点的目的是方便对链表的操作；
  • 头指针：存放头结点地址的指针变量；

[注]：确定一个链表只需要头指针一个参数即可。

单向动态链表示例：

/**
* 单向动态链表测试
*/

# include <stdio.h>
# include <string.h>
# include <mm_malloc.h>

struct Student {
    char name[10]; //链表数据
    float score;
    struct Student * pNext; //指针数据
};

int main() {
    int len;
    struct Student * create_stu_list(int);
    void traverse_stu_list(struct Student *);
    
    printf("please input the num of stu: ");
    scanf(" %d", &len);
    
    //创建链表
    struct Student *pHead = create_stu_list(len);
    
    //遍历链表
    traverse_stu_list(pHead);
    
    return 0;
}

struct Student * create_stu_list(int len) {
    /*
      pHead是头指针
      pre指针的作用是开辟动态存储空间
      post指针的作用是创建各结点的链接
    */
    struct Student *pHead, *pre, *post;
    
    //首结点
    pre = (struct Student *) malloc(sizeof(struct Student));
    pHead = pre;
    post = pre;
    
    printf("please input the information of stu:\n");
    printf("name=");
    scanf(" %s", pre->name);
    printf("score=");
    scanf(" %f", &pre->score);
    
    int i = 1;
    while (i<len) {
        //开辟新的内存空间
        pre = (struct Student *) malloc(sizeof(struct Student));
        
        //赋值
        printf("name=");
        scanf(" %s", pre->name);
        printf("score=");
        scanf(" %f", &pre->score);
        
        //勾连
        post->pNext = pre;
        post = pre;
        
        i++;
    }
    post->pNext = NULL; //最后的尾结点指针不指向任何结点

    return pHead;
}

void traverse_stu_list(struct Student *pHead) {
    struct Student *p;
    
    printf("[while] the student info is as follows: \n");
    p = pHead;
    while (p!=NULL) {
        printf("%-15s %-5.1f\n", p->name, p->score);
        p = p->pNext;
    }
    
    printf("[for] the student info is as follows: \n");
    for (p=pHead; p!=NULL; p=p->pNext) {
       printf("%-15s %-5.1f\n", p->name, p->score);
    }
}


Tags:


Share: