資料結構順序表元素整體互換和單連結清單插入練習

線性表用順序存儲，設計一個算法，用盡可能少的輔助存儲空間将順序表中前m個元素與後n個元素進行整體互換，即将線性表

（a1,a2,a3,......,am,b1,b1,b3,......,bn)

  (b1,b2,b3,.......,bn,a1,a2,a3,.......,am)

#include <stdio.h>
#include <stdlib.h>
#define Num 100
typedef struct
{
    char data[Num];
    int last;
} seqlist;
seqlist* init (seqlist*l,int arrsize)
{
    l=(seqlist*)malloc(sizeof(seqlist));
    l->last=arrsize-1;
    return l;
}
seqlist* getresult(seqlist*s,int m,int n)
{
    int x,j,i=0;
    if(m<n)
    {
        for(i=0; i<m; i++) //移動m次
        {
            x=s->data[0];
            for(j=1; j<=s->last; j++)
            {
                s->data[j-1]=s->data[j];//從第二個數開始全體向前移動
            }
            s->data[s->last]=x;
        }
    }
    else
    {
        for(i=0; i<n; i++) //移動n次
        {
            x=s->data[s->last];
            for(j=s->last-1; j>=0; j--)
            {
                s->data[j+1]=s->data[j];//從倒數第二個數開始之前的數往後移
            }
            s->data[0]=x;
        }
    }
    return s;
}
int main()
{
    seqlist *s;
    int m,n,i;
    scanf("%d %d",&m,&n);
    s=init(s,m+n);
    for(i=0; i<=s->last; i++)
    {
        scanf(" %c",&s->data[i]);//前有一個空格，處理字元空格
    }
    s=getresult(s,m,n);
    for(i=0;i<=s->last;i++)
    {
        printf("%c ",s->data[i]);
    }
    return 0;
}
           

 已知帶頭結點的單連結清單L中的結點是按整數遞增排列的。試寫一算法，将值為x的結點插入到表L中，使得表L仍然遞增有序。

這是原題中帶有頭結點的做法，與不帶頭結點稍有差異，注意差別，展現在 creat函數和插入數之前的處理。

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}Lnode,*Lnode1;
Lnode* init()
{
    Lnode *s;
    s=(Lnode1)malloc(sizeof(Lnode));
    s->data=0;
    s->next=NULL;
    return s;
}
Lnode1 creat()
{
    Lnode* s,*r;Lnode1 L;
    //Lnode1 L=NULL;
    int x,flag=1;
    L=(Lnode1)malloc(sizeof(Lnode));
    L->next=NULL;
    r=L;
    printf("input the num of -1 to stop\n");
    scanf("%d",&x);
    while(flag)
    {
        s=(Lnode1)malloc(sizeof(Lnode));
        s->data=x;
        s->next=NULL;
        r->next=s;
        r=s;
        scanf("%d",&x);
        if (x==-1)
        {
            flag=0;
        }
    }
    return L;
}
Lnode1 insert(Lnode* L,int x)
{
    Lnode* p,*q,*s;
    s=(Lnode1)malloc(sizeof(Lnode));
    p=L;
    q=p;//q為p的前驅結點
    while(p->data<x)
    {
        q=p;
        p=p->next;
    }
    s->data=x;
    s->next=q->next;
    q->next=s;
    return L;
}
int main()
{
    Lnode* s,*r;
    int x;
    s=creat();
    printf("please give the num you want to insert\n");
    scanf("%d",&x);
    r=s->next;//有頭結點，頭結點的資料是随機的，是以指向第一個結點
    s=insert(r,x);
    while(s)
   {
       printf("%d ",s->data);//這裡不先寫下式，是因為頭結點已經處理，是以直接列印
       s=s->next;
   }
    return 0;
}
           

 不帶頭節點的做法，注意建立時第一個結點的處理

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}Lnode,*Lnode1;
Lnode* init()
{
    Lnode *s;
    s=(Lnode1)malloc(sizeof(Lnode));
    s->data=0;
    s->next=NULL;
    return s;
}
Lnode1 creat()
{
    Lnode* s,*r=NULL;Lnode1 L=NULL;
    int x,flag=1;
    printf("input the num of -1 to stop\n");
    scanf("%d",&x);
    while(flag)
    {
        s=(Lnode1)malloc(sizeof(Lnode));
        s->data=x;
        if(L==NULL)L=s;//第一個結點處理
        else r->next=s;
        r=s;
//        s->next=L;
//        L=s; //頭插
        scanf("%d",&x);
        if (x==-1)
        {
            flag=0;
        }
    }
    if(r!=NULL) r->next=NULL;
    return L;
}
Lnode1 insert(Lnode* L,int x)
{
    Lnode* p,*q,*s;
    s=(Lnode1)malloc(sizeof(Lnode));
    p=L;
    q=p;//q為p的前驅結點
    while(p->data<x)
    {
        q=p;
        p=p->next;
    }
    s->data=x;
    s->next=q->next;
    q->next=s;
    return L;
}
int main()
{
    Lnode* s;
    int x;
    s=creat();
    printf("please give the num you want to insert\n");
    scanf("%d",&x);//輸入的是遞增的資料
    s=insert(s,x);
    while(s)
   {
       printf("%d ",s->data);
       s=s->next;
   }
    return 0;
}