2019-08-24 | 数据结构 | UNLOCK

链表基本操作代码示例

一、单链表的基本操作

/*
    链表基本操作练习:
        1. 建立链表---createList
        2. 输出链表---displayList
        3. 删除节点---deleteNodes
        4. 插入节点---insertNodes 
*/


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>

using namespace std;
struct student{
    int num;//学号 
    char name[20];//姓名
    int age;//年龄
    struct student *next;//指向下一个节点的指针 
};

struct student *createList();//建立学生信息
void displayList(struct student *head);//按照建立顺序输出学生信息
struct student *reverseList(struct student *head);//与建立顺序相反,逆序顺序输出学生信息 
struct student *deleteNodes(struct student *head);//删除某个学生信息 
struct student *insertNodes(struct student *head);//插入某个学生的信息 
void search_student_info(struct student *head);//查找对应学生信息 
void modify_student_info(struct student *head);//修改学生信息 
struct student *destroyList(struct student *head);//清空整个链表 
struct student *head = NULL;

int main(){
    int select;//根据对应不同select的值,调用不同的函数 
    do{
        printf("请输入select的值:");
        scanf("%d",&select); 
        switch(select){
            case 1:
                head = createList();
                break;
            case 2:
                displayList(head);
                break;
            case 3:
                head = deleteNodes(head);
                break;
            case 4:
                head = insertNodes(head);
                break; 
            case 5:
                search_student_info(head);
                break;
            case 6:
                modify_student_info(head);
                break;
            case 7:
                head = reverseList(head);
//                displayList(head);
                break;
            case 8:
                head = destroyList(head);
                break;

        }
    }while(select!=0); 
    return 0;
}
//1. 建立学生信息 
struct student *createList(){
    struct student *head;//头节点 
    struct student *p1;//开辟新节点  
    struct student *p2;//与p1连接 
    int num1;
    char name1[20];
    int age1;
    head = NULL;
    int count = 1;

    printf("请输入第1个学生的学号、姓名、年龄(用空格分隔):");
    scanf("%d%s%d",&num1,&name1,&age1);
    while(age1>0){
        p1 = (struct student*)malloc(sizeof(struct student));
        p1->num = num1;
        strcpy(p1->name,name1);
        p1->age = age1;
        p1->next = NULL;
        if(head == NULL){
            head = p1;
        }else{
            p2->next = p1;
        }
        p2 = p1;
        printf("请输入第%d个学生的学号、姓名、年龄(用空格分隔):",++count);
        scanf("%d%s%d",&num1,&name1,&age1);
    }
    return head;
}

//2. 与建立顺序相同输出学生信息
void displayList(struct student *head){
    struct student *p;
    int n = 0;
    if(head!=NULL){
        printf("顺序输出链表中学生信息如下:\n");
        for(p=head;p!=NULL;p=p->next){
            printf("学号:%-6d 姓名:%-20s 年龄:%-6.1d\n",p->num,p->name,p->age);
            n++;
        }
        printf("学生总数:%d\n",n);
    }else{
        printf("空链表!\n");
    }
}

//3. 根据学号删除对应学生信息
struct student *deleteNodes(struct student *head){

    struct student *p1;
    struct student *p2;

    int num2;//要删除学生的学号 
    printf("请输入要删除学生的学号:");
    scanf("%d",&num2);

    if(head == NULL){
        printf("链表为空\n");
        return head;
    }
    p2 = head;

    while(num2!=p2->num&&p2->next!=NULL){ //查找要删除的节点 
        p1 = p2;
        p2 = p2->next;
    } 

    if(num2 == p2->num){
        if(p2 == head){ //要删除的是头节点 
            head = p2->next;
        }else{ //其他节点 
            p1->next = p2->next;
        }
        free(p2);
        printf("删除了学号为%d的学生信息!\n",num2);
    }else{
        printf("该生不存在!\n");
    }
    return head;
}

//4. 根据学号的大小插入某个学生的信息
struct student *insertNodes(struct student *head){
    struct student *p;//待插入节点
    struct student *p1;//待插入节点的前驱节点 
    struct student *p2;//待插入节点的后继节点 
    p2 = head;
    p = (struct student *)malloc(sizeof(struct student));
    printf("请输入要加入学生的学号、姓名、年龄:");
    scanf("%d%s%d",&p->num,&p->name,&p->age);
    if(head == NULL){ //若为空链表,则相当于创建一个新节点 
        head = p;
        p->next = NULL;
    }else{
        while(p->num > p2->num&&p2->next!=NULL){ //查找待插入的位置 
            p1 = p2;
            p2 = p2->next;
        }
        if(p->num < p2->num){ //头节点和中间任意节点的插入 
            if(p == head){ //头节点 
                head = p;
                p->next = p1;
            }else{ // 中间任意节点 
                p1->next = p;
                p->next = p2; 
            }    
        }else{//尾节点的插入 
            p2->next = p;
            p->next = NULL;
        }    
    }
     return head;
}

