[数据结构与算法]C语言从头到尾完整遍历升序链表程序

遍历升序链表程序

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

建立一个升序链表并遍历输出。

输入描述：
输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。

输出描述：
可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。

输入：
4
3 5 7 9

输出：
3 5 7 9

程序编写思路

1. 建立一个typedef结构体
2. 以尾插法建立单链表
3. 对单链表元素进行从小到大排序
4. 排序后进行完整遍历
5. 建立时需要设计头节点

程序编写介绍

1. 结构体代码

typedef struct NODE{
    int data;//数据域
    struct NODE * next;//指针域
}NODE,*PNODE;//PNODE 代表struct NODE * 是一个指针，
//NODE 代表struct NODE 是一个结点域

2.创建单链表

PNODE create(){
    int n,i;
    int val;//设置存放的数值域
    scanf("%d",&n);//节点个数
    PNODE pHead = (PNODE)malloc(sizeof(NODE));//分配内存
    if(pHead == NULL){//检查是否为空
        exit(-1);
    }
    PNODE pTail = pHead;//这里表示当只有一个节点（即只有头节点）
    //设置一个尾指针，始终指向链表的最后一个元素
    pTail->next = NULL;//对最后的数据指向null
    for(i = 0;i<n;i++){//循环建立单链表
        scanf("%d",&val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));//分配节点内存
        if(pNew == NULL){
           exit(-1);
        }
        pNew->data = val;//存放数据域
        pTail->next = pNew;//最后一个节点指向需要添加的节点，
        pNew->next = NULL;//完成添加
        pTail = pNew;//继续让tail指向最后一个节点
    }
    return pHead;
}

3.求链表长度函数

int length_list(PNODE pHead){
    PNODE p = pHead->next;
    int len = 0;
    while(p != NULL){
        len++;
        p = p->next;
    }
    return len;
}

4.链表数据排序
模仿冒泡排序的思路进行设计

void sort_list(PNODE pHead){
    int i,j,temp;
    PNODE p,q;
    int n = length_list(pHead);//得到长度
    for(i = 0,p = pHead->next;i<n-1;i++,p=p->next){
        for(j = i+1,q = p->next;j<n;j++,q= q->next){
            if(p->data > q->data){//找到小值
                temp = p->data;//进行交换
                p->data = q->data;
                q->data = temp;
            }
        }
    }
    
}

5.遍历函数

void traverse(PNODE pHead){
    PNODE p = pHead->next;//设置一个指针指向头节点之后的节点，进行while循环
    while(p != NULL){
        printf("%d ",p->data);
        p = p->next;//循环下一个节点
    }
}

6.main函数

int main(){
   PNODE pHead = NULL;//设置一个空结点
    pHead = create();//调用创建单链表函数
    sort_list(pHead);//链表排序
    traverse(pHead);//遍历链表
    return 0;
}

完整程序

#include<stdio.h>
#include<malloc.h>

typedef struct NODE{
    int data;
    struct NODE * next;
}NODE,*PNODE;


PNODE create(){
    int n,i;
    int val;
    scanf("%d",&n);//节点个数
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if(pHead == NULL){
        exit(-1);
    }
    PNODE pTail = pHead;
    pTail->next = NULL;
    for(i = 0;i<n;i++){
        scanf("%d",&val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(pNew == NULL){
           exit(-1);
        }
        pNew->data = val;
        pTail->next = pNew;
        pNew->next = NULL;
        pTail = pNew;
    }
    return pHead;
}
int length_list(PNODE pHead){
    PNODE p = pHead->next;
    int len = 0;
    while(p != NULL){
        len++;
        p = p->next;
    }
    return len;
}

void sort_list(PNODE pHead){
    int i,j,temp;
    PNODE p,q;
    int n = length_list(pHead);
    for(i = 0,p = pHead->next;i<n-1;i++,p=p->next){
        for(j = i+1,q = p->next;j<n;j++,q= q->next){
            if(p->data > q->data){
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
        }
    }
    
}


void traverse(PNODE pHead){
    PNODE p = pHead->next;
    while(p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
}


int main(){
   PNODE pHead = NULL;
    pHead = create();
    sort_list(pHead);
    traverse(pHead);
    return 0;
}