数据结构与算法-实验1链表的建立与操作

╰+哭是因爲堅強的太久メ 2023-10-01 12:52 10阅读 0赞

#### **实验目的**： 掌握链表数据结构的建立及操作 ####

#### **实验重点**： 利用链表的原空间进行链表的反转 ####

#### **实验内容**：设计一个将输入数据建立成链表、并依次输出链表数据、利用原空间把链表反转的程序。 ####

#### **实验步骤****：** ####

1.  掌握链表的数据结构
2.  建立空链表
3.  用头插法向链表插入数据，实验数据:  
    验证数据：20，20，17，16，15，15，11，10，8，7，7，5，4
4.  依次输出链表中的数据
5.  利用链表原空间进行对链表进行反转
6.  依次输出反转后的链表数据，以判断反转操作的正确性，**注意反转后，链表的第一个和最后一个元素是否正确**

7，进阶要求：删除无序链表的重复元素。

#### **实验提示:** ####

见ppt

#### **程序流程图**： ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16][]

#### **程序代码**： ####

#include<stdio.h>
    #include<stdlib.h>
    #include<conio.h>
    typedef struct Number{
        int num;
    }Num;
    typedef struct NumNode{
        Num number;
        struct NumNode*pNext;
    }Node;
    Node *g_head=NULL;
    Node *prev = NULL;
    void inputnumber();
    void printnumber();
    void reverse();
    void dele();
    void freelink();
    int main(){
        while(1){
            int n;
            printf("请选择功能\n");
            printf("1.输入链表数据\n");
            printf("2.反转链表\n");
            printf("3.删除链表相同元素\n");
            printf("4.输出链表数据\n");
            scanf("%d",&n);
            if(n==1)
                inputnumber();
            else if(n==2)
    			reverse();	 
    		else if(n==3)
    			dele();
    		else if(n==4)
                printnumber();
        }
        void freelink();
        return 0;
    }
    void inputnumber(){
    	int q,i=0;
    	printf("请输入链表元素个数："); 
    	scanf("%d",&q);
        while(i<q){
        	//头插法建立空链表 
    		Node* pnewNode=(Node*)malloc(sizeof(Node));
    		scanf("%d",&pnewNode->number.num);
    		pnewNode->pNext=g_head;
    		g_head=pnewNode;
    		i++;
    	}
    	printf("\n");
    	system("pause");
    }
    
    void printnumber(){
        Node *p=g_head;
        while(p!=NULL){
            printf("%d  ",p->number.num);
            p=p->pNext;
        }
    	//printf("%d",g_head->number.num);
    	printf("\n\n");
    	system("pause");
    }
    void reverse(){   
        Node *curr =g_head;   
        while (curr != NULL) {  
            Node *nextTemp = curr->pNext;
            curr->pNext = prev;
            prev = curr;
            curr = nextTemp;
        }
        g_head=prev;
        printf("链表反转成功\n\n");
        system("pause");
    }
    void dele(){
    	Node *p=g_head,*q=NULL,*r=NULL,*t=NULL;
        while(p!=NULL){
        	q=p;
        	r=q->pNext;
        	while(r!=NULL){
        		if(r->number.num==p->number.num){
        			t=r;
        			r=r->pNext;
        			q->pNext=r; 
        			free(t);
    			}
    			else{
    				q=r;
    				r=r->pNext;
    			}
    		}
    		p=p->pNext;
    	}
    	printf("删除相同元素成功\n\n");
    	system("pause");
    }
    void freelink(){
    	Node *p;
    	while(g_head!=NULL){
    		p=g_head;
    		g_head=p->pNext;
    		free(p);
    	}
    }

#### **运行结果及分析**： ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

头插法进行链表元素的输入，然后输出链表，对链表进行反转，然后输出，对链表进行相同元素的删除和内存的释放，然后输出。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

头插法进行链表元素的输入，然后输出链表，对链表进行相同元素的删除和内存的释放，然后输出。对链表进行反转，然后输出。

#### **心得体会**： ####

对C语言的链表进行深刻复习，进一步加强了链表的建立和删除与反转，而且对链表的结构和算法进行深度学习，对算法有了初步的学习，得以加强。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/88381d85df5c48a0a8ea56752c53fbe5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bmz5p2o54yq,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/4bc71fbaa5da4b269cd10727262ba21f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bmz5p2o54yq,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bmz5p2o54yq_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/344347c1e4f548788cdabc9d3d73cea0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bmz5p2o54yq,size_20,color_FFFFFF,t_70,g_se,x_16