//5. 根据学号查找对应学生的其他信息
void search_student_info(struct student *head){
    struct student *p;
    int num;//要查找对应学生的学号信息
    printf("请输入要查找学生的学号:");
    scanf("%d",&num); 
    p = head;
    //非空链表的情况下 
    if(head != NULL){
        while(p->num!=num&&p->next!=NULL){
            p=p->next;
        }
        //不满足while循环的第一个条件 
        if(p->num==num){
            printf("你所查找的学号为%d的学生信息如下:\n",num);
            printf("学号:%-6d 姓名:%-20s 年龄:%-6.1d\n",p->num,p->name,p->age);
        }else{
            //不满足while循环的最后一个条件 
            printf("没有找到学号为%d的学生信息,请确认学号是否正确!\n",num);
        }
    }else{//空链表的情况 
        printf("空链表!");
    }        
}

//6. 根据学号修改学生信息
void modify_student_info(struct student *head){
    struct student *p;
    int num;
    char name[20];
    int age;
    printf("请输入您要修改学生的学号:");
    scanf("%d",&num);
    p = head;
    if(head!=NULL){
        while(p->num!=num&&p->next!=NULL){
            p = p->next;
        }
        if(p->num==num){
            printf("请输入您要更改后的信息:\n");
            scanf("%d%s%d",&num,&name,&age);
            p->num = num;
            strcpy(p->name,name);
            p->age = age;
        }else{
            printf("没有找到学号为%d的学生信息,请确认学号信息是否正确!\n");
        }
    }else{
        printf("空链表\n");
    }


}

//7. 与建立顺序相反输出学生信息
struct student *reverseList(struct student *head){ 
    /*
        1. 借助递归 
    */
    /*
    struct student *p;
    p = head;
    if(p!=NULL){
        reverseList(p->next);
        printf("学号:%-6d 姓名:%-20s 年龄:%-6.1d\n",p->num,p->name,p->age);
    }
    */

    /*
        2. 借助栈  
    */
    struct student *p;
    p = head;
    stack<int> s;
    while(p!=NULL){
        s.push(p->num);
        p = p->next;    
    }
    while(!s.empty()){
        p = head;
        while(s.top()!=p->num){
            p = p->next;
        }
        if(s.top()==p->num){
            printf("学号:%-6d 姓名:%-20s 年龄:%-6.1d\n",p->num,p->name,p->age);
        }
        s.pop();
    }
    return head; 

    /*
        3. 改变单链表指针指向 
        改变指针指向后,原链表也会被修改 
    */

    /*
    struct student *pre;
    struct student *post;
    struct student *p;
    pre = NULL;
    post = NULL;
    while(head!=NULL){
        post = head->next;
        head->next = pre;
        pre = head;
        head = post;
    } 
    return pre;
    */

}

//8. 清空整个链表
struct student *destroyList(struct student *head){
    struct student *p;
    p = head;
    if(p==NULL){
        printf("空链表!\n");
    }
    while(p!=NULL&&p->next!=NULL){
        p = p->next;
        free(p);
    } 
    printf("信息删除完毕!\n");
    head = NULL;
    return head;
}

二、单循环链表的基本操作

