C语言——线性表及其应用（单链表和顺序表）

ゝ一纸荒年。 2023-06-21 07:21 19阅读 0赞

## 程序要求 ##

1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。  
2.利用前面的实验先建立一个顺序表L=\{21，23，14，5，56，17，31\}，然后在第i个位置插入元素68。  
3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。  
输入和输出的格式

# 1.顺序线性表的建立、插入及删除 #

**顺序表**

#include<stdio.h>
    #include<stdlib.h>
    
    #define ListSize 50
    typedef int DataType;
    
    //线性表的顺序存储方式
    typedef struct {
        
    DataType data[ListSize];
    int l;
    }SeqList;
    
    
    //创建顺序线性表
    void CreateList(SeqList *A,int n)
    {
        
    int i;
    for(i=0;i<n;i++)
    {
        
    scanf("%d",&(A->data[i]));
    }
    A->l=n;
    }
    
    
    //在顺序线性表中插入某个元素
    void InsertList(SeqList *A,DataType x,int i)
    {
        
    int j;
    if(i<1 || i>A->l)       //插入时的条件
    {
        
    printf("插入位置错误!\n");
    exit(0);
    }
    else
    {
        
    printf("插入成功!\n");
    }
    if(A->l >= ListSize)
    {
        
    printf("列表溢出!\n");
    exit(0);
    }
    for(j=A->l-1;j>=i-1;j--)
    {
        
    A->data[j+1]=A->data[j];          //插入时，把各个元素向后移动后，然后在进行插入
    }
    A->data[i-1]=x;
    A->l++;
    }
     
    
    //在顺序线性表中删除某个元素
    void DeleteList(SeqList *A,int i)
    {
        
    int j;
    if(A->l==0)                     //删除时的条件
    {
        
    printf("列表为空!\n");
    exit(0);
    }
    if(i<1 || i>A->l)
    {
        
    printf("删除位置错误!\n\n");
    exit(0);
    }
    for(j=i;j<=A->l-1;j++)      //删除时，把各个元素向前移动，覆盖掉要删除的元素
    {
        
    A->data[j-1]=A->data[j];
    }
    A->l--;
    }
    
    //输出线性表
    void DisList(SeqList *L)
    {
        
    int i;
     for(i=0;i<L->l;i++)
    printf("%d ",L->data[i]);
    printf("\n");
    }
    
    
    void main()
    {
        
    SeqList *A=(SeqList*)malloc(sizeof(SeqList));    
    int a=7;
    printf("请输入7个整型元素:\n");
         CreateList(A,a);
    printf("输出SeqList的长度: \n");
    printf("长度=%d\n",A->l);
    printf("表内元素为");
         DisList(A);
    DataType x;
    printf("请输入需要插入的元素的位置!\n");
    int i;
    scanf("%d",&i);
    printf("请输入需要插入的元素!\n");
    scanf("%d",&x);
         InsertList(A,x,i);
    printf("长度=%d\n",A->l);
    printf("表内元素为");
         DisList(A);
    printf("请输入需要删除的元素的位置!\n");
    scanf("%d",&i);
         DeleteList(A,i);
    printf("表内元素为");
         DisList(A);
    printf("长度=%d\n",A->l);
    }

**输入和输出的格式**  
顺序表输入输出：定义输入7个整型元素，回车进行插入和删除，输出线性表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

# 2.链式线性表的建立、插入及删除 #

**单链表**

#include <stdio.h>
    #include <stdlib.h>
     
    typedef int ElemType;
     
    //定义结点类型 
    typedef struct Node
    {
        
        ElemType data;              //单链表中的数据域 
        struct Node *next;          //单链表的指针域 
    }Node,*LinkedList;
     
     //单链表的初始化
    LinkedList LinkedListInit()
    {
        
        Node *A;
        A = (Node *)malloc(sizeof(Node));   //申请结点空间 
        if(A == NULL)                       //判断是否有足够的内存空间 
        printf("申请内存空间失败\n");
        A->next = NULL;                     //将next设置为NULL,初始长度为0的单链表 
     return A;
    }
     
    
     //单链表的建立
    LinkedList LinkedListCreat()
    {
        
        Node *A;
        A = (Node *)malloc(sizeof(Node));   //申请头结点空间
        A->next = NULL;                     //初始化一个空链表
        Node *r;
        r = A;                              
        ElemType x;                        
        while(scanf("%d",&x) != EOF)
        {
        
            Node *p;
            p = (Node *)malloc(sizeof(Node));   
            p->data = x;                      
            r->next = p;                   
            r = p; 
        }
        r->next = NULL; 
        return A;   
    }
     
    
     //单链表的插入，在链表的第i个位置插入x的元素
    LinkedList LinkedListInsert(LinkedList A,int i,ElemType x)
    {
        
        Node *pre;                            //pre为前驱结点 
        pre = A;
        int tempi = 0;
        for (tempi = 1; tempi < i; tempi++)
            pre = pre->next;                  //查找第i个位置的前驱结点 
        Node *p;                              //插入的结点为p
        p = (Node *)malloc(sizeof(Node));
        p->data = x; 
        p->next = pre->next;
        pre->next = p;
        return A;                           
    } 
     
    
     //单链表的删除，在链表中删除数据值为x的元素
    LinkedList LinkedListDelete(LinkedList A,ElemType x)
    {
        
        Node *p,*pre;                     //pre为前驱结点，p为查找的结点。 
        p = A->next;
        while(p->data != x)              //查找值为x的元素 
        {
           
            pre = p; 
            p = p->next;
        }
        pre->next = p->next;          //删除操作，将其前驱next指向其后继。 
        free(p);
        return A;
    } 
     
     int main()
    {
        
        LinkedList list,start;
        printf("请输入需要添加单链表的数据："); 
        list = LinkedListCreat();
        for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
        printf("\n");
     
        int i;
        ElemType x;
        printf("请输入需要插入数据的位置：");
        scanf("%d",&i);
        printf("请输入需要插入数据的值：");
        scanf("%d",&x);
        LinkedListInsert(list,i,x);
        for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
        printf("\n");
        printf("请输入需要删除的数据的值：");
        scanf("%d",&x);
        LinkedListDelete(list,x); 
        for(start = list->next; start != NULL; start = start->next)
        printf("%d ",start->data);
        printf("\n");
        return 0;
    }

**输入和输出的格式**  
单链表输入输出：本程序可以输入多个整型数据元素  
请输入第一个整数，回车输入下一个数  
请输入第二个整数…最后输入Ctrl+z结束输入,进行插入和删除，最后输出单链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]  
[博客园][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191211170957692.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191211171653282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[Link 1]: https://www.cnblogs.com/zhangyuan1024/