/*
    单向循环链表的建立与遍历 
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct student{
    int num;
    char name[20];
    struct student *next;
}; 
struct student *createList(); //建立循环链表 
void displayList(struct student *head); //输出循环链表(注意与单链表结束的不同条件) 
void isEmpty(struct student *head); //判断链表是否为空
struct student *deleteNode(struct student *head);//删除节点 
struct student *head = NULL;

int main(){
    int select;
    do{
        printf("请输入select的值:");
        scanf("%d",&select);
        switch(select){
            case 1:
                head = createList();
                break;
            case 2:
                displayList(head);
                break;
            case 3:
                isEmpty(head);
                break; 
            case 4:
                head = deleteNode(head);
                break; 
        }
    }while(select!=0);
    return 0;
}

//建立循环链表 
struct student *createList(){
    struct student *head;
    struct student *p1;
    struct student *p2;
    head = (struct student*)malloc(sizeof(struct student));
    head->next = head;
    p2 = head; 
    int num;
    char name[20];
    int count = 1; 
    printf("请输入第1个学生的学号、姓名(用空格分隔):");
    scanf("%d%s",&num,&name);
    while(num!=0){
        p1 = (struct student *)malloc(sizeof(struct student));
        p1->num = num;
        strcpy(p1->name,name);
        p1->next = head; //让每次新生成的节点的next域指向头节点 
        p2->next = p1;   
        p2 = p1;
        printf("请输入第%d个学生的学号、姓名(用空格分隔):",++count);
        scanf("%d%s",&num,&name);
    } 
    return head;
} 


//单向循环链表的遍历
void displayList(struct student *head){
    struct student *p;
    //由于头节点不存储数据信息,因此从头节点的下一个节点循环遍历,当遍历到头节点时,代表循环结束 
    for(p = head->next;p!=head;p=p->next){
        printf("学号:%-6d 姓名:%-20s\n",p->num,p->name); 
    } 
}

//单向循环链表的判空 
void isEmpty(struct student *head){
    struct student *p;
    p = head;
    if(p->next == p){
        printf("空链表\n"); 
    }else{
        printf("链表不为空哟~\n");
    } 
} 

//单向循环链表的删除 
//struct student *deleteNode(struct student *head){
//    //根据输入的学号删除对应的节点
//    struct student *p1;
//    struct student *p2; 
//    int num;
//    printf("请输入要删除学生的学号:");
//    scanf("%d",&num);
//    
//    p2 = head->next;
//    p1 = head;
//    while(num!=p2->num&&p2!=head){ //查找节点 
//        p1 = p2;
//        p2 = p2->next;
//    }
//    if(num==p2->num){
//        p1->next = p2->next; 
//        p2 = p2->next;
//        free(p2);
//        printf("删除了学号为%d的学生信息\n",num);
//    }else{
//        printf("该生不存在!\n");
//    }
//    return head; 
//     
//} 
//
//

三、双向链表的基本操作

/*
    双向链表
*/

#include<stdio.h>
#include<stdlib.h>

struct student{
    int num;
    struct student *pre;
    struct student *next;
};

struct student *createList(); //双向链表的建立 
void displayList(struct student *head); //顺序输出双向链表
void reverseList(struct student *p1); //逆序输出单向链表 
struct student *head = NULL;

int main(){
    int select;
    do{
        printf("请输入select的值:");
        scanf("%d",&select);
        switch(select){
            case 1:
                head = createList();
                break;
            case 2:
                displayList(head);
                break;
            case 3:
                reverseList(head);
                break; 
        }
    }while(select!=0);
    return 0;
}

//双向链表的建立 
struct student *createList(){
    struct student *p1;
    struct student *p2;
    struct student *head;
    int num;
    head = (struct student *)malloc(sizeof(struct student));
    p2 = head;
    p2->next = p2;
    p2->pre = NULL;
    int count = 1;
    printf("请输入第1个学生的学号:");
    scanf("%d",&num);
    while(num!=0){
        p1 = (struct student *)malloc(sizeof(struct student));
        p1->num = num;
        p2->next = p1;
        p1->pre = p2;
        p1->next = p1;
        p2 = p1;
        printf("请输入第%d个学生的学号:",++count);
        scanf("%d",&num);
    }
    p2->next = NULL;
    return p2;
} 

//双向链表的顺序遍历
void displayList(struct student *head){
    struct student *p;
    for(p=head->next;p!=NULL;p=p->next){
        printf("学号:%d\n",p->num);
    }
}
//双向链表的逆序遍历
void reverseList(struct student *p1){
    struct student *p;
    for(p=p1;p->pre!=NULL;p=p->pre){
        printf("学号:%d\n",p->num);
    } 
}

四、双向循环链表的基本操作

/*
    双向循环链表 
*/

#include <stdio.h>
#include <stdlib.h>

struct student{
    int num;
    struct student *pre;
    struct student *next;
};

struct student *createList(); //建立双向循环链表 
void displayList(struct student *head); //顺序输出链表
void reverseList(struct student *head);// 逆序输出链表 
struct student *deleteNode(struct student *head);//删除节点信息 
struct student *insertNode(struct student *head);//插入节点信息 
struct student *destroyList(struct student *head);//销毁链表 
struct student *head = NULL;

int main(){
    int select;
    do{
        printf("请输入select的值:");
        scanf("%d",&select);
        switch(select){
            case 1:
                head = createList();
                break;
            case 2:
                displayList(head);
                break;
            case 3:
                reverseList(head);
                break;
            case 4:
                head = deleteNode(head);
                break; 
            case 5:
                head = insertNode(head);
                break;
            case 6:
                head = destroyList(head);
                break; 
        }
    }while(select!=0);
    return 0;
}


//双向循环链表的建立 
struct student *createList(){
    struct student *p1;
    struct student *p2;
    struct student *head;
    int num;//学号
    int count = 1;//计数器--统计学生个数 
    head = (struct student *)malloc(sizeof(struct student));
    p2 = head;
    p2->next = p2;
    p2->pre = p2;

    printf("请输入第1个学生学号:");
    scanf("%d",&num);
    while(num!=0){
        p1 = (struct student *)malloc(sizeof(struct student));
        p1->num = num;
        p2->next = p1;
        p1->pre = p2;
        p1->next = head;
        head->pre = p1;
        p2 = p1;
        printf("请输入第%d个学生学号:",++count);
        scanf("%d",&num); 
    } 
    return head;
}


//双向循环链表的顺序遍历
void displayList(struct student *head){
    struct student *p;
    if(head->next == head){
        printf("空链表~\n");
    }
    for(p = head->next;p!=head;p=p->next){
        printf("学号:%d\n",p->num);
    }    
}

//双向循环链表的逆序遍历
void reverseList(struct student *head){
    struct student *p;
    for(p=head->pre;p!=head;p=p->pre){
        printf("学号:%d\n",p->num);
    } 
}

//双向链表的删除(根据学号删除)
struct student *deleteNode(struct student *head){
    /*
        温馨提示:双向链表的删除不同于单向链表,在单向链表中需要p1、p2两个指针变量,因为在单向链表中无法访问前驱节点,而在双向链表中则不需要. 
    */
    struct student *p;
    p = head->next;
    int num;//要删除的学号
    printf("请输入您要删除的学生学号:");
    scanf("%d",&num);
    while(num!=p->num&&p!=head){
        p = p->next;
    }
    if(num==p->num){//找到节点并删除 
        p->pre->next = p->next;
        p->next->pre = p->pre;
        free(p);
        printf("删除了学号为%d的学生的信息\n",num);
    }else{
        printf("请输入正确的学号信息哟~亲\n");
    }
    return head;
} 


//双向链表的插入(根据学号大小插入)
struct student *insertNode(struct student *head){
    struct student *p; //循环遍历链表使用
    struct student *pNew;//新生成的节点
    p = head->next;
    int num;//要插入的学生的学号 
    pNew = (struct student*)malloc(sizeof(struct student)); 
    printf("请输入你要加入学生的学号:");
    scanf("%d",&num);
    pNew->num = num; 
    while(num>p->num&&p!=head){ //查找正确的位置 
        p = p->next;
    } 
    pNew->pre = p->pre;
    p->pre->next = pNew;
    pNew->next = p;
    p->pre = pNew; 
    return head;
}

//双向链表的销毁
struct student *destroyList(struct student *head){
    struct student *temp;
    struct student *p;
    temp = head->next;
    while(temp!=head){
        p = temp;
        temp = temp->next;
        printf("%d",p->num);
        free(p);
    } 
//    head->next = head->pre = head;
    printf("链表已清空!\n");
    return head;
} 

五、带头节点的链表

/*
    创建带头节点的链表 
*/


#include<stdio.h>
#include<stdlib.h>

struct student{
    int num;
    struct student *next; 
};

struct student *createList();
void displayList(struct student *head);
struct student *head = NULL;

int main(){
    int select;
    do{
        printf("请输入select的值:");
        scanf("%d",&select);
         switch(select){
             case 1:
                 head = createList();
                 break;
             case 2:
                 displayList(head);
                 break;
         }
    } while(select!=0);
}



struct student *createList(){
    struct student *head;
    struct student *p1;
    struct student *p2;
    head = (struct student*)malloc(sizeof(struct student));
    head->next = NULL;
    p2 = head;
    int num;
    printf("请输入num的值:");
    scanf("%d",&num);
    while(num!=0){
        p1 = (struct student *)malloc(sizeof(struct student));
        p1->num = num;
        p1->next = NULL;
        p2->next = p1;
        p2 = p1;
        printf("请输入num的值:");
        scanf("%d",&num);
    }
    return head;
}

void displayList(struct student *head){
    struct student *p;
    for(p = head->next;p!=NULL;p = p->next){
        printf("学号:%2d\n",p->num);    
    }
}

评论加载中